research-article

Constant-Round Nonmalleable Commitments from Any One-Way Function

Authors:

Rafael PassAuthors Info & Claims

Journal of the ACM (JACM), Volume 62, Issue 1

Article No.: 5, Pages 1 - 30

https://doi.org/10.1145/2699446

Published: 02 March 2015 Publication History

Abstract

We show unconditionally that the existence of commitment schemes implies the existence of constant-round nonmalleable commitments; earlier protocols required additional assumptions such as collision-resistant hash functions or subexponential one-way functions.

Our protocol also satisfies the stronger notions of concurrent nonmalleability and robustness. As a corollary, we establish that constant-round nonmalleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multiparty computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.

References

[1]

Boaz Barak. 2001. How to go beyond the black-box simulation barrier. In Proceedings of the FOCS'01. 106--115.

Digital Library

[2]

Boaz Barak. 2002. Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS'02). IEEE Computer Society, 345--355.

Digital Library

[3]

Manuel Blum. 1983. Coin flipping by telephone a protocol for solving impossible problems. SIGACT News 15, 1, 23--27.

Digital Library

[4]

Gilles Brassard, David Chaum, and Claude Crépeau. 1988. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37, 2, 156--189.

Digital Library

[5]

Ran Canetti and Marc Fischlin. 2001. Universally composable commitments. In Proceedings of CRYPTO'01. 19--40.

Digital Library

[6]

Benny Chor and Michael O. Rabin. 1987. Achieving independence in logarithmic number of rounds. In Proceedings of PODC. 260--268.

Digital Library

[7]

Giovanni Di Crescenzo, Yuval Ishai, and Rafail Ostrovsky. 2001a. Universal service-providers for private information retrieval. J. Crypt. 14, 1, 37--74.

Digital Library

[8]

Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, and Adam Smith. 2001b. Efficient and non-interactive non-malleable commitment. In Proceedings of EUROCRYPT. 40--59.

Digital Library

[9]

Ivan Damgård and Jens Groth. 2003. Non-interactive and reusable non-malleable commitment schemes. In Proceedings of STOC. 426--437.

Digital Library

[10]

Danny Dolev, Cynthia Dwork, and Moni Naor. 2000. Nonmalleable cryptography. SIAM J. Comput. 30, 2 391--437.

Digital Library

[11]

Uriel Feige and Adi Shamir. 1990. Witness indistinguishable and witness hiding protocols. In Proceedings of STOC'90. 416--426.

Digital Library

[12]

Marc Fischlin and Roger Fischlin. 2009. Efficient Non-malleable commitment schemes. J. Crypt. 22, 4, 530--571.

Digital Library

[13]

Oded Goldreich. 2001. Foundations of Cryptography — Basic Tools. Cambridge University Press.

Digital Library

[14]

Oded Goldreich and Ariel Kahan. 1996. How to construct constant-round zero-knowledge proof systems for NP. J. Crypt. 9, 3, 167--190.

Digital Library

[15]

Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to play ANY mental game. In Proceedings of STOC'87. ACM, New York. 218--229.

Digital Library

[16]

Oded Goldreich, Silvio Micali, and Avi Wigderson. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 3, 690--728.

Digital Library

[17]

Shafi Goldwasser and Silvio Micali. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2, 270--299.

[18]

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1, 186--208.

Digital Library

[19]

Vipul Goyal. 2011. Constant round non-malleable protocols using one way functions. In Proceedings of STOC. 695--704.

Digital Library

[20]

Johan Håstad, Russell Impagliazzo, Leonid Levin, and Michael Luby. 1999. A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 12--24.

Digital Library

[21]

Russell Impagliazzo and Michael Luby. 1989. One-way functions are essential for complexity based cryptography (extended abstract). In Proceedings of FOCS. 230--235.

Digital Library

[22]

Jonathan Katz, Rafail Ostrovsky, and Adam Smith. 2003. Round efficiency of multi-party computation with a dishonest majority. In Proceedings of EUROCRYPT'03. 578--595.

Digital Library

[23]

Huijia Lin and Rafael Pass. 2009. Non-malleability amplification. In Proceedings of STOC'09. 189--198.

Digital Library

[24]

Huijia Lin and Rafael Pass. 2011. Constant-round non-malleable commitments from any one-way function. In Proceedings of STOC. 705--714.

Digital Library

[25]

Huijia Lin, Rafael Pass, Wei-Lung Dustin Tseng, and Muthuramakrishnan Venkitasubramaniam. 2010. Concurrent non-malleable zero knowledge proofs. In Proceedings of CRYPTO. 429--446.

Digital Library

[26]

Huijia Lin, Rafael Pass, and Muthuramakrishnan Venkitasubramaniam. 2008. Concurrent non-malleable commitments from any one-way function. In Proceedings of TCC'08. 571--588.

Digital Library

[27]

Huijia Lin, Rafael Pass, and Muthuramakrishnan Venkitasubramaniam. 2009. A unified framework for concurrent security: universal composability from stand-alone non-malleability. In Proceedings of STOC'09. 179--188.

Digital Library

[28]

Moni Naor. 1991. Bit commitment using pseudorandomness. J. Crypt. 4, 151--158.

Digital Library

[29]

Moni Naor and Moti Yung. 1989. Universal one-way hash functions and their cryptographic applications. In Proceedings of STOC. 33--43.

Digital Library

[30]

Omkant Pandey, Rafael Pass, and Vinod Vaikuntanathan. 2008. Adaptive one-way functions and applications. In Proceedings of the 28th Annual conference on Cryptology CRYPTO'08. Springer-Verlag, Berlin, Heidelberg, 57--74.

Digital Library

[31]

Rafael Pass. 2004. Bounded-concurrent secure multi-party computation with a dishonest majority. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC'04). ACM, New York, NY, USA, 232--241.

Digital Library

[32]

Rafael Pass and Alon Rosen. 2005a. Concurrent non-malleable commitments. In Proceedings of FOCS. 563--572.

Digital Library

[33]

Rafael Pass and Alon Rosen. 2005b. New and improved constructions of non-malleable cryptographic protocols. In Proceedings of STOC'05. 533--542.

Digital Library

[34]

Rafael Pass and Hoeteck Wee. 2010. Constant-round non-malleable commitment from strong one-way functions. In Proceedings of Eurocrypt'10.

Digital Library

[35]

John Rompel. 1990. One-way functions are necessary and sufficient for secure signatures. In Proceedings of STOC. 387--394.

Digital Library

[36]

Amit Sahai. 1999. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In Proceedings of FOCS. 543--553.

Digital Library

[37]

Hoeteck Wee. 2010. Black-box, round-efficient secure computation via non-malleability amplification. In Proceedings of FOCS'10. 531--540.

Digital Library

Cited By

Chan TWen TXie HXue Q(2023)Game-Theoretically Secure Protocols for the Ordinal Random Assignment ProblemApplied Cryptography and Network Security10.1007/978-3-031-33491-7_22(582-610)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-33491-7_22
Phung QKim MLee E(2022)Identifying Incorrect Patches in Program Repair Based on Meaning of Source CodeIEEE Access10.1109/ACCESS.2022.314598310(12012-12030)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3145983
Ciampi MOrsini ESiniscalchi L(2022)Four-Round Black-Box Non-malleable Schemes from One-Way PermutationsTheory of Cryptography10.1007/978-3-031-22365-5_11(300-329)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-22365-5_11
Show More Cited By

Index Terms

Constant-Round Nonmalleable Commitments from Any One-Way Function
1. Theory of computation
  1. Models of computation

Recommendations

Constant-round non-malleable commitments from any one-way function
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way ...
Nonmalleable Cryptography

The notion of nonmalleable cryptography, an extension of semantically secure cryptography, is defined. Informally, in the context of encryption the additional requirement is that given the ciphertext it is impossible to generate a different ciphertext ...
New and Improved Constructions of Nonmalleable Cryptographic Protocols

We present a new constant-round protocol for nonmalleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for nonmalleable commitments. Our constructions rely on the existence of (standard) collision-...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 62, Issue 1

February 2015

264 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2742144

Editor:
Victor Vianu
University of California, San Diego

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 March 2015

Accepted: 01 September 2014

Received: 01 April 2012

Revised: 01 March 2012

Published in JACM Volume 62, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Alfred P. Sloan Fellowship, Microsoft New Faculty Fellowship, NSF Award CNS-1217821, NSF CAREER Award CCF-0746990, NSF Award CCF-1214844, AFOSR YIP Award FA9550-10-1-0093, and DARPA and AFRL
Defense Advanced Research Projects Agency or the US Government

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
270
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chan TWen TXie HXue Q(2023)Game-Theoretically Secure Protocols for the Ordinal Random Assignment ProblemApplied Cryptography and Network Security10.1007/978-3-031-33491-7_22(582-610)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-33491-7_22
Phung QKim MLee E(2022)Identifying Incorrect Patches in Program Repair Based on Meaning of Source CodeIEEE Access10.1109/ACCESS.2022.314598310(12012-12030)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3145983
Ciampi MOrsini ESiniscalchi L(2022)Four-Round Black-Box Non-malleable Schemes from One-Way PermutationsTheory of Cryptography10.1007/978-3-031-22365-5_11(300-329)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-22365-5_11
Kiyoshima S(2020)Statistical Concurrent Non-Malleable Zero-Knowledge from One-Way FunctionsJournal of Cryptology10.1007/s00145-020-09348-x33:3(1318-1361)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s00145-020-09348-x
Abraham IDolev DHalpern J(2019)Distributed Protocols for Leader ElectionACM Transactions on Economics and Computation10.1145/33037127:1(1-26)Online publication date: 14-Feb-2019
https://dl.acm.org/doi/10.1145/3303712
Komargodski IYogev E(2018)Another Step Towards Realizing Random Oracles: Non-malleable Point ObfuscationAdvances in Cryptology – EUROCRYPT 201810.1007/978-3-319-78381-9_10(259-279)Online publication date: 31-Mar-2018
https://doi.org/10.1007/978-3-319-78381-9_10
Chung KGuo YLin WPass RShi E(2018)Game Theoretic Notions of Fairness in Multi-party Coin TossTheory of Cryptography10.1007/978-3-030-03807-6_21(563-596)Online publication date: 11-Nov-2018
https://dl.acm.org/doi/10.1007/978-3-030-03807-6_21
Ciampi MOstrovsky RSiniscalchi LVisconti I(2017)Four-Round Concurrent Non-Malleable Commitments from One-Way FunctionsAdvances in Cryptology – CRYPTO 201710.1007/978-3-319-63715-0_5(127-157)Online publication date: 29-Jul-2017
https://doi.org/10.1007/978-3-319-63715-0_5
Ai ZRen G(2016)Dynamic analysis of a transversely isotropic multilayered half-plane subjected to a moving loadSoil Dynamics and Earthquake Engineering10.1016/j.soildyn.2016.01.02283(162-166)Online publication date: Apr-2016
https://doi.org/10.1016/j.soildyn.2016.01.022
Cohen RCoretti SGaray JZikas V(2016)Probabilistic Termination and Composability of Cryptographic ProtocolsProceedings, Part III, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 981610.1007/978-3-662-53015-3_9(240-269)Online publication date: 14-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-662-53015-3_9
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents