{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T00:30:21Z","timestamp":1768437021700,"version":"3.49.0"},"reference-count":102,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T00:00:00Z","timestamp":1712620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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. <\/jats:p>","DOI":"10.62056\/a0fhsgvtw","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T15:13:33Z","timestamp":1728314013000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":2,"title":["Amortizing Circuit-PSI in the  Multiple Sender\/Receiver Setting"],"prefix":"10.62056","author":[{"given":"Aron","family":"van Baarsen","sequence":"first","affiliation":[{"name":"CWI","place":["Amsterdam, The Netherlands"],"department":["Cryptology Group"]},{"name":"Leiden University","place":["Leiden, The Netherlands"],"department":["Mathematical Institute"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Stevens","sequence":"additional","affiliation":[{"name":"CWI","place":["Amsterdam, The Netherlands"],"department":["Cryptology Group"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:Mea86","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1109\/SP.1986.10022","article-title":"A More Efficient Cryptographic Matchmaking Protocol for Use\n  in the Absence of a Continuously Available Third Party","author":"Catherine A. Meadows","year":"1986"},{"key":"ref2:KKRT16","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1145\/2976749.2978381","article-title":"Efficient Batched Oblivious PRF with Applications to\n  Private Set Intersection","author":"Vladimir Kolesnikov","year":"2016"},{"key":"ref3:PRTY19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-030-26954-8_13","article-title":"SpOT-Light: Lightweight Private Set Intersection from\n  Sparse OT Extension","volume":"11694","author":"Benny Pinkas","year":"2019"},{"key":"ref4:CM20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-030-56877-1_2","article-title":"Private Set Intersection in the Internet Setting from\n  Lightweight Oblivious PRF","volume":"12172","author":"Melissa Chase","year":"2020"},{"key":"ref5:RS21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"901","DOI":"10.1007\/978-3-030-77886-6_31","article-title":"VOLE-PSI: Fast OPRF and Circuit-PSI from\n  Vector-OLE","volume":"12697","author":"Peter Rindal","year":"2021"},{"key":"ref6:RR22","doi-asserted-by":"publisher","first-page":"2505","DOI":"10.1145\/3548606.3560658","article-title":"Blazing Fast PSI from Improved OKVS and Subfield\n  VOLE","author":"Srinivasan Raghuraman","year":"2022"},{"key":"ref7:BPSY23","article-title":"Near-Optimal Oblivious Key-Value Stores for Efficient PSI,\n  PSU and Volume-Hiding Multi-Maps","volume-title":"Proceedings of the 32nd USENIX Security Symposium","author":"Alexander Bienstock","year":"2023"},{"key":"ref8:FIPR05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-30576-7_17","article-title":"Keyword Search and Oblivious Pseudorandom Functions","volume":"3378","author":"Michael J. Freedman","year":"2005"},{"key":"ref9:HEK12","article-title":"Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?","volume-title":"Proceedings of the Network and Distributed Systems Security Symposium","author":"Yan Huang","year":"2012"},{"key":"ref10:PSZ14","first-page":"797","article-title":"Faster Private Set Intersection Based on OT Extension","volume-title":"Proceedings of the 23rd USENIX Security Symposium","author":"Benny Pinkas","year":"2014"},{"key":"ref11:PSSZ15","first-page":"515","article-title":"Phasing: Private Set Intersection Using Permutation-based\n  Hashing","volume-title":"Proceedings of the 24th USENIX Security Symposium","author":"Benny Pinkas","year":"2015"},{"key":"ref12:PSZ18","doi-asserted-by":"publisher","DOI":"10.1145\/3154794","article-title":"Scalable Private Set Intersection Based on OT Extension","volume":"21","author":"Benny Pinkas","year":"2018","journal-title":"ACM Trans. Priv. Secur."},{"key":"ref13:PSWW18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-319-78372-7_5","article-title":"Efficient Circuit-Based PSI via Cuckoo Hashing","volume":"10822","author":"Benny Pinkas","year":"2018"},{"key":"ref14:CO18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/978-3-319-98113-0_25","article-title":"Combining Private Set-Intersection with Secure Two-Party\n  Computation","volume":"11035","author":"Michele Ciampi","year":"2018"},{"key":"ref15:FNO19","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/3338498.3358645","article-title":"Private Set Intersection with Linear Communication from\n  General Assumptions","author":"Brett Hemenway Falk","year":"2019"},{"key":"ref16:PSTY19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-030-17659-4_5","article-title":"Efficient Circuit-Based PSI with Linear Communication","volume":"11478","author":"Benny Pinkas","year":"2019"},{"key":"ref17:MRR20","doi-asserted-by":"publisher","first-page":"1271","DOI":"10.1145\/3372297.3423358","article-title":"Fast Database Joins and PSI for Secret Shared Data","author":"Payman Mohassel","year":"2020"},{"key":"ref18:CGS22","doi-asserted-by":"publisher","first-page":"353","DOI":"10.2478\/POPETS-2022-0018","article-title":"Circuit-PSI With Linear Complexity via Relaxed Batch\n  OPPRF","volume":"2022","author":"Nishanth Chandran","year":"2022","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref19:CDG+21","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1145\/3460120.3484591","article-title":"Efficient Linear Multiparty PSI and Extensions to\n  Circuit\/Quorum PSI","author":"Nishanth Chandran","year":"2021"},{"key":"ref20:KMP+17","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1145\/3133956.3134065","article-title":"Practical Multi-party Private Set Intersection from\n  Symmetric-Key Techniques","author":"Vladimir Kolesnikov","year":"2017"},{"key":"ref21:GPR+21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-030-84245-1_14","article-title":"Oblivious Key-Value Stores and Amplification for Private Set\n  Intersection","volume":"12826","author":"Gayathri Garimella","year":"2021"},{"key":"ref22:DY05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-540-30580-4_28","article-title":"A Verifiable Random Function with Short Proofs and Keys","volume":"3386","author":"Yevgeniy Dodis","year":"2005"},{"key":"ref23:BC22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-031-31371-4_7","article-title":"Improved Private Set Intersection for Sets with Small\n  Entries","volume":"13941","author":"Dung Bui","year":"2023"},{"key":"ref24:JKK14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/978-3-662-45608-8_13","article-title":"Round-Optimal Password-Protected Secret Sharing and T-PAKE\n  in the Password-Only Model","volume":"8874","author":"Stanislaw Jarecki","year":"2014"},{"key":"ref25:JKKX16","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/EUROSP.2016.30","article-title":"Highly-Efficient and Composable Password-Protected Secret\n  Sharing (Or: How to Protect Your Bitcoin Wallet Online)","author":"Stanislaw Jarecki","year":"2016"},{"key":"ref26:HSW23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-031-50594-2_23","article-title":"Scaling Mobile Private Contact Discovery to Billions of\n  Users","volume":"14344","author":"Laura Hetz","year":"2023"},{"key":"ref27:KRS+19","first-page":"1447","article-title":"Mobile Private Contact Discovery at Scale","volume-title":"Proceedings of the 28th USENIX Security Symposium","author":"Daniel Kales","year":"2019"},{"key":"ref28:CMdG+21","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1145\/3460120.3484760","article-title":"Labeled PSI from Homomorphic Encryption with Reduced\n  Computation and Communication","author":"Kelong Cong","year":"2021"},{"key":"ref29:Microsoft21","volume-title":"Password Monitor: Safeguarding passwords in Microsoft Edge","author":"Kristin Lauter","year":"2021"},{"key":"ref30:HOS17","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/CSF.2017.24","article-title":"PrivatePool: Privacy-Preserving Ridesharing","author":"Per A. Hallgren","year":"2017"},{"key":"ref31:MPC18","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/3310165.3310168","article-title":"On collaborative predictive blacklisting","volume":"48","author":"Luca Melis","year":"2018","journal-title":"Comput. Commun. Rev."},{"key":"ref32:PSSW09","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-10366-7_15","article-title":"Secure Two-Party Computation Is Practical","volume":"5912","author":"Benny Pinkas","year":"2009"},{"key":"ref33:ARS+15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/978-3-662-46800-5_17","article-title":"Ciphers for MPC and FHE","volume":"9056","author":"Martin R. Albrecht","year":"2015"},{"key":"ref34:GRR+16","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1145\/2976749.2978332","article-title":"MPC-Friendly Symmetric Key Primitives","author":"Lorenzo Grassi","year":"2016"},{"key":"ref35:KLS+17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1515\/POPETS-2017-0044","article-title":"Private Set Intersection for Unequal Set Sizes with Mobile\n  Applications","volume":"2017","author":"\u00c1gnes Kiss","year":"2017","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref36:FNO22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-031-14791-3_19","article-title":"3-Party Distributed ORAM from Oblivious Set Membership","volume":"13409","author":"Brett Hemenway Falk","year":"2022"},{"key":"ref37:CT10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-642-14577-3_13","article-title":"Practical Private Set Intersection Protocols with Linear\n  Complexity","volume":"6052","author":"Emiliano De Cristofaro","year":"2010"},{"key":"ref38:NR97","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1109\/SFCS.1997.646134","article-title":"Number-theoretic Constructions of Efficient Pseudo-random\n  Functions","author":"Moni Naor","year":"1997"},{"key":"ref39:HL08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-540-78524-8_10","article-title":"Efficient Protocols for Set Intersection and Pattern\n  Matching with Security Against Malicious and Covert Adversaries","volume":"4948","author":"Carmit Hazay","year":"2008"},{"key":"ref40:DRRT18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1515\/POPETS-2018-0037","article-title":"PIR-PSI: Scaling Private Contact Discovery","volume":"2018","author":"Daniel Demmler","year":"2018","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref41:CLR17","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1145\/3133956.3134061","article-title":"Fast Private Set Intersection from Homomorphic Encryption","author":"Hao Chen","year":"2017"},{"key":"ref42:CHLR18","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1145\/3243734.3243836","article-title":"Labeled PSI from Fully Homomorphic Encryption with\n  Malicious Security","author":"Hao Chen","year":"2018"},{"key":"ref43:LPR+21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-030-92075-3_21","article-title":"Private Join and Compute from PIR with Default","volume":"13091","author":"Tancr\u00e8de Lepoint","year":"2021"},{"key":"ref44:SJ23","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1145\/3579856.3582817","article-title":"PSI with computation or Circuit-PSI for Unbalanced Sets\n  from Homomorphic Encryption","author":"Yongha Son","year":"2023"},{"key":"ref45:HLP+23","article-title":"Unbalanced Circuit-PSI from Oblivious Key-Value Retrieval","volume-title":"Proceedings of the 33rd USENIX Security Symposium","author":"Meng Hao","year":"2024"},{"key":"ref46:QYYZ22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-031-15777-6_5","article-title":"Maliciously Secure Multi-party PSI with Lower Bandwidth\n  and Faster Computation","volume":"13407","author":"Zhi Qiu","year":"2022"},{"key":"ref47:BCG+19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-030-26954-8_16","article-title":"Efficient Pseudorandom Correlation Generators: Silent OT\n  Extension and More","volume":"11694","author":"Elette Boyle","year":"2019"},{"key":"ref48:Lin17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-319-57048-8_6","article-title":"How to Simulate It - A Tutorial on the Simulation Proof\n  Technique","author":"Yehuda Lindell","year":"2017"},{"key":"ref49:FNP04","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24676-3_1","article-title":"Efficient Private Matching and Set Intersection","volume":"3027","author":"Michael J. Freedman","year":"2004"},{"key":"ref50:KS05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/11535218_15","article-title":"Privacy-Preserving Set Operations","volume":"3621","author":"Lea Kissner","year":"2005"},{"key":"ref51:DSMRY09","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-642-01957-9_8","article-title":"Efficient Robust Private Set Intersection","volume":"5536","author":"Dana Dachman-Soled","year":"2009"},{"key":"ref52:HN10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/978-3-642-13013-7_19","article-title":"Efficient Set Operations in the Presence of Malicious\n  Adversaries","volume":"6056","author":"Carmit Hazay","year":"2010"},{"key":"ref53:MPP10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/978-3-642-13708-2_25","article-title":"Privacy-Preserving Group Discovery with Linear Complexity","volume":"6123","author":"Mark Manulis","year":"2010"},{"key":"ref54:Haz15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-662-46497-7_4","article-title":"Oblivious Polynomial Evaluation and Secure Set-Intersection\n  from Algebraic PRFs","volume":"9015","author":"Carmit Hazay","year":"2015"},{"key":"ref55:HV17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-662-54365-8_8","article-title":"Scalable Multi-party Private Set-Intersection","volume":"10174","author":"Carmit Hazay","year":"2017"},{"key":"ref56:FHNP16","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/S00145-014-9190-0","article-title":"Efficient Set Intersection with Simulation-Based Security","volume":"29","author":"Michael J. Freedman","year":"2016","journal-title":"J. Cryptol."},{"key":"ref57:CDJ16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-319-29485-8_10","article-title":"Efficient Concurrent Covert Computation of String Equality\n  and Set Intersection","volume":"9610","author":"Chongwon Cho","year":"2016"},{"key":"ref58:GN19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-030-17659-4_6","article-title":"An Algebraic Approach to Maliciously Secure Private Set\n  Intersection","volume":"11478","author":"Satrajit Ghosh","year":"2019"},{"key":"ref59:GS19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-26951-7_1","article-title":"The Communication Complexity of Threshold Private Set\n  Intersection","volume":"11693","author":"Satrajit Ghosh","year":"2019"},{"key":"ref60:KRTW19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1007\/978-3-030-34621-8_23","article-title":"Scalable Private Set Union from Symmetric-Key Techniques","volume":"11922","author":"Vladimir Kolesnikov","year":"2019"},{"key":"ref61:PRTY20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/978-3-030-45724-2_25","article-title":"PSI from PaXoS: Fast, Malicious Private Set\n  Intersection","volume":"12106","author":"Benny Pinkas","year":"2020"},{"key":"ref62:PR01","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-44676-1_10","article-title":"Cuckoo Hashing","volume":"2161","author":"Rasmus Pagh","year":"2001"},{"key":"ref63:Cou06","volume-title":"Hard Homogeneous Spaces","author":"Jean-Marc Couveignes","year":"2006"},{"key":"ref64:AFMP20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-030-64834-3_14","article-title":"Cryptographic Group Actions and Applications","volume":"12492","author":"Navid Alamati","year":"2020"},{"key":"ref65:MZ22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-22963-3_1","article-title":"Full Quantum Equivalence of Group Action DLog and CDH, and\n  More","volume":"13791","author":"Hart Montgomery","year":"2022"},{"key":"ref66:CGJ+17","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1145\/3133956.3134092","article-title":"Fairness in an Unfair World: Fair Multiparty Computation\n  from Public Bulletin Boards","author":"Arka Rai Choudhuri","year":"2017"},{"key":"ref67:Google13","volume-title":"Certificate Transparancy","author":"Google","year":"2013"},{"key":"ref68:Cloudflare18","volume-title":"Nimbus","author":"Cloudflare","year":"2018"},{"key":"ref69:BGM16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-662-53357-4_10","article-title":"Cryptocurrencies Without Proof of Work","volume":"9604","author":"Iddo Bentov","year":"2016"},{"key":"ref70:BDD20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/978-3-030-51280-4_22","article-title":"Insured MPC: Efficient Secure Computation with Financial\n  Penalties","volume":"12059","author":"Carsten Baum","year":"2020"},{"key":"ref71:DN03","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-540-45146-4_15","article-title":"Universally Composable Efficient Multiparty Computation from\n  Threshold Homomorphic Encryption","volume":"2729","author":"Ivan Damg\u00e5rd","year":"2003"},{"key":"ref72:BCGI18","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1145\/3243734.3243868","article-title":"Compressing Vector OLE","author":"Elette Boyle","year":"2018"},{"key":"ref73:BCG+19b","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1145\/3319535.3354255","article-title":"Efficient Two-Round OT Extension and Silent\n  Non-Interactive Secure Computation","author":"Elette Boyle","year":"2019"},{"key":"ref74:WYKW21","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1109\/SP40001.2021.00056","article-title":"Wolverine: Fast, Scalable, and Communication-Efficient\n  Zero-Knowledge Proofs for Boolean and Arithmetic Circuits","author":"Chenkai Weng","year":"2021"},{"key":"ref75:CRR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-030-84252-9_17","article-title":"Silver: Silent VOLE and Oblivious Transfer from Hardness\n  of Decoding Structured LDPC Codes","volume":"12827","author":"Geoffroy Couteau","year":"2021"},{"key":"ref76:RRT23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1007\/978-3-031-38551-3_19","article-title":"Expand-Convolute Codes for Pseudorandom Correlation\n  Generators from LPN","volume":"14084","author":"Srinivasan Raghuraman","year":"2023"},{"key":"ref77:BM82","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1109\/SFCS.1982.72","article-title":"How to Generate Cryptographically Strong Sequences of Pseudo\n  Random Bits","author":"Manuel Blum","year":"1982"},{"key":"ref78:AGR+16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-662-53887-6_7","article-title":"MiMC: Efficient Encryption and Cryptographic Hashing with\n  Minimal Multiplicative Complexity","volume":"10031","author":"Martin R. Albrecht","year":"2016"},{"key":"ref79:DPSZ12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-642-32009-5_38","article-title":"Multiparty Computation from Somewhat Homomorphic\n  Encryption","volume":"7417","author":"Ivan Damg\u00e5rd","year":"2012"},{"key":"ref80:BIM00","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-44598-6_4","article-title":"Reducing the Servers Computation in Private Information\n  Retrieval: PIR with Preprocessing","volume":"1880","author":"Amos Beimel","year":"2000"},{"key":"ref81:HHC-G+22","first-page":"3889","article-title":"One Server for the Price of Two: Simple and Fast\n  Single-Server Private Information Retrieval","volume-title":"Proceedings of the 32nd USENIX Security Symposium","author":"Alexandra Henzinger","year":"2023"},{"key":"ref82:ZPZS24","doi-asserted-by":"publisher","first-page":"4296","DOI":"10.1109\/SP54263.2024.00055","article-title":"Piano: Extremely Simple, Single-Server PIR with Sublinear\n  Server Computation","author":"Mingxun Zhou","year":"2024"},{"key":"ref83:MIR23","volume-title":"Simple and Practical Amortized Sublinear Private Information\n  Retrieval","author":"Muhammad Haris Mughees","year":"2023"},{"key":"ref84:GZS23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-031-58751-1_8","article-title":"Efficient Pre-processing PIR Without Public-Key\n  Cryptography","volume":"14656","author":"Ashrujit Ghoshal","year":"2024"},{"key":"ref85:KC21","first-page":"875","article-title":"Private Blocklist Lookups with Checklist","volume-title":"Proceedings of the 30th USENIX Security Symposium","author":"Dmitry Kogan","year":"2021"},{"key":"ref86:LP23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-031-38545-2_10","article-title":"TreePIR: Sublinear-Time and Polylog-Bandwidth Private\n  Information Retrieval from DDH","volume":"14082","author":"Arthur Lazzaretti","year":"2023"},{"key":"ref87:LMW23","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/3564246.3585175","article-title":"Doubly Efficient Private Information Retrieval and Fully\n  Homomorphic RAM Computation from Ring LWE","author":"Wei-Kai Lin","year":"2023"},{"key":"ref88:OPPW24","volume-title":"Towards Practical Doubly-Efficient Private Information\n  Retrieval","author":"Hiroki Okada","year":"2023"},{"key":"ref89:BCG+20a","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-030-56880-1_14","article-title":"Efficient Pseudorandom Correlation Generators from\n  Ring-LPN","volume":"12171","author":"Elette Boyle","year":"2020"},{"key":"ref90:BKV19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-030-34578-5_9","article-title":"CSI-FiSh: Efficient Isogeny Based Signatures Through Class\n  Group Computations","volume":"11921","author":"Ward Beullens","year":"2019"},{"key":"ref91:FFK+23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-031-31368-4_13","article-title":"SCALLOP: Scaling the CSI-FiSh","volume":"13940","author":"Luca De Feo","year":"2023"},{"key":"ref92:Vel71","first-page":"305","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"273","author":"Jacques V\u00e9lu","year":"1971","journal-title":"CR Acad. Sci. Paris, S\u00e9ries A"},{"key":"ref93:Jac99","volume-title":"Subexponential class group computation in quadratic orders","author":"Michael J. Jacobson","year":"1999"},{"key":"ref94:Bia10","doi-asserted-by":"publisher","first-page":"141","DOI":"10.3934\/AMC.2010.4.141","article-title":"Improvements in the computation of ideal class groups of\n  imaginary quadratic number fields","volume":"4","author":"Jean-Fran\u00e7ois Biasse","year":"2010","journal-title":"Adv. Math. Commun."},{"key":"ref95:CLM+18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-030-03332-3_15","article-title":"CSIDH: An Efficient Post-Quantum Commutative Group\n  Action","volume":"11274","author":"Wouter Castryck","year":"2018"},{"key":"ref96:BBD+22","doi-asserted-by":"publisher","first-page":"2702","DOI":"10.1093\/COMJNL\/BXAE038","article-title":"Failing to Hash Into Supersingular Isogeny Graphs","volume":"67","author":"Jeremy Booher","year":"2024","journal-title":"Comput. J."},{"key":"ref97:CHL05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/11426639_18","article-title":"Compact E-Cash","volume":"3494","author":"Jan Camenisch","year":"2005"},{"key":"ref98:Sha80","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1007\/3-540-10003-2_100","article-title":"On the Power of Commutativity in Cryptography","volume":"85","author":"Adi Shamir","year":"1980"},{"key":"ref99:HFH99","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/336992.337012","article-title":"Enhancing privacy and trust in electronic communities","author":"Bernardo A. Huberman","year":"1999"},{"key":"ref100:AES03","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/872757.872771","article-title":"Information sharing across private databases","author":"Rakesh Agrawal","year":"2003"},{"key":"ref101:CT12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-30921-2_4","article-title":"Experimenting with Fast Private Set Intersection","volume":"7344","author":"Emiliano De Cristofaro","year":"2012"},{"key":"ref102:JL09","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-00457-5_34","article-title":"Efficient Oblivious Pseudorandom Function with Applications\n  to Adaptive OT and Secure Computation of Set Intersection","volume":"5444","author":"Stanislaw Jarecki","year":"2009"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:04Z","timestamp":1733866084000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":102,"URL":"https:\/\/doi.org\/10.62056\/a0fhsgvtw","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-04-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-2-34"}}