HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Lattice Foundations: SIS, LWE, and Post-Quantum Trust

9 min read

This is the vocabulary article. Every other piece of the discovery system — the OPRF, the proof, the PIR — stands on two problems introduced here. 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.

1. What is a lattice, informally

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 — and crucially, including quantum algorithms. 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 this with the discrete logarithm, the foundation of elliptic-curve crypto. Discrete log has a quantum shortcut — Shor's algorithm — because the underlying structure (a cyclic group) has a hidden periodicity a quantum computer can detect. Lattices do not have that kind of exploitable periodic structure, which is why, after decades of attack, they remain our best-understood post-quantum foundation. In 2024 the US standards body NIST standardized lattice schemes (ML-KEM, ML-DSA) as the primary post-quantum algorithms. We are standing on the same rock.

2. Problem one: SIS (Short Integer Solution)

Fix a wide, random matrix A with entries taken modulo some number q — 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. 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 commitment / hash that is binding. Define Com(x) = A·x for a short x. If an adversary could open the same commitment two ways — find x ≠ x', both short, with A·x = A·x' — then z = x - x' is a short nonzero solution to A·z ≡ 0, i.e., they just solved SIS. So "you cannot open a commitment two ways" reduces to "you cannot solve SIS," which reduces to "you cannot find short lattice vectors." This chain is exactly why our zero-knowledge proofs are trustworthy: an attacker who could forge a proof could be turned into an SIS-solver, and SIS-solvers are not supposed to exist. The proof system (Greyhound/LaBRADOR-style, see Algorithm: The NIZK) is built on Module-SIS, a structured version we describe in §4.

The intuition to keep: SIS is what makes "you can't cheat" true. It is a soundness and binding assumption.

3. Problem two: LWE (Learning With Errors)

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 a_i is a public random vector, and each e_i 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 e_i 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 (a_i, b_i) are lattice points nudged slightly off the grid; recovering s means finding the nearest grid point, the Closest Vector Problem.)

LWE gives us encryption that hides. To encrypt a message, you bury it in a fresh LWE sample: b = ⟨a, s⟩ + e + (message-scaled-up). Anyone who knows s can subtract ⟨a, s⟩, and the small error e rounds away, revealing the message. Anyone who does not know s sees b, which is computationally indistinguishable from uniform random noise — that is the LWE assumption. This is the primitive behind our Oblivious Linear Evaluation: the client LWE-encrypts its query so the server can compute on it without 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 duals of the same coin — SIS keeps you honest, LWE keeps you blind — and both are "short vectors in a lattice" in disguise.

4. Making it fast: rings and modules

Plain LWE and SIS have a practical problem: A is a big dense matrix, so keys and ciphertexts 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 modulo Xᴰ + 1 and modulo q:

R_q  =  ℤ_q[X] / (Xᴰ + 1)

An element of R_q is a polynomial with D coefficients, each in {0, …, 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 throughout the series.

  • Ring-LWE / Ring-SIS: the same problems, but s, a, e are now single ring elements (polynomials) instead of long vectors. One polynomial multiply replaces a whole matrix–vector product.
  • Module-LWE / Module-SIS: the middle ground we actually use — small vectors of ring elements. It is a dial between "big and conservative" (plain LWE) and "small and structured" (Ring-LWE), letting us pick a security level without going to either extreme. ML-KEM and ML-DSA — the NIST standards — are Module-LWE/SIS schemes; the "M" is for Module.

We could have used plain, unstructured LWE/SIS everywhere for maximum conservatism — no ring structure means one fewer thing an attacker might exploit. We chose module/ring versions because unstructured lattices would make our ciphertexts and proofs an order of magnitude larger and slower, which for a feature that must feel instant on a phone was a non-starter — and because a decade of cryptanalysis has not found a way to turn the ring structure into an attack for the parameter regimes standards bodies now endorse. It is the same bet NIST made.

The two rings you will meet

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 (article 06) The NIZK (article 10)
Degree D 4096 64
Modulus q 2⁴² (a BFV encryption modulus) product of three ~2³² primes ≈ 2⁹⁴·⁶
Job Hold encrypted queries and compute on them Represent exact integers so a proof never "wraps"
Rests on Module-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.

5. Why we trust this against quantum computers

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.

  1. 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), which we absorb just by picking slightly larger parameters.

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

  3. 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, which models the cost of the best known attacks (BKZ lattice reduction and friends). Our evaluation and proof parameters were run through it and cleared comfortable post-quantum security margins. This is why the primes and degrees in the table above are the specific ugly numbers they are, rather than round ones — they are the smallest values that still buy the security target.

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.

6. What to carry into the rest of the series

Four sentences to remember:

  • Lattice problems = find short vectors in a high-dimensional grid; hard even for quantum computers because there is no periodicity to exploit.
  • LWE (noisy inner products) = the reason the server can compute on your data without seeing it. It powers the encryption and the OLE.
  • SIS (short kernel vectors) = the reason nobody can cheat a commitment or forge a proof. It powers the NIZK's binding.
  • Rings and modules are just LWE/SIS with structure bolted on to make everything small and fast; we pay for that with a slightly larger parameter, not a weaker assumption.

With that vocabulary, the 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.

References

  • M. Ajtai, "Generating Hard Instances of Lattice Problems," STOC 1996 — the worst-case to average-case reduction for SIS.
  • O. Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography," STOC 2005 / J. ACM 2009 — the definition and hardness of LWE.
  • V. Lyubashevsky, C. Peikert, O. Regev, "On Ideal Lattices and Learning with Errors over Rings," EUROCRYPT 2010 — Ring-LWE.
  • A. Langlois, D. Stehlé, "Worst-Case to Average-Case Reductions for Module Lattices," 2015 — Module-LWE/SIS, the setting we use.
  • NIST, FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA), 2024 — the standardized module-lattice schemes.
  • Wikipedia: Lattice-based cryptography, Learning with errors, Short integer solution problem, Ring learning with errors.

Next: The Lattice OPRF: Deriving presence_id.