
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

MultiParty PrivacyPreserving Set Intersection with QuasiLinear Complexity
Jung Hee CHEON Stanislaw JARECKI Jae Hong SEO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E95A
No.8
pp.13661378 Publication Date: 2012/08/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E95.A.1366 Print ISSN: 09168508 Type of Manuscript: PAPER Category: Cryptography and Information Security Keyword: multiparty set intersection, privacypreserving set operation,
Full Text: PDF>>
Summary:
Secure computation of the set intersection functionality allows n parties to find the intersection between their datasets without revealing anything else about them. An efficient protocol for such a task could have multiple potential applications in commerce, health care, and security. However, all currently known secure set intersection protocols for n > 2 parties have computational costs that are quadratic in the (maximum) number of entries in the dataset contributed by each party, making secure computation of the set intersection only practical for small datasets. In this paper, we describe the first multiparty protocol for securely computing the set intersection functionality with both the communication and the computation costs that are quasilinear in the size of the datasets. For a fixed security parameter, our protocols require O(n^{2}k) bits of communication and Õ(n^{2}k) group multiplications per player in the malicious adversary setting, where k is the size of each dataset. Our protocol follows the basic idea of the protocol proposed by Kissner and Song, but we gain efficiency by using different representations of the polynomials associated with users' datasets and careful employment of algorithms that interpolate or evaluate polynomials on multiple points more efficiently. Moreover, the proposed protocol is robust. This means that the protocol outputs the desired result even if some corrupted players leave during the execution of the protocol.


