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 “weak” 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 “brute-force” in time
2t, 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.
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 functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.
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 functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.