research-article

Public Access

Scalable Private Set Intersection Based on OT Extension

Authors:

Thomas Schneider,

Michael ZohnerAuthors Info & Claims

ACM Transactions on Privacy and Security (TOPS), Volume 21, Issue 2

Article No.: 7, Pages 1 - 35

https://doi.org/10.1145/3154794

Published: 02 January 2018 Publication History

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.

References

[1]

A. Abadi, S. Terzis, and C. Dong. 2015. O-PSI: Delegated private set intersection on outsourced datasets. In ICT Systems Security and Privacy Protection (SEC’15) (IFIP AICT), Vol. 455. Springer, 3--17.

[2]

A. Abadi, S. Terzis, and C. Dong. 2017. VD-PSI: Verifiable delegated private set intersection on outsourced private datasets. In Financial Cryptography and Data Security (FC’16)(LNCS), Vol. 9603. Springer, 149--168.

[3]

M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner. 2015. Ciphers for MPC and FHE. In Advances in Cryptology—EUROCRYPT’15 (LNCS), Vol. 9056. Springer, 430--454.

[4]

Y. Arbitman, M. Naor, and G. Segev. 2010. Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In Foundations of Computer Science (FOCS’10). IEEE, 787--796.

Digital Library

[5]

G. Asharov, Y. Lindell, T. Schneider, and M. Zohner. 2013. More efficient oblivious transfer and extensions for faster secure computation. In Computer and Communications Security (CCS’13). ACM, 535--548.

Digital Library

[6]

G. Asharov, Y. Lindell, T. Schneider, and M. Zohner. 2015. More efficient oblivious transfer extensions with security for malicious adversaries. In Advances in Cryptology—EUROCRYPT’15 (LNCS), Vol. 9056. Springer, 673--701.

[7]

N. Asokan, A. Dmitrienko, M. Nagy, E. Reshetova, A.-R. Sadeghi, T. Schneider, and S. Stelle. 2013. CrowdShare: Secure mobile resource sharing. In Applied Cryptography and Network Security (ACNS’13) (LNCS), Vol. 7954. Springer, 432--440.

[8]

P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti, and G. Tsudik. 2011. Countering GATTACA: Efficient and secure testing of fully-sequenced human genomes. In Computer and Communications Security (CCS’11). ACM, 691--702.

Digital Library

[9]

R. W. Baldwin and W. C. Gramlich. 1985. Cryptographic protocol for trustable matchmaking. In Symposium on Security and Privacy (S8P’85). IEEE, 92--100.

[10]

D. Beaver. 1996. Correlated pseudorandomness and the complexity of private computations. In Symposium on Theory of Computing (STOC’96). ACM, 479--488.

Digital Library

[11]

M. Bellare, V. Hoang, S. Keelveedhi, and P. Rogaway. 2013. Efficient garbling from a fixed-key blockcipher. In Symposium on Security and Privacy (S8P’13). IEEE, 478--492.

Digital Library

[12]

M. Bellare and P. Rogaway. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In Computer and Communications Security (CCS’93). ACM, 62--73.

Digital Library

[13]

J. Boyar and R. Peralta. 2010. A new combinational logic minimization technique with applications to cryptology. In Symposium on Experimental Algorithms (SEA’10) (LNCS), Vol. 6049. Springer, 178--189.

Digital Library

[14]

E. Bursztein, M. Hamburg, J. Lagarenne, and D. Boneh. 2011. OpenConflict: Preventing real time map hacks in online games. In Symposium on Security and Privacy (S8P’11). IEEE, 506--520.

[15]

H. Carter, C. Amrutkar, I. Dacosta, and P. Traynor. 2013. For your phone only: Custom protocols for efficient secure function evaluation on mobile devices. J. Secur. Commun. Netw. (2013).

[16]

E. De Cristofaro, J. Kim, and G. Tsudik. 2010. Linear-complexity private set intersection protocols secure in malicious model. In Advances in Cryptology—ASIACRYPT’10 (LNCS), Vol. 6477. Springer, 213--231.

[17]

E. De Cristofaro and G. Tsudik. 2010. Practical private set intersection protocols with linear complexity. In Financial Cryptography and Data Security (FC’10) (LNCS), Vol. 6052. Springer, 143--159.

Digital Library

[18]

