More Web Proxy on the site http://driver.im/

Article

Efficient Scalable Multi-party Private Set Intersection Using Oblivious PRF

Authors:

Alireza Kavousi,

Javad Mohajeri,

Mahmoud SalmasizadehAuthors Info & Claims

Security and Trust Management: 17th International Workshop, STM 2021, Darmstadt, Germany, October 8, 2021, Proceedings

Pages 81 - 99

https://doi.org/10.1007/978-3-030-91859-0_5

Published: 08 October 2021 Publication History

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 2020] towards deploying a lightweight multi-point OPRF construction for two-party PSI. Our protocol only includes oblivious transfer (OT) extension and garbled Bloom filter as its main ingredients and avoids computationally expensive operations. From a communication pattern perspective, the protocol consists of two types of interactions. The first type is performed over a star-like communication graph in which one designated party interacts with all other parties via performing OTs as the sender. Besides, parties communicate through a path-like communication graph that involves sending a garbled Bloom filter from the first party to its neighboring party following the last one. This design makes our protocol to be highly scalable due to the independence of each party’s complexity from the number of participating parties and thus causes a communication and computation complexities of

O (n λ k)

, where n is the set size, k is the number of hash functions, and

λ

is the security parameter. Moreover, the asymptotic complexity of the designated party is

O (t n λ)

which linearly scales with the number of parties t. We prove security of the proposed protocol against semi-honest adversaries.

References

[1]

Abadi A, Terzis S, Metere R, and Dong C Efficient delegated private set intersection on outsourced private datasets IEEE Trans. Dependable Secure Comput. 2017 16 4 608-624

[2]

Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: Proceedings of the 2013 ACM Conference on Computer and Communications Security, pp. 535–548 (2013)

[3]

Abadi, A., Terzis, S., Dong, C.: Feather: lightweight multi-party updatable delegated private set intersection. Cryptology ePrint Archive, 2020/407 (2020). https://eprint.iacr.org/2020/407

[4]

Badrinarayanan, S., Miao, P., Raghuraman, S., Rindal, P.: Multi-party threshold private set intersection with sublinear communication. Cryptology ePrint Archive, 2020/600 (2020). https://eprint.iacr.org/2020/600

[5]

Branco, P., Döttling, N., Pu, S.: Multiparty cardinality testing for threshold private set intersection. Cryptology ePrint Archive, 2020/1307 (2020). https://eprint.iacr.org/2020/1307

[6]

Bloom BH Space/time trade-offs in hash coding with allowable errors Commun. ACM 1970 13 7 422-426

[7]

Buddhavarapu, P., Knox, A., Mohassel, P., Sengupta, S., Taubeneck, E., Vlaskin, V.: Private matching for compute. Cryptology ePrint Archive, 2020/599 (2020). https://eprint.iacr.org/2020/599

[8]

Chase M and Miao P Micciancio D and Ristenpart T Private set intersection in the internet setting from lightweight oblivious PRF Advances in Cryptology – CRYPTO 2020 2020 Cham Springer 34-63

[9]

Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: Proceedings of the 2013 ACM Conference on Computer and Communications Security, pp. 789–800 (2013)

[10]

Demmler D, Rindal P, Rosulek M, and Trieu N PIR-PSI: scaling private contact discovery Proc. Priv. Enhanc. Technol. 2018 2018 4 159-178

[11]

Dittmer, S., et al.: Function secret sharing for PSI-CA: with applications to private contact tracing. Cryptology ePrint Archive, 2020/1599 (2020). https://eprint.iacr.org/2020/1599

[12]

Duong T, Phan DH, and Trieu N Moriai S and Wang H Catalic: delegated PSI cardinality with applications to contact tracing Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 870-899

[13]

De Cristofaro E and Tsudik G Sion R Practical private set intersection protocols with linear complexity Financial Cryptography and Data Security 2010 Heidelberg Springer 143-159

[14]

De Cristofaro E and Tsudik G Katzenbeisser S, Weippl E, Camp LJ, Volkamer M, Reiter M, and Zhang X Experimenting with fast private set intersection Trust and Trustworthy Computing 2012 Heidelberg Springer 55-73

