Found by the people who know you. Listed by nobody.

A person who opts in registers a handle, an email, a phone number or a username, through an oblivious function: the phone blinds the handle, the discovery service evaluates its secret key on the blind without seeing the handle, the phone unblinds, and what the service stores is the output, a value it cannot turn back into a handle without guessing the handle, one keyed evaluation per guess. The person proves the handle is hers to a separate verifier role, by a code sent to it, the one place a handle is seen, and the verifier never sees the output.

A phone looking for its friends runs the same blinding over its own address book, on the phone, and asks the service which outputs are registered. A match hands the phone the matched account's pairing material, sealed so that only a phone that really holds that handle can open it; pairing then proceeds exactly as an invitation does, and the matched person's phone asks before any message passes. Nothing is stored about who matched whom. Nothing is stored at all for a person who did not opt in.

What the discovery service sees: the number of registered handles, the rate of queries, and that a query was paid for with an anonymous token. What it never sees: an address book, a lookup's inputs, or who matched whom. The social graph is on no server. Signal's answer to the same problem is trusted hardware; ours is arithmetic, because an enclave is a trust statement about a chip vendor and the company's line is absence, not trust.

Said plainly: the operator of the discovery service, who holds the key, can confirm whether a handle it guesses is registered, offline, at one evaluation per guess, which for phone numbers is days of work. Every client's evaluation is rate-limited and paid for; the operator's own are bounded by nothing but its computer. What removes the residual, rather than rate-limiting it, is splitting the key across two independently operated services, each evaluating in turn, so that one operator alone can test nothing. That is one more evaluation on the wire and it waits on a second operator existing.