Paper 2017/027

Scalable Multi-Party Private Set-Intersection

Carmit Hazay and Muthuramakrishnan Venkitasubramaniam

Abstract

In this work we study the problem of private set-intersection in the multi-party setting and design two protocols with the following improvements compared to prior work. First, our protocols are designed in the so-called star network topology, where a designated party communicates with everyone else, and take a new approach of leveraging the 2PC protocol of [FreedmanNP04]. This approach minimizes the usage of a broadcast channel, where our semi-honest protocol does not make any use of such a channel and all communication is via point-to-point channels. In addition, the communication complexity of our protocols scales with the number of parties. More concretely, (1) our first semi-honest secure protocol implies communication complexity that is linear in the input sizes, namely $O((\sum_{i=1}^n m_i)\cdot\kappa)$ bits of communication where $\kappa$ is the security parameter and $m_i$ is the size of $P_i$'s input set, whereas overall computational overhead is quadratic in the input sizes only for a designated party, and linear for the rest. We further reduce this overhead by employing two types of hashing schemes. (2) Our second protocol is proven secure in the malicious setting. This protocol induces communication complexity $O((n^2 + nm_\maxx + nm_\minn\log m_\maxx)\kappa)$ bits of communication where $m_\minn$ (resp. $m_\maxx$) is the minimum (resp. maximum) over all input sets sizes and $n$ is the number of parties.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in PKC 2017
Keywords
Scalable Multi-Party ComputationPrivate Set-Intersection
Contact author(s)
carmit hazay @ biu ac il
History
2018-08-18: last of 3 revisions
2017-01-13: received
See all versions
Short URL
https://ia.cr/2017/027
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/027,
      author = {Carmit Hazay and Muthuramakrishnan Venkitasubramaniam},
      title = {Scalable Multi-Party Private Set-Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2017/027},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/027}},
      url = {https://eprint.iacr.org/2017/027}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.