# American Institute of Mathematical Sciences

August  2017, 11(3): 481-502. doi: 10.3934/amc.2017040

## Private set intersection: New generic constructions and feasibility results

 1 Dipartimento di Informatica, University of Salerno, 84084 Fisciano (SA), Italy 2 MACIMTE, Area de Matemática Aplicada, U. Rey Juan Carlos, c/ Tulipán, s/n, 28933, Móstoles, Madrid, Spain 3 Telefónica Research, Barcelona, Spain 4 Florida Atlantic University (FAU), 777 Glades Rd, Boca Raton, FL 33431, USA

* Corresponding author

Received  July 2015 Revised  December 2015 Published  August 2017

Fund Project: The first three and the last author were partially supported by the Spanish Ministerio de Economía y Competitividad through the project grant MTM-2010-15167. This research is also partially supported by the Italian PRIN project GenData 2020

In this paper we focus on protocols for private set intersection (PSI), 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.

In the unconditional setting we evidence that PSI is impossible to realize and that unconditionally secure size-hiding PSI is possible assuming a set-up authority is present in an set up phase. In the computational setting we give a generic construction using smooth projective hash functions for languages derived from perfectly-binding commitments. Further, we give two size-hiding constructions: the first one is theoretical and evidences the equivalence between PSI, oblivious transfer and the secure computation of the AND function. The second one is a twist on the oblivious polynomial evaluation construction of Freedman et al. from EUROCRYPT 2004. We further sketch a generalization of the latter using algebraic-geometric techniques. Finally, assuming again there is a set-up authority (yet not necessarily trusted) we present very simple and efficient constructions that only hide the size of the client's set.

Citation: Paolo D'Arco, María Isabel González Vasco, Angel L. Pérez del Pozo, Claudio Soriente, Rainer Steinwandt. Private set intersection: New generic constructions and feasibility results. Advances in Mathematics of Communications, 2017, 11 (3) : 481-502. doi: 10.3934/amc.2017040
##### References:

show all references

##### References:
An unconditionally secure size-hiding set intersection protocol
A generic PSI protocol from smooth projective hashing
A computationally secure size-hiding set intersection protocol
OT protocol based on trapdoor permutations
Polynomial-based construction for $|\mathcal{C}|,|\mathcal{S}| \le M$
Algebraic PSI construction for $|\mathcal{C}|,|\mathcal{S}| \le M$
The PRF-PSI-protocol
Setup phase of the OPRF-PSI-protocol
Performance comparison of SPH-based implementations vs prior public key implementations for PSI
 Protocol Comm. Overhead Server Exp. Client Exp. [20] $\mathcal{O}(v + w)$ $\mathcal{O}(w(\log\log v))$ $\mathcal{O}(w+v)$ [31] $\mathcal{O}(w +v)$ $\mathcal{O}(vw)$ $\mathcal{O}(v+w)$ SPH-DDH $\mathcal{O}(vw)$ $\mathcal{O}(vw)$ $\mathcal{O}(v)$
 Protocol Comm. Overhead Server Exp. Client Exp. [20] $\mathcal{O}(v + w)$ $\mathcal{O}(w(\log\log v))$ $\mathcal{O}(w+v)$ [31] $\mathcal{O}(w +v)$ $\mathcal{O}(vw)$ $\mathcal{O}(v+w)$ SPH-DDH $\mathcal{O}(vw)$ $\mathcal{O}(vw)$ $\mathcal{O}(v)$

2018 Impact Factor: 0.879