Skip to content

Chapter 1: Foundations of Post-Quantum Cryptography

1.1 The Quantum Threat to Classical Cryptography

Modern digital security rests on a small set of mathematical problems that are computationally intractable for classical computers. Public-key cryptography — the backbone of secure internet communication — relies on:

  • Integer Factorization: Breaking RSA requires factoring large semiprimes (e.g., RSA-2048).

  • Discrete Logarithm Problem (DLP): Breaking Diffie-Hellman and DSA over finite fields.

  • Elliptic Curve Discrete Logarithm Problem (ECDLP): Breaking ECDH and ECDSA.

These problems are hard for classical computers, requiring sub-exponential to exponential time. Quantum computers change this landscape fundamentally.

Shor’s Algorithm — The Existential Threat

Peter Shor’s 1994 quantum algorithm solves integer factorization and discrete logarithm in polynomial time \(O((\log N)^3)\) on a quantum computer. This breaks RSA, Diffie-Hellman, DSA, ECDH, and ECDSA completely. A cryptographically relevant quantum computer (CRQC) running Shor’s algorithm would render all currently deployed public-key cryptography useless.

1.1.1 Grover’s Algorithm and Symmetric Cryptography

Grover’s 1996 algorithm provides a quadratic speedup for unstructured search problems, impacting symmetric cryptography:

Table 1.1. Impact of Quantum Algorithms on Cryptographic Primitives
Primitive Classical Security Quantum Security Action
RSA-2048 112 bits Broken (Shor) Replace
ECDH P-256 128 bits Broken (Shor) Replace
ECDSA P-384 192 bits Broken (Shor) Replace
DH-3072 128 bits Broken (Shor) Replace
AES-128 128 bits 64 bits (Grover) Upgrade to AES-256
AES-256 256 bits 128 bits (Grover) Retain
SHA-256 256 bits 128 bits (Grover) Retain (collision resistance halved)
SHA-384 384 bits 192 bits (Grover) Retain
SHA-3 256 bits 128 bits (Grover) Retain

What Grover Means for AES

Grover’s algorithm reduces the effective key length of AES-128 from 128 bits to 64 bits — insufficient for long-term security. AES-128 should be upgraded to AES-256 in quantum-resilient deployments. AES-256 retains 128-bit quantum security, which is acceptable per NIST guidelines.

1.1.2 The “Harvest Now, Decrypt Later” (HNDL) Threat

One of the most urgent concerns in PQC migration is HNDL (also called “Store Now, Decrypt Later”):

  1. An adversary intercepts and stores encrypted data today (e.g., VPN traffic, TLS sessions).

  2. When a CRQC becomes available (estimates: 5–20 years), the adversary decrypts the stored ciphertext.

  3. Data with long-term sensitivity (state secrets, health records, financial data, trade secrets) is compromised retroactively.

HNDL Timeline Urgency

Even if CRQCs arrive in 2035, data encrypted with RSA/ECDH today — in 2025 — can be stored and later decrypted. Any data requiring confidentiality beyond 10 years must be protected with PQC now. NIST, NSA (CNSA 2.0), and BSI all emphasize the urgency of the HNDL threat.

1.2 Mathematical Foundations

1.2.1 Lattice Theory

A lattice \(\mathcal{L}\) is a discrete additive subgroup of \(\mathbb{R}^n\). Given a basis matrix \(\mathbf{B} = [\mathbf{b}_1, \mathbf{b}_2, …, \mathbf{b}_n] \in \mathbb{R}^{n \times n}\), the lattice is:

\[\mathcal{L}(\mathbf{B}) = \left\{ \mathbf{B}\mathbf{x} \;\middle|\; \mathbf{x} \in \mathbb{Z}^n \right\} = \left\{ \sum_{i=1}^{n} x_i \mathbf{b}_i \;\middle|\; x_i \in \mathbb{Z} \right\}\]

Definition 1.1 (Shortest Vector Problem (SVP))

Given a lattice \(\mathcal{L}(\mathbf{B})\), find the shortest non-zero vector \(\mathbf{v} \in \mathcal{L}\) such that \(\|\mathbf{v}\|\) is minimized. SVP is NP-hard in general and conjectured to be hard even for quantum computers.

Definition 1.2 (Closest Vector Problem (CVP))

Given a lattice \(\mathcal{L}(\mathbf{B})\) and a target vector \(\mathbf{t} \in \mathbb{R}^n\), find the lattice point closest to \(\mathbf{t}\): \(\arg\min_{\mathbf{v} \in \mathcal{L}} \|\mathbf{v} - \mathbf{t}\|\). CVP is also NP-hard.

1.2.2 Learning With Errors (LWE)

LWE, introduced by Regev in 2005, is the computational foundation of most deployed PQC algorithms.

Definition 1.3 (Learning With Errors (LWE))

Let \(n, q\) be integers and \(\chi\) be an error distribution over \(\mathbb{Z}_q\). The LWE problem: given \(m\) samples \((\mathbf{a}_i, b_i) \in \mathbb{Z}_q^n \times \mathbb{Z}_q\) where \(b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \pmod{q}\) with \(\mathbf{s} \in \mathbb{Z}_q^n\) (secret) and \(e_i \leftarrow \chi\) (small error), find \(\mathbf{s}\).

The LWE problem is computationally equivalent (via quantum reduction) to worst-case lattice problems.

Example 1.1 (Small LWE Instance)

Let \(n=4\), \(q=17\), \(\mathbf{s} = (3, 1, 4, 1)\). Three LWE samples:

\[(5, 2, 11, 3) \cdot (3,1,4,1)^T + (-1) = 15+2+44+3-1 \equiv 12 \pmod{17}\]

The error term \(e = -1\) is small relative to \(q=17\).

1.2.3 Ring-LWE and Module-LWE

Ring-LWE (RLWE) works over the polynomial ring \(R_q = \mathbb{Z}_q[X]/(X^n+1)\) where \(n\) is a power of 2. This allows efficient operations using the Number Theoretic Transform (NTT).

Module-LWE (MLWE) generalizes RLWE to module lattices over \(R_q^k\) for dimension \(k\). ML-KEM and ML-DSA use MLWE. Parameters:

Table 1.2. LWE Variants Comparison
Variant Ring Key Operations Performance Examples
LWE \(\mathbb{Z}_q^n\) Matrix-vector Slow Regev, FrodoKEM
RLWE \(R_q = \mathbb{Z}_q[X]/(X^n+1)\) Polynomial Fast (NTT) NTRU, early Kyber
MLWE \(R_q^k\) Module-poly Very Fast ML-KEM, ML-DSA

1.2.4 Number Theoretic Transform (NTT)

The NTT is the discrete Fourier transform over \(\mathbb{Z}_q\), enabling fast polynomial multiplication in \(O(n \log n)\) rather than \(O(n^2)\).

Definition 1.4 (NTT)

For \(q\) prime with \(q \equiv 1 \pmod{2n}\), let \(\omega\) be a primitive \(2n\)-th root of unity in \(\mathbb{Z}_q\). The NTT of \(\mathbf{a} = (a_0, …, a_{n-1})\) is:

\[\hat{a}_k = \sum_{j=0}^{n-1} a_j \omega^{jk} \pmod{q}, \quad k = 0, 1, …, n-1\]

Polynomial multiplication then reduces to pointwise multiplication in the NTT domain: \(\hat{c}_k = \hat{a}_k \cdot \hat{b}_k\), followed by inverse NTT.

For ML-KEM with \(n=256\), \(q=3329\), \(\omega = 17\) (primitive 512th root of unity mod 3329). The NTT reduces polynomial multiplication from \(\sim\)65,536 multiplications to \(\sim\)3,328 multiplications plus the NTT overhead.

1.2.5 Short Integer Solution (SIS)

The SIS problem underlies many signature schemes:

Definition 1.5 (SIS Problem)

Given a matrix \(\mathbf{A} \in \mathbb{Z}_q^{n \times m}\), find a short non-zero vector \(\mathbf{z} \in \mathbb{Z}^m\) such that \(\mathbf{A}\mathbf{z} = \mathbf{0} \pmod{q}\) and \(\|\mathbf{z}\| \leq \beta\).

SIS is as hard as worst-case lattice problems (via average-case to worst-case reduction).

1.2.6 Code-Based Mathematical Foundations

Linear error-correcting codes provide an alternative hard problem family:

Definition 1.6 (Syndrome Decoding Problem (SDP))

Given a parity-check matrix \(\mathbf{H} \in \mathbb{F}_2^{(n-k) \times n}\), a syndrome \(\mathbf{s} \in \mathbb{F}_2^{n-k}\), and a weight bound \(w\), find \(\mathbf{e} \in \mathbb{F}_2^n\) with Hamming weight \(\text{wt}(\mathbf{e}) \leq w\) such that \(\mathbf{H}\mathbf{e}^T = \mathbf{s}\). SDP is NP-complete.

1.2.7 Hash-Based Security

Hash-based schemes rely solely on the security of the underlying hash function (e.g., SHA-256, SHAKE-256), making them quantum-resistant via Grover’s algorithm analysis: an \(n\)-bit preimage search takes \(O(2^{n/2})\) quantum operations (acceptable for \(n=256\)).

