Zero-knowledge twenty years after its invention

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

Zero-Knowledge twenty years after its invention

Department of Computer Science and Applied Mathematics Weizmann Institute of Science, Rehovot, Israel. Email: oded@wisdom.weizmann.ac.il First draft posted in July 2002 Current version: December 3, 2002Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, contributed to the development of other areas of cryptography and complexity theory. We survey the main de nitions and results regarding zero-knowledge proofs. Speci cally, we present the basic de nitional approach and its variants, results regarding the power of zeroknowledge proofs as well as recent results regarding questions such as the composeability of zero-knowledge proofs and the use of the adversary's program within the proof of security (i.e., non-black-box simulation).

Oded Goldreich

Abstract

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

Contents

1 Introduction

1.1 The Basics::::::::::::::::::::::::::::::::::::::::::::::::::: 1.2 Advanced Topics:::::::::::::::::::::::::::::::::::::::::::::::: 1.3 Comments::::::::::::::::::::::::::::::::::::::::::::::::::::

11 2 2

I The Basics2 Preliminaries2.1 Interactive proofs and argument systems::::::::::::::::::::::::::::::::::: 2.2 Computational Di culty and One-Way Functions:::::::::::::::::::::::::::::: 2.3 Computational Indistinguishability:::::::::::::::::::::::::::::::::::::: 3.1 The Simulation Paradigm::::::::::::::::::: 3.2 The Basic De nition:::::::::::::::::::::: 3.3 Variants::::::::::::::::::::::::::::: 3.3.1 Universal and black-box simulation:::::::::: 3.3.2 Honest veri er versus general cheating veri er:::: 3.3.3 Statistical versus Computational Zero-Knowledge:: 3.3.4 Strict versus expected probabilistic polynomial-time

34 6 6

3 7

3 De nitional Issues

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

: 7: 8: 9: 9: 10: 10: 11

4 Zero-Knowledge Proofs for every NP-set

4.1 Constructing Zero-Knowledge Proofs for NP-sets:::::::::::::::::::::::::::::: 12 4.2 Using Zero-Knowledge Proofs for NP-sets:::::::::::::::::::::::::::::::::: 14

11

5 Composing zero-knowledge protocols

II Advanced Topics

1414

5.1 Sequential Composition:

::::::::::::::::::::::::::::::::::::::::::: 15 5.2 Parallel Composition:::::::::::::::::::::::::::::::::::::::::::::: 16 5.3 Concurrent Composition (with and without timing):::::::::::::::::::::::::::: 17

6 Using the adversary's program in the proof of security 7 Proofs of Knowledge

Digest: Witness Indistinguishability and the FLS-Technique::::::::::::::::::::::::::: 21 7.1 How to de ne proofs of knowledge:::::::::::::::::::::::::::::::::::::: 22 7.2 How to construct proofs of knowledge:::::::::::::::::::::::::::::::::::: 23

19 22 23 24

8 Non-Interactive Zero-Knowledge 9 Statistical Zero-Knowledge

9.1 Transformations:::::::::::::::::::::::::::::::::::::::::::::::: 25 9.2 Complete problems and structural properties:::::::::::::::::::::::::::::::: 25

10 Knowledge Complexity 11 Resettability of a party's random-tape (rZK and rsZK) 12 Zero-knowledge in other models 13 A source of inspiration for complexity theory References

26 27 27 28 29

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

1 IntroductionZero-Knowledge proofs, introduced by Goldwasser, Micali and Racko 66], are fascinating and extremely useful constructs. Their fascinating nature is due to their seemingly contradictory de nition; zero-knowledge proofs are both convincing and yet yield nothing beyond the validity of the assertion being proven. Their applicability in the domain of cryptography is vast; they are typically used to force malicious parties to behave according to a predetermined protocol. In addition to their direct applicability in Cryptography, zero-knowledge proofs serve as a good bench-mark for the study of various problems regarding cryptographic protocols (e.g., the\preservation of security under various forms of protocol composition" and the\use of of the adversary's program within the proof of security"). In this tutorial we present the basic de nitions and results regarding zero-knowledge protocols as well as some recent developments regarding this notion. The rest of the introduction provides a high-level summary of the tutorial.X? !? !

??

X is true!111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000

!

