Unbalanced PSI

The party holding the massive dataset pre-processes its elements into an encrypted data structure, often a homomorphically encrypted Bloom filter or a polynomial representation. This one-time setup allows the smaller party to obliviously query membership without the server learning the query. Common constructions include:

• PaXoS (Pseudorandom Correlation): Encodes the large set into a compressed, queryable format
• FHE-based matrix: Encrypts the entire large set under a fully homomorphic encryption scheme for arbitrary computation
• OPRF-based structures: Uses oblivious pseudorandom functions to mask elements

The most prominent real-world deployment of unbalanced PSI is private contact discovery in secure messaging applications. When a user joins a platform, their device queries the server's global user database to find which of their contacts are already registered. Unbalanced PSI ensures:

• The server learns nothing about the user's address book
• The user learns only which contacts are registered, not the full user base
• The protocol remains bandwidth-efficient on mobile networks Major platforms like Signal and WhatsApp have deployed variants of this technology to protect user privacy at scale.

A protocol where a client learns the output of a pseudorandom function keyed by a server on the client's input, without the server learning the input or the client learning the key. In unbalanced PSI, the party with the small set typically acts as the client, evaluating the OPRF on their elements while the large-set party holds the key. This prevents the server from brute-forcing the small set.

• Key Property: The server remains oblivious to the client's queried elements.
• Usage: Forms the core of modern semi-honest unbalanced PSI protocols like the KKRT construction.

A hashing scheme that resolves collisions by relocating existing keys using two or more hash functions. In unbalanced PSI, the smaller set is typically placed into a Cuckoo hash table to ensure each bin holds at most one element. This allows the larger set to perform a single lookup per bin rather than a linear scan.

• Optimization: Reduces the number of expensive cryptographic operations on the large set side.
• Stash: A small overflow area for elements that cannot be placed, which must be handled separately to avoid information leakage.

The foundational protocol by Ishai, Kilian, Nissim, and Petrank that efficiently generates a large number of oblivious transfers from a small number of base OTs using only fast symmetric-key operations. This is critical for unbalanced PSI because the party with the large set can pre-compute OT extensions to handle millions of comparisons without prohibitive public-key cryptography costs.

• Efficiency: Amortizes the cost of expensive base OTs over many cheap extensions.
• Modern Variants: Ferret OT and SoftSpoken OT further reduce communication, directly benefiting unbalanced settings.

A cryptographic primitive that allows two parties to generate a long vector of correlated oblivious linear evaluations. VOLE serves as a fast, low-communication foundation for recent high-performance unbalanced PSI protocols. The party with the large set can use VOLE to efficiently encode their entire dataset into a form that enables constant-round intersection checks.

• Advantage: Achieves extremely low communication overhead, often linear only in the size of the smaller set.
• Protocols: Underpins state-of-the-art constructions like PaXoS and SpOT-Light.

A classical approach where both parties hash their elements under their respective secret keys using Elliptic Curve Diffie-Hellman (ECDH). The party with the small set sends their encrypted elements to the large-set party, who re-encrypts them and compares against their own encrypted set. While simple, this approach has linear communication complexity in the size of the small set, making it naturally suited for unbalanced scenarios.

• Limitation: Vulnerable to brute-force attacks if the small set's domain is small.
• Enhancement: Often combined with blinding factors to prevent dictionary attacks.

A construction that leverages fully homomorphic encryption to evaluate the intersection logic directly on encrypted data. In unbalanced settings, the party with the small set encrypts their elements under an FHE scheme and sends them to the large-set party, who homomorphically computes the intersection without decryption. This achieves minimal communication but imposes a heavy computational burden on the large-set party.

• Trade-off: Low round complexity and communication for high computation cost.
• Use Case: Ideal when bandwidth is the primary bottleneck and the large-set party has significant compute resources.