Lattice cryptography: from LWE to Module-LWE.

Lattice cryptography combines precise algebra with controlled uncertainty. The legitimate computation arranges for large terms to cancel; the remaining error stays small enough to decode. Structure makes the operations efficient, while security depends on exactly which noisy problem, parameters, and attacker model the construction actually uses. This chapter derives a toy noisy-linear-system encryption flow with real, checkable numbers, shows how ring and module structure change the representation, and reproduces a small negacyclic transform-based polynomial product in Python — direct preparation for ML-KEM and ML-DSA in Parts 7–8, though it implements neither. All toy secrets and moduli here are intentionally, deliberately insecure.

1. Objectives and prerequisites

Part 4 introduced modular arithmetic, norms, polynomial rings, and the three security games — keep its distinction between arithmetic correctness and computational hardness firmly in mind throughout this chapter. The goal here is that once the relationships below are visible, a real specification's sequence of sampling, multiplication, compression, and hashing stops looking like an arbitrary pile of instructions and starts looking like a small number of ideas applied repeatedly.

2. Geometry: a lattice is generated by a basis

Choose linearly independent basis vectors \(b_1\) through \(b_n\). Their integer combinations form a lattice. In two dimensions, \(b_1=(2,0)\) and \(b_2=(1,2)\) generate points such as \((0,0)\), \((2,0)\), \((1,2)\), \((3,2)\), and \((0,4)\) — the coefficients multiplying the basis vectors are always integers, never arbitrary real numbers.

Different bases can generate the exact same set of points. One basis may make geometric relationships easy to see, while another looks completely awkward for the same lattice. Basis-reduction algorithms try to find more useful descriptions of the same underlying structure. In high dimensions, finding sufficiently short vectors or close lattice points can be computationally demanding — but the exact problem statement and approximation factor matter enormously to how demanding it actually is.

3. Shortest and closest vectors

The shortest-vector intuition asks for a nonzero lattice vector of minimal length. The closest-vector intuition asks for a lattice point nearest some target point. Cryptographic reductions often involve particular decision or approximation variants of these, rather than these exact informal tasks — norm, dimension, and approximation factor are all part of the problem statement, not incidental details.

The distinction between zero and nonzero is already important here: the origin is always a lattice vector with length zero, so a shortest-vector task that allowed it would be trivially solved by that observation alone. Similar exclusions appear throughout cryptographic relations — a missing "nonzero" or "short" condition can turn a hard-looking equation into an easy one.

Regev's LWE work connects a learning problem to worst-case lattice problems under stated conditions. Later ring and module constructions introduce structured lattice settings with their own separate reductions. These results provide disciplined, conditional evidence — not a blanket theorem that every equation containing a lattice symbol is automatically secure. See Regev, Ring-LWE, and Module lattices.

4. Learning With Errors

A useful LWE picture starts with a secret vector \(s\) over residues modulo \(q\). A public sample contains a vector \(a\) and a value \(b\) formed as the dot product of \(a\) with \(s\), plus a small error \(e\), modulo \(q\). Many such samples can be collected into \(b = As+e\) (Part 4 §5).

The search problem asks for the secret \(s\) under the specified distribution. A decisional formulation instead asks whether given samples come from that LWE distribution or from a suitable uniform distribution — these are related but genuinely distinct statements, and security proofs specify precisely which form they need and under what parameters a connection between the two is even available.

Without errors, enough independent equations reveal \(s\) directly through ordinary linear algebra. With carefully distributed errors, that direct solution no longer applies at all. An adversary can still attempt more sophisticated lattice, combinatorial, or algebraic attacks — the claim is never that noise prevents every conceivable method, only that the chosen problem is believed difficult at the specified parameters against all currently known methods.

5. How honest parties cancel the large terms

Consider a pedagogical public key \(t = As+e\). A sender samples a small vector \(r\) and additional small errors \(e_1\) and \(e_2\). It computes \(u = A^T r + e_1\) and \(v = t^T r + e_2 + \text{encode}(m)\). The recipient then computes \(v - s^T u\).

Public key:              t = A*s + e
Sender's first object:   u = transpose(A)*r + e1
Sender's second object:  v = dot(t,r) + e2 + encode(m)
Recipient subtracts:     v - dot(s,u)
Residual:                encode(m) + dot(e,r) + e2 - dot(s,e1)

