HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Algorithm: Oblivious Linear Evaluation from Ring-LWE

8 min read

The client holds a public vector a, the server holds a secret vector s, and we need the client to learn the inner product ⟨a, s⟩ while the server learns nothing about a and the client learns nothing about s. This article builds that primitive — Oblivious Linear Evaluation — out of lattice encryption, and it is the computational core that every other piece of contact discovery sits on.

Prerequisites: Ring-LWE from Lattice Foundations, and the OPRF framing from The Lattice OPRF, which is what wants this inner product.

1. The exact task

From article 02, the PRF is a rounded inner product F_s(x) = Round(⟨a_x, s⟩). The client can compute a_x itself (it is a public hash of the phone number). The server holds s, the everlasting key: N = 512 small secret integers. We need a two-party protocol — Oblivious Linear Evaluation (OLE) — where:

  • Input, client: the public element a_x.
  • Input, server: the secret key s.
  • Output, client: ⟨a_x, s⟩ (the linear part; rounding is a separate step, article 08).
  • Privacy: the server learns nothing about a_x; the client learns nothing about s beyond the single output value.

"OLE" classically means evaluating a degree-1 function f(x) = a·x + b obliviously; ours is the vector/ring version, one big inner product. The tool that makes it possible is homomorphic encryption: encryption you can compute on without decrypting.

2. Homomorphic encryption in one section

Some encryption schemes let you do arithmetic on ciphertexts that "passes through" to the plaintext. If Enc(u) and Enc(v) are ciphertexts, a linearly homomorphic scheme lets anyone (without the key) compute:

Enc(u) ⊕ Enc(v)  →  Enc(u + v)          (add two ciphertexts)
c ⊙ Enc(u)       →  Enc(c · u)          (scale a ciphertext by a public constant c)

That is exactly the arithmetic an inner product needs: ⟨a, s⟩ = Σ aᵢ·sᵢ is scalings and additions. So if the client encrypts its inputs, the server can compute the inner product on the ciphertexts and hand back an encrypted answer that only the client can open. The server did real work on real data and never saw a plaintext.

The scheme we use is BFV (Brakerski–Fan–Vercauteren), a Ring-LWE-based homomorphic scheme. Its plaintexts and ciphertexts are elements of the evaluation ring — polynomials of degree M = 4096 with coefficients modulo Q = 2⁴² (from the table in Lattice Foundations). Two facts about BFV drive everything:

  • A ciphertext is a pair of ring elements (c₀, c₁). Decryption with secret key computes a combination of them and rounds away the noise.
  • It is noisy. Every ciphertext carries a small error term (that is the "LWE" in Ring-LWE — the error is what hides the plaintext). Homomorphic operations make the noise grow; as long as it stays below a threshold, decryption still rounds correctly.

For OLE we only need linear homomorphism (adds and public-constant scalings), which BFV supports cheaply and with modest noise growth. We do not need the far more expensive "multiply two ciphertexts together" capability, and deliberately avoid it.

3. Why an inner product is really a convolution

There is a structural subtlety that shapes the whole proof later, so it is worth seeing now.

The key s has N = 512 coefficients; the ciphertext ring has M = 4096. To multiply the client's ciphertext by s, we embed s into the big ring (zero-pad it up to degree M) and multiply. But multiplication in a polynomial ring is not coefficient-wise — it is convolution. Output coefficient i of c · s is a sum over all the ways degrees combine to i:

(c · s)_i  =  Σ_j  ± c_{i−j} · s_j

and because the ring wraps at degree M with a sign flip (Xᴹ = −1, the "negacyclic" property from article 01), some of those terms pick up a minus sign when the indices wrap around. So each output coefficient is a signed combination of many input coefficients. This is why the relation the server later has to prove is a dense "convolution" relation, and why articles 10 and 11 work so hard to make proving it cheap. Hold onto the picture: applying s = convolving with s in the big ring, with sign flips on the wrap.

4. The protocol, step by step

Here is the OLE, concretely, as round one of the OPRF.

Client (local).

  1. Compute a_x = HashToRing(phone) — public, no secret.
  2. Generate a fresh, single-use Ring-LWE / BFV keypair. Fresh matters: the key is used for exactly this one query, so nothing links two queries and nothing persists to leak.
  3. Encrypt a_x under that key, producing a ciphertext ct = (c₀, c₁). Send ct.

