The Impact of Quantum Computers on Cryptographic Security

If large-scale, fault-tolerant quantum computers are invented, many of the cryptographic systems that we rely on today, particularly those based on certain mathematical problems, will become vulnerable. Here's why and how this could happen:

1. Public-Key Cryptography Will Be Broken

Most modern cryptographic systems, like RSA (Rivest–Shamir–Adleman) and ECC (Elliptic Curve Cryptography), are based on the difficulty of solving certain problems:

• RSA relies on the difficulty of factoring large integers.

• ECC relies on the hardness of the discrete logarithm problem over elliptic curves.

These problems are hard for classical computers, meaning it would take an infeasible amount of time for them to solve. However, quantum computers can efficiently solve these problems using Shor's Algorithm. Shor's algorithm can factor large numbers and solve discrete logarithms exponentially faster than any known classical algorithm, making RSA and ECC essentially useless.

2. Symmetric Key Cryptography

Symmetric key algorithms like AES (Advanced Encryption Standard) and SHA-256 (used for hashing) are based on more fundamental principles, not number-theoretic problems. Quantum computers can still impact symmetric algorithms, but not as dramatically.
For symmetric cryptography:

• Grover's Algorithm can be used to search through possible keys faster than classical computers. This provides a quadratic speedup, meaning that for a key of length nnn, the effective security is reduced to n/2n/2n/2. For example, AES-256 would be reduced to the security of AES-128 under Grover's algorithm.

• To counter this, simply doubling the key length (e.g., from AES-128 to AES-256) would maintain security.

3. Digital Signatures and Hash Functions

Quantum computers would also impact hash functions and digital signature schemes:

• Hash functions like SHA-256 could be attacked using Grover's algorithm, reducing the security of finding collisions. However, this would not break hash functions entirely, just weaken their strength, requiring longer hash outputs.

• Signature schemes based on RSA or ECC would be vulnerable since they rely on the same number-theoretic problems.

Quantum-Resistant (Post-Quantum) Cryptography

Recognizing the potential for quantum computers to break classical cryptography, researchers are actively developing quantum-resistant algorithms that can resist quantum attacks. These are based on hard problems that both classical and quantum computers struggle with, such as:

• Lattice-based cryptography (e.g., NTRU, Learning With Errors)

• Code-based cryptography (e.g., McEliece)

• Hash-based cryptography (e.g., Lamport signatures)

• Multivariate quadratic equations

These post-quantum cryptographic algorithms are designed to remain secure even when large quantum computers are available.

Key Takeaways

• Public-key cryptography (RSA, ECC) will be completely broken by quantum computers using Shor’s algorithm.

• Symmetric key cryptography (like AES) will be weakened but not entirely broken. Increasing key sizes can restore security.

• Hash functions will be somewhat affected but not entirely broken.

• Post-quantum cryptography offers a promising solution, with algorithms designed to resist both classical and quantum attacks.

The development of quantum-safe encryption will become increasingly important as quantum computing advances, but as of now, large-scale quantum computers do not exist yet