Post-Quantum Cryptography: The First Steps

This article was prepared in cooperation with Microsec Ltd. Check out their blog for more interesting readings!

In a previous post, we discussed how the possibility of quantum attacks will affect the security of currently used cryptographic methods. As we saw, the post quantum security level of symmetric key methods including block ciphers and hash functions can reach the classical security level after doubling the key length. At the same time, we need alternative solutions instead of the ubiquitously used public key cryptosystems that are known to be breakable with scalable quantum computers. In this post, we comment on the crypto aspect of a recent breakthrough in quantum computing and briefly introduce the most important standardization effort of the post-quantum transition.

Quantum supremacy, what do you mean for us?

The recent breakthrough of Google and NASA received much attention lately. In a nutshell, they managed to solve a specific problem with a quantum computer faster than any classical computer could have done it. In the jargon this is called the quantum advantage. What Google claims – but IBM repudiates – is a stronger statement, called quantum supremacy: namely that the computation in question is not simply slower with any traditional machine but also prohibitively slower. Either one is the case; the result is undoubtedly a landmark in the quest for scalable quantum computers. But what does this mean for the presence and future of cryptography?

First and foremost the solved problem is not related to the present day cryptographic assumptions, so no cryptosystem is broken yet by quantum computers. On the contrary, while being the first evidence that quantum computers can beat classical ones, the result of Google also demonstrates how far still we are from being able to run the Shor algorithm to break public key crypto. According to a recent study, the factorization of 2048 bit integers, typically used in the RSA cryptosystem today, would require 20,000,000 qubits. For comparison, the processor of Google used 54 qubits.

The NIST post-quantum standardization process

One may wonder when we should start to really care about post-quantum cryptography. To get a reasonable answer, let’s assume that

• we plan to use a digital signature for x years after its creation (or keep the secrecy of some encrypted data for the same duration),
• it takes y years to set up an infrastructure with post-quantum security that can replace our current algorithms,
• it takes z years from now to build a quantum computer, capable of breaking the currently used public-key methods.

After a short contemplation, one can see that if x+y>z then we are already in trouble and that we need to have ready to use methods by z-x years from now. For regular users, it is rather hard to predict y or z. At the same time, several signs indicate that there are applications — requiring long-term security guarantees — for which the year 2020 + z – x, when we have to stop using the current techniques, is within a few years from now. One of the telling indicators of this is the changing attitude and the recent activities of the different standardization bodies. The most notable among these efforts is the post-quantum standardization process, initiated by the U.S. based National Institute of Standards and Technology (NIST) in 2016. NIST aims to prepare draft standards for one or more quantum-resistant public-key encryption schemes or key-establishment protocols and digital signature schemes by 2022-2024 (see their timeline). The standardization is entirely open (it is worth looking into the discussions), anyone could submit proposals which are continuously examined and evaluated by the research community. Currently the process is in its 2^nd round (out of the planned 3, which is scheduled to start around June 2020), where 26 out of the 69 submissions (9 of the 22 signature schemes) are still investigated.

We also mention another, independent effort of NIST related to post-quantum digital signatures. While signature schemes are traditionally stateless (i.e. one does not have to keep track of previous invocations of the signature algorithm, as they are independent), it is possible to construct stateful signatures relying on cryptographic hash functions guaranteeing post-quantum security. Together with proper state management, they provide a convenient solution against quantum attackers as well but due to the differences compared to stateless schemes, NIST aims to standardize stateful signatures in separate project.

In an upcoming post, we are going to introduce the ideas behind the constructions of the post-quantum signatures of round 2 of the standardization. Stay tuned. 🙂

Further reading