Privacy preserving set intersection protocol secure against malicious behaviors

Yingpeng Sang, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

25 Citations (Scopus)

Abstract

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).

Original languageEnglish
Title of host publication18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007
Pages461-468
Number of pages8
DOIs
Publication statusPublished - 2007
Externally publishedYes
Event18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007 - Adelaide, SA, Australia
Duration: 3 Dec 20076 Dec 2007

Publication series

NameParallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

Conference

Conference18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007
Country/TerritoryAustralia
CityAdelaide, SA
Period3/12/076/12/07

Keywords

  • Cryptographic protocol
  • Distributed datasets
  • Privacy preservation
  • Set intersection
  • Zero-knowledge proof

Fingerprint

Dive into the research topics of 'Privacy preserving set intersection protocol secure against malicious behaviors'. Together they form a unique fingerprint.

Cite this