Paper 2010/220

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

Giuseppe Ateniese, Emiliano De Cristofaro, and Gene Tsudik


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 effective solutions have been proposed. Among them, Private Set Intersection (PSI) 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 {\em 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 a stronger privacy property of {\em hiding the size} of the set held by one of the two entities ("client"). We introduce the notion of Size-Hiding Private Set Intersection (SHI-PSI) and propose an efficient construction secure under the RSA assumption in the Random Oracle Model. We also show that input size-hiding is attainable at very low additional cost.

Available format(s)
Publication info
Published elsewhere. A preliminary version of this paper appears in IACR PKC 2011.
Private set intersectiontwo-party computationoblivious pseudo-random functions
Contact author(s)
edecrist @ uci edu
2010-12-24: last of 3 revisions
2010-04-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giuseppe Ateniese and Emiliano De Cristofaro and Gene Tsudik},
      title = {(If) Size Matters: Size-Hiding Private Set Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2010/220},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.