Figure 1: Zero-knowledge proofs{ an illustration.

Loosely speaking, zero-knowledge proofs are proofs that yield nothing beyond the validity of the assertion. That is, a veri er obtaining such a proof only gains conviction in the validity of the assertion. This is formulated by saying that anything that is feasibly computable from a zero-knowledge proof is also feasibly computable from the (valid) assertion itself (by a so-called simulator). Variants on the basic de nition include: Consideration of

auxiliary inputs. Mandating of universal and black-box simulations. Restricting attention to honest (or rather semi-honest) veri ers. The level of similarity required of the simulation. It is well-known that zero-knowledge proofs exist for any NP-set, provided that one-way functions exist. This result is a powerful tool in the design of cryptographic protocols, because it enables to force parties to behave according to a predetermined protocol (i.e., the protocol requires parties to provide zero-knowledge proofs of the correctness of their secret-based actions, without revealing these secrets). 1

1.1 The Basics

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

Organization of Part 1: We start with some preliminaries (Section 2), which are central to

the\mind-set" of the notion of zero-knowledge. In particular, we review the de nitions of interactive proofs and arguments as well as the de nitions of computational indistinguishability (which underlies the de nition of general zero-knowledge) and of one-way functions (which are used in constructions). We then turn to the de nitional treatment of zero-knowledge itself (Section 3). Finally, we discuss the constructibility and applicability of zero-knowledge proofs (Section 4). We start with two basic problems regarding zero-knowledge, which actually arise also with respect to the security of other cryptographic primitives. The rst question refers to the preservation of security (i.e., zero-knowledge in our case) under various types of composition operations. We survey the known results regarding sequential, parallel and concurrent execution of (arbitrary and/or speci c) zero-knowledge protocols. The main facts are: Zero-knowledge (with respect to auxiliary inputs) is closed under sequential composition. In general, zero-knowledge is not closed under parallel composition. Yet, some zero-knowledge proofs (for NP) preserve their security when many copies are executed in parallel. Furthermore, some of these protocol use a constant number of rounds. Some zero-knowledge proofs (for NP) preserve their security when many copies are executed concurrently, but such a result is not known for constant-round protocols. The second basic question regarding zero-knowledge refers to the usage of the adversary's program within the proof of security (i.e., demonstration of the zero-knowledge property). For 15 years, all known proofs of security used the adversary's program as a black-box (i.e., a universal simulator was presented using the adversary's program as an oracle). Furthermore, it was believed that there is no advantage in having access to the code of the adversary's program. Consequently it was conjectured that negative results regarding black-box simulation represent an inherent limitation of zero-knowledge. This believe has been refuted recently by the presentation of a zero-knowledge argument (for NP) that has important properties that are unachievable by black-box simulation. For example, this zero-knowledge argument uses a constant number of rounds

and preserves its security when an (a-priori xed polynomial) number of copies are executed concurrently.1

1.2 Advanced Topics

Organization of Part 2: The composeability of zero-knowledge proofs is discussed in Section 5

and the use of the adversary's program within the proof of security is discussed in Section 6. Other topics treated in the second part of this tutorial include proofs of knowledge (Section 7), NonInteractive Zero-Knowledge proofs (Section 8), Statistical Zero-Knowledge (Section 9), Knowledge Complexity (Section 10), and resettability of a party's random-tape (Section 11). The notion of zero-knowledge has had a vast impact on the development of cryptography. In particular, zero-knowledge proofs of various types were explicitly used (as a tool) in a variety of applications. We wish to highlight also the indirect impact of zero-knowledge on the de nitional

1.3 Comments

copies must be xed before the protocol is presented. Speci cally, the protocol uses messages that are longer than the allowed number of concurrent copies.

1 This result falls short of achieving a fully concurrent zero-knowledge argument, because the number of concurrent

2

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

approach underlying the foundations of cryptography (cf. Section 3.1). In addition, zero-knowledge has served as a source of inspiration for complexity theory (cf. Section 13).

A Brief Historical Account (regarding the main part of the tutorial): The concept of zero-

knowledge has been introduced by Goldwasser, Micali, and Racko 66]. Although their work, which also introduced interactive proof systems, has rst appeared in STOC95, early versions of it have existed as early as in 1982 (and were rejected three times from major conferences; i.e., FOCS83, STOC84, and FOCS84). The wide applicability of zero-knowledge proofs was rst demonstrated by Goldreich, Micali and Wigderson, who showed how to construct zero-knowledge proof systems for any NP-set, using any commitment scheme 57]. An important technique for the design of zero-knowledge was introduced by Feige, Lapidot and Shamir 38], based on the notion of witness indistinguishability (which was introduced by Feige and Shamir 39]). Important contributions to the study of the sequential, parallel and concurrent composition of zero-knowledge protocols were presented in 55, 59], 55, 51] and 34, 81, 28, 72, 7], respectively. The power of non-black-box simulators has been recently discovered by Barak 7]. is referred to 49, Chap. 4]. For a wider perspective on probabilistic proof systems, the reader is referred to 48, Chap. 2].

Suggestions for further reading: For further details regarding most of the material, the reader The current version: This is a minor revision of the rst draft (dated July 31, 2002).

Part I

The Basics

2 PreliminariesModern Cryptography, is concerned with the construction of e cient schemes for which it is infeasible to violate the security feature. The same concern underlies the main de nitions of zeroknowledge. Thus, for

starters, we need a notion of e cient computations as well as a notion of infeasible ones. The computations of the legitimate users of the scheme ought be e cient, whereas violating the security features (via an adversary) ought to be infeasible. E cient computations are commonly modeled by computations that are polynomial-time in the security parameter. The polynomial bounding the running-time of the legitimate user's strategy is xed and typically explicit (and small). Here (i.e., when referring to the complexity of the legitimate users) we are in the same situation as in any algorithmic setting. Things are di erent when referring to our assumptions regarding the computational resources of the adversary. A common approach is to postulate that the latter are polynomial-time too, where the polynomial is not a-priori speci ed. In other words, the adversary is restricted to the class of e cient computations and anything beyond this is considered to be infeasible. Although many de nitions explicitly refer to this convention, this convention is inessential to any of the results known in the area. In all cases, a more general statement can be made by referring to adversaries of running-time bounded by any super-polynomial function (or class of functions). Still, for sake of concreteness and clarity, we shall use the former convention in our treatment. 3

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

Actually, in order to simplify our exposition, we will often consider as infeasible any computation that cannot be conducted by a (possibly non-uniform) family of polynomial-size circuits. For simplicity we consider families of circuits fCn g, where for some polynomials p and q, each Cn has exactly p(n) input bits and has size at most q(n). Randomized computations play a central role in the de nition of zero-knowledge (as well as in cryptography at large). That is, we allow the legitimate users to employ randomized computations, and likewise we consider adversaries that employ randomized computations. This brings up the issue of success probability: typically, we require that legitimate users succeed (in ful lling their legitimate goals) with probability 1 (or negligibly close to this), whereas adversaries succeed (in violating the security features) with negligible probability. Thus, the notion of a negligible probability plays an important role in our exposition. One feature required of the de nition of negligible probability is to yield a robust notion of rareness: A rare event should occur rarely even if we repeat the experiment for a feasible number of times. Likewise, we consider two events to occur\as frequently" if the absolute di erence between their corresponding occurrence probabilities is negligible. For concreteness, we consider as negligible any function: N ! 0; 1] that vanishes faster than the reciprocal of any polynomial (i.e., for every positive polynomial p and all su ciently big n, it holds that (n)< 1=p(n)). Before de ning zero-knowledge proofs, we have to de ne proofs. The sta

ndard notion of static (i.e., non-interactive) proofs will not do, because static zero-knowledge proofs exist only for sets that are easy to decide (i.e, are in BPP ) 59] whereas we are interested in zero-knowledge proofs for arbitrary NP-sets. Instead, we use the notion of an interactive proof (introduced exactly for that reason by Goldwasser, Micali and Racko 66]). That is, here a proof is a (multi-round) randomized protocol for two parties, called veri er and prover, in which the prover wishes to convince the veri er of the validity of a given assertion. Such an interactive proof should allow the prover to convince the veri er of the validity of any true assertion, whereas no prover strategy may fool the veri er to accept false assertions. Both the above completeness and soundness conditions should hold with high probability (i.e., a negligible error probability is allowed). We comment that interactive proofs emerge naturally when associating the notion of e cient veri cation, which underlies the notion of a proof system, with probabilistic and interactive polynomial-time computations. This association is quite natural in light of the growing acceptability of randomized and distributed computations. Thus, a\proof" in this context is not a xed and static object, but rather a randomized and dynamic (i.e., interactive) process in which the veri er interacts with the prover. Intuitively, one may think of this interaction as consisting of\tricky" questions asked by the veri er, to which the prover has to reply\convincingly". The above discussion, as well as the following de nition, makes explicit reference to a prover, whereas a prover is only implicit in the traditional de nitions of proof systems (e.g., NP-proofs). Loosely speaking, an interactive proof is a game between a computationally bounded veri er and a computationally unbounded prover whose goal is to convince the veri er of the validity of some assertion. Speci cally, the veri er is probabilistic polynomial-time. It is required that if the assertion holds then the veri er always accepts (i.e., when interacting with an appropriate prover strategy). On the other hand, if the assertion is false then the veri er must reject with\noticeable" probability, no matter what strategy is being employed by the prover. Indeed, the error probability (in the soundness condition) can be reduced by (either sequential or parallel) repetitions.

2.1 Interactive proofs and argument systems

De nition 1 (Interactive Proof systems and the class IP 66]): An interactive proof system for a set4

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

S is a two-party game, between a veri er executing a probabilistic polynomial-time strategy (denoted V ) and a prover which executes a computationally unbounded strategy (denoted P ), satisfying Completeness: For every x 2 S the veri er V always accepts after interacting with the prover P on common input x. Soundness: For some polynomial p, it holds that for every x 62 S and every potential strategy P, the veri er

V rejects with probability at least 1=p(jxj), after interacting with P on common input x.The class of problems having interactive proof systems is denoted IP . Note that by repeating such a proof system for O(p(jxj)2 ) times, we may decrease the probability that V accepts a false statement (from 1?(1=p(jxj))) to 2?p(jxj) . Thus, when constructing interactive proofs we sometimes focus on obtaining a noticeable rejection probability for no-instances (i.e., obtaining soundness error bounded away from 1), whereas when using interactive proofs we typically assume that their soundness error is negligible.

Variants: Arthur-Merlin games (a.k.a public-coin proof systems), introduced by Babai 4], are a special case of interactive proofs in which the veri er must send the outcome of any coin it tosses (and thus need not send any other information). Yet, as shown in 67], this restricted case has essentially the same power as the general case (introduced by Goldwasser, Micali and Racko 66]). Thus, in the context of interactive proof systems, asking random questions is as powerful as asking\tricky" questions. (As we shall see, this does not necessarily hold in the context of zero-knowledge proofs.) Also, in some sources interactive proofs are de ned so that two-sided error probability is allowed (rather than requiring\perfect completeness" as done above); yet, this does not increase their power 44]. Arguments (or Computational Soundness): A fundamental variant on the notion of interactive proofs was introduced by Brassard, Chaum and Crepeau 21], who relaxed the soundness condition so that it only refers to feasible ways of trying to fool the veri er (rather than to all possible ways). Speci cally, the soundness condition was replaced by the following computational soundness condition that asserts that it is infeasible to fool the veri er into accepting false statements. For every polynomial p, every prover strategy that is implementable by a family of polynomial-size circuits fCn g, and every su ciently large x 2 f0; 1g n S, the probability that V accepts x when interacting with Cjxj is less than 1=p(jxj). We warn that although the computational-soundness error can always be reduced by sequential repetitions, it is not true that this error can always be reduced by parallel repetitions (cf. 14]). Protocols that satisfy the computational-soundness condition are called arguments.2 We mention that argument systems may be more e cient than interactive proofs (see 70, 53]).

