Contact Discovery

Guarding the Directory: Enumeration, Sybils, and Poisoning

10 min read

The cryptography in the rest of this series defends against adversaries who attack the math. This article is about the adversary who attacks the interface — by using the system exactly as designed, only too much, or dishonestly, or with numbers they do not own. None of the fancy lattice machinery helps here, and pretending otherwise is how privacy systems get quietly defeated at their most boring seam.

Prerequisites: Contact Discovery. Familiarity with the Verifiable OPRF and PIR helps but isn't required.

1. The oracle we built on purpose

Look at what the OPRF is, from the outside: a public endpoint that, given a phone number, returns its presence_id. That is not an accident — it is the whole point. Alice must be able to compute presence_ids for numbers she does not own, namely her contacts', or discovery could not work at all. The service is, by design, a machine that turns numbers into identifiers for anyone who asks.

An endpoint that computes a function on inputs you don't control is what cryptographers call an oracle, and oracles get abused in three characteristic ways. Crucially, all three are protocol-compliant — the attacker follows every rule; the cryptography sees nothing wrong.

Enumeration. Feed the oracle every possible phone number and harvest the full map of number → presence_id under the server's key. This would undo the entire point of the keyed OPRF: the key exists precisely to stop precomputation, and an attacker who can query freely just precomputes through the oracle instead.
Sybil listing. Register thousands of fake identities to crowd the directory, or to claim presence_ids for numbers you don't control so you can watch who looks them up.
Poisoning. Publish a directory entry mapping someone else's presence_id to your mailbox, so that people trying to reach them reach you instead — a discovery-layer person-in-the-middle.

Notice these are not cryptographic breaks. They are misuse. The defenses are correspondingly more classical — rate limits, proof-of-control, and authentication — and they are just as essential as the lattices. A system is only as private as its least-defended interface.

2. Enumeration: making the oracle expensive

You cannot forbid a caller from asking about a number they don't own — that ability is the feature. What you can do is make asking about all ten billion numbers prohibitively slow.

The defense is unglamorous and effective: rate limiting. Every call to the oblivious-eval endpoint is metered — per client, per network origin, and globally per unit time — against a sliding window, so a single actor cannot pump the oracle fast enough to sweep the number space in any reasonable time. A user syncing an 800-entry address book fits comfortably under the cap; an enumerator trying to grind ten billion numbers hits a wall.

One design decision here is worth calling out because it runs against a common instinct: the limiter fails closed. If the rate-limiting subsystem itself is unavailable, the endpoint denies rather than allows. The tempting alternative — fail open, so the feature keeps working during an outage — is a classic self-own: an attacker who can knock the limiter offline would get an unmetered enumeration oracle exactly when they want one. We chose to let discovery degrade rather than let the oracle run wild. (Early on this was the reverse; the enumeration threat model is what flipped it.)

We could have leaned harder on making the OPRF itself slow — a deliberately expensive PRF raises the per-query cost for everyone, attacker and honest user alike. But punishing every honest lookup to slow an attacker is a bad trade, and it interacts badly with the "must feel instant" requirement. Rate limiting targets the abuse pattern (too many queries) rather than the operation (one query), which is the right place to put the cost.

3. Custody of `s`: surviving a server breach

Every defense so far assumes the attacker is outside, poking the public endpoint. Now flip to the worst realistic case: an adversary who breaches the server itself and becomes a silent observer — reading process memory, the database, the logs, the wire. What do they learn? Almost nothing, and that is the whole payoff of the cryptography in this series. The query traffic is Ring-LWE ciphertexts sealed under each client's ephemeral key, which the server never held, so not a single lookup decrypts. The PIR queries are the same — encrypted selectors they cannot invert. The directory at rest is a table of opaque presence_ids, keyed-hash outputs that mean nothing without the key. A hacked-in observer sees a pile of noise and a pile of pseudonyms and can attach neither to a person.

