{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T13:10:34Z","timestamp":1765113034829,"version":"3.41.2"},"reference-count":30,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:00:00Z","timestamp":1719878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100014895","name":"Open Philanthropy","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100014895","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>        Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance.                  Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the  semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>o<\/mml:mi>\n                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                <mml:mn>1<\/mml:mn>\n                <mml:mo stretchy=\"false\">)<\/mml:mo>\n              <\/mml:mrow>\n            <\/mml:math> as the batch size increases. The obvious solution using  zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments.                  Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model.         We also present a variant of our maliciously secure protocol that does not rely on the OEP  but nevertheless only has overhead <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n              <mml:mrow>\n                <mml:mi>o<\/mml:mi>\n                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                <mml:mn>1<\/mml:mn>\n                <mml:mo stretchy=\"false\">)<\/mml:mo>\n              <\/mml:mrow>\n            <\/mml:math> over the known semi-honest protocol.         Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers. <\/jats:p>","DOI":"10.62056\/a66cy7qiu","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":3,"title":["Efficient Maliciously Secure   Oblivious Exponentiations"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7905-0198","authenticated-orcid":false,"given":"Carsten","family":"Baum","sequence":"first","affiliation":[{"name":"Technical University of Denmark","place":["Kgs. Lyngby, Denmark"],"department":["DTU Compute"]}]},{"given":"Jens","family":"Berlips","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"given":"Walther","family":"Chen","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6164-0896","authenticated-orcid":false,"given":"Ivan","family":"Damg\u00e5rd","sequence":"additional","affiliation":[{"name":"Aarhus University","place":["Aarhus, Denmark"],"department":["Department of Computer Science"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8797-3945","authenticated-orcid":false,"given":"Kevin","family":"Esvelt","sequence":"additional","affiliation":[{"name":"MIT","place":["Cambridge, USA"],"department":["Media Lab"]}]},{"given":"Leonard","family":"Foner","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4726-9149","authenticated-orcid":false,"given":"Dana","family":"Gretton","sequence":"additional","affiliation":[{"name":"MIT","place":["Cambridge, USA"],"department":["Media Lab"]}]},{"given":"Martin","family":"Kysel","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"given":"Ronald","family":"Rivest","sequence":"additional","affiliation":[{"name":"MIT","place":["Cambridge, USA"],"department":["Computer Science & AI Lab"]}]},{"given":"Lawrence","family":"Roy","sequence":"additional","affiliation":[{"name":"Aarhus University","place":["Aarhus, Denmark"],"department":["Department of Computer Science"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3277-9668","authenticated-orcid":false,"given":"Francesca","family":"Sage-Ling","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"given":"Adi","family":"Shamir","sequence":"additional","affiliation":[{"name":"Weizmann Institute","place":["Rehovot, Israel"],"department":["Department of Computer Science"]}]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[{"name":"MIT","place":["Cambridge, USA"],"department":["Computer Science & AI Lab"]}]},{"given":"Lynn","family":"Van Hauwe","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"given":"Theia","family":"Vogel","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"given":"Benjamin","family":"Weinstein-Raun","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"given":"Daniel","family":"Wichs","sequence":"additional","affiliation":[{"name":"Northeastern University","place":["Boston, USA"],"department":["Khoury College of Computer Sciences"]},{"name":"NTT Research","place":["Sunnyvale, USA"],"department":["Cryptography & Information Security"]}]},{"given":"Stephen","family":"Wooster","sequence":"additional","affiliation":[{"name":"SecureDNA Foundation","place":["Zug, Switzerland"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3648-5594","authenticated-orcid":false,"given":"Andrew","family":"Yao","sequence":"additional","affiliation":[{"name":"Tsinghua University","place":["Beijing, China"],"department":["Institute for Interdisciplinary Information Sciences"]}]},{"given":"Yu","family":"Yu","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University","place":["Shanghai, China"],"department":["Department of Computer Science and Engineering"]}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:TCC:HazLin08","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":"ref2:CCS:CamLehNev15","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1145\/2810103.2813722","article-title":"Optimal Distributed Password Verification","author":"Jan Camenisch","year":"2015"},{"key":"ref3:USENIX:ECSJR15","first-page":"547","article-title":"The Pythia PRF Service","author":"Adam Everspaugh","year":"2015"},{"key":"ref4:AC:JarKiaKra14","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\n  T-PAKE in the Password-Only Model","volume":"8874","author":"Stanislaw Jarecki","year":"2014"},{"key":"ref5:ACNS:JKKX17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-319-61204-1_3","article-title":"TOPPSS: Cost-Minimal Password-Protected Secret Sharing\n  Based on Threshold OPRF","volume":"10355","author":"Stanislaw Jarecki","year":"2017"},{"key":"ref6:CCS:AMMM18","doi-asserted-by":"publisher","first-page":"2042","DOI":"10.1145\/3243734.3243839","article-title":"PASTA: PASsword-based Threshold Authentication","author":"Shashank Agrawal","year":"2018"},{"key":"ref7:baum2020pesto","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1109\/EuroSP48549.2020.00044","article-title":"PESTO: proactively secure distributed single sign-on, or how\n  to trust a hacked server","author":"Carsten Baum","year":"2020"},{"key":"ref8:PoPETS:DGSTV18","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1515\/popets-2018-0026","article-title":"Privacy Pass: Bypassing Internet Challenges Anonymously","volume":"2018","author":"Alex Davidson","year":"2018","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"key":"ref9:EUROSP:CasHesLeh22","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1109\/EuroSP53844.2022.00045","article-title":"SoK: Oblivious Pseudorandom Functions","author":"S\u00edlvia Casacuberta","year":"2022"},{"key":"ref10:EC:NaoPinRei99","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/3-540-48910-X_23","article-title":"Distributed Pseudo-random Functions and KDCs","volume":"1592","author":"Moni Naor","year":"1999"},{"key":"ref11:TCC:Peikert06","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/11681878_9","article-title":"On Error Correction in the Exponent","volume":"3876","author":"Chris Peikert","year":"2006"},{"key":"ref12:biopaper","doi-asserted-by":"publisher","DOI":"10.1101\/2024.03.20.585782","volume-title":"Random adversarial threshold search enables automated DNA\n  screening","author":"Dana Gretton","year":"2024","journal-title":"bioRxiv"},{"volume-title":"A system capable of verifiably and privately screening\n  global DNA synthesis","year":"2024","author":"Carsten Baum","key":"ref13:systempaper"},{"key":"ref14:EC:BelGarRab98","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/BFb0054130","article-title":"Fast Batch Verification for Modular Exponentiation and\n  Digital Signatures","volume":"1403","author":"Mihir Bellare","year":"1998"},{"key":"ref15:EC:Chaum90","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/3-540-46877-3_41","article-title":"Zero-Knowledge Undeniable Signatures","volume":"473","author":"David Chaum","year":"1991"},{"key":"ref16:AC:GLSY04","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-540-30539-2_20","article-title":"Batching Schnorr Identification Scheme with Applications\n  to Privacy-Preserving Authorization and Low-Bandwidth Communication Devices","volume":"3329","author":"Rosario Gennaro","year":"2004"},{"key":"ref17:SP:BBBPWM18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1109\/SP.2018.00020","article-title":"Bulletproofs: Short Proofs for Confidential Transactions and\n  More","author":"Benedikt B\u00fcnz","year":"2018"},{"key":"ref18:C:AttCra20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-030-56877-1_18","article-title":"Compressed $\\varSigma$-Protocol Theory and Practical\n  Application to Plug & Play Secure Algorithmics","volume":"12172","author":"Thomas Attema","year":"2020"},{"key":"ref19:naor_reingold","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","article-title":"Number-theoretic constructions of efficient pseudo-random\n  functions","volume":"51","author":"Moni Naor","year":"2004","journal-title":"Journal of the ACM (JACM)"},{"key":"ref20:PKC:DodYam05","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":"ref21:C:IKNP03","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-540-45146-4_9","article-title":"Extending Oblivious Transfers Efficiently","volume":"2729","author":"Yuval Ishai","year":"2003"},{"key":"ref22:CCS: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":"ref23:C:MPRSY20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-56877-1_1","article-title":"Two-Sided Malicious Security for Private Intersection-Sum\n  with Cardinality","volume":"12172","author":"Peihan Miao","year":"2020"},{"key":"ref24:FOCS:Canetti01","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1109\/SFCS.2001.959888","article-title":"Universally Composable Security: A New Paradigm for\n  Cryptographic Protocols","author":"Ran Canetti","year":"2001"},{"key":"ref25:EC:CDGLN18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-319-78381-9_11","article-title":"The Wonderful World of Global Random Oracles","volume":"10820","author":"Jan Camenisch","year":"2018"},{"key":"ref26:RSA:AbdPoi05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-540-30574-3_14","article-title":"Simple Password-Based Encrypted Key Exchange Protocols","volume":"3376","author":"Michel Abdalla","year":"2005"},{"key":"ref27:FC:Szydlo06","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/11889663_14","article-title":"A Note on Chosen-Basis Decisional Diffie-Hellman\n  Assumptions","volume":"4107","author":"Michael Szydlo","year":"2006"},{"key":"ref28:JC:BFFMSS19","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/s00145-018-9302-3","article-title":"Automated Analysis of Cryptographic Assumptions in Generic\n  Group Models","volume":"32","author":"Gilles Barthe","year":"2019","journal-title":"Journal of Cryptology"},{"key":"ref29:JC:BonLynSha04","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00145-004-0314-9","article-title":"Short Signatures from the Weil Pairing","volume":"17","author":"Dan Boneh","year":"2004","journal-title":"Journal of Cryptology"},{"key":"ref30:elgamal","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on\n  discrete logarithms","volume":"31","author":"Taher ElGamal","year":"1985","journal-title":"IEEE transactions on information theory"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:11Z","timestamp":1733866091000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":30,"URL":"https:\/\/doi.org\/10.62056\/a66cy7qiu","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-02","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-3-30"}}