Efficient Scalable Multiparty Private Set-Intersection via Garbled Bloom Filters. (2018)
Roi Inbar and Eran Omri and Benny Pinkas.
Abstarct:
In private set intersection (PSI), a set of parties, each holding
a private data set, wish to compute the intersection over all data sets
in a manner that guarantees both correctness and privacy. This secure
computation task is of great importance and usability in many different
real-life scenarios. Much research was dedicated to the construction of
PSI-tailored concretely efficient protocols for the case of two-party PSI.
The case of many parties has been given much less attention, despite
probably being a more realistic setting for most applications.
In this work, we propose a new concretely efficient, highly scalable, secure
computation protocol for multiparty PSI. Our protocol is an extension
of the two-party PSI protocol of Dong et al. [ACM CCS’13] and uses the
garbled Bloom filter primitive introduced therein. There are two main
variants to our protocol. The first construction provides semi-honest security.
The second construction provides (the slightly weaker) augmented
semi-honest security, and is substantially more efficient. Furthermore, in
the augmented semi-honest protocol all heavy computations can be performed
ahead of time, in an offline phase, before the parties ever learn
their inputs. This results in an online phase that requires only short interaction.
Moreover the in the online phase, interactions are performed
over a star topology network. All our constructions tolerate any number
of corruptions.
We implemented our protocols and incorporated several optimization
techniques. These techniques allow the running time of the protocol to
be comparable to that of the two party protocol of Dong et al. and scale
linearly with the number of parties. We ran extensive experiments to
compare our protocol with the two-party protocol and to demonstrate
the effect of the different optimizations.