Shor vs Lattice: Post-Quantum Cryptography

RSA / ECC vault

Key size (RSA modulus, bits) Logical qubits available

Available: 4000

Lattice vault (Kyber-style)

Lattice dimension n

Live status

Qubits needed (RSA)

–

Qubit gap

–

RSA/ECC vault

LOCKED

Lattice vault

SECURE

Legend

RSA/ECC vault door Shor period-finding waveform Lattice point (public basis) Shortest vector (the secret key) Search probe (BKZ / quantum-assisted walk)

Attack log

Turn the quantum computer on and raise the qubit count to attempt Shor's algorithm on the RSA/ECC vault.

How it works

Both vaults protect the same kind of secret — but the mathematics behind them belongs to different complexity classes once a fault-tolerant quantum computer exists.

RSA/ECC: hardness = integer factoring / discrete log
  Shor's algorithm finds the period r of a^x mod N
  using a quantum Fourier transform, then
  gcd(a^(r/2) ± 1, N) reveals the factors.
  -> runs in polynomial time on a quantum computer
  -> classically: no known polynomial algorithm

Lattice (Kyber/Dilithium-style): hardness = SVP/LWE
  find the shortest nonzero vector in a lattice
  of dimension n built from the public basis.
  -> best known classical AND quantum attacks
     (BKZ / quantum-assisted BKZ) still scale
     exponentially in n
  -> Shor's period-finding trick does not apply:
     there is no periodic structure to extract

RSA/ECC vault — the estimated logical-qubit register size shown here follows the commonly cited approximation of roughly 2 × keysize + 3 qubits for Shor's period-finding circuit on an n-bit modulus. It is an order-of-magnitude illustration, not a fault-tolerant engineering estimate (real proposals add heavy error-correction overhead on top). Below that threshold, or with the quantum computer off, classical factoring (GNFS) is used instead — no classical or quantum computer has ever factored a modulus this large, so the vault stays locked.
Lattice vault — raising the qubit count or flipping the quantum toggle does nothing here. The best known quantum attack on generic search (Grover's algorithm) only gives a quadratic speedup, not the exponential speedup Shor's algorithm gives against factoring — so it barely dents an exponential-time problem. This is the actual reason NIST standardized lattice-based Kyber (key encapsulation) and Dilithium (signatures) as post-quantum replacements for RSA/ECC.
Increasing the lattice dimension n grows the vault's basis and the exponent in the attack's running time, which is why real post-quantum schemes pick n in the hundreds (512–1024) rather than needing astronomically large keys the way a naive fix would.

RSA/ECC: LOCKED

LATTICE: SECURE

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.