Terminology. Whenever we wish to blur the distinction between proofs and arguments, we will

use the term protocols. We will consider such a protocol trivial if it establishes membership in a BPP-set (because membership in such a set can be determined by the veri er itself). On the other hand, we will sometimes talk about protocols for NP, when what we actually mean is protocols for each set in NP . (This terminology is quite common in the area.)32 3

A related notion not discussed here i

s that of CS-proofs, introduced by Micali 75]. See 9] for further discussion of the distinction.

5

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

2.2 Computational Di culty and One-Way Functions

Most positive results regarding zero-knowledge proofs are based on intractability assumptions. Furthermore, the very notion of a zero-knowledge proof is interesting only in case the assertion being proven to be valid is hard to verify in probabilistic polynomial-time. Thus, our discussion always assumes (at least implicitly) that IP is not contained in BPP, and often we explicitly assume more than that. In general, Modern Cryptography is concerned with the construction of schemes that are easy to operate (properly) but hard to foil. Thus, a complexity gap (i.e., between the complexity of proper usage and the complexity of defeating the prescribed functionality) lies in the heart of Modern Cryptography. However, gaps as required for Modern Cryptography are not known to exist; they are only widely believed to exist. Indeed, almost all of Modern Cryptography rises or falls with the question of whether one-way functions exist. One-way functions are functions that are easy to evaluate but hard (on the average) to invert (cf. 32]). That is, a function f: f0; 1g ! f0; 1g is called one-way if there is an e cient algorithm that on input x outputs f (x), whereas any feasible algorithm that tries to nd a preimage of f (x) under f may succeed only with negligible probability (where the probability is taken uniformly over the choices of x and the algorithm's coin tosses). Associating feasible computations with (possibly non-uniform) families of polynomial-size circuits, we obtain the following de nition.

De nition 2 (one-way functions): A function f: f0; 1g !f0; 1g is called one-way if the following two conditions hold:1. easy to evaluate: There exist a polynomial-time algorithm A such that A(x)= f (x) for every x 2 f0; 1g . 2. hard to invert: For every family of polynomial-size circuits fCn g, every polynomial p, and all su ciently large n, 1 Pr Cn (f (x)) 2 f?1(f (x))]< p(n) where the probability is taken uniformly over all the possible choices of x 2 f0; 1gn .

Some of the most popular candidates for one-way functions are based on the conjectured intractability of computational problems in number theory. One such conjecture is that it is infeasible to factor large integers. Consequently, the function that takes as input two (equal length) primes and outputs their product is widely believed to be a one-way function.

Terminology. Some of the (positive) results mentioned below require stronger forms of one-way

functions (e.g., one-way permutations with (or without) trapdoor 49, Sec. 2.4.4] and claw-free permutation pairs 49, Sec. 2.4.5]). Whenever we wish to avoid the speci c details, we will talk about standard intractability assumptions. In all cases, the conjectured intractability of factoring will su ce.

2.3 Computational Indistinguishability

A central notion in Modern Cryptography is that of\

e ective similarity" (introduced by Goldwasser, Micali and Yao 65, 86]). The underlying thesis is that we do not care whether or not objects are equal, all we care is whether or not a di erence between the objects can be observed by 6

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

a feasible computation. In case the answer is negative, the two objects are equivalent as far as any practical application is concerned. Indeed, like in many other cryptographic de nitions, in the definition of general/computational zero-knowledge we will freely interchange such (computationally indistinguishable) objects. The asymptotic formulation of computational indistinguishability refers to (pairs of) probability ensembles, which are in nite sequences of nite distributions, rather than to (pairs of) nite distributions. Speci cally, we consider sequences indexed by strings (rather than by integers (in unary representation)). For S f0; 1g, we consider the probability ensembles X= fX g 2S and Y= fY g 2S, where each X (resp., Y ) is a distribution that ranges over strings of length polynomial in j j. We say that X and Y are computationally indistinguishable if for every feasible algorithm A the di erence dA (n) def max 2f0;1gn fjPr A(X )= 1]? Pr A(Y )= 1]jg is a negligible= function in j j. That is:

De nition 3 (computational indistinguishability 65, 86]): We say that X= fX g 2S and Y= fY g 2S are computationally indistinguishable if for every family of polynomial-size circuits fDn g, every polynomial p, all su ciently large n and every 2 f0; 1g n\ S,poly( )

jPr Dn(X )=1]? Pr Dn(Y )=1]j< p(1n)where the probabilities are taken over the relevant distribution (i.e., either Xn or Yn ).

That is, we think of D= fDn g as of somebody who wishes to distinguish two distributions (based on a sample given to it), and think of 1 as of D's verdict that the sample was drawn according to the rst distribution. Saying that the two distributions are computationally indistinguishable means that if D is an e cient procedure then its verdict is not really meaningful (because the verdict is almost as often 1 when the input is drawn from the rst distribution as when the input is drawn from the second distribution). We comment that indistinguishability by a single sample (as de ned above) implies indistinguishability by multiple samples. Also note that the de nition would not have been stronger if we were to provide the distinguisher (i.e., D) with the index (i.e., ) of the distribution-pair being tested.4

3 De nitional IssuesLoosely speaking, zero-knowledge proofs are proofs that yield nothing beyond the validity of the assertion. That is, a veri er obtaining such a proof only gains conviction in the validity of the assertion. This is formulated by saying that anything that can be feasibly obtained from a zeroknowledge proof is also feasibly computable from the (valid) assertion itself. The latter formulation follows the simulation paradigm, which is discussed next. In de ning zero-knowledge proofs, we view the ve

