We now make a further restriction against the verifier. While we required in the previous section in the condition II that V learns nothing from P's proof, we now require that V learns nothing whatsoever. By definition, a protocol is zero- knowledge iff I and II are satisfied and, moreover, V learns nothing from P that she could not learn by herself without P. In other words, V is able to simulate the protocol as if P were participating although he, in fact, is not. In this definition we assume the existence of one-way functions (in order to construct lockable boxes).

Let us consider another /VP-complete problem, namely, the construction of a Hamilton cycle in a graph G. By definition, a cycle (that is, a path with the same start and end nodes) in a graph G is a Hamilton cycle iff it passes through all nodes of G exactly once. The Prover, P, wants to convince the Verifier, V, that he knows a Hamilton cycle in a graph G with t nodes 1,. .., t. The protocol has again k rounds. Each round consists of 4 steps and proceeds as follows.

Moreover, P prepares locked boxes B_{tj}, 1 < i <j < t. The box B_{u} contains the

Step 1: P locks the t nodes of G in a random order into t boxes B_{l},... ,B,.

number 1 if there is an edge in G between the nodes locked in boxes B, and Bj. If there is no edge between these nodes, B_{i}} contains the number 0. P gives all boxes to V.

Step 2: V flips a coin and tells P the outcome.

Step 3: (a) If the outcome was "heads", P opens all the boxes, (b) If the outcome was "tails", P opens t boxes B_{ith}, B;_{2I3},..., B_{Ml}, where the indices run cyclically and every index appears exactly twice.

Step 4: (a) V verifies that she got a copy of G. The verification will be easy for her because the opened B,-boxes tell her the isomorphism used, (b) V verifies that all of the opened boxes contain the number 1.

Everything said about the protocol concerning 3-colorability (before Theorem 6.2) is valid also now: the protocol above satisfies the conditions I and II. Let us now show that the protocol is also zero-knowledge. Assume that V has an algorithm A (running in random polynomial time) to extract some information from her conversation with P. In the following way V can use A to extract the same information even in the absence of P.

V first plays the role of P. She flips a coin and, according to the outcome, she either applies an isomorphism to G and locks the result in boxes, or else locks an arbitrary t-cycle in boxes and, just for the fun of it, puts some numbers in other boxes to make the total number of boxes correct.

Now, having received the boxes, V plays the role of V. She applies her algorithm A to decide the choice between (a)- and (b)-lines. She either gets the same information as in the presence of a true prover P or learns that P is a false prover. Fcan do everything in polynomial time.

The same argument applies also to the protocol concerning 3-coloring. Hence, we obtain the following result.

Theorem 6.3. The given protocols for 3-coloring and Hamilton cycles are zero- knowledge.

Consider the way of locking the boxes presented at the end of Section 6.7. Then V does not gain anything from the way P commits himself to specific bits or opens the boxes. The boxes are simulatable in the sense that V can do everything just by herself without P being available at all. This concerns both locking and opening the boxes. The situation is different if the k rounds of the protocol are run in parallel. This will be discussed later on in this section.

Suppose P knows a positive solution for a problem in NP, for instance, a solution to a knapsack problem. (Here the term "positive" is to be contrasted with "negative": no solution exists. Our technique is straightforward for positive solutions. Zero-knowledge proofs are possible for negative solutions as well. For instance, a proof that a given knapsack problem possesses no solution has to be carried out within a suitable formalism.) Both of the problems discussed in Theorem 6.3 are /VP-complete. This means that any instance of a problem in NP, such as an instance of the knapsack problem, can be reduced in polynomial time to either one of them. This reduction can be carried out also by the Verifier. This result will be stated in the following theorem.

Theorem 6.4. Every positive solution for a problem in NP can be given a zero- knowledge proof

An interesting variation is obtained if all k rounds in the protocols of Theorem 6.3 are carried out in parallel. This means that P prepares at once k sets of locked boxes, and V asks k questions, one for each set. Assume that V uses the k sets of locked boxes to formulate her questions, for instance, by interpreting the k sets as k numbers, applying a one-way fc-place function to these numbers, and using the first k bits of the function value to determine the questions. Then it is conceivable that, although the dialogue might contain no information about Fs secret, still the dialogue could not be reconstructed without P. In other words, V could convince a third party about the secret's existence, although she could give no details concerning the secret. In fact, in this parallel version V is not able to simulate k rounds in polynomial time.

