Paper 2015/321

Size-Hiding in Private Set Intersection: what can be done and how to do it without random oracles

Paolo D'Arco, Maria Isabel Gonzalez Vasco, Angel L. Perez del Pozo, and Clauido Soriente


In this paper we focus our attention on private set intersection protocols, through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage. Considering the (more restricted) size-hiding scenario, we are able to: - prove that it is impossible to realize an unconditionally secure set intersection protocol (size-hiding or not); - prove that unconditionally secure size-hiding set intersection is possible in a model where a set up authority provides certain information to the two parties and disappears; - provide several new computationally secure size-hiding set intersection protocols. Regarding the latter, in particular we provide a new generic construction without random oracles for the unbalanced setting, where only the client gets the intersection and hides the size of its set of secrets. The main tool behind this design are smooth projective hash functions for languages derived from perfectly-binding commitments. We stand on the seminal ideas of Cramer-Shoup and Gennaro-Lindell, which have already found applications in several other contexts, such as password-based authenticated key exchange and oblivious transfer.

Available format(s)
-- withdrawn --
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.Size-Hiding in Private Set Intersection: Existential Results and Constructions. Progress in Cryptology - AFRICACRYPT 2012. Lecture Notes in Computer Science Volume 7374, 2012, pp 378-394
Private set intersectionsize-hidingunconditional securitysmooth projective hashing.
Contact author(s)
angel perez @ urjc es
2015-04-23: withdrawn
2015-04-11: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.