ri er as a potential adversary that tries to gain knowledge from the (prescribed) prover. We wish to state that no (feasible) adversary strategy forFurthermore, the de nition would not have been stronger if we were to consider a specialized polynomial-size circuit per each 2 S (i.e., consider the di erence jPr D (X )= 1]? Pr D (Y )= 1]j for any set of circuits D= fD g 2S such that the size of D is polynomial in j j).4

3.1 The Simulation Paradigm

7

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

the veri er can gain anything from the prover (beyond conviction in the validity of the assertion). Let us consider the desired formulation from a wide perspective. A key question regarding the modeling of security concerns is how to express the intuitive requirement that an adversary\gains nothing substantial" by deviating from the prescribed behavior of an honest user. Our approach is that the adversary gains nothing if whatever it can obtain by unrestricted adversarial behavior can be obtained within essentially the same computational e ort by a benign behavior. The de nition of the\benign behavior" captures what we want to achieve in terms of security, and is speci c to the security concern to be addressed. For example, in the previous paragraph, we said that a proof is zero-knowledge if it yields nothing beyond the validity of the assertion (i.e., the benign behavior is any computation that is based (only) on the assertion itself, while assuming that the latter is valid). Thus, in a zero-knowledge proof no feasible adversarial strategy for the veri er can obtain more than a\benign veri er", which believes the assertion, can obtain from the assertion itself. We comment that the simulation paradigm, which was rst developed in the context of zero-knowledge 66], is pivotal also to the de nition of the security of encryption schemes (cf. 50, Chap. 5]) and cryptographic protocols (cf. 24, 47]). A notable property of de ning security (or zero-knowledge) via the simulation paradigm is that this approach is\overly liberal" with respect to its view of the abilities of the adversary as well as to what might constitute a gain for the adversary. Thus, the approach may be considered overly cautious, because it prohibits also\non-harmful" gains of some\far fetched" adversaries. We warn against this impression. Firstly, there is nothing more dangerous in cryptography than to consider\reasonable" adversaries (a notion which is almost a contradiction in terms): typically, the adversaries will try exactly what the system designer has discarded as\far fetched". Secondly, it seems impossible to come up with de nitions of security that distinguish\breaking the scheme in a harmful way" from\breaking it in a non-harmful way": what is harmful is application-dependent, whereas a good de nition of security ought to be application-independent (as otherwise using the scheme in any new application will require a full re-evaluation of its security). Furthermore, even with respect to a speci c application, it

is typically very hard to classify the set of\harmful breakings". Zero-knowledge is a property of some prover strategies. More generally, zero-knowledge is a property of some interactive machines. Fixing an interactive machine (e.g., a prescribed prover), we consider what can be computed by an arbitrary feasible adversary (e.g., a veri er) that interacts with the xed machine on a common input taken from a predetermined set (in our case the set of valid assertions). This is compared against what can be computed by an arbitrary feasible algorithm that is only given the input itself. An interactive strategy A is zero-knowledge on (inputs from) the set S if, for every feasible (interactive) strategy B, there exists a feasible (non-interactive) computation C such that the following two probability ensembles are computationally indistinguishable: 1. f(A; B )(x)gx2S def the output of B after interacting with A on common input x 2 S; and= 2. fC (x)gx2S def the output of C on input x 2 S .= We stress that the rst ensemble represents an actual execution of an interactive protocol, whereas the second ensemble represents the computation of a stand-alone procedure (called the\simulator"), which does not interact with anybody. Thus, whatever can be feasibly extracted from interaction with A on input x 2 S, can also be feasibly extracted from x itself. This means that nothing was gain by the interaction itself (beyond con dence in the assertion x 2 S ). 8

3.2 The Basic De nition

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

The above de nition does not account for auxiliary information that an adversary may have prior to entering the interaction. Accounting for such auxiliary information is essential for using zero-knowledge proofs as subprotocols inside larger protocols (see 55, 59]). This is taken care of by a more strict notion called auxiliary-input zero-knowledge.5

De nition 4 (zero-knowledge 66], revisited 59]): A strategy A is auxiliary-input zero-knowledge

on inputs from S if for every probabilistic polynomial-time strategy B and every polynomial p there exists a probabilistic polynomial-time algorithm C such that the following two probability ensembles are computationally indistinguishable: 1. f(A; B (z ))(x)gx2S; z2f0;1gp(jxj) def the output of B when having auxiliary-input z and inter= acting with A on common input x 2 S; and An interactive proof (resp., an argument) system for S is called auxiliary-input zero-knowledge if the prescribed prover strategy is auxiliary-input zero-knowledge on inputs from S .6 2. fC (x; z )gx2S; z2f0;1gp(jxj) def the output of C on inputs x 2 S and z 2 f0; 1gp(jxj) .=

The more basic de nition of zero-knowledge is obtained by eliminating the auxiliary-input z from De nition 4. We comment that almost all known zero-knowledge proofs are in fact auxiliary-input zero-knowledge. (Notable exceptions are zero-knowledge proofs constructed on purpose in order to show a separation between these two notions (e.g., in 55]) and protocols having only\non black-bo

x simulators" (see warm-up in 7]).) We stress that the zero-knowledge property of an interactive proof (resp., argument) refers to all feasible adversarial strategies that the veri er may employ (in attempt to extract knowledge from the prescribed prover that tries to convince the veri er to accept a valid assertion). In contrast, the soundness property of an interactive proof (resp., the computational-soundness property of an argument) refers to all possible (resp., feasible) adversarial strategies that the prover may employ (in attempt to fool the prescribed veri er to accept a false assertion). Finally, the completeness property (only) refers to the behavior of both prescribed strategies (when given, as common input, a valid assertion).

3.3 Variants

The reader may skip the current subsection and return to it whenever encountering (especially in the second part of this tutorial) a notion that was not de ned above.

3.3.1 Universal and black-box simulation5

We have already discussed two variants on the basic de nition (i.e., with or without auxiliaryinputs). Further strengthening of De nition 4 is obtained by requiring the existence of a universal

We note that the following de nition seems stronger than merely allowing the veri er and simulator to be arbitrary polynomial-size circuits. The issue is that the latter formulation does not guarantee that the simulator can be easily derived from the cheating veri er nor that the length of the simulator's description is related to the length of the description of the veri er. Both issues are important when trying to use zero-knowledge proofs as subprotocols inside larger protocols or to compose them (even sequentially). For further discussion, see Section 5. 6 Note that the prescribed veri er strategy (which is a probabilistic polynomial-time strategy that only depends on the common input) is always auxiliary-input zero-knowledge. In contrast, typical prover strategies are implemented by probabilistic polynomial-time algorithms that are given an auxiliary input (which is not given to the veri er), but not by probabilistic polynomial-time algorithms that are only given the common input.

9

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

is, in terms of De nition 4, one should replace C (x; z ) by C (x; z; hB i), where hB i denotes the description of the program of B (which may depend on x and on z ).7 That is, we e ectively restrict the simulation by requiring that it be a uniform (feasible) function of the veri er's program (rather than arbitrarily depend on it). This restriction is very natural, because it seems hard to envision an alternative way of establishing the zero-knowledge property of a given protocol. Taking another step, one may argue that since it seems infeasible to reverse-engineer programs, the simulator may as well just use the veri er strategy as an oracle (or as a\black-box"). This reasoning gave rise to the notion of black-box simulation, which was introduced and advocated in 55] and further studied in numerous works (see

, e.g., 28]). The belief was that impossibility results regarding black-box simulation represent inherent limitations of zero-knowledge itself. However, this belief has been refuted recently by Barak 7]. For further discussion, see Section 6. The (general) de nition of zero-knowledge (i.e., De nition 4) refers to all feasible veri er strategies. This choice is most natural since zero-knowledge is supposed to capture the robustness of the prover under any feasible (i.e., adversarial) attempt to gain something by interacting with it. Thus, we typically view the veri er as an adversary that is trying to cheat. A weaker and still interesting notion of zero-knowledge refers to what can be gained by an\honest veri er" (or rather a semi-honest veri er)8 that interacts with the prover as directed, with the exception that it may maintain (and output) a record of the entire interaction (i.e., even if directed to erase all records of the interaction). Although such a weaker notion is not satisfactory for standard cryptographic applications, it yields a fascinating notion from a conceptual as well as a complexity-theoretic point of view. Furthermore, as shown in 62], every public-coin proof system that is zero-knowledge with respect to the honest-veri er can be transformed into a standard zero-knowledge proof that maintains many of the properties of the original protocol (and without increasing the prover's powers or using any intractability assumptions). We stress that the de nition of zero-knowledge with respect to the honest-veri er V is derived from De nition 4 by considering a single veri er strategy B that is equal to V except that B also maintains a record of the entire interaction (including its own coin tosses) and outputs this record at the end of the interaction. (In particular, the messages sent by B are identical to the corresponding messages that would have been sent by V .)

simulator, denoted C, that is given the program of the veri er (i.e., B ) as an auxiliary-input; that

3.3.2 Honest veri er versus general cheating veri er

3.3.3 Statistical versus Computational Zero-Knowledge

Recall that the de nition of zero-knowledge postulates that for every probability ensemble of one type (i.e., representing the veri er's output after interaction with the prover) there exists a\similar" ensemble of a second type (i.e., representing the simulator's output). One key parameter is the interpretation of\similarity". Three interpretations, yielding di erent notions of zero-knowledge, have been commonly considered in the literature (cf., 66, 42]): 1. Perfect Zero-Knowledge (PZK) requires that the two probability ensembles be identical.97 8

Actually, we may incorporate x and z in hB i, and thus replace C (x; z; hB i) by C (hB i). The term\honest veri er" is more appealing when considering an alternative (equivalent) formulation of Definition 4. In the alternative de nition, the simulator is\only" required to generate the veri er's view of the real

interaction, when the veri er's view includes its inputs, the outcome of its coin tosses, and all messages it has received. 9 The actual de nition of PZK allows the simulator to fail (while outputting a special symbol) with some probability that is bounded away from 1, and the output distribution of the simulator is conditioned on its not failing.

10

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

2. Statistical Zero-Knowledge (SZK) requires that these probability ensembles be statistically close (i.e., the variation distance between them is negligible). 3. Computational (or rather general) Zero-Knowledge (CZK) requires that these probability ensembles be computationally indistinguishable. Indeed, Computational Zero-Knowledge (CZK) is the most liberal notion, and is the notion considered in De nition 4 as well as in most of this tutorial. (In particular, whenever we fail to qualify the type of zero-knowledge, we mean computational zero-knowledge.) The only exception is Section 9, which is devoted to a discussion of Statistical (or Almost-Perfect) Zero-Knowledge (SZK). We note that the class SZK contains several problems that are considered intractable.

