Cryptology ePrint Archive: Report 2016/1144

Private Projections & Variants

Xavier Carpent and Sky Faber and Tomas Sander and Gene Tsudik

Abstract: There are many realistic settings where two mutually suspicious parties need to share some specific information while keeping everything else private. Various privacy-preserving techniques (such as Private Set Intersection) have been proposed as general solutions.

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:

[ Cryptology ePrint archive ]