Paper 2016/1144

Private Projections & Variants

Xavier Carpent, Sky Faber, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
xcarpent @ uci edu
History
2016-12-14: received
Short URL
https://ia.cr/2016/1144
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1144,
      author = {Xavier Carpent and Sky Faber and Tomas Sander and Gene Tsudik},
      title = {Private Projections & Variants},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1144},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1144}},
      url = {https://eprint.iacr.org/2016/1144}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.