Amortizing Circuit-PSI in the Multiple Sender/Receiver Setting
Authors
Aron van Baarsen, Marc Stevens
Abstract
Private set intersection (PSI) is a cryptographic functionality for two parties to learn the intersection of their input sets, without leaking any other information. Circuit-PSI is a stronger PSI functionality where the parties learn only a secret-shared form of the desired intersection, thus without revealing the intersection directly. These secret shares can subsequently serve as input to a secure multiparty computation of any function on this intersection.
In this paper we consider several settings in which parties take part in multiple Circuit-PSI executions with the same input set, and aim to amortize communications and computations. To that end, we build up a new framework for Circuit-PSI around generalizations of oblivious (programmable) PRFs that are extended with offline setup phases. We present several efficient instantiations of this framework with new security proofs for this setting. As a side result, we obtain a slight improvement in communication and computation complexity over the state-of-the-art semi-honest Circuit-PSI protocol by Bienstock et al. (USENIX '23). Additionally, we present a novel Circuit-PSI protocol from a PRF with secret-shared outputs, which has linear communication and computation complexity in the parties' input set sizes, and is able to realize a stronger security notion. Lastly, we derive the potential amortizations over multiple protocol executions, and observe that each of the presented instantiations is favorable in at least one of the multiple-execution settings.
References
[AES03]
Rakesh Agrawal, Alexandre Evfimievski, and Ramakrishnan Srikant. Information sharing across private databases. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pages 86–97. 2003. DOI: 10.1145/872757.872771
[AFMP20]
Navid Alamati, Luca De Feo, Hart Montgomery, and Sikhar Patranabis. Cryptographic Group Actions and Applications. In ASIACRYPT (2), volume 12492 of Lecture Notes in Computer Science, pages 411–439. 2020. Springer. DOI: 10.1007/978-3-030-64834-3_14
[AGR+16]
Martin R. Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. In ASIACRYPT (1), volume 10031 of Lecture Notes in Computer Science, pages 191–219. 2016. DOI: 10.1007/978-3-662-53887-6_7
[ARS+15]
Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In EUROCRYPT (1), volume 9056 of Lecture Notes in Computer Science, pages 430–454. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_17
[BBD+24]
Jeremy Booher, Ross Bowden, Javad Doliskani, Tako Boris Fouotsa, Steven D. Galbraith, Sabrina Kunzweiler, Simon-Philipp Merz, Christophe Petit, Benjamin Smith, Katherine E. Stange, Yan Bo Ti, Christelle Vincent, José Felipe Voloch, Charlotte Weitkämper, and Lukas Zobernig. Failing to Hash Into Supersingular Isogeny Graphs. Comput. J., 67(8):2702–2719, 2024. DOI: 10.1093/COMJNL/BXAE038
[BC23]
Dung Bui and Geoffroy Couteau. Improved Private Set Intersection for Sets with Small Entries. In Public Key Cryptography (2), volume 13941 of Lecture Notes in Computer Science, pages 190–220. 2023. Springer. DOI: 10.1007/978-3-031-31371-4_7
[BCG+19a]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation. In CCS, pages 291–308. 2019. ACM. DOI: 10.1145/3319535.3354255
[BCG+19b]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient Pseudorandom Correlation Generators: Silent OT Extension and More. In CRYPTO (3), volume 11694 of Lecture Notes in Computer Science, pages 489–518. 2019. Springer. DOI: 10.1007/978-3-030-26954-8_16
[BCG+20]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient Pseudorandom Correlation Generators from Ring-LPN. In CRYPTO (2), volume 12171 of Lecture Notes in Computer Science, pages 387–416. 2020. Springer. DOI: 10.1007/978-3-030-56880-1_14
[BCGI18]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing Vector OLE. In CCS, pages 896–912. 2018. ACM. DOI: 10.1145/3243734.3243868
[BDD20]
Carsten Baum, Bernardo David, and Rafael Dowsley. Insured MPC: Efficient Secure Computation with Financial Penalties. In Financial Cryptography, volume 12059 of Lecture Notes in Computer Science, pages 404–420. 2020. Springer. DOI: 10.1007/978-3-030-51280-4_22
[BGM16]
Iddo Bentov, Ariel Gabizon, and Alex Mizrahi. Cryptocurrencies Without Proof of Work. In Financial Cryptography Workshops, volume 9604 of Lecture Notes in Computer Science, pages 142–157. 2016. Springer. DOI: 10.1007/978-3-662-53357-4_10
[Bia10]
Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Adv. Math. Commun., 4(2):141–154, 2010. DOI: 10.3934/AMC.2010.4.141
[BIM00]
Amos Beimel, Yuval Ishai, and Tal Malkin. Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing. In CRYPTO, volume 1880 of Lecture Notes in Computer Science, pages 55–73. 2000. Springer. DOI: 10.1007/3-540-44598-6_4
[BKV19]
Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. CSI-FiSh: Efficient Isogeny Based Signatures Through Class Group Computations. In ASIACRYPT (1), volume 11921 of Lecture Notes in Computer Science, pages 227–247. 2019. Springer. DOI: 10.1007/978-3-030-34578-5_9
[BM82]
Manuel Blum and Silvio Micali. How to Generate Cryptographically Strong Sequences of Pseudo Random Bits. In FOCS, pages 112–117. 1982. IEEE Computer Society. DOI: 10.1109/SFCS.1982.72
[BPSY23]
Alexander Bienstock, Sarvar Patel, Joon Young Seo, and Kevin Yeo. Near-Optimal Oblivious Key-Value Stores for Efficient PSI, PSU and Volume-Hiding Multi-Maps. In USENIX Security Symposium. 2023. USENIX Association.
[CDG+21]
Nishanth Chandran, Nishka Dasgupta, Divya Gupta, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar, and Akash Shah. Efficient Linear Multiparty PSI and Extensions to Circuit/Quorum PSI. In CCS, pages 1182–1204. 2021. ACM. DOI: 10.1145/3460120.3484591
[CDJ16]
Chongwon Cho, Dana Dachman-Soled, and Stanislaw Jarecki. Efficient Concurrent Covert Computation of String Equality and Set Intersection. In CT-RSA, volume 9610 of Lecture Notes in Computer Science, pages 164–179. 2016. Springer. DOI: 10.1007/978-3-319-29485-8_10
[CGJ+17]
Arka Rai Choudhuri, Matthew Green, Abhishek Jain, Gabriel Kaptchuk, and Ian Miers. Fairness in an Unfair World: Fair Multiparty Computation from Public Bulletin Boards. In CCS, pages 719–728. 2017. ACM. DOI: 10.1145/3133956.3134092
[CGS22]
Nishanth Chandran, Divya Gupta, and Akash Shah. Circuit-PSI With Linear Complexity via Relaxed Batch OPPRF. Proc. Priv. Enhancing Technol., 2022(1):353–372, 2022. DOI: 10.2478/POPETS-2022-0018
[CHL05]
Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. Compact E-Cash. In EUROCRYPT, volume 3494 of Lecture Notes in Computer Science, pages 302–321. 2005. Springer. DOI: 10.1007/11426639_18
[CHLR18]
Hao Chen, Zhicong Huang, Kim Laine, and Peter Rindal. Labeled PSI from Fully Homomorphic Encryption with Malicious Security. In CCS, pages 1223–1237. 2018. ACM. DOI: 10.1145/3243734.3243836
[CLM+18]
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. CSIDH: An Efficient Post-Quantum Commutative Group Action. In ASIACRYPT (3), volume 11274 of Lecture Notes in Computer Science, pages 395–427. 2018. Springer. DOI: 10.1007/978-3-030-03332-3_15
[Clo18]
Cloudflare. Nimbus. Accessed: 10-10-2023. https://blog.cloudflare.com/introducing-certificate-transparency-and-nimbus/. 2018.
[CLR17]
Hao Chen, Kim Laine, and Peter Rindal. Fast Private Set Intersection from Homomorphic Encryption. In CCS, pages 1243–1255. 2017. ACM. DOI: 10.1145/3133956.3134061
[CM20]
Melissa Chase and Peihan Miao. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF. In CRYPTO (3), volume 12172 of Lecture Notes in Computer Science, pages 34–63. 2020. Springer. DOI: 10.1007/978-3-030-56877-1_2
[CMdG+21]
Kelong Cong, Radames Cruz Moreno, Mariana Botelho da Gama, Wei Dai, Ilia Iliashenko, Kim Laine, and Michael Rosenberg. Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication. In CCS, pages 1135–1150. 2021. ACM. DOI: 10.1145/3460120.3484760
[CO18]
Michele Ciampi and Claudio Orlandi. Combining Private Set-Intersection with Secure Two-Party Computation. In SCN, volume 11035 of Lecture Notes in Computer Science, pages 464–482. 2018. Springer. DOI: 10.1007/978-3-319-98113-0_25
[Cou06]
Jean-Marc Couveignes. Hard Homogeneous Spaces. Cryptology ePrint Archive, Paper 2006/291. 2006.
[CRR21]
Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman. Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes. In CRYPTO (3), volume 12827 of Lecture Notes in Computer Science, pages 502–534. 2021. Springer. DOI: 10.1007/978-3-030-84252-9_17
[CT10]
Emiliano De Cristofaro and Gene Tsudik. Practical Private Set Intersection Protocols with Linear Complexity. In Financial Cryptography, volume 6052 of Lecture Notes in Computer Science, pages 143–159. 2010. Springer. DOI: 10.1007/978-3-642-14577-3_13
[CT12]
Emiliano De Cristofaro and Gene Tsudik. Experimenting with Fast Private Set Intersection. In TRUST, volume 7344 of Lecture Notes in Computer Science, pages 55–73. 2012. Springer. DOI: 10.1007/978-3-642-30921-2_4
[DMRY09]
Dana Dachman-Soled, Tal Malkin, Mariana Raykova, and Moti Yung. Efficient Robust Private Set Intersection. In ACNS, volume 5536 of Lecture Notes in Computer Science, pages 125–142. 2009. DOI: 10.1007/978-3-642-01957-9_8
[DN03]
Ivan Damgård and Jesper Buus Nielsen. Universally Composable Efficient Multiparty Computation from Threshold Homomorphic Encryption. In CRYPTO, volume 2729 of Lecture Notes in Computer Science, pages 247–264. 2003. Springer. DOI: 10.1007/978-3-540-45146-4_15
[DPSZ12]
Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty Computation from Somewhat Homomorphic Encryption. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 643–662. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_38
[DRRT18]
Daniel Demmler, Peter Rindal, Mike Rosulek, and Ni Trieu. PIR-PSI: Scaling Private Contact Discovery. Proc. Priv. Enhancing Technol., 2018(4):159–178, 2018. DOI: 10.1515/POPETS-2018-0037
[DY05]
Yevgeniy Dodis and Aleksandr Yampolskiy. A Verifiable Random Function with Short Proofs and Keys. In Public Key Cryptography, volume 3386 of Lecture Notes in Computer Science, pages 416–431. 2005. Springer. DOI: 10.1007/978-3-540-30580-4_28
[FFK+23]
Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz, Lorenz Panny, and Benjamin Wesolowski. SCALLOP: Scaling the CSI-FiSh. In Public Key Cryptography (1), volume 13940 of Lecture Notes in Computer Science, pages 345–375. 2023. Springer. DOI: 10.1007/978-3-031-31368-4_13
[FHNP16]
Michael J. Freedman, Carmit Hazay, Kobbi Nissim, and Benny Pinkas. Efficient Set Intersection with Simulation-Based Security. J. Cryptol., 29(1):115–155, 2016. DOI: 10.1007/S00145-014-9190-0
[FIPR05]
Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. Keyword Search and Oblivious Pseudorandom Functions. In TCC, volume 3378 of Lecture Notes in Computer Science, pages 303–324. 2005. Springer. DOI: 10.1007/978-3-540-30576-7_17
[FNO19]
Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky. Private Set Intersection with Linear Communication from General Assumptions. In WPES@CCS, pages 14–25. 2019. ACM. DOI: 10.1145/3338498.3358645
[FNO22]
Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky. 3-Party Distributed ORAM from Oblivious Set Membership. In SCN, volume 13409 of Lecture Notes in Computer Science, pages 437–461. 2022. Springer. DOI: 10.1007/978-3-031-14791-3_19
[FNP04]
Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. Efficient Private Matching and Set Intersection. In EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pages 1–19. 2004. Springer. DOI: 10.1007/978-3-540-24676-3_1
[GN19]
Satrajit Ghosh and Tobias Nilges. An Algebraic Approach to Maliciously Secure Private Set Intersection. In EUROCRYPT (3), volume 11478 of Lecture Notes in Computer Science, pages 154–185. 2019. Springer. DOI: 10.1007/978-3-030-17659-4_6
[Goo13]
Google. Certificate Transparancy. Accessed: 10-10-2023. https://certificate.transparency.dev/. 2013.
[GPR+21]
Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. Oblivious Key-Value Stores and Amplification for Private Set Intersection. In CRYPTO (2), volume 12826 of Lecture Notes in Computer Science, pages 395–425. 2021. Springer. DOI: 10.1007/978-3-030-84245-1_14
[GRR+16]
Lorenzo Grassi, Christian Rechberger, Dragos Rotaru, Peter Scholl, and Nigel P. Smart. MPC-Friendly Symmetric Key Primitives. In CCS, pages 430–443. 2016. ACM. DOI: 10.1145/2976749.2978332
[GS19]
Satrajit Ghosh and Mark Simkin. The Communication Complexity of Threshold Private Set Intersection. In CRYPTO (2), volume 11693 of Lecture Notes in Computer Science, pages 3–29. 2019. Springer. DOI: 10.1007/978-3-030-26951-7_1
[GZS24]
Ashrujit Ghoshal, Mingxun Zhou, and Elaine Shi. Efficient Pre-processing PIR Without Public-Key Cryptography. In EUROCRYPT (6), volume 14656 of Lecture Notes in Computer Science, pages 210–240. 2024. Springer. DOI: 10.1007/978-3-031-58751-1_8
[Haz15]
Carmit Hazay. Oblivious Polynomial Evaluation and Secure Set-Intersection from Algebraic PRFs. In TCC (2), volume 9015 of Lecture Notes in Computer Science, pages 90–120. 2015. Springer. DOI: 10.1007/978-3-662-46497-7_4
[HEK12]
Yan Huang, David Evans, and Jonathan Katz. Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?. In NDSS. 2012. The Internet Society.
[HFH99]
Bernardo A. Huberman, Matthew K. Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities. In EC, pages 78–86. 1999. ACM. DOI: 10.1145/336992.337012
[HHC+23]
Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, and Vinod Vaikuntanathan. One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval. In USENIX Security Symposium, pages 3889–3905. 2023. USENIX Association.
[HL08]
Carmit Hazay and Yehuda Lindell. Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries. In TCC, volume 4948 of Lecture Notes in Computer Science, pages 155–175. 2008. Springer. DOI: 10.1007/978-3-540-78524-8_10
[HLP+24]
Meng Hao, Weiran Liu, Liqiang Peng, Hongwei Li, Cong Zhang, Hanxiao Chen, and Tianwei Zhang. Unbalanced Circuit-PSI from Oblivious Key-Value Retrieval. In USENIX Security Symposium. 2024. USENIX Association.
[HN10]
Carmit Hazay and Kobbi Nissim. Efficient Set Operations in the Presence of Malicious Adversaries. In Public Key Cryptography, volume 6056 of Lecture Notes in Computer Science, pages 312–331. 2010. Springer. DOI: 10.1007/978-3-642-13013-7_19
[HOS17]
Per A. Hallgren, Claudio Orlandi, and Andrei Sabelfeld. PrivatePool: Privacy-Preserving Ridesharing. In CSF, pages 276–291. 2017. IEEE Computer Society. DOI: 10.1109/CSF.2017.24
[HSW23]
Laura Hetz, Thomas Schneider, and Christian Weinert. Scaling Mobile Private Contact Discovery to Billions of Users. In ESORICS (1), volume 14344 of Lecture Notes in Computer Science, pages 455–476. 2023. Springer. DOI: 10.1007/978-3-031-50594-2_23
[HV17]
Carmit Hazay and Muthuramakrishnan Venkitasubramaniam. Scalable Multi-party Private Set-Intersection. In Public Key Cryptography (1), volume 10174 of Lecture Notes in Computer Science, pages 175–203. 2017. Springer. DOI: 10.1007/978-3-662-54365-8_8
[Jac99]
Michael J. Jacobson. Subexponential class group computation in quadratic orders. PhD thesis, Darmstadt University of Technology, Germany, 1999.
[JKK14]
Stanislaw Jarecki, Aggelos Kiayias, and Hugo Krawczyk. Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only Model. In ASIACRYPT (2), volume 8874 of Lecture Notes in Computer Science, pages 233–253. 2014. Springer. DOI: 10.1007/978-3-662-45608-8_13
[JKKX16]
Stanislaw Jarecki, Aggelos Kiayias, Hugo Krawczyk, and Jiayu Xu. Highly-Efficient and Composable Password-Protected Secret Sharing (Or: How to Protect Your Bitcoin Wallet Online). In EuroS&P, pages 276–291. 2016. IEEE. DOI: 10.1109/EUROSP.2016.30
[JL09]
Stanislaw Jarecki and Xiaomin Liu. Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection. In TCC, volume 5444 of Lecture Notes in Computer Science, pages 577–594. 2009. Springer. DOI: 10.1007/978-3-642-00457-5_34
[KC21]
Dmitry Kogan and Henry Corrigan-Gibbs. Private Blocklist Lookups with Checklist. In USENIX Security Symposium, pages 875–892. 2021. USENIX Association.
[KKRT16]
Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. In CCS, pages 818–829. 2016. ACM. DOI: 10.1145/2976749.2978381
[KLS+17]
Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, and Benny Pinkas. Private Set Intersection for Unequal Set Sizes with Mobile Applications. Proc. Priv. Enhancing Technol., 2017(4):177–197, 2017. DOI: 10.1515/POPETS-2017-0044
[KMP+17]
Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and Ni Trieu. Practical Multi-party Private Set Intersection from Symmetric-Key Techniques. In CCS, pages 1257–1272. 2017. ACM. DOI: 10.1145/3133956.3134065
[KRS+19]
Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. Mobile Private Contact Discovery at Scale. In USENIX Security Symposium, pages 1447–1464. 2019. USENIX Association.
[KRTW19]
Vladimir Kolesnikov, Mike Rosulek, Ni Trieu, and Xiao Wang. Scalable Private Set Union from Symmetric-Key Techniques. In ASIACRYPT (2), volume 11922 of Lecture Notes in Computer Science, pages 636–666. 2019. Springer. DOI: 10.1007/978-3-030-34621-8_23
[KS05]
Lea Kissner and Dawn Xiaodong Song. Privacy-Preserving Set Operations. In CRYPTO, volume 3621 of Lecture Notes in Computer Science, pages 241–257. 2005. Springer. DOI: 10.1007/11535218_15
[Lin17]
Yehuda Lindell. How to Simulate It - A Tutorial on the Simulation Proof Technique. In Tutorials on the Foundations of Cryptography, pages 277–346. Springer International Publishing 2017. DOI: 10.1007/978-3-319-57048-8_6
[LKLM21]
Kristin Lauter, Sreekanth Kannepalli, Kim Laine, and Radames Cruz Moreno. Password Monitor: Safeguarding passwords in Microsoft Edge. Accessed: 11-10-2023. 2021.
[LMW23]
Wei-Kai Lin, Ethan Mook, and Daniel Wichs. Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE. In STOC, pages 595–608. 2023. ACM. DOI: 10.1145/3564246.3585175
[LP23]
Arthur Lazzaretti and Charalampos Papamanthou. TreePIR: Sublinear-Time and Polylog-Bandwidth Private Information Retrieval from DDH. In CRYPTO (2), volume 14082 of Lecture Notes in Computer Science, pages 284–314. 2023. Springer. DOI: 10.1007/978-3-031-38545-2_10
[LPR+21]
Tancrède Lepoint, Sarvar Patel, Mariana Raykova, Karn Seth, and Ni Trieu. Private Join and Compute from PIR with Default. In ASIACRYPT (2), volume 13091 of Lecture Notes in Computer Science, pages 605–634. 2021. Springer. DOI: 10.1007/978-3-030-92075-3_21
[Mea86]
Catherine A. Meadows. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In IEEE Symposium on Security and Privacy, pages 134–137. 1986. IEEE Computer Society. DOI: 10.1109/SP.1986.10022
[MIR23]
Muhammad Haris Mughees, Sun I, and Ling Ren. Simple and Practical Amortized Sublinear Private Information Retrieval. Cryptology ePrint Archive, Paper 2023/1072. 2023.
[MPC18]
Luca Melis, Apostolos Pyrgelis, and Emiliano De Cristofaro. On collaborative predictive blacklisting. Comput. Commun. Rev., 48(5):9–20, 2018. DOI: 10.1145/3310165.3310168
[MPP10]
Mark Manulis, Benny Pinkas, and Bertram Poettering. Privacy-Preserving Group Discovery with Linear Complexity. In ACNS, volume 6123 of Lecture Notes in Computer Science, pages 420–437. 2010. DOI: 10.1007/978-3-642-13708-2_25
[MRR20]
Payman Mohassel, Peter Rindal, and Mike Rosulek. Fast Database Joins and PSI for Secret Shared Data. In CCS, pages 1271–1287. 2020. ACM. DOI: 10.1145/3372297.3423358
[MZ22]
Hart Montgomery and Mark Zhandry. Full Quantum Equivalence of Group Action DLog and CDH, and More. In ASIACRYPT (1), volume 13791 of Lecture Notes in Computer Science, pages 3–32. 2022. Springer. DOI: 10.1007/978-3-031-22963-3_1
[NR97]
Moni Naor and Omer Reingold. Number-theoretic Constructions of Efficient Pseudo-random Functions. In FOCS, pages 458–467. 1997. IEEE Computer Society. DOI: 10.1109/SFCS.1997.646134
[OPPW23]
Hiroki Okada, Rachel Player, Simon Pohmann, and Christian Weinert. Towards Practical Doubly-Efficient Private Information Retrieval. Cryptology ePrint Archive, Paper 2023/1510. 2023.
[PR01]
Rasmus Pagh and Flemming Friche Rodler. Cuckoo Hashing. In ESA, volume 2161 of Lecture Notes in Computer Science, pages 121–133. 2001. Springer. DOI: 10.1007/3-540-44676-1_10
[PRTY19]
Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension. In CRYPTO (3), volume 11694 of Lecture Notes in Computer Science, pages 401–431. 2019. Springer. DOI: 10.1007/978-3-030-26954-8_13
[PRTY20]
Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. PSI from PaXoS: Fast, Malicious Private Set Intersection. In EUROCRYPT (2), volume 12106 of Lecture Notes in Computer Science, pages 739–767. 2020. Springer. DOI: 10.1007/978-3-030-45724-2_25
[PSSW09]
Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams. Secure Two-Party Computation Is Practical. In ASIACRYPT, volume 5912 of Lecture Notes in Computer Science, pages 250–267. 2009. Springer. DOI: 10.1007/978-3-642-10366-7_15
[PSSZ15]
Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. Phasing: Private Set Intersection Using Permutation-based Hashing. In USENIX Security Symposium, pages 515–530. 2015. USENIX Association.
[PSTY19]
Benny Pinkas, Thomas Schneider, Oleksandr Tkachenko, and Avishay Yanai. Efficient Circuit-Based PSI with Linear Communication. In EUROCRYPT (3), volume 11478 of Lecture Notes in Computer Science, pages 122–153. 2019. Springer. DOI: 10.1007/978-3-030-17659-4_5
[PSWW18]
Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. Efficient Circuit-Based PSI via Cuckoo Hashing. In EUROCRYPT (3), volume 10822 of Lecture Notes in Computer Science, pages 125–157. 2018. Springer. DOI: 10.1007/978-3-319-78372-7_5
[PSZ14]
Benny Pinkas, Thomas Schneider, and Michael Zohner. Faster Private Set Intersection Based on OT Extension. In USENIX Security Symposium, pages 797–812. 2014. USENIX Association.
[PSZ18]
Benny Pinkas, Thomas Schneider, and Michael Zohner. Scalable Private Set Intersection Based on OT Extension. ACM Trans. Priv. Secur., 21(2):7:1–7:35, 2018. DOI: 10.1145/3154794
[QYYZ22]
Zhi Qiu, Kang Yang, Yu Yu, and Lijing Zhou. Maliciously Secure Multi-party PSI with Lower Bandwidth and Faster Computation. In ICICS, volume 13407 of Lecture Notes in Computer Science, pages 69–88. 2022. Springer. DOI: 10.1007/978-3-031-15777-6_5
[RR22]
Srinivasan Raghuraman and Peter Rindal. Blazing Fast PSI from Improved OKVS and Subfield VOLE. In CCS, pages 2505–2517. 2022. ACM. DOI: 10.1145/3548606.3560658
[RRT23]
Srinivasan Raghuraman, Peter Rindal, and Titouan Tanguy. Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN. In CRYPTO (4), volume 14084 of Lecture Notes in Computer Science, pages 602–632. 2023. Springer. DOI: 10.1007/978-3-031-38551-3_19
[RS21]
Peter Rindal and Phillipp Schoppmann. VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE. In EUROCRYPT (2), volume 12697 of Lecture Notes in Computer Science, pages 901–930. 2021. Springer. DOI: 10.1007/978-3-030-77886-6_31
[Sha80]
Adi Shamir. On the Power of Commutativity in Cryptography. In ICALP, volume 85 of Lecture Notes in Computer Science, pages 582–595. 1980. Springer. DOI: 10.1007/3-540-10003-2_100
[SJ23]
Yongha Son and Jinhyuck Jeong. PSI with computation or Circuit-PSI for Unbalanced Sets from Homomorphic Encryption. In AsiaCCS, pages 342–356. 2023. ACM. DOI: 10.1145/3579856.3582817
[V{\'e}l71]
Jacques Vélu. Isogénies entre courbes elliptiques. CR Acad. Sci. Paris, Séries A, 273:305–347, 1971.
[WYKW21]
Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits. In IEEE Symposium on Security and Privacy, pages 1074–1091. 2021. IEEE. DOI: 10.1109/SP40001.2021.00056
[ZPZS24]
Mingxun Zhou, Andrew Park, Wenting Zheng, and Elaine Shi. Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation. In SP, pages 4296–4314. 2024. IEEE. DOI: 10.1109/SP54263.2024.00055
PDF
History
Submitted: 2024-04-09
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Aron van Baarsen and Marc Stevens, Amortizing Circuit-PSI in the Multiple Sender/Receiver Setting. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a0fhsgvtw.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.