Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity

Jung Hee CHEON; Stanislaw JARECKI; Jae Hong SEO

doi:10.1587/transfun.E95.A.1366

Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity

Jung Hee CHEON, Stanislaw JARECKI, Jae Hong SEO

Full Text Views

0

Cite this

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 multi-party protocol for securely computing the set intersection functionality with both the communication and the computation costs that are quasi-linear in the size of the datasets. For a fixed security parameter, our protocols require O(n²k) bits of communication and Õ(n²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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E95-A No.8 pp.1366-1378

Publication Date: 2012/08/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E95.A.1366

Type of Manuscript: PAPER

Category: Cryptography and Information Security

Cite this

Copy

Jung Hee CHEON, Stanislaw JARECKI, Jae Hong SEO, "Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity" in IEICE TRANSACTIONS on Fundamentals, vol. E95-A, no. 8, pp. 1366-1378, August 2012, doi: 10.1587/transfun.E95.A.1366.
Abstract: 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 multi-party protocol for securely computing the set intersection functionality with both the communication and the computation costs that are quasi-linear in the size of the datasets. For a fixed security parameter, our protocols require O(n²k) bits of communication and Õ(n²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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E95.A.1366/_p

Copy

@ARTICLE{e95-a_8_1366,
author={Jung Hee CHEON, Stanislaw JARECKI, Jae Hong SEO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity},
year={2012},
volume={E95-A},
number={8},
pages={1366-1378},
abstract={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 multi-party protocol for securely computing the set intersection functionality with both the communication and the computation costs that are quasi-linear in the size of the datasets. For a fixed security parameter, our protocols require O(n²k) bits of communication and Õ(n²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.},
keywords={},
doi={10.1587/transfun.E95.A.1366},
ISSN={1745-1337},
month={August},}

Copy

TY - JOUR
TI - Multi-Party Privacy-Preserving Set Intersection with Quasi-Linear Complexity
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1366
EP - 1378
AU - Jung Hee CHEON
AU - Stanislaw JARECKI
AU - Jae Hong SEO
PY - 2012
DO - 10.1587/transfun.E95.A.1366
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E95-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2012
AB - 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 multi-party protocol for securely computing the set intersection functionality with both the communication and the computation costs that are quasi-linear in the size of the datasets. For a fixed security parameter, our protocols require O(n²k) bits of communication and Õ(n²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.
ER -