{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T11:12:27Z","timestamp":1785409947575,"version":"3.56.0"},"reference-count":54,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"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,12,3]]},"abstract":"<jats:p>A central question in the theory of cryptography is whether we can build protocols that achieve stronger security guarantees, e.g., security against malicious adversaries,  by combining building blocks that achieve much weaker security guarantees, e.g., security only against semi-honest adversaries; and with the minimal number of rounds. An additional focus is whether these building blocks can be used only as a black-box. Since Oblivious Transfer (OT) is the necessary and sufficient building block to securely realize any two-party (and multi-party) functionality, theoreticians often focus on proving whether maliciously secure OT can be built from a weaker notion of OT.<\/jats:p>\n                  <jats:p>There is a rich body of literature that provides (black-box) compilers that build malicious OT from OTs that achieve weaker security such as semi-malicious OT and defensibly secure OT,  within the minimal number of rounds. However, no round-optimal compiler exists that builds malicious OT from the weakest notion of semi-honest OT, in the plain model.<\/jats:p>\n                  <jats:p>Correlation intractable hash (CIH) functions are special hash functions whose properties allow instantiating the celebrated Fiat-Shamir transform, and hence reduce the round complexity of public-coin proof systems.<\/jats:p>\n                  <jats:p>In this work, we devise the first round-optimal compiler from semi-honest OT to malicious OT, by a novel application of CIH for collapsing rounds in the plain model. We provide the following contributions. First, we provide a new  CIH-based round-collapsing construction for general cut-and-choose. This gadget can be used generally to prove the correctness of the evaluation of a function. Then, we use our gadget to build the first round-optimal compiler from semi-honest OT to malicious OT.<\/jats:p>\n                  <jats:p>Our compiler uses the semi-honest OT protocol and the other building blocks in a black-box manner. However,  for technical reasons,  the underlying CIH construction requires the upper bound of the circuit size of the semi-honest OT protocol used. The need for this upper-bound makes our protocol not fully black-box, hence is incomparable with existing, fully black-box, compilers.<\/jats:p>","DOI":"10.62056\/abe0wa3y6","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T12:00:52Z","timestamp":1736769652000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Round-Optimal Compiler for Semi-Honest to Malicious Oblivious Transfer via CIH"],"prefix":"10.62056","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4390-3096","authenticated-orcid":false,"given":"Varun","family":"Madathil","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03v76x132","id-type":"ROR","asserted-by":"publisher"}],"name":"Yale University","place":["51 Prospect Street, New Haven, CT, 06511, USA"],"department":["Computer Science"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1797-9457","authenticated-orcid":false,"given":"Alessandra","family":"Scafuro","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04tj63d06","id-type":"ROR","asserted-by":"publisher"}],"name":"North Carolina State University","place":["Campus Box 8206 890 Oval Drive, Raleigh, NC, 27695, USA"],"department":["Computer Science"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tanner","family":"Verber","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04tj63d06","id-type":"ROR","asserted-by":"publisher"}],"name":"North Carolina State University","place":["Campus Box 8206 890 Oval Drive, Raleigh, NC, 27695, USA"],"department":["Computer Science"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,1,13]]},"reference":[{"key":"ref1:fiat1986prove","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 Identification\n  and Signature Problems","volume":"263","author":"Amos Fiat","year":"1986"},{"key":"ref2:bellare1993random","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1145\/168588.168596","article-title":"Random Oracles are Practical: A Paradigm for Designing\n  Efficient Protocols","author":"Mihir Bellare","year":"1993"},{"key":"ref3:goldwasser2003security","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1109\/SFCS.2003.1238185","article-title":"On the (In)security of the Fiat-Shamir Paradigm","author":"Shafi Goldwasser","year":"2003"},{"key":"ref4:barak2006lower","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/J.JCSS.2005.06.010","article-title":"Lower bounds for non-black-box zero knowledge","volume":"72","author":"Boaz Barak","year":"2006","journal-title":"J. Comput. Syst. Sci."},{"key":"ref5:canetti2016on","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-662-49096-9_17","article-title":"On the Correlation Intractability of Obfuscated Pseudorandom\n  Functions","volume":"9562","author":"Ran Canetti","year":"2016"},{"key":"ref6:kalai2017from","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-319-63715-0_8","article-title":"From Obfuscation to the Security of Fiat-Shamir for Proofs","volume":"10402","author":"Yael Tauman Kalai","year":"2017"},{"key":"ref7:canetti2018fiat","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-319-78381-9_4","article-title":"Fiat-Shamir and Correlation Intractability from Strong\n  KDM-Secure Encryption","volume":"10820","author":"Ran Canetti","year":"2018"},{"key":"ref8:peikert2019noninteractive","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-030-26948-7_4","article-title":"Noninteractive Zero Knowledge for NP from (Plain) Learning\n  with Errors","volume":"11692","author":"Chris Peikert","year":"2019"},{"key":"ref9:canetti2019fiat","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1145\/3313276.3316380","article-title":"Fiat-Shamir: from practice to theory","author":"Ran Canetti","year":"2019"},{"key":"ref10:lombardi2020multi","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.102","article-title":"Correlation-Intractable Hash Functions via Shift-Hiding","volume":"215","author":"Alex Lombardi","year":"2022"},{"key":"ref11:jain2021noninteractive","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-77870-5_1","article-title":"Non-interactive Zero Knowledge from Sub-exponential DDH","volume":"12696","author":"Abhishek Jain","year":"2021"},{"key":"ref12:choudhuri2023correlation","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-031-38551-3_20","article-title":"Correlation Intractability and SNARGs from Sub-exponential\n  DDH","volume":"14084","author":"Arka Rai Choudhuri","year":"2023"},{"key":"ref13:brakerski2020nizk","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1007\/978-3-030-56877-1_26","article-title":"NIZK from LPN and Trapdoor Hash via Correlation\n  Intractability for Approximable Relations","volume":"12172","author":"Zvika Brakerski","year":"2020"},{"key":"ref14:rabin2005exchange","first-page":"187","article-title":"How To Exchange Secrets with Oblivious Transfer","author":"Michael O. Rabin","year":"2005","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref15:katz2004round","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-540-28628-8_21","article-title":"Round-Optimal Secure Two-Party Computation","volume":"3152","author":"Jonathan Katz","year":"2004"},{"key":"ref16:friolo2019black","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-030-36030-6_5","article-title":"A Black-Box Construction of Fully-Simulatable, Round-Optimal\n  Oblivious Transfer from Strongly Uniform Key Agreement","volume":"11891","author":"Daniele Friolo","year":"2019"},{"key":"ref17:madathil2022from","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITC.2022.5","article-title":"From Privacy-Only to Simulatable OT: Black-Box,\n  Round-Optimal, Information-Theoretic","volume":"230","author":"Varun Madathil","year":"2022"},{"key":"ref18:goldreich1987how","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1145\/28395.28420","article-title":"How to Play any Mental Game or A Completeness Theorem for\n  Protocols with Honest Majority","author":"Oded Goldreich","year":"1987"},{"key":"ref19:ishai2007zero","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/1250790.1250794","article-title":"Zero-knowledge from secure multiparty computation","author":"Yuval Ishai","year":"2007"},{"key":"ref20:canetti2004random","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1008731.1008734","article-title":"The random oracle methodology, revisited","volume":"51","author":"Ran Canetti","year":"2004","journal-title":"J. ACM"},{"key":"ref21:holmgren2018cryptographic","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1109\/FOCS.2018.00085","article-title":"Cryptographic Hashing from Strong One-Way Functions (Or:\n  One-Way Product Functions and Their Applications)","author":"Justin Holmgren","year":"2018"},{"key":"ref22:choudhuri2021snargs","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1109\/FOCS52979.2021.00016","article-title":"SNARGs for\n  $\\mathcal{P}$ from LWE","author":"Arka Rai Choudhuri","year":"2021"},{"key":"ref23:jawale2021snargs","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1145\/3406325.3451055","article-title":"SNARGs for bounded depth computations and PPAD hardness\n  from sub-exponential LWE","author":"Ruta Jawale","year":"2021"},{"key":"ref24:choudhuri2021non","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-030-84259-8_14","article-title":"Non-interactive Batch Arguments for NP from Standard\n  Assumptions","volume":"12828","author":"Arka Rai Choudhuri","year":"2021"},{"key":"ref25:lindell2007efficient","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-540-72540-4_4","article-title":"An Efficient Protocol for Secure Two-Party Computation in\n  the Presence of Malicious Adversaries","volume":"4515","author":"Yehuda Lindell","year":"2007"},{"key":"ref26:haitner2008semi","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-540-78524-8_23","article-title":"Semi-honest to Malicious Oblivious Transfer - The Black-Box\n  Way","volume":"4948","author":"Iftach Haitner","year":"2008"},{"key":"ref27:haitner2011black","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/100790537","article-title":"Black-Box Constructions of Protocols for Secure\n  Computation","volume":"40","author":"Iftach Haitner","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref28:lindell2013fast","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-40084-1_1","article-title":"Fast Cut-and-Choose Based Protocols for Malicious and Covert\n  Adversaries","volume":"8043","author":"Yehuda Lindell","year":"2013"},{"key":"ref29:canetti2018simplerassumptions","first-page":"1004","article-title":"Fiat-Shamir From Simpler Assumptions","author":"Ran Canetti","year":"2018","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref30:goldwasser2008delegating","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1145\/1374376.1374396","article-title":"Delegating computation: interactive proofs for muggles","author":"Shafi Goldwasser","year":"2008"},{"key":"ref31:holmgren2021fiat","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1145\/3406325.3451116","article-title":"Fiat-Shamir via list-recoverable codes (or: parallel\n  repetition of GMW is not zero-knowledge)","author":"Justin Holmgren","year":"2021"},{"key":"ref32:peikert2018privately","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/978-3-319-76581-5_23","article-title":"Privately Constraining and Programming PRFs, the LWE Way","volume":"10770","author":"Chris Peikert","year":"2018"},{"key":"ref33:badrinarayanan2020statistical","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1007\/978-3-030-45727-3_22","article-title":"Statistical ZAP Arguments","volume":"12107","author":"Saikrishna Badrinarayanan","year":"2020"},{"key":"ref34:goyal2020statistical","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1007\/978-3-030-45727-3_23","article-title":"Statistical Zaps and New Oblivious Transfer Protocols","volume":"12107","author":"Vipul Goyal","year":"2020"},{"key":"ref35:ostrovsky2015round","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-662-48000-7_17","article-title":"Round-Optimal Black-Box Two-Party Computation","volume":"9216","author":"Rafail Ostrovsky","year":"2015"},{"key":"ref36:dottling2020two","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1007\/978-3-030-45724-2_26","article-title":"Two-Round Oblivious Transfer from CDH or LPN","volume":"12106","author":"Nico D\u00f6ttling","year":"2020"},{"key":"ref37:choudhuri2021oblivious","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1007\/978-3-030-90453-1_18","article-title":"Oblivious Transfer from Trapdoor Permutations in Minimal\n  Rounds","volume":"13043","author":"Arka Rai Choudhuri","year":"2021"},{"key":"ref38:ishai2022roundrom","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-031-06944-4_8","article-title":"Round-Optimal Black-Box Protocol Compilers","volume":"13275","author":"Yuval Ishai","year":"2022"},{"key":"ref39:kilian1988founding","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/62212.62215","article-title":"Founding Cryptography on Oblivious Transfer","author":"Joe Kilian","year":"1988"},{"key":"ref40:ishai2006black","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/1132516.1132531","article-title":"Black-box constructions for secure computation","author":"Yuval Ishai","year":"2006"},{"key":"ref41:choi2009simple","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-642-00457-5_23","article-title":"Simple, Black-Box Constructions of Adaptively Secure\n  Protocols","volume":"5444","author":"Seung Geol Choi","year":"2009"},{"key":"ref42:pass2009black","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-00457-5_24","article-title":"Black-Box Constructions of Two-Party Protocols from One-Way\n  Functions","volume":"5444","author":"Rafael Pass","year":"2009"},{"key":"ref43:wee2010black","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1109\/FOCS.2010.87","article-title":"Black-Box, Round-Efficient Secure Computation via\n  Non-malleability Amplification","author":"Hoeteck Wee","year":"2010"},{"key":"ref44:goyal2011constant","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1145\/1993636.1993729","article-title":"Constant round non-malleable protocols using one way\n  functions","author":"Vipul Goyal","year":"2011"},{"key":"ref45:lin2012black","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-3-642-32009-5_27","article-title":"Black-Box Constructions of Composable Protocols without\n  Set-Up","volume":"7417","author":"Huijia Lin","year":"2012"},{"key":"ref46:kiyoshima2014constant","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-3-642-54242-8_15","article-title":"Constant-Round Black-Box Construction of Composable\n  Multi-Party Computation Protocol","volume":"8349","author":"Susumu Kiyoshima","year":"2014"},{"key":"ref47:goyal2014black","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1145\/2591796.2591879","article-title":"Black-box non-black-box zero knowledge","author":"Vipul Goyal","year":"2014"},{"key":"ref48:goyal2012constructing","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1109\/FOCS.2012.47","article-title":"Constructing Non-malleable Commitments: A Black-Box\n  Approach","author":"Vipul Goyal","year":"2012"},{"key":"ref49:ishai2021round","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-030-84245-1_8","article-title":"On the Round Complexity of Black-Box Secure MPC","volume":"12826","author":"Yuval Ishai","year":"2021"},{"key":"ref50:asharov2012multiparty","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-29011-4_29","article-title":"Multiparty Computation with Low Communication, Computation\n  and Interaction via Threshold FHE","volume":"7237","author":"Gilad Asharov","year":"2012"},{"key":"ref51:ishai2023round","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-031-38557-5_13","article-title":"Round-Optimal Black-Box MPC in the Plain Model","volume":"14081","author":"Yuval Ishai","year":"2023"},{"key":"ref52:ciampilist2023","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-031-38557-5_15","article-title":"List Oblivious Transfer and Applications to Round-Optimal\n  Black-Box Multiparty Coin Tossing","volume":"14081","author":"Michele Ciampi","year":"2023"},{"key":"ref53:ishai2022round","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-031-22365-5_16","article-title":"Round-Optimal Black-Box Secure Computation from Two-Round\n  Malicious OT","volume":"13748","author":"Yuval Ishai","year":"2022"},{"key":"ref54:canetti1998random","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/276698.276741","article-title":"The Random Oracle Methodology, Revisited (Preliminary\n  Version)","author":"Ran Canetti","year":"1998"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T12:12:14Z","timestamp":1736770334000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/4\/29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,13]]},"references-count":54,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,1,13]]}},"URL":"https:\/\/doi.org\/10.62056\/abe0wa3y6","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,13]]},"assertion":[{"value":"2024-10-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-4-59"}}