Cryptology ePrint Archive: Report 2015/321

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

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

Abstract: 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.

Category / Keywords: cryptographic protocols / Private set intersection, size-hiding, unconditional security, smooth projective hashing.

Original Publication (with major differences): 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

Date: received 9 Apr 2015, withdrawn 23 Apr 2015

Contact author: angel perez at urjc es

Available format(s): (-- withdrawn --)

Version: 20150423:105243 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]