1.3 Security Levels

NIST defines five security levels for PQC algorithms:

Table 1.3. NIST PQC Security Levels
Level Classical Classical Equivalent Quantum Equivalent
1 AES-128 exhaustive key search 128-bit (classical) 64-bit (Grover)
2 SHA-256/SHA3-256 collision 128-bit collision 85-bit quantum collision
3 AES-192 exhaustive key search 192-bit 96-bit
4 SHA-384/SHA3-384 collision 192-bit collision 128-bit quantum collision
5 AES-256 exhaustive key search 256-bit 128-bit

Security Level Selection

Security Level 1 (ML-KEM-512) is adequate for most applications. Classified/government data often requires Level 3 or 5. The NSA CNSA 2.0 mandates Level 5 (ML-KEM-1024, ML-DSA-87) for classified national security systems.

1.4 Cryptographic Primitives: KEM and DSS

1.4.1 Key Encapsulation Mechanism (KEM)

A KEM is a three-algorithm system:

Algorithm: KEM Abstract Syntax

  1. \((\mathit{ek}, \mathit{dk}) \leftarrow \textsc{KeyGen}()\) // Encapsulation key (public) + Decapsulation key (private)

  2. \((\mathit{K}, \mathit{c}) \leftarrow \textsc{Encaps}(\mathit{ek})\) // Shared secret \(K\) + Ciphertext \(c\)

  3. \(\mathit{K}' \leftarrow \textsc{Decaps}(\mathit{dk}, \mathit{c})\) // Recover shared secret; \(K' = K\) if valid

KEMs replace public-key encryption in key establishment. The shared secret \(K\) is used to derive symmetric keys via a KDF (e.g., HKDF).

1.4.2 Digital Signature Scheme (DSS)

Algorithm: Digital Signature Scheme Abstract Syntax

  1. \((\mathit{pk}, \mathit{sk}) \leftarrow \textsc{KeyGen}()\) // Verification key (public) + Signing key (private)

  2. \(\sigma \leftarrow \textsc{Sign}(\mathit{sk}, M)\) // Signature \(\sigma\) over message \(M\)

  3. \(b \leftarrow \textsc{Verify}(\mathit{pk}, M, \sigma)\) // Accept (\(b=1\)) or Reject (\(b=0\))

1.5 NIST PQC Standardization History

Table 1.4. NIST PQC Standardization Timeline
Date Event
December 2016 NIST calls for proposals; 82 submissions received
January 2019 26 Round 2 candidates announced
July 2020 7 Round 3 finalists + 8 alternates selected
July 2022 4 algorithms selected for standardization (CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, SPHINCS+)
August 2023 Draft FIPS 203/204/205 released for comment
August 2024 FIPS 203, FIPS 204, FIPS 205 finalized
September 2023 Additional signatures Round 2 (14 candidates) announced
March 2025 HQC selected as 5th PQC standard (code-based KEM)
2025–2026 Draft FIPS 206 (FN-DSA, from FALCON) expected
2026+ Additional signature standard(s) expected from Round 2 process

1.6 Algorithm Families Overview

Post-quantum cryptography encompasses five principal algorithm families:

Post-quantum cryptography algorithm families and their deployed standards.
Figure 1.1. Post-quantum cryptography algorithm families and their deployed standards.
Table 1.5. PQC Algorithm Families: Strengths and Weaknesses
Family Strengths Weaknesses Key Sizes Status
Lattice-Based Fast, small keys, KEM+Sign Newer analysis Small Standardized
Code-Based 50-year security history, KEM Large public keys Large Standardized (HQC)
Hash-Based Conservative, stateless Large signatures Small pk, Large sig Standardized
Multivariate Fast signing, small sig Large public keys Large Research
Isogeny-Based Small keys SIDH/SIKE broken; slow Very small Research only

1.7 Summary

  • Shor’s algorithm breaks RSA, DH, ECDH, and ECDSA in polynomial quantum time — replacing these is mandatory.

  • Grover’s algorithm halves the effective key length of symmetric ciphers — upgrade AES-128 to AES-256.

  • The HNDL threat is immediate: encrypted data collected today can be decrypted when CRQCs arrive.

  • PQC security rests on hard mathematical problems: SVP/CVP (lattices), SDP (codes), MQ (multivariate), and hash function properties.

  • NIST finalized FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA) in August 2024; HQC selected as the 5th algorithm in March 2025.

  • Security levels 1–5 correspond to AES-128 through AES-256 equivalent quantum security.