There is exactly one thing on that server worth stealing: the everlasting key s (from The Verifiable OPRF). It is the master secret that turns a presence_id back into a phone number by brute force — with s, the equation presence_id = Hash(F_s(phone)) becomes computable offline across the whole ten-billion number space, so an intruder holding s and a directory dump could reverse the membership set (which numbers are registered). So "does a server breach leak anything useful?" collapses to a single question: can the intruder get s? Two facts bound the damage even if they do, and they are worth stating plainly: a stolen s is a forward enumeration capability, not a time machine — it does not retroactively decrypt any recorded query, and it does not reveal who looked up whom (PIR never exposed the lookups). The worst case is "the directory becomes phone-queryable," which reverts discovery to a keyed-hash-without-the-key: bad, bounded, not a collapse.

Baseline custody is the obvious hygiene — s lives in a KMS/HSM, loaded fail-closed at boot, kept off the database, its evaluation rate-limited (§2). But that leaves a real gap: to evaluate the OPRF, the honest server must hold s in process memory, and a memory-reading intruder can scrape it from there. We could shrug and file "don't let your RAM get read" under someone else's problem — but the entire ambition of the design is to make a breach boring, so we close it the same way the system closes the compelled-operator threat elsewhere: run the evaluator inside an attested enclave (TEE). Sealed in the enclave, s is non-exportable — provisioned to enclave-sealed storage, never in plaintext process memory — so a total server compromise yields the same nothing as a partial one. This attested-enclave custody is defense-in-depth we treat as the destination, not a prerequisite: the lattice OPRF's guarantees hold wherever s sits, and the enclave is simply what makes the claim literal — hack in, observe everything, learn nothing useful.

4. Sybils: proof that you control the number

The second abuse is fake identities. The defense is a Sybil gate: before a number can be listed in the directory as reachable, whoever is registering it must prove they actually control that phone number.

Proving control of a phone is done the mundane way — an SMS one-time code, verified through a gateway — but wrapped so that the server issuing the credential does not get to build a phone → account link out of it. The verification service checks the code and then issues a verified-phone token the client can later present, blindly, to prove "some real, SMS-verified human stands behind this listing" without the token being traceable back to the verification event. This unlinkability is itself an oblivious-pseudorandom-function-style blind-signature dance.

Here is a place to be scrupulously honest about the post-quantum boundary, because it is exactly the kind of detail that gets glossed. For a while the Sybil-gate token was the one classical holdout — a verified-phone credential built on a classical (elliptic-curve) blind signature while the rest of discovery was already lattice. That was a deliberate, clearly-bounded exception: the token is an upstream, one-time registration credential whose secret is anti-abuse, not social-graph linkage, and it is not part of the contact-discovery lookup, so a future quantum forgery would only have let someone register a fake listing, never decrypt anyone's contacts. We named that boundary rather than gloss it.

We have since closed it. The verified-phone token — and its companion rate-limit / admission token — was migrated onto the same lattice oblivious OPRF the lookup uses (with its own issuer key), and the classical blind-signature code was deleted outright. So there is now no classical cryptography anywhere in the discovery or the listing path: both the lookup (number → presence_id → blind PIR) and the Sybil gate are post-quantum end to end, and a 2035 adversary can no more forge a listing credential than it can decrypt discovery traffic.

That migration moved two properties, not one, and it is worth naming both. Unforgeability went from a discrete log a quantum computer breaks to a lattice problem it does not — the win we were after. But the old blinding was a one-time pad, which made unlinkability unconditional, and the lattice version hides the client's input under Ring-LWE instead, which makes it computational. A quantum computer still cannot link a token to its issuance; an adversary with unbounded computation could. Anonymous Admission works through that trade in full.

One internal detail reinforces this at rest: the directory and the issuance ledger are keyed by the lattice presence_id, never by any phone-derived value the server could invert — so even the listing ledger holds only the post-quantum identifier, and a full dump reveals nothing about which numbers it corresponds to.

5. Poisoning: authenticating who publishes

The third abuse is claiming someone else's slot. Defense: a directory entry can only be published by someone holding a phone-ownership certificate for that presence_id, and the publish endpoint refuses entries without a valid one. The certificate is minted by the verification service (§4) when you prove control of your number, and it cryptographically binds this presence_id to your right to publish under it. No cert, no entry; someone else's cert, wrong presence_id, rejected.

The ownership certificate's signature is a hybrid: a classical Ed25519 signature and a post-quantum ML-DSA (Dilithium) signature, both required. The hybrid design is the honest middle path — you get post-quantum forgery resistance from the ML-DSA half immediately, while keeping the battle-tested classical half so a flaw in the (younger) lattice-signature implementation cannot silently open the door by itself. This is authorization (who may publish), not the discovery confidentiality, and putting a PQ signature in the hybrid is us extending the post-quantum posture past the lookup into the surrounding integrity layer where we reasonably can.

We could have skipped certificates and let the directory be write-open, relying on the OPRF's unlinkability to make poisoning "pointless." That reasoning is a trap: unlinkability hides who a presence_id belongs to from the server, but a targeted attacker who already knows their victim's number can compute the victim's presence_id themselves (that is the feature!) and then poison that specific slot. Unlinkability is not authorization. So publication has to be authenticated, full stop.

6. The tripod, restated

It is worth stepping back to see how this article fits the whole. Contact-discovery privacy rests on three independent legs, and this article is the third:

Honest computation — the server proves it used the committed key (Verifiable OPRF). Defends against a lying server.
Blind lookup — the client hides which IDs it checks (PIR). Defends against a watching server.
Abuse resistance — this article. Defends against a dishonest caller using the system as designed.

The recurring point of the series is sharpest here: the first two legs are where the beautiful mathematics lives, and it would be tempting to think they are the security. But an enumeration oracle, a Sybil flood, or a poisoned entry defeats the system without touching a single lattice. The boring interfaces are load-bearing. Cryptography earns its keep only inside a system whose plain, protocol-compliant surfaces are also defended.

7. Summary

The OPRF is deliberately an oracle (numbers → IDs for anyone), and oracles get abused by compliant callers in three ways: enumeration, Sybils, poisoning.
Enumeration is fought with fail-closed rate limiting — metering the abuse pattern, not slowing every honest query.
Server breach learns nothing useful: query traffic is ciphertext, the directory is opaque keyed IDs, and the only prize is the everlasting key s. Baseline custody is KMS/HSM + rate-limited evaluation; the destination is an attested enclave (TEE) that keeps s non-exportable, so even a full compromise yields nothing. A stolen s is forward-enumeration only — no retroactive decryption, no lookup graph.
Sybils are fought with a proof-of-phone-control gate, issuing an unlinkable verified-phone token — now a lattice VOPRF credential (it was the last classical holdout, since migrated), so the Sybil gate is post-quantum too, upstream of and separate from the discovery lookup. Everything stored is keyed by the lattice presence_id, so nothing about your number sits at rest in a form the server could invert.
Poisoning is fought by requiring a hybrid-signed (Ed25519 + ML-DSA) ownership certificate to publish; unlinkability is not a substitute for authorization.
These interface defenses are the third leg of the tripod, as essential as the cryptography they sit next to.

References

J. Douceur, "The Sybil Attack," IPTPS 2002 — the fake-identity threat and why proof-of-cost or proof-of-resource gating is needed.
D. Chaum, "Blind Signatures for Untraceable Payments," CRYPTO 1982 — the unlinkable-token technique behind the Sybil gate.
NIST, FIPS 204 (ML-DSA / Dilithium), 2024 — the post-quantum half of the hybrid ownership signature.
Wikipedia: Sybil attack, Rate limiting, Blind signature, Harvest now, decrypt later.

Next, descend into the engine room: Algorithm: Oblivious Linear Evaluation from Ring-LWE.