research-article

Collusion-resistant outsourcing of private set intersection

Author:

Florian KerschbaumAuthors Info & Claims

SAC '12: Proceedings of the 27th Annual ACM Symposium on Applied Computing

Pages 1451 - 1456

https://doi.org/10.1145/2245276.2232008

Published: 26 March 2012 Publication History

Abstract

Set intersection is a building block for many data analysis techniques, e.g. in data mining. Private set intersection enables to compute the set intersection without revealing the non-matching items. The advent of cloud computing drives the desire to outsource such computations, but without the need to trust the service provider. Homomorphic encryption enables secure, outsourced computations, but in case of multiple clients cannot prevent collusion.

In this paper we present non-interactive, encrypted computation of the set intersection using an untrusted service provider. Two or more clients submit their encrypted sets to the service provider which facilitates the computation of their intersection. The service provider either learns the intersection or remains completely obvious to both input and output - including the intersection's size. We prove our protocols secure in the random oracle model and under the RSA assumption. Our prototypical implementation shows the difference between the protocols using different cryptographic techniques and that even a fully untrusted service provider can be practically feasible.

References

[1]

G. Ateniese, E. De Cristofaro, and G. Tsudik. (If) Size Matters: Size-Hiding Private Set Intersection. Proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography, 2011.

Digital Library

[2]

M. Bellare, A. Boldyreva, and A. OŠNeill. Deterministic and Efficiently Searchable Encryption. Proceedings of CRYPTO, 2007.

Digital Library

[3]

D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano. Public Key Encryption with Keyword Search. Proceedings of EUROCRYPT, 2004.

[4]

D. Boneh, and M. Franklin. Efficient Generation of Shared RSA Keys. Journal of the ACM 48(4), 2001.

Digital Library

[5]

D. Boneh, E. Goh, and K. Nissim. Evaluating 2-DNF Formulas on Ciphertexts. Proceedings of the 2nd Theory of Cryptography Conference, 2005.

Digital Library

[6]

D. Chaum. Blind Signatures for Untraceable Payments. Proceedings of CRYPTO, 1983.

[7]

K. Chung, Y. Kalai, and S. Vadhan. Improved Delegation of Computation Using Fully Homomorphic Encryption. Proceedings of CRYPTO, 2010.

Digital Library

[8]

D. Dachman-Soled, T. Malkin, M. Raykova, and Moti Yung. Efficient Robust Private Set Intersection. Proceedings of the 7th International Conference on Applied Cryptography and Network Security, 2009.

Digital Library

[9]

E. De Cristofaro, J. Kim, and G. Tsudik. Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model. Proceedings of ASIACRYPT, 2010.

[10]

E. De Cristofaro, Y. Lu, and G. Tsudik. Efficient Techniques for Privacy-preserving Sharing of Sensitive Information. Proceedings of the International Conference on Trust and Trustworthy Computing, 2011.

Digital Library

[11]

E. De Cristofaro, and G. Tsudik. Practical Private Set Intersection Protocols with Linear Complexity. Proceedings of the 14th International Conference on Financial Cryptography and Data Security, 2010.

Digital Library

[12]

M. Van Dijk, and A. Juels. On the Impossibility of Cryptography Alone for Privacy-Preserving Cloud Computing. Proceedings of the 5th USENIX Conference on Hot Topics in Security, 2010.

Digital Library

[13]

Y. Frankel, P. MacKenzie, and M. Yung. Robust Efficient Distributed RSA-Key Generation. Proceedings of the 30th ACM Aymposium on Theory of Computing, 1998.

Digital Library

[14]

M. Freedman, Y. Ishai, B. Pinkas, and O. Reingold. Keyword Search and Oblivious Pseudorandom Functions. Proceedings of the 2nd Theory of Cryptography Conference, 2005.

Digital Library

[15]

M. Freedman, K. Nissim, and B. Pinkas. Efficient Private Matching and Set Intersection. Proceedings of EUROCRYPT, 2004.

[16]

H. Garcia-Molina, J. Ullman, and J. Widom. Database Systems: The Complete Book. Prentice Hall, 2008.

Digital Library

[17]