S. K. Debnath and R. Dutta. 2015. Secure and efficient private set intersection cardinality using bloom filter. In Information Security Conference (ISC’15) (LNCS), Vol. 9290. Springer, 209--226.

Digital Library

[19]

D. Demmler, T. Schneider, and M. Zohner. 2015. ABY: A framework for efficient mixed-protocol secure two-party computation. In Network and Distributed System Security (NDSS’15). The Internet Society.

[20]

G. Dessouky, F. Koushanfar, A.-R. Sadeghi, T. Schneider, S. Zeitouni, and M. Zohner. 2017. Pushing the communication barrier in secure computation using lookup tables. In Network and Distributed System Security (NDSS’17). The Internet Society.

[21]

M. Dietzfelbinger, A. Goerdt, M. Mitzenmacher, A. Montanari, R. Pagh, and M. Rink. 2010. Tight thresholds for cuckoo hashing via XORSAT. In International Colloquium on Automata, Languages and Programming (ICALP’10) (LNCS), Vol. 6198. Springer, 213--225.

[22]

C. Dong, L. Chen, and Z. Wen. 2013. When private set intersection meets big data: An efficient and scalable protocol. In Computer and Communications Security (CCS’13). ACM, 789--800.

Digital Library

[23]

M. Fischlin, B. Pinkas, A.-R. Sadeghi, T. Schneider, and I. Visconti. 2011. Secure set intersection with untrusted hardware tokens. In Cryptographers’ Track at the RSA Conference (CT-RSA’11) (LNCS), Vol. 6558. Springer, 1--16.

[24]

M. J. Freedman, C. Hazay, K. Nissim, and B. Pinkas. 2016. Efficient set intersection with simulation-based security. J. Cryptol. 29, 1 (2016), 115--155.

Digital Library

[25]

M. J. Freedman, Y. Ishai, B. Pinkas, and O. Reingold. 2005. Keyword search and oblivious pseudorandom functions. In Theory of Cryptography Conference (TCC’05) (LNCS), Vol. 3378. Springer, 303--324.

Digital Library

[26]

M. J. Freedman, K. Nissim, and B. Pinkas. 2004. Efficient private matching and set intersection. In Advances in Cryptology—EUROCRYPT’04 (LNCS), Vol. 3027. Springer, 1--19.

[27]

O. Goldreich. 2004. Foundations of Cryptography. Vol. 2: Basic Applications. Cambridge University Press, Cambridge, UK.

[28]

O. Goldreich, S. Micali, and A. Wigderson. 1987. How to play any mental game or a completeness theorem for protocols with honest majority. In Symposium on Theory of Computing (STOC’87). ACM, 218--229.

[29]

G. Gonnet. 1981. Expected length of the longest probe sequence in hash code searching. J. ACM 28, 2 (1981), 289--304.

Digital Library

[30]

C. Hazay and Y. Lindell. 2008. Constructions of truly practical secure protocols using standard smartcards. In Computer and Communications Security (CCS’08). ACM, 491--500.

[31]

W. Henecka and T. Schneider. 2013. Faster secure two-party computation with less memory. In Symposium on Information, Computer and Communications Security (ASIACCS’13). ACM, 437--446.

Digital Library

[32]

Y. Huang, P. Chapman, and D. Evans. 2011. Privacy-preserving applications on smartphones. In Hot topics in Security (HotSec’11). USENIX.

[33]

Y. Huang, D. Evans, and J. Katz. 2012. Private set intersection: Are garbled circuits better than custom protocols? In Network and Distributed System Security (NDSS’12). The Internet Society.

[34]

Y. Huang, D. Evans, J. Katz, and L. Malka. 2011. Faster secure two-party computation using garbled circuits. In USENIX Security Symposium 2011. USENIX, 539--554.

[35]

B. A. Huberman, M. Franklin, and T. Hogg. 1999. Enhancing privacy and trust in electronic communities. In ACM Conference on Electronic Commerce (EC’99). ACM, 78--86.

Digital Library

[36]

Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. 2003. Extending oblivious transfers efficiently. In Advances in Cryptology—CRYPTO’03 (LNCS), Vol. 2729. Springer, 145--161.

[37]

