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⟩ (multiply the two vectors entry by entry, then add
the results) while the server learns nothing
about a and the client learns nothing about s. This article builds that primitive (a
cryptographic building block),
Oblivious Linear Evaluation, out of lattice encryption. 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 (an OPRF is an oblivious pseudorandom function, a keyed hash the server computes for you without ever seeing your input), which is what wants this inner product.
From The Lattice OPRF, the PRF (a pseudorandom function, the
keyed hash at the heart of discovery) is a rounded inner product:
F_s(x) = Round(⟨a_x, s⟩).
The client can compute ax on its own, since it is just a public hash of the phone number. The server holds s, the everlasting key: N = 512 small secret integers. What we need between them is a two-party protocol called Oblivious Linear Evaluation, or OLE.
⟨a_x, s⟩, the linear part only. Rounding is a separate
step, Rounding by Oblivious Transfer.Classically, "OLE" means obliviously evaluating a degree-1 function f(x) = a·x + b.
Ours is the vector version, carried out in a polynomial ring (a number system whose elements
are polynomials, where adding and multiplying stay inside the system): one big inner product.
The tool that makes it possible is homomorphic encryption: encryption you can compute on without decrypting.
Some encryption schemes let you do arithmetic on ciphertexts that "passes through" to the
plaintext underneath. If Enc(u) and Enc(v) are ciphertexts, a linearly homomorphic
scheme lets anyone (without holding 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⟩ is a sum of
products a_i·s_i: nothing but 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 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 = 242, from the parameter table in Lattice Foundations.
Two facts about BFV drive everything that follows.
(c_0, c_1). Decrypting computes a combination
of the two with the secret key and rounds the noise away.For OLE we need only linear homomorphism: adds, and scalings by public constants. BFV supports both cheaply and with modest noise growth.
We do not need the far more expensive ability to multiply two ciphertexts together, and we deliberately avoid it.
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 (pad it with zeros up to degree M) and multiply.
But multiplication in a polynomial ring is not coefficient-wise. It is convolution:
every coefficient of one polynomial meets every coefficient of the other, and the products
that land on the same degree pile up.
Output coefficient i of c·s is a sum over every way two degrees can combine to make
i:
(c·s)_i = Σ_j ± c_(i−j) · s_j
The ± is there because the ring wraps at degree M with a sign flip. That is the
negacyclic property, X^M = −1, from
Lattice Foundations: terms whose indices wrap around come back
negated.
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 The Proof Ring and OLE Packed work so hard to make proving it cheap.
Hold onto the picture: applying s means convolving with s in the big ring, with sign flips on the wrap.
Here is the OLE, concretely, as round one of the OPRF.
Client (local).
a_x = HashToRing(phone). Public, no secret.ct = (c_0, c_1), and send it.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, the server scales and adds the
ciphertext's ring elements to realize the convolution from §3, and the output is a
ciphertext of ⟨a_x, s⟩ spread across the reply's coefficients.
5. Fold in a fresh mask R: random noise added so that what the client eventually
decrypts reveals only the intended output, and nothing extra about s. The rounding step
and the proof both have to account for this mask later.
6. Return the reply ciphertext; in the verifiable version, also the proof and the
rounding setup (Trust, but Verify and
Rounding by Oblivious Transfer).
Client (local). 7. Decrypt with the single-use key to recover the noisy inner product.
The decryption step has one detail worth unpacking. The BFV plaintext modulus (the size of
the space messages live in) is 216, and
the scaling factor Δ = 2^(42−16) = 2^26 is what separates message from noise. The
plaintext gets multiplied up by Δ before encryption, so it sits in the high bits and
leaves the low bits free for the error to grow into.
And what comes out is not the inner product. The server added that fresh uniform mask R
(uniform meaning indistinguishable from pure randomness)
across the whole ring before replying. So the client decrypts a random-looking share u
while the server keeps R, with u − R = a_x·s.
The value ends the round additively shared: split into two pieces, one per side, each meaningless alone, that add up to the true value. That is precisely why round two's rounding has to be oblivious: neither side can round a value that neither side holds.
Throughout, the server saw ct, an encryption it cannot open (Ring-LWE hiding guarantees
that) 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.
Why BFV and not "fully" homomorphic encryption?
Sibling lattice schemes like CKKS and TFHE (same shape, more capability) and BFV with relinearization can multiply two ciphertexts and evaluate arbitrary circuits. (Relinearization is the repair step that shrinks the oversized ciphertext a ciphertext-times-ciphertext multiply leaves behind.)
We deliberately stayed with linear-only homomorphism, for three reasons.
The inner product is linear, so ciphertext-times-ciphertext is a capability we would pay for and never use. The noise growth of full multiplication is far larger, which forces bigger parameters and makes everything slower.
And the decisive one: the proof has to certify the server's computation, and a purely linear relation is enormously easier to prove in zero-knowledge (convincing a verifier that a computation was done correctly without revealing the secrets inside it) than a general circuit. Keeping the homomorphic evaluation linear is what keeps The NIZK (the non-interactive zero-knowledge proof, a certificate anyone can check without a conversation) tractable.
This is a recurring theme in the series. 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 by their shared key material, and it would make a single key compromise catastrophic.
A single-use key makes each query an island: nothing to correlate, nothing to persist. The cost is one key generation per lookup, which is cheap next to the network round-trip.
Why not garbled circuits or generic MPC?
You can compute any two-party function with garbled circuits (a technique that encrypts a computation gate by gate so two parties can run it without seeing each other's inputs) or with generic secure multiparty computation (MPC), inner products included. For a single big inner product, that is a sledgehammer. Garbling an N-input inner-product circuit means encrypting a gate for every bit operation and shipping the lot, which is far more data than one homomorphic multiply.
We reached instead for the special-purpose primitive (linear homomorphism) that matches the special structure of the task, which is a linear function. Generic tools are the fallback when no structure exists. Here the structure was the whole point.
Two loose ends leave this article deliberately open:
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.
⟨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 (private information retrieval: fetching
a record without the server learning which one).