# Find out a set of values without sharing my own

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.

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

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.