3.3.4 Strict versus expected probabilistic polynomial-time

So far, we did not specify what we exactly mean by the term probabilistic polynomial-time. Two common interpretations are: 1. Strict probabilistic polynomial-time. That is, there exist a (polynomial in the length of the input) bound on the number of steps in each possible run of the machine, regardless of the outcome of its coin tosses. 2. Expected probabilistic polynomial-time. The standard approach is to look at the running-time as a random variable and bound its expectation (by a polynomial in the length of the input). As observed by Levin 73] (cf. 46]), this de nitional approach is quite problematic (e.g., it is not model-independent and is not closed under algorithmic composition), and an alternative treatment of this random variable is preferable.10 Consequently, the notion of expected polynomial-time raises a variety of conceptual and technical problems. For that reason, whenever possible, one should prefer to use the more robust (and restricted) notion of strict (probabilistic) polynomial-time. Thus, with the exception of constantround zero-knowledge protocols, whenever we talk of a probabilistic polynomial-time veri er (resp., simulator) we mean one in the strict sense. In contrast, with the exception of 7, 11],11 all results regarding constant-round zero-knowledge protocols refer to a strict polynomial-time veri er and an expected polynomial-time simulator, which is indeed a small cheat. For further discussion, the reader is referred to 11]. A question avoided so far is whether zero-knowledge proofs exist at all. Clearly, every set in P (or rather in BPP )12 has a\trivial" zero-knowledge proof (in which the veri er determines membershipSpeci cally, it is preferable to de ne expected polynomial-time as having running time that is polynomiallyrelated to a function that has

linear expectation. That is, rather than requiring that E Xn]= poly(n), one requires that for some Yn it holds that Xn= poly(Yn ) and E Yn]= O(n). The advantage of the latter approach is that if Xn 2 is deemed polynomial on the average then so is Xn, which is not the case under the former approach (e.g., Xn= 2n with probability 2?n and Xn= n otherwise). 11 Speci cally, in 7, 11] both the veri er and the simulator run in strict polynomial-time. We comment that, as shown in 11], the use of non-black-box is necessary for the non-triviality of constant-round zero-knowledge protocols under the strict de nition. 12 Trivial zero-knowledge proofs for sets in BPP n coRP require modifying the de nition of interactive proofs such that to allow a negligible error also in the completeness condition. Alternatively, zero-knowledge proofs for sets in BPP can be constructed by having the prover send a single message that is distributed almost uniformly (cf. 44]).10

4 Zero-Knowledge Proofs for every NP-set

11

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

by itself); however, what we seek is zero-knowledge proofs for statements that the veri er cannot decide by itself. Assuming the existence of commitment schemes13, which in turn exist if one-way functions exist 76, 68], there exist (auxiliary-input) zero-knowledge proofs of membership in any NP-set (i.e., sets having e ciently veri able static proofs of membership). These zero-knowledge proofs, rst constructed by Goldreich, Micali and Wigderson 57] (and depicted in Figure 2), have the following important property: the prescribed prover strategy is e cient, provided it is given as auxiliary-input an NP-witness to the assertion (to be proven). That is: Theorem 5 ( 57], using 68, 76]): If one-way functions exist then every set S 2 NP has a zeroknowledge interactive proof. Furthermore, the prescribed prover strategy can be implemented in probabilistic polynomial-time, provided it is given as auxiliary-input an NP-witness for membership of the common input in S . Theorem 5 makes zero-knowledge a very powerful tool in the design of cryptographic schemes and protocols (see below). We comment that the intractability assumption used in Theorem 5 seems essential; see 78].Commitment schemes are digital analogies of sealed envelopes (or, better, locked boxes). Sending a commitment means sending a string that binds the sender to a unique value without revealing this value to the receiver (as when getting a locked box). Decommitting to the value means sending some auxiliary information that allows to read the uniquely committed value (as when sending the key to the lock).

4.1 Constructing Zero-Knowledge Proofs for NP-sets

Common Input: A graph G(V; E ). Suppose that V f1;:::; ng for n def jV j.= Auxiliary Input (to the prover): A 3-coloring: V ! f1; 2; 3g. The following 4 steps are repeated t jE j many times so to obtain soundness error exp(?t). Prover's rst step (P1): Select uniformly a permutation over f1; 2; 3g. For i= 1 to n, sendthe veri er a co

mmitment to the value ( (i)). Veri er's rst step (V1): Select uniformly an edge e 2 E and send it to the prover. Prover's second step (P2): Upon receiving e= (i; j ) 2 E, decommit to the ith and j th values sent in Step (P1). Veri er's second step (V2): Check whether or not the decommitted values are di erent elements of f1; 2; 3g and whether or not they match the commitments received in Step (P1).

Figure 2: The zero-knowledge proof of Graph 3-Colorability (of 57]). Zero-knowledge proofs for other NP-sets can be obtained using the standard reductions.

Analyzing the protocol of Figure 2. Let us consider a single execution of the main loop.Clearly, the prescribed prover is implemented in probabilistic polynomial-time, and always convinces the veri er (provided that it is given a valid 3-coloring of the common input graph). In case13

Loosely speaking, commitment schemes are digital analogue of non-transparent sealed envelopes. See further discussion in Figure 2.

12

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

the graph is not 3-colorable then, no matter how the prover behaves, the veri er will reject with probability at least 1=jE j (because at least one of the edges must be improperly colored by the prover). We stress that the veri er selects uniformly which edge to inspect after the prover has committed to the colors of all vertices. Thus, Figure 2 depicts an interactive proof system for Graph 3-Colorability. As can be expected, the zero-knowledge property is the hardest to establish, and we will con ne ourselves to presenting a simulator (which we hope will convince the reader without a detailed analysis). We start with three simplifying conventions (which are useful in general): 1. Without loss of generality, we may assume that the cheating veri er strategy is implemented by a deterministic polynomial-size circuit (or, equivalently, by a polynomial-time algorithm with an auxiliary input). This is justi ed by xing any outcome of the veri er's coins, and observing that our (uniform) simulation of the various (residual) deterministic strategies yields a simulation of the original probabilistic strategy. 2. Without loss of generality, it su ces to consider cheating veri ers that (only) output their view of the interaction (i.e., their input, coin tosses, and the messages the received). This is justi ed by observing that the output of the original veri er can be computed by an algorithm of comparable complexity that is given the veri er's view of the interaction. Thus, it su ces to simulate the view of that cheating veri ers have of the real interaction. 3. Without loss of generality, it su ces to construct a\weak simulator" that produces output with some noticeable probability. This is the case because, by repeatedly invoking this weak simulator (polynomially) many times, we may obtain a simulator that fails to produce an output with negligible probability, whereas the latter yields a simulator that never fails (as required). The simulator starts by selecting uniformly and independe

ntly a random color (i.e., element of f1; 2; 3g) for each vertex, and feeding the veri er strategy with random commitments to these random colors. Indeed, the simulator feeds the veri er with a distribution that is very di erent from the distribution that the veri er sees in a real interaction with the prover. However, being computationally-restricted the veri er cannot tell these distributions apart (or else we obtain a contradiction to the security of the commitment scheme in use). Now, if the veri er asks to inspect an edge that is properly colored then the simulator performs the proper decommitment action and outputs the transcript of this interaction. Otherwise, the simulator halts proclaiming failure. We claim that failure occurs with probability approximately 1=3 (or else we obtain a contradiction to the security of the commitment scheme in use). Furthermore, based on the same hypothesis (but via a more complex proof), conditioned on not failing, the output of the simulator is computationally indistinguishable from the veri er's view of the real interaction.

Zero-knowledge proofs for other NP-sets. By using the standard Karp-reductions to 3-

Colorability, the protocol of Figure 2 can be used for constructing zero-knowledge proofs for any set in NP . We comment that this is probably the rst time that an NP-completeness result was used in a\positive" way (i.e., in order to construct something rather than in order to derive a hardness result). Subsequent positive uses of completeness results have appeared in the context of interactive proofs 74, 84], probabilistically checkable proofs 5, 36, 3, 2],\hardness versus randomness tradeo s" 6], and statistical zero-knowledge 83].

E ciency considerations. The protocol in Figure 2 calls for invoking some constant-roundprotocol for a non-constant number of times. At rst glance, it seems that one can derive a 13

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

constant-round zero-knowledge proof system (of negligible soundness error) by performing these invocations in parallel (rather than sequentially). Unfortunately, as demonstrated in 55], this intuition is not sound. See further discussions in Sections 5 and 6. We comment that the number of rounds in a protocol is commonly considered the most important e ciency criteria (or complexity measure), and typically one desires to have it be a constant. We mention that, under standard intractability assumptions (e.g., the intractability of factoring), constant-round zero-knowledge proofs (of negligible soundness error) exists for every set in NP (cf. 54]).

4.2 Using Zero-Knowledge Proofs for NP-sets

We stress two important aspects regarding Theorem 5: Firstly, it provides a zero-knowledge proof for every NP-set, and secondly the prescribed prover can be implemented in probabilistic polynomial-time when given an adequate NP-witness.

A generic application. In a typical cryptographic setting, a user referred to as U, has a secret

and is supposed to take some action depending on its secret. The

question is how can other users verify that U indeed took the correct action (as determined by U 's secret and the publicly known information). Indeed, if U discloses its secret then anybody can verify that U took the correct action. However, U does not want to reveal its secret. Using zero-knowledge proofs we can satisfy both con icting requirements (i.e., having other users verify that U took the correct action without violating U 's interest in not revealing its secrets). That is, U can prove in zeroknowledge that it took the correct action. Note that U 's claim to having taken the correct action is an NP-assertion (since U 's legal action is determined as a polynomial-time function of its secret and the public information), and that U has an NP-witness to its validity (i.e., the secret is an NP-witness to the claim that the action ts the public information). Thus, by Theorem 5, it is possible for U to e ciently prove the correctness of its action without yielding anything about its secret. Consequently, it is fair to ask U to prove (in zero-knowledge) that it behaves properly, and so to force U to behave properly. Indeed,\forcing proper behavior" is the canonical application of zero-knowledge proofs (see 58, 47]).

Zero-knowledge proofs for all IP. For the sake of elegancy, we mention that under the same assumption used in case of NP, it holds that any set that has an interactive proof also has a zero-knowledge interactive proof (cf. 69, 15]).

Part II

Advanced Topics

5 Composing zero-knowledge protocolsA natural question regarding zero-knowledge proofs (and arguments) is whether the zero-knowledge condition is preserved under a variety of composition operations. Three types of composition operation were considered in the literature: sequential composition, parallel composition and concurrent composition. We note that the preservation of zero-knowledge under these forms of composition is not only interesting on its own sake, but rather also sheds light of the preservation of the security of general protocols under these forms of composition. 14