{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:45Z","timestamp":1787340225333,"version":"build-2736575974"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Galois"},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["W911NF- 15-C-0236"],"award-info":[{"award-number":["W911NF- 15-C-0236"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-11-2-0211"],"award-info":[{"award-number":["FA8750-11-2-0211"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-08-1-0197"],"award-info":[{"award-number":["FA9550-08-1-0197"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-10-1-0093"],"award-info":[{"award-number":["FA9550-10-1-0093"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010336","name":"Hellman Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010336","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1217821"],"award-info":[{"award-number":["CNS-1217821"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1214844"],"award-info":[{"award-number":["CCF-1214844"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0746990"],"award-info":[{"award-number":["CCF-0746990"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1528178"],"award-info":[{"award-number":["CNS-1528178"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1514526"],"award-info":[{"award-number":["CNS-1514526"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1652849"],"award-info":[{"award-number":["CNS-1652849"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2006317"],"award-info":[{"award-number":["2006317"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>Non-malleable commitments are a fundamental cryptographic tool for preventing (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991, their round-complexity has been extensively studied, leading up to constant-round protocols based on one-way functions (OWFs), and three-round protocols based on sub-exponential OWFs, and standard polynomial-time hardness assumptions such as decisional Diffie--Hellman (DDH) and ZAPs (i.e., two-round witness-indistinguishable proofs). But constructions of two-round, or non-interactive, non-malleable commitments have so far remained elusive; the only known construction relied on a strong and non-falsifiable assumption with a non-malleability flavor. Additionally, a recent result by Pass shows the impossibility of basing two-round non-malleable commitments on falsifiable assumptions using a polynomial-time black-box security reduction. In this work, we show how to overcome this impossibility using super-polynomial-time hardness assumptions. Our main result demonstrates the existence of two-round concurrent non-malleable commitments based on the following four primitives (all with sub-exponential security): (1) non-interactive commitments, (2) ZAPs (i.e., 2-round witness indistinguishable proofs), (3) collision-resistant hash functions, and (4) a \u201cweak\u201d time-lock puzzle. Primitives (1), (2), and (3) can be based on, e.g., the discrete log and the RSA assumption. Time-lock puzzles---puzzles that can be solved by \u201cbrute-force\u201d in time $2^t$, but cannot be solved significantly faster even using parallel computers---were proposed by Rivest, Shamir, and Wagner in 1996 and have been extensively studied since. We additionally obtain a non-interactive (i.e., one-message) version of our protocol satisfying concurrent non-malleability w.r.t. uniform attackers and show that our non-malleable commitments satisfy an even stronger notion of chosen commitment attack security.<\/jats:p>","DOI":"10.1137\/17m1163177","type":"journal-article","created":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T12:11:05Z","timestamp":1579176665000},"page":"FOCS17-196-FOCS17-279","source":"Crossref","is-referenced-by-count":3,"title":["Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles"],"prefix":"10.1137","volume":"49","author":[{"given":"Huijia","family":"Lin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3225-3323","authenticated-orcid":true,"given":"Pratik","family":"Soni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,1,16]]},"reference":[{"key":"atypb1","unstructured":"M. Ball, D. Dachman-Soled, M. Kulkarni, H. Lin, and T. Malkin,\n                      Non-Malleable Codes against Bounded Polynomial Time Tampering\n                      , Cryptology ePrint Archive, Report 2018\/1015, 2018,https:\/\/eprint.iacr.org\/2018\/1015."},{"key":"atypb2","first-page":"345","author":"Barak B.","year":"2002","journal-title":"Washington, DC"},{"key":"atypb3","first-page":"299","author":"Barak B.","year":"2003","journal-title":"Heidelberg"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"B. Barak and R. Pass,\n                      On the possibility of one-message weak zero-knowledge\n                      , in TCC 2004, M. Naor, ed., Lecture Notes in Comput. Sci. 2951, Springer, Heidelberg, 2004, pp. 121-132,https:\/\/doi.org\/10.1007\/978-3-540-24638-1_7.","DOI":"10.1007\/978-3-540-24638-1_7"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF00208000"},{"key":"atypb6","first-page":"345","author":"Bitansky N.","year":"2016","journal-title":"New York"},{"key":"atypb7","first-page":"209","author":"Bitansky N.","year":"2018","journal-title":"Cham"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"N. Bitansky and O. Paneth,\n                      ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation\n                      , in TCC 2015, Part II, Y. Dodis and J. B. Nielsen, eds., Lecture Notes in Comput. Sci. 9015, Springer, Heidelberg, 2015, pp. 401-427,https:\/\/doi.org\/10.1007\/978-3-662-46497-7_16.","DOI":"10.1007\/978-3-662-46497-7_16"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398521"},{"key":"atypb10","first-page":"236","author":"Boneh D.","year":"2000","journal-title":"Heidelberg"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, S. Halevi, and A. Polychroniadou,\n                      Four round secure computation without setup\n                      , in TCC 2017, Part I, Y. Kalai and L. Reyzin, eds., Lecture Notes in Comput. Sci. 10677, Springer, Heidelberg, 2017, pp. 645-677,https:\/\/doi.org\/10.1007\/978-3-319-70500-2_22.","DOI":"10.1007\/978-3-319-70500-2_22"},{"key":"atypb12","first-page":"541","author":"Canetti R.","year":"2010","journal-title":"Washington, DC"},{"key":"atypb13","first-page":"270","author":"Ciampi M.","year":"2016","journal-title":"Heidelberg"},{"key":"atypb14","first-page":"127","author":"Ciampi M.","year":"2017","journal-title":"Heidelberg"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291562"},{"key":"atypb16","first-page":"139","author":"Dwork C.","year":"1993","journal-title":"Heidelberg"},{"key":"atypb17","first-page":"283","author":"Dwork C.","year":"2000","journal-title":"Washington, DC"},{"key":"atypb18","first-page":"308","author":"Feige U.","year":"1990","journal-title":"Washington, DC"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-010-9080-z"},{"key":"atypb20","first-page":"25","author":"Goldreich O.","year":"1989","journal-title":"New York"},{"key":"atypb21","first-page":"695","author":"Goyal V.","year":"2011","journal-title":"New York"},{"key":"atypb22","first-page":"21","author":"Goyal V.","year":"2016","journal-title":"Washington, DC"},{"key":"atypb23","first-page":"51","author":"Goyal V.","year":"2012","journal-title":"Washington, DC"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"V. Goyal, H. Lin, O. Pandey, R. Pass, and A. Sahai,\n                      Round-efficient concurrently composable secure computation via a robust extraction lemma\n                      , in TCC 2015, Part I, Y. Dodis and J. B. Nielsen, eds., Lecture Notes in Comput. Sci. 9014, Springer, Heidelberg, 2015, pp. 260-289,https:\/\/doi.org\/10.1007\/978-3-662-46494-6_12.","DOI":"10.1007\/978-3-662-46494-6_12"},{"key":"atypb25","first-page":"1128","author":"Goyal V.","year":"2016","journal-title":"New York"},{"key":"atypb26","first-page":"97","author":"Groth J.","year":"2006","journal-title":"Heidelberg"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"M. Jakobsson and A. Juels,\n                      Proofs of work and bread pudding protocols\n                      , in Proceedings of the IFIP TC6\/TC11 Joint Working Conference on Secure Information Networks: Communications and Multimedia Security, CMS '99, Deventer, The Netherlands, 1999, Kluwer, Dordrecht, The Netherlands, pp. 258-272,http:\/\/dl.acm.org\/citation.cfm?id=647800.757199.","DOI":"10.1007\/978-0-387-35568-9_18"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"D. Khurana,\n                      Round optimal concurrent non-malleability from polynomial hardness\n                      , in TCC 2017, Part II, Y. Kalai and L. Reyzin, eds., Lecture Notes in Comput. Sci. 10678, Springer, Heidelberg, 2017, pp. 139-171,https:\/\/doi.org\/10.1007\/978-3-319-70503-3_5.","DOI":"10.1007\/978-3-319-70503-3_5"},{"key":"atypb29","first-page":"564","author":"Khurana D.","year":"2017","journal-title":"Washington, DC"},{"key":"atypb30","first-page":"351","author":"Kiyoshima S.","year":"2014","journal-title":"Heidelberg"},{"key":"atypb31","first-page":"189","author":"Lin H.","year":"2009","journal-title":"New York"},{"key":"atypb32","first-page":"705","author":"Lin H.","year":"2011","journal-title":"New York"},{"key":"atypb33","first-page":"461","author":"Lin H.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"H. Lin, R. Pass, and M. Venkitasubramaniam,\n                      Concurrent non-malleable commitments from any one-way function\n                      , in TCC 2008, R. Canetti, ed., Lecture Notes in Comput. Sci. 4948, Springer, Heidelberg, 2008, pp. 571-588,https:\/\/doi.org\/10.1007\/978-3-540-78524-8_31.","DOI":"10.1007\/978-3-540-78524-8_31"},{"key":"atypb35","unstructured":"T. May,\n                      Timed-Release Crypto\n                      , 1993,http:\/\/cypherpunks.venona.com\/date\/1993\/02\/msg00129.html."},{"key":"atypb36","unstructured":"S. Nakamoto,\n                      Bitcoin: A Peer-to-Peer Electronic Cash System, 2008\n                      , 2012,http:\/\/www.bitcoin.org\/bitcoin.pdf."},{"key":"atypb37","first-page":"57","author":"Pandey O.","year":"2008","journal-title":"Heidelberg"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"R. Pass,\n                      Unprovable security of perfect NIZK and non-interactive non-malleable commitments\n                      , in TCC 2013, A. Sahai, ed., Lecture Notes in Comput. Sci. 7785, Springer, Heidelberg, 2013, pp. 334-354,https:\/\/doi.org\/10.1007\/978-3-642-36594-2_19.","DOI":"10.1007\/978-3-642-36594-2_19"},{"key":"atypb39","first-page":"563","author":"Pass R.","year":"2005","journal-title":"Washington, DC"},{"key":"atypb40","first-page":"533","author":"Pass R.","year":"2005","journal-title":"New York"},{"key":"atypb41","first-page":"638","author":"Pass R.","year":"2010","journal-title":"Heidelberg"},{"key":"atypb42","unstructured":"R. L. Rivest, A. Shamir, and D. A. Wagner,\n                      Time-Lock Puzzles and Timed-Release Crypto\n                      , Tech. report, Massachusetts Institute of Technology, Cambridge, MA, 1996."},{"key":"atypb43","first-page":"211","author":"Rogaway P.","year":"2006","journal-title":"Heidelberg"},{"key":"atypb44","first-page":"531","author":"Wee H.","year":"2010","journal-title":"Washington, DC"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1163177","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:39Z","timestamp":1787336739000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1163177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/17M1163177"],"URL":"https:\/\/doi.org\/10.1137\/17m1163177","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}