Private set intersection
A private set intersection (PSI) protocol is a two-party protocol in which a sender holding a set and a receiver holding a set , each of bounded size, securely compute the functionality : the receiver learns , each party learns the size of the other’s set, and neither learns anything more.
Syntax
A PSI protocol for a universe and size bounds and , with , and polynomials, is a two-party protocol :
- , a randomized algorithm generating public parameters, with in the plain model,
- (the sender) and (the receiver) are stateful interactive algorithms with:
- input: a set with ,
- input: a set with ,
- output: an integer ,
- output: a set and an integer .
We write . The ideal functionality receives from and from , replaces an input that is not a subset of of at most (respectively ) elements by , and hands each party its component of
The sizes and are the functionality’s leakage. With sets encoded as strings of a fixed length and an input that encodes no admissible set replaced by , is a two-party functionality in the sense of MPC.
Properties
Correctness
A PSI protocol is -correct if for all and all with and ,
where and . When , is perfectly correct.
Semi-honest security
The corrupted party is fixed in advance and runs honestly, and the adversary chooses both sets after seeing the reference string. In world it receives ‘s view of a real execution together with the honest party’s output; in world it receives the simulator’s output on ‘s input and ‘s component of , together with the honest party’s component. In world the simulator also produces the reference string, as in semi-honest MPC; in the plain model this is immaterial.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sh}}_{\Pi,P,\Sim,\calA}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$; $\pp_0 \gets \Setup(1^\secpar)$; $\pp_1 \gets \Sim(1^\secpar)$
\Comment{$P \in \{S, R\}$ is the corrupted party; $\Sim$ is stateful}
\State $(X, Y, \stA) \gets \calA(1^\secpar, \pp_b)$
\Comment{Admissible: $X, Y \subseteq U$, $|X| \le n_S$, $|Y| \le n_R$}
\State Run $\langle S(\pp_0, X), R(\pp_0, Y) \rangle \to (s, (Z, s'))$; let $\View_P$ be $P$'s view
\If{$P = S$}
\State $\mathit{out}_0 := (\View_S, (Z, s'))$; $\mathit{out}_1 := (\Sim(X, |Y|), (X \cap Y, |X|))$
\Else
\State $\mathit{out}_0 := (\View_R, s)$; $\mathit{out}_1 := (\Sim(Y, X \cap Y, |X|), |Y|)$
\EndIf
\State $b' \gets \calA(\stA, \mathit{out}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
A PSI protocol is semi-honest secure if for each there is an efficient such that for all efficient admissible ,
is negligible. This is semi-honest two-party computation of .
Malicious security
A PSI protocol has malicious security if it securely computes with abort against corruptions, in the sense of security with abort for (2PC): for all efficient corrupting one of the two parties and deviating arbitrarily there is an efficient such that for all efficient , is negligible. In the ideal execution a corrupted sender hands the trusted party a set with of the simulator’s choice and receives , and a corrupted receiver hands it a set with of the simulator’s choice and receives ; in either case the simulator may then make the honest party output . The bound on the substituted set is what protects the honest sender: a corrupted receiver allowed to submit would learn .
Variations
Non-degenerate PSI
A non-degenerate PSI protocol is a semi-honest secure PSI protocol for with and size bounds and . For , PSI is perfectly realizable with no assumption: sends , and sends if and otherwise; for , the receiver’s output determines — folklore.
Two-sided PSI
In two-sided (or mutual) PSI both parties learn the intersection: the functionality hands to and to . Semi-honest and malicious security are defined as above for this functionality; with abort, the corrupted party receives the intersection before the simulator decides whether the honest party receives it.
PSI cardinality
In PSI cardinality the receiver learns the size of the intersection and not its elements: the functionality hands to and to .
Size-hiding PSI
In size-hiding PSI one party’s set has no a priori polynomial bound on its size, and the functionality does not reveal that size to the other party. Against semi-honest adversaries, if fully homomorphic encryption exists, every function can be securely computed while hiding the input size of one party when both parties receive output, or when the party not receiving output learns the size of the output, so in particular two-sided PSI can; some functions cannot be securely computed while hiding the input sizes of both parties — LNO13.
Other results
- The general protocol run on is a semi-honest secure PSI protocol when it comes from semi-honest 2PC (semi-honest 2PC ⇒ PSI) and one with malicious security when it comes from 2PC (2PC ⇒ malicious PSI) — folklore.
- A semi-honest secure OPRF with a range of super-polynomial size and a PRF that collides on each pair of distinct inputs with negligible probability over the key (OPRF with super-polynomial range) gives non-degenerate PSI: the sender sends the sorted list of the PRF values of its elements under its key, and the receiver obtains the PRF value of each of its elements from one OPRF execution and keeps the elements whose values were sent (OPRF ⇒ PSI) — folklore. HL08 base set intersection on secure evaluation of a pseudorandom function rather than on polynomials.
- Non-degenerate PSI gives semi-honest OT with message space : with sender set and receiver set , the intersection, if and otherwise, reveals and nothing about , and the sender learns nothing about (PSI ⇒ OT) — folklore.
- FNP04 compute set intersection with an additively homomorphic encryption scheme, such as Paillier’s (Pai99): the receiver encrypts under its own key the coefficients of ; for each the sender computes from them an encryption of for a uniform and sends these ciphertexts in random order; and the receiver decrypts and outputs the plaintexts that lie in . The protocol is secure against semi-honest adversaries in the standard model, and a variant is secure against malicious adversaries in the random oracle model; with balanced allocation hashing, sets of size cost communication and computation.
- Of the set intersection protocols of HL08, one is secure against malicious adversaries under a relaxed definition, simulatable when one party is corrupted and only private, in an indistinguishability sense, when the other is; another is fully simulatable against covert adversaries, which may cheat but are then caught with probability at least the protocol’s deterrence factor.
- JL09 obtain secure computation of set intersection against malicious adversaries from an OPRF for the Dodis–Yampolskiy PRF (DY05).
- KKRT16 build a batched, related-key OPRF, which gives the receiver the values at inputs of its choice of many PRF instances with related keys, by adapting 1-out-of-2 OT extension protocols, secure against semi-honest adversaries; with cuckoo hashing it gives semi-honest PSI whose cost does not depend on the bit length of the elements.
Participates in
Builds on Private set intersection
Produces Private set intersection