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 '18 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 '18 at 20:38
  • $\begingroup$ "Set reconciliation" Ari Trachtenberg et al $\endgroup$ – Vadym Fedyukovych Jun 10 '18 at 23:07
  • $\begingroup$ eprint.iacr.org/2018/579 $\endgroup$ – Squeamish Ossifrage Jun 11 '18 at 1:02
  • $\begingroup$ eprint.iacr.org/2019/634.pdf and citations inside $\endgroup$ – Bush Jun 13 '19 at 17:26

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

| improve this answer | |

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.

| improve this answer | |

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.