Paper 2011/141

Fast and Private Computation of Cardinality of Set Intersection and Union

Emiliano De Cristofaro
Paolo Gasti
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.

Note: This paper extends a prior version that appears in the 11th International Conference on Cryptology and Network Security (CANS 2012), addressing a technical issue in the definition of random oracle H identified by Tan and Lv. in: Y. Tan and B. Lv., Mistakes of a popular protocol calculating private set intersection and union cardinality and its corrections. arXiv preprint arXiv:2207.13277, 2022

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. CANS 2012 - The 11th International Conference on Cryptology and Network Security
Keywords
public-key cryptography cryptographic protocols private set operations private set intersection cardinality linear complexity
Contact author(s)
pgasti @ nyit edu
History
2022-11-08: last of 7 revisions
2011-03-22: received
See all versions
Short URL
https://ia.cr/2011/141
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/141,
      author = {Emiliano De Cristofaro and Paolo Gasti and Gene Tsudik},
      title = {Fast and Private Computation of Cardinality of Set Intersection and Union},
      howpublished = {Cryptology ePrint Archive, Paper 2011/141},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/141}},
      url = {https://eprint.iacr.org/2011/141}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.