Product Security
30.Apr.2025
Quantum Computing and Cybersecurity: A Threat Game Changer
Author: Anders Olof Möller
Over the past decade, substantial investments in quantum computing have resulted in significant progress and increased awareness of its effect on cybersecurity. Quantum computing is expected to be a transformative technology, capable of solving complex problems beyond the reach of classical computers, creating what is known as the quantum advantage.
This technological breakthrough could provide many opportunities, and there are expectations of finding applications in areas such as finance, pharma, health, optimization and artificial intelligence. However, there is a particular application of quantum computers that is crucial for cybersecurity – the potential of breaking the currently used public key cryptosystems. In this article, we will dive into the challenges of quantum computing and examine its profound impact on cybersecurity.
Despite its potential, quantum computing and executing quantum algorithms face significant technical barriers. One of them is the issue of coherence time, which is the time that a qubit can maintain its quantum state before it is lost. Another challenge is error rates, as quantum computers tend to be highly error-prone. A solution for this is error correction, which requires several physical qubits to create one logical qubit. This, on the other hand, introduces the challenge of performing quantum operations on quantum logical qubits, as opposed to on physical qubits.
A significant milestone in addressing these challenges was recently achieved with Google’s introduction of the Willow quantum chip. The chip successfully demonstrated the theory of quantum error correction in practice, by using several physical qubits for one logical qubit. This breakthrough moves us one step closer to achieving an efficient quantum computer for real-world applications.
The quantum threat to cryptography stems from two known quantum algorithms, Grove’s algorithm and Shor’s algorithm:
Grover’s algorithm implies a quadratic speed-up for unstructured searches. Simplifying, it means that the security level for symmetric, secret key cryptography, such as the Advanced Encryption Standard (AES), is reduced to half the key length. For most cases of symmetric cryptography, a sufficient security against the quantum threat can simply be obtained by doubling the key length, for example by using the already standardized and widely used version of AES with key length 256 bits.
Shor’s algorithm implies a polynomial-time algorithm for the factorization of a number into prime factors, and a polynomial-time algorithm for the discrete logarithm problem in finite fields. In practice, this implies that the security of most known public key cryptography cryptosystems can be broken. This includes Elliptic Curve Cryptography (ECC) and RSA. This can’t be remediated by longer keys but needs other solutions that are resistant to the quantum adversary.
(In fact, the problem of factorization and the discrete logarithm problem in finite fields are closely related, since it can be shown that the factorization problem can be posed as a discrete logarithm problem. This means that if you can solve the discrete logarithm problem, you can solve the factorization problem. Shor’s algorithm on quantum computers can solve the discrete logarithm problem, also for unknown order.)
Even though quantum computers are still under development, organizations must start considering quantum adversaries today. This is especially important in two cases:
Long-term data confidentiality, and software update signatures are implemented in long-lived applications, where the update mechanism can’t be updated.
For confidentiality, the quantum adversary introduces the “record now, decrypt later” attack scenario. In this approach, a quantum adversary can record encrypted data today, to later decrypt in the future when an efficient quantum computer becomes available. To address this risk, organizations can apply Mosca’s Law for Confidentiality.
As shown in the figure, the timeline for transitioning to quantum-safe cryptographic systems can be estimated by using the following equation:
Time to start migration = Z - Y - X
X = the time that data needs to remain confidential
Y = the time required to migrate to a secure quantum-safe system
Z = the estimated time for the quantum threat materialized
If the sum of X and Y exceeds Z, it means that by the time quantum computers reach the required level of capability, sensitive data could already be exposed. For example, if a quantum adversary is estimated to be in the year 2035, the confidentiality time is 5 years, migration time is 3 years and the time to start migration is in 2027.
Currently, quantum computers operate with hundreds of qubits, far below the estimated threshold. Nonetheless, steady progress continues with industry leaders like Google and IBM adhering closely to their development roadmaps.
While predicting technological milestones is uncertain, many experts believe that quantum computers capable of breaking modern crypto could emerge between 2030 and 2045. For this reason, organizations must begin considering these future risks now to ensure today’s secured data remains protected in a post-quantum era.
At DEKRA, we provide evaluation according to FIPS 140-3 certification, ISO/IEC 19790 certification and NIST standards on cryptographic modules, helping organizations to ensure their products meet the highest level of security and compliance. We are committed to navigate our customers through the complex landscape of cybersecurity requirements, achieving certification with confidence.
Ready to get started? Contact us now!
References:
[1] IBM, “What is Quantum Computingt,” [Online]. Available: https://www.ibm.com/think/topics/quantum-computing.
[2] Quanta Magazine “Thirty Years Later, a Speed Boost for Quantum Factoring,” [Online]. Available: https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/.
[3] Google, “Meet Willow, our state-of-the-art Quantum Chip,” [Online]. Available: https://blog.google/technology/research/google-willow-quantum-chip/
[4] Google, "Explore Google Quantum AI", [Online]. Available: https://quantumai.google/
[5] Arxiv, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, Craig Gidney, Martin Ekerå, Available: https://eprint.iacr.org/2015/1075.pdf
[6] eprint, “Cybersecurity in an era with quantum computers: will we be ready?”, Michele Mosca, Available: https://eprint.iacr.org/2015/1075.pdf
Over the past decade, substantial investments in quantum computing have resulted in significant progress and increased awareness of its effect on cybersecurity. Quantum computing is expected to be a transformative technology, capable of solving complex problems beyond the reach of classical computers, creating what is known as the quantum advantage.
This technological breakthrough could provide many opportunities, and there are expectations of finding applications in areas such as finance, pharma, health, optimization and artificial intelligence. However, there is a particular application of quantum computers that is crucial for cybersecurity – the potential of breaking the currently used public key cryptosystems. In this article, we will dive into the challenges of quantum computing and examine its profound impact on cybersecurity.
What is Quantum Computing?
Quantum computing is an emergent field at the intersection of physics and computer science. It leverages the principles of quantum mechanics to solve problems that are beyond the reach of even the most advanced classical computers. While classical computers use bits, quantum computers use qubits. Like classical bits, qubits can take the value 0 or 1. But quantum computers can also handle the superposition of 0 and 1. For example, in a two-qubit vector, there are four components of the superposition, and computations can be made simultaneously on all these states. The number of components grows exponentially with the number of qubits, which means 2^n components for n qubits. This remarkable simultaneous computation is one of the quantum computer’s strengths. However, this advantage comes with a fundamental complexity: when observing the state, it collapses into one specific, random binary combination. While random, the probability of achieving different states can be affected through calculations in quantum algorithms, using quantum gates.Despite its potential, quantum computing and executing quantum algorithms face significant technical barriers. One of them is the issue of coherence time, which is the time that a qubit can maintain its quantum state before it is lost. Another challenge is error rates, as quantum computers tend to be highly error-prone. A solution for this is error correction, which requires several physical qubits to create one logical qubit. This, on the other hand, introduces the challenge of performing quantum operations on quantum logical qubits, as opposed to on physical qubits.
A significant milestone in addressing these challenges was recently achieved with Google’s introduction of the Willow quantum chip. The chip successfully demonstrated the theory of quantum error correction in practice, by using several physical qubits for one logical qubit. This breakthrough moves us one step closer to achieving an efficient quantum computer for real-world applications.
Quantum Computing & Cybersecurity: Why Are Future Efficient Quantum Computers a Problem Now?
One of the most discussed implications of quantum computing is the potential to break modern public key cryptography, which is already posing a significant cybersecurity threat. Simply put, cryptography is a fundamental pillar of cybersecurity, and quantum computing is set to reshape the very foundations of cryptography.The quantum threat to cryptography stems from two known quantum algorithms, Grove’s algorithm and Shor’s algorithm:
Grover’s algorithm implies a quadratic speed-up for unstructured searches. Simplifying, it means that the security level for symmetric, secret key cryptography, such as the Advanced Encryption Standard (AES), is reduced to half the key length. For most cases of symmetric cryptography, a sufficient security against the quantum threat can simply be obtained by doubling the key length, for example by using the already standardized and widely used version of AES with key length 256 bits.
Shor’s algorithm implies a polynomial-time algorithm for the factorization of a number into prime factors, and a polynomial-time algorithm for the discrete logarithm problem in finite fields. In practice, this implies that the security of most known public key cryptography cryptosystems can be broken. This includes Elliptic Curve Cryptography (ECC) and RSA. This can’t be remediated by longer keys but needs other solutions that are resistant to the quantum adversary.
(In fact, the problem of factorization and the discrete logarithm problem in finite fields are closely related, since it can be shown that the factorization problem can be posed as a discrete logarithm problem. This means that if you can solve the discrete logarithm problem, you can solve the factorization problem. Shor’s algorithm on quantum computers can solve the discrete logarithm problem, also for unknown order.)
Even though quantum computers are still under development, organizations must start considering quantum adversaries today. This is especially important in two cases:
Long-term data confidentiality, and software update signatures are implemented in long-lived applications, where the update mechanism can’t be updated.
For confidentiality, the quantum adversary introduces the “record now, decrypt later” attack scenario. In this approach, a quantum adversary can record encrypted data today, to later decrypt in the future when an efficient quantum computer becomes available. To address this risk, organizations can apply Mosca’s Law for Confidentiality.
Time to start migration = Z - Y - X
X = the time that data needs to remain confidential
Y = the time required to migrate to a secure quantum-safe system
Z = the estimated time for the quantum threat materialized
If the sum of X and Y exceeds Z, it means that by the time quantum computers reach the required level of capability, sensitive data could already be exposed. For example, if a quantum adversary is estimated to be in the year 2035, the confidentiality time is 5 years, migration time is 3 years and the time to start migration is in 2027.
When Will Quantum Computers Break Public Key Cryptography?
How many qubits are needed to break current cryptography? This question was addressed in 2019 by researchers Martin Ekerå and Craig Gidney. Based on the usage of quantum error correcting codes for logical qubits (now practically verified by Google’s quantum chip Willow) and the state-of-the-art improved versions of Shor’s algorithm, they estimated that in the order of 20 million qubits would be needed to factor a 2048-bit RSA integer in 8 hours. This corresponds to breaking a typical use case for RSA.Currently, quantum computers operate with hundreds of qubits, far below the estimated threshold. Nonetheless, steady progress continues with industry leaders like Google and IBM adhering closely to their development roadmaps.
While predicting technological milestones is uncertain, many experts believe that quantum computers capable of breaking modern crypto could emerge between 2030 and 2045. For this reason, organizations must begin considering these future risks now to ensure today’s secured data remains protected in a post-quantum era.
At DEKRA, we provide evaluation according to FIPS 140-3 certification, ISO/IEC 19790 certification and NIST standards on cryptographic modules, helping organizations to ensure their products meet the highest level of security and compliance. We are committed to navigate our customers through the complex landscape of cybersecurity requirements, achieving certification with confidence.
Ready to get started? Contact us now!
[1] IBM, “What is Quantum Computingt,” [Online]. Available: https://www.ibm.com/think/topics/quantum-computing.
[2] Quanta Magazine “Thirty Years Later, a Speed Boost for Quantum Factoring,” [Online]. Available: https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/.
[3] Google, “Meet Willow, our state-of-the-art Quantum Chip,” [Online]. Available: https://blog.google/technology/research/google-willow-quantum-chip/
[4] Google, "Explore Google Quantum AI", [Online]. Available: https://quantumai.google/
[5] Arxiv, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, Craig Gidney, Martin Ekerå, Available: https://eprint.iacr.org/2015/1075.pdf
[6] eprint, “Cybersecurity in an era with quantum computers: will we be ready?”, Michele Mosca, Available: https://eprint.iacr.org/2015/1075.pdf