Substituting the definitions gives \(e^T r + e_2 - s^T e_1 + \text{encode}(m)\), because the large \(A\) terms cancel exactly — this is the entire trick. If the remaining small-error residual lies within the decoding margin, the recipient recovers the encoded message correctly. The asymmetric information (only the recipient knows \(s\)) and the noisy public relation together motivate the whole construction; a complete encryption scheme needs much more precise definitions and analysis than this sketch provides.

The cancellation itself is a pure algebraic identity — it always happens, given the definitions. Whether the probability that remaining error stays decodable is high enough is a correctness question. Whether the public objects conceal the message from an attacker is a completely separate security question. Keeping these three levels — algebra, correctness, security — clearly separate is one of the most useful habits when reading lattice cryptography papers.

6. A fully worked tiny example

Use \(q=97\), \(A\) with rows \((3,7)\) and \((2,5)\), \(s=(1,-1)\), and \(e=(1,0)\). Then \(As=(-4,-3)\), so \(t=(-3,-3)\), represented modulo 97 as \((94,94)\). All values here are public for the purpose of this exercise.

Let \(r=(1,1)\), \(e_1=(0,1)\), \(e_2=-1\), and encode bit "one" as 48. The first ciphertext-like object is \(u=(5,13)\). The second is \(v = 94+94-1+48 = 235 \equiv 41 \pmod{97}\). The recipient computes \(s^T u = 5-13=-8\), then \(v - s^T u = 49\).

The decoded center for "one" was 48, so the residual error is exactly 1. The symbolic expression predicts the same result: \(e^T r + e_2 - s^T e_1 = 1 - 1 - (-1) = 1\). We can check the direct computation and the algebraic cancellation independently, and they agree.

7. From ordinary LWE to Ring-LWE

An unstructured matrix can require substantial storage and computation. Ring-LWE introduces algebraic structure so one ring element represents many coefficients at once, and multiplication becomes structured convolution (Part 4 §8). The foundational work studies the resulting problem and its connection to ideal lattices carefully — it does not merely assert that compression preserves every property of ordinary LWE for free. See Lyubashevsky, Peikert, and Regev.

A polynomial ring representation gives an efficient language for this structure. One entry can hold a vector of coefficients, and a single polynomial multiplication mixes those coefficients according to one fixed rule. The public relation can be compactly described without ever storing a completely independent scalar matrix entry for every pairwise interaction.

The performance benefit comes paired with a more specialized assumption. A structured distribution is not the same object as an arbitrary random matrix distribution. That's not automatically a weakness in a deployed parameter set — but it has to be explicitly acknowledged in the security statement. More structure and more cryptanalytic confidence are two separate axes, not interchangeable measurements of the same thing.

8. Module-LWE: vectors whose entries are polynomials

Module-LWE uses vectors and matrices over a ring rather than over a field. If the module rank is \(k\) and each polynomial has \(n\) coefficients, a vector contains \(k \times n\) scalar coefficients total — but its algebraic organization remains significant. A \(k\)-by-\(k\) matrix of ring elements is not equivalent to a fully unstructured \(kn\)-by-\(kn\) scalar matrix with independent entries; the ring structure inside each block is preserved and matters for both performance and security.

This gives a design space sitting between pure scalar-ring constructions and fully unstructured forms. Module rank and ring degree both affect representation, performance, and the underlying hardness problem. The module-lattice reduction literature makes those relationships explicit — it should never be summarized as "more rank always means more secure" without accounting for the rest of the parameter choice too. See Langlois and Stehlé.

ML-KEM uses degree-256 polynomials modulo \(q=3329\), with module rank 2, 3, or 4 across its three parameter sets. Its named security levels also involve specific sampling and compression choices layered on top. ML-DSA uses a different modulus and different matrix dimensions entirely. The same optimization idea can apply to both, but the actual constants and representations are algorithm-specific and not interchangeable. See FIPS 203 and FIPS 204.

9. Module-SIS is a different problem

The short-integer-solution (SIS) intuition asks for a short, nonzero vector \(z\) satisfying a modular relation such as \(Az = 0\). Solving the modular equation alone is not the hard part in the intended setting — finding a solution that also satisfies the smallness constraint is the actual central difficulty. Without that bound, ordinary linear algebra can often find many solutions trivially.

