Chapter 30: Quantum Cryptography and Post-Quantum Security

QKD, Lattice-Based Crypto, and the Race to Protect Data Before Quantum Computers Break It

Learning Objectives

By the end of this chapter, you will be able to:

• Explain how Shor's algorithm threatens RSA, ECC, and Diffie-Hellman key exchange
• Describe the "harvest now, decrypt later" threat model and its urgency
• Enumerate the NIST post-quantum cryptography finalists and their mathematical foundations
• Implement a simplified Learning With Errors (LWE) encryption scheme in Python
• Understand the BB84 and E91 quantum key distribution protocols
• Evaluate the practical limitations of QKD and the case for hybrid cryptography
• Articulate the transition timeline from classical to post-quantum cryptography
• Derive the security reductions for lattice-based cryptography
• Analyze the performance trade-offs between PQC algorithms
• Design a migration plan for organizations transitioning to post-quantum security

30.1 The Quantum Threat to Public-Key Cryptography

The security of the modern internet rests on a mathematical accident: certain problems are easy in one direction and hard in the other. Multiplying two large primes is straightforward; factoring the product back into its constituent primes is believed to be exponentially hard for classical computers. This asymmetry underpins RSA, the most widely deployed public-key cryptosystem in history. Elliptic curve cryptography (ECC) relies on a similar asymmetry: the discrete logarithm problem on elliptic curves.

In 1994, Peter Shor demonstrated that this asymmetry dissolves in the presence of a sufficiently large quantum computer. Shor's algorithm factors an $n$-bit integer in $O(n^2 \log n \log \log n)$ time — polynomial in the input size. For comparison, the best known classical algorithm, the general number field sieve, runs in subexponential time $O(\exp((64/9)^{1/3} n^{1/3} (\log n)^{2/3}))$.

The implications are stark. A quantum computer with approximately 4,000 logical qubits (or roughly 20 million physical qubits under current error correction schemes) could break RSA-2048 in hours. ECC keys are even more vulnerable: breaking a 256-bit ECC key requires fewer qubits than breaking RSA-2048.

Common Misconception: "Quantum computers can break all cryptography."

Shor's algorithm breaks public-key cryptography based on factoring and discrete logarithms. It does not break symmetric-key cryptography (AES, ChaCha20) or hash functions (SHA-256). Grover's algorithm provides at most a quadratic speedup for brute-force attacks on symmetric ciphers, which is easily countered by doubling the key length (AES-256 remains secure). The threat is specifically to RSA, ECC, Diffie-Hellman, and other schemes based on the hardness of factoring or discrete logarithms.

30.1.1 What Shor's Algorithm Actually Does

Recall from Chapter 17 that Shor's algorithm reduces factoring to period finding. Given an integer $N$ to factor:

1. Choose a random $a < N$ coprime to $N$
2. Use the quantum period-finding subroutine to find the order $r$ of $a$ modulo $N$
3. If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2} \pm 1, N)$ yields nontrivial factors

The quantum core is the period-finding circuit:

     ┌───┐ ┌──────────────────────┐
|0⟩──┤ H ├─┤                      ├──•── QFT⁻¹ ── Measure
     └───┘ │                      │  │
|0⟩──┤ H ├─┤  Modular             ├──•── QFT⁻¹ ── Measure
     └───┘ │  Exponentiation       │  │
     ...    │  U_a |x⟩ = |ax mod N⟩│ ...
     ┌───┐ │                      │  │
|0⟩──┤ H ├─┤                      ├──•── QFT⁻¹ ── Measure
     └───┘ └──────────────────────┘  │
                                     │
|1⟩──────────────────────────────────•────────────────

The modular exponentiation $U_a$ is the expensive part, requiring $O(n^3)$ gates. This is what drives the physical qubit requirements into the millions.

Detailed resource estimate for factoring RSA-2048:

The most detailed resource estimates for Shor's algorithm on RSA-2048 give:

These estimates assume gate error rates of $10^{-4}$ (well within current capabilities for superconducting qubits) and a surface code distance of $d = 27$. The key bottleneck is not the number of qubits per se, but the required circuit depth and the overhead of error correction. We're at the beginning — current quantum computers have ~1,000 qubits with error rates of $10^{-2}$ to $10^{-3}$, far from the requirements for cryptographically relevant Shor's algorithm.

30.1.2 The "Harvest Now, Decrypt Later" Problem

A particularly insidious threat is the store-now-decrypt-later (SNDL) attack. Adversaries — nation-states, organized crime — can record encrypted traffic today and store it indefinitely. When quantum computers become available, they will retroactively decrypt this traffic.

Consider the implications:

• State secrets with 30-year classification periods are already at risk
• Financial records, medical data, and personal communications have long-term sensitivity
• Software update signing keys — if compromised retroactively, every device that ever trusted that key is vulnerable
• Blockchain and cryptocurrency — transactions signed with ECDSA today could be forged tomorrow

The timeline is uncertain but the threat is not. The question is not if quantum computers will break RSA, but when. And for data with long-term sensitivity, "when" may already be "now."

Quantitative risk assessment:

Michele Mosca's theorem provides a framework for assessing the urgency:

$$P(\text{risk}) = P(\text{QC arrives before transition}) + P(\text{transition takes too long})$$

If a quantum computer that can break RSA-2048 arrives within $Y$ years, and the transition to post-quantum cryptography takes $Z$ years, then data with sensitivity lifetime $X$ years is at risk if:

$$Y < X + Z$$

For $X = 25$ years (classified data), $Z = 10$ years (realistic transition time), and $Y = 15$ years (optimistic quantum timeline): the data is at risk today, because $15 < 25 + 10 = 35$ means the adversary has 20 years to harvest before the data becomes irrelevant.

30.2 The NIST Post-Quantum Cryptography Standardization

In 2016, NIST initiated a public competition to select quantum-resistant cryptographic algorithms. After three rounds of evaluation, NIST published its first three final standards on August 13, 2024 (effective August 14).

30.2.1 The Winners

Be careful with the word "winner" — it is used loosely in press coverage. Only three algorithms are published FIPS standards today; the rest are selected-but-unpublished or still under evaluation.

Published standards (final, August 2024):

Selected but not yet published as standards:

Still under evaluation (Round 4 / on-ramp):

NIST selected a diversity of mathematical foundations to hedge against future cryptanalytic breakthroughs. If one hard problem falls, others may remain standing. HQC matters specifically for this reason: ML-KEM and FALCON are both lattice-based, so a lattice breakthrough would take out the primary KEM and one signature scheme at once. HQC is code-based, giving the ecosystem a KEM that does not share that assumption.

