Find out a set of values without sharing my own

Question

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.

Answer 1

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

Answer 2

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.