Private set intersection
Protocols that let parties holding private sets learn the intersection of those sets, or a function of it, without revealing anything else about the items outside it.
What it is
Two parties hold sets and and want without revealing anything about the items outside it (). Usually one party, the receiver, learns the intersection and the other, the sender, learns nothing; the set sizes are typically public. With more parties, all of them compute the intersection of their sets and learn nothing else beyond bounds on the set sizes (). Variants release only a function of the intersection: its size, a sum of values attached to its items, a decision on whether it is large, or secret shares for a further secure computation. Generic secure computation can compute PSI, and garbled-circuit PSI ran as fast as the public-key protocols of its time, or faster at higher security levels, at much higher bandwidth (); protocols that exploit the structure of the problem are more efficient (). Applications include private contact discovery from a phone (, ) and aggregate ad-conversion statistics ().
Core notions
- Adversaries: semi-honest parties follow the protocol; augmented semi-honest parties may change their inputs and then follow it (); malicious parties deviate arbitrarily. Security can differ by party, as in protocols that are simulation-secure against a malicious receiver but only private against a malicious sender ().
- Set-size slack: the fastest malicious protocols realize a relaxed functionality in which a corrupt party may effectively input more items than it declared, up to a constant factor (, , ).
- Balanced and unbalanced: sets of similar size, or a small receiver set against a much larger sender set, where communication can be sublinear in the larger set ().
- Outputs: the intersection; its cardinality; an intersection-sum, the sum of values attached to matching items (); threshold PSI, which releases the intersection only when the sets differ in few items (); circuit-PSI, secret shares of per-item results that feed a further secure computation (, ); and labeled PSI, which returns labels the sender attaches to matching items ().
- Hashing to bins: items are mapped into bins by simple hashing or by cuckoo hashing, which places each item in one of a few candidate bins, possibly with a stash, so that per-bin work is small; parameters are set for a hashing failure probability such as ().
- Oblivious PRF (OPRF): the receiver learns for its items while the sender holds and sends for its own items, so the receiver compares values (); many instances can be produced at once from OT extension ().
- Oblivious key-value store (OKVS): a data structure that encodes key-value pairs and hides the keys when the values are random; a polynomial through the pairs is the simplest one (), and PaXoS is a binary one decoded by XOR ().
- Lower bounds: computing the intersection needs communication linear in the set size, by the complexity of disjointness (; ); threshold PSI needs for two parties () and for parties over point-to-point channels (); and PSI implies oblivious transfer, so it has no black-box construction from one-way functions ().
Main approaches
- Public-key-based: commutative Diffie-Hellman exponentiation of hashed items (), oblivious polynomial evaluation under additively homomorphic encryption (), RSA blind signatures as the OPRF (), and PSI from any two-round key agreement with responses encoded in a polynomial, which suits small sets ().
- OT- and VOLE-based: OPRFs from OT extension combined with hashing to bins (, ); malicious security by dual execution () and by encoding the receiver's set in a PaXoS, with linear communication (); general OKVS and amplification of their failure probability (); OPRFs from vector oblivious linear evaluation (VOLE) (); and subfield VOLE with a triangulation OKVS ().
- Circuit-based and computing on the intersection: a sort-compare-shuffle garbled circuit (); hashing-based circuits with comparisons () and with communication through batched oblivious programmable PRFs (OPPRF) (, ); intersection-sum with cardinality from Diffie-Hellman double masking (); and threshold PSI from polynomial encodings and cardinality tests (, , ).
- Unbalanced and labeled: fully homomorphic encryption with batching, so that the sender evaluates the intersection on the receiver's encrypted set (), with OPRF preprocessing and labels () and lower computation and communication (); alternatively the server's OPRF-encrypted set is transferred once and queried online ().
- Multiparty: zero-sharing delivered through OPPRFs, secure against any number of colluding semi-honest parties (), malicious versions over OKVS (, ), and protocols from homomorphic set representations surveyed in .
Notation used in the comparison table
Parameters below occur in efficiency or security bounds. Each meaning is scoped to its stated regime. Measured quantities are named in words; protocol objects are defined where used. Source aliases do not equate different regimes.
| Symbol | Meaning | Regime | Paper aliases |
|---|---|---|---|
| κ | Computational security parameter. | PSI cryptographic security. | writes κ; writes κ; writes λ; writes λ; writes λ; writes λ |
| λ | Statistical security/error parameter. | PSI statistical failures; exact error expression remains source-specific. | writes λ; writes σ; writes k; writes κ; writes κ; writes ϵ; writes σ |
| nX | Sender-set cardinality: nX = |X|. | Arbitrary two-party set sizes. | writes Nx; writes n; writes kS; writes w; writes n1; writes |X|; writes Ns; writes n1; writes |X|; writes ny; writes n1; writes ny |
| nY | Receiver-set cardinality: nY = |Y|. | Arbitrary two-party set sizes. | writes Ny; writes m; writes kC; writes v; writes n2; writes |Y|; writes Nc; writes n2; writes |Y|; writes nx; writes n2; writes nx |
| n | The size of every party's set when the paper assumes equal sizes (n = nX = nY), or the common padded bound it states. | Balanced two-party or equal-size multiparty PSI. | writes n; writes m; writes n; writes k; writes M; writes m; writes m; writes m; writes k |
| σ | Bit length of an input item before any explicitly stated hashing/compression. | Bit-string PSI inputs. | writes σ; writes σ; writes α; writes λ; writes ℓ |
| ℓ | Number of parties. | Multiparty PSI. | writes n; writes ℓ; writes n; writes n; writes n; writes n; writes n |
| t | Allowed deficit from the intersection under the explicitly named threshold functionality. | Threshold PSI; per-set deficit and union deficit are different predicates. | writes T; writes t |
| tc | Maximum number of colluding/corrupted parties. | Multiparty PSI security. | writes t; writes t; writes t |
| p | Prime order of the base field 𝔽p, or the prime modulus of ℤ∗p. | PSI over prime fields, discrete-log groups, and FHE plaintext slots. | writes p; writes p; writes p; writes p; writes t; writes t |
| N | RSA or Paillier modulus N = PQ. | RSA- and Paillier-based PSI. | writes n |
| q | Ciphertext modulus of a lattice-based homomorphic encryption scheme. | FHE-based PSI. | No paper spelling asserted. |
| 𝔾 | An element of the prime-order group of the Diffie-Hellman or OPRF protocol. | Public-key PSI. | No paper spelling asserted. |
| 𝔽 | An element of the field the encoding (polynomial, OKVS) or the VOLE works over. | OKVS-, VOLE- and polynomial-based PSI. | No paper spelling asserted. |
| ℤN | An element of ℤN or ℤN2 (a Paillier ciphertext is one element of ℤN2). | RSA- and Paillier-based PSI. | No paper spelling asserted. |
| Rq | An element of the ciphertext ring ℤq[X]/(Xm + 1); an RLWE ciphertext is two. | FHE-based PSI. | No paper spelling asserted. |
Costs in the comparison tables are recorded per role, as the papers state them: what each role sends and the work it performs. A figure a paper states only for the whole protocol is recorded as the total; it is never split among the roles, and role figures are never summed into one.
| Role | Meaning | Regime | Paper names |
|---|---|---|---|
| Sender | Holds the set X, of size nX; in one-sided PSI, the party that does not learn the output. | Two-party PSI. | writes "Alice"; writes "server"; writes "server"; writes "server"; writes "P1"; writes "Bob" |
| Receiver | Holds the set Y, of size nY; in one-sided PSI, the party that learns the output. | Two-party PSI. | writes "Bob"; writes "client (chooser)"; writes "client"; writes "client"; writes "P2"; writes "Alice" |
| Leader | The party that collects the other parties' messages and computes the output. | Multiparty PSI with a designated party. | writes "leader"; writes "the last server, P_ℓ"; writes "P_1" |
| Per client | Each party that only contributes its set and sends to the leader or the pivot, counted per party. | Multiparty PSI with a designated party. | writes "client"; writes "client"; writes "P_i" |
| Per party | Each party, when all parties play the same role. | Symmetric multiparty PSI. | No paper name asserted. |
| Pivot | The party that receives and combines the clients' encodings before the final step (NTY). | Multiparty PSI with clients, a pivot and servers. | writes "pivot" |
| Per server | Each party that holds the clients' PRF keys and runs an OPPRF with the leader (NTY). | Multiparty PSI with clients, a pivot and servers. | writes "server" |
This topic covers two-party and multiparty PSI and functions of the intersection (cardinality, intersection-sum, threshold, circuit outputs, labels) in five subfields: public-key-based, OT- and VOLE-based, circuit-based, unbalanced and labeled, and multiparty PSI. Server-aided and delegated PSI, fuzzy and updatable PSI, private set union, and PSI from trusted hardware are outside it; OT extension, VOLE, and garbling belong to secure multiparty computation, and keyword PIR to private information retrieval. The covered papers date from 1999 to 2024; later work, including maliciously secure circuit-PSI, is not yet covered.