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 -