Cryptanalysis & Post-Quantum Cryptography and Quantum Computing

Qubit Requirement

~4000 logical qubits to break RSA-2048; millions of physical qubits with current error rates

Timeline Estimate

Cryptographically relevant quantum computer: >10 years away

Factors N-bit integers in O(N³) quantum gates using quantum Fourier transform for period finding. Breaks RSA and integer-based cryptography. Solves discrete log for ECC.

Searches an unstructured database of N items in O(√N) quantum oracle calls, providing quadratic speedup. Reduces effective symmetric key security by half (AES-256 → 128-bit classical security).

Subroutine within Shor's algorithm and other number-theoretic algorithms. Computes the discrete Fourier transform exponentially faster than classical FFT for quantum input.

Uses quantum properties (BB84, E91) to distribute cryptographic keys with information-theoretic security. Not a quantum computing algorithm — uses photon transmission. Distinct from the Shor/Grover threat model.

Qubit Count

~4,000 logical qubits to break RSA-2048 (Beauregard circuit). At current physical-to-logical qubit ratios (~1,000:1 for surface codes), this implies ~4 million physical qubits with excellent error rates.

Circuit Depth

Shor's algorithm for RSA-2048 requires ~1.5 billion Toffoli gates (Webber et al. 2022 resource estimate). At 1 MHz logical clock rate, this is ~25 minutes per factoring instance.

Error Tolerance

Requires logical error rates of 10⁻¹⁰ per gate or lower for Shor's circuit length. Surface code with 1,000 physical qubits per logical qubit achieves this if physical error rates are below 10⁻³.

Key Limitation

Every qubit improvement in physical error rate reduces the physical qubit overhead dramatically. Hardware progress is the critical variable — if physical error rates reach 10⁻⁴, the physical qubit requirement drops from millions to hundreds of thousands.

Largest available qubit counts; IBM has demonstrated QFT and Bernstein-Vazirani subroutines. Decades from Shor-relevant scale. Fast gates reduce logical clock cycle time once fault-tolerant.

Highest two-qubit gate fidelity of any commercial platform; Quantinuum has demonstrated small Shor circuits. All-to-all connectivity reduces SWAP overhead for Shor modular arithmetic. Slow gates (millisecond) increase Shor runtime per factoring instance.

Promising long-term platform for fault-tolerant computation; long coherence times. No Shor demonstrations; gate error rates still maturing. Reconfigurable arrays may suit lattice surgery for surface codes.

Photonic platforms can in principle execute Shor's algorithm but require measurement-based quantum computation with huge resource overheads. Photonic computing operates at room temperature and high clock rates but faces extreme photon loss challenges.

Cannot run Shor's or Grover's algorithms — these require gate-based universal quantum computation. D-Wave quantum annealing is not a threat to cryptography.

Microsoft's topological qubit approach targets logical error rates 10× lower than superconducting platforms, which could reduce the physical qubit count for Shor by an order of magnitude. The most plausible path to a compact CRQC, if topological qubits achieve the predicted error rates.

Algorithms for Quantum Computation: Discrete Logarithms and Factoring

Shor, P.W. · 1994 · FOCS 1994

Original Shor's algorithm paper; exponential speedup for integer factoring proven.

Post-Quantum Cryptography Standards

NIST · 2024 · NIST FIPS 203, 204, 205

ML-KEM (CRYSTALS-Kyber), ML-DSA (CRYSTALS-Dilithium), SLH-DSA (SPHINCS+) finalized as PQC standards.

The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime

Webber, M. et al. · 2022 · AVS Quantum Science

Resource estimates for breaking RSA-2048: ~4,000 logical qubits, ~4 million physical qubits needed.

Is my encrypted data safe from quantum computers right now?

Yes — no quantum computer today can break any production encryption. RSA-2048, AES-256, and ECC remain completely secure against any quantum hardware currently in existence or planned for the next several years. The threat is "harvest now, decrypt later": adversaries could be collecting encrypted data now, hoping to decrypt it when CRQCs exist in 10–15 years. Organizations with long-term data sensitivity (national security, healthcare records) should begin migrating to NIST-standardized post-quantum algorithms (ML-KEM, ML-DSA) now.

What is post-quantum cryptography and why does it matter?

Post-quantum cryptography (PQC) refers to classical cryptographic algorithms designed to resist attack by quantum computers. They run on ordinary classical hardware but are based on mathematical problems believed to be hard for quantum algorithms (lattice problems, hash functions, code-based cryptography). NIST finalized PQC standards in 2024 (FIPS 203/204/205), and all organizations should plan PQC migration timelines — especially for systems with long operational lifetimes.

Why does Shor's algorithm need ~4,000 logical qubits for RSA-2048?

Shor's algorithm for an N-bit RSA modulus requires approximately 2N logical qubits for the modular exponentiation circuit, plus ancilla qubits. For RSA-2048 (N=2048), this is roughly 4,096 logical qubits. Each logical qubit in a surface code error-correction scheme requires ~1,000 physical qubits at realistic error rates, totaling ~4 million physical qubits — far beyond any existing or near-term system.

Does Grover's algorithm break AES encryption?

Grover's algorithm halves the effective key search space, reducing AES-128 to 2^64 effective security (which is vulnerable to classical pre-computation attacks) and AES-256 to 2^128 (which remains secure). Practically, Grover's attack on AES-256 requires ~10^24 quantum operations — computationally infeasible even on theoretical large-scale quantum computers. The recommendation is to use AES-256 for quantum-resistant symmetric security.