How Lattice Encryption Works, a Worked Example With Real Numbers

Almost every explanation of lattice encryption stops at the metaphor. You are told that a lattice is a grid of points, that finding the nearest one is hard, and that this hardness is what will protect your data from a future quantum computer. All of that is true, and none of it lets you see the thing actually work.

This page does the arithmetic instead. We pick numbers small enough to check with a pencil, build a key, encrypt a single bit, and decrypt it, showing every intermediate value. Then we push the noise until the bit flips, break the scheme twice on purpose, and finish by mapping each piece onto ML-KEM, the standard the world is now deploying.

Every number below was produced by Python that was executed rather than imagined, and the script is short enough to be printed in full further down. If you want the concepts behind it, the geometry and the hard problems and the standards landscape, our guide to lattice-based cryptography covers that ground. This one is the calculator.

Why doing the arithmetic beats reading a metaphor

Lattice encryption has a reputation for being unapproachable, and the reputation is undeserved. The mathematics that protects a real connection is genuinely deep, but the mechanism at the centre of it is a piece of arithmetic that a school pupil could follow. The difficulty is that almost nobody writes it down with actual numbers in it.

What follows is that missing article. We are going to run a complete public-key encryption scheme at a scale so small that you can check every line, and the scheme is not a simplification invented for teaching. It is Learning With Errors, the construction Oded Regev introduced in a 2005 paper on lattices, learning with errors and cryptography, and it is the direct ancestor of the standard now being rolled out across the internet.

The only thing we change is the size of the numbers. Where the real scheme uses a modulus of 3329 and works with 256 coefficients at a time, we use a modulus of 97 and four numbers, which shrinks the security to nothing and the arithmetic to something you can do on the back of an envelope. Everything structural stays exactly where it is.

Counting on a ring of 97

One convention has to be settled before any of the numbers make sense. All the arithmetic in this lattice encryption example happens modulo 97, which means that after every addition or multiplication we divide by 97 and keep only the remainder. The numbers therefore live on a circle of 97 positions rather than on an infinite line, and counting past 96 brings you back to 0.

This wrap-around is doing real work rather than tidying up. It is what makes a public key look like meaningless noise, because a value of 87 could have come from 87, or 184, or 281, and nothing in the published number says which. It is also why distance has to be measured the short way round, so the gap between 96 and 0 is 1 rather than 96.

Ninety-seven is prime, which matters more than it looks. A prime modulus means every non-zero number has a multiplicative inverse, so systems of linear equations behave the way they do over ordinary fractions, and that property is exactly what we exploit later when we break the scheme on purpose.

The parameters chosen for this walkthrough

The secret key is a list of four numbers, and we will use s = (1, 3, 0, 2). Real lattice encryption also keeps its secret small, because ML-KEM draws its secret from a centred binomial distribution that produces values clustered tightly around zero, so a short secret here is faithful to the real thing rather than a convenience.

The public part starts with a matrix A of six rows and four columns, filled with numbers chosen uniformly at random between 0 and 96. Nothing about A is secret, and in a real implementation it is not even transmitted, because it is regrown on demand from a short seed. Alongside it sits an error vector e with one small entry per row, each of them −1, 0 or +1.

Those three objects are all that lattice encryption needs. The reader should be warned honestly that at these sizes the scheme has no security whatsoever, since a secret of four small numbers can be guessed by exhaustion in microseconds. The parameters are chosen for legibility, and the sections on breaking the scheme will show precisely which knob turns legibility back into security.

Step one, building the public key by hand

The public key is the pair (A, b), where each entry of b is the dot product of one row of A with the secret, plus that row’s error, reduced modulo 97. Written as a formula it is b = A·s + e mod q, and written out longhand it is six lines of ordinary multiplication and addition. Here is every one of them, with s = (1, 3, 0, 2) substituted in.

row 1:  62*1 + 13*3 +  5*0 + 41*2 = 183    + 1 = 184    mod 97 = 87
row 2:   7*1 + 88*3 + 30*0 + 66*2 = 403    - 1 = 402    mod 97 = 14
row 3:  51*1 +  2*3 + 74*0 + 19*2 =  95    + 0 =  95    mod 97 = 95
row 4:  23*1 + 45*3 + 60*0 +  9*2 = 176    + 1 = 177    mod 97 = 80
row 5:  80*1 + 71*3 + 16*0 + 33*2 = 359    - 1 = 358    mod 97 = 67
row 6:  11*1 + 27*3 + 95*0 + 48*2 = 188    + 1 = 189    mod 97 = 92

public key  b = (87, 14, 95, 80, 67, 92)

Take the first line slowly, because the other five are the same operation. The first row of A is (62, 13, 5, 41), and multiplying it term by term against the secret gives 62, 39, 0 and 82, which sum to 183. The error for that row is +1, taking the total to 184, and 184 leaves a remainder of 87 when divided by 97, so the published value is 87.

That is the whole of key generation in lattice encryption. An observer sees the six rows of A and the six values of b, which is a system of six equations in four unknowns, and ordinarily that would be more than enough to solve. The errors are the only thing standing between that observer and the secret key, and they are never published.

Step two, encrypting a single bit

To encrypt, the sender picks a random handful of rows from the public key and adds them together. We will use rows 1, 3 and 6, a choice made at random and never revealed. Adding the corresponding rows of A column by column gives the first half of the ciphertext.

u[1] =  62 + 51 + 11 = 124    mod 97 = 27
u[2] =  13 +  2 + 27 =  42    mod 97 = 42
u[3] =   5 + 74 + 95 = 174    mod 97 = 77
u[4] =  41 + 19 + 48 = 108    mod 97 = 11

u = (27, 42, 77, 11)

The second half carries the message. Add up the matching entries of b, which gives 87 + 95 + 92 = 274, and then add an offset that depends entirely on the bit being sent. A zero adds nothing at all, while a one adds 48, the whole part of q/2, which is as far from zero as it is possible to get on a ring of 97.

sum of the chosen b values  =  87 + 95 + 92  =  274    mod 97 = 80

sending a 1:   v = 274 + 48 = 322    mod 97 = 31
sending a 0:   v = 274 +  0 = 274    mod 97 = 80

ciphertext for the bit 1:   u = (27, 42, 77, 11),   v = 31

That pair is the entire ciphertext, five numbers for one bit of message, and that ratio is why lattice encryption moves so much more data than the schemes it replaces. Every one of those five numbers may be read by anyone, and none of them betrays either the bit or the secret. The reason is that the sum of the three chosen rows is itself a fresh, unpredictable-looking equation carrying its own accumulated error.

Step three, getting the bit back

Only the holder of s can decrypt, and decryption in lattice encryption is a single dot product followed by a subtraction. Compute the dot product of u with the secret, subtract it from v, and reduce modulo 97. Here it is in full.

<u,s>  =  27*1 + 42*3 + 77*0 + 11*2
       =  27 + 126 + 0 + 22
       =  175                     mod 97 = 78

d  =  v - <u,s>  =  31 - 78  =  -47      mod 97 = 50

The answer is 50, and now the rounding decides. Measure how far 50 is from 0, taking the short way round the ring, which gives 47. Then measure how far it is from 48, which gives 2. Since 50 is far closer to 48 than to 0, the recovered bit is a one, which is exactly what was sent.

distance from d = 50 to  0  =  47
distance from d = 50 to 48  =   2

50 is nearer 48, so the recovered bit is 1

Run the same decryption on the zero ciphertext and the arithmetic is just as short. There v was 80, so d = 80 − 78 = 2, which sits 2 away from zero and 46 away from 48, and the recovered bit is a zero. Two ciphertexts built from the same rows differ only by that offset of 48, and the offset is the message.

Why the rounding recovers the right answer

The decryption did not land on 48. It landed on 50, and the gap is not an error in the arithmetic but the whole point of the design. Working through the algebra, the dot product of u with s cancels almost everything, and what is left behind is the offset plus the errors of exactly the rows that were used.

Rows 1, 3 and 6 carried errors of +1, 0 and +1, which sum to 2, and 48 plus 2 is 50. That is the identity the whole of lattice encryption rests on, and it holds every single time. The decrypted value is always the intended offset plus whatever noise was dragged along by the chosen rows.

d  =  48 * bit  +  (sum of the errors on the chosen rows)

our case:   d  =  48 * 1  +  (+1 + 0 + 1)  =  48 + 2  =  50

So decryption never recovers the offset cleanly, and it does not need to. It only needs the noise to be small enough that the answer stays nearer the offset it started from than the other one. That tolerance is a measurable quantity, and it is the subject of the next section.

The noise budget drawn to scale

Because lattice encryption decides by rounding, the ring of 97 splits into two regions. A value from 0 to 24, or from 73 up to 96, is nearer zero and decodes to a zero bit, while anything from 25 to 72 is nearer 48 and decodes to a one. The boundaries sit at q/4 and 3q/4, which are 24.25 and 72.75.

Now put a bit of one through that rule. Its decrypted value is 48 plus the error sum, so it decodes correctly as long as 48 plus the error sum stays between 25 and 72. That gives an explicit budget, and the budget is slightly lopsided because 48 is not exactly half of 97.

decodes to 0:   d in [0, 24]   and   d in [73, 96]
decodes to 1:   d in [25, 72]

a bit of 1 lands at d = 48 + E, so it survives while

        -23  <=  E  <=  +24

Every lattice encryption scheme carries a budget of this kind. With errors confined to −1, 0 and +1 there is no way to break ours. Even if all six rows were used and every error pointed the same way, the total would be 6, well inside the range. Widen the errors to a maximum of 4 each and six rows could reach 24, which just touches the edge, and beyond that failures become possible.

Step four, watching a decryption fail

Assertions about thresholds are easy to make and easy to doubt, so here is lattice encryption failing. We keep the same matrix A, the same secret key, and the same three rows for encryption, and change nothing except the size of the errors, which now range up to 9 either way. The public key rebuilds like this.

row 1:  62*1 + 13*3 +  5*0 + 41*2 = 183    - 9 = 174    mod 97 = 77
row 2:   7*1 + 88*3 + 30*0 + 66*2 = 403    - 1 = 402    mod 97 = 14
row 3:  51*1 +  2*3 + 74*0 + 19*2 =  95    - 8 =  87    mod 97 = 87
row 4:  23*1 + 45*3 + 60*0 +  9*2 = 176    + 2 = 178    mod 97 = 81
row 5:  80*1 + 71*3 + 16*0 + 33*2 = 359    - 3 = 356    mod 97 = 65
row 6:  11*1 + 27*3 + 95*0 + 48*2 = 188    - 9 = 179    mod 97 = 82

public key  b' = (77, 14, 87, 81, 65, 82)

Encryption is unchanged, so u is still (27, 42, 77, 11), because u depends only on A and the rows chosen. What changes is v, since the b values are different now. Adding the same three rows gives 77 + 87 + 82 = 246, and sending a one adds 48 as before.

v'  =  246 + 48  =  294      mod 97 = 3

d'  =  v' - <u,s>  =  3 - 78  =  -75      mod 97 = 22

check:  the errors on rows 1, 3 and 6 are -9, -8 and -9, summing to -26
        48 + (-26) = 22, which is exactly d'

distance from d' = 22 to  0  =  22
distance from d' = 22 to 48  =  26

22 is nearer 0, so the recovered bit is 0.  A 1 was sent.  FAILURE.

The error sum of −26 is outside the budget of −23, so the value slid past the boundary at 24.25 and landed in the region that decodes to zero. Nothing was corrupted in transit and no attacker was involved. The scheme simply accumulated more noise than its own decision rule could absorb, and it returned the wrong bit with no indication that anything had gone wrong.

How often failure actually happens

A single failure proves the threshold exists, but the useful question for lattice encryption is how likely it is. To answer that we ran 200,000 encryptions at each error width, generating a fresh key and a fresh random bit every time, and counted how often the recovered bit differed from the one sent. The results show the sharp knee that lattice designers work with.

error width      failures out of 200,000      rate
-----------      -----------------------      --------
  |e| <=  1                    0              0.0000 %
  |e| <=  2                    0              0.0000 %
  |e| <=  3                    0              0.0000 %
  |e| <=  4                    0              0.0000 %
  |e| <=  5                    2              0.0010 %
  |e| <=  6                   52              0.0260 %
  |e| <=  8                  950              0.4750 %
  |e| <= 10                 4620              2.3100 %
  |e| <= 12                10523              5.2615 %

Up to a width of 4 there was not one failure in 800,000 encryptions, because at that width the worst possible error sum is 24 and the budget stretches to 24. The moment the worst case can exceed the budget the rate stops being zero, and from there it climbs steeply rather than gently. Doubling the width from 6 to 12 multiplies the failure rate by more than two hundred.

This is why decryption failure is a designed quantity rather than an accident. Real lattice encryption picks its noise and its modulus so that the rate is small enough to ignore, and the figures are startling. FIPS 203 gives a decapsulation failure rate of 2 to the power of −164.8 for ML-KEM-768, a probability so tiny that the event will not occur in the lifetime of the technology.

The care is not merely about reliability. A scheme whose failures depend on the secret key leaks information every time one happens, so an attacker who can provoke failures and watch for them learns something each time. Driving the rate below any reachable threshold closes that channel as well as keeping the protocol working.

Breaking it by taking the noise away

The best way to see what the errors are doing is to remove them and watch the scheme die. Set every error to zero and rebuild the public key, which now satisfies b = A·s exactly, with no slack anywhere. Six clean equations in four unknowns over a prime modulus is a schoolbook problem.

with e = 0 the public key becomes  b0 = (86, 15, 95, 79, 68, 91)

Gaussian elimination on the first four rows, modulo 97:

    recovered s = (1, 3, 0, 2)
    true      s = (1, 3, 0, 2)          elapsed: 0.027 ms

Twenty-seven microseconds, and the secret key is on the table. There is no lattice problem left to solve, no search, and no hardness of any kind, because a system of linear equations over a field has been solvable since the nineteenth century. The identical routine run against the real noisy public key returns (82, 56, 42, 80), which is not the secret and is not close to it.

Trying to decrypt our original ciphertext with that wrong key gives 81, a value sitting 16 from zero and 33 from 48, which is to say nowhere useful at all. One unit of error per row was enough to turn a solved problem into an unsolved one. Everything else in lattice encryption exists to make sure that small amount of error cannot be removed.

Breaking it by making the modulus too large

Keeping some noise is necessary but not sufficient, because what matters is the noise measured against the modulus. If q is enormous and the errors stay tiny, the correct solution stands out so far from every wrong one that lattice reduction can find it. To demonstrate that we moved to a slightly larger instance, six unknowns and twelve equations with q = 1021, and ran the classical LLL reduction algorithm of Lenstra, Lenstra and Lovász on twenty random instances at each noise width.

error width     noise / q      secret recovered
-----------     ---------      ----------------
  |e| <=   0       0.0000           20 of 20
  |e| <=   1       0.0010           20 of 20
  |e| <=   2       0.0020           20 of 20
  |e| <=   4       0.0039           20 of 20
  |e| <=   8       0.0078           20 of 20
  |e| <=  16       0.0157           20 of 20
  |e| <=  32       0.0313           20 of 20
  |e| <=  64       0.0627            3 of 20
  |e| <= 128       0.1254            0 of 20
  |e| <= 255       0.2498            0 of 20

The transition is abrupt. While the errors stay below about three percent of the modulus, reduction recovers the exact secret every time, and once they reach roughly twelve percent it never does. Nothing about the code changed between those rows, only the ratio of noise to modulus.

That ratio is the single most important parameter in lattice encryption, and it explains a design tension that otherwise looks arbitrary. A larger modulus makes decryption failures rarer, because the budget of q/4 grows, and it also makes the underlying problem easier, because the noise shrinks in relative terms. Every parameter set is a chosen point between those two pressures.

It should be said plainly that this experiment shows a boundary, not a proof. Lattice encryption is believed to resist quantum attack because no efficient quantum algorithm for these problems is known, and an absence of known attack is not the same as a theorem that none exists.

Run the whole thing yourself

Every number above came out of Python that was executed rather than sketched, and the core of this lattice encryption demonstration of it is short enough to reproduce here in full. Paste this into a file and run it with any Python 3, with no libraries needed, and it will print the same public key, the same ciphertext and the same decrypted value that appear throughout this page.

q, s = 97, [1, 3, 0, 2]                  # modulus and secret key
A = [[62,13,5,41], [7,88,30,66], [51,2,74,19],
     [23,45,60,9], [80,71,16,33], [11,27,95,48]]
e = [1, -1, 0, 1, -1, 1]                 # one small error per row
dot = lambda x, y: sum(a*c for a, c in zip(x, y))

b = [(dot(A[i], s) + e[i]) % q for i in range(6)]
print("public key b =", b)

rows, bit = [0, 2, 5], 1                 # rows 1, 3 and 6, and the bit to send
u = [sum(A[i][j] for i in rows) % q for j in range(4)]
v = (sum(b[i] for i in rows) + bit * (q // 2)) % q
print("ciphertext   =", u, v)

d = (v - dot(u, s)) % q
print("d =", d, "-> bit", 0 if d <= q//4 or d >= q - q//4 else 1)

# public key b = [87, 14, 95, 80, 67, 92]
# ciphertext   = [27, 42, 77, 11] 31
# d = 50 -> bit 1

Two experiments are worth trying immediately. Change the error vector to six zeros and watch the scheme still work perfectly, which is the point about it being insecure rather than broken, and then widen the errors to values around 9 and keep re-running until a bit flips. The second is the fastest way to feel what a noise budget actually is.

What changes on the way to ML-KEM

The scheme just worked through is genuinely the same shape as the one protecting real traffic, but four things scale up between here and ML-KEM, the standard published as FIPS 203, the specification that turns lattice encryption into a deployed protocol. None of them alters the round trip you have just followed.

From single numbers to whole polynomials

The first change is that numbers become polynomials. Instead of a secret of four integers, ML-KEM uses polynomials of 256 coefficients, and instead of plain vectors it arranges them into small matrices, which is the Module variant of the problem. Ring and module structure of this kind was introduced for efficiency by Lyubashevsky, Peikert and Regev, and it shrinks keys dramatically because a whole polynomial can be regrown from a seed.

Why the modulus is 3329 and not something rounder

The second change is the Number Theoretic Transform. Multiplying two 256-coefficient polynomials directly costs 65,536 multiplications, and the transform reduces that to something proportional to 256 times its logarithm. The modulus 3329 is chosen precisely to make the transform available, since 3329 is 256 times 13 plus 1.

What compression costs in noise

The third change is compression. ML-KEM throws away low-order bits of the ciphertext before sending it, which is why the parameters include du and dv, set to 10 and 4 for ML-KEM-768. Discarding those bits adds a little more noise, so compression is paid for out of the same budget we measured earlier.

Surviving an attacker who chooses the ciphertexts

The fourth change is the largest conceptual jump. What we built is secure only against an attacker who watches, and the Fujisaki-Okamoto transform upgrades it to withstand one who submits chosen ciphertexts. It works by deriving the encryption randomness from the message, so the recipient can re-encrypt what they decrypted and check it matches. FIPS 203 states that the underlying encryption scheme is not secure in that stronger sense and “shall not be used as a stand-alone scheme”.

The parameters that make the real scheme secure are its size rather than its shape. Where we used four unknowns, ML-KEM-768 works with three polynomials of 256 coefficients, giving 768 unknowns, and NIST rates that set at security category 3. The construction was proposed as CRYSTALS-Kyber by Bos and colleagues in 2018, and it was standardised with modifications six years later.

Why ML-KEM never encrypts your message

One thing our lattice encryption example does slightly misrepresent, and it is worth correcting carefully because readers get it wrong constantly. We encrypted a chosen bit, which is what a public-key encryption scheme does, but ML-KEM is not a public-key encryption scheme. It is a key encapsulation mechanism, and the difference is not pedantry.

A KEM has three operations rather than two. Key generation produces a keypair as usual, but encapsulation takes only the public key and returns two things, a ciphertext and a fresh random shared secret, with no input message anywhere. Decapsulation takes the ciphertext and the private key and returns the same shared secret.

public-key encryption          key encapsulation (ML-KEM)
---------------------          --------------------------
KeyGen()      -> pk, sk        KeyGen()   -> ek, dk
Encrypt(pk,m) -> c             Encaps(ek) -> c, K
Decrypt(sk,c) -> m             Decaps(dk,c) -> K

you choose m                   nobody chooses K, it is random
                               K is 32 bytes, always

The shared secret is 32 bytes for every ML-KEM parameter set, and it is not your data. It is a key, and it goes on to feed a symmetric cipher such as AES-256, which does the actual encrypting of the actual traffic. So when a browser negotiates a post-quantum connection, ML-KEM runs once at the start of the handshake and then steps aside.

There are good reasons for the split. Symmetric ciphers are far faster than any public-key operation and are already considered quantum-resistant at adequate key lengths, so there is nothing to gain from pushing bulk data through a lattice. Restricting the public-key part to a random value it generates itself also removes a whole class of attacks that depend on an adversary choosing what gets encrypted.

This is also why lattice encryption key sizes matter more than they might seem to. ML-KEM-768 moves 1184 bytes of encapsulation key and 1088 bytes of ciphertext, roughly 2.3 kilobytes, against 64 bytes for the elliptic-curve exchange it replaces, and all of it lands in the first round trip of the connection. If you want to know which vendors are shipping this today, our guide to post-quantum cryptography companies tracks the field, and our explainer on what post-quantum cryptography is sets out the wider migration.

Frequently asked questions