HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Bulk Membership: Private Information Retrieval

8 min read

Alice can now compute her contacts' identifiers privately and correctly. She still has to look them up in a directory — and the act of looking something up is itself a leak. This article is about the last mile: checking whether an identifier is registered without telling the server which identifier you asked about.

Prerequisites: Contact Discovery for the framing, and Lattice Foundations for LWE. The Lattice OPRF produced the presence_ids we are now looking up.

1. The leak nobody expects

The OPRF was a lot of work to make sure the server never sees a phone number. Here is the deflating part: if Alice now turns around and asks the server "is presence_id = 0x9f3c… in the directory?", she has handed the server a presence_id. Do that for all 800 contacts and the server has Alice's entire contact set — as a list of pseudonyms, but that list is the social graph we spent the whole system protecting. A pseudonymous social graph is still a social graph.

It is worth naming why this is easy to miss. The OPRF protects the derivation of the identifier. Membership checking is a different operation, and its privacy is a different problem. A system can be flawless at the first and wide open at the second. The general lesson, again: privacy is a property of the whole pipeline, not of its most impressive component.

So the requirement for the lookup is: Alice learns which of her presence_ids are in the directory, and the server learns nothing about which IDs she asked about — not the IDs, not which matched, ideally not even how many.

2. The tempting non-solutions

Two designs look like they solve this and do not.

"Just download the whole directory." If Alice downloads every registered presence_id and checks locally, the server learns nothing about her queries — perfect privacy. But a directory of millions of users is tens or hundreds of megabytes, it grows forever, and it would have to be re-downloaded to stay fresh. It also leaks the entire member set to every user, which is its own privacy problem (now anyone can enumerate who is registered). For a phone doing this on cellular data, it is a non-starter. We could have shipped a compressed Bloom filter of the directory to shrink the download — and Bloom filters are lovely — but they still leak the whole membership set, still grow with the user base, and introduce false-positive matches that would make Alice think a stranger is a contact. So "download it all" was out.

"Two non-colluding servers." A classic and very efficient family of PIR schemes (going back to Chor–Goldreich–Kushilevitz–Sudan, 1995) splits the database across two servers that are assumed not to talk to each other, and gets information-theoretic privacy almost for free. This is genuinely great when you can arrange it. We chose not to depend on it because "two servers that never collude" is an operational assumption, not a mathematical one — in practice both servers are often run by the same organization or in the same cloud, and the security evaporates the moment they compare notes. We wanted the privacy to come from a hardness assumption we could point at, not from an org chart.

That leaves single-server, computational PIR, where the math stops one server from learning the query.

3. What PIR is, and the one-line intuition

Private Information Retrieval is a protocol where a client fetches item i from a server's database and the server does not learn i. The single-server version sounds impossible — how can the server return row i without knowing i? — and the resolution is beautifully simple once you see it.

Model the database as a vector of records D = (D_0, D_1, …, D_{m-1}). To fetch record i, the client conceptually wants the selector vector e_i = (0, …, 0, 1, 0, …, 0) with a 1 in position i, because the dot product ⟨e_i, D⟩ = D_i picks out exactly the row it wants. If the client could compute that dot product without revealing e_i, it would get D_i and the server would learn nothing.

But we already know how to compute a dot product on hidden inputs — that is what lattice encryption gives us. The client encrypts the selector vector e_i and sends the ciphertexts. The server, using the homomorphic property (add and scalar-multiply under encryption), computes ⟨Enc(e_i), D⟩ on the ciphertexts — a big weighted sum of its records — and returns one encrypted result. To the server, Enc(e_i) is a vector of LWE ciphertexts, each indistinguishable from random noise; it cannot tell the 1 from the 0s, so it cannot tell which record it just returned. The client decrypts and gets D_i.

That is the whole idea: PIR is a homomorphic dot product against a selector you keep encrypted. It is the same LWE trick as the OLE from article 02, pointed at a different job. And it is post-quantum for the same reason: the query is an LWE ciphertext, and inverting it is a hard lattice problem, so a "harvest-now" adversary who records the query learns nothing even after quantum computers exist.

4. FrodoPIR: paying for privacy with a one-time hint

The naive scheme above has the server do a full pass over the entire database for every query — expensive if the database is large and queries are frequent. The scheme we use, FrodoPIR (Davidson–Pestana–Celi, 2023), makes this practical with a stateful, preprocessing trick, and the trick is worth understanding because it shows how PIR gets fast.

