This is the vocabulary article. Every other piece of the discovery system stands on two problems introduced here: the OPRF (the keyed hash a server computes for you without ever seeing your input), the proof, the PIR (the database lookup that hides which row you asked for). Read it once, and the rest of the series stops looking like alphabet soup.
In Contact Discovery we committed to a hard rule: no elliptic curves, no RSA, nothing a quantum computer can break. That rule left us essentially one mathematical playground: lattices. This article explains what a lattice problem is, the two specific problems we build everything on, and why they are believed to be safe even against quantum computers. No prior cryptography assumed; if you can multiply matrices and take a remainder, you can follow this.
Take two arrows in the plane, say (2, 0) and (1, 3). A lattice is the infinite grid of all points you can reach by adding and subtracting whole-number copies of those arrows: (2, 0), (1, 3), (3, 3), (−1, 3), (4, 0), and so on. In two dimensions it looks like a slanted sheet of graph paper. The arrows are called a basis.
The magic is that a lattice has many bases that generate the exact same grid: some "nice" (short, nearly perpendicular arrows) and some "ugly" (long, nearly parallel arrows). And here is the computational asymmetry that all of lattice cryptography squeezes:
Given an ugly basis, it is easy to check whether a point is on the grid, but genuinely hard to find the grid point closest to some target, or to find a very short vector in the grid.
In two dimensions this is easy for anyone. In five hundred dimensions, with an adversarially ugly basis, the best known algorithms take exponential time (the work roughly doubles with each added dimension, so it explodes beyond reach), and crucially, that holds for quantum algorithms too. Wikipedia's entries on the Shortest Vector Problem and Closest Vector Problem are the formal versions. This is the whole game: short vectors in high-dimensional lattices are hard to find, and nobody, quantum or not, knows a shortcut.
Contrast that with the discrete logarithm: the problem of undoing repeated multiplication, and the foundation of elliptic-curve crypto. Discrete log does have a quantum shortcut. The reason is structural: the problem lives in a cyclic group (a number system you can walk through end to end by repeating one step), so it has a hidden periodicity, and detecting hidden periodicity is the one thing a quantum computer is spectacularly good at. That is Shor's algorithm.
Lattices offer no such periodicity to detect. After decades of people trying, that is still true, which is why they remain the best-understood post-quantum foundation we have.
The standards bodies agree. In 2024 NIST (the US National Institute of Standards and Technology, which sets the cryptographic standards most of the industry follows) standardized lattice schemes as the primary post-quantum algorithms: ML-KEM for agreeing a shared secret over an open wire (KEM is short for key-encapsulation mechanism), and ML-DSA for digital signatures. We are standing on the same rock.
Fix a wide, random matrix A with entries taken modulo some number q: every value wraps around at q, like clock arithmetic. Say A has κ rows and n columns, with n much bigger than κ. The Short Integer Solution problem asks:
Find a short, nonzero integer vector z such that
A·z ≡ 0 (mod q).
Because A is wide, there are many vectors z with A·z ≡ 0: the equation is
underdetermined, with more unknowns than constraints. Finding some solution is trivial linear algebra. The catch is the word
short: we insist z has small entries. Finding a short solution turns out to be as
hard as finding short vectors in a lattice, and that is the hard problem from §1.
Why do we care? Because SIS gives us a binding commitment: a way to seal a value so
that you cannot later claim you sealed something else. Define Com(x) = A·x
for a short x.
Watch what binding costs an attacker. Suppose they could open one commitment two ways:
find two different short values x and x′ with A·x = A·x′. Subtract one
from the other. Now z = x − x′ is short, it is not zero, and A·z ≡ 0. That
is a solution to SIS.
So the attacker cannot have both. Either commitments are binding, or short lattice vectors are easy to find, and we spent §1 establishing that they are not.
This chain is what makes our zero-knowledge proofs trustworthy. A zero-knowledge proof convinces you a statement is true while revealing nothing else about it, which sounds like it should be impossible to hold anyone to. But an attacker who could forge one of ours could be mechanically turned into an SIS-solver, and SIS-solvers are not supposed to exist.
That proof system rests on Module-SIS, the structured variant of §4, and follows the Greyhound/LaBRADOR line of lattice proof systems. We build it in Algorithm: The NIZK. NIZK stands for non-interactive zero-knowledge: the prover convinces the verifier with a single message, no back-and-forth, and the message reveals nothing beyond the truth of the statement.
The intuition to keep: SIS is what makes "you can't cheat" true. It is a soundness assumption (false statements cannot be proven) and a binding assumption (sealed values cannot be swapped).
Now the encryption side. Fix a secret vector s (also mod q). Regev's Learning With Errors problem, from 2005, is this. You are handed many equations of the form
b_i = ⟨a_i, s⟩ + e_i (mod q)
where each ai is a public random vector, ⟨a_i, s⟩ is the inner product
(multiply the two vectors entry by entry, then sum), and each ei is a small random error:
a little bit of noise. Your job: recover s.
Without the noise, this is a linear system; you would solve it with Gaussian elimination in a heartbeat. The noise ei is what ruins Gaussian elimination (errors compound catastrophically as you combine equations) and turns recovering s into, once again, a hard lattice problem. (The samples (ai, bi) are lattice points nudged slightly off the grid; recovering s means finding the nearest grid point, the Closest Vector Problem.)
Where SIS gives us binding, LWE gives us encryption that hides. To encrypt a message, you bury it inside a fresh LWE sample:
b = ⟨a, s⟩ + e + message
Whether you can read it back depends entirely on whether you hold s. If you do, subtract
⟨a, s⟩; the small error e rounds away and the message falls out. If you
do not, all you have is b, and by the LWE assumption, b is computationally
indistinguishable from uniform random noise: no realistic algorithm can tell the
difference.
This is the primitive behind our Oblivious Linear Evaluation, where the client encrypts its query so the server can compute on it without ever decrypting it.
The intuition to keep: LWE is what makes "the server can't see your data" true. It is a hiding and secrecy assumption. Notice the two problems are two sides of the same coin (SIS keeps you honest, LWE keeps you blind), and both are "short vectors in a lattice" in disguise.
Plain LWE and SIS have a practical problem: A is a big dense matrix, so keys and ciphertexts, the encrypted blobs themselves, are huge (megabytes), and every operation is a full matrix multiply. The fix, which every deployed lattice scheme uses, is to give the matrix structure so it can be stored and multiplied cheaply, without (we believe) making the underlying problem easier.
The structure is polynomial rings. Instead of vectors of numbers, we work with
polynomials, reduced modulo Xᴰ + 1 and modulo q:
R_q = ℤ_q[X] / (Xᴰ + 1)
An element of Rq is a polynomial with D coefficients, each between 0 and q−1. You add
them coefficient-wise. You multiply them like polynomials, then reduce: whenever X
reaches degree D, it wraps around with a sign flip (Xᴰ = −1). This "negacyclic" wrap
is why you will see minus signs appear in convolution formulas (the multiply-and-add
patterns that polynomial multiplication expands into) throughout the series.
The conservative choice would have been plain, unstructured LWE and SIS everywhere. No ring structure means one fewer thing an attacker might exploit, and we considered it.
Two things decided against it. Unstructured lattices would make our ciphertexts and proofs roughly an order of magnitude larger and slower, which is disqualifying for a feature that has to feel instant on a phone. And a decade of cryptanalysis (of researchers actively trying to break it) has not found a way to turn the ring structure into an attack at the parameter sizes standards bodies now endorse.
It is the same bet NIST made.
The series uses two different rings, and confusing them is the single most common way to get lost, so pin them down now:
| The evaluation ring | The proof ring | |
|---|---|---|
| Where | The OPRF / OLE (OLE from Ring-LWE) | The NIZK (The Proof Ring) |
| Degree D | 4096 | 64 |
| Modulus q | 2⁴² (a BFV encryption modulus; BFV is the lattice scheme that lets a server compute on ciphertexts) | product of three ~2³² primes ≈ 2⁹⁴·⁶ |
| Job | Hold encrypted queries and compute on them | Represent exact integers so a proof never "wraps" |
| Rests on | Ring-LWE (hiding) | Module-SIS (binding) |
They have different sizes for different reasons, spelled out in their own articles. When a later article says "the ring," check which one it means.
A fair question from a skeptical sophomore: "You keep saying 'believed hard.' Believed by whom, and why should I believe it too?" Three honest reasons.
No structure for Shor to exploit. Shor's algorithm breaks discrete-log and factoring because those problems hide a periodicity that a quantum Fourier transform uncovers. The hardness of short lattice vectors does not come from periodicity; it comes from high-dimensional geometry. Forty years of trying has not produced a quantum lattice shortcut better than a modest polynomial speedup (Grover-style: the generic quantum search trick, which merely shaves the exponent), and we absorb that just by picking slightly larger parameters.
Worst-case to average-case reductions. This is the crown jewel, due to Ajtai (1996) and Regev (2005). For most cryptographic problems, "random instances are hard" is a hope. For SIS and LWE it is a theorem: breaking a random instance on average is provably as hard as solving the worst possible lattice instance. You cannot get unlucky and pick a secretly-easy key.
We do not just trust the theory. We measured it. The security of a specific parameter choice is estimated with the community's lattice estimator. That tool models the cost of the best known attacks: BKZ lattice reduction and friends, the algorithms that grind an ugly basis toward a short vector, and the reason "hard" has a price tag at all. Our evaluation and proof parameters were run through it and cleared comfortable post-quantum security margins. This is why the evaluation ring's degree and the PIR dimension are the specific unlovely numbers they are rather than round ones: they are the smallest values that still buy the security target.
The proof ring's primes are ugly for a different reason, and it is worth separating. They are
not the output of a minimality search. Each prime is pinned so that the polynomial X⁶⁴ + 1
only partially factors ("splits") modulo that prime. That partial splitting is what
guarantees the difference of any two short challenge values can be inverted (divided out)
inside the ring, a step the soundness argument depends on. A prime that
made the ring split completely would break that argument no matter how comfortable
its security margin looked; a rounder number is simply not available.
None of this is a proof that lattices are unbreakable; no useful cryptography has that. It is the strongest available combination of structural resistance, provable worst-case hardness, and measured concrete security, which is exactly why it is what the world is standardizing on.
Four sentences to remember:
A·z ≡ 0) = the reason nobody can cheat a commitment or forge a
proof. It powers the NIZK's binding.With that vocabulary, The Lattice OPRF is next: how to turn "a noisy inner product a server can compute blind" into an actual keyed pseudorandom function two strangers can agree on.