Post quantum cryptography – The Final Frontier

We have previously reported on the ongoing search by the National Institute of Standards and Technology (NIST) to find one or more ‘quantum-proof’ algorithms that could be used as standard encryption and verification methods in the future (see Post-quantum cryptography – a new hope).

This was launched back in 2017 in response to the threat that a fully armed and operational quantum computer would pose to the existing cryptographic methods used to secure the transfer of information. For example, using Shor’s algorithm, a quantum computer would be able to factor (very) large integer numbers in a fraction of the time it takes a classical computer, undercutting some of the most well-known and established cryptographic schemes used today at their foundation.

Whilst quantum computers are only available at small scale today, with many experts not expecting quantum computing to be mainstream until around 2030, it is also clear that the task of completely overhauling current cryptographic methods and implementing new ‘quantum-proof’ approaches will take a long time. There is also a threat of so-called ‘hack now, decrypt later’ attacks, in which a hacker collects encrypted data that they cannot access now with the intent of breaking into it later when quantum computers become a reality. This is why it is vital that practical steps are being taken now to prepare for the future.

The NIST ‘Post-Quantum Cryptography Standardization Process’ has announced the results of its third round, in which the following four algorithms have been selected to be standardized:

• CRYSTALS-Kyber
• CRYSTALS-Dilithium
• FALCON
• SPHINCS+

Of this list, the two primary algorithms to be implemented in most scenarios are CRYSTALS-Kyber for general public-key encryption, and CRYSTALS-Dilithium for digital signatures. The remaining two algorithms, FALCON and SPHINCS+, have been selected as additional options for digital signatures.

Hash-based cryptography

Whilst CRYSTALS-Kyber, CRYSTALS-Dilithium and FALCON all use lattice-based cryptography techniques, the SPHINCS+ algorithm takes an entirely different approach that makes use of hash functions. These are mathematical functions that convert an arbitrary numerical input ‘message’ into a second numerical ‘digest’ value of a certain fixed length (say 256 bits).

A hash function must have certain properties. For example, it must be deterministic (a particular input always results in the same output), it must be computationally efficient to compute an output from a given input, and it must be collision resistant, meaning that it should be hard to find two inputs that will produce the same output. Most importantly of all though, it must be (computationally) hard to convert an output back into the original input. In other words, a hash function needs to be ‘one-way’.

Numerous cryptographic schemes have been developed that use hash functions as their basis. The Lamport and Merkle schemes being perhaps the best examples, which allow messages to be authenticated using a private and public key pair to generate and verify a digital signature attached to the message. But these schemes have not traditionally been used in standard cryptography because they require a relatively large bandwidth. Especially the Merkle scheme, whose digital signature can become quite large when many keys are generated.

However, these concerns have been mitigated in more recent times by the fact that many hash functions have been found to be ‘one-way’ even on a quantum computer. As such, they represent a viable alternative to the sleeker, but quantum insecure, methods that are currently used.

Why diversify?

Putting all your eggs into a single basket is rarely a good idea, and this is especially true when you are not even certain how secure that single basket is!

In cryptography, the security of the algorithms that are used is based on the argument that there is no efficient (computationally easy) way to solve the mathematical problems that underpin the cryptographic schemes. In the case of RSA encryption and the Diffie–Hellman key exchange, two standard cryptographic schemes used today, this means that no one has found an efficient way to factor large integers on a classical computer. However, this does not mean that there isn’t a way, just that no one has yet found it. Indeed, Shor’s algorithm can solve this problem efficiently, but on a quantum rather than classical computer, and this is why there is a need to find quantum-resistant schemes in the first place.

These arguments are even more relevant for the cryptographic algorithms that are currently believed to be quantum-resistant, as it is harder to yet be certain which ones will stand the test of time. This point was highlighted recently, when one of the front-runner algorithms in the previous round of the NISTs search was withdrawn after a paper was published under the title: “Breaking Rainbow takes a weekend on a laptop”. In this paper, the author lays out a way to break the SL1 version of the Rainbow algorithm, where SL1 refers to the security level. Whilst this is a relatively low security version of the algorithm, it still shows that there is always the potential that new ways will be discovered to crack algorithms that were previously thought of as ‘safe’.

This is why it is always good to have backup schemes based on different underlying principles, and is one of the reasons why the SPHINCS+ algorithm has been selected.

The future

Over the coming months, NIST will work to select standard parameters for the selected algorithms, and these will be posted for public comment. After this, the standards will be revised based on the feedback received, and a final review will then take place before the finalised forms of these four quantum-proof encryption methods are published and (hopefully) adopted by the world.

In addition, NIST will also begin their fourth-round process, which will take between 18-24 months to complete. In this, four more candidate algorithms (BIKE, Classic McEliece, HQC and SIKE) will be assessed for their suitability for public-key encryption, with the aim being to provide alternatives to CRYSTALS-Kyber.

We will continue to keep you updated on the progress of NIST throughout the remaining stages of this seven-year process.