The database is thought of as a matrix. Ahead of time, the server publishes a hint — a one-time, query-independent digest of the database (concretely, the database multiplied by a public random matrix). The client downloads this hint once and caches it. Now, at query time:

  • The client's query is a single LWE-encrypted selector, small and cheap.
  • The server's per-query work is a single fast matrix–vector product, not a from-scratch pass.
  • The client combines the server's small answer with the cached hint to recover its record, and the hint is exactly what lets it cancel out the LWE noise and the server's masking.

The name "Frodo" is a nod to the FrodoKEM family — it uses plain (unstructured) LWE, not Ring-LWE. That is a deliberate conservatism: for the PIR layer we were willing to trade some speed for the most cautious possible lattice assumption, since a membership query leaks less structure to begin with. We sized the LWE dimension (n = 1728) so the scheme clears the strict quantum core-SVP ≥128 bar under the community lattice estimator, the same tool from article 01 — roughly 135.7-bit quantum and 149.5-bit classical. Smaller dimensions we tried cleared only classical security: n = 1536 came in at about 116-bit quantum and n = 1024 at only ~74, and for a "private forever" system classical-only was not good enough, so we paid for the larger n.

The cost model, made explicit: PIR moves the expense to a one-time hint download (tens of MB, cached and refreshed lazily) in exchange for cheap, private, per-query lookups. "Refreshed lazily" is a conditional request: the client keeps its cached hint and revalidates against the server's content ETag, so an unchanged directory answers with a tiny 304 Not Modified and the re-scan pays nothing for the hint — it re-downloads only when the directory has actually changed. For contact discovery — where a user syncs a big address book occasionally, then does light lookups — that trade is exactly right.

5. From "is it there?" to "give me the mailbox"

A membership bit ("yes, this presence_id is registered") is only half of what discovery needs. Once Alice knows Bob is reachable, she needs Bob's actual discovery mailbox — the sealed inbox she'll use to start a conversation — and fetching that leaks which member she matched just as badly as the membership query did.

So the system runs PIR twice, in two tiers:

  1. Membership PIR answers "is this presence_id registered?" privately, using a compact membership structure so the per-query cost stays tiny even for a large directory.
  2. Record PIR then privately fetches the matched user's record — their mailbox address and the key material needed to reach them — without revealing which record was pulled.

Both tiers are the same underlying FrodoPIR machinery aimed at different tables. The result: Alice goes from a phone number all the way to "here is Bob's sealed mailbox and how to encrypt to it," and at no point did the server learn the number, the identifier, the match, or the mailbox it just handed over.

6. What PIR does not do (and who does it)

PIR hides which row Alice reads. It does not, by itself, stop Alice from reading many rows to enumerate the directory, and it does not authenticate who put a row there. Those are abuse and integrity problems, handled by rate limits and directory authentication in Guarding the Directory.

It also assumes the presence_ids Alice is looking up were computed honestly — which is the job of the Verifiable OPRF. PIR is the blind-lookup leg of the tripod; it is only private in a system where the other two legs also hold.

7. Summary

  • Looking up an identifier leaks the identifier; a pseudonymous social graph is still the social graph. Membership privacy is a separate problem from OPRF privacy.
  • "Download the whole directory" and "trust two non-colluding servers" both fail — the first on bandwidth and member-set leakage, the second on an operational non-collusion assumption we refused to depend on.
  • Single-server PIR solves it by making the query a homomorphic dot product against an encrypted selector, so the server computes the answer without learning the index. It is post-quantum because the query is an LWE ciphertext.
  • FrodoPIR makes it fast with a one-time cached hint and plain (conservative) LWE, sized for a real post-quantum margin.
  • Discovery runs PIR in two tiers — membership, then record — so Alice reaches Bob's mailbox without the server learning anything about the lookup.

References

  • B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan, "Private Information Retrieval," FOCS 1995 — the origin of PIR and the multi-server schemes we chose not to depend on.
  • E. Kushilevitz, R. Ostrovsky, "Replication is Not Needed: Single Database, Computationally-Private Information Retrieval," FOCS 1997 — single-server PIR.
  • A. Davidson, G. Pestana, S. Celi, "FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval," PoPETs 2023 — the scheme we use.
  • Wikipedia: Private information retrieval, Homomorphic encryption, Bloom filter.

Next: Guarding the Directory: Enumeration, Sybils, and Poisoning.