PSI protocol reveals only one element of the intersection of two sets

Question

So let Alice has a set of integers, says, $A = \{a_1,\dots, a_n\}$, similarly, Bob has a set of integers $B=\{b_1,\dots, b_n\}$.

is there any protocol that allows Alice and Bob to randomly learn exactly one element from the intersection, $A\cap B$? I am aware of few private set intersection algorithms, but all of them reveal the whole intersection.

Answer 1

In fact, one possibility is to use the generic garbled circuit protocol that implements a PSI circuit + a filter circuit such that the result (intersection) from the PSI is filtered and only one randomly chosen element in the intersection is output at the end of the protocol. However, I cannot say much except this is feasible.

Below is a custom protocol for your purpose, assuming $|A\cap B|$ can be leaked and semi-honest adversaries. It can be further optimized.

You need 3 building blocks:

1. A PSI with data transfer protocol (see below references [1,2, 3]). A PSI with data transfer protocol is a PSI protocol such that at the end of the execution, Bob gets nothing and Alice gets for each element $a_i$ in her set, a piece of data $d_i$. If we just want PSI, then if $a_i$ is not in the intersection $d_i$ is a random string, otherwise if $a_i$ is in the intersection $d_i$ is $a_i$ itself. So that after running the protocol, Alice gets the intersection. The trick we will use relies on the fact that it is entirely possible to let $d_i$ convey other information than just the set element.
2. A semantically secure encryption scheme $(\mathcal{G},\mathcal{E},\mathcal{D})$ in which the ciphertext can be efficiently re-randomized. Here $\mathcal{G},\mathcal{E},\mathcal{D}$ are the key generation, encryption, decryption algorithms. One example is Paillier. For any ciphertext $\mathcal{E}_{pk}(m)$, one can re-randomize it by generating a fresh encryption of 0, $\mathcal{E}_{pk}(0)$, and use the homomorphic property to get a new ciphertext $\mathcal{E}_{pk}(m)*\mathcal{E}_{pk}(0) = \mathcal{E}_{pk}(m+0)= \mathcal{E}_{pk}(m)$. The new ciphertxt encrypts the same plaintext but looks totally different.
3. A sementically secure symmetric block cipher $(G,E,D)$.

In the protocol, Alice has a set $A$, Bob has a set $B$. Bob also generates a key pair $(pk,sk)=\mathcal{G}(\lambda)$ ($\lambda$ is a security paramter). Bob gives $pk$ to Alice. Then they do the following:

1. Bob generates a random key $k_1=G(\lambda)$, then use the block cipher to encrypt all his elements $E_{k_1}(b_1),\ldots,E_{k_1}(b_n)$.

2. Bob and Alice run the PSI with data transfer protocol, such that Alice uses her set as input, and Bob for each his element $b_i$, send a data payload $(\mathcal{E}_{pk}(1),E_{k_1}(b_i))$, -- note that each $\mathcal{E}_{pk}(1)$ must be generated using fresh randomness.

3. In total, Alice will receive $n$ pieces of data in the form of $(c_1^i,c_2^i)$. If Alice has an element $a_i =b_j$ (i.e. $a_i =b_j$ is in the intersection), Alice will receive the payload $(\mathcal{E}_{pk}(1),E_{k_1}(b_j))$, otherwise, Alice will receive a piece of random data which can be parsed as $(\mathcal{E}_{pk}(r_1),E_{k_1}(r_2))$ where $r_1,r_2$ are random. However, Alice cannot tell whether each $(c_1^i,c_2^i)$ she received is "good" or random because it is a pair of ciphertexts.
4. Alice generates a new key $k_2=G(\lambda)$. For each $(c_1^i,c_2^i)$ pair, Alice re-randomizes $c_1^i$ to get a new ciphertext $(c^i_1)'$, and encrypts $c_2^i$ to get $(c^i_2)'=E_{k_2}(c_2^i)$. Alice puts all pairs $((c^i_1)',(c^i_2)')$ in a set $A'$, randomly permutes $A'$, and then sends $A'$ to Bob.
5. Bob generates a new key $k_3=G(\lambda)$. For each element $((c^i_1)',(c^i_2)')$ in $A'$, decrypts $(c^i_1)'$, if the result $\mathcal{D}_{sk}((c^i_1)')=1$, puts $E_{k3}((c^i_2)')$ in a set $B'$. After all pairs have been processed, permute $B'$ and send $B'$ to Alice. (If $B'$ is empty then stop because the intersection is empty).
6. Alice randomly chooses one element $e \in B'$, sends $e$ to Bob. Bob decrypts and sends $e' =D_{k_3}(e)$ to Alice. Alice decrypts and sends $e''= D_{k_2}(e')$ to Bob. Bob decrypts and sends $e'''=D_{k_1}(e'')$ to Alice. Now $e'''=D_{k_1}(D_{k_2}(D_{k_3}(E_{k_3}(E_{k_2}(E_{k_1}(b_l))))))$ is a random element in $A\cap B$.

1 Efficient Private Matching and Set Intersection, Michael J. Freedman, Kobbi Nissim, Benny Pinkas, EUROCRYPT 2004 (link)

2 Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity, Emiliano De Cristofaro and Gene Tsudik, FC2010 (link)

3 When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol, Changyu Dong, Liqun Chen, Zikai Wen, CCS 2013 (link)