S. Kamara, P. Mohassel, M. Raykova, and S. Sadeghian. 2014. Scaling private set intersection to s-element sets. In Financial Cryptography and Data Security (FC’14) (LNCS), Vol. 8437. Springer, 195--215.

[38]

A. Kirsch, M. Mitzenmacher, and U. Wieder. 2009. More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput. 39, 4 (2009), 1543--1561.

Digital Library

[39]

Á. Kiss, J. Liu, T. Schneider, N. Asokan, and B. Pinkas. 2017. Private set intersection for unequal set sizes with mobile applications. Privacy Enhancing Technologies (PoPETs’17) 2017, 4 (2017), 97--117.

[40]

L. Kissner and D. Song. 2005. Privacy-preserving set operations. In Advances in Cryptology—CRYPTO’05 (LNCS), Vol. 3621. Springer, 241--257.

[41]

V. Kolesnikov and R. Kumaresan. 2013. Improved OT extension for transferring short secrets. In Advances in Cryptology—CRYPTO’13 (2) (LNCS), Vol. 8043. Springer, 54--70.

[42]

V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu. 2016. Efficient batched oblivious PRF with applications to private set intersection. In Computer and Communications Security (CCS’16). ACM, 818--829.

Digital Library

[43]

V. Kolesnikov and T. Schneider. 2008. Improved garbled circuit: Free XOR gates and applications. In International Colloquium on Automata, Languages and Programming (ICALP’08) (LNCS), Vol. 5126. Springer, 486--498.

[44]

M. Lambæk. 2016. Breaking and Fixing Private Set Intersection Protocols. Cryptology ePrint Archive, Report 2016/665. (2016). http://ia.cr/2016/665.

[45]

D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. 2004. Fairplay—A secure two-party computation system. In USENIX Security Symposium 2004. USENIX, 287--302.

[46]

C. Meadows. 1986. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In Symposium on Security and Privacy (S8P’86). IEEE, 134--137.

[47]

G. Mezzour, A. Perrig, V. D. Gligor, and P. Papadimitratos. 2009. Privacy-preserving relationship path discovery in social networks. In Cryptology and Network Security (CANS’09) (LNCS), Vol. 5888. Springer, 189--208.

Digital Library

[48]

M. D. Mitzenmacher. 2001. The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst. 12, 10 (2001), 1094--1104.

Digital Library

[49]

Robert H. Morelos-Zaragoza. 2006. The Art of Error Correcting Coding. Wiley, Hoboken (New Jersey), US. Code generation tools: http://eccpage.com.

[50]

R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press, New York, NY.

[51]

S. Nagaraja, P. Mittal, C.-Y. Hong, M. Caesar, and N. Borisov. 2010. BotGrep: Finding P2P bots with structured graph analysis. In USENIX Security Symposium 2010. USENIX, 95--110.

[52]

M. Nagy, E. De Cristofaro, A. Dmitrienko, N. Asokan, and A.-R. Sadeghi. 2013. Do I know you? -- Efficient and privacy-preserving common friend-finder protocols and applications. In Annual Computer Security Applications Conference (ACSAC’13). ACM, 159--168.

[53]

M. Naor and B. Pinkas. 2001. Efficient oblivious transfer protocols. In SIAM Symposium On Discrete Algorithms (SODA’01). Society for Industrial and Applied Mathematics (SIAM’01), 448--457.

[54]

A. Narayanan, N. Thiagarajan, M. Lakhani, M. Hamburg, and D. Boneh. 2011. Location privacy via private proximity testing. In Network and Distributed System Security (NDSS’11). The Internet Society.

[55]

J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra. 2012. A new approach to practical active-secure two-party computation. In Advances in Cryptology -- CRYPTO’12 (LNCS), Vol. 7417. Springer, 681--700.

Digital Library

[56]

NIST. 2012. NIST Special Publication 800-57, Recommendation for Key Management Part 1: General (Rev. 3). Technical Report. National Institute of Standards and Technology (NIST), Gaithersburg (Maryland), US.

[57]

O. Oksuz, I. Leontiadis, S. Chen, A. Russell, Q. Tang, and B. Wang. 2017. SEVDSI: Secure, Efficient and Verifiable Data Set Intersection. Cryptology ePrint Archive, Report 2017/215. (2017). http://ia.cr/2017/215.

[58]

