QuantumSafe
// Research

The quantum threat, and the math that defends against it

Why a quantum computer breaks today's public-key cryptography, why lattice schemes survive it, and how QuantumSafe implements both sides. Every algorithm below is runnable in this repo.

1. The threat model

Public-key cryptography rests on problems that are hard for classical computers: integer factorization (RSA) and the discrete logarithm (Diffie-Hellman, elliptic curves). Two quantum algorithms change the picture:

"Harvest now, decrypt later": an adversary can record encrypted traffic today and decrypt it once a cryptographically-relevant quantum computer exists. For data that must stay secret for years, the threat is effectively present now — which is why migration is a present-day engineering problem, not a future one.

2. Shor's algorithm (breaks RSA / ECC)

Shor reduces factoring N = p·q to order-finding: the period r of f(x) = aˣ mod N. Quantum phase estimation over a modular-exponentiation operator, followed by an inverse Quantum Fourier Transform, yields a measurement of s/r; continued fractions recover r. If r is even and a^(r/2) ≢ −1 (mod N), then gcd(a^(r/2) ± 1, N) are non-trivial factors. With p and q the RSA private exponent d ≡ e⁻¹ (mod φ(N)) follows immediately.

Run it: python quantum/shor.py — factors N=15 and reconstructs an RSA key.  ·  python quantum/resources.py — qubit/depth/gate cost vs. RSA-2048 estimates.

3. Grover's algorithm (weakens AES / hashes)

Grover finds a marked item in an unstructured space of size N in ≈ (π/4)√N iterations via amplitude amplification (an oracle reflection plus a diffuser). For a k-bit key, brute force drops from 2^k to ~2^(k/2) — effective strength is halved. The fix is to double sizes: AES-128 → AES-256, SHA-256 → SHA-384/512. AES-256 still needs ~2^128 Grover iterations, which remains infeasible.

Run it: python quantum/grover.py

4. Learning With Errors — the post-quantum foundation

Lattice schemes base security on the Learning With Errors (LWE) problem: given A and b = A·s + e (mod q) with a small error e, recover the secret s. This is provably as hard as worst-case lattice problems. Crucially, LWE has no periodic / hidden-subgroup structure for Shor to exploit, so the best known quantum attacks offer only modest speedups — it stays hard.

Run it: python pqc/lwe_kem.py — a full quantum-safe key exchange.  ·  python pqc/benchmark.py — sizes & latency vs. RSA / ML-KEM.

5. CRYSTALS-Kyber / ML-KEM and the NIST standards

ML-KEM (the standardized form of CRYSTALS-Kyber) is a Module-LWE key-encapsulation mechanism: it adds ring structure for efficiency (fast NTT-based multiplication) and a Fujisaki-Okamoto transform for chosen-ciphertext security. QuantumSafe's pqc/ module implements the underlying LWE construction to demonstrate the math. In 2024 NIST finalized the first post-quantum standards:

References