Zero-Knowledge Proofs

Zero-knowledge proofs are probabilistic and interactive proofs that efficiently demonstrate membership in the language without conveying any additional knowledge. Zero-knowledge proofs were introduced by Goldwasser, Micali and Rackoff in The Knowledge Complexity of Interactive Proof Systems (SIAM J. of Comuting, January 1989). The wide applicability of zero-knowledge was demonstrated in Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs, coauthored by Goldreich, Micali and Wigderson [JACM, July 1991]. In particular, assuming the existence of one-way functions, they showed that every language in NP has a zero-knowledge proof system. This work is not available on-line, yet most of the material is covered in Foundations of Cryptography - Fragments of a Book [by Oded Goldreich]. (See also an extract of the relevant part.)

The general result cited above leaves open the question of designing practical zero-knowledge proof systems for specific tasks. One of our current aims is to provide techniques and tools which may be useful towards such a task. Our work in this direction includes

Honest-Verifier Statistical Zero-Knowledge equals general Statistical Zero-Knowledge by Oded Goldreich, Amit Sahai and Salil Vadhan shows how to transform any interactive proof system which is statistical zero-knowledge with respect to the honest-verifier, into a proof system which is statistical zero-knowledge with respect to any verifier. This is done by limiting the behavior of potentially cheating verifiers, without using computational assumptions or even referring to the complexity of such verifier strategies. (Previous transformations have either relied on computational assumptions or were applicable only to constant-round public-coin proof systems.)

The transformation also applies to public-coin (aka Arthur-Merlin) computational zero-knowledge proofs: that is, it transforms any Arthur-Merlin proof system which is computational zero-knowledge with respect to the honest-verifier, into an Arthur-Merlin proof system which is computational zero-knowledge with respect to any probabilistic polynomial-time verifier.

A Complete Promise Problem for Statistical Zero-Knowledge, by Amit Sahai and Salil Vadhan, presents a complete promise problem for SZK, the class of languages possessing statistical zero-knowledge proofs (against an honest verifier). The problem is to decide whether two efficiently samplable distributions are either statistically close or far apart. This characterizes SZK with no reference to interaction or zero-knowledge . From this theorem and its proof, we are able to establish several other results about SZK, knowledge complexity, and efficiently samplable distributions.

Concurrent Zero-Knowledge, by Cynthia Dwork, Moni Naor, and Amit Sahai. Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto; for example, in the case of zero-knowledge interactive proofs or arguments, the interactions remain proofs but may fail to remain zero-knowledge. This paper addresses the problem of achieving concurrent zero-knowledge.

We introduce timing in order to obtain zero-knowledge in concurrent executions. We assume that the adversary is constrained in its control over processors' clocks by what we call an (alpha,beta)-constraint for some alpha, beta: for any two processors P1 and P2, if P1 measures alpha elapsed time on its local clock and P2 measures beta elapsed time on its local clock, and P2 starts after P1 does, then P2 will finish after P1 does. We obtain four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP. We also address the more specific problem of Deniable Authentication, for which we propose efficient solutions.

Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints, by Cynthia Dwork and Amit Sahai. An interactive proof system (or argument) (P,V) is concurrent zero-knowledge if whenever the prover engages in polynomially many concurrent executions of (P,V), with (possibly distinct) colluding polynomial time bounded verifiers V1, ..., V{poly(n)}, the entire undertaking is zero-knowledge. Dwork, Naor, and Sahai recently showed the existence of a large class of concurrent zero-knowledge arguments, including arguments for all of NP, under a reasonable assumption on the behavior of clocks of nonfaulty processors.

In this paper, we continue the study of concurrent zero-knowledge arguments. After observing that, without recourse to timing, the existence of a Trusted Center considerably simplifies the design and proof of many concurrent zero-knowledge arguments (again including arguments for all of NP), we design a preprocessing protocol, making use of timing, to simulate the Trusted Center for the purposes of achieving concurrent zero-knowledge. Once a particular prover and verifier have executed the preprocessing protocol, any polynomial number of subsequent executions of a rich class of protocols will be concurrent zero-knowledge. Thus, we push all use of timing into a preprocessing phase, executed once for each (P,V), whenever in real time they choose to do it, and serving all their (polynomially many) future interaction needs.

Resettable Zero-Knowledge, by Ran Canetti, Oded Goldreich, Shafi Goldwasser and Silvio Micali. 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 adeversary can interact with the prover many times, each time resetting the prover to its initial state and forcing him to use the same random tape. 
Under general complexity asumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct (1) rZK proof-systems for NP: (2) constant-round resettable witness-indistinguishable proof-systems for NP; and (3) constant-round rZK 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, we show that 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. Secondly, rZK protocols enlarge the range of physical ways in which provers of a ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state betweeen invocations. (For instance, because ordinary smart cards with secure hardware are resattable, they could not be used to implement securely the provers of classical ZK protocols, but can now be used to implement securely the provers of rZK protocols.)

Min-Round Resettable Zero-Knowledge in the Public-Key Model, by Silvio Micali and Leonid Reyzin, achieves ultimate round efficiency in a slightly strengthened public-key model model. Specifically, it shows a 3-round black-box RZK protocol for NP in a public-key model where the number of times a given public key is used is bounded a priori. It also proves that three is indeed the minimum possible number of rounds. The result stresses the surprising power of public keys. In fact, Goldreich and Krawcyk [GK96] prove that, without public keys, 3-round black-box protocols for non-trivial languages do not exist, even for ordinary zero knowledge.

Soundness in the Public-Key Model, by Silvio Micali and Leonid Reyzin, explores the issues of soundness in the public-key model for interactive proofs. As our previous work and the work of Canetti, Goldreich, Goldwasser and Micali had demonstrated, the public-key model for interactive proofs is quite effective in improving protocol efficiency. In this work, we discovered that its soundness notion is more subtle and complex than in the classical model, and that it should be better understood to avoid designing erroneous or inefficient protocols. We identified and separated four meaningful notions of soundness. We also demonstrated that weaker notions of soundness can be achieved more efficiently than stronger ones, and may actually suffice in many practical settings.

General results on zero-knowledge leave open the question of designing practical zero-knowledge proof systems for specific tasks. An important practical scenario is proving that your public key is "good" without revealing the secret key. For example, when registering your RSA key N = PQ with a certification authority you might be required for security purposes to prove that N is indeed the product of exactly two primes. Some RSA-based application also require that the RSA modulus satisfies some special properties, usually that P and Q are "safe", i.e., (P-1)/2 and (Q-1)/2 are also prime. In An Efficient Non-interactive Statistical Zero-knowledge Proof System for Quasi-Safe Prime Products, Rosario Gennaro, Daniele Micciancio and Tal Rabin present an efficient statistical zero-knowledge proof system to prove that an RSA modulus N=PQ is the product of two "quasi-safe" primes, i.e., primes such that (P-1)/2 and (Q-1)/2 are prime powers, a relaxation of safe-primes still usefull in many practical scenarios where safe-prime products are assumed (e.g., RSA-based undeniable signatures).