Performance comparison:

The key observation: PQC algorithms have larger keys and ciphertexts than RSA/ECC, but their performance is in the same ballpark for lattice-based schemes. Classic McEliece has enormous public keys (~1 MB) but very fast encryption and decryption.

30.2.2 The Mathematical Zoo of Post-Quantum Cryptography

Post-quantum cryptography draws from several families of hard problems:

Lattice-Based Cryptography. The most promising and versatile family. Security rests on the hardness of problems like the Shortest Vector Problem (SVP) and Learning With Errors (LWE) in high-dimensional lattices. Lattice problems are believed to be hard even for quantum computers. Kyber and Dilithium are lattice-based.

Hash-Based Signatures. The oldest and most conservative approach. Security relies solely on the collision resistance of cryptographic hash functions. SPHINCS+ is a stateless hash-based signature scheme. The trade-off: large signatures (tens of kilobytes).

Code-Based Cryptography. Based on the hardness of decoding random linear codes. Classic McEliece uses Goppa codes, which have resisted attack for over 40 years. The public key is large (~1 MB) but encryption is fast.

Multivariate Cryptography. Based on the hardness of solving systems of multivariate polynomial equations over finite fields. Several schemes were broken during the NIST competition, but research continues.

Isogeny-Based Cryptography. Based on finding isogenies (maps) between supersingular elliptic curves. SIKE was a promising candidate until it was broken on a laptop in 2022 — a sobering reminder that post-quantum security assumptions need more scrutiny.

Common Misconception: "Post-quantum cryptography is just as secure as classical cryptography."

Post-quantum algorithms are newer and have received less cryptanalytic scrutiny than RSA and ECC, which have been studied for 40+ years. The security estimates for PQC algorithms come with larger uncertainty bands. This is why NIST selected multiple algorithms based on different mathematical foundations — as a hedge against future attacks. We're at the beginning of PQC deployment, and the security guarantees will strengthen over time as the community gains more confidence in these constructions.

30.3 Lattice-Based Cryptography: Learning With Errors

The Learning With Errors (LWE) problem is the workhorse of modern post-quantum cryptography. Its elegance lies in its simplicity.

30.3.1 The LWE Problem

Given: - A secret vector $\mathbf{s} \in \mathbb{Z}_q^n$ - Many samples $(\mathbf{a}_i, b_i)$ where $\mathbf{a}_i \in \mathbb{Z}_q^n$ is random and $b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \pmod{q}$, with $e_i$ drawn from a small error distribution

Search-LWE: Find $\mathbf{s}$. Decision-LWE: Distinguish LWE samples from uniformly random $(\mathbf{a}_i, b_i)$.

Both are believed to be hard for quantum computers when parameters are chosen appropriately.

The relationship between LWE and lattice problems:

Regev (2009) proved that solving LWE (with appropriate parameters) is as hard as solving the GapSVP (Gap Shortest Vector Problem) and SIVP (Shortest Independent Vectors Problem) on worst-case lattices, via a quantum reduction. This means:

1. If you can solve LWE, you can solve these hard lattice problems (via a classical reduction)
2. These lattice problems have no known efficient quantum algorithm
3. Therefore, breaking LWE requires a breakthrough in quantum algorithms for lattice problems

This worst-case to average-case reduction is what gives LWE its strong security guarantee: even the hardest lattice instance is no harder than a random LWE instance.

Detailed parameter analysis:

The security of LWE depends on three parameters: - $n$: the dimension (typically 256–1024) - $q$: the modulus (typically 3329 for Kyber, much larger for other schemes) - $\sigma$: the error standard deviation (typically 1–3)

The best known attack on LWE is the primal or dual lattice attack, which requires time:

$$T_{\text{attack}} \approx 2^{c \cdot n / \log(q/\sigma)}$$

where $c$ is a constant depending on the lattice reduction algorithm used. For Kyber-768 ($n = 768$, $q = 3329$, $\sigma \approx 1.5$), this gives security level $\sim 2^{256}$, matching AES-256 security.

30.3.2 A Simplified LWE Encryption Scheme

Let's implement a toy LWE-based public-key encryption scheme. This is educational — real schemes use ring or module variants for efficiency.

import numpy as np

class LWEParams:
    """Toy LWE parameters (NOT SECURE — for education only)."""
    def __init__(self, n=256, q=3329, sigma=3.0):
        self.n = n          # dimension
        self.q = q          # modulus
        self.sigma = sigma  # error standard deviation

def keygen(params):
    """Generate public and secret keys."""
    n, q = params.n, params.q
    # Secret key: random small vector
    s = np.random.randint(-2, 3, size=n) % q
    # Public key: (A, b = A·s + e)
    A = np.random.randint(0, q, size=(n, n))
    e = np.round(np.random.normal(0, params.sigma, size=n)).astype(int) % q
    b = (A @ s + e) % q
    return (A, b), s  # (public_key, secret_key)

