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

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.