5.11.9 Why Will Quantum Computers Break Today's Encryption?
- What Is a Quantum Computer?
- Why Are Quantum Computers Different?
- Why Does Modern Cryptography Depend on Difficult Mathematical Problems?
- What Is Shor's Algorithm?
- Which Cryptographic Systems Are Affected?
- Does Quantum Computing Break AES?
- What Is Grover's Algorithm?
- Why Is Public-Key Cryptography More Vulnerable?
- Should We Be Worried Now?
- What Is "Harvest Now, Decrypt Later"?
- Which Industries Will Be Affected?
- What Is Cryptographic Agility?
- What Is Being Done to Prepare?
- Does Quantum Computing Mean Cryptography Will Become Obsolete?
- Why Is Understanding Quantum Computing Important?
Description
Explore how quantum computing threatens many of today's public-key cryptographic systems. Learn how Shor's and Grover's algorithms affect RSA, ECC, and AES, and why organizations are preparing for the transition to post-quantum cryptography.
Introduction
For more than forty years, modern cryptography has relied upon mathematical problems that are believed to be computationally infeasible for conventional computers to solve. Algorithms such as RSA and Elliptic Curve Cryptography (ECC) have protected Internet banking, secure websites, electronic commerce, government communications, and countless other applications because breaking them would require an impractical amount of computing power.
The emergence of quantum computing has changed this picture dramatically.
Although large-scale quantum computers capable of breaking today's encryption do not yet exist, researchers have shown that sufficiently powerful quantum computers could solve certain mathematical problems far more efficiently than any conventional computer. This means that many of the public-key cryptographic systems upon which the modern Internet depends would no longer provide adequate security.
For this reason, governments, standards organizations, and technology companies around the world have begun preparing for the transition to post-quantum cryptography—new encryption algorithms designed to resist attacks from both classical and quantum computers.
What Is a Quantum Computer?
A quantum computer is a type of computer that exploits the principles of quantum mechanics to process information.
Unlike conventional computers, which store information as binary digits (bits) having values of either 0 or 1, quantum computers use quantum bits, or qubits. Qubits exhibit uniquely quantum properties that allow certain classes of mathematical problems to be solved much more efficiently than is possible using classical computers. It is important to understand that quantum computers are not simply faster versions of today's computers.
Instead, they solve some problems using fundamentally different computational techniques.
Why Are Quantum Computers Different?
Classical computers perform calculations by manipulating binary digits through logical operations.
Quantum computers exploit phenomena such as:
- superposition;
- entanglement;
- quantum interference.
These effects allow quantum algorithms to explore certain mathematical possibilities much more efficiently than classical algorithms.
However, quantum computers are not faster for every problem. Many everyday computing tasks receive little or no advantage from quantum computation.
Their greatest impact is expected to occur in areas involving particular classes of mathematical problems—including some that underpin modern cryptography.
Why Does Modern Cryptography Depend on Difficult Mathematical Problems?
Public-key cryptographic algorithms rely upon mathematical problems that appear to be computationally difficult for classical computers.
Examples include:
- factoring very large integers;
- solving discrete logarithms;
- solving elliptic-curve discrete logarithms.
No efficient classical algorithms are known for solving these problems when sufficiently large numbers are involved. Consequently, recovering the private key from the public key would require an impractical amount of computation.
This assumption forms the basis of RSA, Diffie–Hellman, and Elliptic Curve Cryptography.
What Is Shor's Algorithm?
In 1994, mathematician Peter Shor developed a quantum algorithm capable of solving two mathematical problems that underpin much of today's public-key cryptography:
- integer factorization;
- discrete logarithms.
On a sufficiently large and reliable quantum computer, Shor's algorithm could solve these problems in polynomial time rather than the astronomical times required by classical computers. This discovery demonstrated that many widely used public-key algorithms would become vulnerable if practical large-scale quantum computers were built.
It is one of the most significant discoveries in the history of cryptography.
Which Cryptographic Systems Are Affected?
Shor's algorithm threatens many widely used public-key systems, including:
- RSA;
- Diffie–Hellman key exchange;
- Elliptic Curve Cryptography (ECC);
- Elliptic Curve Diffie–Hellman (ECDH);
- Elliptic Curve Digital Signature Algorithm (ECDSA).
These algorithms all rely upon mathematical problems that quantum computers could solve efficiently.
As a result, they are not considered secure against future large-scale quantum computers.
Does Quantum Computing Break AES?
Not directly.
Symmetric encryption algorithms such as AES are affected much less severely. The principal quantum attack against symmetric encryption is Grover's algorithm. Rather than completely breaking AES, Grover's algorithm provides approximately a square-root improvement in brute-force key searching. In practical terms:
- AES-128 provides roughly the security of a 64-bit key against an ideal quantum attacker.
- AES-256 provides security roughly comparable to a 128-bit classical key.
Simply increasing the key length therefore provides an effective countermeasure.
For this reason, symmetric cryptography is expected to remain secure with relatively modest modifications.
What Is Grover's Algorithm?
Grover's algorithm is a quantum search algorithm developed by Lov Grover in 1996.
Unlike Shor's algorithm, it does not exploit weaknesses in encryption algorithms themselves. Instead, it accelerates exhaustive key searches. Although useful, the improvement is much smaller than that provided by Shor's algorithm.
Consequently, Grover's algorithm represents a manageable threat compared with the challenges posed to public-key cryptography.
Why Is Public-Key Cryptography More Vulnerable?
Public-key cryptography depends upon specific mathematical problems.
Once efficient quantum algorithms exist for solving those problems, the security of the corresponding cryptographic systems collapses. Symmetric cryptography does not rely upon such mathematical structures. Instead, it depends primarily upon the size of the key space.
This difference explains why quantum computing has such dramatically different effects on the two families of cryptographic algorithms.
Should We Be Worried Now?
Large-scale fault-tolerant quantum computers capable of breaking RSA or ECC have not yet been demonstrated.
Nevertheless, many experts believe that organizations should begin preparing well before such machines become available. Cryptographic transitions often require many years. Large organizations may operate systems that remain in service for decades.
Waiting until practical quantum computers arrive would leave insufficient time to replace vulnerable systems.
What Is "Harvest Now, Decrypt Later"?
One important concern is known as Harvest Now, Decrypt Later.
An attacker may record encrypted communications today, even though they cannot currently decrypt them. If sufficiently powerful quantum computers become available in the future, those stored communications could potentially be decrypted.
This threat is particularly significant for information that must remain confidential for many years, such as:
- government information;
- military communications;
- medical records;
- intellectual property;
- long-term commercial secrets.
Organizations responsible for such information are already beginning the migration to quantum-resistant cryptography.
Which Industries Will Be Affected?
The transition to post-quantum cryptography is expected to affect virtually every sector that relies upon secure digital communications.
These include:
- banking and finance;
- telecommunications;
- cloud computing;
- government;
- defence;
- healthcare;
- critical infrastructure;
- satellite communications;
- Internet service providers.
Almost every organization connected to the Internet will eventually be affected.
What Is Cryptographic Agility?
Cryptographic agility refers to the ability of a system to replace one cryptographic algorithm with another without major redesign.
Systems designed with cryptographic agility can transition more easily from today's algorithms to future post-quantum algorithms.
This has become an increasingly important design objective for modern communication systems.
What Is Being Done to Prepare?
Governments and standards organizations have been preparing for many years. Major activities include:
- evaluating new post-quantum algorithms;
- developing international standards;
- updating communication protocols;
- replacing vulnerable public-key algorithms;
- designing quantum-resistant digital signatures.
Many software vendors have already begun introducing support for post-quantum cryptographic algorithms into their products.
Does Quantum Computing Mean Cryptography Will Become Obsolete?
No.
Quantum computing threatens certain cryptographic algorithms, not the science of cryptography itself. As computing technology evolves, cryptography evolves with it. Just as DES was replaced by AES and larger RSA key sizes replaced smaller ones, today's public-key algorithms will gradually be replaced by quantum-resistant alternatives.
The fundamental need for secure communications remains unchanged.
Why Is Understanding Quantum Computing Important?
Quantum computing represents one of the most significant developments in the history of information security. Although practical quantum attacks remain some years away, their eventual impact on public-key cryptography is expected to be profound.
Understanding why quantum computers threaten today's encryption helps explain why the global cryptographic community is investing heavily in new post-quantum standards that will protect future communication systems.
Summary
Quantum computers exploit the principles of quantum mechanics to solve certain mathematical problems much more efficiently than classical computers. Shor's algorithm threatens widely used public-key cryptographic systems such as RSA and Elliptic Curve Cryptography, while Grover's algorithm modestly reduces the effective security of symmetric encryption.
Although practical large-scale quantum computers do not yet exist, governments, standards organizations, and industry are already preparing for the transition to post-quantum cryptography. This migration will ensure that secure communications remain possible throughout the coming decades, even in the presence of powerful quantum computers.
Back to reading