Size-hiding in private set intersection: existential results and constructions

In this paper we focus our attention on private set intersection. We show impossibility and existential results, and we provide some explicit constructions. More precisely, we start by looking at the case in which both parties, client and server, in securely computing the intersection, would like to hide the sizes of their sets of secrets, and we show that: - It is impossible to realize an unconditionally secure size-hiding set intersection protocol. - In a model where a TTP provides set up information to the two parties and disappears, unconditionally secure size-hiding set intersection is possible. - There exist computationally secure size-hiding set intersection protocols. Then, we provide some explicit constructions for one-sided protocols, where only the client gets the intersection and hides the size of her set of secrets. In the model with the TTP, we design two protocols which are computationally secure under standard assumptions, and two very efficient protocols which are secure in the random oracle model. We close the paper with some remarks and by pointing out several interesting open problems.