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
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
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
protocols, where only the client
the intersection and
the size of her set of secrets. In the model with the
, 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.