Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. [23] in Eurocrypt’08 (which generalizes the work on precise zero-knowledge by Micali and Pass [19] in STOC’06). This notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time. [23] constructed some (private-coin) concurrent zero-knowledge argument systems for NP which achieve precision in different levels and all these protocols use at least ω(log n) rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for NP only using almost constant rounds, i.e., ω(1) rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn’t need any setup assumption. We stress that this result cannot be obtained by [23] even in bounded-concurrent setting.
Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. [23] in Eurocrypt’08 (which generalizes the work on precise zero-knowledge by Micali and Pass [19] in STOC’06). This notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time. [23] constructed some (private-coin) concurrent zero-knowledge argument systems for NP which achieve precision in different levels and all these protocols use at least ω(log n) rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for NP only using almost constant rounds, i.e., ω(1) rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn’t need any setup assumption. We stress that this result cannot be obtained by [23] even in bounded-concurrent setting.
Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. in Eurocrypt'08, which captures the idea that the view of any verifier in concurrent interaction can be reconstructed in almost the same time. They also constructed some (private-coin) concurrent zero-knowledge argument systems for NP which achieve precision in different levels and all these protocols use at least ω (log n) rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our main result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for NP only using almost constant rounds, i.e., ω (1) rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn't need any setup assumption.
In this paper we put forward the Bounded Player Model for secure computation. In this new model, the number of players that will ever be involved in secure computations is bounded, but the number of computations has no a priori bound. Indeed, while the number of devices and people on this planet can be realistically estimated and bounded, the number of computations these devices will run can not be realistically bounded. We stress that in the Bounded Player model, in addition to no a priori bound on the number of sessions, there is no synchronization barrier, no trusted party, and simulation must be performed in polynomial time. In this setting, we achieve concurrent Zero Knowledge (cZK) with sub-logarithmic round complexity. Our security proof is (necessarily) non-black-box, our simulator is “straight-line” and works as long as the number of rounds is ω(1). We further show that unlike previously studied relaxations of the standard model (e.g., bounded number of sessions, timing assumptions, super-polynomial simulation), concurrent-secure computation is still impossible to achieve in the Bounded Player model. This gives evidence that our model is “closer” to the standard model than previously studied models, and study of this model might shed light on constructing round efficient concurrent zero-knowledge in the standard model as well.
Concurrent non-malleable zero-knowledge ( CNMZK ) considers the concurrent execution of zero-knowledge protocols in a setting even when adversaries can simultaneously corrupt multiple provers and verifiers. As far as we know, the round complexity of all the constructions of CNMZK arguments for NP is at least ω (log n ). In this paper, we provide the first construction of a constant-round concurrent non-malleable zero-knowledge argument for every language in NP . Our protocol relies on the existence of families of collision-resistant hash functions , one-way permutations and indistinguishability obfuscators . As an additional contribution, we study the composition of two central notions in zero knowledge, the simultaneously resettable zero-knowledge and non-malleable zero-knowledge , which seemingly have stronger proved security guarantees. We give the first construction of a constant-round simultaneously-resettable non-malleable zero-knowledge . To the best of our knowledge, this is the first study to combine the two security concepts described above together in the zero-knowledge protocols.
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
In this work, we consider the long-standing open question of constructing constant-round concurrent zero-knowledge protocols in the plain model. Resolving this question is known to require non-black-box techniques. We consider non-black-box techniques for zero-knowledge based on knowledge assumptions, a line of thinking initiated by the work of Hada and Tanaka (CRYPTO 1998). Prior to our work, it was not known whether knowledge assumptions could be used for achieving security in the concurrent setting, due to a number of significant limitations that we discuss here. Nevertheless, we obtain the following results: 1. We obtain the first constant round concurrent zero-knowledge argument for \textbf{NP} in the plain model based on a new variant of knowledge of exponent assumption. Furthermore, our construction avoids the inefficiency inherent in previous non-black-box techniques such that those of Barak (FOCS 2001); we obtain our result through an efficient protocol compiler. 2. Unlike Hada and Tanaka, we do not require a knowledge assumption to argue the soundness of our protocol. Instead, we use a discrete log like assumption, which we call Diffie-Hellman Logarithm Assumption, to prove the soundness of our protocol. 3. We give evidence that our new variant of knowledge of exponent assumption is in fact plausible. In particular, we show that our assumption holds in the generic group model. 4. Knowledge assumptions are especially delicate assumptions whose plausibility may be hard to gauge. We give a novel framework to express knowledge assumptions in a more flexible way, which may allow for formulation of plausible assumptions and exploration of their impact and application in cryptography.
A fundamental question in cryptography deals with understanding the role that randomness plays in cryptographic protocols and to what extent it is necessary. One particular line of works was initiated by Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) who introduced the notion of resettable zero-knowledge, where the protocol must be zeroknowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the setting where the verifier uses a fixed random tape in multiple interactions. Subsequent to these works, a number of papers studied the notion of resettable protocols in the setting where only one of the participating parties uses a fixed random tape multiple times. The notion of resettable security has been studied in two main models: the plain model and the bare public key model (also introduced in the above paper by Canetti et. al.). In a recent work, Deng, Goyal and Sahai (FOCS 2009) gave the first construction of a simultaneous resettable zero-knowledge protocol where both participants of the protocol can reuse a fixed random tape in any (polynomial) number of executions. Their construction however required O(nɛ) rounds of interaction between the prover and the verifier. Both in the plain as well as the BPK model, this construction remain the only known simultaneous resettable zero-knowledge protocols. In this work, we study the question of round complexity of simultaneous resettable zeroknowledge in the BPK model. We present a constant round protocol in such a setting based on standard cryptographic assumptions. Our techniques are significantly different from the ones used by Deng, Goyal and Sahai. 1