The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
Scalable Private Set Intersection Based on OT Extension
Abstract
Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI protocols have been proposed. However, the variety of existing PSI protocols makes it difficult to identify the solution that performs best in a respective scenario, especially since they were not compared in the same setting. In addition, existing PSI protocols are several orders of magnitude slower than an insecure naïve hashing solution, which is used in practice. In this article, we review the progress made on PSI protocols and give an overview of existing protocols in various security models. We then focus on PSI protocols that are secure against semi-honest adversaries and take advantage of the most recent efficiency improvements in Oblivious Transfer (OT) extension, propose significant optimizations to previous PSI protocols, and suggest a new PSI protocol whose runtime is superior to that of existing protocols. We compare the performance of the protocols, both theoretically and experimentally, by implementing all protocols on the same platform, give recommendations on which protocol to use in a particular setting, and evaluate the progress on PSI protocols by comparing them to the currently employed insecure naïve hashing protocol. We demonstrate the feasibility of our new PSI protocol by processing two sets with a billion elements each.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
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
How to generate and exchange secrets
Yao, A. C.-C. (1986) · 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) · doi:10.1109/sfcs.1986.25 · Cited by 3,733
(2011) · IEEE Software · doi:10.1109/ms.2011.67 · Cited by 1,989
Goldreich, O. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511721656 · Cited by 1,805
(2004) · IEEE Security & Privacy Magazine · doi:10.1109/msp.2004.9 · Cited by 1,518
The power of two choices in randomized load balancing
Mitzenmacher, M. (2001) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.963420 · Cited by 1,399
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
Self-citationPagh, R., & Rodler, F. F. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2003.12.002 · Cited by 1,045
ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation
Demmler, D., Schneider, T., & Zohner, M. (2015) · Proceedings 2015 Network and Distributed System Security Symposium · doi:10.14722/ndss.2015.23113 · Cited by 827
Self-citationExtending 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
Improved Garbled Circuit: Free XOR Gates and Applications
Kolesnikov, V., & Schneider, T. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70583-3_40 · Cited by 743
Self-citationSecure Two-Party Computation Is Practical
Pinkas, B., Schneider, T., Smart, N. P., & Williams, S. C. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10366-7_15 · Cited by 711
Self-citationPrivacy-Preserving Set Operations
Kissner, L., & Song, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/11535218_15 · Cited by 648
“Balls into Bins” — A Simple and Tight Analysis
Raab, M., & Steger, A. (1998) · Lecture Notes in Computer Science · doi:10.1007/3-540-49543-6_13 · Cited by 455
Keyword Search and Oblivious Pseudorandom Functions
Freedman, M. J., Ishai, Y., Pinkas, B., & Reingold, O. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_17 · Cited by 441
Self-citationPractical 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
When private set intersection meets big data: an efficient and scalable protocol
Dong, C., Chen, L., & Wen, Z. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516701 · Cited by 387
Efficient Batched Oblivious PRF with Applications to Private Set Intersection
Kolesnikov, V., Kumaresan, R., Rosulek, M., & Trieu, N. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978381 · Cited by 380
A New Approach to Practical Active-Secure Two-Party Computation
Nielsen, J. B., Nordholt, P. S., Orlandi, C., & Burra, S. S. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_40 · Cited by 379
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
Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits Using Half Gates
Zahur, S., Rosulek, M., & Evans, D. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-46803-6_8 · Cited by 367
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
Self-citationThe Art of Error Correcting Coding
Morelos‐Zaragoza, R. H. (2006) · Wiley eBooks · doi:10.1002/0470035706 · Cited by 319
Efficient Garbling from a Fixed-Key Blockcipher
Bellare, M., Hoang, V. T., Keelveedhi, S., & Rogaway, P. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.39 · Cited by 304
Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?
Huang, Y., Evans, D., & Katz, J. I. (2012) · Cited by 301
Albrecht, M. R., Rechberger, C., Schneider, T., Tiessen, T., & Zohner, M. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-46800-5_17 · Cited by 290
Self-citationCorrelated 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
Enhancing privacy and trust in electronic communities
Huberman, B. A., Franklin, M., & Hogg, T. (1999) · Proceedings of the 1st ACM conference on Electronic commerce · doi:10.1145/336992.337012 · Cited by 224
Meadows, C. (1986) · 1986 IEEE Symposium on Security and Privacy · doi:10.1109/sp.1986.10022 · Cited by 207
Privacy-Preserving Set Operations
Kissner, L., & Song, D. (2005) · doi:10.21236/ada457144 · Cited by 169
Improved OT Extension for Transferring Short Secrets
Kolesnikov, V., & Kumaresan, R. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40084-1_4 · Cited by 167
A New Combinational Logic Minimization Technique with Applications to Cryptology
Boyar, J., & Peralta, R. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13193-6_16 · Cited by 140
Improved Private Set Intersection Against Malicious Adversaries
Rindal, P., & Rosulek, M. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56620-7_9 · Cited by 120
GMW vs. Yao? Efficient Secure Two-Party Computation with Low Depth Circuits
Schneider, T. H., & Zohner, M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39884-1_23 · Cited by 112
Self-citationTwo Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates.
Zahur, S., Rosulek, M., & Evans, D. (2014) · Cited by 112
Malicious-Secure Private Set Intersection via Dual Execution
Rindal, P., & Rosulek, M. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3134044 · Cited by 109
Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
Arbitman, Y., Naor, M., & Segev, G. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.80 · Cited by 105
Efficient Set Intersection with Simulation-Based Security
Freedman, M. J., Hazay, C., Kobbi Nissim, B., & Benny Pinkas, B. (2014) · Journal of Cryptology · doi:10.1007/s00145-014-9190-0 · Cited by 100
More Efficient Oblivious Transfer Extensions with Security for Malicious Adversaries
Asharov, G., Lindell, Y., Schneider, T. H., & Zohner, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46800-5_26 · Cited by 96
Self-citation2008 Annual Computer Security Applications Conference (ACSAC)
(2008) · doi:10.1109/acsac14895.2008 · Cited by 83
Constructions of truly practical secure protocols using standardsmartcards
Hazay, C., & Lindell, Y. (2008) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/1455770.1455832 · Cited by 69
Privacy-preserving applications on smartphones
Huang, Y., Chapman, P., & Evans, D. (2011) · Cited by 68
O-PSI: Delegated Private Set Intersection on Outsourced Datasets
Abadi, A., Terzis, S., & Dong, C. (2015) · IFIP advances in information and communication technology · doi:10.1007/978-3-319-18467-8_1 · Cited by 62
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
VD-PSI: Verifiable Delegated Private Set Intersection on Outsourced Private Datasets
Abadi, A., Terzis, S., & Dong, C. (2017) · Lecture notes in computer science · doi:10.1007/978-3-662-54970-4_9 · Cited by 52
The Circle Game: Scalable Private Membership Test Using Trusted Hardware
Tamrakar, S., Liu, J., Paverd, A., Ekberg, J.-E., Benny Pinkas, B., & Asokan, N. (2017) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/3052973.3053006 · Cited by 50
Cited by
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
Lindell, Y. (2021) · Communications of the ACM · doi:10.1145/3387108 · Cited by 320
Secure Federated Submodel Learning
Niu, C., Wu, F., Tang, S., Hua, L., Jia, R., Lv, C., Wu, Z., & Chen, G. (2019) · arXiv · doi:10.48550/arxiv.1911.02254 · Cited by 28
Metadata
- Authors
- Pinkas, B., Schneider, T., & Zohner, M.
- Venue
- ACM Transactions on Privacy and Security
- Published
- 2018-01-02
- Volume
- 21
- Issue
- 2
- Pages
- 1-35
- ISSN
- 2471-2566 (ISSN-L)
- 2471-2574
- OpenAlex
- W2782492233
- Cited by
- 313
- References
- 49
- FWCI
- 14.00
- Type
- journal article
- 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.