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.
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.
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.
We provide the first constant round constructions of non-malleable commitment and zero-knowledge protocols based only on one-way functions. This improves upon several previous (incomparable) works which required either: (a) super-constant number of rounds, or, (b) non-standard or sub-exponential hardness assumptions, or, (c) non-black-box simulation and collision resistant hash functions. These constructions also allow us to obtain the first constant round multi-party computation protocol relying only on the existence of constant round oblivious transfer protocols. Our primary technique can be seen as a means of implementing the previous “two-slot simulation ” idea in the area of non-malleability with only black-box simulation. A simple modification of our commitment scheme gives a construction which makes use of the underlying one-way function in a black-box way. The modified construction satisfies the notion of what we call nonmalleability w.r.t. replacement. Non-malleability w.r.t. replacement is a slightly weaker yet natural notion of non-malleability which we believe suffices for many application of non-malleable commitments. We show that a commitment scheme which is non-malleable only w.r.t. replacement is sufficient to obtain a (fully) black-box multi-party computation protocol. This allows us to obtain a constant round multi-party computation protocol making only a black-box use of the standard cryptographic primitives with polynomial-time hardness thus directly improving upon the recent work of Wee (FOCS’10). 0 1
We construct two-message non-malleable commitments with respect to opening in the standard model, assuming only one-to-one one-way functions. Our protocol consists of two unidirectional messages by the committer (with no message from the receiver), and is secure against all polynomial-time adversaries in the standard synchronous setting. Pass (TCC 2013) proved that any commitment scheme with non-malleability with respect to commitment, using only 2 rounds of communication, cannot be proved secure via a black-box reduction to any "standard" intractability assumption. We extend this by showing a similar impossibility result for commitments with non-malleability with respect to opening, another standard notion of non-malleability for commitments, for any 2-message challenge-response protocol, as well. However, somewhat surprisingly, we show that this barrier breaks down in the setting of two unidirectional messages by the committer (with no message from the receiver), for non-malleability with respect to opening.°Our protocol makes only black-box use of any non-interactive statistically binding commitment scheme. Such a scheme can be based on any one-to-one one-way function.°Our techniques depart significantly from the commit-challenge-response structure followed by nearly all prior works on non-malleable protocols in the standard model. Our methods are combinatorial in nature.°Our protocol resolves the round complexity of commitments with non-malleability with respect to opening via natural (non-embedding) black-box security reductions. We show that completely non-interactive non-malleable commitments w.r.t. opening cannot be proved secure via most natural black-box reductions. This result extends to also rule out bi-directional two-message non-malleable commitments w.r.t. opening in the synchronous or asynchronous setting.°Our protocol, together with our impossibility result, also resolves the round complexity of block-wise non-malleable codes (Chandran et al) w.r.t. natural black-box reductions.
Non-malleable commitment is one of the most fundamental cryptographic primitives in that it is often used as a basic building block in modern cryptography. Briefly, a commitment scheme allows a sender to commit to a value while keeping the value secret from the receiver. In addition, when the commitment is opened in a later stage, the scheme guarantees that the sender can reveal only the unique value being committed to in the previous stage. A commitment scheme is said to be non-malleable if no adversary can succeed in committing to a related massage m', after seeing a commitment of a message m. In this dissertation, we study the construction of non-malleable commitments and some of their applications.A black-box construction of non-malleable commitment is presented in the first part of this dissertation. Our protocol requires only a constant number of rounds and satisfies the standard notion of non-malleability w.r.t. commitment. Our technique is based on ideas from the ``zero-knowledge from secure multi-party computation'' paradigm by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). Furthermore, our construction only uses one-way functions as a black-box and thus does not depend on the actual implementation details of the functions. Prior to our result, under the standard notion of security, no black-box construction of constant-round non-malleable commitment was known. Hence, our main result closes the gap between black-box and non-black-box constructions for the problem of non-malleable commitment.In the second part of this dissertation, we show that our technique can be applied to multiple applications. Specifically, we extend our work to obtain a constant-round concurrent non-malleable commitment, a constant-round multi-party parallel coin tossing, and a non-malleable statistically hiding commitment (according to the notion of non-malleability w.r.t. opening.) Additionally, all results mentioned above are based only on a black-box use of one-way functions.
We propose the first black-box construction of non-malleable commitments according to the standard notion of non-malleability with respect to commitment. Our construction additionally only requires a constant number of rounds and is based only on (black-box use of) one-way functions. Prior to our work, no black-box construction of non-malleable commitments was known (except for relaxed notions of security) in any (polynomial) number of rounds based on any cryptographic assumption. This closes the wide gap existent between black-box and non-black-box constructions for the problem of non-malleable commitments. Our construction relies on (and can be seen as a generalization of) the recent non-malleable commitment scheme of Goyal (STOC 2011). We also show how to get black-box constructions for a host of other cryptographic primitives. We extend our construction to get constant-round concurrent non-malleable commitments, constant-round multi-party coin tossing, and non-malleable statistically hiding commitments (satisfying the notion of non-malleability with respect to opening). All of the mentioned results make only a black-box use of one-way functions. Our primary technical contribution is a novel way of implementing the proof of consistency typically required in the constructions of non-malleable commitments (and other related primitives). We do this by relying on ideas from the ``zero-knowledge from secure multi-party computation" paradigm of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). We extend in a novel way this ``computation in the head" paradigm (which can be though of as bringing powerful error-correcting codes into purely computational setting). To construct a non-malleable commitment scheme, we apply our computation in the head techniques to the recent (constant-round) construction of Goyal. Along the way, we also present a simplification of the construction of Goyal where a part of the protocol is implemented in an information theoretic manner. Such a simplification is crucial for getting a black-box construction. This is done by making use of pair wise-independent hash functions and strong randomness extractors. We show that our techniques have multiple applications, as elaborated in the paper. Hence, we believe our techniques might be useful in other settings in future.