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
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
The main aim of cryptography is to provide the frameworks and solutions for information security. The fundamental weapons to protect information are interactions and private randomness. Since the breakthrough result, zero-knowledge proof system, by Goldwasser, Micali, and Rackoff in mid 80s, the cryptography community has endeavored to propose the new notions of information security and the relative solutions which more closely reflect the modern computing environment. Concurrent security first introduced by Dwork, Naor, and Sahai was suggested to capture the information security in the modern internet environment. That is, the adversary may interact with a honest parties in many concurrent executions of a protocol where the messages are scheduled in any adversarial way.Resettable security was first introduced by Canetti, Goldreich, Goldwasser, and Micali, which models the security issues in which parties have a limited source of private randomness. In other words, an adversary might interact with honest parties in many executions of a protocol while the honest parties are only allowed to use the polynomially bounded number of (hard-wired) randomness.An important question is: "How much efficient protocol can we construct to achieve the above security in terms of round complexity?" Unfortunately, it has been showed that the best possible round complexity for such protocols is poly-logarithmic in the security parameter based on black-box simulation without help of external set-up assumptions. Thus, the question is now to minimize the round complexity of protocols with a minimal set-up assumption.In this thesis, we positively answer the above question with help of set-up assumptions. Specifically, we consider two set-up assumptions, the Bare Public Key (BPK) model and the Cross-Domain (CD) model. The BPK model was first introduced by Canetti, Goldreich, Goldwasser, and Micali. In the BPK model, each party is required to register their public keys before the start of interacting with each other. The CD model is a newly proposed model in this work. In the CD model, we have domains which models key certification authorities in the real world and each party belongs to one of the domains.In the BPK model, we show a constructions of constant-round simultaneously resettable zero-knowledge argument of knowledge with a standard cryptographic assumptions. As a main building block for this result, we show a construction of constant-round simultaneously resettable witness-indistinguishable argument of knowledge.In the CD model, we show a construction of constant-round concurrently secure multi-party computation protocol with the fixed number of domains. On the other hand, we prove that if the number of domains is not fixed, such a constant-round protocol does not exist.
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge.In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape.All known examples of zero-knowledge proofs and arguments are trivially breakable in this setting.Moreover, by definition, all zero-knowledge proofs of knowledge are breakable in this setting.Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct: • Resettable Zero-Knowledge proof-systems for NP with non-constant number of rounds.* Five-round Resettable Witness-Indistinguishable proofsystems for NP. e Four-round Resettabie Zero-Knowledge arguments for NP in the public key model: where verifiers have fixed, public keys associated with them.In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications.Firstly, rZK protocols are closed under parallel and concurrent execution and thus are guaranteed to be secure when implemented in fully asynchronous networks, even if an adversary schedules the arrival of every message sent so as to foil security.Secondly, rZK protocols enlarge the range of physical ways in which provers of ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state *A subset of this work is included in patent application [21].
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape. Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct (non-constant round) Resettable Zero-Knowledge proof-systems for NP constant-round Resettable Witness-Indistinguishable proof-systems for NP constant-round Resettable Zero-Knowledge arguments for NP in the public key model: where veriers have fixed, public keys associated with them. In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications. Firstly, we show that rZK protocols are closed under parallel and
Secure computation protocols inherently involve multiple rounds of interaction among the parties where, typically a party has to keep a state about what has happened in the protocol so far and then wait for the other party to respond. We study if this is inherent. In particular, we study the possibility of designing cryptographic protocols where the parties can be completely stateless and compute the outgoing message by applying a single fixed function to the incoming message (independent of any state). The problem of designing stateless secure computation protocols can be reduced to the problem of designing protocols satisfying the notion of resettable computation introduced by Canetti, Goldreich, Goldwasser and Micali (FOCS'01) and widely studied thereafter. The current start of art in resettable computation allows for construction of protocols which provide security only when a single predetermined party is resettable [15]. An exception is for the case of the zero-knowledge functionality for which a protocol in which both parties are resettable was recently obtained by Deng, Goyal and Sahai (FOCS'09). The fundamental question left open in this sequence of works is, whether fully-resettable computation is possible, when: 1) An adversary can corrupt any number of parties, and 2) The adversary can reset any party to its original state during the execution of the protocol and can restart the protocol. In this paper, we resolve the above problem by constructing secure protocols realizing any efficiently computable multi-party functionality in the plain model under standard cryptographic assumptions. First, we construct a Fully-Resettable Simulation Sound Zero-Knowledge (ss-rs-rZK) protocol. Next, based on these ss-rs-rZK protocols, we show how to compile any semi-honest secure protocol into a protocol secure against fully resetting adversaries. Next, we study a seemingly unrelated open question: "Does there exist a functionality which, in the concurrent setting, is impossible to securely realize using BB simulation but can be realized using NBB simulation?". We resolve the above question in the affirmative by giving an example of such a (reactive) functionality. Somewhat surprisingly, this is done by making a connection to the existence of a fully resettable simulation sound zero-knowledge protocol.
Resettable-security, introduced by Canetti, Goldreich, Goldwasser and Micali (STOC'00), considers the security of cryptographic two-party protocols (in particular zero-knowledge arguments) in a setting where the attacker may “reset” or “rewind” one of the players. The strongest notion of resettable security, simultaneous resettability, introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS'01), requires resettable security to hold for both parties: in the context of zero-knowledge, both the soundness and the zero-knowledge conditions remain robust to resetting attacks. To date, all known constructions of protocols satisfying simultaneous resettable security rely on the existence of ZAPs; constructions of ZAPs are only known based on the existence of trapdoor permutations or number-theoretic assumptions. In this paper, we provide a new method for constructing protocols satisfying simultaneous resettable security while relying only on the minimal assumption of one-way functions. Our key results establish, assuming only one-way functions: Every language in NP has an ω(1)-round simultaneously resettable witness indistinguishable argument system; Every language in NP has a (polynomial-round) simultaneously resettable zero-knowledge argument system. The key conceptual insight in our technique is relying on black-box impossibility results for concurrent zero-knowledge to achieve resettable-security.
Abstract. In resetting attacks against a proof system, a prover or a verifier is reset and enforced to use the same random tape on various inputs as many times as an adversary may want. Recent deployment of cloud computing gives these attacks a new importance. This paper shows that argument systems for any NP language that are both resettably-sound and resettable zero-knowledge are possible by a constant-round protocol in the BPK model. For that sake, we define and construct a resettablyextractable conditional commitment scheme.