An Overview Of Quantum Computing's Possible Impact On Cryptography

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.

Overview

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.

Source: Bernstein & Lange, 2017, p. 3.

Research Fields

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).

New Cryptographic Methods

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).

The Current State Of Quantum Computing

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).

References

• Bernstein, D. J., & Lange, T. (2017): Post-quantum cryptography – dealing with the fallout of physics success.
• Bobrysheva, J., & Zapechnikov, S. (2021): Post-quantum Secure Group Messaging. 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus), 2323–2326.
• Bobrysheva, J., & Zapechnikov, S. (2022): Post-quantum security of messengers: Secure group chats and continuous key distribution protocols. Journal of Computer Virology and Hacking Techniques.
• BSI. (2020): Entwicklungsstand Quantencomputer.
• Grover, L. K. (1996): A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing - STOC ’96, 212–219.
• Grubbs, P., McPherson, R., Naveed, M., Ristenpart, T., & Shmatikov, V. (2016): Breaking Web Applications Built On Top of Encrypted Data. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 1353–1364.
• Hagemeier, H. (2019): Kryptografie – heute und zukünftig: Grundbaustein für IT-Sicherheit. Datenschutz und Datensicherheit - DuD, 43(10), 631–635.
• Lenze, B. (2020): Post-Quanten-Kryptografie. In B. Lenze, Basiswissen Angewandte Mathematik – Numerik, Grafik, Kryptik (S. 351–375). Springer Fachmedien Wiesbaden.
• Schmeh, K. (2022): Post-Quanten-Kryptografie. iX, 9/2022, 114–117.
• Shor, P. W. (1994): Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings 35th annual symposium on foundations of computer science, 124–134.