{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T15:53:17Z","timestamp":1785426797439,"version":"3.56.0"},"reference-count":18,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2024,12,31]],"date-time":"2024-12-31T00:00:00Z","timestamp":1735603200000},"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":[[2025,3,11]]},"abstract":"\n The Chou-Orlandi batch oblivious transfer (OT) protocol is a particularly attractive OT protocol that bridges the gap between practical efficiency and strong security guarantees and is especially notable due to its simplicity. The security analysis provided by Chou and Orlandi bases the security of their protocol on the hardness of the computational Diffie-Hellman (CDH) problem in prime-order groups. Concretely, in groups in which no better-than-generic algorithms are known for the CDH problem, their security analysis yields that an attacker running in time\n \n \n t<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n and issuing\n \n \n q<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n random-oracle queries breaks the security of their protocol with probability at most\n \n \n \u03f5<\/mml:mi>\n \u2264<\/mml:mo>\n \n q<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \u00b7<\/mml:mi>\n t<\/mml:mi>\n \/<\/mml:mo>\n \n 2<\/mml:mn>\n \n \u03ba<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n , where\n \n \n \u03ba<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n is the bit-length of the group's order. This concrete bound, however, is somewhat insufficient for 256-bit groups (e.g., for\n \n \n \u03ba<\/mml:mi>\n =<\/mml:mo>\n 256<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n , it does not provide any guarantee already for\n \n \n t<\/mml:mi>\n =<\/mml:mo>\n \n 2<\/mml:mn>\n \n 48<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n and\n \n \n q<\/mml:mi>\n =<\/mml:mo>\n \n 2<\/mml:mn>\n \n 40<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n ).\n <\/jats:p>\n In this work, we establish a tighter concrete security bound for the Chou-Orlandi protocol. First, we introduce the list square Diffie-Hellman problem and present a tight reduction from the security of the protocol to the hardness of solving the list square Diffie-Hellman problem. That is, we completely shift the task of analyzing the concrete security of the protocol to that of analyzing the concrete hardness of the list square Diffie-Hellman problem. Second, we reduce the hardness of the list square Diffie-Hellman problem to that of the decisional Diffie-Hellman (DDH) problem without incurring a multiplicative loss. Our key observation is that although CDH and DDH have the same assumed concrete hardness, relying on the hardness of DDH enables our reduction to efficiently test the correctness of the solutions it produces.<\/jats:p>\n \n Concretely, in groups in which no better-than-generic algorithms are known for the DDH problem, our analysis yields that an attacker running in time\n \n \n t<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n and issuing\n \n \n q<\/mml:mi>\n \u2264<\/mml:mo>\n t<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n random-oracle queries breaks the security of the Chou-Orlandi protocol with probability at most\n \n \n \u03f5<\/mml:mi>\n \u2264<\/mml:mo>\n t<\/mml:mi>\n \/<\/mml:mo>\n \n 2<\/mml:mn>\n \n \u03ba<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n (i.e., we eliminate the above multiplicative\n \n \n \n q<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n term). We prove our results within the standard real-vs-ideal framework considering static corruptions by malicious adversaries, and provide a concrete security treatment by accounting for the statistical distance between a real-model execution and an ideal-model execution.\n <\/jats:p>","DOI":"10.62056\/akp2fhsfg","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:23:17Z","timestamp":1744132997000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Tighter Concrete Security for the Simplest OT"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3167-3294","authenticated-orcid":false,"given":"Iftach","family":"Haitner","sequence":"first","affiliation":[{"name":"Stellar Development Foundation","place":["USA"]},{"id":[{"id":"https:\/\/ror.org\/04mhzgx49","id-type":"ROR","asserted-by":"publisher"}],"name":"Tel-Aviv University","place":["Israel"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8073-579X","authenticated-orcid":false,"given":"Gil","family":"Segev","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03qxff017","id-type":"ROR","asserted-by":"publisher"}],"name":"School of Computer Science and Engineering, Hebrew University of Jerusalem","place":["Israel"]},{"name":"Coinbase","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"ref1:Rabin81","volume-title":"How to exchange secret by oblivious transfer","author":"Michael O. Rabin","year":"1981"},{"key":"ref2:EvenGL85","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1145\/3812.3818","article-title":"A Randomized Protocol for Signing Contracts.","volume":"28","author":"Shimon Even","year":"1985","journal-title":"Communications of the ACM"},{"key":"ref3:BellareM89","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1007\/0-387-34805-0_48","article-title":"Non-Interactive Oblivious Transfer and Applications","volume":"435","author":"Mihir Bellare","year":"1990"},{"key":"ref4:NaorP01","first-page":"448","article-title":"Efficient Oblivious Transfer Protocols","author":"Moni Naor","year":"2001"},{"key":"ref5:AielloIR01","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-44987-6_8","article-title":"Priced Oblivious Transfer: How to Sell Digital Goods","volume":"2045","author":"William Aiello","year":"2001"},{"key":"ref6:Lindell08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-540-79263-5_4","article-title":"Efficient Fully-Simulatable Oblivious Transfer","volume":"4964","author":"Andrew Y. Lindell","year":"2008"},{"key":"ref7:PeikertVW08","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-540-85174-5_31","article-title":"A Framework for Efficient and Composable Oblivious\n Transfer","volume":"5157","author":"Chris Peikert","year":"2008"},{"key":"ref8:ChouO15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-319-22174-8_3","article-title":"The Simplest Protocol for Oblivious Transfer","volume":"9230","author":"Tung Chou","year":"2015"},{"key":"ref9:ChouO15ePrint","volume-title":"The Simplest Protocol for Oblivious Transfer","author":"Tung Chou","year":"2015"},{"key":"ref10:FiatS86","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","article-title":"How to Prove Yourself: Practical Solutions to\n Identification and Signature Problems","volume":"263","author":"Amos Fiat","year":"1987"},{"key":"ref11: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":"ref12:BressonCP04","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-540-24632-9_11","article-title":"New Security Results on Encrypted Key Exchange","volume":"2947","author":"Emmanuel Bresson","year":"2004"},{"key":"ref13:Shoup97","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","article-title":"Lower Bounds for Discrete Logarithms and Related Problems","volume":"1233","author":"Victor Shoup","year":"1997"},{"key":"ref14:KushilevitzLR10","doi-asserted-by":"publisher","first-page":"2090","DOI":"10.1137\/090755886","article-title":"Information-Theoretically Secure Protocols and Security\n under Composition","volume":"39","author":"Eyal Kushilevitz","year":"2010","journal-title":"SIAM Journal on Computing"},{"key":"ref15:Maurer05","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11586821_1","article-title":"Abstract Models of Computation in Cryptography (Invited\n Paper)","volume":"3796","author":"Ueli M. Maurer","year":"2005"},{"key":"ref16:Pagh00","first-page":"487","article-title":"Faster deterministic dictionaries","author":"Rasmus Pagh","year":"2000"},{"key":"ref17:PaghR04","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","article-title":"Cuckoo hashing","volume":"51","author":"Rasmus Pagh","year":"2004","journal-title":"Journal of Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"electronic"},{"key":"ref18:ArbitmanNS10","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1109\/FOCS.2010.80","article-title":"Backyard Cuckoo Hashing: Constant Worst-Case Operations\n with a Succinct Representation","author":"Yuriy Arbitman","year":"2010"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:23:56Z","timestamp":1744133036000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/1\/11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":18,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,8]]}},"URL":"https:\/\/doi.org\/10.62056\/akp2fhsfg","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"assertion":[{"value":"2024-12-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-1-13"}}