1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mind leaking the size of $A\cap B$? $\endgroup$ – Changyu Dong Jul 23 '18 at 8:42
  • $\begingroup$ @ChangyuDong since I don't have anything in mind, it is ok to leak $|A\cap B|$. $\endgroup$ – DiamondDuck Jul 23 '18 at 16:37
3
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.