Asymmetric PSI

The fundamental property of asymmetric PSI is that only the client receives the intersection result. The server learns absolutely nothing about the client's input set or the resulting intersection. This is cryptographically enforced, not merely a policy choice.

• Client learns: The elements common to both sets
• Server learns: Nothing beyond what it already knows (its own set)
• No leakage: The server cannot distinguish between a client query that yields an intersection and one that yields an empty result

This one-sidedness is what makes the protocol suitable for scenarios where the server's dataset is public or already known to the server, and only the client requires privacy.

Asymmetric PSI is inherently designed for a client-server topology, where the server holds a large, often static dataset and the client queries with a smaller, private set. This architecture reflects real-world applications like messaging contact discovery.

• Server role: Holds the full dataset (e.g., all registered users) and responds to queries
• Client role: Initiates the protocol with a private input set (e.g., phone contacts)
• Communication pattern: Single request-response round trip in optimized protocols
• Scalability: Server can pre-process its dataset once and serve many clients efficiently

The asymmetry in roles maps directly to the asymmetry in output, creating a natural fit for service-oriented deployments.

Asymmetric PSI protocols are specifically optimized for highly unbalanced set sizes, where the server's set is orders of magnitude larger than the client's. This is the typical scenario in contact discovery, where a server may hold billions of records while a client queries with hundreds or thousands.

• Server set size: Can be billions of elements
• Client set size: Typically hundreds to thousands
• Optimization: Server computation scales with client set size, not server set size
• Techniques used: Oblivious Pseudorandom Functions (OPRFs) and hash-based binning

Protocols like the KKRT framework and VOLE-based constructions exploit this asymmetry to keep client computation and communication minimal while allowing the server to handle massive datasets efficiently.

A key performance feature of asymmetric PSI is the ability for the server to perform one-time pre-processing on its dataset. This pre-computed state can be reused across many client queries without regeneration.

• Pre-processing: Server encrypts or hashes its entire set once
• Reusability: The same pre-processed data serves all subsequent client queries
• Amortized cost: The heavy cryptographic work is amortized over many interactions
• Storage trade-off: Pre-computed structures may require significant server storage

This design pattern is critical for production deployments where the server's dataset changes infrequently but must handle high query volumes with low latency.

Modern asymmetric PSI protocols can achieve malicious security, protecting against adversaries that arbitrarily deviate from the protocol specification. This is essential for real-world deployments where the server cannot be trusted to follow the protocol honestly.

• Semi-honest model: Assumes parties follow the protocol but may try to learn extra information
• Malicious model: Protects against any deviation, including sending malformed messages
• Cut-and-choose techniques: Used to verify server behavior without revealing private data
• Trade-off: Malicious security adds computational overhead but provides stronger guarantees

Protocols like those based on Vector OLE (VOLE) can achieve malicious security with minimal overhead compared to semi-honest variants, making them practical for production use.

The most common security model for efficient asymmetric PSI. Assumes both parties follow the protocol specification correctly but may be curious—they will try to infer additional information from the protocol transcript. This is often acceptable for client-server contact discovery where the server has a business reputation to maintain. Provides significantly better performance than malicious security, which defends against arbitrary deviations.

An extension where the server's set elements have associated data labels (e.g., public keys, profile photos). In an asymmetric setting, the client learns not only which of their inputs are in the server's set, but also the labels attached to those matching elements. This is critical for contact discovery: the client needs to retrieve the user ID or encryption key for matched contacts, not just a boolean yes/no.

A privacy-preserving variant that reveals only the size of the intersection, not the elements themselves. In an asymmetric context, a client might learn that 15 of their contacts use a service without discovering which 15. This provides an even stronger privacy guarantee for the server's user base. Useful for anonymous analytics, measuring audience overlap, or triggering actions based on a threshold without exposing identities.