Paper 2017/273

Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles

Huijia Lin, Rafael Pass, and Pratik Soni

Abstract

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, the round-complexity of non-malleable commitments has been extensively studied, leading up to constant-round concurrent non-malleable commitments based only on one-way functions, and even 3-round concurrent non-malleable commitments based on subexponential one-way functions, or standard polynomial-time hardness assumptions, such as, DDH and ZAPs. 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 a two-round concurrent non-malleable commitment based on sub-exponential ``standard-type" assumptions---notably, assuming the existence of all four of the following primitives (all with subexponential 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),(3) can be based on e.g., the discrete log assumption and the RSA assumption. Time-lock puzzles--puzzles that can be solved by ``brute-force" 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 quite extensively studied since; the most popular instantiation relies on the assumption that $2^t$ repeated squarings mod $N = pq$ require ``roughly" $2^t$ parallel time. Our notion of a ``weak" time-lock puzzle requires only that the puzzle cannot be solved in parallel time $2^{t^\epsilon}$ (and thus we only need to rely on the relatively mild assumption that there are no huge improvements in the parallel complexity of repeated squaring algorithms). We additionally show that if replacing assumption (2) for a non-interactive witness indistinguishable proof (NIWI), and (3) for a uniform collision-resistant hash function, then a non-interactive (i.e., one-message) version of our protocol satisfies concurrent non-malleability w.r.t. uniform attackers. Finally, we show that our two-round (and non-interactive) non-malleable commitments, in fact, satisfy an even stronger notion of Chosen Commitment Attack (CCA) security (w.r.t. uniform attackers).

Note: The new version minor differences from the original publication -- includes a strengthening of the definition of non-malleability from the previous version and detailed proofs of one-many non-malleability implies concurrent non-malleability and the log-n trick along with minor modifications in the overall structure of the paper.