Analyzing quantum computing's impact on cryptography, this post briefly discusses challenges in encryption and advances in post-quantum cryptography, emphasizing the race for quantum-resistant security.
Published on Tue, February 27, 2024
While in practice, side-channel attacks regularly represent the most relevant threat category for applied encryption methods (Bernstein & Lange, 2017, p. 12), a potentially catastrophic threat scenario is simmering in the background due to the development of quantum computers.
Asymmetric encryption methods fundamentally rely on two mathematical problems: the factorization problem and the discrete logarithm problem.
In 1994, Shor developed an algorithm that can efficiently solve both problems using quantum computing (Shor, 1994). Assuming the existence of such a computer, this would significantly weaken or even break many of the asymmetric cryptographic systems currently used in practice (BSI, 2020, p. 5; Hagemeier, 2019, p. 633). However, symmetric encryption is also affected by the development of quantum computers, albeit to a much lesser extent, as Grover's algorithm demonstrates (Grover, 1996, p. 199).
For symmetric methods, current knowledge suggests that doubling the key lengths used would be necessary to protect them from cryptoanalysis methods conducted on quantum computers (Bernstein & Lange, 2017, p. 4; BSI, 2020, p. 6; Hagemeier, 2019, p. 633; Lenze, 2020, p. 352). See the table below for an overview of common cryptosystems and their assumed pre- and post-quantum security levels.
| Function | Security Levels Pre-Quantum |
Security Levels Post-Quantum |
|
|---|---|---|---|
| Symmetric Methods | |||
| AES-128 | Block Cipher | 128 | 64 (Grover) |
| AES-256 | Block Cipher | 256 | 128 (Grover) |
| Salsa20 | Stream Cipher | 256 | 128 (Grover) |
| GMAC | MAC | 128 | 128 (no influence) |
| Poly1305 | MAC | 128 | 128 (no influence) |
| SHA-256 | Hash Function | 256 | 128 (Grover) |
| SHA-3 | Hash Function | 256 | 128 (Grover) |
| Asymmetric Methods | |||
| RSA-3072 | Encryption | 128 | Broken (Shor) |
| RSA-3072 | Signature | 128 | Broken (Shor) |
| DH-3072 | Key Exchange | 128 | Broken (Shor) |
| DSA-3072 | Signature | 128 | Broken (Shor) |
| ECDH with 256-bits | Key Exchange | 128 | Broken (Shor) |
| ECDSA with 256-bits | Signature | 128 | Broken (Shor) |
Source: Bernstein & Lange, 2017, p. 3.
Two research fields are addressing this issue: quantum cryptography and post-quantum cryptography. Quantum cryptography attempts to directly utilize quantum mechanical concepts for cryptographic applications, such as in quantum key distribution methods. However, there are still so many unresolved questions that the effective practical applicability cannot yet be foreseen (Hagemeier, 2019, p. 634; Lenze, 2020, p. 351).
Post-quantum cryptography, on the other hand, aims to develop cryptographic systems that function on classical security architectures while assuming the existence of quantum computers. It identifies mathematical operations that cannot be performed significantly faster by quantum computing and tries to develop cryptographic systems around these. The goal is for these systems to ultimately be unbreakable by quantum computers (Bernstein & Lange, 2017, p. 1; Hagemeier, 2019, p. 634; Lenze, 2020, p. 352; Schmeh, 2022, p. 114).
Current research focuses in post-quantum cryptography primarily include lattice-based, one-way function-based, coding function-based, multivariate function-based, and isogeny-ECC-based techniques, as well as methods based on non-commutative algebraic structures (Lenze, 2020, pp. 352ff). (Grubbs et al., 2016)
Besides securing against the capabilities of quantum computers, a major challenge in developing these techniques is their practicability in real-world applications. With the security requirements, key lengths, signatures, ciphertexts, and especially the required computational time all increase (Schmeh, 2022, p. 115).
To not lose the race between cryptography and the development of quantum computers, NIST initiated a competition in November 2016 to select quantum computer-resistant cryptographic methods. Of the 82 candidates submitted, 69 were accepted, with 64 effectively entering the race – including 45 encryption or key transport methods and 19 signature methods (Hagemeier, 2019, p. 634). A key goal of the competition is to identify suitable methods based on different mathematical principles and with varying strengths and weaknesses (Schmeh, 2022, p. 114). In July 2022, the first four winners were announced, among them CRYSTALS-Kyber, a lattice-based encryption algorithm. These four winners are now undergoing a standardization process while the competition continues (Schmeh, 2022, p. 114).
All of this will only become practically relevant if quantum computers become a reality in their physical form. However, significant progress is currently being made in this field as well, with "the leading platforms currently transitioning from basic scientific research to applied research with industry participation, and content-wise, from fundamental scientific to technological challenges in the development of complex controlled quantum systems" (BSI, 2020, p. 7).
A major challenge so far is the structural susceptibility to errors of quantum computers. Active error correction is necessary to realistically use them in cryptoanalysis. The theoretical foundations for this exist, but the practical implementation is still in its early stages (BSI, 2020, p. 7).
According to an estimate by the BSI, a quantum computer with an error rate of 1:10,000 would require a computing capacity of about one million physical qubits for a successful attack on 2048-bit RSA within 100 days. For an attack within an hour, about one billion physical qubits would be needed (BSI, 2020, p. 9). For context: Systems developed by large industrial players like Google, IBM, or Microsoft are currently targeting a capacity of 20 to 50 physical qubits (BSI, 2020, p. 9).
Beyond basic research, the topic of post-quantum cryptography is now also finding its way into application-oriented research. For example, Bobrysheva and Zapechnikov have been working on Post-Quantum Messaging (Bobrysheva & Zapechnikov, 2021, 2022). However, as long as the standardization of the algorithms selected by NIST is not yet complete, their use in practice should not yet occur (Schmeh, 2022, p. 114).