article

Efficient Set Intersection with Simulation-Based Security

Authors:

Michael J. Freedman,

Benny PinkasAuthors Info & Claims

Journal of Cryptology, Volume 29, Issue 1

Pages 115 - 155

https://doi.org/10.1007/s00145-014-9190-0

Published: 01 January 2016 Publication History

Abstract

We consider the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain. This problem has many applications for online collaboration. In this work, we present protocols based on the use of homomorphic encryption and different hashing schemes for both the semi-honest and malicious environments. The protocol for the semi-honest environment is secure in the standard model, while the protocol for the malicious environment is secure in the random oracle model. Our protocols obtain linear communication and computation overhead. We further implement different variants of our semi-honest protocol. Our experiments show that the asymptotic overhead of the protocol is affected by different constants. (In particular, the degree of the polynomials evaluated by the protocol matters less than the number of polynomials that are evaluated.) As a result, the protocol variant with the best asymptotic overhead is not necessarily preferable for inputs of reasonable size.

References

[1]

Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal.Balanced allocations. SIAM Journal on Computing, 29(1):180---200, 1999.

[2]

Proc. Twentieth Annual ACM Symposium on Theory of Computing, Chicago, Illinois, 2---4 May 1988.

[3]

Giuseppe Ateniese, Emiliano De Cristofaro, and Gene Tsudik. (if) size matters: Size-hiding private set intersection. In Dario Catalano, Nelly Fazio, Rosario Gennaro, and Antonio Nicolosi, editors, Public Key Cryptography, volume 6571 of Lecture Notes in Computer Science, pages 156---173. Springer, 2011.

[4]

Martin Aumller, Martin Dietzfelbinger, and Philipp Woelfel. Explicit and efficient hash families suffice for cuckoo hashing with a stash. 2012.

[5]

Bill Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: How to sell digital goods. In Advances in Cryptology---EUROCRYPT 2001, Innsbruck, Austria, May 2001.

[6]

Miklós Ajtai, János Kolmós, and Endre Szemerédi. An $$O(n \log n)$$O(nlogn) sorting network. In STOC, pages 1---9, 1983.

[7]

Yonatan Aumann and Yehuda Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. In Salil P. Vadhan, editor, TCC, volume 4392 of Lecture Notes in Computer Science, pages 137---156. Springer, 2007.

[8]

Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, pages 307---314, 32(1968).

Digital Library

[9]

Donald Beaver. Foundations of secure interactive computing. CRYPTO, 576:377---391, 1991.

[10]

Dan Boneh and Matthew K. Franklin. Efficient generation of shared rsa keys. J. ACM, 48(4):702---722, 2001.

Digital Library

[11]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In ACM {2}, pages 1---10.

[12]

Andrei Z. Broder and Michael Mitzenmacher. Using multiple hash functions to improve ip lookups. In IEEE INFOCOM 2001. 20th Ann. Joint Conference of the IEEE Computer and Communications Societies. Proceedings, 2001.

[13]

Fabrice Boudot, Berry Schoenmakers, and Jacques Traore. A fair and efficient solution to the socialist millionaires' problem. Discrete Applied Mathematics, 111(1-2):23---036, 2001.

[14]

Ran Canetti. Security and composition of multi-party cryptographic protocols. Journal of Cryptology, 13(1):143---202, 2000.

Digital Library

[15]

David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In ACM {2}, pages 11---19.

[16]

Jung Hee Cheon, Stanislaw Jarecki, and Jae Hong Seo. Multi-party privacy-preserving set intersection with quasi-linear complexity. Cryptology ePrint Archive, Report 2010/512, 2010.

[17]

David Chaum and Torben P. Pedersen. Wallet databases with observers. In CRYPTO, pages 89---105, 1992.

Digital Library

[18]

Jan Camenisch and Gregory M. Zaverucha. Private intersection of certified sets. In Roger Dingledine and Philippe Golle, editors, Financial Cryptography, volume 5628 of Lecture Notes in Computer Science, pages 108---127. Springer, 2009.

[19]

Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644---654, November 1976.

Digital Library

[20]

Ivan Damgård and Mads Jurik. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In 4th International Workshop on Practice and Theory in Public Key Cryptosystems (PKC 2001), pages 13---15, Cheju Island, Korea, February 2001.

[21]

Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In CRYPTO, pages 643---662, 2012.

Digital Library

[22]

Dana Dachman-Soled, Tal Malkin, Mariana Raykova, and Moti Yung. Efficient robust private set intersection. In Michel Abdalla, David Pointcheval, Pierre-Alain Fouque, and Damien Vergnaud, editors, ACNS, volume 5536 of Lecture Notes in Computer Science, pages 125---142, 2009.

[23]

Martin Dietzfelbinger and Philipp Woelfel. Almost random graphs with simple hash functions. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 629---638, 2003.

Digital Library

[24]

Ivan Damgård and Sarah Zakarias. Constant-overhead secure computation of boolean circuits using preprocessing. In TCC, pages 621---641, 2013.

Digital Library

[25]

Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proc. 22nd ACM Symposium on Principles of Database Systems (PODS 2003), pages 211---222, San Diego, CA, June 2003.

Digital Library

[26]

Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469---472, 1985.

Digital Library

[27]

Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. Keyword search and oblivious pseudorandom functions. In Joe Kilian, editor, TCC, volume 3378 of Lecture Notes in Computer Science, pages 303---324. Springer, 2005.

[28]

Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. Efficient private matching and set intersection. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology---EUROCRYPT 2004, volume 3027 of LNCS, pages 1---19. Springer-Verlag, 2---6 May 2004.

[29]

Ronald Fagin, Moni Naor, and Peter Winkler. Comparing information without leaking it. Communications of the ACM, 39(5):77---85, 1996.

Digital Library

[30]

Oded Goldreich and Ariel Kahan. How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology, 9(3):167---189, 1996.

Digital Library

[31]

Shafi Goldwasser and Leonid A. Levin. Fair computation of general functions in presence of immoral majority. CRYPTO, 537:77---93, 1990.

[32]

GMP. GNU Multiple Precision Arithmetic Library. gmplib.org, 2009.

[33]

Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proc. Nineteenth Annual ACM Symposium on Theory of Computing, pages 218---229, New York City, 25---27 May 1987.

[34]

Oded Goldreich. Foundations of cryptography: Basic applications. Cambridge Univ Pr, 2004.

[35]

Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities. In Proc. ACM Conference on Electronic Commerce, pages 78---86, Denver, Colorado, November 1999.

Digital Library

[36]

Carmit Hazay and Yehuda Lindell. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In TCC, pages 155---175, 2008.

Digital Library

[37]

Carmit Hazay, Gert LæssØe Mikkelsen, Tal Rabin, and Tomas Toft. Efficient rsa key generation and threshold paillier in the two-party setting. In CT-RSA, pages 313---331, 2012.

Digital Library

[38]

Carmit Hazay and Kobbi Nissim. Efficient set operations in the presence of malicious adversaries. In Public Key Cryptography, pages 312---331, 2010.

[39]

Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proc. 21st Annual ACM Symposium on Theory of Computing, pages 44---61, Seattle, Washington, May 1989.

[40]

Stanislaw Jarecki and Xiaomin Liu. Efficient oblivious pseudorandom function with applications to adaptive ot and secure computation of set intersection. TCC, 5444:577---594, 2009.

[41]

Stanislaw Jarecki and Xiaomin Liu. Fast secure computation of set intersection. SCN, 6280:418---435, 2010.

[42]

Stanislaw Jarecki and Vitaly Shmatikov. Efficient two-party secure computation on committed inputs. EUROCRYPT, 4515:97---114, 2007.

[43]

Adam Kirsch, Michael Mitzenmacher, and Udi Wieder. More robust hashing: Cuckoo hashing with a stash. In Proceedings of the 16th annual European symposium on Algorithms, pages 611---622. Springer, 2008.

Digital Library

[44]

Efficient password-authenticated key exchange using human-memorable passwords. In Advances in Cryptology - EUROCRYPT 2001, Innsbruck, Austria, May 6---10, 2001, pages 475---494, 2001.

[45]

Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discrete Mathematics, 5(4):545---557, 1992.

Digital Library

[46]

Lea Kissner and Dawn Song. Private and threshold set-intersection. In Proceedings of CRYPTO '05, August 2005.

[47]

Helger Lipmaa. Verifiable homomorphic oblivious transfer and private equality test. In Advances in Cryptology---ASIACRYPT 2003, pages 416---433, Taipei, Taiwan, November 2003.

[48]

Sven Laur and Helger Lipmaa. A new protocol for conditional disclosure of secrets and its applications. In ACNS, pages 207---225, 2007.

[49]

Yehuda Lindell and Benny Pinkas. A proof of security of yaos protocol for two-party computation. Journal of Cryptology, 22(2):161---188, 2009.

Digital Library

[50]

Yehuda Lindell and Benny Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. J. Cryptology, 25(4):680---722, 2012.

Digital Library

[51]

David Mazières. A toolkit for user-level file systems. In USENIX Technical Conference, June 2001.

Digital Library

[52]

Silvio Micali and Phillip Rogaway. Privacy preserving data mining. Unpublished manuscript, 576:392---404, 1991.

[53]

Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In Proc. 31st Annual ACM Symposium on Theory of Computing, pages 245---254, Atlanta, Georgia, May 1999.

Digital Library

[54]

Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In SIAM Symposium on Discrete Algorithms (SODA), pages 448---457, Washington, D.C., January 2001.

[55]

Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology---EUROCRYPT '99, pages 223---238, Prague, Czech Republic, May 1999.

[56]

Torben Pryds Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, Advances in Cryptology---CRYPTO '91, volume 576 of LNCS, pages 129---140. Springer-Verlag, 1992, 11---15 August 1991.

[57]

Anna Pagh and Rasmus Pagh. Uniform hashing in constant time and optimal space. SIAM J. Comput., 38(1):85---96, 2008.

Digital Library

[58]

Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122---144, 2004.

Digital Library

[59]

Mihai Patrascu and Mikkel Thorup. The power of simple tabulation hashing. J. ACM, 59(3):14, 2012.

Digital Library

[60]

Alexander A. Razborov. Application of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81---93, 1990.

[61]

Martin Raab and Angelika Steger. Balls into Bins - A Simple and Tight Analysis. Randomization and Approximation Techniques in Computer Science, pages 159---170, 1998.

[62]

Berthold Vöcking. How asymmetry helps load balancing. Journal of the ACM (JACM), 50:568---589, July 2003.

[63]

Udi Wieder. Balanced allocations with heterogenous bins. In Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, page 193. ACM, 2007.

[64]

Philipp Woelfel. Asymmetric balanced allocation with simple hash functions. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, SODA '06, pages 424---433, 2006.

Digital Library

[65]

Andrew C. Yao. Protocols for secure computations. In 23rd Annual Symposium on Foundations of Computer Science, pages 160---164, Chicago, Illinois, 3---5 November 1982. IEEE.

Digital Library

Cited By

Wang PLiu YLi ZLi R(2024)An LDP Compatible Sketch for Securely Approximating Set Intersection CardinalitiesProceedings of the ACM on Management of Data10.1145/36392812:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639281
Li JWang JZhang RXin YXu W(2024)NEMO: Practical Distributed Boolean Queries With Minimal LeakageIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.335143319(2594-2608)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3351433
Zhang YWang LZhou L(2024)Efficient Updateable Private Set Intersection on Outsourced DatasetsWeb and Big Data10.1007/978-981-97-7241-4_6(84-99)Online publication date: 31-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-7241-4_6
Show More Cited By

Index Terms

Efficient Set Intersection with Simulation-Based Security

Index terms have been assigned to the content through auto-classification.

Recommendations

Efficient Batched Oblivious PRF with Applications to Private Set Intersection
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

We describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semihonest adversaries. In an OPRF protocol a receiver has an input r; the sender gets output s and the receiver gets output F(s; r), where ...
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 ...
New Realizations of Efficient and Secure Private Set Intersection Protocols Preserving Fairness
ICISC 2016: Proceedings of the 19th International Conference on Information Security and Cryptology - Volume 10157

Private Set Intersection PSI is a useful cryptographic primitive for developing practical privacy preserving techniques for Big Data. PSI allows entities to securely extract intersection of the large data sets they own, without revealing any other ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Cryptology

Journal of Cryptology Volume 29, Issue 1

January 2016

241 pages

ISSN:0933-2790

Issue’s Table of Contents

Copyright © Copyright © 2016 International Association for Cryptologic Research.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2016

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang PLiu YLi ZLi R(2024)An LDP Compatible Sketch for Securely Approximating Set Intersection CardinalitiesProceedings of the ACM on Management of Data10.1145/36392812:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639281
Li JWang JZhang RXin YXu W(2024)NEMO: Practical Distributed Boolean Queries With Minimal LeakageIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.335143319(2594-2608)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2024.3351433
Zhang YWang LZhou L(2024)Efficient Updateable Private Set Intersection on Outsourced DatasetsWeb and Big Data10.1007/978-981-97-7241-4_6(84-99)Online publication date: 31-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-7241-4_6
Carpent XHwang STsudik G(2024)Element Distinctness and Bounded Input Size in Private Set Intersection and Related ProtocolsApplied Cryptography and Network Security10.1007/978-3-031-54770-6_2(26-57)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54770-6_2
Purcell MLi YNg KEvans RShpitser I(2023)Split, count, and shareProceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence10.5555/3625834.3625992(1684-1694)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.5555/3625834.3625992
Badrinarayanan SKumaresan RChristodorescu MNagaraja VPatel KRaghuraman SRindal PSun WXu M(2023)A Plug-n-Play Framework for Scaling Private Set Intersection to Billion-Sized SetsCryptology and Network Security10.1007/978-981-99-7563-1_20(443-467)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1007/978-981-99-7563-1_20
Zhou QLai CGuo QMa HZheng D(2022)A novel privacy protection scheme for internet of things based on blockchain and privacy set intersection techniqueJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-022-00375-611:1Online publication date: 15-Dec-2022
https://dl.acm.org/doi/10.1186/s13677-022-00375-6
Yu XLi FZhao WDai ZTang D(2022)Multiparty Threshold Private Set Intersection Protocol with Low Communication ComplexitySecurity and Communication Networks10.1155/2022/92455162022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/9245516
Elkordy AEzzeldin YAvestimehr SAl Hasan MXiong L(2022)Federated K-Private Set IntersectionProceedings of the 31st ACM International Conference on Information & Knowledge Management10.1145/3511808.3557321(436-445)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3511808.3557321
Ma JChow SSuga YSakurai KDing XSako K(2022)Secure-Computation-Friendly Private Set Intersection from Oblivious Compact Graph EvaluationProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security10.1145/3488932.3501278(1086-1097)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3488932.3501278
Show More Cited By

View Options

View options

Get Access

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents