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