Abstract. Consider a joint distribution (X,A) on a set X ×{0, 1}ℓ. We show that for any family F of distinguishers f: X × {0, 1}ℓ → {0, 1}, there exists a simulator h: X → {0, 1}ℓ such that 1. no function in F can distinguish (X,A) from (X,h(X)) with advantage ǫ, 2. h is only O(23ℓǫ−2) times less efficient than the functions in F. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ǫ> 0 is negligible and F consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt’09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem. 1
The notion of zero-knowledge [GMR85] is formalized by requiring that for every malicious efficient verifier V ∗ , there exists an efficient simulator S that can reconstruct the view of V ∗ in a true interaction with the prover, in a way that is indistinguishable to every polynomialtime distinguisher. Weak zero-knowledge weakens this notions by switching the order of the quantifiers and only requires that for every distinguisher D, there exists a (potentially different) simulator SD. In this paper we consider various notions of zero-knowledge, and investigate whether their weak variants are equivalent to their strong variants. Although we show (under complexity assumption) that for the standard notion of zero-knowledge, its weak and strong counterparts are not equivalent, for meaningful variants of the standard notion, the weak and strong counterparts are indeed equivalent. Towards showing these equivalences, we introduce new non-black-box simulation techniques permitting us, for instance, to demonstrate that the classical 2-round graph non-isomorphism protocol of Goldreich-Micali-Wigderson [GMW91] satisfies a “distributional” variant of zero-knowledge. Our equivalence theorem has other applications beyond the notion of zero-knowledge. For instance, it directly implies the dense model theorem of Reingold et al (STOC ’08), and the leakage lemma of Gentry-Wichs (STOC ’11), and provides a modular and arguably simpler proof of these results (while at the same time recasting these result in the language of zeroknowledge). 0 1
We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol is sound against uniform polynomial-time attackers, and relies on the existence of families of collision-resistant hash functions, and a new (but in our eyes, natural) falsifiable intractability assumption: Roughly speaking, that Micali’s non-interactive CS-proofs are sound for languages in P.
The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS 2003, Goldwasser and Kalai showed that this transformation is provably insecure in the standard model by presenting a counterexample of a 3-round protocol, the Fiat-Shamir transformation of which is (although provably secure in the random oracle model) insecure in the standard model, thus showing that the random oracle is uninstantiable. In particular, for every hash function that is used to replace the random oracle, the resulting signature scheme is existentially forgeable. This result was shown by relying on the non-black-box techniques of Barak (FOCS 2001). An alternative to the Fiat-Shamir paradigm was proposed by Fischlin in Crypto 2005. Fischlin’s transformation can be applied to any so called 3-round “Fiat-Shamir proof of knowledge’ ’ and can be used to derive non-interactive zero-knowledge proofs of knowledge as well as signature schemes. An attractive property of this transformation is that it provides online extractability (i.e., the extractor works without having to rewind the prover). Fischlin remarks that in comparison to the Fiat-Shamir transformation, his construction tries to
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
Depending on the application, malleability in cryptography can be viewed as either a flaw or — especially if sufficiently understood and restricted — a feature. In this vein, Chase, Kohlweiss, Lysyanskaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs. As an application, they construct the first compact verifiable shuffle, in which one such controlled-malleable proof suffices to prove the correctness of an entire multi-step shuffle. Despite these initial steps, a number of natural open problems remain: (1) their construction of controlled-malleable proofs relies on the inherent malleability of Groth-Sahai proofs and is thus not based on generic primitives; (2) the classes of allowable transformations they can support are somewhat restrictive; and (3) their construction of a compactly verifiable shuffle has proof size O(N 2 + L) (where N is the number of votes and L is the number of mix authorities), whereas in theory such a proof could be of size O(N + L). In this paper, we address these open problems by providing a generic construction of controlledmalleable proofs using succinct non-interactive arguments of knowledge, or SNARGs for short. Our construction has the advantage that we can support a very general class of transformations (as we no longer rely on the transformations that Groth-Sahai proofs can support), and that we can use it to obtain a proof of size O(N + L) for the compactly verifiable shuffle.
A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in NEXP. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, revisited the possibility of efficient ZK-PCPs for all of NP where the PCP is encoded as a polynomial-size circuit that given a query i returns the ith symbol of the PCP. Ishai et al showed that there is no efficient ZK-PCP for NP with a non-adaptive verifier, that prepares all of its PCP queries before seeing any answers, unless NP⊆coAM and the polynomial-time hierarchy collapses. The question of whether adaptive verification can lead to efficient ZK-PCPs for NP remained open.
In this work, we resolve this question and show that any language or promise problem with efficient ZK-PCPs must be in SZK (the class of promise problems with a statistical zero-knowledge single prover proof system). Therefore, no NP-complete problem can have an efficient ZK-PCP unless NP⊆SZK (which also implies NP⊆coAM and the polynomial-time hierarchy collapses). We prove our result by reducing any promise problem with an efficient ZK-PCP to two instances of the Conditional Entropy Approximation problem defined and studied by Vadhan (FOCS'04) which is known to be complete for the class SZK.
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
Malleability for cryptography is not necessarily an opportunity for attack, but in many cases a potentially useful feature that can be exploited. In this work, we examine notions of malleability for non-interactive zero-knowledge (NIZK) proofs. We start by defining a malleable proof system, and then consider ways to meaningfully control the malleability of the proof system, as in many settings we would like to guarantee that only certain types of transformations can be performed. We also define notions for the cases in which we do not necessarily want a user to know that a proof has been obtained by applying a particular transformation; these are analogous to function/circuit privacy for encryption. As our motivating application, we consider a shorter proof for verifiable shuffles. Our controlled-malleable proofs allow us for the first time to use one compact proof to prove the correctness of an entire multi-step shuffle. Each authority takes as input a set of encrypted votes and a controlled-malleable NIZK proof that these are a shuffle of the original encrypted votes submitted by the voters; it then permutes and re-randomizes these votes and updates the proof by exploiting its controlled malleability. As another application, we generically use controlled-malleable proofs to realize a strong notion of encryption security. Finally, we examine malleability in existing proof systems and observe that Groth-Sahai proofs are malleable. We then go beyond this observation by characterizing all the ways in which they are malleable, and use them to efficiently instantiate our generic constructions from above; this means we can instantiate our proofs and all their applications using only the Decision Linear (DLIN) assumption. Work done as an intern at Microsoft Research Redmond
In this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all N P. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zeroknowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO 1989). Although it is widely believed that there exist constant-round zero-knowledge proofs of knowledge for all N P, to the best of our knowledge, no proof of this fact has been published. 1
In this thesis, we provide contributions to signature schemes and identi cation schemes in four di erent ways.\nFirst, we make contributions to universal designated veri er signatures. We propose the notion of a one-time universal designated veri er signature such that the number of veri ers verifying the signature is controlled by the signer. We also propose the notion of a universal designated veri er signature with threshold-signers such that the privacy and anonymity of the signer can be achieved.\nSecond, we propose a new notion called "policy-controlled signatures". In this notion, a policy-controlled signature can be veri ed by a veri er that satis es a policy assigned by a signer. We provide two extensions to this notion, which are "universal policy-controlled signatures" and "multi-level controlled signatures". Universal policy-controlled signatures allow a party called "a policy signer" to apply a policy on a signature on a particular message such that only a veri er that satis es this policy can verify this policy-controlled signature. In practice, some policies can be simply represented by a level of the security, for example, "POLICY= more than the fth level of security". From the above idea, a de nition of multi-level controlled signatures is introduced. It allows a signer to eliminate the unnecessary chain of attributes in the policy and simply assign the level of security as a policy instead. Hence, the size of the policy remains constant.\nNext, a new notion called "fair multi-signatures" is proposed. A multi-signature allows a group of parties to engage in an interactive protocol in order to generate a joint signature on an agreement. If all the signers follow the protocol honestly, then a multi-signature is generated and distributed fairly. However, if a dishonest signer refuses to complete his part in the protocol, but he has already obtained the other parties' contributions, then the honest signers cannot obtain a multi-signature and yet the dishonest signer can generate a multi-signature. Our notion of fair multisignatures ensures that if the protocol is completed, then every signer involved in the signing protocol can output a multi-signature. Meanwhile, if the protocol is not completed, then none of the signers involved in the signing protocol can output a multi-signature.\nFinally, in modern communications, the public becomes aware of privacy issues. Some identi cation systems provide privacy for users, especially those that are based on zero knowledge proof. However, a malicious user may take advantage of privacy to deny his malicious acts. Hence, we propose a new notion called "escrowed deniable identi cation schemes". In this notion, a trusted party is introduced to act as a transaction opener such that it can generate evidence of the conversation from the deniable transcript generated during the interaction between a prover and a veri er. In an identi cation scheme, the major concern about security is impersonation. The strongest type of attack against identi cation schemes is the reset attack. In this thesis, we provide an identity-based identi cation scheme secure against reset attack. We also provide proof of our scheme which is secure against reset attack in the standard model.
Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, Louis Salvail
Attacks on classical cryptographic protocols are usually modeled by allowing an adversary to ask queries from an oracle. Security is then defined by requiring that as long as the queries satisfy some constraint, there is some problem the adversary cannot solve, such as compute a certain piece of information. In this paper, we introduce a fundamentally new model of quantum attacks on classical cryptographic protocols, where the adversary is allowed to ask several classical queries in quantum superposition. This is a strictly stronger attack than the standard one, and we consider the security of several primitives in this model. We show that a secret-sharing scheme that is secure with threshold $t$ in the standard model is secure against superposition attacks if and only if the threshold is lowered to $t/2$. We use this result to give zero-knowledge proofs for all of NP in the common reference string model. While our protocol is classical, it is sound against a cheating unbounded quantum prover and computational zero-knowledge even if the verifier is allowed a superposition attack. Finally, we consider multiparty computation and show that for the most general type of attack, simulation based security is not possible. However, putting a natural constraint on the adversary, we show a non-trivial example of a protocol that can indeed be simulated.
Zero-knowledge proofs protocols are effective interactive methods to prove a node's identity without disclosing any additional information other than the veracity of the proof. They are implementable in several ways. In this thesis, I investigate the graph isomorphism based zero-knowledge proofs protocol. My experiments and analyses suggest that graph isomorphism can easily be solved for many types of graphs and hence is not an ideal solution for implementing ZKP.
We propose a distributed key generation protocol for pairing-based cryptosystems which is adaptively secure in the erasure-free and secure channel model, and at the same time completely avoids the use of interactive zero-knowledge proofs. Utilizing it as the threshold key generation protocol, we present a secure (t,n) threshold signature scheme based on the Waters' signature scheme. We prove that our scheme is unforgeable and robust against any adaptive adversary who can choose players for corruption at any time during the run of the protocols and make adaptive chosen-message attacks. And the security proof of ours is in the standard model (without random oracles). In addition our scheme achieves optimal resilience, that is, the adversary can corrupt any t<n/2 players.
Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya
Abstract. Efficient non-interactive zero-knowledge proofs are a powerful tool for solving many cryptographic problems. We apply the recent Groth-Sahai (GS) proof system for pairing product equations (Eurocrypt 2008) to two related cryptographic problems: compact e-cash (Eurocrypt 2005) and simulatable verifiable random functions (CRYPTO 2007). We present the first efficient compact e-cash scheme that does not rely on a random oracle. To this end we construct efficient GS proofs for signature possession, pseudo randomness and set membership. The GS proofs for pseudorandom functions give rise to a much cleaner and substantially faster construction of simulatable verifiable random functions (sVRF) under a weaker number theoretic assumption. We obtain the first efficient fully simulatable sVRF with a polynomial sized output domain (in the security parameter). 1
Rafael Pass, Wei-Lung Dustin Tseng, Douglas Wikström
We show that only languages in BPP have public-coin black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any setup) and in the bare public key model (where the prover and the verifier have registered public keys). We complement this result by constructing a public-coin black-box zero-knowledge proof based on one-way functions that remains secure under any a priori bounded number of concurrent executions. A key step (of independent interest) in the analysis of our lower bound shows that any public-coin protocol, when repeated sufficiently in parallel, satisfies a notion of “resettable soundness” if the verifier picks its random coins using a pseudorandom function.