def encrypt(pk, message_bit, params):
    """Encrypt a single bit using LWE."""
    A, b = pk
    n, q = params.n, params.q
    # Random binary vector
    r = np.random.randint(0, 2, size=n)
    # Ciphertext: (c1 = A^T·r, c2 = b·r + message_bit * floor(q/2))
    c1 = (A.T @ r) % q
    e_prime = np.round(np.random.normal(0, params.sigma)).astype(int)
    c2 = (np.dot(b, r) + message_bit * (q // 2) + e_prime) % q
    return (c1, c2)

def decrypt(sk, ct, params):
    """Decrypt a ciphertext."""
    s = sk
    c1, c2 = ct
    q = params.q
    # Compute c2 - c1·s ≈ message_bit * floor(q/2) + noise
    v = (c2 - np.dot(c1, s)) % q
    # Decode: if v is closer to q/2 than to 0, message is 1
    if abs(v - q // 2) < q // 4 or abs(v - q // 2) > 3 * q // 4:
        return 1
    else:
        return 0

# Demonstration
params = LWEParams(n=256, q=3329, sigma=3.0)
pk, sk = keygen(params)

# Encrypt and decrypt 100 random bits
errors = 0
for _ in range(100):
    bit = np.random.randint(0, 2)
    ct = encrypt(pk, bit, params)
    decrypted = decrypt(sk, ct, params)
    if bit != decrypted:
        errors += 1

print(f"Decryption errors: {errors}/100")
print(f"Error rate: {errors}%")

The correctness of this scheme depends on the noise not exceeding $q/4$. The error terms accumulate: $e \cdot r + e'$ must remain small. With appropriate parameters, the decryption error rate can be made negligible.

Why does decryption work?

The decryption computes:

$$v = c_2 - \mathbf{c}_1 \cdot \mathbf{s} = (\mathbf{b} \cdot \mathbf{r} + m \cdot \lfloor q/2 \rfloor + e') - (\mathbf{A}^T \mathbf{r}) \cdot \mathbf{s}$$

Substituting $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$:

$$v = \mathbf{r}^T \mathbf{A} \mathbf{s} + \mathbf{r}^T \mathbf{e} + m \cdot \lfloor q/2 \rfloor + e' - \mathbf{r}^T \mathbf{A} \mathbf{s}$$

The $\mathbf{r}^T \mathbf{A} \mathbf{s}$ terms cancel, leaving:

$$v = \mathbf{r}^T \mathbf{e} + m \cdot \lfloor q/2 \rfloor + e' \pmod{q}$$

If $\mathbf{r}^T \mathbf{e} + e'$ is small compared to $q/4$, then $v$ is close to 0 (if $m = 0$) or close to $q/2$ (if $m = 1$), and the decryption succeeds.

30.3.3 Why Lattices Resist Quantum Attacks

The best known quantum algorithm for lattice problems is the same as the best known classical algorithm (up to polynomial factors): lattice basis reduction (BKZ, sieving). There is no known quantum algorithm that provides an exponential speedup for SVP or LWE, unlike factoring.

The quantum speedup for lattice problems is limited to: 1. Grover's algorithm: Provides a $\sqrt{2}$ speedup for exhaustive search within lattice reduction, reducing the attack cost by a factor of $\sim 2^{n/2}$ — significant, but countered by doubling the dimension. 2. Quantum walk algorithms: Provide polynomial speedups for sieving, reducing the time from $2^{0.292n}$ to $2^{0.265n}$ — a small improvement.

This is not a proof of security — no such proof exists for any public-key cryptosystem — but after 25+ years of intense scrutiny, the confidence is high.

Try It Yourself: LWE Error Accumulation

In the toy LWE scheme above, the error in the ciphertext is $e_{\text{total}} = \mathbf{r}^T \mathbf{e} + e'$. For $n = 256$, $\mathbf{r}$ has approximately $n/2 = 128$ nonzero entries (each 0 or 1), and each $\mathbf{e}_i$ is drawn from $\mathcal{N}(0, \sigma^2)$. Estimate the standard deviation of $e_{\text{total}}$ using the central limit theorem. For $\sigma = 3$ and $q = 3329$, what is the probability that $|e_{\text{total}}| > q/4$? This determines the decryption error rate.

30.4 Hash-Based Signatures

Hash-based signatures are the most conservative post-quantum option. Their security reduces to the preimage resistance of the underlying hash function — a property that quantum computers affect only quadratically (via Grover's algorithm). Doubling the hash output length neutralizes this.

30.4.1 Lamport One-Time Signatures

The simplest construction, due to Leslie Lamport (1979):

Key Generation: For a 256-bit hash, generate 256 pairs of random 256-bit values: $(x_1^0, x_1^1), (x_2^0, x_2^1), \ldots, (x_{256}^0, x_{256}^1)$. The public key is the hash of each: $(y_i^b = H(x_i^b))$.

Signing: To sign a 256-bit message $m$, reveal $x_i^{m_i}$ for each bit $i$. The signature is 256 × 256 = 8 KB.

Verification: Hash each revealed $x_i^{m_i}$ and check against the public key.

Critical limitation: Each key pair can sign exactly one message. Signing two messages reveals both $x_i^0$ and $x_i^1$ for some positions, allowing forgeries.

Detailed security analysis:

An adversary who sees a signature on message $m$ learns $x_i^{m_i}$ for each $i$. To forge a signature on a different message $m'$, they would need to find $x_i^{1-m_i}$ for at least one position where $m_i' \neq m_i$. Since $x_i^{1-m_i}$ is a random 256-bit value, the probability of finding it via brute force is $2^{-256}$ — infeasible even for a quantum computer (Grover's algorithm reduces this to $2^{-128}$, still infeasible).

The limitation to one-time use is severe. For $k$ signatures, Lamport requires $2k$ times as much public key material. This motivates Merkle trees.

30.4.2 From One-Time to Many-Time: Merkle Trees

Merkle trees extend one-time signatures to sign many messages. The idea:

                    Root (public key)
                   /                \
              H(N1||N2)          H(N3||N4)
             /        \         /        \
          N1=H(PK1)  N2=H(PK2) N3=H(PK3) N4=H(PK4)
             |          |         |         |
            PK1        PK2       PK3       PK4

Each leaf is the hash of a one-time public key. To sign with $PK_i$, the signer reveals: 1. The signature on the message using $SK_i$ 2. The authentication path from $PK_i$ to the root: $(N_{i \oplus 1}, H(N_{i \oplus 1} || N_i), \ldots)$

The verifier hashes the authentication path to reconstruct the root and compares it to the public key.

Worked Example 30.1: Merkle Tree Signing

For a tree of height $h$, the signer can produce $2^h$ signatures. Each signature includes: - The one-time signature (e.g., 8 KB for Lamport) - The authentication path ($h \times 32$ bytes, assuming 256-bit hashes)

For $h = 10$ (1024 signatures): total signature size = 8 KB + 10 × 32 B = 8.3 KB. This is manageable, but for $h = 20$ (1 million signatures), the tree requires generating and storing $2^{20}$ one-time key pairs — a significant key generation overhead.

SPHINCS+ uses a hyper-tree of Merkle trees with a few-time signature scheme (FORS — Forest of Random Subsets) at the leaves, achieving stateless operation at the cost of larger signatures (~30 KB for 256-bit security).

Common Misconception: "Hash-based signatures are too large to be practical."

SPHINCS+ signatures are 7.9–49 KB depending on the security level and speed/size trade-off. This is larger than RSA-2048 (256 B) or Dilithium (2.5 KB), but still practical for most applications. A TLS handshake with SPHINCS+ adds ~30 KB — about 10× larger than RSA, but transmitted in milliseconds on modern networks. The trade-off is conservative security (hash-only assumption) for larger signatures.

30.5 Quantum Key Distribution (QKD)

QKD uses quantum mechanics to distribute symmetric keys with information-theoretic security. Unlike post-quantum cryptography, QKD's security does not rely on computational assumptions — it relies on the laws of physics.

30.5.1 BB84 Protocol

Proposed by Bennett and Brassard in 1984, BB84 remains the most studied QKD protocol.

The Setup:

Alice and Bob are connected by a quantum channel (optical fiber or free space) and an authenticated classical channel.

Protocol Steps:

1. Preparation (Alice): For each bit, Alice randomly chooses a basis: - Z-basis (computational): $|0\rangle$ encodes 0, $|1\rangle$ encodes 1 - X-basis (Hadamard): $|+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$ encodes 0, $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$ encodes 1

2. Transmission: Alice sends each qubit to Bob through the quantum channel.

3. Measurement (Bob): For each received qubit, Bob randomly chooses Z or X basis and measures.

4. Sifting (classical channel): Alice and Bob publicly announce which bases they used (but not the bit values). They discard bits where their bases differed. On average, 50% of bits survive.

5. Error Estimation: They reveal a random subset of the sifted key to estimate the quantum bit error rate (QBER). If QBER exceeds a threshold (~11%), they abort — an eavesdropper is likely present.

6. Information Reconciliation: They perform error correction on the remaining bits.

7. Privacy Amplification: They apply a randomness extractor (e.g., a universal hash function) to reduce any partial information Eve may have gained to negligible levels.

ASCII Art: BB84 Protocol Flow

Alice                                    Eve?              Bob
──────                                                      ─────
│                                                             │
│  Random bits:    1 0 1 1 0                                 │
│  Random bases:   Z X X Z X                                 │
│  Encode:        |1⟩|+⟩|-⟩|1⟩|+⟩                            │
│                                                             │
│  ═════════════════════════════════════►  Quantum Channel       │
│       (fiber / free-space)                                  │
│                                                             │
│                                        Random bases:  X Z X Z X
│                                        Measure:       |+⟩|0⟩|-⟩|1⟩|+⟩
│                                                             │
│  ◄═══════════════════════════════════  Classical Channel     │
│       "I used Z, X, X, Z, X"                               │
│                                                             │
│  ◄═══════════════════════════════════  "I used X, Z, X, Z, X"
│                                                             │
│  Matching positions:    2, 3, 5                             │
│  Sifted key:            0, 1, 0    (Alice)                 │
│  Sifted key:            0, 1, 0    (Bob)                    │
│                                                             │
│  Error estimation, reconciliation, privacy amplification   │
│  ═══════════════════════════════════►                       │
│  ◄═══════════════════════════════════                       │
│                                                             │
│  Final shared secret key                                    │
│                                                             │

Detailed security analysis of BB84:

The security of BB84 rests on two principles:

1. No-cloning theorem: Eve cannot make a copy of an unknown quantum state. If she tries to intercept and measure a qubit, she must choose a basis, and half the time she will choose the wrong basis, introducing errors.

2. Measurement disturbance: Any measurement that extracts information about the qubit also disturbs it. The Heisenberg uncertainty principle ensures that Eve's measurements on the wrong basis leave detectable traces.

The quantitative security proof shows that for QBER $= \epsilon$, Eve's information about the sifted key is at most $I_{\text{Eve}} \leq h(\epsilon)$, where $h$ is the binary entropy function. After privacy amplification with a universal hash function of output length $\ell = n - I_{\text{Eve}} - s$ (where $s$ is a security parameter), Eve's information about the final key is at most $2^{-s}$ — negligible.

The threshold QBER of ~11% comes from the condition that $I_{\text{Eve}} < I_{\text{Alice-Bob}}$, i.e., Eve has less information than Bob. For BB84, this threshold is:

$$\epsilon_{\text{threshold}} = 1 - h^{-1}(1/2) \approx 0.110$$

where $h^{-1}$ is the inverse binary entropy function.

30.5.2 E91 Protocol: Entanglement-Based QKD

Artur Ekert's 1991 protocol uses entangled pairs. A source emits Bell pairs $|\Phi^+\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}}$, sending one qubit to Alice and one to Bob. They measure in randomly chosen bases and test the CHSH inequality. A violation of the CHSH inequality certifies entanglement and thus security.

The CHSH inequality:

The CHSH parameter $S$ is defined as:

$$S = |E(a_1, b_1) + E(a_1, b_2) + E(a_2, b_1) - E(a_2, b_2)|$$

where $E(a_i, b_j)$ is the correlation between Alice's measurement setting $a_i$ and Bob's setting $b_j$. For local hidden variable theories, $|S| \leq 2$. For quantum mechanics with entanglement, $S = 2\sqrt{2} \approx 2.83$.

The security argument: if $S > 2$, the measurement outcomes cannot be explained by any local hidden variable theory, which means they cannot be pre-determined by any eavesdropper. The degree of violation directly bounds Eve's information about the key.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
import numpy as np

def bb84_single_qubit(alice_bit, alice_basis):
    """Prepare a single BB84 qubit."""
    qc = QuantumCircuit(1, 1)
    # Encode Alice's bit
    if alice_bit == 1:
        qc.x(0)
    # Apply basis transformation
    if alice_basis == 'X':
        qc.h(0)
    return qc

def bb84_measure(circuit, bob_basis):
    """Bob measures in his chosen basis."""
    if bob_basis == 'X':
        circuit.h(0)
    circuit.measure(0, 0)
    return circuit

def simulate_bb84(n_bits=100, eavesdropper=False):
    """Simulate BB84 with optional eavesdropper."""
    sim = AerSimulator()

    alice_bits = np.random.randint(0, 2, n_bits)
    alice_bases = np.random.choice(['Z', 'X'], n_bits)
    bob_bases = np.random.choice(['Z', 'X'], n_bits)

    bob_results = []
    for i in range(n_bits):
        qc = bb84_single_qubit(alice_bits[i], alice_bases[i])

        # Eve intercepts and resends (if present)
        if eavesdropper:
            eve_basis = np.random.choice(['Z', 'X'])
            if eve_basis == 'X':
                qc.h(0)
            qc.measure(0, 0)
            # Re-prepare based on Eve's measurement
            # (simplified — in reality Eve would need to re-prepare)

        qc = bb84_measure(qc, bob_bases[i])
        job = sim.run(qc, shots=1)
        result = int(list(job.result().get_counts().keys())[0])
        bob_results.append(result)

    # Sifting
    matching = alice_bases == bob_bases
    alice_sifted = alice_bits[matching]
    bob_sifted = np.array(bob_results)[matching]

    # Error rate
    error_rate = np.mean(alice_sifted != bob_sifted)

    return {
        'sifted_key_length': len(alice_sifted),
        'error_rate': error_rate,
        'alice_sifted': alice_sifted,
        'bob_sifted': bob_sifted
    }

# Without eavesdropper
result_no_eve = simulate_bb84(200, eavesdropper=False)
print(f"No eavesdropper — Error rate: {result_no_eve['error_rate']:.3f}")
print(f"Sifted key length: {result_no_eve['sifted_key_length']}")

# With eavesdropper (intercept-resend)
result_with_eve = simulate_bb84(200, eavesdropper=True)
print(f"With eavesdropper — Error rate: {result_with_eve['error_rate']:.3f}")

In a real implementation, Eve's intercept-resend attack introduces a 25% error rate in the sifted key (she guesses the wrong basis 50% of the time, and when she does, Bob gets a random result 50% of the time: $0.5 \times 0.5 = 0.25$). This is easily detectable.

Detailed derivation of the 25% error rate:

When Eve intercepts, she measures in a random basis. There are four cases:

After sifting (keeping only cases where Alice and Bob used the same basis):

• Cases 1 and 3 (50% of sifted bits): Alice and Eve's bases match → Eve resends correctly → Bob measures correctly → 0% error
• Cases 2 and 4 (50% of sifted bits): Alice and Eve's bases mismatch → Eve disturbs the state → Bob gets a random result → 50% error

Total error rate in sifted key: $0.5 \times 0 + 0.5 \times 0.5 = 0.25 = 25\%$.

This 25% error rate far exceeds the 11% threshold, making the eavesdropper immediately detectable.

30.5.3 Practical Limitations of QKD

Despite its theoretical elegance, QKD faces significant practical challenges:

1. Distance limitations. Optical fiber loss limits QKD to ~100-200 km without trusted nodes or quantum repeaters. The loss in optical fiber is approximately 0.2 dB/km at 1550 nm, meaning 100 km of fiber attenuates the signal by 20 dB (99%). Current QKD systems operate at ~1 Mbps at 50 km and ~1 kbps at 200 km.

2. Key rate. Current QKD systems produce keys at kbps to Mbps rates — sufficient for key distribution but not for one-time-pad encryption of bulk data.

3. Authentication requirement.QKD requires an authenticated classical channel, which itself requires either a pre-shared key or post-quantum signatures. QKD does not eliminate the need for asymmetric cryptography.

4. Hardware vulnerabilities. Side-channel attacks (photon number splitting, detector blinding, Trojan horse attacks) have compromised commercial QKD systems. Security proofs assume perfect devices; real devices are imperfect.

5. Cost and infrastructure. QKD requires dedicated fiber or line-of-sight free-space links. It cannot traverse standard network infrastructure (routers, amplifiers).

6. No authentication or non-repudiation. QKD provides key distribution, not digital signatures. You still need post-quantum signatures for authentication.

Common Misconception: "QKD makes all communication quantum-secure."

QKD only provides information-theoretic security for the key distribution step. The actual data encryption still uses symmetric ciphers (AES-256), which provide computational security. The overall security is: key distribution is unconditionally secure, data encryption is computationally secure. This is a meaningful improvement over classical key distribution (where key exchange is also only computationally secure), but it's not "unconditional security for all communication."

30.6 The Transition Timeline

The migration to post-quantum cryptography is the largest cryptographic transition in history. Every protocol, library, hardware security module, and certificate authority must be updated.

NIST Timeline (actual and projected):

2016 ─── NIST PQC competition announced
  │
2019 ─── Round 2 candidates selected (26 algorithms)
  │
2020 ─── Round 3 finalists announced (7 finalists + 8 alternates)
  │
2022 ─── First algorithms selected (CRYSTALS-Kyber, CRYSTALS-Dilithium,
  │      SPHINCS+, FALCON)
2023 ─── Draft standards released for public comment
  │
2024 ─── FINAL standards published: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA),
  │      FIPS 205 (SLH-DSA) — August 13, 2024
2025 ─── HQC selected as backup KEM (March 11); FIPS 206 (FN-DSA/FALCON)
  │      still in development
  │
2024-2030 ─── Migration period: protocols, libraries, and infrastructure
  │           updated to support hybrid and post-quantum cryptography
2030-2035 ─── Classical public-key cryptography deprecated
  │
2035+ ─── Post-quantum cryptography mandatory for sensitive applications

What organizations should do now:

1. Inventory cryptographic assets. Identify every use of RSA, ECC, and Diffie-Hellman in your systems.
2. Prioritize by data lifetime. Data with 10+ year sensitivity needs immediate attention.
3. Implement crypto-agility. Design systems to swap algorithms without architectural changes.
4. Deploy hybrid schemes. Use classical + post-quantum in parallel during the transition.
5. Test PQC implementations. Start integrating Kyber and Dilithium in non-critical paths.

Detailed migration challenges:

• Key size increases: Kyber-768 public keys are 1,184 bytes vs. 64 bytes for ECC-P256. This affects TLS handshakes, certificate chains, and constrained devices.
• Performance: PQC operations are slower than ECC (5–50× for key generation, 2–10× for signing/verification). Hardware acceleration will help but requires time.
• Protocol changes: TLS 1.3, X.509 certificates, SSH, and VPN protocols must be updated to accommodate larger keys and different algorithms.
• Backward compatibility: During the transition, systems must support both classical and post-quantum algorithms, doubling the configuration complexity.
• HSMs and hardware: Hardware Security Modules that perform RSA/ECC operations must be replaced or upgraded to support PQC algorithms.

30.7 Hybrid Cryptography: The Pragmatic Bridge

Hybrid cryptography combines classical and post-quantum algorithms so that security holds as long as either scheme remains unbroken. This is the recommended approach during the transition.

Hybrid Key Exchange (TLS 1.3 with PQC):

Client                                    Server
──────                                    ──────
│                                           │
│  ClientHello:                             │
│    - X25519 key share                     │
│    - Kyber-768 key share (encapsulation)  │
│  ═══════════════════════════════════════► │
│                                           │
│                              ServerHello: │
│                                - X25519 key share
│                                - Kyber-768 ciphertext
│  ◄═══════════════════════════════════════ │
│                                           │
│  Shared secret = KDF(                      │
│    X25519_shared_secret ||                │
│    Kyber_shared_secret                    │
│  )                                        │
│                                           │
│  Security: breaks only if BOTH X25519     │
│  AND Kyber-768 are broken                │
│                                           │

Formal security argument:

If $H$ is a cryptographic hash function modeled as a random oracle, and the key derivation function is $\text{KDF}(x, y) = H(x || y)$, then the hybrid shared secret is:

$$K = H(\text{X25519}(x, Y) || \text{Kyber}(x', Y'))$$

An adversary who can break X25519 but not Kyber cannot compute $K$ because they cannot compute $\text{Kyber}(x', Y')$. An adversary who can break Kyber but not X25519 cannot compute $\text{X25519}(x, Y)$. Only an adversary who breaks both can compute $K$.

This hybrid approach has been standardized by the IETF in RFC 9180 (HPKE) and is being deployed in Chrome, Firefox, and Cloudflare as of 2024.

Additional Qiskit Example: E91 Protocol Simulation

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

def simulate_e91(n_pairs=1000):
    """Simulate the E91 QKD protocol with CHSH inequality test."""
    sim = AerSimulator()

    # Measurement settings for CHSH test
    # Alice: a1 = 0°, a2 = 45°
    # Bob: b1 = 22.5°, b2 = 67.5°
    angles_a = [0, np.pi/4]
    angles_b = [np.pi/8, 3*np.pi/8]

    # Sifting bases for key generation
    # Alice and Bob both use Z-basis for key bits

    chsh_correlations = np.zeros((2, 2))
    chsh_counts = np.zeros((2, 2))

    key_bits_alice = []
    key_bits_bob = []

    for i in range(n_pairs):
        qc = QuantumCircuit(2, 2)

        # Create Bell state |Φ+⟩ = (|00⟩ + |11⟩)/√2
        qc.h(0)
        qc.cx(0, 1)

        # Decide: CHSH test or key generation?
        if i < 200:
            # CHSH test: measure at different angles
            setting_a = np.random.randint(2)
            setting_b = np.random.randint(2)

            # Apply rotation for Alice
            qc.ry(2 * angles_a[setting_a], 0)
            # Apply rotation for Bob
            qc.ry(2 * angles_b[setting_b], 1)

            qc.measure([0, 1], [0, 1])
            result = sim.run(qc, shots=1).result()
            bits = list(result.get_counts().keys())[0]
            a_outcome = int(bits[1])  # Alice's measurement
            b_outcome = int(bits[0])  # Bob's measurement

            # Correlation: +1 for same outcomes, -1 for different
            correlation = 1 if a_outcome == b_outcome else -1
            chsh_correlations[setting_a, setting_b] += correlation
            chsh_counts[setting_a, setting_b] += 1
        else:
            # Key generation: both measure in Z-basis
            qc.measure([0, 1], [0, 1])
            result = sim.run(qc, shots=1).result()
            bits = list(result.get_counts().keys())[0]
            key_bits_alice.append(int(bits[1]))
            key_bits_bob.append(int(bits[0]))

    # Compute CHSH parameter
    S = 0
    for i in range(2):
        for j in range(2):
            if chsh_counts[i, j] > 0:
                S += ((-1)**(i+j)) * chsh_correlations[i, j] / chsh_counts[i, j]
    S = abs(S)

    # Key error rate
    key_alice = np.array(key_bits_alice)
    key_bob = np.array(key_bits_bob)
    qber = np.mean(key_alice != key_bob)

    print(f"E91 Protocol Simulation ({n_pairs} pairs)")
    print(f"CHSH parameter S = {S:.3f} (classical limit: 2.0, quantum: 2√2 ≈ 2.83)")
    print(f"Key QBER = {qber:.3f}")
    print(f"Sifted key length: {len(key_alice)}")

    if S > 2:
        print("✓ CHSH inequality violated — entanglement verified, key is secure")
    else:
        print("✗ CHSH inequality not violated — possible eavesdropper, abort!")

    return S, qber

# Run E91 simulation
S, qber = simulate_e91(1000)

30.8 Code-Based Cryptography: Classic McEliece

The McEliece cryptosystem (1978) encodes a message by adding errors to a codeword from a Goppa code. Decryption requires knowledge of the code structure to correct the errors.

Encryption: $c = mG + e$, where $G$ is the public generator matrix (scrambled to hide the code structure) and $e$ is a random error vector of weight $t$.

Decryption: The secret key reveals the code structure, allowing efficient decoding to recover $m$ from $c$.

Detailed description of McEliece parameters:

The security of Classic McEliece depends on three parameters: - $n$: the code length (typically 6960) - $k$: the code dimension (typically 5413) - $t$: the error-correcting capability (typically 119)

The public key is the $k \times n$ generator matrix $G$, which requires $kn/8 \approx 1$ MB of storage. The secret key includes the Goppa polynomial and permutation matrix.

Classic McEliece has withstood cryptanalysis for over 40 years. Its main drawback is the large public key (~1 MB for 128-bit security), which makes it unsuitable for embedded devices but acceptable for long-term key distribution.

Worked Example 30.2: McEliece Key Sizes

For Classic McEliece with $(n, k, t) = (6960, 5413, 119)$: - Public key size: $kn/8 = 5413 \times 6960 / 8 = 4,710,225$ bytes $\approx 4.5$ MB (before systematic form reduction; after reduction, ~1 MB) - Ciphertext size: $n/8 = 6960/8 = 870$ bytes - Secret key size: ~140 KB (Goppa polynomial + permutation)

For comparison: - RSA-2048: public key = 256 B, ciphertext = 256 B - Kyber-768: public key = 1,184 B, ciphertext = 1,088 B - McEliece: public key = 1,044,992 B (~1 MB), ciphertext = 226 B

The trade-off is clear: McEliece has enormous keys but very small ciphertexts and fast operations.

30.9 Isogeny-Based Cryptography: A Cautionary Tale

SIKE (Supersingular Isogeny Key Encapsulation) was a promising PQC candidate based on finding isogenies between supersingular elliptic curves. It had the smallest keys of any PQC scheme (330 bytes for SIKEp434), making it attractive for bandwidth-constrained applications.

In July 2022, SIKE was broken by Wouter Castryck and Thomas Decru using a polynomial-time attack based on Kani's theorem from algebraic geometry. The attack recovers the secret key in hours on a laptop. A subsequent implementation by Giacomo Pope ran in just 4 minutes on a single core.

Why SIKE's break is instructive:

1. Small keys were the attraction: SIKE's 330-byte keys were comparable to ECC-P256 (64 bytes), far smaller than Kyber's 1,184 bytes. The temptation to optimize for key size led to a less conservative construction.

2. The attack was mathematical, not computational: The break used deep results from algebraic geometry (Kani's theorem on products of elliptic curves), not brute force. This illustrates that cryptanalysis can come from unexpected directions.

3. The break was total: Not a "slight weakening" but a complete polynomial-time break. The security claim of ~AES-256 turned out to be ~$2^{60}$ operations.

4. Redundancy pays off: NIST had already selected Kyber as the primary KEM before SIKE was broken. The multi-algorithm strategy (Kyber + Dilithium + SPHINCS+ + FALCON) provides resilience against similar breaks.

Common Misconception: "The SIKE break means all PQC is insecure."

The SIKE break was specific to the isogeny-based approach. Lattice-based cryptography (Kyber, Dilithium), hash-based signatures (SPHINCS+), and code-based cryptography (McEliece) were unaffected. The break illustrates why NIST selected algorithms based on diverse mathematical foundations — if one falls, others stand. Noise is the enemy in cryptography too, and mathematical assumptions are a form of noise that can turn out to be wrong.

30.10 Performance and Deployment Considerations

30.10.1 PQC Algorithm Comparison

30.10.2 Hybrid Deployment

The recommended approach during the transition is to deploy hybrid schemes that combine classical and post-quantum algorithms:

# Hybrid key exchange: X25519 + Kyber-768
import hashlib

def hybrid_key_exchange(x25519_shared, kyber_shared):
    """
    Combine X25519 and Kyber-768 shared secrets using HKDF.
    Security holds if EITHER X25519 OR Kyber-768 remains unbroken.
    """
    # Concatenate both shared secrets
    combined = x25519_shared + kyber_shared

    # Derive final key using HKDF-SHA384
    # The output key is secure as long as at least one input is secure
    from hashlib import sha384
    derived_key = sha384(combined).digest()

    return derived_key[:32]  # 256-bit key for AES-256

# Example usage
x25519_secret = b'\x01' * 32  # Placeholder: real X25519 shared secret
kyber_secret = b'\x02' * 32    # Placeholder: real Kyber-768 shared secret

final_key = hybrid_key_exchange(x25519_secret, kyber_secret)
print(f"Hybrid key: {final_key.hex()[:32]}...")
print(f"Key length: {len(final_key) * 8} bits")

TLS integration:

As of 2024, major browsers and servers support hybrid key exchange in TLS 1.3: - Chrome: X25519+Kyber-768 hybrid (enabled by default since Chrome 116) - Firefox: X25519+Kyber-768 (available via preference) - Cloudflare: X25519+Kyber-768 (deployed on all edge servers) - AWS: Supports hybrid KEM via AWS-LC

The hybrid key exchange adds ~1.2 KB to the TLS handshake (Kyber-768 public key + ciphertext), which increases the handshake latency by ~1 ms on typical connections — an acceptable overhead for the security improvement.

30.11 Ring-LWE and Module-LWE: The Mathematics Behind Kyber

30.11.1 From LWE to Ring-LWE

The LWE scheme in Section 30.3 has a critical practical limitation: the public key is an $n \times n$ matrix, requiring $O(n^2)$ storage. For $n = 256$ and $q = 3329$, the public key is $256^2 \times 4$ bytes $\approx 256$ KB — too large for many applications.

Ring-LWE (RLWE) reduces this to $O(n)$ by replacing the random matrix $A$ with a structured matrix derived from a polynomial ring. Instead of sampling $A$ uniformly at random, we define:

$$A = \text{circ}(a)$$

where $a$ is a random element of the polynomial ring $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ with $n = 256$ (a power of 2). The public key becomes $(a, b = a \cdot s + e)$, where multiplication is in $R_q$ — requiring only $O(n \log n)$ operations via the Number Theoretic Transform (NTT).

Detailed NTT explanation:

The Number Theoretic Transform is the finite-field analog of the FFT. For a polynomial $a(x) = a_0 + a_1 x + \ldots + a_{n-1} x^{n-1}$, the NTT computes:

$$\hat{a}_k = \sum_{j=0}^{n-1} a_j \omega^{jk} \pmod{q}$$

where $\omega$ is an $n$-th root of unity modulo $q$. For $q = 3329$ and $n = 256$, we need $\omega^{256} \equiv 1 \pmod{3329}$, which holds because 3329 is a prime of the form $256 \times k + 1$ (specifically, $3329 = 256 \times 13 + 1$).

The NTT reduces polynomial multiplication from $O(n^2)$ to $O(n \log n)$, making encryption and decryption practical. In Kyber, all operations are performed in the NTT domain, and the NTT is never explicitly inverted during encryption.

30.11.2 Module-LWE: The Kyber Construction

Kyber uses Module-LWE (MLWE), a generalization that interpolates between LWE and Ring-LWE. Instead of a single polynomial, MLWE uses a module of rank $k$ over the ring $R_q$. The public key is:

$$\mathbf{A} \in R_q^{k \times k}, \quad \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$$

where $\mathbf{s}, \mathbf{e} \in R_q^k$ are small polynomial vectors. For Kyber-768, $k = 3$, giving a public key of $3 \times 3 \times 256 \times 2 = 4,608$ bytes (before compression), which is compressed to 1,184 bytes.

Why Module-LWE instead of Ring-LWE?

Ring-LWE with a single polynomial ($k = 1$) has a potential vulnerability: the NTRU attack, which exploits the structure of the ring to reduce the lattice dimension. Module-LWE with $k \geq 2$ provides a security cushion: even if the Ring-LWE problem for a single polynomial is easier than expected, the Module-LWE problem with multiple polynomials remains hard. The security proof for MLWE is simpler and more conservative.

Kyber parameter sets:

30.11.3 CCA Security: The Fujisaki-Okamoto Transform

The basic Kyber construction is only secure against chosen-plaintext attacks (CPA). To achieve security against chosen-ciphertext attacks (CCA) — the standard security notion for KEMs — Kyber applies the Fujisaki-Okamoto (FO) transform:

1. Encapsulation: Generate a random coin $m \xleftarrow{\$} {0,1}^{256}$. Compute $K = H(m)$, $(c_1, c_2) = \text{Enc}_{pk}(m; r = G(m))$, and $c = (c_1, c_2)$.
2. Decapsulation: Compute $\hat{m} = \text{Dec}_{sk}(c)$. If $\text{Enc}_{pk}(\hat{m}; G(\hat{m})) \neq c$, return $\text{KDF}(z, c)$ (a pseudo-random key from the "failure" path). Otherwise, return $K = H(\hat{m})$.

The re-encryption check ensures that an adversary cannot submit a modified ciphertext and learn anything about the secret key, because any valid ciphertext must have been produced by the honest encryption algorithm.

Common Misconception: "Kyber is just LWE with smaller keys."

Kyber's Module-LWE construction provides different (and in some views, stronger) security guarantees than plain LWE. The module structure introduces additional mathematical constraints that make the problem harder, not easier, to solve. The NIST security level assignment (Level 3 for Kyber-768) is based on extensive cryptanalysis by the world's leading lattice cryptographers, not just on the parameter sizes.

30.12 Quantum-Safe TLS: The Deployment Reality

30.12.1 TLS 1.3 with Hybrid Key Exchange

The most critical deployment target for PQC is TLS (Transport Layer Security), which protects HTTP, email, and virtually all internet communication. The IETF has standardized hybrid key exchange for TLS 1.3 in RFC 9180 (HPKE) and the subsequent TLS working group drafts.

A hybrid TLS 1.3 handshake using X25519 + Kyber-768:

Client                                      Server
──────                                      ──────
│  ClientHello:                              │
│    key_share = X25519_public + Kyber-768_public
│  ═══════════════════════════════════════► │
│                                           │
│  ServerHello:                             │
│    key_share = X25519_public + Kyber-768_ciphertext
│  ◄═══════════════════════════════════════ │
│                                           │
│  Shared secret = KDF(                     │
│    X25519(X25519_private, X25519_public) ||
│    Kyber-768.Decaps(Kyber_secret, Kyber-768_ciphertext)
│  )                                        │
│                                           │
│  Derived keys = HKDF(shared_secret, info) │
│  ═══════════════════════════════════════►  │
│  ◄═══════════════════════════════════════   │
│  [Application data encrypted with derived keys]

The overhead of hybrid key exchange compared to classical TLS:

The hybrid handshake adds ~1.2 KB and ~0.2 ms — an acceptable overhead for the security improvement. Major browsers (Chrome, Firefox) and CDNs (Cloudflare) are deploying this in production as of 2024.

30.12.2 Certificate Chain Challenges

While the TLS key exchange can be hybrid, the certificate chain (X.509 certificates signed by certificate authorities) presents a different challenge:

1. Root certificates: Must be signed with a PQC algorithm (Dilithium or SPHINCS+)
2. Intermediate certificates: Must also be PQC-signed
3. End-entity certificates: Can be PQC-signed or hybrid

The challenge is that Dilithium-3 certificates are 3.3 KB (vs. 0.5 KB for ECDSA-P256), and SPHINCS+ certificates are 30 KB. A full certificate chain with SPHINCS+ at the root, Dilithium at the intermediate, and Dilithium at the leaf would be:

Root (SPHINCS+): 64 B public key + 29,792 B signature = ~30 KB Intermediate (Dilithium): 1,952 B public key + 3,293 B signature = ~5 KB Leaf (Dilithium): 1,952 B public key + 3,293 B signature = ~5 KB Total: ~40 KB (vs. ~2 KB for a classical certificate chain)

This 20× increase in certificate chain size has significant implications for TLS handshake latency, especially on mobile networks.

30.13 Quantum-Safe Blockchain

30.13.1 The Blockchain Vulnerability

Blockchain systems rely on digital signatures (ECDSA) for transaction authentication. A quantum computer that can break ECDSA can: 1. Forge signatures to steal funds from any address whose public key has been revealed 2. Create alternative block histories (double-spending) by forging signatures

The vulnerability is not hypothetical: Bitcoin addresses that have made a transaction have their public key revealed on the blockchain, making them vulnerable to a future quantum attack. As of 2024, approximately 4 million BTC ($\sim$ $200 billion) are in addresses with exposed public keys.

30.13.2 Migration Strategies for Blockchain

1. P2PKH (Pay-to-Public-Key-Hash): Bitcoin addresses that have never made a transaction reveal only the hash of the public key, not the public key itself. Breaking ECDSA requires first inverting the hash (SHA-256 + RIPEMD-160), which is not vulnerable to Shor's algorithm. However, once a transaction is made, the public key is revealed.

2. Post-quantum signature schemes: Replace ECDSA with Dilithium or SPHINCS+. The challenge is that SPHINCS+ signatures are 30 KB — far too large for a blockchain that stores every transaction permanently. Dilithium-3 signatures (3.3 KB) are more practical but still 13× larger than ECDSA.

3. Lamport signatures with Merkle trees: One-time or few-time signatures with small on-chain footprints. Requires state management (tracking which one-time keys have been used).

4. Quantum-resistant address formats: New address formats that reveal only the hash of the PQC public key, maintaining the same security model as current P2PKH addresses but with PQC algorithms.

Try It Yourself: Blockchain Migration Timeline

Estimate the cost of migrating Bitcoin to Dilithium-3 signatures. Assume: (a) 4 million active addresses, (b) each address needs a Dilithium-3 key pair, (c) Dilithium-3 public key is 1,952 bytes, (d) Dilithium-3 signature is 3,293 bytes, (e) average transaction makes 2 signature verifications. What is the total additional storage per year (assuming 300 million transactions)? How does this compare to the current Bitcoin blockchain size (~500 GB)?

30.14 Quantum-Resistant Symmetric Cryptography

While Shor's algorithm primarily threatens public-key cryptography, Grover's algorithm also has implications for symmetric-key cryptography. Grover's algorithm provides a quadratic speedup for brute-force key search: an $n$-bit key that would require $2^n$ classical operations requires only $2^{n/2}$ quantum operations.

Impact of Grover's algorithm on symmetric cryptography:

The mitigation is straightforward: double the key size. AES-256 provides 128-bit security against quantum attacks, which is considered sufficient for the foreseeable future. There is no need for "post-quantum AES" — the existing algorithm with a larger key is quantum-resistant.

However, a subtlety: Grover's algorithm requires $2^{n/2}$ sequential oracle queries, meaning it cannot be parallelized beyond $O(2^{n/3})$ with $2^{n/3}$ parallel processors. This makes the actual quantum attack cost significantly higher than $2^{n/2}$ in practice, because the quantum computer must maintain coherence for the duration of the search.

Worked Example 30.3: Quantum Security of AES-256

AES-256 has a 256-bit key. Classical brute force requires $2^{256}$ operations. With Grover's algorithm:

• Best case: $2^{128}$ sequential operations (no parallelization)
• With parallelization: $2^{85}$ sequential operations with $2^{43}$ parallel quantum processors
• With optimistic gate counts: ~$10^{18}$ operations per Grover iteration, total ~$10^{56}$ operations

For comparison, the total number of operations performed by all classical computers in history is ~$10^{22}$. Even with a billion quantum computers operating at 1 GHz, breaking AES-256 would take ~$10^{31}$ years — far longer than the age of the universe.

Conclusion: AES-256 and SHA-256/SHA-3 are quantum-resistant with their current key sizes. No migration is needed for symmetric cryptography.