Contact Discovery

Contact discovery is a classic asymmetric PSI use case. Only the client (user) learns the intersection—which of their contacts are on the service. The server learns nothing about the user's address book beyond what it already knows. This prevents the service provider from harvesting non-user contact data. The protocol enforces this through cryptographic means, not policy: even a malicious server cannot extract the full contact list.

Contact discovery exhibits extreme set size asymmetry. A user's address book typically contains hundreds to thousands of contacts, while the service's registered user base can number in the billions. Protocols like KKRT and VOLE-based constructions are specifically optimized for this imbalance, allowing the client to perform work proportional to their small input set while the server handles the massive set efficiently through precomputed data structures and OT extension.

Without rate limiting, a malicious client could perform enumeration attacks—repeatedly querying the service with arbitrary phone numbers to reconstruct the entire user database. Production contact discovery systems enforce cryptographic rate limiting or require the client to solve computational puzzles (e.g., proof-of-work) before each query. This makes bulk enumeration economically infeasible while remaining transparent to legitimate users performing a single lookup.

To achieve sub-second latency for billions of records, modern contact discovery protocols leverage offline precomputation. The server can pre-hash its entire user database into a Cuckoo hashing table or precompute OPRF keys once, then reuse these structures across millions of client queries. This shifts the heavy cryptographic work to idle periods, allowing online queries to complete with minimal computation and communication.

Contact discovery implementations face a critical security model choice:

• Semi-honest security: Assumes the server follows the protocol correctly but may inspect the transcript. Faster and sufficient when the server is trusted not to deviate.
• Malicious security: Protects against servers that arbitrarily deviate from the protocol to extract information. Essential when the service provider cannot be fully trusted, but incurs higher computational overhead. Signal's private contact discovery service uses a semi-honest model with hardware enclave attestation as an additional trust anchor.

Classical contact discovery protocols relying on Diffie-Hellman assumptions are vulnerable to future quantum adversaries capable of breaking discrete logarithms. Forward-looking deployments are evaluating post-quantum PSI constructions based on lattice assumptions or FHE-based PSI that remain secure against Shor's algorithm. While current quantum threats are theoretical, the long-term sensitivity of social graph data warrants crypto-agility in protocol design.

Signal uses a trusted execution environment (TEE) based on Intel SGX to perform contact discovery. The client encrypts their address book and sends it to a secure enclave running on Signal's servers. The enclave decrypts the data, compares it against the registered user database, and returns only the intersection. The server operator cannot inspect the plaintext address book because the enclave's memory is hardware-encrypted. This approach trades cryptographic complexity for practical performance, processing millions of lookups daily while ensuring the plaintext never leaves the CPU package.

WhatsApp employs an oblivious pseudorandom function (OPRF) to protect user contact lists. The client hashes each phone number and blinds it before sending it to the server. The server applies its secret key to the blinded value and returns the result. The client unblinds the response to obtain a PRF output, which is then used to query an encrypted database. This ensures the server never sees the raw phone numbers and cannot link queries across different sessions. The protocol is designed to handle unbalanced PSI scenarios where the server holds billions of registered users while the client uploads a few hundred contacts.

Telegram performs contact discovery by uploading hashed phone numbers to its servers. The server computes the intersection against its user database and returns matching contacts. While this approach is fast and simple, it provides weaker privacy guarantees compared to OPRF or TEE-based methods. A malicious or compromised server could theoretically perform a brute-force enumeration attack against the hashed numbers, especially given the limited entropy of phone numbers. Telegram relies on rate limiting and operational security rather than cryptographic privacy for this feature.

Apple's iMessage uses identity-based encryption (IBE) for contact discovery. When a user enables iMessage, their device generates a set of public keys derived from their phone number and Apple's master secret. Other users can encrypt invitation tokens to these derived public keys without needing to query Apple's servers for each contact. The server acts as a relay but cannot decrypt the tokens. This design shifts the privacy guarantee toward client-side cryptography, reducing server trust requirements while maintaining the ability to discover which contacts are iMessage-enabled.

Microsoft Edge's Password Monitor uses a private set intersection cardinality protocol to check if a user's saved credentials appear in known breach databases without revealing the passwords to Microsoft. The client hashes and blinds each credential, sends the blinded values to the server, and receives back encrypted results. The client can determine if a match exists without the server learning which credentials were checked or which matched. This is a practical deployment of asymmetric PSI where only the client learns the result, protecting billions of credentials from exposure.

Google's Private Join and Compute is a labeled PSI protocol that allows two organizations to compute aggregate statistics over the intersection of their datasets without revealing individual records. For example, an advertiser can measure campaign conversion rates by joining their impression data with a merchant's sales data, learning only the aggregate conversion count. The protocol uses homomorphic encryption to compute sums over the matched records, ensuring that neither party learns the other's non-matching entries or individual matched values. This demonstrates PSI's evolution from simple membership testing to privacy-preserving analytics.