R. Gennaro, C. Gentry, and B. Parno. Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers. Proceedings of CRYPTO, 2010.

Digital Library

[18]

C. Gentry. Fully Homomorphic Encryption using Ideal Lattices. Proceedings of the 41st ACM Symposium on Theory of Computing, 2009.

Digital Library

[19]

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

Digital Library

[20]

S. Goldwasser, and S. Micali. Probabilistic Encryption. Journal of Computer and Systems Science 28(2), 1984.

[21]

H. Hacigümüs, B. Iyer, C. Li, and S. Mehrotra. Executing SQL over Encrypted Data in the Database-Service-Provider Model. Proceedings of the ACM Symposium on Principles Database and Systems, 2002.

Digital Library

[22]

H. Hacigümüs, S. Mehrotra, and B. Iyer. Providing Database as a Service. Proceedings of the IEEE International Conference on Data Engineering, 2002.

Digital Library

[23]

C. Hazay, and Y. Lindell. Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries. Proceedings of the 5th Theory of Cryptography Conference, 2008.

Digital Library

[24]

C. Hazay, and K. Nissim. Efficient Set Operations in the Presence of Malicious Adversaries. Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography, 2010.

Digital Library

[25]

S. Jarecki and X. Liu. Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection. Proceedings of the 6th Theory of Cryptography Conference, 2009.

Digital Library

[26]

L. Kissner, and D. Song. Privacy-Preserving Set Operations. Proceedings of CRYPTO, 2005.

Digital Library

[27]

M. Naor, and B. Pinkas. Oblivious Transfer and Polynomial Evaluation. Proceedings of the 31st Symposium on Theory of Computer Science, 1999.

Digital Library

[28]

P. Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Proceedings of EUROCRYPT, 1999.

Digital Library

[29]

M. Raykova, B. Vo, S. Bellovin, and T. Malkin. Secure Anonymous Database Search. Proceedings of the ACM Cloud Computing Security Workshop, 2009.

Digital Library

[30]

R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21(2), 1978.

Digital Library

[31]

D. Song, D. Wagner, and A. Perrig. Practical Techniques for Searches on Encrypted Data. Proceedings of IEEE Symposium on Security and Privacy, 2000.

Digital Library

[32]

P. Tan, M. Steinbach, and V. Kumar. Introduction to Data Mining. Addison-Wesley, 2005.

Digital Library

[33]

J. Vaidya, C. Clifton, and Y. Zhu. Privacy Preserving Data Mining. Sprinter - Advances in Information Security 19, 2006.

[34]

A. Yao. Protocols for Secure Computations. Proceedings of the IEEE Symposium on Foundations of Computer Science, 1982.

Digital Library

Cited By

Li XWang HLi ZWu LWei XSu YLu R(2024)Publicly Verifiable Secure Multi-Party Computation Framework Based on Bulletin BoardIEEE Transactions on Services Computing10.1109/TSC.2024.338025817:4(1698-1711)Online publication date: Jul-2024
https://doi.org/10.1109/TSC.2024.3380258
Sharma SLi YMehrotra SPanwar NGupta PGhosh D(2024) Prism: Pr ivacy-Preserving and Ver i fiable S et Computation Over M ulti-Owner Secret Shared Outsourced Databases IEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.327935621:3(1355-1371)Online publication date: May-2024
https://doi.org/10.1109/TDSC.2023.3279356
Chen QChai ZWang ZYan HLin XZhou J(2024)QP-LDP for Better Global Model Performance in Federated LearningIEEE Internet of Things Journal10.1109/JIOT.2024.339531011:15(25968-25981)Online publication date: 1-Aug-2024
https://doi.org/10.1109/JIOT.2024.3395310
Show More Cited By

Index Terms

Collusion-resistant outsourcing of private set intersection

Recommendations

Outsourced private set intersection using homomorphic encryption
ASIACCS '12: Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security

Private set intersection enables two parties -- a client and a server -- to compute the intersection of their respective sets without disclosing anything else. It is a fundamental operation -- equivalent to a secure, distributed database join -- and has ...
Server-aided anonymous attribute-based authentication in cloud computing