Server (on the ciphertext). 4. Homomorphically apply the secret key: compute reply = ct · ι(s), where ι(s) is the key zero-padded into the big ring. Concretely it scales and adds the ciphertext's ring elements to realize the convolution from §3. The output is a ciphertext of ⟨a_x, s⟩ (spread across the reply's coefficients). The server also folds in a fresh mask R — random noise it adds so that what the client eventually decrypts reveals only the intended output and not extra information about s. (This mask is also what the rounding step and the proof will have to account for.) 5. Return the reply ciphertext (and, in the verifiable version, the proof and the rounding-setup — articles 03 and 08).

Client (local). 6. Decrypt with its single-use key to recover the noisy inner product. The BFV plaintext modulus is 2¹⁶, and the scaling factor Δ = 2^(42−16) = 2²⁶ is what separates the message from the noise on decryption. What comes out is ⟨a_x, s⟩ plus small noise — ready to be rounded in round two.

Throughout, the server saw ct (an encryption it cannot open — Ring-LWE hiding) and produced reply (an encryption of a value it also cannot see, because it never had the client's single-use secret key). Neither party's secret crossed the wire.

5. Design choices, and the roads not taken

Why BFV and not "fully" homomorphic encryption? Schemes like CKKS or TFHE, or BFV with relinearization, can multiply two ciphertexts and evaluate arbitrary circuits. We deliberately stayed with linear-only homomorphism because (a) the inner product is linear, so ciphertext × ciphertext is a capability we would pay for and never use, (b) the noise growth of full multiplication is far larger, forcing bigger parameters and slower everything, and (c) — the decisive reason — the proof in article 09 has to certify the server's computation, and a purely linear relation is enormously easier to prove in zero-knowledge than a general circuit. Keeping the homomorphic evaluation linear is what keeps the verifiability tractable. This is a theme: we repeatedly chose the less capable primitive because it made the proof simpler.

Why a fresh key per query? We could have had the client hold one long-lived encryption key and reuse it. Reuse would let the server correlate queries (same key material across lookups) and would make a single key compromise catastrophic. A single-use key means each query is an island: nothing to correlate, nothing to persist. The cost is one keygen per lookup, which is cheap relative to the network round-trip.

Why not garbled circuits or generic MPC? You can compute any two-party function with garbled circuits or generic secure multiparty computation, inner products included. For a single big inner product, that is using a sledgehammer: garbling an N-input inner-product circuit means encrypting a gate for every bit operation and shipping it, which is far more data than one homomorphic multiply. We reached for the special-purpose primitive (linear homomorphism) that matches the special structure of the task (a linear function). Generic tools are the fallback when no structure exists; here the structure was the whole point.

6. Where the noise and the mask go next

Two loose ends leave this article deliberately open:

  • The decrypted result is noisy, and turning it into a clean, agreed-upon PRF value is the rounding problem — solved with oblivious transfer in Rounding by Oblivious Transfer (Route B).
  • The server's homomorphic step used a secret s and a mask R, and a malicious server could have used the wrong s. Proving it used the committed s — over the exact convolution relation of §3, accounting for the mod-Q wraps — is the NIZK, built on the Proof Ring.

The convolution structure from §3 is the thread connecting all three: it is what the server computes, what the client rounds, and what the proof certifies.

7. Summary

  • OLE lets the client learn ⟨a, s⟩ with the server holding s and neither side revealing its half. It is the computational heart of the OPRF (and, in a different costume, of the PIR).
  • It is built from linearly-homomorphic BFV encryption: the client encrypts, the server computes the inner product on the ciphertext, the client decrypts.
  • Applying s in the ring is a negacyclic convolution — a dense, sign-flipping combination of coefficients — which is the relation the later proof must certify.
  • We chose linear-only homomorphism and fresh per-query keys on purpose: less capability, less correlation, and — above all — a far simpler statement to prove in zero-knowledge.

References

  • J. Fan, F. Vercauteren, "Somewhat Practical Fully Homomorphic Encryption," ePrint 2012/144 — the BFV scheme.
  • Z. Brakerski, "Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP," CRYPTO 2012 — the "B" in BFV.
  • M. Naor, B. Pinkas, "Oblivious Transfer and Polynomial Evaluation," STOC 1999 — early oblivious linear/polynomial evaluation.
  • I. Damgård, et al., and the OLE-from-LWE line of work in modern MPC (e.g., "Overdrive," "Silent OT/VOLE") — OLE as an MPC building block.
  • Wikipedia: Homomorphic encryption, Ring learning with errors, Convolution.

Next: Algorithm: Post-Quantum Oblivious Transfer.