(If) Size Matters: Size-Hiding Private Set Intersection

(If) Size Matters: Size-Hiding Private Set Intersection,10.1007/978-3-642-19379-8_10,Giuseppe Ateniese,Emiliano De Cristofaro,Gene Tsudik

(If) Size Matters: Size-Hiding Private Set Intersection   (Citations: 3)
BibTex | RIS | RefWorks Download
Modern society is increasingly dependent on, and fearful of, the availability of electronic information. There are numerous examples of situations where sensitive data must be { sometimes reluctantly { shared between two or more entities without mutual trust. As often happens, the research community has foreseen the need for mechanisms to enable limited (privacy-preserving) sharing of sensitive information and a number of eective (if not always ecient) solutions have been proposed. Among them, Private Set Intersection techniques are particularly appealing for scenarios where two parties wish to compute an intersection of their respective sets of items without revealing to each other any other information. Thus far, "any other information" has been interpreted to mean any information about items not in the intersection. In this paper, we motivate the need for Private Set Intersection with stronger privacy properties that include hiding of the set size held by one of the two entities (Client). This new and important privacy feature turns out to be attainable at relative low additional cost. We illustrate a pair of concrete SHI- PSI (Size-Hiding Private Set Intersection) protocols that oer a trade-o between stronger privacy and better eciency. Both protocols are provably secure under very standard cryptographic assumptions. We demonstrate their practicality via experimental results obtained from a prototype implementation. We also consider size-hiding in a group PSI setting and construct a Group SHI-PSI extension that incurs surprisingly low overhead.
Conference: Public Key Cryptography - PKC , pp. 156-173, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: