The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
Space/time trade-offs in hash coding with allowable errors
Bloom, B. H. (1970) · Communications of the ACM · doi:10.1145/362686.362692 · Cited by 7,492
Random oracles are practical: a paradigm for designing efficient protocols
Bellare, M., & Rogaway, P. (1993) · Proceedings of the 1st ACM conference on Computer and communications security - CCS '93 · doi:10.1145/168588.168596 · Cited by 4,712
Applied cryptography: Protocols, algorithms, and source code in C
(1994) · Computer Law & Security Report · doi:10.1016/0267-3649(94)90017-5 · Cited by 3,411
MapReduce: Simplified Data Processing on Large Cluster
Senior Software Developer, A. U., & Dayalan, M. (2018) · International Journal of Research and Engineering · doi:10.21276/ijre.2018.5.5.4 · Cited by 2,948
Foundations of Cryptography: Volume 2, Basic Applications
Goldreich, O. (2004) · Cited by 1,592
A Randomized Protocol for Signing Contracts
Even, S., Goldreich, O., & Lempel, A. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_19 · Cited by 1,450
Security and Composition of Multiparty Cryptographic Protocols
Canetti, R. (2000) · Journal of Cryptology · doi:10.1007/s001459910006 · Cited by 1,403
Efficient Private Matching and Set Intersection
Freedman, M. J., Nissim, K., & Pinkas, B. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_1 · Cited by 1,266
How to Exchange Secrets with Oblivious TransferPreprint
Rabin, M. O. (1981) · IACR Cryptology ePrint Archive · Cited by 870
Extending Oblivious Transfers Efficiently
Ishai, Y., Kilian, J., Nissim, K., & Petrank, E. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_9 · Cited by 746
Privacy-Preserving Set Operations
Kissner, L., & Song, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/11535218_15 · Cited by 648
Efficient oblivious transfer protocols
Naor, M., & Benny Pinkas, B. (2001) · Symposium on Discrete Algorithms · doi:10.5555/365411.365502 · Cited by 614
Privacy-Preserving Data Mining: Models and Algorithms
(2008) · Advances in Database Systems · doi:10.1007/978-0-387-70992-5 · Cited by 503
Practical Private Set Intersection Protocols with Linear Complexity
De Cristofaro, E., & Tsudik, G. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14577-3_13 · Cited by 416
Location Privacy via Private Proximity Testing.
Narayanan, A., Thiagarajan, N., Lakhani, M., Hamburg, M., & Boneh, D. (2011) · Network and Distributed System Security Symposium · Cited by 376
Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?
Huang, Y., Evans, D., & Katz, J. I. (2012) · Cited by 301
Jarecki, S., & Liu, X. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00457-5_34 · Cited by 300
BotGrep: finding P2P bots with structured graph analysis
Nagaraja, S., Mittal, P., Hong, C.-Y., Caesar, M., & Borisov, N. (2010) · University of Birmingham Research Portal (University of Birmingham) · Cited by 273
Hazay, C., & Lindell, Y. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78524-8_10 · Cited by 267
Correlated pseudorandomness and the complexity of private computations
Beaver, D. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237996 · Cited by 233
Countering GATTACA: efficient and secure testing of fully-sequenced human genomes
Baldi, P., Baronio, R., De Cristofaro, E., Gasti, P., & Tsudik, G. (2011) · Proceedings of the 18th ACM conference on Computer and communications security · doi:10.1145/2046707.2046785 · Cited by 227
Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model
De Cristofaro, E., Kim, J., & Tsudik, G. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_13 · Cited by 225
Fast Secure Computation of Set Intersection
Jarecki, S., & Liu, X. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15317-4_26 · Cited by 191
Privacy-Preserving Set Operations
Kissner, L., & Song, D. (2005) · doi:10.21236/ada457144 · Cited by 169
Efficient Robust Private Set Intersection
Dachman-Soled, D., Malkin, T., Raykova, M., & Yung, M. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-01957-9_8 · Cited by 160
Private Intersection of Certified Sets
Camenisch, J. L., & Zaverucha, G. M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03549-4_7 · Cited by 124
(If) Size Matters: Size-Hiding Private Set Intersection
Ateniese, G., Cristofaro, E. D., & Tsudik, G. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19379-8_10 · Cited by 120
Efficient Set Operations in the Presence of Malicious Adversaries
Hazay, C., & Kobbi Nissim, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13013-7_19 · Cited by 119
Experimenting with Fast Private Set Intersection
Cristofaro, E. D., & Tsudik, G. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30921-2_4 · Cited by 81
Random Oracles with(out) Programmability
Fischlin, M., Lehmann, A., Ristenpart, T., Shrimpton, T., Stam, M., & Tessaro, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17373-8_18 · Cited by 79
Privacy-Preserving Relationship Path Discovery in Social Networks
Mezzour, G., Perrig, A., Gligor, V. D., & Papadimitratos, P. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10433-6_13 · Cited by 61
OpenConflict: Preventing Real Time Map Hacks in Online Games
Bursztein, E., Hamburg, M., Lagarenne, J., & Boneh, D. (2011) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2011.28 · Cited by 42
Cited by
Secure Multi-Party Computation: Theory, practice and applications
Zhao, C., Zhao, S., Zhao, M., Chen, Z., Gao, C.-Z., Li, H., & Tan, Y.-A. (2019) · Information Sciences · doi:10.1016/j.ins.2018.10.024 · Cited by 508
Security and Privacy in Smart Health: Efficient Policy-Hiding Attribute-Based Access Control
Zhang, Y., Zheng, D., & Deng, R. H. (2018) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2825289 · Cited by 487
More efficient oblivious transfer and extensions for faster secure computation
Asharov, G., Lindell, Y., Schneider, T., & Zohner, M. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516738 · Cited by 358
Fast Private Set Intersection from Homomorphic Encryption
Chen, H., Laine, K., & Rindal, P. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134061 · Cited by 352
Scalable Private Set Intersection Based on OT Extension
Pinkas, B., Schneider, T., & Zohner, M. (2018) · ACM Transactions on Privacy and Security · doi:10.1145/3154794 · Cited by 313
Metadata
- Authors
- Dong, C., Chen, L., & Wen, Z.
- Venue
- Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13
- Publisher
- ACM Press
- Published
- 2013
- Pages
- 789-800
- OpenAlex
- W2004957971
- Cited by
- 387
- References
- 33
- FWCI
- 14.31
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.