If the zero-knowledge character is to be maintained even in the parallel version of the protocol, then V should be able to open a locked box both as 0 and as 1. This is precisely what P is not able to do, and the situation can be achieved in some cases if V has additional information. More specifically, we say that the locked boxes are (or the method of locking information into the boxes is) chameleon iff V can simulate whatever she would have seen in the process by which P commits himself to bits and, moreover, V can simulate both the process by which P opens a box as a 0 and the process by which he opens it as a 1.

The boxes based on the discrete logarithm, as described at the end of Section 6.7, are not chameleon. If V, instead of P, chooses the number y, she still cannot open the box for both of the bits. This means that the protocol should not be performed in parallel if it is to be zero-knowledge. This can be seen by the following argument. Assume that V gives the number (2g^{e}, mod p) = r to P, where she has chosen e by herself. This means that a box locked by P looks like

(rV, mod p) = (g'e+W+y, mod p),

where is the discrete logarithm of 2 (mod p). Now V can use several boxes of this form to compute a function value to determine, for instance, her challenges to P. How would this be possible without P? V could, of course, fix the numbers y by herself but still, in order to open the box both as 0 and 1, she would have to know /?. By our assumption concerning discrete logarithms, she does not know /?. The more boxes there are, the greater will the influence of P be. Hence, V cannot play the role of P. The only way V could have created the record of the protocol without P is that she knows herself the thing to be proven, or else she knows the discrete logarithm of 2. If we exclude the second alternative, the record of the protocol can be used to convince a third party about the truth of the thing to be proven.

It is possible to add the chameleon property to the locked boxes. Rather than choosing r randomly, V chooses an exponent e randomly and gives P the number

r = (g^{e}, mod p).

Now V knows the discrete logarithm of r and can, if necessary, convince P of this fact by a minimum disclosure proof.

We still consider another very basic /VP-complete problem, namely, the satisfiability problem for propositional formulas. The problem remains /VP-complete even if we assume that the propositional formulas are in 3-conjunctive normal form, that is, conjunctions of disjunctions, where each disjunction consists of 3 literals. A literal is a propositional variable or its negation. For instance,

(x, V X_{2} V ~ X_{4}) A (x_{2} V ~ x_{3} V X_{4}) A ( ~ X_{t} V X_{2} V X_{3}) A ( ~ X_{t} V ~ X_{2} V ~ X_{3}) A (X, V X_{3} V X_{4}) A ( ~ X_{2} V X_{3} V X_{4})

is a propositional formula in 3-conjunctive normal with four propositional variables and six clauses. The formula is satisfiable iff there is an assignment of truth-values T(true) and F (false) for the variables for which the formula assumes the truth- value T. In this case, such an assignment is

(*) Xj = x_{3} = x_{4} = r, x_{2} = F .

When Peter wants to convince Vera in a zero-knowledge manner that he knows a satisfiability assignment, he can do so following Theorem 6.4. We present a more direct method, resembling our discussion concerning 3-colorability. Such a more direct approach is more appropriate because satisfiability problem is basic in the sense that problems in NP can be reduced to it in a straightforward fashion, see [Sal],

Thus, P and V know a propositional formula a in 3-conjunctive normal form. Assume that a has r propositional variables and t clauses. (We could assume that a is arranged in some alphabetic order but this is not important.) P wants to convince V that he knows an assignment of truth-values for the variables making a true. As an illustration, we consider the formula above and the assignment (*).

P first prepares 2r boxes B, and Bf^{v}, i = 1,. . ., 2r, referred to as variable and truth-value boxes, respectively. For each of the 2r pairs (x, y), where x is a propositional variable and y is a truth-value (Tor F), there is an i such that x is locked in B_{i }and y is locked in Bf^{y}. Moreover, the pairs (x, y) appear in a random order in the pairs of boxes (B,, Bf). In our illustration, there are 8 pairs of boxes, for instance,

B,:

*4

T

B_{2}:

*2

BY:

F

B_{3}:

BY:

F

B_{4}:

x_{4}

BY:

F

B_{s}-

*3

BY:

T

B_{6}:

*3

BY:

F

B_{7}:

Xj

BY:

T

B_{8}:

x_{2}

BY:

T

Moreover, P prepares (4r)^{3} boxes B_{i j k}, where the three indices range from 1 to 2 r and from ~ 1 to ~ 2 r, and each box contains either 0 or 1. The number 1 appears in the box B_{iyr} exactly in case i' = i or f = ~ i,j' = j or/ = ~j,k' = k or k! = ~ k, a contains a clause, where the three variables are the ones appearing in the boxes B,, Bj, B_{k} (in this order and negated if this is indicated by /',/, k') and, in addition, the three truth-values P assigns to these three variables (in his specific satisfiability assignment) are the ones appearing in the boxes Bj^{y}, Bj^{v}, B%^{v} (in this order). The boxes Be,/,*- are referred to as assignment boxes. Thus, t of them contain the number 1. In our illustration, the six assignment boxes containing the number 1 are

We have listed the boxes in the same order as the clauses above.

The protocol now runs similarly as the protocol for 3-colorability. In each round of the protocol, P prepares and gives V the locked boxes as described above,

V has now two options.

If V so desires, P opens for her all the boxes except the truth-value boxes.

V learns from the assignment boxes containing the number 1 the original propositional formula a. Thus, she learns that P has used the correct a when locking the boxes but she obtains no information whatever about P's truth-value assignment.

V may also ask P to open all truth-value boxes. P then opens for her also all those assignment boxes B_{rj}where each of the indices is of the form x with F in B or of the form ~ x with T in Bl^{v}. If the number 0 appears in all of these boxes, then P's truth-value assignment is correct: no clause getting the value F by this assignment appears in a. Thus, all clauses appearing in a get the value T by P's assignment. V will be convinced about this, although she learns nothing about P's assignment. In our illustration, P opens all assignment boxes, where each of the three indices belongs to the set {2, 3,4,6, ~ 1, ~ 5, ~ 7, ~ 8}.

The following result is obtained in the same way as Theorem 6.3: the probability of P cheating is multiplied by \ after the completion of each round.

Theorem 6.5. The protocol given above for satisfiability is zero-knowledge.

Any of Theorems 6.3-6.5 can be used to convert any mathematical proof into a zero-knowledge proof. Suppose you know a proof of, say, Fermat's Last Theorem. Suppose, further, that your proof has been formalized within some proof-theoretic system. This means that there is no "hand-waving" involved: a verifier can check that every step in the proof follows by the rules of the system. Assume, finally, that an upper bound for the length of the proof is given.

The proof can be found out by a nondeterministic procedure working in polynomial time. The procedure first guesses the proof and then checks its validity step by step. On the other hand, the procedure (say, a nondeterministic Turing machine) can be described in terms of a propositional formula a in 3-conjunctive normal form such that a is satisfiable iff the theorem has a proof whose length does not exceed the given bound. The construction of a is effective in the sense that anybody knowing a proof for the theorem knows also a satisfiability assignment for a. Hence, you are able to convince a verifier that you know a proof for the theorem without giving away any information about the proof except an upper bound for its length.

A few additional comments are in order. In results such as Theorem 6.4 the existence of one-way functions is needed. In fact, in our zero-knowledge protocols one-way functions are used in the construction of lockable boxes. What this means is that the prover reveals his secret to the verifier in an encrypted form. Although the verifier does not gain any on-line information, it is conceivable that she could later on, either by luck or by sufficient computing effort, break the cryptosystem and learn the entire secret. Recall, for instance, that the 3-coloring is given to the verifier in each set of locked boxes.

We will not discuss here protocols referred to as perfect zero-knowledge. In such protocols V obtains no information whatsoever about P's secret (beyond its existence), whereas in the zero-knowledge protocols discussed above V obtains no information she could use on-line or in polynomial time. The reader might think about the meaning of zero-knowledge proofs with RSA-locked boxes in case the theorem to be proved is "There is an algorithm for factorization working in linear time".

In the protocols discussed above, the probability of P cheating decreases very rapidly with respect to the number of rounds. However, arbitrarily high security is not obtained with a bounded number of rounds. This technique can be modified to combine arbitrarily high security with a constant number of rounds. In some setups even non-interactive zero-knowledge proof systems are possible. The results of [BeG] can be applied in the following scenario. After P and V have generated together a long random sequence, P leaves for a trip around the world. Whenever he discovers a theorem, he writes a postcard to V proving his new theorem in zero-knowledge. This process is necessarily non-interactive because P has no predictable address.