Welcome to the resource topic for 2017/273
Title:
Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles
Authors: Huijia Lin, Rafael Pass, 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).
ePrint: https://eprint.iacr.org/2017/273
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .