I have the following problem which i am trying to find a reasonable protocol to solve it.

This is a simplified version of the problem.

Alice has a set of values $\{a_1,a_2,...,a_n\}$.

Bob has a set of values $\{b_1,b_2,...,b_n\}$.

Alice wants to learn which values Bob has that are equal to her values but without Bob learning any of the inputs she gives him, Alice is also not allowed to learn any other values bob has.

I appreciate an efficient solution but any solution at the moment is better than nothing.

  • 2
    $\begingroup$ You want "private set intersection" or maybe "private information retrieval". $\endgroup$
    – SEJPM
    Jun 10, 2018 at 19:40
  • $\begingroup$ Or you could establish a trusted third party of course, but I presume that this has already been deemed infeasible for this situation (?). $\endgroup$
    – Maarten Bodewes
    Jun 10, 2018 at 20:38
  • $\begingroup$ "Set reconciliation" Ari Trachtenberg et al $\endgroup$ Jun 10, 2018 at 23:07
  • $\begingroup$ eprint.iacr.org/2018/579 $\endgroup$ Jun 11, 2018 at 1:02
  • $\begingroup$ eprint.iacr.org/2019/634.pdf and citations inside $\endgroup$
    – Bush
    Jun 13, 2019 at 17:26

2 Answers 2


You are looking for a private set intersection protocol.

For the semi-honest (passive adversary that follows the protocol) setting, go to Benny Pinkas's homepage and read the papers there, e.g.

Scalable Private Set Intersection Based on OT Extension

Efficient Circuit-based PSI via Cuckoo Hashing

For the malicious (active adversary that behaves arbitrarily) setting, go to Mike Rosulek's homepage and read the papers there, e.g.

Malicious-Secure Private Set Intersection via Dual Execution

Improved Private Set Intersection against Malicious Adversaries


This seems the same as how advertisers share email lists.

Bob sends a list of hashed values to Alice and she computes the hashes of her values and compares.

Of course, this is not completely hiding so if the values come from a small enumerable domain then Alice can obtain all Bob's values.

Concatenation of nonces would deal with repeated values.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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