Quantum Computation: A cryptography armageddon?

Cryptography is a cornerstone of information security. It is used to encode and decode data in order to fulfil the requirement for confidentiality, integrity, authenticity as well as non-repudiation. Together, these are frequently referred to as cryptography services.

Advances in cryptanalysis, computer science and engineering are always pushing the limits of what is considered secure. RSA, which was once believed secure under 129 bit-keys, nowadays is not considered secure using keys smaller than 2,048 bits. MD5, which was designed in 1992 and had been one of the most widely used hash functions, was proven to be breakable (in the sense of collision-attack) in 2004. Likewise, freestart collision against SHA-1, which is somewhat easier to find than standard collisions, was demonstrated and published at Eurocrypt 2016.

One of the resources in the toolkit of cryptanalysts is quantum computing. Quantum computing is based on physical quantum properties to perform operations, which behaves differently than the electronic properties we are used to finding in today's computers and its basic unit of information, instead of bit, is called quantum bit or qubit. It started to be used in theoretical attacks against cryptosystems back in 1994, when Peter Shor published a quantum algorithm to find the prime factors of a given integer.

This algorithm enables the solving of integer factorisation and discrete logarithm problems, which are the basis of most (not to say all) widely used public-key cryptography algorithms. Less devastating in its impact but still of major importance, Grover's quantum algorithm enables a huge speedup in search algorithms that impacts the security of many cryptosystems, including AES. This leads us to make a fairly surprising statement: all major cryptographic algorithms in use today are (virtually) broken!

Today, the only mitigating factor is the absence of a quantum computer large enough to run such algorithms against the parameters currently in use by crypto algorithms.

In the landscape of quantum computing everything is evolving fast. In April 2016, the European Commission announced plans to invest one billion euros in an EU project for a "large-scale EU-wide quantum technologies flagship". As with this program, many others have been launched to fund the development of large-scale quantum computers.

Also in April 2016, researchers in Canada established a new record in quantum computer factorisation, after factoring the number 200,099 using a D-Wave 2X processor, although it is not clear whether D-Wave produces universal quantum computers able to run the Shor's algorithm. Furthermore, 200,099 is only an 18-bit number, way too small to need the computation power required to factor a 2,048-bit integer to break current RSA parameters.

The current stage of large-scale deployment of public key cryptosystems counts on pretty elderly algorithms like Diffie-Hellman (1976), RSA (1977) and Elliptic Curves (1985). The latter was first published more than 30 years ago, but has recently started to be deployed on a large scale.

To tackle the cryptography armageddon imposed by large-scale quantum computers, cryptographers around the world have been working for at least a decade to design and improve cryptosystems resistant to quantum attacks, known as post-quantum cryptography or PQCrypto. Many cryptosystems have been designed and even standardised, like NTRU, nonetheless confidence in such new cryptosystems takes time to earn by being thoroughly scrutinised over and over again until they are proven to be ready for large-scale deployment.

What is the current state of PQCrypto?

In 2006 the first PQCrypto Conference was hosted, bringing together researchers to look for secure alternatives against quantum computing attacks. At the time, some alternatives were already at hand, such as McEliece encryption (1978), and ever since many programs to fund research in PQCrypto have been launched. This includes the European Commission's SAFECrypto, a program for the development of quantum-resistant lattice-based cryptography, and CryptoWorks21, a Canadian program to develop next-generation quantum-safe cryptographic tools for the 21st century. The outcome of all these efforts towards PQCrypto is a huge advance in the field that has already provided post-quantum candidates that meet all desired features of like efficiency and key-size comparable to classic algorithms.

PQCrypto does not entail any special hardware. It is like classic crypto, but built on problems that are infeasible even for large quantum computers. PQCrypto algorithms have been designed to fulfil the services provided by classic crypto and many of them are able to run even on the most limited platforms.

How will PQCrypto evolve?

Even in a quantum world, current security protocols will continue to be as secure as they are today if their design assumptions are fulfilled using post-quantum cryptosystems. Thus, we should see a gradual adoption of modern PQCrypto algorithms by existing protocols over the coming years.

We should see a decline in the use of public-key algorithms most used nowadays, such as RSA and Elliptic Curves. In cases like symmetric crypto and hash functions, the current parameters will have to be revisited (usually doubled) to ensure that they stay secure in a quantum world. This shift to modern algorithms should happen transparently to end users; however, whoever is responsible for development or configuration of security applications should be ready for the coming changes – in particular, those who support these functionalities in legacy systems.

By way of speculating on how long it will take until large quantum computers are able to perform attacks on cryptosystems set with today's parameters, let's assume that Moore's law will be valid throughout the development of quantum computation. Shor's algorithm requires roughly 3 log2(N) qubits to factor an integer N (it means that Shor's algorithms require roughly 6K qubits to break RSA-2048), whereas Moore's law states that the number of bits – qubits here – that can be packed into a circuit doubles every 12-24 months.

As an exercise, let's take a 5-qubit quantum computer such as the one made available online by IBM this month; then the total number of qubits available to run Shor's algorithm after M cycles of Moore's law can be calculated as 5 * 2M, therefore taking 18 months as an average cycle span of Moore's law, we end up with approximately 16 years from now until attacks against RSA-2048 become feasible – it takes 16.5 years to go over 11 cycles of Moore's law; this results in the availability of 10K qubits (more precisely 10240=5*211) after this period, which is able to supply the 6K qubits required to run the aforementioned attack.

The same magnitude of qubits goes for Grover's algorithm ("between around 3,000 and 7,000 logical qubits") to mount attacks against AES, so that their security level will be halved within that period of time. It means that if our assumptions hold, in sixteen years AES-256 will be as secure as AES-128 is today and AES-128 will be broken. Therefore, if we recall the time taken by Elliptic Curves until it was ready for wide deployment, we realise that clock is ticking for PQCrypto.

What should I care about and what should I do?

A topic that will have major impact along with the advance of quantum computing is long-term security, which can be related to:

Long-term authenticity; such as the life span of a digitally-signed contract

Long-term confidentiality; on legal grounds – for instance, the German Legal Code stipulates that medical data must remain confidential even after the patient´s death – or for strategic reasons, such as organisation or government secrets

Long-term authenticity can be accomplished using simple techniques, like re-signing a document using secure algorithms for as long as needed. Nonetheless, this possibility has to be foreseen and guaranteed by the underlying laws or any system of rules in place; otherwise it will also be threatened by the advance of quantum computation.

Yet, long-term confidentiality is a much more difficult task. There is no established way to address this issue and it is fair to state that none of the current public-key cryptosystems can fulfil this task. It might be a good choice to encrypt these data using strong symmetric cyphers using keys of at least 192 bits to stay secure even if their security level is halved by quantum computers.

Finally, if you expect long-term security for your information, then you should start looking for alternatives or planning for these changes right away. Adversaries who cannot overcome the security of your information today, by decrypting your data or forging your signature, can nevertheless keep a record of the data until they have quantum computers, at which point their attacks will succeed.

Article by Cassius Puodzious, ESET analyst