The Building Blocks of Post-Quantum Security
The cryptographic foundations of the Internet are shifting. Quantum computers, once they reach sufficient scale, will be able to break the public-key systems that guard today's TLS connections. The transition to post-quantum (PQ) cryptography is therefore not optional — it's inevitable. Lattice-based cryptography is the leading candidate to replace elliptic curves, and understanding its mechanics is essential for anyone involved in the engineering effort required to make the switch.
Lattices aren't a minor tweak to existing algorithms. They represent a fundamentally different way of structuring public-key operations, and while they offer many of the same capabilities, they come with a significant trade-off: much larger key sizes and communication overhead. For instance, establishing a key with ML-KEM-768 requires 2,272 bytes of data exchange, versus just 64 bytes using X25519 elliptic-curve key exchange. That difference creates practical challenges — from TCP packet fragmentation to redesigning TLS's public key infrastructure.
A Primer on Lattice-Based Key Exchange
To understand how lattice cryptography works, it helps to start with familiar ground: Diffie-Hellman (DH) key exchange. In DH, Alice and Bob each pick a random secret number, compute a public key share, and exchange those shares. From their own secret and the other's public share, they derive a common secret that an eavesdropper cannot easily compute.
ML-KEM — the NIST-standardized Kyber algorithm — replaces the mathematical operations of DH with matrix arithmetic over structured lattices. It's not a drop-in replacement, but the conceptual flow is similar. The security rests on the hardness of certain lattice problems, which even quantum computers cannot efficiently solve.
Encryption Today, Decryption Tomorrow
The most urgent motivation for PQ encryption is the "harvest now, decrypt later" threat model. An adversary can record encrypted traffic flowing across the Internet today and store it, waiting for a quantum computer capable of breaking the key exchange that protected that data. While the actual bulk encryption in TLS is already largely resistant to quantum attacks, the key-establishment process typically relies on elliptic-curve cryptography, which is vulnerable. Switching key exchange to lattice-based schemes closes that gap.
The rest of the source material — including detailed code examples and deeper mathematical exposition — will appear in later sections of this article.
Matrix arithmetic, the modular way
A matrix is a two-dimensional array of numbers. In NumPy, we can define one as follows:
A = np.matrix([[1, 2, 3],
[4, 5, 6],
[7, 8, 9]])This sets A to a 3-by-3 matrix where A[0,0]==1, A[0,1]==2, A[0,2]==3, A[1,0]==4, and so forth. All matrix entries in this context are integers. Whenever we add, subtract, or multiply integers, we then reduce the result, as with hours on a clock, so that it lands in range(Q) for some positive modulus Q. For ML-KEM, that modulus is Q=3329. In Python, we write modular multiplication as c = a*b % Q, which computes the product and takes the remainder. For instance, 42*1337 % Q is 2890 rather than 56154. Modular addition and subtraction work the same way. Where context makes it clear, we may omit the "% Q".
Three matrix operations matter here. The first is matrix transpose, written A.T in NumPy, which flips a matrix along its diagonal so that A.T[j,i] == A[i,j]:
print(A.T)
# [[1 4 7]
# [2 5 8]
# [3 6 9]]Picture writing a matrix on translucent paper, drawing a diagonal line from top-left to bottom-right, and rotating the paper 180° around that line:
The second operation is matrix multiplication, usually of a matrix by a column vector (a matrix with one column). For example:
s = np.matrix([[0],
[1],
[0]])This same vector can be written more compactly as np.matrix([[0,1,0]]).T. Multiplying a square matrix A by a column vector s means taking the dot product of each row of A with s. If t = A*s % Q, then for each row i:
t[i] == (A[i,0]*s[0,0] + A[i,1]*s[1,0] + A[i,2]*s[2,0]) % Q
The result is always a column vector whose length equals the number of rows in the left-hand matrix:
print(A*s % Q)
# [[2]
# [5]
# [8]]If we transpose our column vector s into a 1-by-3 matrix and multiply it by a 3-by-1 matrix r, the product is a 1-by-1 matrix:
r = np.matrix([[1,2,3]]).T
print(s.T*r % Q)
# [[2]]The third operation is matrix addition: if A and B are both N-by-M matrices, then C = (A+B) % Q is the N-by-M matrix where C[i,j] == (A[i,j]+B[i,j]) % Q. This requires the dimensions to match exactly.
A first, insecure key exchange
We can start by replacing the scalar operations in a classic Diffie-Hellman exchange with matrix operations. The resulting protocol is not secure, but it is the foundation for a secure scheme we'll develop next:
- Alice and Bob agree on a public,
N-by-NmatrixA(the analogue of g). - Alice picks a random length-
Nvectorsand sendst = A*s % Qto Bob. - Bob picks a random length-
Nvectorrand sendsu = r.T*A % Qto Alice (equivalently,(A.T*r).T % Q).
After the exchange, Alice computes the shared secret as u*s % Q, and Bob computes it as r.T*t % Q. These match because u*s == (r.T*A)*s == r.T*(A*s) == r.T*t.
ML-KEM builds on this kind of exchange but uses it as a public key encryption scheme rather than a direct key agreement. Such a scheme has three algorithms:
key_gen(): outputs a public encryption keypkand a secret decryption keysk.encrypt(): takes the public key and a plaintext, and outputs a ciphertext.decrypt(): takes the secret key and a ciphertext, and recovers the plaintext. For allptxt, we needdecrypt(sk, encrypt(pk, ptxt)) == ptxt.
The scheme is considered secure if, given a ciphertext and its public key, no attacker can learn anything about the plaintext without the secret key. Once we have this public key encryption, we convert it into a key-encapsulation mechanism (the "KEM" in "ML-KEM"), in which the plaintext is always a randomly generated key.
Here is the encryption scheme in detail:
key_gen(): choose a random square matrixAand a random column vectors. The public key is(A, t=A*s % Q), and the secret key iss.encrypt(): the plaintextptxtis an integer inrange(Q). Bob generates a key shareu, derives the shared secret, and adds it to the plaintext. The ciphertext is:
u = r.T*A % Q
v = (r.T*t + m) % Q
Here m is a 1-by-1 matrix containing the plaintext (i.e., m = np.matrix([[ptxt]])), and r is a random column vector.
decrypt(): Alice computes the shared secret and subtracts it:
m = (v - u*s) % Q
Readers may notice the similarity to El Gamal encryption. For good reason: this scheme is a direct matrix analogue, and good cryptographers borrow from other good cryptographers.
Before we can implement it, we need a way to generate random matrices and column vectors. We'll call it gen_mat(). Our scheme has two parameters: the modulus Q and the matrix/vector dimension N. The choice of N drives security, and for now you can pick any value.
def key_gen():
# Here `gen_mat()` returns an N-by-N matrix with entries
# randomly chosen from `range(0, Q)`.
A = gen_mat(N, N, 0, Q)
# Like above except the matrix is N-by-1.
s = gen_mat(N, 1, 0, Q)
t = A*s % Q
return ((A, t), s)
def encrypt(pk, ptxt):
(A, t) = pk
m = np.matrix([[ptxt]])
r = gen_mat(N, 1, 0, Q)
u = r.T*A % Q
v = (r.T*t + m) % Q
return (u, v)
def decrypt(sk, ctxt):
s = sk
(u, v) = ctxt
m = (v - u*s) % Q
return m[0,0]
# Test
assert decrypt(sk, encrypt(pk, 1)) == 1Turning a draft into a cryptosystem
The warm-up scheme is insecure in a straightforward way: given the public (A,t), an attacker can recover s with linear algebra. If A is invertible, then A-1*t == A-1*(A*s) == s, where A-1 denotes the inverse matrix. Gaussian elimination computes this directly. Even for non-invertible A, solving for s is simply solving a linear system.
To block this, we add noise. The key generation becomes:
def key_gen():
A = gen_mat(N, N, 0, Q)
s = gen_mat(N, 1, 0, Q)
e = gen_mat(N, 1, 0, Q)
t = (A*s + e) % Q
return ((A, t), s)The public vector t now includes an additive error vector e, generated at random. The previous attack no longer succeeds: A-1*t == s + A-1*e, which requires knowing e to recover s.
But this fix introduces a new problem. Plug the revised key generation into the scheme, and decrypt() now returns garbage. Algebra shows why:
(v - u*s) == (r.T*t + m) - (r.T*A)*s
== r.T*(A*s + e) + m - (r.T*A)*s
== r.T*e + m
Since r and e are random, r.T*e is uniformly random, so decryption is equivalent to encrypting with a one-time pad and then throwing that pad away.
ML-KEM handles this in stages. First, it helps if r.T*e is small, so that decryption yields a value close to the plaintext. But "close" is not enough; occasional decryption failures are not acceptable in practice. The trick is to encode the plaintext cleverly. Suppose we want to encrypt a single bit: ptxt is either 0 or 1. We split the number line of range(Q) into four roughly equal chunks:
The region around zero (modulo Q) represents ptxt=0; the far region represents ptxt=1. We encode the bit as m = np.matrix([[ptxt * Q//2]]) — the double slash denotes integer division. Decoding picks the bit corresponding to the range containing m[0,0]. If the decryption error is small, we will almost certainly decode correctly.
Finally, we ensure the error r.T*e is small by sampling short vectors for r and e. Short here means entries drawn from range(-beta, beta+1) for some small positive integer beta. The trade-off is immediate: beta must be small enough that decryption nearly always succeeds, but large enough that r and e cannot be guessed. The tunable parameters are:
- the modulus
Q - the vector dimension
N - the shortness parameter
beta
Experimentation will show that some parameter sets yield reliable decryption with secret vectors that seem hard to guess; others fail in one direction or the other.
There is another hole to patch. An attacker who recovers the random vector r can decrypt directly, since v == r.T*t + m and both t and v are public. And r can be recovered from u by Gaussian elimination, since u is linear in r. The fix mirrors the first one: add a short error vector to u, and another to v. Because decryption multiplies u by s, the added noise must be small, but now its magnitude also depends on the secret key s, which is why s has to be short as well.
The updated scheme has three parameters ( Q, N, beta) and encrypts a single bit:
def key_gen():
A = gen_mat(N, N, 0, Q)
s = gen_mat(N, 1, -beta, beta+1)
e1 = gen_mat(N, 1, -beta, beta+1)
t = (A*s + e1) % Q
return ((A, t), s)
def encrypt(pk, ptxt):
(A, t) = pk
m = np.matrix([[ptxt*(Q//2) % Q]])
r = gen_mat(N, 1, -beta, beta+1)
e2 = gen_mat(N, 1, -beta, beta+1)
e3 = gen_mat(1, 1, -beta, beta+1)
u = (r.T*A + e2) % Q
v = (r.T*t + e3 + m) % Q
return (u, v)
def decrypt(sk, ctxt):
s = sk
(u, v) = ctxt
m = (v - u*s) % Q
if m[0,0] in range(Q//4, 3*Q//4):
return 1
return 0
# Test
assert decrypt(sk, encrypt(pk, 0)) == 0
assert decrypt(sk, encrypt(pk, 1)) == 1Finding parameters where decryption is reliable and the secret vectors are hard to guess is part of the design process.
The Learning With Errors problem
The two attacks described above share a common form: the attacker has a public vector p and wishes to recover a secret vector x, where p is a linear function of x. In the key-recovery case, t == A*s. In the plaintext-recovery case, u == r.T*A. In both cases, the fix adds noise, blocking direct linear algebra. But can we prove that the noisy version leaks nothing?
This is where the Learning With Errors (LWE) problem comes in. LWE asks an attacker to distinguish between two distributions:
(A, t=A*s + e), whereAis fromgen_mat(N,N,0,Q)and bothsandeare short vectors fromgen_mat(N,1,-beta,beta+1).(A, t), whereAis random fromgen_mat(N,N,0,Q)andtis random fromgen_mat(N,1,0,Q).
The first distribution is what the encryption scheme actually produces; the second has no secret vector at all. The LWE problem is hard if no attacker can tell which distribution a sample came from with probability significantly better than a coin flip. If LWE is hard for chosen parameters, our encryption scheme is passively secure: ciphertexts and public keys look indistinguishable from random, so ciphertexts cannot leak plaintext information. The error term added to v (call it e3) is necessary for this argument to go through.
Where lattices enter
A lattice is an infinite grid of points in high-dimensional space — the two-dimensional case might look like lattice work in a garden:
The lattice we care about is defined by a matrix P that "recognizes" membership: the lattice consists of all vectors v for which P*v == 0, the all-zero vector being np.zeros((N,1), dtype=int). Lattice problems can also be described in terms of a basis of generating vectors, but we will not use that formulation here.
The connection to LWE is geometric. Given an LWE instance (A, t=A*s + e), consider the matrix P formed by concatenating A with an identity matrix I. For N=3 and beta=2:
A = gen_mat(N, N, 0, Q)
P = np.concatenate((A, np.identity(N, dtype=int)), axis=1)
print(P)
# [[1570 634 161 1 0 0]
# [1522 1215 861 0 1 0]
# [ 344 2651 1889 0 0 1]]Multiplying P by the concatenation of s and e yields t:
s = gen_mat(N, 1, -beta, beta+1)
e = gen_mat(N, 1, -beta, beta+1)
t = (A*s + e) % Q
z = np.concatenate((s, e))
print(z)
# [[-2]
# [ 0]
# [-2]
# [ 0]
# [-1]
# [ 2]]
assert np.array_equal(t, P*z % Q)Let z be that concatenated vector. The set of points v satisfying P*v == t is "close to" the lattice because z is short — its entries are bounded by beta. For a random (A,t), the set of such points is typically "far away," in the sense that no short z exists. Distinguishing close from far gets harder as the dimension grows, and as z becomes longer the LWE instance looks more random:
But making z too long trades one problem for another. The Short Integer Solution (SIS) problem asks for short vectors z1 and z2 such that (A*z1 + z2) % Q is zero — equivalently, a short vector z in the lattice recognized by P:
z = np.concatenate((z1, z2))
assert np.array_equal((A*z1 + z2) % Q, P*z % Q)A (quantum) computer that solves SIS would also solve LWE: for an LWE instance, z1.T*t is small, while for a random instance it is uniformly random. So our encryption scheme is only as secure as SIS is hard. Finding short vectors in a lattice is harder than finding long ones, which means SIS gets easier as beta approaches Q. Simultaneously, LWE gets easier as beta approaches zero. System designers must aim for a middle ground where neither problem is tractable.
Choosing concrete parameters
The question of parameter selection is really a question about the most efficient known attacks. The lattice cryptography community maintains a tool called lattice-estimator that estimates the complexity of state-of-the-art quantum and classical algorithms for lattice problems. Running it with ML-KEM's parameters produces output like the following (the tool requires Sage):
sage: from estimator import *
sage: res = LWE.estimate.rough(schemes.Kyber768)
usvp :: rop: ≈2^182.2, red: ≈2^182.2, δ: 1.002902, β: 624, d: 1427, tag: usvp
dual_hybrid :: rop: ≈2^174.3, red: ≈2^174.3, guess: ≈2^162.5, β: 597, p: 4, ζ: 10, t: 60, β': 597, N: ≈2^122.7, m: 768The "rop" figure estimates the computation cost of an attack. For a candidate parameter set such as N=600, Q=3329, and beta=4, lattice-estimator finds an attack — codenamed "arora-gb" — that applies to our scheme but not to ML-KEM and carries much lower complexity than the "usvp" and "dual_hybrid" attacks:
sage: res = LWE.estimate.rough(LWE.Parameters(n=600, q=3329, Xs=ND.Uniform(-4,4), Xe=ND.Uniform(-4,4)))
usvp :: rop: ≈2^180.2, red: ≈2^180.2, δ: 1.002926, β: 617, d: 1246, tag: usvp
dual_hybrid :: rop: ≈2^226.2, red: ≈2^225.4, guess: ≈2^224.9, β: 599, p: 3, ζ: 10, t: 0, β': 599, N: ≈2^174.8, m: 600
arora-gb :: rop: ≈2^129.4, dreg: 9, mem: ≈2^129.4, t: 4, m: ≈2^64.7Bumping parameters further would bring our scheme into a regime with comparable security, though that is only part of the story. Establishing security also requires a solid proof in a realistic adversarial model; without one, we cannot exclude other avenues of attack.
Making LWE practical: polynomial rings
The scheme as described encrypts only one bit per ciphertext. The root cause is the need to split range(Q) into two broad regions. We could split it into more chunks to encrypt more bits per message, but that raises the chance of decryption errors.
Efficiency is also a concern: every encryption and decryption step requires O(N2) multiplications, and security forces N quite high. ML-KEM sidesteps both issues by working over a polynomial ring. Matrix entries become polynomials instead of integers. Addition, subtraction, and multiplication must then be defined for polynomials, but the overall encryption logic stays the same.
The only unfamiliar operation is polynomial modular reduction: after multiplying two polynomials in the usual grade-school manner, we divide by a special polynomial — ML-KEM uses X256+1 — and take the remainder. The output is a polynomial with 256 coefficients, each in range(Q).
This buys us two things. First, plaintext capacity: each coefficient of the plaintext polynomial encodes one bit, yielding 256 bits (32 bytes) per ciphertext. Second, security with a far smaller matrix: the most widely used variant, ML-KEM-768, works with a 3-by-3 matrix A (just nine polynomials; note that 256 * 3 = 768). The choice of X256+1 is deliberate, as it lacks algebraic structure known to enable attacks.
The combination of coefficient modulus Q=3329 and polynomial modulus X256+1 has an additional benefit: polynomial multiplication can be slotted into the NTT algorithm, which drastically reduces the number of multiplications and additions. This is part of why ML-KEM can outperform elliptic-curve Diffie-Hellman in CPU time on some platforms. NTT operates by repeatedly applying the Chinese Remainder Theorem, much like optimized RSA implementations do.
From encryption to a KEM
One last step takes us from public key encryption to ML-KEM proper: hardening the scheme against chosen ciphertext attacks (CCA). The current scheme is only secure against chosen plaintext attacks: ciphertexts leak no information about plaintexts, but the attacker gains no ability to query decryptions of its own crafted ciphertexts. CCA security grants exactly that (except for the target ciphertext itself), which matters in real-world protocols. Consider a server authenticating to a client by decrypting a client-chosen ciphertext; such a server effectively offers a decryption oracle. If the scheme is not CCA-secure, repeated queries can leak key material and eventually enable impersonation.
ML-KEM uses a specific transform that turns the CPA-secure public key encryption into a CCA-secure KEM. Additional optimizations keep the wire format small. Rather than transmitting a random matrix A in full, the protocol derives it from a 32-byte seed via an eXtendable Output Function (XOF) — SHAKE128 for ML-KEM. Ciphertext size is reduced by compressing the polynomial coefficients, rounding off their least significant bits.
For the most common parameters, ML-KEM-768, the public key is 1184 bytes and the ciphertext is 1088 bytes. Shrinking either size would require reducing the encapsulated key or the public matrix — the first would narrow its applicability, the second cuts into the security margin. Smaller lattice-based schemes exist, but they rest on different hardness assumptions and remain subject to ongoing analysis.
Authentication and the Road to ML-DSA
Encryption is only half of the secure-connection story. A TLS handshake also needs to authenticate the server (and sometimes the client) so you know who you're talking to. That job falls to digital signatures: a secret key signs a message, and a public key verifies the signature. Today's signature schemes share the same Achilles' heel as today's encryption — a quantum computer could recover a server's secret key from its public key and impersonate it at will.
The threat to signatures is less immediate than to encryption, but the fix is messier. Over the years, many signatures have been bolted onto the TLS handshake to satisfy the web PKI's evolving requirements. While we have post-quantum signature candidates — one of which we examine below — they are currently too large (in bytes) to be comfortable drop-in replacements. Unless NIST's ongoing standardization effort produces a breakthrough, we'll need to re-engineer TLS and the web PKI to lean on fewer signatures.
The first PQ signature likely to see deployment is ML-DSA (also known as Dilithium). Its design follows the same template as ML-KEM: build an intermediate primitive, then transform it into the final scheme. ML-DSA is considerably more involved that ML-KEM, so let's focus on the core ideas.
Schnorr's Protocol, on Lattices
Where ML-KEM is lattice-based El Gamal encryption, ML-DSA is essentially the Schnorr identification protocol with elliptic curves swapped for lattices. Schnorr's protocol lets a prover convince a verifier that it knows the secret key matching a public key — without revealing that key. It's a three-move protocol with four algorithms:
initialize(): prover sends a commitment to the verifier.challenge(): verifier sends back a challenge.finish(): prover responds with a proof.verify(): verifier checks the proof to decide if the prover really knows the secret key.
Turning this into a signature scheme means making it non-interactive: the prover derives the challenge itself by hashing the commitment together with the message. The signature is the commitment plus proof; the verifier recomputes the challenge from those and runs verify().
Now let's build Schnorr's protocol from lattices. The public key is an LWE instance (A,t=A*s1 + s2), just like in ML-KEM — but this time the secret is the pair of short vectors (s1,s2), error term included:
def key_gen():
A = gen_mat(N, N, 0, Q)
s1 = gen_mat(N, 1, -beta, beta+1)
s2 = gen_mat(N, 1, -beta, beta+1)
t = (A*s1 + s2) % Q
return ((A, t), (s1, s2))To initialize, the prover generates another LWE instance (A,w=A*y1 + y2) and sends the hash of w, keeping (y1,y2) secret. The hash keeps the protocol from revealing w directly:
def initialize(A):
y1 = gen_mat(N, 1, -beta, beta+1)
y2 = gen_mat(N, 1, -beta, beta+1)
w = (A*y1 + y2) % Q
return (H(w), (y1, y2))Here H is a cryptographic hash function like SHA-3. The verifier's challenge is an integer (chosen carefully, not just at random) within a given range:
def challenge():
return random.randrange(0, Q)In the signature version, that challenge comes from hashing the commitment and message, and the hash's output range must match the challenge set. The proof is the pair (z1,z2) satisfying A*z1 + z2 == c*t + w — which is easy if you hold the secret key:
z1 = (c*s1 + y1) % Q
z2 = (c*s2 + y2) % Q
Verification doesn't check that equation directly. Since the commitment is H(w), the equation needs rearrangement so verification can proceed without knowing w:
def finish(s1, s2, y1, y2, c):
z1 = (c*s1 + y1) % Q
z2 = (c*s2 + y2) % Q
return (z1, z2)
def verify(A, t, hw, c, z1, z2):
return H((A*z1 + z2 - c*t) % Q) == hw
# Test
((A, t), (s1, s2)) = key_gen()
(hw, (y1, y2)) = initialize(A) # hw: prover -> verifier
c = challenge() # c: verifier -> prover
(z1, z2) = finish(s1, s2, y1, y2, c) # (z1, z2): prover -> verifier
assert verify(A, t, hw, c, z1, z2) # verifierPlugging the Leaks
Security hinges on whether an attacker can impersonate the prover without the secret key. Extracting the key from public data is out if LWE is hard, and the commitment doesn't leak helpful info. The proof, however, has a problem: (y1,y2) mask the secret vectors, but the secret is also scaled by the challenge c. If c spans a wide range, so do the entries of c*s1 and c*s2, and short (y1,y2) entries can't fully mask them. Observe z1 over a few runs (N=3, Q=3329, beta=4):
((A, t), (s1, s2)) = key_gen()
print('s1={}'.format(s1.T % Q))
for _ in range(10):
(w, (y1, y2)) = initialize(A)
c = challenge()
(z1, z2) = finish(s1, s2, y1, y2, c)
print('c={}, z1={}'.format(c, z1.T))
# s1=[[ 1 0 3326]]
# c=1123, z1=[[1121 3327 3287]]
# c=1064, z1=[[1060 4 137]]
# c=1885, z1=[[1884 3327 999]]
# c=269, z1=[[ 270 3325 2524]]
# c=1506, z1=[[1510 3325 2141]]
# c=3147, z1=[[3149 4 547]]
# c=703, z1=[[ 700 4 1219]]
# c=1518, z1=[[1518 3327 2104]]
# c=1726, z1=[[1726 0 1478]]
# c=2591, z1=[[2589 4 2217]]With enough samples, statistical analysis recovers s1 — because Q is prime, c*pow(c,-1,Q)==1 for any nonzero c. The same trick works on s2 or via t. The core flaw: mask vectors (y1,y2) must be short enough that recovering w from (A,w) is hard, but long enough to hide a challenge-scaled secret. Making them span range(Q) would make the LWE instance easy to break via SIS.
The needed balance involves the challenge space — the set of possible challenge outputs. The space must be large enough that collisions are improbable. Why? Consider a known valid signature for message m with challenge c == H(H(w),m). If an attacker finds a different message m* with H(H(w),m*) == c, the signature is valid for both. A small challenge space makes such collisions trivial.
You can't just enlarge the challenge space by raising modulus Q; larger challenges leak more information about the secret. But the hardness of LWE is about the ratio of beta to Q, not absolute sizes. So pick a bigger modulus (say Q=2**31 - 1) and keep the challenge space at range(2**16):
def initialize(A):
y1 = gen_mat(N, 1, -gamma, gamma+1)
y2 = gen_mat(N, 1, -gamma, gamma+1)
w = (A*y1 + y2) % Q
return (H(w), (y1, y2))
((A, t), (s1, s2)) = key_gen()
print('s1={}'.format(s1.T % Q))
for _ in range(10):
(w, (y1, y2)) = initialize(A)
c = challenge()
(z1, z2) = finish(s1, s2, y1, y2, c)
print('c={}, z1={}'.format(c, z1.T))
# s1=[[3 0 1]]
# c=31476, z1=[[175933 141954 93186]]
# c=27360, z1=[[ 136404 2147438807 283758]]
# c=33536, z1=[[2147430945 2147377022 190671]]
# c=23283, z1=[[186516 73400 4955]]
# c=24756, z1=[[ 328377 2147438906 2147388768]]
# c=12428, z1=[[2147340715 188675 90282]]
# c=24266, z1=[[ 175498 2147261581 2147301553]]
# c=45331, z1=[[357595 185269 177155]]
# c=45641, z1=[[ 21592 2147249191 2147446200]]
# c=57893, z1=[[297750 113335 144894]]Now z1 entries live in range(-gamma, gamma+1) with gamma = beta*(2**16-1) — relatively short — and are uniformly masked by drawing (y1,y2) from the same range. Correlations with the secret vanish. But 2**16 challenges still means collisions after only a handful of runs. We need ~2**256 challenges, which would demand an enormous modulus to stay secure — except ML-DSA works over polynomial rings. With the same modulus polynomial as ML-KEM, the challenge is a 256-coefficient polynomial whose coefficients are chosen so the challenge space is large but multiplication by the challenge scales the secret only slightly. That keeps Q at a modest 8380417, just over twelve bits above ML-KEM's modulus.
Yet information leakage isn't fully ruled out. If the prover often picks a small entry for y1, repeated runs reveal s1's entries. The fix: force prover outputs to be long enough and verify their bounds.
Proving Security with Simulation
The elegant solution involves a proof technique called simulation. If we know z1 and z2 entries always fall in range(-beta_loose, beta_loose+1) for some beta_loose > beta, then an honest protocol run can be perfectly simulated without the secret key:
def simulate(A, t):
z1 = gen_mat(N, 1, -beta_loose, beta_loose+1)
z2 = gen_mat(N, 1, -beta_loose, beta_loose+1)
c = challenge()
w = (A*z1 + z2 - c*t) % Q
return (H(w), c, (z1, z2))
# Test
((A, t), (s1, s2)) = key_gen()
(hw, c, (z1, z2)) = simulate(A, t)
assert verify(A, t, hw, c, z1, z2)The output of simulate() is indistinguishable from a real transcript: w, c, z1, and z2 share the same mathematical relations (the verification equation holds) and the same distribution. Since the simulator doesn't touch the secret key, an eavesdropper learns nothing beyond what's computable from the public key.
To make this work, initialize() widens the sampling range for y1 and y2 by beta_loose, pushing proof vectors into a roughly uniform range but possibly causing them to fall just outside it:
def initialize(A):
y1 = gen_mat(N, 1, -gamma+beta_loose, gamma+beta_loose+1)
y2 = gen_mat(N, 1, -gamma+beta_loose, gamma+beta_loose+1)
w = (A*y1 + y2) % Q
return (H(w), (y1, y2))That's why finish() must abort when proof vectors are out of bounds, and verify() rejects them:
def finish(s1, s2, y1, y2, c):
z1 = (c*s1 + y1) % Q
z2 = (c*s2 + y2) % Q
if not in_range(z1, beta_loose) or not in_range(z2, beta_loose):
return (None, None)
return (z1, z2)
def verify(A, t, hw, c, z1, z2):
if not in_range(z1, beta_loose) or not in_range(z2, beta_loose):
return False
return H((A*z1 + z2 - c*t) % Q) == hwIf finish() returns (None,None), both sides abort and retry:
((A, t), (s1, s2)) = key_gen()
while True:
(hw, (y1, y2)) = initialize(A) # hw: prover -> verifier
c = challenge() # c: verifier -> prover
(z1, z2) = finish(s1, s2, y1, y2, c) # (z1, z2): prover -> verifier
if z1 is not None and z2 is not None:
break
assert verify(A, t, hw, c, z1, z2)Aborts are ordinary, not exceptional: ML-DSA's parameters are tuned so the protocol succeeds only once in five attempts on average. The security proof must also simulate aborted runs, and the simulator's abort probability must match the real one — meaning the rejection rate must be independent of the secret key. The simulator also needs to generate realistic commitments for aborted transcripts, which is exactly the reason the prover hashes w: hashes of random inputs are easy to simulate.
Making It Smaller and Faster
ML-DSA uses the same optimizations as ML-KEM: polynomial rings, NTT-based multiplication, and fixed-bit encoding. But it squeezes bytes further. Where the toy scheme carries two proof vectors, ML-DSA's proof is just one vector z = c*s1 + y, with a special commitment encoding that prevents recovering y. A related trick shrinks the public key's t vector.
Still, for the first planned parameters (ML-DSA-44), the public key is 1312 bytes and the signature hits 2420 bytes — far larger than current schemes. It's possible to do better, but only by complicating things: HAETAE tweaks the distributions to shave off bytes, and Falcon goes further with smaller signatures via a different, elegant but implementation-heavy approach.
A Look Beyond Signatures
Lattice cryptography is the foundation for the first PQ algorithms heading to wide deployment. ML-KEM already shields encryption from quantum computers, and ML-DSA should follow in the coming years to protect authentication. But lattices open a new frontier: computing on encrypted data itself.
LWE-based encryption enables, for example, clients to submit encrypted metrics that a server can aggregate without ever decrypting individual submissions. It also permits encoding a server-side database so clients can issue encrypted queries without the server learning which rows were requested. These are special cases of Fully Homomorphic Encryption (FHE) — arbitrary computations on encrypted data. FHE is uniquely a lattice construct today, though for most applications a special-purpose protocol remains far more practical. FHE has steadily improved, and for some uses it's already viable. Lattices, as it turns out, are not just the fix for the quantum threat — they're a new set of tools for handling data in ways that classic public-key cryptography never allowed.
