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 uses.

Objectives and prerequisites

Part 4 introduced modular arithmetic, norms, polynomial rings, and security games. Keep its distinction between arithmetic correctness and computational hardness in mind. Here you will derive a toy noisy-linear-system encryption flow, understand how ring and module structure change the representation, and reproduce a small transform-based polynomial product.

This is preparation for ML-KEM and ML-DSA, not an implementation of either. All toy secrets and moduli are intentionally insecure. The goal is to expose the relationships that real specifications preserve. Once those relationships are visible, a sequence of sampling, multiplication, compression, and hashing stops looking like an arbitrary collection of instructions.

Geometry: a lattice is generated by a basis

Choose linearly independent basis vectors b₁ through bₙ. Their integer combinations form a lattice. In two dimensions, b₁ = (2, 0) and b₂ = (1, 2) generate points such as (0, 0), (2, 0), (1, 2), (3, 2), and (0, 4). The coefficients multiplying the basis vectors are integers, not arbitrary real numbers.

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

One possible two-dimensional lattice:

 y=4   o-----o-----o-----o
 y=2      o-----o-----o-----o
 y=0   o-----o-----o-----o
          x increases -->

Every point is an integer combination of (2,0) and (1,2).
A target between points need not itself be a lattice point.

This picture builds geometric intuition only. A cryptographic lattice may have hundreds or thousands of dimensions, and its security can involve distributions and modular structure that a two-dimensional drawing cannot represent. Do not infer an attack's cost from how easy the closest point looks in a diagram.

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 a target. Cryptographic reductions often involve particular decision or approximation variants rather than these exact informal tasks. Norm, dimension, and approximation factor are part of the problem statement.

The distinction between zero and nonzero is already important: zero is always a lattice vector and has length zero, so a shortest-vector task that allowed it would be trivial. Similar exclusions appear in cryptographic relations. A missing “nonzero” or “short” condition can turn a hard-looking equation into an easy problem.

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 reductions. These results provide disciplined evidence, not a blanket theorem that every equation containing a lattice symbol is secure. Regev, Ring-LWE, Module lattices

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.

The search problem asks for the secret under the specified distribution. A decisional formulation asks whether samples come from that distribution or from a suitable uniform distribution. These are related but distinct statements. Security proofs specify which form they need and under what parameters a connection is available.

Without errors, enough independent equations can reveal s through linear algebra. With carefully distributed errors, that direct solution no longer applies. The adversary can still use more sophisticated lattice, combinatorial, or algebraic attacks. The claim is not that noise prevents every conceivable method; it is that the chosen problem is believed difficult at the specified parameters.

Noise cannot be selected casually. A distribution with too little uncertainty, repeated error patterns, or exploitable correlations can change the problem. Increasing the amount of error also affects honest computation. Concrete parameter work balances these effects with attack estimates and correctness analysis. Lindner and Peikert

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₁ and e₂. It computes u = Aᵀr + e₁ and v = tᵀr + e₂ + encode(m). The recipient computes v − sᵀu.

Substituting the definitions gives eᵀr + e₂ − sᵀe₁ + encode(m), because the large A terms cancel. If the remaining error lies within the decoding margin, the recipient recovers the encoded message. The asymmetric information and the noisy public relation motivate the construction; a complete encryption scheme needs much more precise definitions and analysis.

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)

The cancellation is an algebraic identity. The probability that residual error remains decodable is a correctness question. Whether public objects conceal the message is a security question. Keeping those three levels separate is one of the most useful habits when reading lattice cryptography.

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 the exercise.

Let r = (1, 1), e₁ = (0, 1), e₂ = −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 = 41 modulo 97. The recipient computes sᵀu = 5 − 13 = −8, then v − sᵀu = 49.

The decoded center for one was 48, so the residual error is one. The symbolic expression predicts the same result: eᵀr + e₂ − sᵀe₁ = 1 − 1 − (−1) = 1. We can check both the direct computation and the cancellation independently.

This example is not ML-KEM's K-PKE and is not a secure encryption scheme. Its secret and randomness spaces are tiny, its parameters are invented, and its encoding is only illustrative. It exists to make one mechanism visible: cancellation leaves a controlled residual. Part 7 replaces these illustrative choices with the actual standardized operations.

From ordinary LWE to Ring-LWE

An unstructured matrix can require substantial storage and computation. Ring-LWE introduces algebraic structure so an element represents many coefficients and multiplication becomes structured convolution. The foundational work studies the resulting problem and its connection to ideal lattices; it does not merely assert that compression preserves every property of ordinary LWE. Lyubashevsky, Peikert, and Regev

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

The performance benefit comes with a more specialized assumption. A structured distribution is not the same as an arbitrary random matrix distribution. That is not automatically a weakness in a deployed parameter set, but it must be acknowledged in the security statement. More structure and more cryptanalytic confidence are separate axes, not interchangeable measurements.

Module-LWE: vectors whose entries are polynomials

