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.