The notion of attribute-based signature is one of the important security primitives to realize anonymous authentication. In an attribute based signature (ABS), users can generate a signature on a message with their attributes. With this signature, any ...
Bilinear-map accumulator-based verifiable intersection operations on encrypted data in cloud

The intersection operation on multisets has many applications in different scenarios, such as data mining and pattern matching. This motivates us to study the problem that when users outsource their private encrypted sets and delegate the set-...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '12: Proceedings of the 27th Annual ACM Symposium on Applied Computing

March 2012

2179 pages

ISBN:9781450308571

DOI:10.1145/2245276

Conference Chairs:
Sascha Ossowski
University Rey Juan Carlos, Spain
,
Paola Lecca
The Microsoft Research - University of Trento COSBI, Italy

Copyright © 2012 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 ACM 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]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 March 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC 2012

Sponsor:

SIGAPP

SAC 2012: ACM Symposium on Applied Computing

March 26 - 30, 2012

Trento, Italy

Acceptance Rates

SAC '12 Paper Acceptance Rate 270 of 1,056 submissions, 26%;

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
364
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)2

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li XWang HLi ZWu LWei XSu YLu R(2024)Publicly Verifiable Secure Multi-Party Computation Framework Based on Bulletin BoardIEEE Transactions on Services Computing10.1109/TSC.2024.338025817:4(1698-1711)Online publication date: Jul-2024
https://doi.org/10.1109/TSC.2024.3380258
Sharma SLi YMehrotra SPanwar NGupta PGhosh D(2024) Prism: Pr ivacy-Preserving and Ver i fiable S et Computation Over M ulti-Owner Secret Shared Outsourced Databases IEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.327935621:3(1355-1371)Online publication date: May-2024
https://doi.org/10.1109/TDSC.2023.3279356
Chen QChai ZWang ZYan HLin XZhou J(2024)QP-LDP for Better Global Model Performance in Federated LearningIEEE Internet of Things Journal10.1109/JIOT.2024.339531011:15(25968-25981)Online publication date: 1-Aug-2024
https://doi.org/10.1109/JIOT.2024.3395310
Lai CZhang HLu RZheng D(2024)Privacy-Preserving Medical Data Sharing Scheme Based on Two-Party Cloud-Assisted PSIIEEE Internet of Things Journal10.1109/JIOT.2024.335002911:9(15855-15868)Online publication date: 1-May-2024
https://doi.org/10.1109/JIOT.2024.3350029
Jiang GZhang HLin JKong FYu L(2024)Optimized verifiable delegated private set intersection on outsourced private datasetsComputers & Security10.1016/j.cose.2024.103822(103822)Online publication date: Mar-2024
https://doi.org/10.1016/j.cose.2024.103822
Wang YWang ZMa XHe J(2024)Two-Round Private Set Intersection Mechanism and Algorithm Based on BlockchainDigital Forensics and Watermarking10.1007/978-981-97-2585-4_18(248-261)Online publication date: 25-Apr-2024
https://doi.org/10.1007/978-981-97-2585-4_18
Fan CJia PLin MWei LGuo PZhao XLiu X(2023)Cloud-Assisted Private Set Intersection via Multi-Key Fully Homomorphic EncryptionMathematics10.3390/math1108178411:8(1784)Online publication date: 8-Apr-2023
https://doi.org/10.3390/math11081784
Wang ZXu YLiu JLi ZLi ZJia HWang D(2022)An Efficient Data Sharing Scheme for Privacy Protection Based on Blockchain and Edge Intelligence in 6G-VANETWireless Communications & Mobile Computing10.1155/2022/50311122022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/5031112
Ruan OZeng J(2022)A Delegated Offline Private Set Intersection Protocol for Cloud Computing EnvironmentsProceedings of the 2022 2nd International Conference on Control and Intelligent Robotics10.1145/3548608.3559297(735-739)Online publication date: 24-Jun-2022
https://dl.acm.org/doi/10.1145/3548608.3559297
Chen QChai ZWang ZChen JYan HLin X(2022)QP-LDP for better global model performance in federated learning2022 18th International Conference on Mobility, Sensing and Networking (MSN)10.1109/MSN57253.2022.00074(422-426)Online publication date: Dec-2022
https://doi.org/10.1109/MSN57253.2022.00074
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents