Based on timely real-world examples, this paper motivates the need for a new privacy tool, called Private Set Intersection with Projection (PSI-P). In it, Server has (at least) a two-attribute table and Client has a set of values. At the end of the protocol, based on all matches between Client's set and values in one (search) attribute of Serverís database, Client should learn the set of elements corresponding to the second attribute, and nothing else. In particular the intersection of Client's set and the set of values in the search attribute must remain hidden.
We construct several efficient (linear complexity) protocols that approximate privacy required by PSI-P and suffice in many practical scenarios. We also provide a new construction for PSI-P with full privacy, albeit slightly less efficient. Its key building block is a new primitive called Existential Private Set Intersection (PSI-X) which yields a binary flag indicating whether the intersection of two private sets is empty or non-empty.Category / Keywords: cryptographic protocols / Date: received 9 Dec 2016, last revised 9 Dec 2016 Contact author: xcarpent at uci edu Available format(s): PDF | BibTeX Citation Version: 20161214:190409 (All versions of this report) Short URL: ia.cr/2016/1144 Discussion forum: Show discussion | Start new discussion