History has taught us: never underestimate the amount of money, time, and effort someone will expend to thwart a security system. It's always better to assume the worst. Assume your adversaries are better than they are. Assume science and technology will soon be able to do things they cannot yet. Give yourself a margin for error. Give yourself more security than you need today. When the unexpected happens, you'll be glad you did.

Introduction

Cryptographic primitives such as block ciphers, stream ciphers, hash functions, key exchanges and digital signatures are the fundamental building blocks which modern computer security is built from. A secure cryptographic primitive on its own cannot guarantee security. Conversely a weak cipher offers no security or worse, the illusion of security.

Cryptographic security has historically been a moving target. Cryptographic security is influenced by advances in cryptanalysis (mathematical attacks against ciphers), advances in computing power and advances in our understanding of physics. Today we are entering into the next great shift in cryptography. To quote an official publication of the European Network of Excellence for Cryptology (ECRYPT), a European FP7 program that coordinates over 32 organisations including Ericsson AB (Sweden), France Telecom, Gemalto, IBM Research GmbH (Switzerland), MasterCard Europe sprl (Belgium), Vodafone Group Services Ltd (UK) and over 20 leading European universities:

Advances have often been done in steps, and beyond approximately 10 years into the future, the general feeling among ECRYPT partners is that recommendations made today should be assigned a rather small confidence level, perhaps in particular for asymmetric primitives. ... For instance, signing a message both with RSA and discrete logarithm technology does not offer any additional security if quantum computers become a reality.

In this short web article we will explore the advances that are leading to greater discomfort and uncertainty in the global cryptographic community and the strategy Synaptic proposes to comprehensively manage these known risks on the event horizon.

The widely acknowledged threat of code breaking quantum computers

So the threat to cryptography is well understood due to work by Peter Shor and others. A symmetric algorithm like AES or others standard crypto processes is cut (of) key-size in half, which is a dramatic reduction. It reduces AES on 128 (bit key) to 64 bits, a DES equivalent. We don’t need it.

So during the AES competition we put in an insurance policy. It was the right thing to do, because it had not yet been built and you have to take care of what you can think of in the long range future. If quantum computing came to be, they said put in a key size 256 (bits). We don’t need it now, its an absurd number, alright, but if quantum computing comes to be, it drops us to 128, a nice healthy number, still quite useable thank you, we can keep going and its no longer a threat.

So it was a marvelous response to quantum computing.

Now for key management purposes, against the RSA and the Diffie-Hellman and stuff, they flat-line under a quantum computer. It’s not just a cut (of) the key size in half.

It is these new quantum algorithms that threaten today's mainstream cryptographic systems. The arrival of code breaking quantum computers implies that all recorded Internet traffic that is secured using our mainstream cryptographic systems can then be decrypted at will.

The uncomfortable problem that the cryptographic community has faced until just recently (2008) is that the community did not have a viable solution to this threat. Professor Jacques Patarin (University of Versailles-Saint-Quentin-en-Yvelines in France) and Louis Goubin (also UoV) are designers of several candidate post quantum secure key exchanges based on MVQS techniques. They advise in a report to Synaptic:

Currently there is no known (symmetric or asymmetric) key exchange technology suited for replacing RSA, D&H, and ECC to support key exchanges between potentially billions of users within one system like the Internet. So far, we are not aware of any publications with provably secure algorithms in this model. This is not just our opinion.

This opinion is also echoed by Brian Snow (former US NSA director) at the 30th anniversary of PKI conference:

So this becomes an invitation to the research community to get cracking lads. We need new algorithms that are robust at least to the square root factor under a quantum computer attack that can be used for non-repudiation, and public key processes.

Open problem. Aching problem – work on it, please!

Today Synaptic Laboratories Limited offer the world's first viable high assurance solution to this problem.

The anticipated timeline for code breaking quantum computers

The rapidly evolving field of quantum computers is one of the most active research areas of modern science, attracting substantial funding that supports research groups at internationally leading academic institutions, national laboratories, and major industrial-research centers.

Even with the enormous research efforts currently underway there is significant uncertainty as to when large quantum computers might arrive. In 2003 prominent experts involved in the design of quantum computers published that it might take 10 to 100 years before large quantum computers could be built. Therefore the warning flag was raised that our security systems were at risk of catastrophic failure perhaps as early as 2013.

The most comprehensive authoritative report and time estimate our survey identified was from 2004. A report of the Quantum Information Science and Technology Experts Panel of the U.S. Advanced Research and Development Activity [see wiki: Disruptive_Technology_Office] under the auspices of the United States Army, Air Force, Navy, and the US National Science Foundation states in section 6.9 that it might be a decade or two before large quantum computers arrive.

In May 2008 Prof. Seth Lloyd of MIT, a coauthor of the ARDA Report, estimates that “at current rates of progress, big, code-breaking quantum computers are at least a decade away”.

As of Aug 2008 Andrew Shields, leader of the quantum information group at Toshiba’s Cambridge Research lab, Andrew is of the opinion that “the use of quantum information technologies in business computing will become a reality in the next 10 years”.

These public estimates on the arrival of large quantum computers shed light on the original ECRYPT quote stating that recommendations made today should be assigned a rather small confidence level, perhaps in particular for asymmetric primitives.

However this is not the only the issue facing the cryptographic community.

The possibility of an unabated continuation of conventional computing power growth

Moore's law describes an important trend in the history of computer hardware: that the number of transistors that can be inexpensively placed on an integrated circuit is increasing exponentially, doubling approximately every two years. The trend has continued for more than half a century and is not expected to stop for another decade at least and perhaps much longer.

Many publications recommending key lengths of cryptographic primitives take into account the historical rate of computational improvement which is based on Moore’s law to determine how long a key length might be secure [see here, here, and here].

This type of analysis attempts to extrapolate future performance from the past rate of development. This type of approach cannot take into account disruptive advances in science and technology. For example according to a press announcement “a team of Michigan Technological University researchers led by physicist Ranjit Pati have developed a model to explain the mechanism behind the single molecular switch, widely considered to be computing's Holy Grail. If worked out experimentally, the model could help explode Moore's Law and revolutionize computing technology.”

Another example is that it is not known at what time computers will have greater computational ability than humans – or alternatively at what time computer enhanced humans will significantly exceed our current intelligence levels. One or more abrupt advances in computing power may occur as a result of AI [39, 36].

The situation is worse when we attempt to consider the interaction between Moore's law and quantum computing. Unfortunately it is not possible to project how fast quantum computing power might grow in the next year, five years or 20 years because, according to Prof. Scott Aaronson of MIT, “there is currently no analogue of Moore’s law for quantum computing”.

A conservative strategy to address both issues

An alternative approach to conventional thinking is to design cryptographic algorithms that would be secure against known classical and quantum computing attacks that operated at the known limits currently permitted by our understanding of physics.

Prof. Seth Lloyd explains “Computers are physical systems: what they can and cannot do is dictated by the laws of physics.” … “(I) explore the physical limits of computation as determined by the speed of light, the quantum scale and the gravitational constant. As an example, quantitative bounds are put to the computational power of an ‘ultimate laptop’ with a mass of one kilogram confined to a volume of one liter.” It is estimated by Lloyd that this ultimate laptop has 10³¹ qubits, has 10¹⁰ degree of parallelism in each clock cycle and can perform a maximum of 10⁵¹ operations per second. That is about 2¹⁹³ gate operations per year."

Based on our extensive survey of the currently known quantum computing algorithms the most secure cryptographic primitives appear to be those based on mainstream symmetric techniques. That is, cryptographic block ciphers, stream ciphers and hash functions based on today's conservative mainstream design techniques appear to offer the best possible security against quantum algorithms.

According to Lov Grover's quantum search algorithm the security rating of 'ideal' block ciphers and stream ciphers against brute-force of quantum computer attacks is half the length of the key-length. A 512-bit key length offers 2²⁵⁶ security rating against Grover's algorithm and remain secure against a large cluster of Lloyd's ultimate laptops.

Selecting cryptography primitives that remain secure against the 'ultimate laptop' for more than a 100 years suggests that it will also remain secure against Moore’s law applied to classical computing for more than a 100 years with a high level of confidence.

Synaptic Labs' approach to the design of cryptographic systems

It has been known for over 30 years how to build privacy primitives, hash functions, digital signatures and key exchanges using symmetric key principles. However the techniques for digital signatures based on hash function were originally very inefficient and the techniques for scaling many-to-many key exchanges were limited by the requirement for a central trusted authority.

Researchers at Technischen Universität Darmstadt (TUD), Hitachi, RSA and IBM have incrementally improved the performance and efficiency of digital signatures based on the security of cryptographic hash functions to the point where today they are competitive with equivalent classically rated mainstream approaches.

Today Synaptic Laboratories has identified viable solutions for building scalable many-to-many key exchange technologies based on symmetric techniques.

By building complete systems based on conservative symmetric cryptographic primitives it is now possible to create a new security ecosystem capable of a 100 year security rating for the first time.