Post-Quantum Cryptography: Threats and New Encryption Standards
While classical computers work with bits, quantum computers work with qubits [1]. Qubits can take states 0 or 1, just like bits, but they can also use the possibilities of quantum physics to be in a superposition of 1 and 0. This means that its value can be 1 and 0 at the same time, and only when measured it collapses to 1 or 0 with a given probability (just like Schrödinger’s cat). Applied to cryptography, while a regular brute-force attack would require testing every possible key one at a time, a quantum computer could superimpose all possible keys and test them all at once. However, a quantum algorithm has to be used to increase the probability for the state to collapse to the correct key to recover it. The quantum threat to cryptography stems from two such algorithms:
Grover´s Algorithm:
[2] Iterates a series of transformations on the state to slowly converge to the key. It can reduce the security strength of the attacked algorithm by half. For example, it could brute-force an AES-256 in the same time a classical computer would brute-force an AES-128. This threat can easily be mitigated by doubling the length of the keys. Modern algorithms already have long enough keys to be safe against Grover’s algorithm.
Shor’s Algorithm:
[3], On the other hand, takes advantage of the cyclic nature of modular arithmetic and elliptic curves to recover the keys in polynomial time (fast!). For that, it uses the quantum Fourier transform, a transformation on the quantum state analogous to the classical Fourier transform that can find the periods of the cycles. This threat cannot be mitigated and affects popular algorithms such as RSA, DSA, Diffie-Hellman and elliptic curve cryptography (ECC).
In summary, the security of hashes or symmetric algorithms will be reduced by half due to Grover’s algorithm, but they will still be safe as long as their key sizes increases. However, asymmetric algorithms such as RSA, DSA, Diffie-Hellman and ECC will become perfectly breakable due to Shor’s algorithm.
Post-Quantum Cryptography New Standards
Even if there is not an efficient quantum computer yet, an attacker can record encrypted data today and decrypt it later when an efficient quantum computer is available. In addition, devices deployed today could be attacked later, when the keys that protect them from malicious software or firmware updates would become easy to break with quantum computers. Therefore, the migration to safe alternatives for key encapsulation (i.e., securely transfer of cryptographic keys) and digital signatures must begin as soon as possible.
Post-quantum cryptography is the name given to cryptography that is secure against attackers with both classical and quantum computing capabilities. It can be implemented in any classical computer. Among the different types of mathematics underlying the proposals for new algorithms are multivariate problems, isogenies, lattice problems, hash-functions and code-based cryptography [4].
In 2015 NIST started a process to develop a new line of secure cryptographic algorithms as a response to the quantum threat [5]. Similar to previous successful processes for development and standardization of cryptographic algorithms, the process has been in the form of a competition where anyone could submit proposals. The cryptographic community has dedicated significant attention to the competition, both in the development of post-quantum algorithm proposals and cryptanalysis of the suggested algorithms.
The first algorithms to be standardized by NIST were XMSS and LMS, published in NIST SP 800-208 in October 2020. They are signature schemes whose security relies on hash algorithms, which are already well- studied and secure against quantum computers. Thus, they were good candidates for an early standardization. Their main drawback is that they are stateful, i.e., they need to keep track of all produced signatures, which makes them not suitable for general use in e.g. large Public Key Infrastructures. Nonetheless, until better options are developed, they are recommended for digital signatures of software and firmware of devices that are planned to have a long lifespan and need to be protected for a time in which quantum computers could become available.
In July 2022 NIST announced four candidates to be standardized: one key encapsulation mechanism called CRYSTALS-Kyber and three digital signature schemes called CRYSTALS-Dilithium, Falcon and SPHINCS+. Other key encapsulation mechanisms remain under consideration for standardization. Three new standards were published on August 13, 2024:
FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard:
It standardizes the CRYSTALS-Kyber algorithm. It is a key encapsulation mechanism based on lattices, a geometric structure that is known to contain hard-to-solve mathematical problems, such as the learning with errors (LWE) problem on which Kyber is based.
FIPS 204, Module-Lattice-Based Digital Signature Standard:
FIPS 205, Stateless Hash-Based Digital Signature Standard:
While quantum computing still has a long way to go, its threat to cryptographic security is already present, which makes post-quantum algorithms more relevant every day. The new standards are already here and actors in the cryptographic world must be aware and prepare for the change.
Except for XMSS, all of these newly standardized algorithms are already available for certification in the ACVP (Automated Cryptographic Validation Protocol). If you have a post-quantum cryptographic implementation and want to certify it,
contact our DEKRA experts
and we will guide you through the certification process.
References:
[1] Wikipedia, “Qubit,” [Online]. Available: https://en.wikipedia.org/wiki/Qubit.
[2] L.K. Grover, “A fast quantum mechanical algorithm for database search,” Symposium on the Theory of Computing, 1996.
[3] P.W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing, vol. 26, no. 5, p. 1484–1509, 1997.
[4] BSI, “Post-quantum cryptography,” [Online]. Available: https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisationen/Informationen-und-Empfehlungen/Quantentechnologien-und-Post-Quanten-Kryptografie/Post-Quanten-Kryptografie/post-quanten-kryptografie_node.html
[5] NIST, “Post-Quantum Cryptography Standardization,” [Online]. Available: https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization