Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

Подождите немного. Документ загружается.

11.2 Interactive Proof Systems 147

11.2 Interactive Proof Systems

Now that we have motivated the notion of interactive proofs and discussed

possible realizations, we come to the formal deﬁnition.

Deﬁnition 11.2.1. An interactive proof system consists of a communication

protocol between two parties P (Paul, prover) and V (Victoria, veriﬁer), each

of which has a randomized algorithm. The communication protocol speciﬁes

who sends the ﬁrst message. After a number of communication rounds that

may depend on the input and on randomness, Victoria must decide whether

or not to accept the input. The computation time for Victoria is bounded by

a polynomial.

We use D

P,V

(x) to denote the random variable that describes whether x

is accepted by Victoria at the end of the protocol. D

P,V

(x) takes on the value

1ifx is accepted and 0 if x is rejected. The requirement that the algorithms

P and V abide by the communication protocol C will be tacitly assumed

throughout the following discussion.

Deﬁnition 11.2.2. A decision problem L belongs to the complexity class

if there is a communication protocol C and a randomized polynomial-time

bounded algorithm V with the properties that

• There is a randomized algorithm P such that for all x ∈ L,

Prob(D

P,V

(x)=1)≥ 3/4 .

• For all randomized algorithms P ,ifx/∈ L, then

Prob(D

P,V

(x)=1)≤ 1/4 .

A problem L ∈

IP belongs to IP(k) if the communication protocol in the deﬁni-

tion above allows at most k communication rounds, that is, at most k messages

are exchanged.

We can always arrange that Paul sends the last message, since it doesn’t

help Victoria any to send a message to which she receives no reply. The allow-

able error-probability of 1/4 that appears in Deﬁnition 11.2.2 is to a certain

extent arbitrary. Without increasing the number of communication rounds

required, Paul and Victoria could carry out polynomially many simultaneous

dialogues. At the end, Victoria could use the majority of these polynomially

many individual “mini-decisions” as her decision for the expanded protocol.

So by Theorem 3.3.6, the error-probability can be reduced from 1/2 − 1/p(n)

to 2

−q(n)

,wherep and q are polynomials. It is therefore suﬃcient to design

interactive proof systems with an error-probability 1/2 − 1/p(n) to obtain

interactive proof systems with error-probability 2

−q(n)

In Section 11.1 we informally discussed an interactive proof system for

problems L ∈

NP. There we only required one communication round in which

148 11 Interactive Proofs

Paul sent y to Victoria. The decision of Victoria was to accept x if and only if

(x, y) ∈ L



. Since this decision protocol is error-free, it follows that NP ⊆ IP(1).

Since

IP(1) is already “quite large”, we can suspect that IP is “really large”.

In fact,

IP = PSPACE (Shamir (1992)). Here PSPACE denotes the class of all

decision problems for which there are algorithms that require only polynomi-

ally bounded storage space (see Chapter 13). Since we will show in Chapter 13

that all the complexity classes of the polynomial hierarchy belong to

PSPACE,

IP is indeed a very large complexity class. We will concentrate our attention

on interactive proof systems with a small number of communication rounds.

11.3 Regarding the Complexity of Graph Isomorphism

Problems

To simplify notation, for the rest of this chapter we will use GI as an abbre-

viation for

GraphIsomorphism. Recall that GI is the problem of determining

whether two graphs G

=(V

)andG

=(V

) are isomorphic. They

are isomorphic if they are identical up to the labeling of their vertices, that

is, if G

is the result of applying a relabeling of the vertices to the graph G

The relabeling π : V

→ V

must be bijective and satisfy

{u, v}∈E

⇔{π(u),π(v)}∈E

It is simple to check whether |V

| = |V

|. Graphs with diﬀerent numbers of

vertices cannot be isomorphic, so we will assume in what follows that V

= {1,...,n}, and thus the set of bijections π : {1,...,n}→{1,...,n} is

just the set S

of permutations on {1,...,n}.

Since

NP ⊆ IP(1), GI ∈ IP(1). The proof consists of giving a suitable

permutation π. Because of the asymmetry between Paul and Victoria and

the diﬃculty of realizing universal quantiﬁers in an interactive proof system,

most experts do not believe that

co-NP ⊆ IP(1) or even that co-NP ⊆ IP(2).

In particular, it is believed that the

co-NP-complete problems do not belong

IP(2). For this reason, the following result showing that

GI ∈ IP(2) is an

indication that

GI is not NP-complete.

Theorem 11.3.1.

GI ∈ IP(2).

Proof. The input consists of two graphs G

and G

with V

= V

= {1,...,n}.

Paul and Victoria use the following interactive proof system.

• Victoria randomly generates i ∈{0, 1} and π ∈ S

. Then she computes

H = π(G

), the graph that results from applying the permutation π to

graph G

, and sends the graph H to Paul.

• Paul computes j ∈{0, 1} and sends it to Victoria.

• Victoria accepts (G

)ifi = j. Accepting (G

) means that Victoria

believes the graphs G

and G

are not isomorphic.

11.3 Regarding the Complexity of Graph Isomorphism Problems 149

Victoria can do her work in polynomial time. A permutation π can be

represented as (π(1),...,π(n)). When generating a random permutation, one

must take care that each π(i)isdiﬀerentfromπ(1),...,π(i − 1). This can

be done by generating the log(n − i +1) bits of a random integer k which

represents that for π(i) we should choose the (k + 1)st smallest as yet unused

number. With probability less than 1/2, k>n−i+1 and so is too large. In this

case we simply repeat the procedure up to n times. The probability that this

method fails to produce a permuation is then less than n/2

, which is so small

that Victoria can just arbitrarily choose whether or not to accept the pair of

graphs. By the robustness of the

IP-classes with respect to small changes in

the error-probability, this small amount of error won’t make any diﬀerence.

We have discussed the procedure for generating a random permutation in

detail here, but in the future we will simply make statements like “generate

a random π ∈ S

” without further commentary.

If G

and G

are not isomorphic, then H is isomorphic to G

but not to

1−i

. So Paul can determine i by applying all π



∈ S

to G

and G

,and

comparing the results to H. He sets j = i and sends this value to Victoria

who will correctly accept (G

). If Victoria decides to accept also in the

(rare) case that she is unable to generate a random permutation, then this

interactive proof system will have one-sided error.

If G

and G

are isomorphic, all three of the graphs that Paul has (G

,andH) are isomorphic. In fact there will be exactly as many π



∈ S

with H = π



) as there are π



∈ S

with H = π



). We want to take

a closer look at this observation. Let G

∗

=(V

∗

)withV

∗

= {1, 2, 3} and

∗

= {{1, 2}}.Forπ

∗

deﬁned by π

∗

(1) = 2, π

∗

(2) = 1, π

∗

(3) = 3, we have

∗

)=G

∗

. In general, the permutations π on G with π(G)=G form the

automorphism group of G, denoted Aut(G). These permutations form a group

under composition of functions. Since the order (size) of a subgroup always

divides the order of a group, n!/| Aut(G)| is an integer. We claim that there

are exactly | Aut(H)| many π



∈ S

with H = π



). Since there is such a

permutation π



, the set of permutations π

∗

◦ π



such that π

∗

∈ Aut(H) form

| Aut(H)| many permutations of the desired kind. Furthermore, there cannot

be any more such permutations because if

π(G

)=H and π



)=H,then



◦ (

π)

−1

(H)=H and π

∗

:= π



◦ (π)

−1

∈ Aut(H). So (π

∗

)

−1

∈ Aut(H)and

π =(π

∗

)

−1

◦ π



belongs to the set of permutations we already have.

By deﬁnition Prob(i =0)=Prob(i =1)=1/2, and the only ad-

ditional information for Paul is the random graph H. We have seen that

H is (independent of the value of i) a random graph from the set of

n!/| Aut(G

)| = n!/| Aut(G

)| graphs that are isomorphic to G

and G

.So

Prob(i =0| H)=Prob(i =1| H)=1/2 and Paul is in the situation of

having to correctly provide the outcome of a fair coin toss. No matter how

he decides, he will only succeed with probability 1/2. So the entire interac-

tive proof system has a one-sided error-probability just over 1/2. For non-

isomorphic graphs Victoria’s decision is correct, and for isomorphic graphs,

she makes an error with probability

n+1

. If we carry out the protocol

150 11 Interactive Proofs

twice and Victoria only accepts if both trials recommend acceptance, then

her decision for non-isomorphic graphs remains correct and for isomorphic

graphs the error-rate is approximately 1/4. The number of communication

rounds does not increase, since in each round the subprotocol can be carried

out twice. 

In the deﬁnition of interactive proof systems we combined nondetermin-

ism and randomization with limited two-sided error, as we discussed in Sec-

tion 11.1. The complexity class

BPP(NP) also combines nondeterminism and

randomization (see Deﬁnition 10.5.2). In this case, a

BPP algorithm may make

repeated queries to an

NP-oracle. In particular, the oracle answer may be

negated and so

BPP(NP)=co-BPP(NP). If instead we want to think of ran-

domization as a “third quantiﬁer” in addition to ∃ and ∀, then we want to

rule out the negation of the oracle answer. This idea leads to the following

deﬁnition of the operator

BP(·) on a complexity class C:

Deﬁnition 11.3.2. A decision problem L belongs to

BP(C) if there is a de-

cision problem L



∈Cwith the following properties, where r ∈{0, 1}

p(|x|)

for

some polynomial p and the probabilities are with respect to the choice of r:

• If x ∈ L, then Prob

((x, r) ∈ L



) ≥ 3/4.

• If x/∈ L, then Prob

((x, r) ∈ L



) ≤ 1/4.

It follows immediately from this deﬁnition that

BP(C) ⊆ BPP(C).

We can characterize

BP(NP) as follows: There is a language L



∈ P and a

polynomial p describing the lengths of r and y in dependence upon |x| such

that

• if x ∈ L,thenProb

(∃y :(x, r, y) ∈ L



) ≥ 3/4;

• if x/∈ L,thenProb

(∃y :(x, r, y) ∈ L



) ≤ 1/4.

Note that our proof that

NP(BPP) ⊆ BPP(NP) (Lemma 10.5.7) actually

showed that

NP(BPP) ⊆ BP(NP).

While for the class

BP(NP) the entire computation time is polynomially

bounded, for

IP(2), Paul has unlimited time. The requirements regarding error-

probability are the same for the two classes, so the following result is not

surprising.

Theorem 11.3.3.

BP(NP) ⊆ IP(2).

Proof. Victoria and Paul use the characterization for a language L ∈

BP(NP)

given following Deﬁnition 11.3.2.

• Victoria randomly generates r ∈{0, 1}

p(|x|)

and sends r to Paul.

• Paul computes a y ∈{0, 1}

p(|x|)

and sends y to Victoria.

• Victoria accepts if (x, r, y) ∈ L



11.3 Regarding the Complexity of Graph Isomorphism Problems 151

Since L



∈ P, Victoria can do her work in polynomial time. For all y ∈

{0, 1}

p(|x|)

Paul can check the property (x, r, y) ∈ L



. If he ﬁnds a suitable y,

he sends it to Victoria. If x ∈ L, this succeeds with probability at least 3/4;

but if x/∈ L, then this succeeds with probability at most 1/4. Thus L ∈

IP(2).



The interactive proof system used in the proof of Theorem 11.3.3 can also

be described in the form of a fairy tale. King Arthur gives the wizard Merlin

a task (x, r). Merlin is supposed to ﬁnd y with (x, r, y) ∈ L



. This is a task

that normal people cannot do in polynomial time, but Merlin is usually able

to do it – even wizards must and can live with exponentially small error-

probabilities. This view of

BP(NP) has led to the names Arthur-Merlin game

for this type of proof system and

AM for the complexity class BP(NP).

By Theorem 11.3.3, a proof that

GI ∈ BP(NP) would be an even stronger

indication that

GI is not NP-complete. It is not known whether GI /∈ NPC

follows from NP = P. But from

GI ∈ BP(NP) and the assumption that Σ

= Π

(see Chapter 10) it follows that GI is not NP-complete. We will show this in

Theorems 11.3.4 and 11.3.5.

Theorem 11.3.4.

GI ∈ BP(NP).

Proof. First we outline the basic ideas in the proof. Then we will go back and

ﬁll in the details. In order to show that

GI ∈ BP(NP), we are looking for a

characterization of

GI that matches Deﬁnition 11.3.2. Let x =(G

). We

can assume that G

and G

are deﬁned on the vertex set {1,...,n}. We will

use ≡ to represent graph isomorphism. So we need to come up with a y that

contains enough information to distinguish between G

≡ G

and G

≡ G

The basis for this distinction will be the sets

Y (G

):={(H, π) | π ∈ Aut(H)andH ≡ G

} ,

and

Y := Y (G

):=Y (G

) ∪ Y (G

) .

|Y | can be used to determine whether G

≡ G

or G

≡ G

. In the proof

of Theorem 11.3.1 we saw that there are n!/| Aut(G

)| many graphs H such

that H ≡ G

,so|Y (G

)| = n! for any graph G

with n vertices. Furthermore,

if G

≡ G

,thenY (G

)=Y (G

), so |Y | = |Y (G

)| = n!. But if G

≡ G

then Y (G

) ∩ Y (G

)=∅,so|Y | = |Y (G

)| + |Y (G

)| =2n!.

Of course, we don’t see how to compute |Y | eﬃciently. It suﬃces, however,

to distinguish between the cases |Y | = n!and|Y | =2n!, which means that an

approximate computation of |Y | would be enough, and we may even allow a

small error-probability. At the end of our proof we will see that the diﬀerence

between n!and2n! is too small. So instead of Y we will use Y



:= Y × Y ×

Y × Y × Y .Then|Y



| =(n!)

,ifG

≡ G

, and |Y



| =32· (n!)

,ifG

≡ G

The vector y from the characterization following Deﬁnition 11.3.2 will be made

from strings y



and y



. The string y



must belong to Y



,itisrequiredthaty



152 11 Interactive Proofs

a 0-1 string of ﬁxed length, and we must be able to check whether y



∈ Y



.The

vector y



will be another 0-1 string that will help us check whether y



∈ Y



A necessary condition for (x, r, y) ∈ L



will therefore be that y =(y





where y



describes graphs H

,...,H

and permutations π

,...,π

and that



describes permutations α

,...,α

such that π

∈ Aut(H

)andH

≡ α

)

or H

≡ α

). These conditions can be checked in polynomial time.

Let the length of the description of y



be l. We will only consider such



∈{0, 1}

that are contained in Y



. For reasons that will be clear shortly,

we assume that 0

/∈ Y



, which is certainly the case for obvious descriptions

of graphs and permutations.

It’s about time we describe how to obtain a randomized estimate for |Y



For this we will make use of a family of hash functions on the universe U =

{0, 1}

with values in {0, 1}

for a value of k to be speciﬁed later. For a random

choice of hash function from the family and for every z ∈{0, 1}

with z =0

we want to have the following property:

Prob

(h(z)=0

)=2

−k

We will be interested in the probability of the event “∃y



∈ Y



: h(y



)=0

”. It

is obvious that this probability grows with |Y



|.Furthermore,forz,z



∈{0, 1}

such that z = z



, z =0

,andz



=0

, we want the events “h(z)=0

”and

“h(z



)=0

” to be independent. All probabilities are with respect to the

random choice of a hash function.

Now we ﬂesh out this proof idea. Our family of hash functions contains

for each k × l-matrix W over {0, 1} the hash function h

(z)=W · z,wherez

is interpreted as a column vector and the computations are carried out in Z

i.e., modulo 2. The random matrix W takes the place of the random vector r

in the characterization following Deﬁnition 11.3.2. Finally, L



contains all (x =

),r = W, y =(y





)) such that y



∈ Y



, y



contains the information

described above for helping to check whether y



∈ Y



,andW ·y



.Bythe

preceding discussion it is clear that L



∈ P, so it only remains to check the

probability part of the characterization following Deﬁnition 11.3.2.

First we investigate the random hash function h

(z)=W · z. Here it will

become clear why we must avoid the case that z =0

. We know for sure that

)=0

.Nowletz =0

and z

=1.Thei-th bit of h

(z)isgivenby



m=j

· z

= w



m=j

· z

with sums taken mod 2. Since the values of h

(z)forw

= 0 and w

are diﬀerent, the ith bit of h

(z) takes on the values 0 and 1 with probability

1/2 each. Since the rows of W are chosen independently of each other, every

value from {0, 1}

(including 0

) has probability 2

−k

of being equal to h

(z).

Finally, if z = z



, z =0

,andz



=0

, then the random vectors h

(z)and



) are independent. Suppose z

= z



.Thenw

= w



if and only

if w

= 0, and therefore this event has probability 1/2. Independent of the

11.3 Regarding the Complexity of Graph Isomorphism Problems 153

values of the sum of all w

with m = j and the sum of all w



with

m = j,theith bits of h

(z)andh



) agree with probability 1/2. Once

again the statement for vectors follows from the fact that the rows of W are

chosen independently.

The next step is to investigate the random number S of all y



∈ Y



with



)=0

. The random variable S is the sum of the |Y



| random vari-

ables S(y



), where S(y



)=1ifh



)=0

and otherwise S(y



)=0.By

Remark A.2.3 it follows that E(S(y



)) = 2

−k

and by Theorem A.2.4 it follows

that E(S)=|Y



|·2

−k

.SinceS(y



) only takes on values 0 and 1, the variance is

easy to compute straight from the deﬁnition: V (S(y



)) = 2

−k

·(1−2

−k

) ≤ 2

−k

So by Theorem A.2.7, V (S) ≤|Y



|·2

−k

=E(S). Since |Y



| is diﬀerent in the

two cases G

≡ G

and G

≡ G

, it is good that |Y



| showsupasafactorin

the expected value of S.Furthermore,V (S)isnotverylarge.

The probability that we are interested in is

Prob(∃y =(y





):(x =(G

),r = W, y =(y





)) ∈ L



) .

If y



∈ Y



, then there is also a corresponding y



. So we can represent the event

more succinctly: we are interested in Prob(∃y



∈ Y



: h



)=0

), or using

the notation used above, in Prob(S ≥ 1). This probability should be large if

E(S) is somewhat larger than 1, and small if E(S) is somewhat smaller than

1. The choice of k := log(4 · (n!)

) achieves this.

If G

≡ G

,then

E(S)=(n!)

· 2

−log(4·(n!)

)

≤ 1/4 .

By the Markov Inequality (Theorem A.2.9) with t =1,

Prob(S ≥ 1) ≤ E(S) ≤ 1/4 ,

and we obtain for (G

) /∈

GI the desired small acceptance probability.

If G

≡ G

,then

E(S)=32· (n!)

· 2

−log(4·(n!)

)

≥ 32 · (n!)

· 2

− log(4·(n!)

)

=4.

Our goal is to show that Prob(S ≥ 1) ≥ 3/4, or equivalently that Prob(S =

0) ≤ 1/4. In order to be able to apply the Chebychev Inequality (Corol-

lary A.2.10), we use the fact that if S =0,then|S − E(S)|≥E(S). We let

t := E(S) in the Chebychev Inequality. Then

Prob(S =0)≤ Prob(|S − E(S)|≥E(S))

≤ V (S)/ E(S)

Earlier we showed that V (S) ≤ E(S)andE(S) ≥ 4. From this it follows that

Prob(S =0)≤ 1/ E(S) ≤ 1/4

154 11 Interactive Proofs

and so Prob(S ≥ 1) ≥ 3/4. For (G

) ∈

GI this is the large acceptance

probability that was desired. All together we have characterized

GI in such

a way that the statement

GI ∈ BP(NP) has been proven according to Deﬁni-

tion 11.3.2. 

Theorem 11.3.5. If

GI is NP-complete, then Σ

= Π

Proof. For most parts of this proof we will ﬁnd the operator notation of Chap-

ter 10 convenient. In order to show that Σ

= Π

, by Lemma 10.4.2 it is

suﬃcient to show that Σ

⊆ Π

.SoletL ∈ Σ

and thus representable as

∃·∀·

P.IfGI is NP -complete, then

GI is co-NP-complete and the ∀-operator

can be replaced by an oracle for

GI. By Theorem 11.3.4, GI ∈ BP(NP)and

we can make use of the characterization of

BP(NP) that was discussed follow-

ing Deﬁnition 11.3.2. This means that there is a representation for L of the

form ∃·

BP ·∃ · P. Shortly we will show that from this it follows that there

is a

BP ·∃ · P-representation. By Theorem 10.5.1 BPP ⊆ Π

and BP · P can be

replaced with ∀·∃·

P. We can directly generalize the proof of Theorem 10.5.1

without any new ideas so that we can replace

BP ·∃ · P with ∀·∃·∃·P and so

with ∀·∃·

P. This representation proves that L ∈ Π

and Σ

⊆ Π

It remains to show the transformation from a ∃(

BP)∃ P-representation into

BP)∃ P -representation. If L has a ∃(BP)∃ P-representation, then there is a

decision problem L



∈ P such that

x ∈ L ⇒∃y :Prob(∃z :(x, y, z, r) ∈ L



) ≥ 3/4 , and

x/∈ L ⇒∀y :Prob(∃z :(x, y, z, r) ∈ L



) ≤ 1/4 ,

where the probabilities above are with respect to the random vector r, and for

n = |x| the vectors y, z,andr have length p(n). By repeating the procedure

and taking a majority vote, we can reduce the error-probability to 2

−p(n)

/4.

This makes z and r longer, but not x and y.

The statement “∃y :Prob(∃z :(x, y, z, r) ∈ L



) ≥ 1−2

−p(n)

/4” means that

this y exists independent of the random vector r. From this it follows that

x ∈ L ⇒ Prob(∃(y, z): (x, y, z, r) ∈ L



) ≥ 1 − 2

−p(n)

/4 ≥ 3/4.

In the second case (x/∈ L)wecannotargueinthesameway.Assumefor

the sake of contradiction that there is an x/∈ L with

Prob(∃(y,z): (x, y, z, r) ∈ L



) > 1/4.

Then for more than a quarter of the r’s there is a “good pair” (y,z). We

write this as a table of the selected random vectors r with a respective good

(y, z)-pair for each of these r’s. Since there are only 2

p(n)

vectors y,bythe

pigeonhole principle there is a y

∗

such that y

∗

occurs in the y-column for at

least a fraction of 2

−p(n)

of the r’s in our table. This y

∗

is then a good choice

for a fraction of more than 2

−p(n)

/4ofallr’s. That is, for an x/∈ L we have

11.4 Zero-Knowledge Proofs 155

∃y (namely y

∗

): Prob(∃z :(x, y, z, r) ∈ L



) > 2

−p(n)

/4 .

This contradicts the characterization of x/∈ L given above for the error-

probability 2

−p(n)

/4. Thus the assumption must be false and we have

x/∈ L ⇒ Prob(∃(y, z): (x, y, z, r) ∈ L



) ≤ 1/4.

Thus we have obtained a

BP ·∃ · P-representation for L and the Theorem is

proven. 

In the example of the graph isomorphism problem we have seen that the

consideration of the polynomial hierarchy, the characterization of its

complexity classes, and the investigation of interactive proof systems

have all contributed to the complexity theoretic classiﬁcation of speciﬁc

problems. The hypothesis that

GI is not NP-complete is at least as

well supported as the hypothesis that the polynomial hierarchy does

not collapse to the second level.

11.4 Zero-Knowledge Proofs

The underlying idea of an interactive proof system is that Paul provides Vic-

toria with enough information that she can check the proof with a small error-

probability. So, for example, to convince Victoria that two publicly available

graphs are isomorphic, Paul could send Victoria his secret π, the relabeling

of the vertices that shows the two graphs are isomorphic. In any interactive

proof system, Paul must send to Victoria some information related to the in-

put. So in this sense, there are no interactive proof systems that reveal “zero

knowledge”. On the other hand, if Victoria could have computed the infor-

mation sent by Paul herself in polynomial time and we consider polynomial

time to be available, then it is as if Paul had revealed no information. But in

such a case, Paul can’t do any more than Victoria, so he has no secret infor-

mation. Now let’s go a step further and allow Victoria expected polynomial

time. This means exponential time with correspondingly small exponential

probability. If Paul does not want to reveal any knowledge (for example, he

doesn’t want to reveal any information about his password), then he has to

assume that others are interested in this information. Among them are spies

who may eavesdrop on the conversation and Victoria, who may deviate from

the prescribed protocol if it helps her gain information from Paul. We will

not, however, allow the spies to interfere with the conversation and send or

modify messages. This all leads to the deﬁnition of zero-knowledge proofs.

Deﬁnition 11.4.1. Let P and V be randomized algorithms of an interactive

proof system for the decision problem L. This proof system has the perfect

zero-knowledge property if for every polynomial-time randomized algorithm

156 11 Interactive Proofs



that can replace V (that is, V



must send the same type of messages), there

is a randomized algorithm A with polynomially bounded worst-case expected

runtime that for each x ∈ L produces what is communicated between P and



with the same probabilities.

For problems in

P, Victoria can compute all the information herself, so

perfect zero-knowledge proofs are only interesting for problems that lie outside

P. It is not immediately clear that there are any perfect zero-knowledge

proofs for problems outside

P, but for GI, which presumably does not belong

P, we have the following:

Theorem 11.4.2. There is an interactive proof system for

GI with the perfect

zero-knowledge property.

Proof. Let G

and G

be graphs so that Paul’s secret is a permutation π

∗

with

= π

∗

). He would like to prove that G

and G

are isomorphic without

giving away any information about π

∗

in the course of the conversation. The

trick is to generate a random graph H that is isomorphic to G

and G

and

later to give an isomorphism proving either that G

and H are isomorphic or

that G

and H are isomorphic. To keep Paul from cheating in the case that

and G

are not actually isomorphic, Victoria gets to decide later which

of the two isomorphisms Paul must reveal. These considerations lead to the

following interactive proof system:

• Paul randomly chooses i ∈{0, 1} and π ∈ S

, then he computes H :=

π(G

) and sends H to Victoria.

• Victoria randomly selects j ∈{0, 1} and sends j to Paul.

• Paul computes π



∈ S

and sends π



to Victoria.

• Victoria accepts if H = π



Victoria can complete her work in polynomial time. If G

and G

are

isomorphic, and G

= π

∗

), then Paul can get Victoria to accept the input

with certainty: If i = j, then Paul can choose π



= π;ifi = 1 and j =0,

then H = π(G

)andG

= π

∗

), so H = π ◦ π

∗

)andπ



= π ◦ π

∗

will

work; ﬁnally, if i = 0 and j =1,thenH = π(G

)andG

=(π

∗

)

−1

so H = π ◦ (π

∗

)

−1

), and π



= π ◦ (π

∗

)

−1

will work. If the two graphs

and G

are not isomorphic, Paul can still get Victoria to accept if i = j.

But if i = j,thenH and G

are not isomorphic and there is no π



that will

lead Victoria to accept. Since Prob(i = j)=1/2, the error-probability is 1/2,

and since the error is one-sided, we can reduce this to 1/4justaswedidin

Theorem 11.3.1.

In the conversation above, Victoria receives the triple (H, j, π



) as infor-

mation. In the case that G

and G

are isomorphic, H is a random graph that

is isomorphic to G

and G

, j is a random bit, and π



is a permutation such

that H = π



). Now let V



be an arbitrary polynomial-time randomized

algorithm that computes the bit j. Then we can describe the algorithm A

that simulates the communication as follows: