The future of cryptology: which 3 letters algorithm(s) could be our Titanic?

The format will be a co-presentation (Jean-Jacques Quisquater/David Samyde) and occasional friendly debate or exchange, with point and counter-point of different contrasting views on the impact of solving integer factorization in Information Security.

At the last RSA conference, Ronald Rivest, Adi Shamir and Leonard Adleman received the RSA Conference Lifetime Achievement Award. They were rewarded for the creation of the RSA cryptosystem and their magnificient contribution to the field of cryptography. Rivest during his speech said that it has not been demonstrated mathematically that factorization into primes is difficult. So "Factoring could turn out to be easy," and according to him "maybe someone here will find the method".

Since 1994 and Shor's algorithm, the cryptographic community is aware of the danger of quantum computer for the the integer factorization problem. With a sufficient number of qubits, Shor's algorithm can be used to break RSA in polynomial time. Since last year RSA conference the first commercially available quantum computer with 128-qubit chip has been sold to an american company. But some criticism and a controversy are present around the real potential of this solution.

A well accepted assumption is that factoring large numbers is computationally infeasible on classic non quantum computers. No classical algorithm is known and the research in the last 30 years did not show enormous progress even if the improvements to the field of integer factorization are important since the existence of RSA.

The consequences of solving integer factorization in polynomial time would be to render the RSA scheme vulnerable. According to Ron Rivest a variety of alternative schemes have been developed in the decades since RSA was published, and a new system could probably be adopted quickly.

Some new encryption/signature schemes are available but they do not all rely on some problems that can be proven to be very hard in all cases and instances. The difference between a solid proof and a conjecture is important but it is not because a problem is proven hard that it is enough and sufficient to use it to build a secure cryptosystem. The knapsack problem is NP-complete to solve exactly but it can be difficult to create a secure cryptosystem from it. Leonard Adleman broke the Ron Graham and Adi Shamir enhancement of the Merkle-Hellman scheme and so did Serge Vaudenay who broke the Chor-Rivest knapsack cryptosystem.

Discrete logarithm, graph isomorphism and integer factorization are NP-intermediate problems and they are not known to be to be P or NP-complete. Solving the discrete logarithm problem brings a solution to the integer factorization problem in a trivial manner. The lack of recent progress on the resolution of the discrete logarithm helps and supports integer factorization. But in general an advance in one of them can be translated into the other one. This is not automatic, however it can be expected.

Cryptographic problems rely massively on the integer factorization and discrete logarithm problems. Few other systems exist and amongst this group some algorithms suffer from cryptanalysis methods, reducing their usage to specific cases. The worldwide presence, acceptance and usage, of RSA are huge therefore if the algorithm would be compromised then a lot of companies would have no choice and would be forced to switch to another encryption system.

The quick and rapid adoption of a new system would play an important part in maintaining a high level of trust in security. Because public key cryptography secures Internet and ecommerce, banking and financial transactions, governments communications and much more, the new system(s) should be proven to be secure and quickly deployed.

The assumption of Ron Rivest about the difficulty of integer factorization relies on the fact that the solution to factorization would not create more perturbations in the field of encryption algorithms and would not enable new cryptanalytic methods on potential replacement solutions. In such a case his statement about replacing RSA with a new method is correct. However several other cases can be considered, and in some of them the action to replace RSA with a new algorithm could require more work than initially planned. In the same manner big companies can not really afford (and not only on the financial side) to replace one encryption algorithm by another one and to experience a failure of the new system just after its deployment.

This presentation challenges the conventional thinking, indeed factorization is at the core of number theory and a limited number of top researchers do really work and understand it. But a tremendous amount of money and business is secured relying on the resistance of this problem to years of attack by talented minds. The entire world use the RSA algorithm and trusts its security. This is so true that some scheme do not even plan a replacement plan and some certificates never expire.

In the greek mythology Cassandra received from Apollo the ability to predict the future, but she could not provide any evidence data of her predictions. She foresaw the destruction of Troy using the Trojan Horse, the death of Agamemnon, and her own troubles but she could not forestall these tragedies. Ron Rivest did not provide any new method to solve factorization but he clarified the possible existence of a solution. When the inventor of the system starts to consider that a solution can exits it seems to be time to be open minded. If a solution can be reached, so what?

Andrew Grove, former CEO of a silicon manufacturer highlighted in his book "Only the paranoid survive." the importance of Cassandras in an organization. According to Grove, they can help to predict a strategic inflection point.

Factorization in a practical manner would be a strategic inflection point but could also not be limited to integer factorization only and extend to other fields. A much more elegant method to the problem of the decomposition of a composite in primes even inspired movie makers and Hollywood (Sneakers by Phil Alden Robinson) or book writers (Tetraktys by Ari Juels). What is the reality of such an assumption, is this pure science or pure fiction. Are these people Cassandras or is it simply impossible ? Through the usage of comparisons and metaphors the authors deal with what would be the lessons to learn from the resolution of factorization in different cases.

It is difficult to make accurate predictions and cryptographers learned with time that even the most brilliant of them and/or the giants amongst the community can make bad predictions. The inventors of RSA stated in Martin Gardner's column (August 1977) of Scientific American that it would require 40 quadrillion years to factorize RSA-129 (426 bits). Derek Atkins lead the work that proved them wrong few years later.

The recent history of cryptanalysis teaches us that some schemes are weaker than expected and the general perception of the cryptologic community can be modified very quickly. A good example is the lack of collision resistance of the MD5 hash function designed by Ron Rivest.

The co authors believe that any prediction about the time separating us from the existence of an elegant solution to the integer factorization problems makes no sense. The art of prediction is much more difficult than doing simple comparisons.

The existence of a practical solution to factorize would have the effect of an earthquake to the world of cryptography and computer security. Predicting earthquake is not really possible and the recent past brings to our mind all the colateral effects that can be related to an earthquake. In real life seismologists monitor many phenomena that are considered to be possible precursors of earthquakes. This presentation will develop a simple model based on common sense to explain what could be the consequences of an improvement of integer factorization according to the probability of its apparition.

If the perception of the cryptologic community would be drastically modified about factorization, what could be the consequences on cryptography and security in the real world? Can the best practises used with RSA be improved or even translated into a new scheme? What would be the impact of solving the RSA assumption on numerous other algorithm ?

In the case of a resolution of the integer factorization problem, several scenari are possible. They all have different implications and conclusions. This presentation consider each main scenario according to a level of relevance and details the impact and the consequences of the new discovery on different fields including computer security, governance, cloud security, cyberwar and cyber weapons and other fields.

Managing the risk of the creation of a solution to any major problem used in cryptography is important for the whole industry. In general cryptographers consider that non linear improvements in their field take time and that all algorithm are deprecated before to be absolutely broken. This presentation will challenge some of these statements.