M. Orrù, E. Orsini, and P. Scholl. 2017. Actively secure 1-out-of-N OT extension with application to private set intersection. In Topics in Cryptology—CT-RSA’17 (LNCS), Vol. 10159. Springer, 381--396.

[59]

R. Pagh and F. F. Rodler. 2001. Cuckoo hashing. In European Symposium on Algorithms (ESA’01) (LNCS), Vol. 2161. Springer, 121--133.

[60]

R. Pagh and F. F. Rodler. 2004. Cuckoo hashing. J. Algorithms 51, 2 (2004), 122--144.

Digital Library

[61]

B. Pinkas, T. Schneider, G. Segev, and M. Zohner. 2015. Phasing: Private set intersection using permutation-based hashing. In USENIX Security Symposium 2015. USENIX, 515--530. http://eprint.iacr.org/2015/634.

[62]

B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams. 2009. Secure two-party computation is practical. In Advances in Cryptology—ASIACRYPT’09 (LNCS), Vol. 5912. Springer, 250--267.

Digital Library

[63]

B. Pinkas, T. Schneider, and M. Zohner. 2014. Faster private set intersection based on OT extension. In USENIX Security Symposium 2014. USENIX, 797--812. http://eprint.iacr.org/2014/447.

[64]

M. Raab and A. Steger. 1998. “Balls into bins”—A simple and tight analysis. In Randomization and Approximation Techniques in Computer Science (RANDOM’98) (LNCS), Vol. 1518. Springer, 159--170.

[65]

P. Rindal and M. Rosulek. 2016. Faster malicious 2-party secure computation with online/offline dual execution. In USENIX Security Symposium 2016. USENIX.

[66]

P. Rindal and M. Rosulek. 2017a. Improved private set intersection against malicious adversaries. In Advances in Cryptology—EUROCRYPT’17 (LNCS), Vol. 10210. Springer, 235--259.

[67]

P. Rindal and M. Rosulek. 2017b. Malicious-secure private set intersection via dual execution. Forthcoming. In Computer and Communications Security (CCS’17). ACM.

Digital Library

[68]

T. Schneider and M. Zohner. 2013. GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In Financial Cryptography and Data Security (FC’13) (LNCS), Vol. 7859. Springer, 275--292.

[69]

R. Schürer and W. Schmid. 2006. Monte Carlo and Quasi-Monte Carlo Methods 2004. Springer, Chap. MinT: A Database for Optimal Net Parameters, 457--469.

[70]

A. Shamir. 1980. On the power of commutativity in cryptography. In International Colloquium on Automata, Languages and Programming (ICALP’80) (LNCS), Vol. 85. Springer, 582--595.

[71]

S. Tamrakar, J. Liu, A. Paverd, J.-E. Ekberg, B. Pinkas, and N. Asokan. 2017. The circle game: Scalable private membership test using trusted hardware. In Computer and Communications Security (ASIACCS’17). ACM, 31--44.

Digital Library

[72]

A. C. Yao. 1986. How to generate and exchange secrets. In Foundations of Computer Science (FOCS’86). IEEE, 162--167.

Digital Library

[73]

S. Zahur, M. Rosulek, and D. Evans. 2015. Two halves make a whole: Reducing data transfer in garbled circuits using half gates. In Advances in Cryptology—EUROCRYPT’15 (LNCS), Vol. 9057. Springer, 220--250.

Cited By

Yan JWei LQian XZhang L(2025)IDPriU: A two-party ID-private data union protocol for privacy-preserving machine learningJournal of Information Security and Applications10.1016/j.jisa.2024.10391388(103913)Online publication date: Feb-2025
https://doi.org/10.1016/j.jisa.2024.103913
Qiao MWei LHan DWu H(2025)Efficient multi-party PSI and its application in port managementComputer Standards & Interfaces10.1016/j.csi.2024.10388491:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.csi.2024.103884
Mu GZhang HLin JKong F(2025)SMCD: Privacy-preserving deep learning based malicious code detectionComputers & Security10.1016/j.cose.2024.104226150(104226)Online publication date: Mar-2025
https://doi.org/10.1016/j.cose.2024.104226
Show More Cited By

Index Terms

Scalable Private Set Intersection Based on OT Extension
1. Security and privacy
  1. Security services
    1. Privacy-preserving protocols