Module-LWE uses vectors and matrices over a ring. If the module rank is k and a polynomial has n coefficients, a vector contains k×n scalar coefficients, 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.

This gives a design space between scalar ring constructions and unstructured forms. Module rank and ring degree affect representation, performance, and the underlying problem. The module-lattice reduction literature makes those relationships explicit. It should not be summarized as “more rank always means secure” without the rest of the parameter choice. Langlois and Stehlé

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

Module-SIS is a different problem

The short-integer-solution 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 central. Without the bound, ordinary algebra can often find many solutions.

Signature constructions use related short-relation ideas along with challenge generation and message binding. A forgery can be connected to solving an underlying problem in a proof, but the exact reduction may involve specialized variants and additional assumptions. “ML-DSA equals Module-SIS” is therefore too compressed to explain its whole security argument.

The practical distinction is this: LWE emphasizes noisy observations that should not reveal a secret or distinguishable structure; SIS emphasizes finding a short relation. Both live in a lattice-related landscape and can share arithmetic machinery, yet they play different roles in constructions. Part 8 will show how bounded responses and rejection sampling enter signing.

Sampling and compression are part of the algorithm

A sampler translates random bits into the required distribution. Uniform sampling modulo q may use rejection to avoid bias when q is not a power of two. Small-noise sampling uses a different specified distribution. Reusing one routine because it is faster can alter the mathematical object being generated.

Compression reduces representation size by approximating coefficients, and decompression maps them back to representative values. The approximation contributes error. A protocol designer cannot reduce ciphertext bytes indefinitely without affecting the honest decoding margin and possibly the security argument. The standard's rounding behavior and bit widths are consequently mandatory details.

There are also distinct reasons for rejection. Rejecting out-of-range candidates during uniform sampling avoids distribution bias. Rejecting a signature candidate can hide relationships to the secret. Rejecting malformed external input enforces an interface contract. These operations should not be conflated merely because all contain a loop or a conditional branch.

Why polynomial multiplication dominates attention

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

An NTT 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 exist for the transform convention and ring. This is why picking a modulus and then assuming a convenient transform exists can be wrong.

Coefficient representation
        |
Twist if the negacyclic construction requires it
        |
Forward transform
        |
Pointwise or specified small-block multiplication
        |
Inverse transform and normalization
        |
Untwist if required -> reduced coefficients

ML-KEM's specific transform does not fully split its degree-256 negacyclic ring into scalar evaluations because the needed primitive 512th root is unavailable modulo 3329. Its NTT representation instead uses the specified quadratic components and base multiplication. The standard is authoritative for those details. Our next example deliberately uses a modulus where a fully split toy construction is possible. FIPS 203

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×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 transform efficiently.

The factor w is often called a twiddle factor. Its order, stage placement, and representation matter. Implementations may store bit-reversed order, use Montgomery arithmetic, or defer some reductions within proven bounds. Matching high-level formulas does not excuse ignoring those conventions when comparing arrays between implementations.

The performance work is therefore both algebraic and architectural. Efficient loads, vector lanes, cache use, and instruction scheduling matter. Every optimization must preserve arithmetic bounds and secret-independent behavior where required. A faster NTT that overflows a signed integer on one target is not a valid implementation improvement.

Reproduce a negacyclic transform product

For n = 4 and q = 17, choose ψ = 2: ψ⁴ = −1 and ψ⁸ = 1 modulo 17. Let ω = ψ² = 4, which has order four. Twist coefficients by ψ^i, apply a four-point transform using ω, multiply transformed values, invert, and untwist. This computes multiplication modulo x⁴ + 1.

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 transform for clarity, not a fast butterfly implementation. It validates the transform identity and normalization against the earlier multiplication example. Its Python arithmetic and branches are not intended for secret processing. Studying a maintained implementation such as mlkem-native is the next step for understanding how actual code handles these constraints.

Security reductions and engineering evidence

A reduction says that a successful attack under certain conditions would yield an algorithm for another problem. It provides a structured conditional argument. The concrete parameter decision also needs analysis of known attacks, reduction losses, and the particular distributions used. An introductory proof sketch cannot replace that work.

Implementation evidence addresses another boundary. Known-answer tests establish agreement on examples; differential tests compare implementations; formal proofs can establish specified properties within a model; side-channel analysis examines observable behavior. None of these alone proves the whole deployed application secure. Part 13 will combine them into an implementation-assurance argument.

Knowledge check and next step

Why does the toy recipient obtain 49 instead of 48? The large matrix terms cancel, leaving the encoded center plus residual error one.

Why is “solve Az = 0” incomplete as an SIS description? The solution must be suitably short and nonzero; those constraints are central.

Why not use the toy transform directly for ML-KEM? Its modulus, degree, root structure, layout, and multiplication convention differ from the standard.

You can now read a lattice operation as a combination of algebra, distribution, representation, and security purpose. Part 7 follows the complete ML-KEM interface, including the transformation that strengthens its internal encryption component and the rejection behavior required for hostile ciphertexts.