Cryptography

The Quantum Threat to Cryptography

In 1994, Peter Shor published an algorithm that theoretically breaks RSA in polynomial time. The entire internet runs on RSA. Quantum computers are becoming a reality.

  • **Google Willow 2024**: 105 qubits, quantum advantage demonstrated on specialized tasks - progress is exponential.
  • **NIST 2024**: three final post-quantum standards (ML-KEM, ML-DSA, SLH-DSA) - the PQC era has begun.
  • **China Quantum Backbone**: 2000 km QKD network between cities - quantum cryptography in production.
  • **Harvest Now Decrypt Later**: intelligence agencies are presumably already collecting encrypted traffic today, waiting for future quantum capability.

Shor's Algorithm

Shor's algorithm (1994) solves the integer factorization problem in polynomial time O((log N)^3) on a quantum computer. The best classical algorithm (GNFS) runs in sub-exponential time - an exponential gap. RSA-2048 classically requires ~2^112 operations; quantumly on the order of (2048)^3 ≈ 8 billion. The key insight: factorization reduces to finding the period of f(x) = a^x mod N, which a quantum computer solves via QFT (Quantum Fourier Transform).

Shor's algorithm breaks RSA, finite-field DH, and ECDH/ECDSA - all systems based on factorization or discrete logarithm. Google Willow (2024) demonstrated quantum advantage on specialized tasks, but RSA-2048 remains out of reach. NIST launched its post-quantum standardization competition in 2016 and finalized it in 2024 - first standards: CRYSTALS-Kyber (ML-KEM), CRYSTALS-Dilithium (ML-DSA), FALCON, SPHINCS+.

Why is Shor's algorithm specifically devastating for RSA and ECC?

0

1

Sign In

Grover's Algorithm

Grover's algorithm (1996) accelerates search quadratically: classical search over N elements takes O(N), quantum search takes O(sqrt(N)). For symmetric cryptography this means: AES-128 is effectively reduced to AES-64 (2^64 instead of 2^128 operations); AES-256 to AES-128. For hash functions: SHA-256 (256-bit space) becomes equivalent to 128-bit security. NIST conclusion: symmetric keys and hash outputs must be doubled.

Grover's algorithm is significantly less alarming than Shor's. Doubling the AES key size to 256 bits already exists and suffices. The real quantum threat to cryptography is asymmetric cryptography via Shor's algorithm. Harvest Now, Decrypt Later (HNDL): adversaries are already collecting encrypted traffic today, planning to decrypt it once quantum computers become available. Long-lived confidential data (state secrets, medical records) is already at risk.

Why is AES-256 considered quantum-resistant while AES-128 is not?

Quantum Key Distribution (QKD)

QKD (Quantum Key Distribution) is a technology for distributing keys with information-theoretic security: safety is guaranteed by the laws of physics, not computational hardness. The BB84 protocol (Bennett and Brassard, 1984): quantum bits (photons) are transmitted in random bases. If an eavesdropper measures the photons, detectable errors are introduced. The key is accepted only when the error rate falls below a threshold (~11%).

QKD limitations: maximum range ~500 km (photon loss in fiber), requires a dedicated quantum channel, and is vulnerable to attacks on hardware rather than the protocol. QKD networks are deployed in China (2000 km Beijing-Shanghai backbone), Japan, and Europe (OpenQKD project). Post-quantum cryptography (mathematical) is a more practical solution for mass deployment.

How does QKD fundamentally differ from post-quantum cryptography?

Practical Impact of Quantum Computers

Crypto-agility is the ability of a system to quickly swap cryptographic algorithms without a full rewrite. This is a key requirement for modern systems. TLS 1.3 already supports hybrid modes: X25519+Kyber768 simultaneously (classical + post-quantum). Google Chrome has included Kyber for connections to Google servers since 2023. Cloudflare similarly. NIST 2024: three final standards - FIPS 203 (ML-KEM/Kyber), FIPS 204 (ML-DSA/Dilithium), FIPS 205 (SLH-DSA/SPHINCS+).

Harvest Now, Decrypt Later is real: intelligence agencies and large adversaries are likely already collecting encrypted traffic. Long-retention data such as medical records stored for 30+ years is critically exposed. The first victims will be governments, defense industries, and pharmaceuticals. Migration to PQC is not a question of 'if' but 'when'. NIST recommends beginning migration immediately.

What is Harvest Now, Decrypt Later and why is it a threat today?

The Quantum Threat

  • **Shor's algorithm**: factorization in O((log N)^3) - completely breaks RSA, DH, and ECDH/ECDSA.
  • **Grover's algorithm**: quadratic speedup of brute-force search - AES-128 becomes insecure; AES-256 remains sufficient.
  • **QKD**: physically secure key distribution, but expensive and limited to ~500 km range.
  • **HNDL**: today's data is already at risk - migration to PQC must begin immediately.

Related Topics

The quantum threat motivates post-quantum cryptography research and highlights the limitations of classical schemes.

  • Post-Quantum Cryptography — The direct response to Shor's algorithm: Kyber, Dilithium, and SPHINCS+.
  • RSA: Mathematics — Shor's algorithm destroys the factorization problem on which RSA is based.
  • ECC in Practice — The elliptic curve discrete logarithm is also vulnerable to Shor's algorithm.

Вопросы для размышления

  • If quantum computers are only expected in 10-15 years, why are NIST and major companies starting migration now rather than in 5 years?
  • QKD provides unconditional security but PQC only computational security. Why is PQC considered the more practical solution for most use cases?
  • Which category of data has the highest HNDL risk today: banking transactions, medical records, or government communications?

Связанные уроки

  • qc-01
  • nt-12
The Quantum Threat to Cryptography