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...
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.
Non-malleable commitments are a fundamental cryptographic tool for preventing against (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. But constructions of two-round, or non-interactive, nonmalleable 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 subexponential “standard-type” assumptions-notably, assuming the existence 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 2t, 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 2t repeated squarings mod N = pq require “roughly” 2t parallel time. Our notion of a “weak” time-lock puzzle, requires only that the puzzle cannot be solved in parallel time 2tϵ(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.
Non-malleable commitments, introduced by Dolev, Dwork and Naor (STOC 1991), are a fundamental cryptographic primitive, and their round complexity has been a subject of great interest. And yet, the goal of achieving non-malleable commitments with only one or two rounds has been elusive. Pass (TCC 2013) captured this difficulty by proving important impossibility results regarding two-round non-malleable commitments. This led to the widespread belief that achieving two-round nonmalleable commitments was impossible from standard assumptions. We show that this belief was false. Indeed, we obtain the following positive results: We construct two-message non-malleable commitments satisfying non-malleability with respect to commitment, based on standard sub-exponential assumptions, namely: sub-exponential one-way permutations, sub-exponential ZAPs, and sub-exponential DDH. Furthermore, our protocol is public-coin.; We obtain two-message private-coin non-malleable commitments with respect to commitment, assuming only sub-exponential DDH or QR or Nth-residuosity.; We bootstrap the above protocols (under the same assumptions) to obtain two round constant boundedconcurrent non-malleable commitments. In the simultaneous message model, we obtain unbounded concurrent non-malleability in two rounds.; In the simultaneous messages model, we obtain oneround non-malleable commitments, with unbounded concurrent security with respect to opening, under standard sub-exponential assumptions.; This implies non-interactive non-malleable commitments with respect to opening, in a restricted model with a broadcast channel, and a-priori bounded polynomially many parties such that every party is aware of every other party in the system. To the best of our knowledge, this is the first protocol to achieve completely non-interactive non-malleability in any plain model setting from standard assumptions.; As an application of this result, in the simultaneous exchange model, we obtain two-round multi-party pseudorandom coin-flipping.; We construct two-message zero-knowledge arguments with super-polynomial strong simulation (SPSS-ZK), which also serve as an important tool for our constructions of non-malleable commitments.; In order to obtain our results, we develop several techniques that may be of independent interest.; We give the first two-round black-box rewinding strategy based on standard sub-exponential assumptions, in the plain model.;- We also give a two-round tag amplification technique for non-malleable commitments, that amplifies a 4-tag scheme to a scheme for all tags, while relying on sub-exponential DDH. This includes a more efficient alternative to the DDN encoding.
We present a non-malleable commitment scheme that retains its security properties even when concurrently executed a polynomial number of times. That is, a man-in-the-middle adversary who is simultaneously participating in multiple concurrent commitment phases of our scheme, both as a sender and as a receiver cannot make the values he commits to depend on the values he receives commitments to. Our result is achieved without assuming an a-priori bound on the number of executions and without relying on any set-up assumptions. Our construction relies on the existence of standard collision resistant hash functions and only requires a constant number of communication rounds.
One of the central questions in Cryptography today is proving security of the protocols "on the Internet", i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called "man-in-the-middle" attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, the main challenge in this setting is to provide security with respect to adaptive concurrent composition of protocols and also the non-malleability property, where the "man-in-the-middle" attacks are prevented. Despite much research effort, we do not know how to implement many basic tasks in this setting (which features concurrent composition and man-in-the-middle attacks). Indeed, even
Commitment schemes are fundamental building blocks in cryptography, and have wide applications in constructing various protocols. Non-malleable commitment considers concurrent executions of a commitment scheme against a man-in-the-middle adversary. In this paper, we investigate non-malleability of statistically hiding commitment schemes, and present the first concurrent non-malleable statistically hiding commitment scheme. Our protocol admits black-box simulation, and relies on the robust (stand-alone) non-malleable commitment and specially designed witness indistinguishable proofs to achieve concurrent non-malleability. Based on the one-way function assumption, the commit phase of our protocol needs polynomial rounds, and the decommit phase needs super-logarithmic rounds.