PQC notation becomes manageable the moment each symbol represents an operation you've already performed by hand on a small example. This chapter builds that vocabulary from remainders up through polynomial arithmetic, then explains precisely what cryptographers mean by "hardness" and "security" — culminating in the three security games (IND-CPA, IND-CCA, EUF-CMA) you'll see named throughout Parts 7–9. Every numerical example here is educational, not a secure parameter choice — the goal is to be able to read an expression like \(t = As + e \bmod q\) and know exactly what each object is, how to compute it by hand, and which part of its security is an assumption rather than an arithmetic identity.
1. Objectives and prerequisites
You need integer arithmetic and the cryptographic roles from Part 2 — you do not need calculus or a mathematics degree for any of this. The examples deliberately use tiny spaces so their behavior stays fully visible by hand. Tiny spaces are also trivially easy to enumerate, which makes them unsuitable for actual security — a successful calculation below demonstrates correctness of arithmetic only, never that recovering a secret is computationally difficult. The ML-KEM standard supplies the real algorithm and parameters; these examples exist purely as preparation for reading it in Part 7.
2. Modular arithmetic: working with remainders
Arithmetic modulo \(q\) identifies integers that differ by a multiple of \(q\). For \(q=7\), the numbers \(3\), \(10\), and \(-4\) all represent the same residue. We can choose representatives from \(0\) through \(6\), so \(10 \bmod 7 = 3\) and \(-4 \bmod 7 = 3\). Addition and multiplication are simply followed by reduction back to a representative.
Compute \(5+6 \bmod 7\): the ordinary sum is 11, which reduces to 4. Compute \(5 \times 6\): the product 30 reduces to 2. Reduction can also happen partway through a longer calculation, because it preserves both operations — this is genuinely useful in software, where letting an intermediate integer grow without bound risks overflowing its machine representation.
Subtraction often makes a negative representative the natural choice. The residue \(6 \bmod 7\) can equally be written as \(-1\). A centered representation chooses values near zero, which is useful when discussing small errors (§8). The residue hasn't changed — only the chosen integer representative has. Confusing a residue with its unsigned storage value can make a genuinely small error look artificially large, a real source of implementation bugs.
3. Division requires an inverse
Dividing by a nonzero element means multiplying by its multiplicative inverse, when one exists. Modulo 7, the inverse of 3 is 5, because \(3 \times 5 = 15 \equiv 1 \pmod 7\). So dividing 2 by 3 in this field gives \(2 \times 5 = 3 \pmod 7\) — this is not ordinary real-number division followed by truncation, a common misreading.
Not every nonzero residue has an inverse for every modulus. Modulo 8, the number 2 has no multiplicative inverse at all: multiplying it by any integer stays even, and can never reach 1 modulo 8. More generally, an integer has an inverse modulo \(q\) exactly when it's relatively prime to \(q\). The extended Euclidean algorithm computes such inverses efficiently.
When \(q\) is prime, the residues modulo \(q\) form a finite field — every nonzero element is invertible. This explains why a prime modulus is convenient, but it does not imply that every structure built from that field is itself a field — polynomial quotient rings (§8) introduce an additional condition, and that distinction becomes important when interpreting the arithmetic lattice schemes actually use.
4. Vectors and dot products
A vector is simply an ordered list. Let \(a = (1,2)\) and \(s = (2,1)\). Their dot product multiplies corresponding entries and sums the products: \(1{\times}2 + 2{\times}1 = 4\). Modulo 7, the result stays 4. Order matters here — it's what tells us which entries are paired with which.
A vector is not necessarily a point in ordinary physical space. It may encode coefficients, samples, or entirely algebraic objects. In a module-lattice construction (Part 6), a single vector entry can itself be a whole polynomial. Keeping careful track of the type of each entry prevents a common and costly mistake: treating a vector of polynomials as though it were a vector of single integers, silently losing an entire dimension of the construction.
The transpose symbol changes rows into columns. A row vector times a column vector produces a scalar dot product. A column vector times a row vector instead produces a full matrix. These two operations look almost identical on paper but return completely different kinds of objects — when reading unfamiliar pseudocode, write out the dimensions beside every matrix multiplication before trying to simplify or optimize it.
5. Matrices as many equations at once
Let \(A\) have rows \((1,2)\) and \((3,4)\), and let \(s=(2,1)\). Multiplication produces \(As = (4,10)\), or \((4,3)\) modulo 7 — each row of \(A\) defines exactly one dot product with \(s\). The compact matrix notation is simply collecting several equations into one expression.
Now add \(e = (1,-1)\). We obtain \(t = As+e = (5,2)\) modulo 7. Here \(A\) is public in this toy example, \(s\) is the value we imagine hiding, and \(e\) is a small deliberate disturbance. Without that disturbance, a suitable invertible system can just be solved by ordinary linear algebra. With it, the observed equations are no longer exact equations for \(s\) alone — this small addition is the entire idea behind LWE.
A = [1 2] s = [2] e = [ 1]
[3 4] [1] [-1]
A*s = [ 4] A*s + e mod 7 = [5]
[10] [2]This is only the shape of a noisy-linear-system example. Real LWE assumptions depend on dimensions, sample counts, distributions, modulus, and the attack model under consideration — adding an arbitrary perturbation to a small invertible matrix does not, by itself, create a secure cryptosystem. Regev's foundational work connects carefully specified learning problems like this one to worst-case lattice problems under explicit, stated conditions. See Regev.
6. Norms: more than one meaning of "small"
A norm measures vector size, and there's more than one useful way to do it. For \(v = (-2,1,2)\): the one-norm is \(|-2|+|1|+|2|=5\); the Euclidean norm is \(\sqrt{4+1+4}=3\); the infinity-norm is the largest absolute coordinate, which is 2. These three values answer three genuinely different questions about the same vector.
A bound on every coefficient individually is naturally expressed with the infinity-norm. Geometric distance more often uses the Euclidean norm. A proof or rejection condition that's written using one must never be silently swapped for the other — dimension changes the relationship between the two norms, so even a seemingly conservative substitution can quietly change a correctness or security condition.
For modular values, the representative convention from §2 matters again here. In modulo-7 arithmetic, a stored coefficient of 6 may actually represent the centered value \(-1\). Measuring "6" when the specification intends the centered value \(-1\) can either reject valid objects or admit invalid ones — exact definitions of reduction, rounding, and norm are implementation requirements, never stylistic preferences left to the implementer.
7. Probability distributions and sampling
A distribution assigns probabilities to possible outcomes. A uniform distribution on seven residues gives each one probability \(1/7\). A distribution concentrated near zero behaves very differently — zero may be common while large magnitudes are rare or even impossible. In cryptography, the exact distribution used is part of the scheme's formal definition, not an implementation detail left open to choice.
One small worked example: take four independent fair coin flips, add the first two, and subtract the last two. The possible results are \(-2,-1,0,1,2\), with respective counts \(1,4,6,4,1\) among the sixteen equally likely bit strings. The distribution is centered and bounded — this illustrates the shape of a centered binomial distribution, without claiming these particular four bits describe every sampler used in every lattice scheme.
8. Polynomials as structured vectors
The polynomial \(a(x) = 1+2x+3x^2\) can be stored as the coefficient vector \((1,2,3)\). Adding polynomials adds corresponding coefficients directly. Multiplication combines every coefficient of one polynomial with every coefficient of the other, according to the resulting powers of \(x\).
For example: \((1+2x)(3+x) = 3+7x+2x^2\). Modulo 7, its coefficient vector becomes \((3,0,2)\). The middle coefficient receives two separate contributions — \(1{\times}1\) and \(2{\times}3\) — summed together. This combining of shifted products is exactly convolution, the operation lattice implementations spend most of their compute time on.
The symbol \(x\) is purely formal here — we are never evaluating the polynomial at any particular real number. It just records how coefficients shift and combine under multiplication. Thinking of polynomial multiplication as structured convolution makes it much easier to understand why fast transforms (the NTT, covered in Part 6) can dramatically accelerate it.
9. Quotient rings: a rule for folding powers back
A polynomial quotient ring adds an explicit reduction rule on top of ordinary polynomial arithmetic. In \(R = \mathbb{F}_{17}[x]/(x^4+1)\), coefficients are reduced modulo 17, and powers are reduced using the rule \(x^4 = -1\). Therefore \(x^5=-x\), \(x^6=-x^2\), and \(x^7=-x^3\) — every element of this ring can be represented using at most four coefficients, no matter how high a power appears during multiplication.
Multiply \(a=1+2x^3\) by \(b=3+x\). Ordinary multiplication gives \(3+x+6x^3+2x^4\). Folding \(x^4\) to \(-1\) changes the constant coefficient from 3 to 1, producing \(1+x+6x^3\). The final coefficient vector is \((1,1,0,6)\).
The negative sign in the folding rule makes this a negacyclic convolution. A quotient by \(x^4-1\) instead would use \(x^4=1\) and produce a genuinely different result. Confusing cyclic and negacyclic multiplication is not a small numerical rounding error — it means computing in the entirely wrong algebraic structure, which silently invalidates every downstream calculation.
There are two independent reductions happening at once: coefficient reduction modulo 17, and polynomial reduction modulo \(x^4+1\). The former bounds coefficient representatives; the latter bounds the polynomial's degree. Many intimidating-looking expressions throughout PQC literature are just compact ways of naming both of these rules simultaneously.
10. Coding-theory bridge: bits, distance, and syndromes
A binary vector uses entries in \(\mathbb{F}_2\), where addition is XOR. The Hamming weight counts nonzero entries; the Hamming distance between two vectors counts the positions where they differ. For \(1011\) and \(1000\), the distance is two. This describes errors by their locations rather than by Euclidean length — the natural error model for a noisy binary channel.
A code adds redundancy so a receiver can distinguish likely original messages from corrupted observations. A parity-check matrix \(H\) gives a syndrome \(Hc\) for a received vector \(c\), using arithmetic in the relevant field. Valid codewords satisfy the code's parity-check equations exactly; an error changes the syndrome in a way that (with enough structure) reveals where the error is. Decoding tries to infer a suitable codeword or error under a specific noise model.
For a tiny parity check: \(H = (1,1,1)\) and \(c=(1,0,1)\) give syndrome 0. Flipping the middle bit yields \((1,1,1)\), giving syndrome 1. This detects an odd number of flips but cannot identify which single bit changed — more structure is needed for actual correction, and cryptographic code-based schemes (Part 10, HQC) pose carefully chosen decoding problems that are computationally hard in a specific, precise sense — not this toy parity bit used as "security."
11. Why noise can help — and hurt
In ordinary engineering, noise is usually something to remove. In LWE-style constructions, carefully controlled uncertainty instead helps separate public observations from a secret. The legitimate computation uses relationships specifically designed to cancel large terms, leaving behind a small residual that the intended recipient can decode — while an attacker, lacking the same secret information, cannot perform that cancellation at all.
Noise must fit inside a strict correctness budget. Too little noise can weaken the intended hiding problem; too much can make even honest decoding fail outright. Compression (used to shrink ciphertexts) can add another bounded approximation error on top. These effects have to be analyzed together, never described as "more noise = more security" in an unlimited sense. Part 6 develops the cancellation intuition in full before Part 7 follows ML-KEM's exact operations.
This tradeoff is exactly why seemingly harmless implementation changes can secretly become cryptographic changes. Altering a rounding rule, a distribution, or an acceptance bound can affect both correctness and what an attacker learns from observing outputs. Performance optimization work has to preserve the exact specified mathematical object — not merely make a random sample of test exchanges pass, which can hide a real correctness or security regression.
12. Hardness is a statement with parameters
A problem is computationally hard only relative to a model, a parameter growth regime, and the algorithms currently known against it. "There are many possible secrets" is not enough on its own — structure can let an attacker avoid enumerating all of them, sometimes dramatically. Conversely, exhibiting one expensive known attack does not prove that no cheaper attack exists; absence of a known break is not a proof of security.
A security reduction connects an adversary against a construction to an algorithm for solving another, presumably-hard problem. It supplies a conditional argument — its assumptions, loss factors, and threat model all matter enormously when interpreting concrete parameter choices. A worst-case-to-average-case connection (as Regev's LWE work provides) is valuable evidence, but it should never be paraphrased as an unconditional proof that one specific compiled binary cannot leak its key through some other channel.
Asymptotic statements study a security parameter \(\lambda\) growing without bound. Concrete security instead studies actual sizes and real attack resources at a fixed parameter. Both are useful lenses. The distinction resembles the difference between an algorithm's big-O complexity and its measured runtime on one particular machine — except cryptographic comparisons also depend on the adversary's assumed capabilities and success probability, which big-O analysis doesn't need to track.
13. Negligible probability
A function is negligible if it eventually becomes smaller than the inverse of every positive polynomial in the security parameter. An exponentially decreasing function such as \(2^{-\lambda}\) is negligible. The function \(1/\lambda^{100}\) is extremely small for many practical values of \(\lambda\), but it is not negligible under this formal definition — it's still just inverse-polynomial, no matter how large the exponent.
This definition should never be confused with a universal operational acceptance threshold. A fleet executing enormous numbers of operations has to consider aggregate risk across all of them, and a proof's negligible bound still requires real, concrete interpretation at your actual scale. The union bound gives a simple, conservative tool here: the probability of any of several events happening is at most the sum of their individual probabilities, without requiring the events to be independent.
For illustration: if each of a million operations has failure probability at most \(10^{-12}\), the union bound gives at most \(10^{-6}\) for at least one failure across the whole million. These are invented numbers purely to explain the calculation — not failure-rate claims for any standardized algorithm. A real security argument needs the actual proven bound and the precisely correct event definition, not a plausible-sounding estimate.
14. Three security games engineers should recognize
| Game | Informal setup | What it does NOT cover |
|---|---|---|
| IND-CPA | Adversary picks two equal-length messages, receives an encryption of one chosen by a hidden bit, and must guess which. Encryption shouldn't reveal the choice beyond what's explicitly permitted. | Any active manipulation of ciphertexts — that's IND-CCA's job. |
| IND-CCA | Strengthens IND-CPA with access to a decryption oracle under restrictions (notably, no trivial query on the challenge ciphertext itself). A KEM uses a related real-vs-random shared-secret experiment with a decapsulation interface. | It should not be described as merely "the same plaintext game with different function names" — the decryption oracle access is the entire point. |
| EUF-CMA | Existential unforgeability under chosen-message attack. The attacker obtains signatures on chosen messages, then tries to produce a valid signature on a genuinely new message. | Differs from stronger notions that also forbid a new signature on an already-signed message — knowing the exact goal prevents overstating what a scheme proves. |
For full formal definitions and constructions, use Boneh and Shoup's book and the security discussion in SP 800-227. The descriptions above are intuition-building only — not substitutes for the complete formal experiments or the quantum-query security models used in particular published proofs. See Boneh & Shoup and SP 800-227.
Fig. 1 — Three different attacker capabilities, testing three different things. Naming which game a paper's proof actually targets prevents overstating what that proof establishes.
15. Reproduce the arithmetic
The following Python 3 checks cover every worked example above, independently of any cryptographic library. Their deliberately straightforward multiplication is for learning — it is not constant-time, production-grade code, and should never be used as such.
from itertools import product
from collections import Counter
# Modular arithmetic (Section 2-3)
assert (5 + 6) % 7 == 4
assert (5 * 6) % 7 == 2
assert (3 * 5) % 7 == 1 # inverse of 3 mod 7 is 5
# Matrix-vector: t = As + e mod 7 (Section 5)
A, s, e = [[1, 2], [3, 4]], [2, 1], [1, -1]
assert [(sum(a*b for a, b in zip(row, s)) + z) % 7
for row, z in zip(A, e)] == [5, 2]
# Centered binomial from 4 fair bits (Section 7)
counts = Counter(a+b-c-d for a,b,c,d in product([0,1], repeat=4))
assert [counts[i] for i in range(-2,3)] == [1,4,6,4,1]
# Negacyclic polynomial multiplication mod (x^4+1), mod 17 (Section 9)
a, b, out = [1,0,0,2], [3,1,0,0], [0]*4
for i in range(4):
for j in range(4):
k = i+j
out[k % 4] += a[i]*b[j] * (1 if k < 4 else -1)
assert [v % 17 for v in out] == [1,1,0,6]
print('Mathematics examples passed')Why is −1 sometimes represented as q−1?
They're the same residue (§2) — centered and nonnegative representatives just serve different purposes. Centered representations make small errors visually and analytically small; nonnegative representations are simpler to store.
Does a prime coefficient modulus make every quotient ring a field?
No (§9). The polynomial modulus must also satisfy the relevant irreducibility condition — "all coefficients are modulo a prime" alone doesn't justify dividing by every nonzero polynomial.
Why can more noise reduce reliability?
Honest decoding has a finite correctness margin (§11), and any residual error has to fit inside that margin. Too much noise pushes legitimate decoding outside it, causing correct implementations to fail.
Is a tiny passing example evidence of security?
No (§1, §12). It demonstrates arithmetic correctness only — a tiny secret space like our examples here can simply be brute-force searched, which real LWE parameters are specifically chosen to prevent.
Does IND-CCA authenticate a peer's identity?
No (§14). It's a confidentiality-style primitive security notion, not a complete authenticated protocol — that additional layer is exactly what Parts 6, 9, and 11 build on top of a secure KEM or signature scheme.
Takeaways
- Every symbol in a PQC paper corresponds to an operation you can perform by hand on a small example — modular reduction, dot products, polynomial convolution, and quotient-ring folding are all mechanical once separated from their notation.
- LWE's core idea is one line: \(t = As+e\) is solvable exactly without \(e\), but the added noise makes recovering \(s\) computationally hard — while a legitimate recipient's construction is designed to cancel that same noise.
- Norms answer different questions — infinity-norm bounds individual coefficients, Euclidean norm measures geometric distance. Silently swapping one for the other in a proof or bound is a real error, not a stylistic choice.
- A quotient ring is not automatically a field — it needs an irreducible defining polynomial, and ML-KEM's exact ring (\(q=3329\), degree 256) is tailored to its own specific transform structure.
- "Hard" is always relative to a model and parameter regime — a security reduction is a conditional argument, not an unconditional proof that a specific compiled binary can't leak its key some other way.
- IND-CPA, IND-CCA, and EUF-CMA test three different attacker powers. Knowing exactly which game a paper's proof targets prevents overstating what that proof actually establishes.
References & further reading
- Regev — On Lattices, Learning with Errors... — §5, the foundational LWE-to-lattice reduction.
- FIPS 203 (ML-KEM) — §9, the ring ML-KEM actually uses.
- Boneh & Shoup — A Graduate Course in Applied Cryptography — §14, full formal security-game definitions.
- NIST SP 800-227 — §14, KEM security discussion.