When private set intersection meets big data: an efficient and scalable protocol

Changyu Dong, Liqun Chen, Zikai Wen

Research output: Chapter in Book/Report/Conference proceedingChapter

113 Citations (Scopus)

Abstract

Large scale data processing brings new challenges to the design of privacy-preserving protocols: how to meet the increasing requirements of speed and throughput of modern applications, and how to scale up smoothly when data being protected is big. Efficiency and scalability become critical criteria for privacy preserving protocols in the age of Big Data. In this paper, we present a new Private Set Intersection (PSI) protocol that is extremely efficient and highly scalable compared with existing protocols. The protocol is based on a novel approach that we call oblivious Bloom intersection. It has linear complexity and relies mostly on efficient symmetric key operations. It has high scalability due to the fact that most operations can be parallelized easily. The protocol has two versions: a basic protocol and an enhanced protocol, the security of the two variants is analyzed and proved in the semi-honest model and the malicious model respectively. A prototype of the basic protocol has been built. We report the result of performance evaluation and compare it against the two previously fastest PSI protocols. Our protocol is orders of magnitude faster than these two protocols. To compute the intersection of two million-element sets, our protocol needs only 41 seconds (80-bit security) and 339 seconds (256-bit security) on moderate hardware in parallel mode.
LanguageEnglish
Title of host publicationProceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security
Subtitle of host publicationCCS '13
Place of PublicationNew York
Pages789-800
Number of pages12
DOIs
Publication statusAccepted/In press - 4 Nov 2013
Event20th ACM Conference on Computer and Communications Security - Berlin, Germany
Duration: 4 Nov 20138 Nov 2013

Conference

Conference20th ACM Conference on Computer and Communications Security
CountryGermany
CityBerlin
Period4/11/138/11/13

Fingerprint

Scalability
Throughput
Hardware
Big data

Keywords

  • private set intersection
  • big data
  • efficient
  • scalable protocol

Cite this

Dong, C., Chen, L., & Wen, Z. (Accepted/In press). When private set intersection meets big data: an efficient and scalable protocol. In Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security: CCS '13 (pp. 789-800). New York. https://doi.org/10.1145/2508859.2516701
Dong, Changyu ; Chen, Liqun ; Wen, Zikai. / When private set intersection meets big data : an efficient and scalable protocol. Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security: CCS '13. New York, 2013. pp. 789-800
@inbook{726fa0f5544c4e2d8d8e491f53e6ad7f,
title = "When private set intersection meets big data: an efficient and scalable protocol",
abstract = "Large scale data processing brings new challenges to the design of privacy-preserving protocols: how to meet the increasing requirements of speed and throughput of modern applications, and how to scale up smoothly when data being protected is big. Efficiency and scalability become critical criteria for privacy preserving protocols in the age of Big Data. In this paper, we present a new Private Set Intersection (PSI) protocol that is extremely efficient and highly scalable compared with existing protocols. The protocol is based on a novel approach that we call oblivious Bloom intersection. It has linear complexity and relies mostly on efficient symmetric key operations. It has high scalability due to the fact that most operations can be parallelized easily. The protocol has two versions: a basic protocol and an enhanced protocol, the security of the two variants is analyzed and proved in the semi-honest model and the malicious model respectively. A prototype of the basic protocol has been built. We report the result of performance evaluation and compare it against the two previously fastest PSI protocols. Our protocol is orders of magnitude faster than these two protocols. To compute the intersection of two million-element sets, our protocol needs only 41 seconds (80-bit security) and 339 seconds (256-bit security) on moderate hardware in parallel mode.",
keywords = "private set intersection, big data, efficient , scalable protocol",
author = "Changyu Dong and Liqun Chen and Zikai Wen",
year = "2013",
month = "11",
day = "4",
doi = "10.1145/2508859.2516701",
language = "English",
isbn = "9781450324779",
pages = "789--800",
booktitle = "Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security",

}

Dong, C, Chen, L & Wen, Z 2013, When private set intersection meets big data: an efficient and scalable protocol. in Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security: CCS '13. New York, pp. 789-800, 20th ACM Conference on Computer and Communications Security, Berlin, Germany, 4/11/13. https://doi.org/10.1145/2508859.2516701

When private set intersection meets big data : an efficient and scalable protocol. / Dong, Changyu; Chen, Liqun; Wen, Zikai.

Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security: CCS '13. New York, 2013. p. 789-800.

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - When private set intersection meets big data

T2 - an efficient and scalable protocol

AU - Dong, Changyu

AU - Chen, Liqun

AU - Wen, Zikai

PY - 2013/11/4

Y1 - 2013/11/4

N2 - Large scale data processing brings new challenges to the design of privacy-preserving protocols: how to meet the increasing requirements of speed and throughput of modern applications, and how to scale up smoothly when data being protected is big. Efficiency and scalability become critical criteria for privacy preserving protocols in the age of Big Data. In this paper, we present a new Private Set Intersection (PSI) protocol that is extremely efficient and highly scalable compared with existing protocols. The protocol is based on a novel approach that we call oblivious Bloom intersection. It has linear complexity and relies mostly on efficient symmetric key operations. It has high scalability due to the fact that most operations can be parallelized easily. The protocol has two versions: a basic protocol and an enhanced protocol, the security of the two variants is analyzed and proved in the semi-honest model and the malicious model respectively. A prototype of the basic protocol has been built. We report the result of performance evaluation and compare it against the two previously fastest PSI protocols. Our protocol is orders of magnitude faster than these two protocols. To compute the intersection of two million-element sets, our protocol needs only 41 seconds (80-bit security) and 339 seconds (256-bit security) on moderate hardware in parallel mode.

AB - Large scale data processing brings new challenges to the design of privacy-preserving protocols: how to meet the increasing requirements of speed and throughput of modern applications, and how to scale up smoothly when data being protected is big. Efficiency and scalability become critical criteria for privacy preserving protocols in the age of Big Data. In this paper, we present a new Private Set Intersection (PSI) protocol that is extremely efficient and highly scalable compared with existing protocols. The protocol is based on a novel approach that we call oblivious Bloom intersection. It has linear complexity and relies mostly on efficient symmetric key operations. It has high scalability due to the fact that most operations can be parallelized easily. The protocol has two versions: a basic protocol and an enhanced protocol, the security of the two variants is analyzed and proved in the semi-honest model and the malicious model respectively. A prototype of the basic protocol has been built. We report the result of performance evaluation and compare it against the two previously fastest PSI protocols. Our protocol is orders of magnitude faster than these two protocols. To compute the intersection of two million-element sets, our protocol needs only 41 seconds (80-bit security) and 339 seconds (256-bit security) on moderate hardware in parallel mode.

KW - private set intersection

KW - big data

KW - efficient

KW - scalable protocol

UR - http://eprint.iacr.org/2013/515

UR - http://www.sigsac.org/ccs/CCS2013/index.html

U2 - 10.1145/2508859.2516701

DO - 10.1145/2508859.2516701

M3 - Chapter

SN - 9781450324779

SP - 789

EP - 800

BT - Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security

CY - New York

ER -

Dong C, Chen L, Wen Z. When private set intersection meets big data: an efficient and scalable protocol. In Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security: CCS '13. New York. 2013. p. 789-800 https://doi.org/10.1145/2508859.2516701