Post-quantum cryptography refers to cryptographic schemes that are assumed to be unbreakable even with the help of a quantum computer. In contrast to quantum cryptography, these algorithms can be implemented on classical hardware.

Background

The security of digital infrastructures today is largely based on public-key cryptography. The public-key cryptography systems currently implemented rely on the difficulty of certain mathematical problems, for example the problem of decomposing a natural number into its prime factors. These mathematical problems can be used to derive one-way functions, i.e. functions that are easy to compute but difficult to invert. In the given example, an associated one-way function is the multiplication of two very large (roughly 2000 bits long) prime numbers, which can be performed quickly on a computer. So far, however, no efficient classical algorithm is known that can recover the prime factors of a 4000-bit long integer. This problem is the basis of the RSA encryption and digital signature scheme, named after its developers (Rivest, Shamir, Adleman). Another mathematical problem, which is considered for current cryptographic schemes is the so-called Discrete Logarithm Problem (DLP). In particular, algorithms for key exchange and digital signatures can be constructed from the DLP.

To exchange encrypted data, cryptographic keys are usually agreed upon by implementing a public-key algorithm in order to then encrypt messages with a symmetric algorithm (such as AES). To the best of today’s knowledge, the public-key algorithms commonly in use cannot be broken with classical computers. However, this will dramatically change once sufficiently powerful universal quantum computers become available. For example, as early as 1994, Peter Shor published quantum algorithms that can efficiently solve the mathematical problems mentioned above. Thus, the level of security provided by current public-key cryptography systems would be greatly diminished by the development of a quantum computer on which Shor's algorithms can be implemented for sufficiently large input sizes.

Candidates for post-quantum cryptography

The security of post-quantum cryptography relies on problems which are currently believed to be difficult to solve even with quantum computers. Candidates for such algorithms are based, for example,

• on the difficulty of efficiently decoding general error-correcting codes ("code-based cryptography"), or
• on the difficulty of certain problems in mathematical lattices ("lattice-based cryptography"), or
• on security properties of cryptographic hash functions ("hash-based cryptography").

Standardisation

There are ongoing standardisation processes for post-quantum cryptography, most notably the "Post-Quantum Cryptography Project" initiated by the US National Institute of Standards and Technology (NIST) in 2016. Numerous submitted algorithms were examined in detail over three rounds. In July 2022, at the end of the third round, NIST announced that it would standardise the key encapsulation mechanism CRYSTALS-Kyber and the signature schemes CRYSTALS-Dilithium, Falcon, and SPHINCS+. In addition, the three code-based key encapsulation mechanisms Classic McEliece, BIKE and HQC are being considered for standardisation in a fourth round. Furthermore, NIST has called for the submission of additional signature schemes by June 2023. The overarching aim is to standardise signature schemes whose security is based on as many different mathematical problems as possible.

Stateful hash-based signatures have already been specified by the Internet Research Task Force (IRTF) (LMS in RFC 8554 and XMSS RFC 8391) and recommended by NIST for certain parameter choices in NIST SP 800-208. However, stateful hash-based signatures are not suitable for all purposes since it must be ensured that the state can be securely managed by the user of the signature.

Post-quantum schemes are currently implemented in the open source cryptographic library Botan as part of a BSI project.