This paper focuses on the robustness of concurrent non-malleable zero-knowledge.Existing concurrent non-malleable zero-knowledge protocols either apply non-black-box techniques,or employ black-box but incorporate a zero-knowledge sub-protocol.Hence when concurrently composed with other protocols,security of these protocols is not preserved or hard to argue.Following the well-known Feige-Shamir style,this paper presents a new construction for concurrent non-malleable zero-knowledge argument system,which is easily composed.This protocol takes the robust non-malleable commitment scheme introduced by Lin and Pass in STOC 2009 and specially designed witness indistinguishable proofs as basic components to achieve non-malleability and robustness.Moreover,this paper applies the oblivious simulation strategy to simulate the view of the adversary,and the proof technique introduced by Lin et al.in Crypto 2010 to analyze the indistinguishability of simulation.Since witness indistinguishability is closed under concurrent composition,the commitment sub-protocol is robust and the is oblivious,when concurrently composed with other protocols,this protocol is easier to work with and analyze.Based on the one-way function assumption,the round complexity of this protocol is super-logarithmic.
This paper focuses on the robustness of concurrent non-malleable zero-knowledge.Existing concurrent non-malleable zero-knowledge protocols either apply non-black-box techniques,or employ black-box but incorporate a zero-knowledge sub-protocol.Hence when concurrently composed with other protocols,security of these protocols is not preserved or hard to argue.Following the well-known Feige-Shamir style,this paper presents a new construction for concurrent non-malleable zero-knowledge argument system,which is easily composed.This protocol takes the robust non-malleable commitment scheme introduced by Lin and Pass in STOC 2009 and specially designed witness indistinguishable proofs as basic components to achieve non-malleability and robustness.Moreover,this paper applies the oblivious simulation strategy to simulate the view of the adversary,and the proof technique introduced by Lin et al.in Crypto 2010 to analyze the indistinguishability of simulation.Since witness indistinguishability is closed under concurrent composition,the commitment sub-protocol is robust and the is oblivious,when concurrently composed with other protocols,this protocol is easier to work with and analyze.Based on the one-way function assumption,the round complexity of this protocol is super-logarithmic.
We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol Pi such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of Pi, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities {including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC2004). We obtain an Otilde(n) -round protocol under the assumption that one-to-one one-way functions exist. This can be improved to Otilde(k log n) rounds under the assumption that there exist k-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol
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.
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.
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
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.