TY - GEN

T1 - Privacy preserving set intersection protocol secure against malicious behaviors

AU - Sang, Yingpeng

AU - Shen, Hong

PY - 2007

Y1 - 2007

N2 - When datasets are distributed on different sources, finding out their intersection while preserving the privacy of the datasets is a widely required task. In this paper, we address the Privacy Preserving Set Intersection (PPSI) problem, in which each of the N parties learns no elements other than the intersection of their N private datasets. We propose an efficient protocol in the malicious model, where the adversary may control arbitrary number of parties and execute the protocol for its own benefit. A related work in [12] has a correctness probability of (N-1/N)N (N is the size of the encryption scheme's plaintext space), a computation complexity of O(N2S 2lgN) (S is the size of each party's data set). Our PPSI protocol in the malicious model has a correctness probability of (N-1/N)N-1, and achieves a computation cost of O(c2S2lgN) (c is the number of malicious parties and c ≤ N - 1).

AB - When datasets are distributed on different sources, finding out their intersection while preserving the privacy of the datasets is a widely required task. In this paper, we address the Privacy Preserving Set Intersection (PPSI) problem, in which each of the N parties learns no elements other than the intersection of their N private datasets. We propose an efficient protocol in the malicious model, where the adversary may control arbitrary number of parties and execute the protocol for its own benefit. A related work in [12] has a correctness probability of (N-1/N)N (N is the size of the encryption scheme's plaintext space), a computation complexity of O(N2S 2lgN) (S is the size of each party's data set). Our PPSI protocol in the malicious model has a correctness probability of (N-1/N)N-1, and achieves a computation cost of O(c2S2lgN) (c is the number of malicious parties and c ≤ N - 1).

KW - Cryptographic protocol

KW - Distributed datasets

KW - Privacy preservation

KW - Set intersection

KW - Zero-knowledge proof

UR - http://www.scopus.com/inward/record.url?scp=48049104079&partnerID=8YFLogxK

U2 - 10.1109/PDCAT.2007.4420204

DO - 10.1109/PDCAT.2007.4420204

M3 - Conference contribution

AN - SCOPUS:48049104079

SN - 0769530494

SN - 9780769530499

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 461

EP - 468

BT - 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007

T2 - 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007

Y2 - 3 December 2007 through 6 December 2007

ER -