Recommendations

Faster private set intersection based on OT extension
SEC'14: Proceedings of the 23rd USENIX conference on Security Symposium

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 ...
Blazing Fast OT for Three-Round UC OT Extension
Public-Key Cryptography – PKC 2020
Abstract
Oblivious Transfer (OT) is an important building block for multi-party computation (MPC). Since OT requires expensive public-key operations, efficiency-conscious MPC protocols use an OT extension (OTE) mechanism [Beaver 96, Ishai et al. 03] to ...
Efficient Scalable Multi-party Private Set Intersection Using Oblivious PRF
Security and Trust Management
Abstract
In this paper, we present a concretely efficient protocol for private set intersection (PSI) in the multi-party setting using oblivious pseudorandom function (OPRF). In fact, we generalize the approach used in the work of Chase and Miao [CRYPTO ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Privacy and Security

ACM Transactions on Privacy and Security Volume 21, Issue 2

May 2018

159 pages

ISSN:2471-2566

EISSN:2471-2574

DOI:10.1145/3175499

Editor:
David Basin
ETH Zurich, Switzerland

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 January 2018

Accepted: 01 October 2017

Revised: 01 September 2017

Received: 01 September 2016

Published in TOPS Volume 21, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

European Union's 7th Framework Program (FP7/2007-2013)
German Federal Ministry of Education and Research (BMBF) within EC SPRIDE and CRISP
Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister's Office
Hessian LOEWE excellence initiative within CASED
BIU Center for Research in Applied Cryptography
National Science Foundation
DFG as part of Project E4 within the CRC 1119 CROSSING
Israel Ministry of Science and Technology

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

189
Total Citations
View Citations
3,432
Total Downloads

Downloads (Last 12 months)794
Downloads (Last 6 weeks)72

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yan JWei LQian XZhang L(2025)IDPriU: A two-party ID-private data union protocol for privacy-preserving machine learningJournal of Information Security and Applications10.1016/j.jisa.2024.10391388(103913)Online publication date: Feb-2025
https://doi.org/10.1016/j.jisa.2024.103913
Qiao MWei LHan DWu H(2025)Efficient multi-party PSI and its application in port managementComputer Standards & Interfaces10.1016/j.csi.2024.10388491:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.csi.2024.103884
Mu GZhang HLin JKong F(2025)SMCD: Privacy-preserving deep learning based malicious code detectionComputers & Security10.1016/j.cose.2024.104226150(104226)Online publication date: Mar-2025
https://doi.org/10.1016/j.cose.2024.104226
Pelosi G(2025)Privacy-Preserving Joins over Encrypted DataEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_1560(1942-1944)Online publication date: 8-Jan-2025
https://doi.org/10.1007/978-3-030-71522-9_1560
van Baarsen AStevens M(2024)Amortizing Circuit-PSI in the Multiple Sender/Receiver SettingIACR Communications in Cryptology10.62056/a0fhsgvtwOnline publication date: 7-Oct-2024
https://doi.org/10.62056/a0fhsgvtw
Hao MLiu WPeng LLi HZhang CChen HZhang TBalzarotti DXu W(2024)Unbalanced circuit-PSI from oblivious key-value retrievalProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699260(6435-6451)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699260
Yan XLian BYang YWang XCui JZhao XWang FChen K(2024)A Ciphertext Reduction Scheme for Garbling an S-Box in an AES Circuit with Minimal Online TimeSymmetry10.3390/sym1606066416:6(664)Online publication date: 28-May-2024
https://doi.org/10.3390/sym16060664
Wang ZMa X(2024)Blockchain-Based Unbalanced PSI with Public Verification and Financial SecurityMathematics10.3390/math1210154412:10(1544)Online publication date: 15-May-2024
https://doi.org/10.3390/math12101544
Chen YDing NGu DBian Y(2024)Practical multi-party private set intersection cardinality and intersection-sum protocols under arbitrary collusion1Journal of Computer Security10.3233/JCS-230091(1-41)Online publication date: 4-Apr-2024
https://doi.org/10.3233/JCS-230091
Zhang CChen YLiu WPeng LHao MWang AWang XLuo BLiao XXu JKirda ELie D(2024)Unbalanced Private Set Union with Reduced Computation and CommunicationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690308(1434-1447)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690308
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents