nist-pqc-standards.ipynb

Kernel: SageMath 10.0

Connect: NIST Post-Quantum Cryptography Standards

Module 08 | Real-World Connections

The lattice problems you studied in this module are now the foundation of national cryptographic standards.

Introduction

In August 2024, NIST published three post-quantum cryptography standards:

• FIPS 203 (ML-KEM): Module-Lattice-Based Key Encapsulation Mechanism, based on the Kyber submission. This is the primary standard for post-quantum key exchange.

• FIPS 204 (ML-DSA): Module-Lattice-Based Digital Signature Algorithm, based on the Dilithium submission. This is the primary standard for post-quantum digital signatures.

• FIPS 205 (SLH-DSA): Stateless Hash-Based Digital Signature Algorithm, based on SPHINCS+. This is a hash-based backup that does not rely on lattice problems.

Both ML-KEM and ML-DSA are built on the Module-LWE problem over the polynomial ring $R_q = \mathbb{Z}_q[x]/(x^{256} + 1)$ --- exactly the structures you explored in notebooks 08d and 08e.

This notebook traces how the abstract lattice concepts from Module 08 become the concrete algorithms standardized for worldwide use.

ML-KEM (Kyber): Ring-LWE for Key Encapsulation

ML-KEM uses Module-LWE over $R_q = \mathbb{Z}_{3329}[x]/(x^{256}+1)$. The module rank $k$ determines the security level:

Parameter Set	Module Rank $k$	Effective Dimension	Security Level
ML-KEM-512	2	512	AES-128
ML-KEM-768	3	768	AES-192
ML-KEM-1024	4	1024	AES-256

The core operations are:

1. Key generation: Sample small polynomials $\mathbf{s}, \mathbf{e} \in R_q^k$. The public key is $(A, \mathbf{t} = A\mathbf{s} + \mathbf{e})$ where $A$ is a $k \times k$ matrix of random polynomials in $R_q$.

2. Encapsulation: To send a shared secret, sample fresh small polynomials $\mathbf{r}, \mathbf{e}_1, e_2$, compute the ciphertext as a new Ring-LWE sample that encodes a random message.

3. Decapsulation: Use the secret key $\mathbf{s}$ to strip away the Ring-LWE structure and recover the encoded message.

Let us implement a simplified version with tiny parameters to see the mechanics.

# === Toy ML-KEM: simplified Kyber key exchange ===
# Real Kyber uses n=256, q=3329, k=2/3/4.
# We use n=8, q=17, k=2 for pedagogy.

n = 8       # polynomial degree (real: 256)
q = 17      # modulus (real: 3329)
k = 2       # module rank (like Kyber-512)

Zq = Zmod(q)
Px.<x> = PolynomialRing(Zq)
Rq.<xbar> = Px.quotient(x^n + 1)

def small_poly(bound=1):
    """Sample a polynomial with small coefficients in {-bound, ..., bound}."""
    return Rq([ZZ.random_element(-bound, bound + 1) for _ in range(n)])

def uniform_poly():
    """Sample a uniformly random polynomial in R_q."""
    return Rq([ZZ.random_element(0, q) for _ in range(n)])

def poly_coeffs(p):
    """Extract coefficient list from a quotient ring element."""
    lifted = p.lift()
    return [lifted[i] for i in range(n)]

print(f'Toy ML-KEM parameters:')
print(f'  Ring: R_q = Z_{q}[x] / (x^{n} + 1)')
print(f'  Module rank: k = {k}')
print(f'  Public matrix A is {k}x{k} over R_q')
print(f'  Real Kyber uses n=256, q=3329')

# === Key Generation ===
set_random_seed(42)

# Public matrix A (k x k random polynomials)
A_mat = matrix(Rq, k, k, lambda i, j: uniform_poly())

# Secret key: vector of k small polynomials
s_vec = vector(Rq, [small_poly() for _ in range(k)])

# Error: vector of k small polynomials
e_vec = vector(Rq, [small_poly() for _ in range(k)])

# Public key: t = A * s + e
t_vec = A_mat * s_vec + e_vec

print('=== KEY GENERATION ===')
print(f'\nPublic matrix A ({k}x{k} ring elements):')
for i in range(k):
    for j in range(k):
        print(f'  A[{i},{j}] = {A_mat[i,j]}')

print(f'\nSecret key s (vector of {k} small polynomials):')
for i in range(k):
    print(f'  s[{i}] = {s_vec[i]}')

print(f'\nPublic key t = A*s + e:')
for i in range(k):
    print(f'  t[{i}] = {t_vec[i]}')

# === Encapsulation: Alice encodes a shared secret ===

# In real Kyber, the message is a random 256-bit string.
# Here we encode a simple binary polynomial.
msg_bits = [1, 0, 1, 1, 0, 1, 0, 1]
msg_poly = Rq([b * (q // 2) for b in msg_bits])  # scale: 0 -> 0, 1 -> q/2

# Sample fresh randomness
r_vec = vector(Rq, [small_poly() for _ in range(k)])  # random vector
e1_vec = vector(Rq, [small_poly() for _ in range(k)]) # error 1
e2 = small_poly()                                       # error 2 (scalar poly)

# Ciphertext:
#   u = A^T * r + e1    (vector of k polynomials)
#   v = t^T * r + e2 + msg_poly   (single polynomial)
u_vec = A_mat.transpose() * r_vec + e1_vec
v_poly = sum(t_vec[i] * r_vec[i] for i in range(k)) + e2 + msg_poly

print('=== ENCAPSULATION ===')
print(f'Message bits: {msg_bits}')
print(f'\nCiphertext u (vector of {k} polynomials):')
for i in range(k):
    print(f'  u[{i}] = {u_vec[i]}')
print(f'\nCiphertext v (single polynomial):')
print(f'  v = {v_poly}')

# === Decapsulation: Bob recovers the shared secret ===

# Compute: v - s^T * u
# This should be close to msg_poly (the errors approximately cancel)
noisy_msg = v_poly - sum(s_vec[i] * u_vec[i] for i in range(k))

# Decode: each coefficient is either ~0 (bit 0) or ~q/2 (bit 1)
def decode_bit(coeff, q):
    """Decode a coefficient to a bit: closer to 0 -> 0, closer to q/2 -> 1."""
    c = ZZ(coeff) % q
    dist_to_0 = min(c, q - c)
    dist_to_half = abs(c - q // 2)
    return 0 if dist_to_0 < dist_to_half else 1

noisy_coeffs = poly_coeffs(noisy_msg)
recovered_bits = [decode_bit(c, q) for c in noisy_coeffs]

print('=== DECAPSULATION ===')
print(f'\nNoisy message polynomial: {noisy_msg}')
print(f'Noisy coefficients: {noisy_coeffs}')
print(f'Expected (for bit=1): q/2 = {q // 2}')
print(f'\nDecoded bits:  {recovered_bits}')
print(f'Original bits: {msg_bits}')
print(f'Match: {recovered_bits == msg_bits}')
print(f'\nThe errors from s, e, r, e1, e2 are all small enough that')
print(f'they do not flip any bits during decoding.')

Why Does Decapsulation Work?

Let us trace the algebra. Write $\mathbf{t} = A\mathbf{s} + \mathbf{e}$. Then:

$$v - \mathbf{s}^T \mathbf{u} = (\mathbf{t}^T \mathbf{r} + e_2 + m) - \mathbf{s}^T(A^T \mathbf{r} + \mathbf{e}_1)$$$$= (A\mathbf{s} + \mathbf{e})^T \mathbf{r} + e_2 + m - \mathbf{s}^T A^T \mathbf{r} - \mathbf{s}^T \mathbf{e}_1$$$$= \mathbf{s}^T A^T \mathbf{r} + \mathbf{e}^T \mathbf{r} + e_2 + m - \mathbf{s}^T A^T \mathbf{r} - \mathbf{s}^T \mathbf{e}_1$$$$= m + \underbrace{\mathbf{e}^T \mathbf{r} + e_2 - \mathbf{s}^T \mathbf{e}_1}_{\text{small noise}}$$

The $\mathbf{s}^T A^T \mathbf{r}$ terms cancel perfectly. What remains is the message $m$ plus a small noise term. Since all of $\mathbf{s}, \mathbf{e}, \mathbf{r}, \mathbf{e}_1, e_2$ have small coefficients, their products remain small enough that rounding recovers the correct message bits.

ML-DSA (Dilithium): Lattice Signatures

ML-DSA uses a similar lattice structure but for digital signatures rather than key exchange. The core idea is the Fiat-Shamir-with-aborts paradigm:

1. Key generation: Same Module-LWE structure. Public key is $(A, \mathbf{t} = A\mathbf{s}_1 + \mathbf{s}_2)$ where $\mathbf{s}_1, \mathbf{s}_2$ are short secret vectors.

2. Signing: To sign a message $\mu$:

   • Sample a random masking vector $\mathbf{y}$ with bounded coefficients

   • Compute $\mathbf{w} = A\mathbf{y}$ and derive a challenge $c$ from $(\mathbf{w}, \mu)$

   • Compute $\mathbf{z} = \mathbf{y} + c \cdot \mathbf{s}_1$

   • If $\mathbf{z}$ has any coefficients too large, abort and retry (this prevents leaking $\mathbf{s}_1$)

3. Verification: Check that $A\mathbf{z} - c\mathbf{t}$ has the right structure. This works because: $A\mathbf{z} - c\mathbf{t} = A(\mathbf{y} + c\mathbf{s}_1) - c(A\mathbf{s}_1 + \mathbf{s}_2) = A\mathbf{y} - c\mathbf{s}_2$

The key difference from Kyber: signatures must be short vectors that satisfy a lattice relation, while key exchange encodes messages as noisy lattice points.

# === Toy ML-DSA: simplified Dilithium signature ===
# We demonstrate the sign/verify flow with tiny parameters.

import hashlib

# Reuse the ring from above: R_q = Z_17[x]/(x^8 + 1), k=2
set_random_seed(99)

# Key generation
A_sig = matrix(Rq, k, k, lambda i, j: uniform_poly())
s1 = vector(Rq, [small_poly() for _ in range(k)])
s2 = vector(Rq, [small_poly() for _ in range(k)])
t_sig = A_sig * s1 + s2

print('=== ML-DSA KEY GENERATION ===')
print(f'Public key: A ({k}x{k}), t = A*s1 + s2')
print(f'Secret key: s1, s2 (short polynomial vectors)')
for i in range(k):
    print(f'  s1[{i}] = {s1[i]}')
    print(f'  s2[{i}] = {s2[i]}')

# === Signing ===

message = "Post-quantum cryptography is here!"
gamma = 4  # bound for masking vector coefficients
beta = 3   # rejection threshold (simplified)

max_attempts = 100
for attempt in range(max_attempts):
    # Step 1: Sample masking vector y with coefficients in [-gamma, gamma]
    y = vector(Rq, [Rq([ZZ.random_element(-gamma, gamma+1) for _ in range(n)])
                     for _ in range(k)])
    
    # Step 2: Compute w = A*y
    w = A_sig * y
    
    # Step 3: Challenge c (in real Dilithium, this is a hash; we simplify)
    # Use a simple deterministic small polynomial derived from w and message
    h = hashlib.sha256((str(w) + message).encode()).digest()
    c_coeffs = [(b % 3) - 1 for b in h[:n]]  # coefficients in {-1, 0, 1}
    c_poly = Rq(c_coeffs)
    
    # Step 4: Compute z = y + c * s1
    z = y + vector(Rq, [c_poly * s1[i] for i in range(k)])
    
    # Step 5: Rejection sampling, check if z is "too large"
    # (coefficients must stay bounded to avoid leaking s1)
    z_coeffs_max = max(abs(ZZ(c) if ZZ(c) <= q//2 else ZZ(c) - q)
                       for zi in z for c in poly_coeffs(zi))
    if z_coeffs_max <= gamma - beta:
        print(f'Signing succeeded on attempt {attempt + 1}')
        break
else:
    print(f'Signing failed after {max_attempts} attempts (toy parameters too tight)')

print(f'\nSignature: (z, c)')
print(f'  Challenge c = {c_poly}')
for i in range(k):
    print(f'  z[{i}] = {z[i]}')

# === Verification ===

# Verifier computes: A*z - c*t = A*(y + c*s1) - c*(A*s1 + s2)
#                               = A*y + c*A*s1 - c*A*s1 - c*s2
#                               = A*y - c*s2 = w - c*s2
# Then re-derives the challenge from this value and the message.

w_prime = A_sig * z - vector(Rq, [c_poly * t_sig[i] for i in range(k)])

# Re-derive challenge
h_check = hashlib.sha256((str(w_prime) + message).encode()).digest()
c_check_coeffs = [(b % 3) - 1 for b in h_check[:n]]
c_check = Rq(c_check_coeffs)

print('=== VERIFICATION ===')
print(f'Recomputed w\' = A*z - c*t')
print(f'Original w - c*s2 for comparison:')
w_expected = w - vector(Rq, [c_poly * s2[i] for i in range(k)])
print(f'  Match: {w_prime == w_expected}')
print(f'\nChallenge check:')
print(f'  Original c  = {c_poly}')
print(f'  Recomputed  = {c_check}')
print(f'  Match: {c_poly == c_check}')
print(f'\nSignature valid: {c_poly == c_check}')

Security Levels and Parameter Sizes

Here are the real-world parameters from the NIST standards:

ML-KEM (FIPS 203)

Parameter	ML-KEM-512	ML-KEM-768	ML-KEM-1024
$n$ (ring degree)	256	256	256
$k$ (module rank)	2	3	4
$q$ (modulus)	3329	3329	3329
$\eta_1$ (secret noise)	3	2	2
$\eta_2$ (cipher noise)	2	2	2
Public key size	800 bytes	1184 bytes	1568 bytes
Ciphertext size	768 bytes	1088 bytes	1568 bytes
Shared secret	32 bytes	32 bytes	32 bytes

ML-DSA (FIPS 204)

Parameter	ML-DSA-44	ML-DSA-65	ML-DSA-87
$(k, l)$	(4, 4)	(6, 5)	(8, 7)
$q$	8380417	8380417	8380417
Public key	1312 bytes	1952 bytes	2592 bytes
Signature	2420 bytes	3309 bytes	4627 bytes

Key sizes are larger than RSA or ECC, but still practical for most applications. The real cost is in bandwidth, not computation.

# === Key size comparison across schemes ===

schemes = [
    ('RSA-2048', 256, 256, 'classical'),
    ('ECDSA P-256', 32, 64, 'classical'),
    ('X25519 (ECDH)', 32, 32, 'classical'),
    ('ML-KEM-512', 800, 768, 'post-quantum'),
    ('ML-KEM-768', 1184, 1088, 'post-quantum'),
    ('ML-KEM-1024', 1568, 1568, 'post-quantum'),
    ('ML-DSA-44', 1312, 2420, 'post-quantum'),
    ('ML-DSA-65', 1952, 3309, 'post-quantum'),
]

print('Scheme PK (bytes) CT/Sig (bytes) Type')for name, pk, ct, typ in schemes:
    print(f'{name} {pk:>12,} {ct:>15,} {typ}')

print(f'\nPost-quantum keys are 10-50x larger than classical, but still')
print(f'under 2 KB for public keys and under 5 KB for signatures.')
print(f'This is very manageable for TLS, SSH, and certificate chains.')

Concept Map: Module 08 to NIST Standards

Module 08 Concept	NIST Standard Application
Lattices and bases (08a)	The algebraic structure underlying all ML-KEM/ML-DSA computations
SVP/CVP hardness (08b)	Security assumption: no efficient algorithm finds short vectors in the lattice dimension used
LLL algorithm (08c)	Motivates choosing parameters large enough that LLL (and BKZ) cannot break the scheme
LWE problem (08d)	The core hardness assumption: $\mathbf{b} = A\mathbf{s} + \mathbf{e}$ is indistinguishable from random
Ring-LWE (08e)	Efficient key sizes via polynomial rings; the ring $R_q = \mathbb{Z}_q[x]/(x^{256}+1)$
Module-LWE (08e)	Kyber uses a $k \times k$ matrix of ring elements --- the middle ground between LWE and Ring-LWE
NTT (08e)	Fast polynomial multiplication that makes Kyber competitive with classical schemes in speed

Summary

Concept	Key idea
ML-KEM (Kyber)	Key encapsulation using Module-LWE over $\mathbb{Z}_{3329}[x]/(x^{256}+1)$. The noise from LWE is what makes key exchange secure, and the ring structure is what makes it efficient.
ML-DSA (Dilithium)	Digital signatures using the same lattice structure with a Fiat-Shamir-with-aborts paradigm. Signing produces a short vector satisfying a lattice relation.
Security levels	128, 192, and 256 bit security map to module ranks $k = 2, 3, 4$, giving effective lattice dimensions of 512, 768, and 1024
Practical key sizes	Larger than classical crypto but still under 2 KB for public keys and under 5 KB for signatures
SLH-DSA (SPHINCS+)	A hash-based backup signature scheme that does not rely on lattice problems, providing algorithmic diversity

---

Back to Module 08: Lattices and Post-Quantum Cryptography