Cryptology ePrint Archive: Report 2011/141
Fast and Private Computation of Cardinality of Set Intersection and Union
Emiliano De Cristofaro and Paolo Gasti and Gene Tsudik
Abstract: In many everyday scenarios, sensitive information must be shared between parties without complete mutual trust. Private set operations are particularly useful to enable sharing information with privacy, as they allow two or more parties to jointly compute operations on their sets (e.g., intersection, union, etc.), such that only the minimum required amount of information is disclosed. In the last few years, the research community has proposed a number of secure and efficient techniques for Private Set Intersection (PSI), however, somewhat less explored is the problem of computing the magnitude, rather than the contents, of the intersection - we denote this problem as Private Set Intersection Cardinality (PSI-CA).
This paper explores a few PSI-CA variations and constructs several protocols that are more efficient than the state-of-the-art.
Category / Keywords: public-key cryptography; cryptographic protocols; private set operations; private set intersection; cardinality; linear complexity
Original Publication (with minor differences): CANS 2012 - The 11th International Conference on Cryptology and Network Security
Date: received 21 Mar 2011, last revised 14 Aug 2013
Contact author: pgasti at nyit edu
Available format(s): PDF | BibTeX Citation
Note: This version presents modified constructions and new security model/proofs.
Version: 20130814:165930 (All versions of this report)
Short URL: ia.cr/2011/141
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]