[15]

Efraim, A.B., Nissenbaum, O., Omri, E., Paskin-Cherniavsky, A.: Psimple: practical multiparty maliciously-secure private set intersection. Cryptology ePrint Archive, 2021/122 (2021). https://eprint.iacr.org/2021/122

[16]

Freedman MJ, Nissim K, and Pinkas B Cachin C and Camenisch JL Efficient private matching and set intersection Advances in Cryptology - EUROCRYPT 2004 2004 Heidelberg Springer 1-19

[17]

Freedman MJ, Ishai Y, Pinkas B, and Reingold O Kilian J Keyword search and oblivious pseudorandom functions Theory of Cryptography 2005 Heidelberg Springer 303-324

[18]

Ghosh S and Nilges T Ishai Y and Rijmen V An algebraic approach to maliciously secure private set intersection Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 154-185

[19]

Goldreich, O.: Foundations of Cryptography: Volume 2, Basic Applications (2004)

[20]

Ghosh S and Simkin M Boldyreva A and Micciancio D The communication complexity of threshold private set intersection Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 3-29

[21]

Halevi, S.: Advanced cryptography: promise and challenges. In: ACM Conference on Computer and Communications Security, p. 647 (2018)

[22]

Hazay C Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs J. Cryptol. 2018 31 2 537-586

[23]

Huang, Y., Evans, D., Katz, J.: Private set intersection: are garbled circuits better than custom protocols? In: NDSS (2012)

[24]

Hazay C and Venkitasubramaniam M Fehr S Scalable multi-party private set-intersection Public-Key Cryptography – PKC 2017 2017 Heidelberg Springer 175-203

[25]

Inbar R, Omri E, and Pinkas B Catalano D and De Prisco R Efficient scalable multiparty private set-intersection via garbled bloom filters Security and Cryptography for Networks 2018 Cham Springer 235-252

[26]

Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 44–61 (1989)

[27]

Ishai Y, Kilian J, Nissim K, and Petrank E Boneh D Extending oblivious transfers efficiently Advances in Cryptology - CRYPTO 2003 2003 Heidelberg Springer 145-161

[28]

Kales, D., Rechberger, C., Schneider, T., Senker, M., Weinert, C.: Mobile private contact discovery at scale. In: 28th

{

USENIX

}

Security Symposium (

{

USENIX

}

Security 2019), pp. 1447–1464 (2019)

[29]

Kolesnikov V and Kumaresan R Canetti R and Garay JA Improved OT extension for transferring short secrets Advances in Cryptology – CRYPTO 2013 2013 Heidelberg Springer 54-70

[30]

Kavousi, A., Mohajeri, J., Salmasizadeh, M.: Improved secure efficient delegated private set intersection. In: 2020 28th Iranian Conference on Electrical Engineering (ICEE), pp. 1–6. IEEE (2020)

[31]

Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: Proceedings of the 2016 ACM Conference on Computer and Communications Security, pp. 818–829 (2016)

[32]

Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: Proceedings of the 2017 ACM Conference on Computer and Communications Security, pp. 1257–1272 (2017)

[33]

Miao P, Patel S, Raykova M, Seth K, and Yung M Micciancio D and Ristenpart T Two-sided malicious security for private intersection-sum with cardinality Advances in Cryptology – CRYPTO 2020 2020 Cham Springer 3-33

[34]

Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: 24th

{

USENIX

}

Security Symposium (

{

USENIX

}

Security 2015), pp. 515–530 (2015)

[35]

Pinkas B, Schneider T, Weinert C, and Wieder U Nielsen JB and Rijmen V Efficient circuit-based PSI via cuckoo hashing Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 125-157

[36]

Pinkas B, Rosulek M, Trieu N, and Yanai A Boldyreva A and Micciancio D SpOT-Light: lightweight private set intersection from sparse OT extension Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 401-431

[37]

Pinkas B, Schneider T, Tkachenko O, and Yanai A Ishai Y and Rijmen V Efficient circuit-based PSI with linear communication Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 122-153

[38]

Pinkas B, Rosulek M, Trieu N, and Yanai A Canteaut A and Ishai Y PSI from PaXoS: fast, malicious private set intersection Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 739-767

[39]

Pagh R and Rodle FF Cuckoo hashing J. Algorithms 2004 51 2 122-144

[40]

Pinkas B, Schneider T, and Zohner M Scalable private set intersection based on OT extension ACM Trans. Priv. Secur. (TOPS) 2018 21 2 1-35

[41]

Rabin, M.O.: How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, 2005/187 (2005). https://eprint.iacr.org/2005/187

[42]

Rindal, P., Rosulek, M.: Faster malicious 2-party secure computation with online/offline dual execution. In: 25th

{

USENIX

}

Security Symposium (

{

USENIX

}

Security 2016), pp. 297–314 (2016)

[43]

Shamir A How to share a secret Commun. ACM 1979 22 11 612-613

[44]

Ying, J.H.M., Cao, S., Poh, G.S., Xu, J., Lim, H.W.: PSI-stats: private set intersection protocols supporting secure statistical functions. Cryptology ePrint Archive, 2020/623 (2020). https://eprint.iacr.org/2020/623

[45]

Zhao, Y., Chow, S.S.M.: Can you find the one for me? In: Proceedings of the 2018 Workshop on Privacy in the Electronic Society, pp. 54–65 (2018)

[46]

Zhang, E., Liu, F.-H., Lai, Q., Jin, G., Li, Y.: Efficient multi-party private set intersection against malicious adversaries. In: Proceedings of the 2019 ACM Conference on Cloud Computing Security Workshop, pp. 93–104 (2019)

Cited By

Ma LWang HNiu ZLi ZWu LWei XSu Y(2024)Over-threshold multi-party private set operation protocols for lightweight clientsComputer Standards & Interfaces10.1016/j.csi.2023.10378188:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.csi.2023.103781
Zhang QYan XDing YXu QHu CZhou XJiang J(2024)TreeCSS: An Efficient Framework for Vertical Federated LearningDatabase Systems for Advanced Applications10.1007/978-981-97-5552-3_29(425-441)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5552-3_29
Avizheh SSafavi-Naini R(2024)Fair Private Set Intersection Using Smart ContractsApplied Cryptography and Network Security10.1007/978-3-031-54776-8_4(74-104)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54776-8_4

Index Terms

Efficient Scalable Multi-party Private Set Intersection Using Oblivious PRF
1. Security and privacy
  1. Cryptography
2. Theory of computation

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 Multiparty Private Set-Intersection via Garbled Bloom Filters
Security and Cryptography for Networks
Abstract
In private set intersection (PSI), a set of parties, each holding a private data set, wish to compute the intersection over all data sets in a manner that guarantees both correctness and privacy. This secure computation task is of great importance ...
Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Security and Trust Management: 17th International Workshop, STM 2021, Darmstadt, Germany, October 8, 2021, Proceedings

Oct 2021

207 pages

ISBN:978-3-030-91858-3

DOI:10.1007/978-3-030-91859-0

Editors:
Rodrigo Roman
University of Málaga, Málaga, Spain
,
Jianying Zhou
Singapore University of Technology and Design, Singapore, Singapore

© Springer Nature Switzerland AG 2021.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 October 2021

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ma LWang HNiu ZLi ZWu LWei XSu Y(2024)Over-threshold multi-party private set operation protocols for lightweight clientsComputer Standards & Interfaces10.1016/j.csi.2023.10378188:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.csi.2023.103781
Zhang QYan XDing YXu QHu CZhou XJiang J(2024)TreeCSS: An Efficient Framework for Vertical Federated LearningDatabase Systems for Advanced Applications10.1007/978-981-97-5552-3_29(425-441)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5552-3_29
Avizheh SSafavi-Naini R(2024)Fair Private Set Intersection Using Smart ContractsApplied Cryptography and Network Security10.1007/978-3-031-54776-8_4(74-104)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54776-8_4

View Options

View options

Media

Figures

Other

Tables

View Table of Contents