Signature constructions use related short-relation ideas, along with challenge generation and message binding (§10 of Part 2, Part 8 in detail). A forgery can be connected to solving an underlying problem via a security proof, but the exact reduction may involve specialized variants and additional assumptions beyond plain SIS. "ML-DSA equals Module-SIS" is therefore too compressed a statement to explain its full security argument on its own.

The practical distinction to hold onto: LWE emphasizes noisy observations that shouldn't reveal a secret or any distinguishable structure; SIS emphasizes finding a short relation. Both live in the same lattice-related landscape and can share arithmetic machinery, yet they play genuinely different roles in constructions. Part 8 shows exactly how bounded responses and rejection sampling enter ML-DSA's signing procedure.

10. Sampling and compression are part of the algorithm

A sampler translates random bits into a required distribution. Uniform sampling modulo \(q\) may use rejection to avoid bias whenever \(q\) is not a power of two. Small-noise sampling uses a different, specified distribution entirely. Reusing one sampling routine "because it's faster" can silently alter the mathematical object actually being generated, invalidating the security argument built around the original distribution.

Compression reduces representation size by deliberately approximating coefficients, and decompression maps them back to representative values. The approximation itself contributes error. A protocol designer cannot reduce ciphertext bytes indefinitely without affecting the honest decoding margin (§6) and possibly the security argument along with it — the standard's exact rounding behavior and bit widths are consequently mandatory implementation details, not tuning knobs.

There are also genuinely distinct reasons for rejection throughout these algorithms. Rejecting out-of-range candidates during uniform sampling avoids distribution bias. Rejecting a signature candidate (Part 8) can hide relationships to the secret key. Rejecting malformed external input enforces an interface contract. These three operations should not be conflated just because all three contain a loop or a conditional branch that "rejects" something.

11. Why polynomial multiplication dominates attention

Directly multiplying two degree-\((n-1)\) polynomials requires on the order of \(n^2\) coefficient products using the schoolbook method. Structured transforms can reduce the asymptotic work by moving to a representation where multiplication becomes many smaller, independent operations. The conversion in and out of that representation has its own cost, so the practical benefit depends on sizes, reuse, and target hardware.

An NTT (number-theoretic transform) is a finite-field analogue of a Fourier transform. It uses roots of unity in modular arithmetic rather than complex floating-point numbers. The required roots must actually exist for the chosen transform convention and ring — this is exactly why picking a modulus and then simply assuming a convenient transform exists for it can be wrong.

11.1 A butterfly is a small reusable operation

A common transform building block combines values \(a\) and \(b\) using a root-derived factor \(w\): compute \(t = w \times b\), then output \(a+t\) and \(a-t\), reduced modulo \(q\). With \(q=17\), \(a=3\), \(b=5\), and \(w=1\), the outputs are 8 and 15 — multiple stages arrange these small operations to evaluate or invert a full transform efficiently.

The factor \(w\) is often called a twiddle factor. Its order, stage placement, and representation all matter. Real implementations may store values in bit-reversed order, use Montgomery arithmetic, or defer some reductions within proven bounds. Matching high-level formulas alone does not excuse ignoring these conventions when comparing raw arrays between two implementations.

The performance work here is therefore both algebraic and architectural. Efficient loads, vector lanes, cache use, and instruction scheduling all matter in practice. Every optimization must preserve the arithmetic bounds and secret-independent timing behavior required — a faster NTT that overflows a signed integer on one target platform is not a valid implementation improvement, it's a bug.

11.2 Reproduce a negacyclic transform product

For \(n=4\) and \(q=17\), choose \(\psi=2\): \(\psi^4 \equiv -1\) and \(\psi^8 \equiv 1 \pmod{17}\). Let \(\omega = \psi^2 = 4\), which has order four. Twist coefficients by \(\psi^i\), apply a four-point transform using \(\omega\), multiply the transformed values pointwise, invert, and untwist. This computes multiplication modulo \(x^4+1\) — the same negacyclic rule from Part 4 §9.

q, n, psi, omega = 17, 4, 2, 4
assert pow(psi, 4, q) == q-1 and pow(psi, 8, q) == 1

def transform(a, inverse=False):
    w = pow(omega, -1, q) if inverse else omega
    scale = pow(n, -1, q) if inverse else 1
    return [sum(a[j]*pow(w, j*k, q) for j in range(n))*scale % q
            for k in range(n)]

def multiply(a, b):
    aa = transform([a[i]*pow(psi,i,q) % q for i in range(n)])
    bb = transform([b[i]*pow(psi,i,q) % q for i in range(n)])
    c = transform([x*y % q for x,y in zip(aa,bb)], inverse=True)
    return [c[i]*pow(psi,-i,q) % q for i in range(n)]

assert multiply([1,0,0,2], [3,1,0,0]) == [1,1,0,6]
assert [(3+5)%17, (3-5)%17] == [8,15]
print('Toy transform checks passed')

The code uses a direct (\(O(n^2)\)) transform for clarity, not a fast butterfly implementation — it validates the transform identity and normalization against the earlier multiplication example from Part 4 §9. Its Python arithmetic and branches are not intended for secret processing under any circumstances. Studying a maintained implementation such as mlkem-native is the natural next step for understanding how real, production code handles these constraints correctly.

12. Security reductions and engineering evidence

A reduction says that a successful attack under certain conditions would yield an algorithm for another, presumably-hard problem — it provides a structured, conditional argument. The concrete parameter decision also needs a separate analysis of known attacks, reduction losses, and the particular distributions actually used. An introductory proof sketch like this chapter's cannot replace that dedicated cryptanalytic work.

Implementation evidence addresses a different boundary entirely. Known-answer tests establish agreement on fixed examples; differential tests compare independent implementations against each other; formal proofs can establish specified properties within a formal model; side-channel analysis examines actual observable behavior on real hardware. None of these alone proves a whole deployed application is secure — Part 13 combines all of them into one implementation-assurance argument.

Concept	What it explains	What it does NOT establish alone
Cancellation identity	Why honest arithmetic can recover an encoded value	Confidentiality against an attacker
Noise distribution	The sampled problem and correctness budget	Security of arbitrary replacement parameters
Module structure	Compact algebraic representation	Equivalence to unstructured LWE
NTT	Efficient multiplication in a specified representation	Correctness of all compiler/target combinations
Reduction	A conditional relationship between problems	Absence of future attacks or implementation leakage

Why does the toy recipient obtain 49 instead of 48?

The large matrix terms cancel exactly (§5), leaving the encoded center (48) plus a residual error of 1 — the worked example in §6 confirms this both by direct computation and by the symbolic cancellation formula.

Why is "solve Az = 0" incomplete as an SIS description?

The solution must be suitably short and nonzero (§9) — those two constraints are what makes the problem hard. Without them, ordinary linear algebra finds solutions trivially.

Why not use the toy transform from §11.2 directly for ML-KEM?

Its modulus, degree, root structure, memory layout, and multiplication convention all differ from the actual FIPS 203 standard (§11). It demonstrates the transform identity, not ML-KEM's exact operations.

Takeaways

• The core mechanism is cancellation: \(t=As+e\) lets a legitimate recipient's construction cancel the large \(A\)-dependent terms algebraically, leaving a small, decodable residual an attacker can't reproduce without the secret.
• Algebra, correctness, and security are three separate levels — the cancellation identity always holds; whether decoding succeeds is a correctness question; whether the message stays hidden is a security question.
• Ring-LWE and Module-LWE trade a more specialized assumption for compact, efficient representation — structure is a real, deliberate tradeoff, not a free performance win with no security cost to consider.
• LWE and SIS play different roles despite sharing lattice machinery — LWE hides a secret in noisy observations; SIS asks for a short nonzero relation. ML-KEM leans on the former, ML-DSA's core reduction leans on variants of the latter.
• Sampling and compression are mandatory, specified parts of the algorithm — swapping a sampler "because it's faster" changes the actual distribution and can invalidate the security argument entirely.
• A reduction proof is conditional evidence, not a guarantee — it needs to be combined with concrete attack-cost analysis and separate implementation-assurance work (Part 13) to say anything about a deployed system.

References & further reading

• Regev — On Lattices, Learning with Errors... — §3, §4, the foundational LWE reduction.
• Lyubashevsky, Peikert & Regev — Ring-LWE — §3, §7.
• Langlois & Stehlé — Module lattices — §3, §8.
• Lindner & Peikert — §4, concrete parameter/attack balance.
• FIPS 203 (ML-KEM) · FIPS 204 (ML-DSA) — §8, §11, the real parameters.
• mlkem-native — §11.2, a maintained real-world implementation.