Multiprover interactive verification system

In a multiparty verification system, a prover and a verifier are coupled to rocess respective outputs to provide a system output such as an identification verification. The prover is formed of plural units which share confidential information used to encrypt information carried by the prover. Communication between the prover units is prevented. The first prover unit encrypts the information based on additional information received from the verifier and transfers the encrypted information to the verifier. Subsequently, the verifier obtains from the second prover unit the shared confidential information required to decrypt a subset of the transmitted encrypted information.

BACKGROUND OF THE INVENTION 
An identification scheme is a method by which a party A can prove to a 
party B that he is indeed A. In 1976 Diffie and Hellman (DH) introduced 
the idea of digital signatures. In 1978 Rivest, Shamir and Addleman (RSA) 
suggested an implementation of this idea based on the assumption that 
factoring large integers is a hard computational problem. However, there 
is no known proof that party B who is validating the identity of a using 
digital signatures cannot turn around falsely, and prove that he is A to a 
third party C, even under the assumption that factoring integers is a hard 
computational problem. Moreover, the cost of using the RSA digital 
signature scheme is about k modular multiplications each of cost k.sup.2 k 
digit numbers. The smallest value of k considered secure today is k =200. 
This makes using RSA for identification in software too slow, and in 
hardware and VLSI to expensive and special purpose. 
In 1985 Goldwasser, Micali and Rackoff (GMR) presented the idea of 
"Zero-Knowledge Interactive Proof-Systems" which are interactive 
procedures by which a party A (the prover) can convince a party B (the 
verifier) that a theorem is true without telling B anything else. One 
possible theorem would be that A knows how to perform a hard computation. 
If the ability to perform this computation identifies A, an interactive 
identification scheme immediately follows. 
In 1986 Goldreich, Micali and Wigderson (GMW) showed that if one-way 
functions exist then every language in nondeterministic polynomial time 
(NP) has a computationally zero-knowledge interactive proof system. 
Although theoretically quite exciting, using their result in practice 
would be very inefficient. 
In 1986 Shamir and Fiat (FS) suggested a particular zero-knowledge 
identification scheme based on the assumption that distinguishing 
quadratic residues from non-residues modulo composite integers is a hard 
problem. A number of modular multiplication of many-digit numbers are 
required. 
An example of a zero knowledge identification scheme based on the ideas of 
GMW and Blum is illustrated in FIG. 1. In that system, a prover A must 
prove its identification to a verifier B. The prover A may, for example, 
be a smart card having a processor thereon and the verifier B may be an 
automatic teller machine. Other forms of the prover A include credit 
cards, access control cards and digital passports. The prover A carries an 
identification set of information S.sub.i which is unique to prover A and 
which is also known to verifier B. Knowledge of that identification set of 
information, however, is not considered sufficient to identify prover A, 
because it is generally available at least to verifiers and an 
eavesdropper from a prior identification may also have that identification 
set. To prove its identity, prover A must prove that it also has access to 
a solution subset S.sub.s without actually disclosing that solution subset 
to either the verifier B or a potential eavesdropper. This result is 
accomplished by means of a zero knowledge system. 
The solution subset should have a predetermined mathematical relationship 
with the identification set and be readily verifiable as a proper 
solution, but it should not be readily determinable from the 
identification set. For example, as illustrated in FIG. 1B, the 
identification set could be the graph illustrated. The solution subset 
could be the listing of vertices which identify a Hamiltonian cycle; that 
is, a cycle such as shown in bold lines which intersects each vertex 
without overlap. The graph of FIG. 1B is very simple for purposes of 
illustration. With more complex graphs, a Hamiltonian cycle may be nearly 
impossible to determine from the full graph. On the other hand, by 
starting with a Hamiltonian cycle, one can develop a complex graph which 
includes the cycle so that prover A could be provided with both the 
complex graph as the identification set S.sub.i and the Hamiltonian cycle 
as the solution subset S.sub.s. The cycle and graph would be generated by 
the prover itself or by a trusted center. 
Given that prover A has access to both the identification set and the 
solution subset, and that the verifier B only has access to the 
identification set, the task remains for prover A to prove to the verifier 
B that it in fact has access to the solution set without actually reealing 
the solution set to verifier B. To that end, the prover has a permutator 
.pi., an encryptor E and a decryptor. Based on a random sequence, the 
vertices of the identification set graph can be permutated for successive 
message transmissions to the verifier. Thus, the permutated graph 
S.sub..pi.i shown in FIG. 1B is the initial identification graph with the 
vertices renumbered according to some random process. Prover A then 
encrypts the individual elements of the permutated identification set of 
information for transfer as S.sub.i.pi.E to the verifier B. Also, the 
permutation .pi. is encrypted for transfer to verifier B. As illustrated 
in FIG. 1C, this encryption is analagous to the placement of each vertex 
of the permutated identification set in a respective envelope for transfer 
to verifier B. Such a transfer is a commitment by prover A to the 
permutated graph as well as to the permutation which allows for 
reconstruction of the original graph S.sub.i ; however, the encryption 
"envelopes" cannot then be opened by the verifier B. 
Next, the verifier randomly selects, for each of successive encrypted 
permutated graphs, either the entire identification set or the solution 
subset. In response to that random selection, the prover A either opens 
all encryption envelopes or only those envelopes corresponding to the 
solution subset. If all envelopes are opened by transferring the original 
nonencrypted permutated identification set S.sub..pi.i and the 
nonencrypted permutation .pi., the verifier B can reconstruct S.sub.i and 
compare the reconstructed set to the already available identification set 
S.sub.i. This proves that A had in fact committed to a permutation of the 
identification set. As already noted, if this were the only test, there 
would be no verification because others might have access to that 
identification set. However, the verifier may at random select the 
solution subset. In that case, the prover A returns only the nonencrypted 
permutated vertices of the Hamiltonian cycle. For example, the Hamiltonian 
cycle illustrated in FIG. 1B would be returned to the verifier as follows: 
(1,2), (2,3), (7,3), (7,4), (4,5), (5,6) and (1,6). Because the 
information is permutated and the permutation .pi. is not in this case 
available to B, B cannot make a correspondence between the permutated 
Hamiltonian cycle and the original nonpermutated cycle S.sub.i and thus 
gain knowledge of the Hamiltonian cycle corresponding to S.sub.i. However, 
B could step through the vertices to confirm that the permutated vertices 
in fact create a cycle naming each of the seven vertices without overlap. 
For a full commitment by A, the prover A must encrypt the information in a 
manner which cannot readily be decrypted by the verifier or an 
eavesdropper; yet the encryption method must allow the verifier to readily 
confirm that, when provided with both the encrypted information and the 
nonencrypted information, one is the true encryption of the other. For 
example, in using for encryption the RSA function m.sup.3 mod n where m is 
the transferred message and n is a multidigit product of two primes, the 
verifier could not readily decrypt the information. However, with the 
nonencrypted information later provided with selection of all vertices and 
the permutation, the verifier could itself easily encrypt the information 
and compare it to the encrypted information to which the prover had 
already committed itself. 
Thus, because the prover A had committed to the full set of vertices, it 
must know both the identification set and the solution subset in order to 
be correct with either selection made by the verifier. For any one 
transfer of a permutated graph, the prover A could transfer either the 
proper graph with an incorrect solution or the proper solution with an 
incorrect graph. However, it could not transfer both a correct graph and a 
correct a cycle without access to the solution. With one transfer of the 
permutated graph, the verifier could only verify to fifty percent 
probability; however, with successive transfers of the permutation graph 
and random selections, the verifiction becomes more and more certain. If 
the prover does not have both the identification set and the solution set, 
the verifier would soon select an incorrect full graph or an incorrect 
cycle from the prover. 
Previous methods of commitment such as that just described are based on the 
assumption that one-way functions, such as the RSA function, exist. This 
assumption has not yet been proven. Further, the many modular 
multiplications of large digit numbers required for secure use of the RSA 
and other functions make those functions too slow for software and too 
expensive for hardware. Further, the approaches lose security when 
performed in parallel, that is, when multiple permutated graphs are 
transferred to the verifier in parallel. 
DISCLOSURE OF THE INVENTION 
An object of the present invention is to provide a verification system in 
which a computationally less complex encryption approach may be utilized. 
Complex one-way functions are not necessary where encryption is based on 
random (including pseudorandom) information, a so-called one-time-pad 
encryption scheme. Thus, in a system embodying the present invention the 
identification set may be encrypted utilizing random information generated 
at the prover. However, with such encryption, the verifier is no able to 
verify the decryption without the random information utilized in the 
encryption, and that can only be obtained from the prover. If the verifier 
then looked to the prover of FIG. 1A for that information, the prover 
would have the opportunity to provide false information depending on the 
verifier's selection. The false information would be other than that with 
which the identification set had been encrypted, and the prover could 
guarantee the appearance of a correct solution to the verifier if the 
verifier selected the permutated solution set. Thus the system would fail. 
In accordance with the present invention, to overcome the above 
shortcoming, the prover comprises first and second prover units which 
share confidential prover encryption information. The first prover 
initially encrypts the identification set with that information, and the 
second prover later provides to the verifier the prover encryption 
information required for decryption. To make the second prover unit 
ignorant of the actual information which had been transferred by the first 
prover unit, the encryption is also based on verifier encryption 
information received from the verifier, and communications between the two 
prover units during the verification are limited to prevent cheating. The 
verifier encryption information is held confidential from the second 
prover unit though it may be read by an eavesdropper. In providing the 
prover encryption information required for decryption, the second prover 
unit lacks the verifier encryption information required to fool the 
verifier by modifying the encryption information. Thus, in a method 
embodying the present invention, the first prover unit commits itself to 
encrypted identification information based on encryption information 
shared by the first and second prover units, and the second prover unit 
provides the information required for decryption. Preferably, the 
confidential verifier information and the confidential prover informaion 
on which the encryption is based on both random. 
In a more specific implementation of the present invention, after receipt 
of encrypted information, the verifier selects a subset of the encrypted 
information, such as the full identification set or a solution subset, for 
decryption. The encryption information provided to the verifier by the 
second prover unit corresponds to the selected subset of the encrypted 
information exclusively. Preferably, the selection information is chosen 
at random. 
Preferably, both the prover and verifier have access to an identification 
set of information, and the prover alone has access to the identity of a 
solution subset of the identification set, the solution subset having a 
predetermined mathematical relationship with the identification set. The 
solution subset is readily verifiable as a proper solution but not readily 
determinable from the identification set of information. In a plurality of 
cycles with respect to identification sets permutated by the first prover 
unit, transfers of encrypted information include each permutated 
identification set. The selection information selects information 
including the full identification set or the solution subset, exclusively. 
In one approach, the solution subset is a solution to the knapsack problem 
where the numbers of the solution subset sum to a target number. In a very 
specific implementation, encrypted permutated information based on the 
following is transferred by the first prover unit: 
A={v.sub.i, 1.ltoreq.i.ltoreq.n} where v.sub.i is chosen at random in 
##EQU1## 
B={w.sub.i, 1.ltoreq.i.ltoreq.n}, the identification set 
C={s.sub.i, 1.ltoreq.i.ltoreq.n} where s.sub.i =v.sub.i +w.sub.i for all 
1.ltoreq.i.ltoreq.n 
D=.SIGMA..sub.j.epsilon.J v.sub.j 
E=J, the solution subset 
F=T+.SIGMA..sub.j.epsilon.J v.sub.j, where T is the target 
The selection information selects (A,B,C), (A,D,E), or (C,E,F) with equal 
probability. 
In another approach, the prover and verifier both have access to a graph 
which serves as the identification set, and the prover alone has access to 
a Hamiltonian cycle within the graph which serves as the solution set. 
Both the knapsack problem and the Hamiltonian cycle problem are well-known 
hard problems which are hard to invert yet easy to initially compute. 
Their use is particularly advantageous in the present two-prover approach 
because they allow for a simple protocol between the prover and verifier. 
The knapsack problem is the most preferred due to the ease with which 
specific hard instances can be generated. 
The present invention is not restricted to identification schemes. The 
identification system is one example of a system in which two processors 
can together determine an output based on information available to only 
one of the processors and in which the one processor need not disclose its 
confidential information to assure the other processor of the validity of 
the output. More specifically, the Hamiltonian cycle and knapsack problem 
approaches described above are approaches in which one processor has 
access both to a function F(x) and the confidential informaton x and in 
which the second processor has access only to F(x), F(x) being a hard 
problem which is readily computed but which is difficult to invert. The 
successful identification, the output of the system, is based on x, and 
the second processor is assured of the validity of the identification, but 
the first processor need not disclose x to the second processor. 
Systems embodying the present invention may include more than two 
processors and more than two prover units per processor. Also, each 
processor may comprise plural units such that each processor may assume 
the roles of both prover and verifier. 
A system embodying the present invention has the advantage of requiring no 
unproven assumptions to assure a zero knowledge system. Further, the 
encryption can be performed with a simple addition and can thus be readily 
implemented in software or inexpensive hardware. Also, the system is fully 
parallelizable without any decrease in security properties.

PREFERRED EMBODIMENTS OF THE INVENTION 
As illustrated in FIG. 2, the single prover of the prior art is replaced by 
two prover units P1 and P2. In its simplest form, each prover unit would 
be a smart card which carries a microprocessor. However, the prover may be 
a single card having separate units mounted thereon in a manner which 
limits communications therebetween. During a verification, the verifier V 
must guarantee that there is no communication between the two prover units 
P1 and P2 in order to be convinced of the validity of the identification. 
Communication can be prevented by physical distance and active jamming of 
any communication channel between the two units. 
The dual prover units allow for a simplification of the commitment process 
for use in any one-way function identification technique such as that 
described above with respect to the Hamiltonian cycle. Prover P1 commits 
to the information by encrypting that information based on a confidential, 
preferably random, verifier encryption signal c from the verifier and its 
own confidential, preferably random, prover encryption signal r. Utilizing 
the random information r, the encryption can be computationally very 
simple. Subsequently, to open the encryption envelopes of the full set of 
transmitted information or a subset thereof selected by the random signal 
t, prove P2 transfers the prover encryption information required for 
decryption by the verifier. 
Say the message m to which P1 is to commit consists of 1 bit, i.e. 
m.epsilon.{(0,1}. Let P1 and P2 share a secret random tape of r.sub.i each 
of which was chosen a priori at random from {0,1,2}. Let .sigma..sub.0 
(r.sub.i) =r.sub.i and .sigma..sub.1 (0)=0,.sigma..sub.1 
(1)=2,.sigma..sub.1 (2)=1. To commit to ith bit m: 
1. V sends c chosen at random in {0,1} to P1. 
2. P1 sends .sigma..sub.c (r.sub.i)+m mod 3 to V. 
To reveal ith bit m to V: 
3. P2 sends r.sub.i to V. 
To commit to longer messages m, simply commit bit-by-bit. 
In the complete protocol, using the Hamiltonian cycle approach described in 
the background, the prover P1 generates successive permutations of the 
identification graph. Based on the random information c received from the 
verifier V, prover P1 selects either the function .sigma..sub.0 or 
.sigma..sub.1 for encryption. It then encrypts the permutated information 
using the function 
EQU .sigma..sub.c (r.sub.i)+m mod 3. 
That encrypted permutated information is transferred to the verifier as the 
prover's commitment. Next, the verifier randomly selects either the full 
graph or the Hamiltonian cycle with the signal t. Prover P2 operates in 
parallel with prover P1 and thus can generate the same random numbers r 
and identify the solution subset which in this case is the Hamiltonian 
cycle. P1 returns the requested prover encryption information r to the 
verifier. Where the full graph is requested, the encryption information 
required to decrypt the permutation is also returned. Because V is now 
able to perform the decryption itself, it can readily verify that the 
decrypted information corresponds to the originally committed encrypted 
information and can also confirm that the decrypted information is either 
the identification set S.sub.i or a permutated cycle which includes every 
vertex of the graph without overlap. Therefore verification is complete. 
A preferred hard problem which may be used as an alternative to the 
Hamiltonian cycle is the so-called knapsack problem. The knapsack problem 
is based on the assumption that, given a large set of large numbers, 
determination of a subset of numbers which sum to a target number is not 
possible. By starting with the subset, one can readily generate a larger 
set, both of which can be stored on the prover. However, given the larger 
set, determination of the subset is extremely difficult. 
We describe the automatic teller machine application. The trusted center 
(the bank in this case) issues a pair of cards for every customer A to be 
identified. One card P1 has an instance of the knapsack problem on it. 
Both cards P1 and P2 have a shared pool of random bits. The instance of 
knapsack problem is a tuple (w.sub.i, 1.ltoreq.i.ltoreq.n,T,JC{1, . . . , 
n}), such that .SIGMA..sub.j.epsilon.J w.sub.j =T. J is the solution 
subset. The bank stores a table having customer A's name along with 
(w.sub.i, 1.ltoreq.i .ltoreq.n,T), the identification set. 
When A comes to the bank machine, the two cards are inserted into the 
machine and the following protocol is executed. Steps 1-3 are executed in 
parallel k times where k is a security parameter. 
1. P1 permutes the w.sub.i 's at random and accordingly the set J. Now, P1 
commits to secrets A,B,C,D,E,F where 
A={v.sub.i, 1.ltoreq.i.ltoreq.n} where v.sub.i is chosen at random in 
##EQU2## 
B={w.sub.i, 1.ltoreq.i.ltoreq.n}, the identification set C={s.sub.i, 
1.ltoreq.i.ltoreq.n} where s.sub.i =v.sub.i +w.sub.i for all 
1.ltoreq.i.ltoreq.n 
D=.SIGMA..sub.j.epsilon.J v.sub.j 
E=J, the solution subset 
F=T+.SIGMA..sub.j.epsilon.J v.sub.j, where T is the target 
2. V sends to to P2 whre t.epsilon.{1,2,3} at random. 
3. If t=1, P2 reveals secrets A, B and C to V. 
If t=2, P2 reveals secrets A, D and E to V. 
If t=3, P2 reveals secrets C, E and F to V. 
4. If in every execution of the above protocol; when t=1, s.sub.i =v.sub.i 
+w.sub.i for all 1.ltoreq.i.ltoreq.n; when t=2, .SIGMA..sub.j.epsilon.E 
v.sub.i =D; and when t=3, .SIGMA..sub.j.epsilon.E s.sub.i =F, then Bank 
accepts customer A as valid. 
For all customers C other than A, the probability that C succeeds in 
convincing the Bank that he is A is less than or equal to (1/3).sup.k. 
Further discussion of the model on which the invention is based and proofs 
related thereto follows. 
1.1 New Model 
We extend the definition of an interactive proof for language L as follows: 
instead of one prover attempting to convince a verifier that x, the input 
string, is in L, our prover consists of two separate agents (or rather two 
provers) who jointly attempt to convince a verifier that x is in L. The 
two provers can cooperate and communicate between them to decide on a 
common optimal strategy before the interaction with the verifier starts. 
But, once they start to interact with the verifier, they can no longer 
send each other messages or see the messages exchanged between the 
verifier and the "other prover". As in [GMR] the verifier is probabilistic 
polynomial time, and can exchange upto a polynomial number of messages 
with either one of the two provers (with no restriction on interleaving 
the exchanged messages) before deciding to accept or reject string 
x..sup.1 
FNT .sup.1 A proof-system for a language in this model is defined in a similar 
manner to [GMR]. Namely, L has a multi-prover interactive proof-system if 
there exist a verifier V and provers P1, P2 such that when x .epsilon. L 
the probability that V accepts is greater than 2/3, and when x is not in L 
then for all P1, P2, the probability that V accepts is less than 1/3. 
We restrict the verifier to send messages to the prover in a predetrmined 
order. It can be shown that this is equivalent with respect to language 
recognition, to a model in which the verifier is free to talk to the 
provers in any order he wishes. Moreover, the verifier can be forced to 
send messages to the provers in a predetermined order by using a simple 
password scheme. Thus, we can work in the easier to deal with synchronous 
model completely without loss of generality. 
The main novelty of our model is that the verifier can "check" its 
interactions with the provers "against each other". One may thick of this 
as the process of checking the alibi of two suspects of a crime (who have 
worked long and hard to prepare a joint alibi), where the suspects are the 
provers and the verifier is the interrogator. The interrogators conviction 
that the alibi is valid, stems from his conviction that once the 
interrogation starts the suspects can not talk to each other as they are 
kept in separate rooms, and since they can not anticipate the randomized 
questions he may ask them, he can trust his findings (i.e receiving a 
correct proof of the proposition at hand). 
Applying this model in a cryptographic scenario, one may think of a bank 
customer holding two bank-cards rather than one, attempting to prove its 
identity to the bank machine. The machine makes sure that once the two 
cards are inserted they can no longer communicate with each other. In this 
scenario, the provers correspond to the two cards, and the verifier to to 
bank machine. 
1.2 Results 
1.2.1 Perfect Zero Knowledge Multi-Prover Interactive Proofs 
We show, that in our extended model all NP languages have a perfect 
zero-knowledge interactive proof-system, making no intractability 
assumptions. 
The protocol for NP languages proposed, requires the two provers to share 
either a polynomially long random pad or a function which they can compute 
but the polynomially bounded verifier can not. It is well known that such 
functions exist by counting arguments. Most of the burden of the proof 
lies on one predetermined prover. In fact, the "other" prover sole 
function is to periodically output segments of the random pad he shares 
with the "primary prover". The protocol is constant (two) round. 
Differently then in the case of the graph non-isomorphism and quadratic 
non-residousity proof-systems in [GMR], [GMW], parallel executions of the 
protocol remain perfect zero-knowledge. 
More generally, we show that any language which can be recognized in our 
extended model, can be recognized in perfect zero-knowledge making no 
intractability assumptions. 
Our construction does not assume that the verifier is polynomial time 
bounded. The assumption that there is no communication between the two 
provers while interacting with the verifier, must be made in order for the 
verifier to believe the validity of the proofs. It need not be made to 
show that the interaction is perfect zero-knowledge. 
1.3 Language Recognition Power of New Model 
It is interesting to consider what is the power of this new model solely 
with respect to language recognition. Clearly, NP IP which in turn is a 
subset of languages accepts by our extended model. We show that adding 
more provers than two, adds no more power to the model. 
We also show for every language possessing a two prover interactive proof 
there exists another two prover interactive proof which achieves 
completeness, i.e. the verifier will always accept strings which are in 
the language. 
Fortnow, Rompel and Sipser [FRS] have shown that two provers can accept any 
language in IP (one-prover model with polynomial number of rounds) using 
only a constant number of rounds. They also show that three provers can 
accept in a constant number of rounds all languages recognized by a multi 
prover model. 
Feige, Shamir and Tennenholtz [FST] look at a model they call the k-noisy 
oracle model, in which the verifier is interacting with k oracles all of 
which but one may be dishonest. Based on the assumption that one of the 
oracles is trusted, they show that P-space langauages can be recognized in 
a 2-noisy oracle model. 
1.4 Open Problem 
Whether the two-prover proof-system is actually more powerful with respect 
to language recognition than the original one-prover interactive 
proof-system of [GMR], [B], remains an open problem. 
Even the simplest case of two-round two-prover proof-system in which the 
verifier sends the result of his coin tosses first (some to prover 1 and 
some to prover 2), receives responses (from both provers) on the 
subsequent round, and then evaluates a polynomial time predicate to decide 
whether to accept or reject, is not known to lie in PSE. Hastad and 
Mansour [HM] show that resolving this question in the positive will imply 
that NP.noteq.poly(log)-SE. 
2. Definitions 
Definition 1 
Let P.sub.1, P.sub.2, . . . , P.sub.k be Turing machines which are 
computationally unbounded and V be a probabilistic polynomial time Turning 
machine. All machines have a read-only input tape, a work tape and a 
random tape. In addition, P.sub.1, P.sub.2, . . . , P.sub.i share an 
infinite read-only random tape of 0's and 1's. Every P.sub.i has one 
write-only communication tape on which it writes messages for V. V has k 
write-only communication tapes. On communication tape i, V writes messages 
to P.sub.i. We call (P.sub.1, P.sub.2, . . . , P.sub.k, V) a k-prover 
interactive protocol. 
Remark 1 
Fortnow, Rompel and Sipser [FRS] remark that the above can be modeled as a 
probabilistic polynomial time turning machine V and an oracle p such that 
queries to p are prefixed always by 1.ltoreq.i.ltoreq.k, corresponding to 
whether the query is directed to prover i. Each query contains the history 
of the communication thus far. 
We note that although this memoryless formulation is equivalent to the 
i-prover formulation with respect to language recognition, it is not 
equivalent when zero-knowledge is considered. In this latter case the 
provers must be able to check that the history is indeed what is claimed 
by the verifier, before answering the next query. Since the verifier is 
not untrusted, the provers can not be memoryless. 
Definition 2 
Let L {0,1}*, We say that L has a k-prover interactive proof-system (IPS) 
if there exists an interactive BPP machine V such that: 
1 P.sub.1, P.sub.2, . . . , P.sub.k such that (P.sub.1, P.sub.2, . . . , 
P.sub.k, V) is a k-prover interactive protocol and x.epsilon.L, prob (V 
accepts input x).gtoreq.1/2. 
1 P.sub.1, P.sub.2, . . . , P.sub.k such that (P.sub.1, P.sub.2, . . . , 
P.sub.k, V) is a k-prover interactive protocol, prob (V accepts input 
x).gtoreq.1/3. 
Remark 2 
if L has an k-prover interactive proof-system and condition (1) holds for a 
particular P.sub.1 P.sub.2, . . . , P.sub.k, then we say that (.sub.1, 
P.sub.2, P.sub.k, V) is a k-prover interactive proof-system for L. 
Remark 3 
if L has an two-prover interactive proof-system, then L has a two-prover 
interactive proof-systems (P.sub.1, P.sub.2, V) such that for x.epsilon.L, 
prob (V accepts x)=1. See Theorem 5. 
Remark 4 
For convenience, without loss of generality, we assume that every verifier 
V outputs his coin tosses at the end of his interaction with the Pi's. 
Definition 3 
Let IPk={L which have k-prover interactive proof-system}. 
The following definition of perfect zero-knowledge is identical to the 
Goldwasser-Micali-Rackoff [GMR] definition of perfect zero-knowledge in 
the 1-prover model. 
Definition 4 
Let (P.sub.1, P.sub.2, . . . , P.sub.i, V) be a k-prover interactive 
proof-system for L. Let View P.sub.1, P.sub.2, . . . , P.sub.k, V) (x) 
denote the verifier's view during the protocol (namely the sequence of 
messages exchanged between the verifier and the two provers including the 
last message of the verifier which contains his coin tosses--see remark 4 
above). This is a probability space taken over the coin tosses of V and 
the joint random tape of P.sub.1, P.sub.2, . . ., P.sub.k. We say that 
k-prover interactive protocol (P.sub.1, P.sub.2, . . . , P.sub.k, V) is 
perfect zero-knowledge for V if there exists a BPP machine M such that 
M(x)=View P.sbsb.1.sub.,P.sbsb.2.sub., . . . , V (x). We say that L has a 
k-prover perfect zero-knowledge proof-system if there exists provers 
P.sub.1, P.sub.2, . . . , P.sub.i such that for all BPP verifiers V, there 
exists a probabilistic Turning machine M such that for all x in L, 
M(x)=View.sub.P.sbsb.1.sub.,.sbsb.P.sub.2.sub., . . . , 
P.sbsb.k.sub.,.sub.V (x) and M(x) terminates in expected polynomial time. 
3. Statement of our Results 
Theorem 1 
Every L.epsilon.NP has a two-prover perfect zero-knowledge interactive 
proof-system. 
Proposition 1 
parallel executions of the perfect zero-knowledge interactive proof-system 
for NP remain perfect zero-knowledge. 
Theorem 2 
Every L.epsilon.IP.sub.2 has a perfect zero-knowledge interactive 
proof-system. 
Theorem 3 
Any two party oblivious function computation can be done in this model. 
Theorem 4 
For all k.gtoreq.2, if L.epsilon.IP.sub.k then L.epsilon.IP.sub.2. 
Theorem 5 
If L.epsilon.IP.sub.2 then P.sub.1, P.sub.2, V such that (.sub.1, P.sub.2, 
V) is a two-prover interactive proof-system for L and for all x 
.epsilon.L, Prob(V accepts x)=1. 
3. Key Ideas 
A general primitive used in complexity based cryptography (and in 
particular in the proof that NP is in zero-knowledge under the assumption 
that one-way functions exist) is the ability to encrypt a bit so that the 
decryption is unique. In our model, encryption is replaced by a commitment 
protocol to a bit such that the bit is equally likely to be 0 or 1 
(information theoretically), and yet the probability that a different bit 
can be decommited (i.e. revealed) is less than 1/2 (this fraction can then 
be made arbitrarily small using standard techniques). The idea is that one 
prover is used to commit the bit, and the other to reveal it. 
Another important primitive is that of oblivious circuit evaluation. This 
primitive allows two parties, A and B, possessing secrets i and j 
respectively, to compute some agred upon function f(i,j) in such a way 
that A learns nothing, and B learns only f(i,j). the original 
implementation of this protocol, due to Yao [Yao86a], requires the 
existence of trapdoor functions. In fact, oblivious circuit evaluation can 
not be implemented without cryptographic assumptions in the standard two 
party scenario. However, we show that oblivious circuit evaluation between 
verifier and 1 prover can be done without assumptions in the two-prover 
model. The proof relies on a result of [K] reducing oblivious circuit 
evaluation to a simpler protocol, known as 1-out-of-2 oblivious transfer, 
which was reduced by [C] to a still simpler protocol, known as oblivious 
transfer. This last protocol is implemented in the two-prover model. 
4 Proof of Theorem 1: How to Commit Bits 
We first show that every language in NP has a perfect zero-knowledge 
two-prover interactive proof-system. 
Theorem 1 
Every L in NP has a two-prover perfect zero-knowledge interactive 
proof-system 
Idea of Proof 
Let (P.sub.1, P.sub.2, V) denote a multi-prover protocol which receives as 
input the graph G=(V,E). Let P.sub.1 and P.sub.2 share an infinite random 
pad R such that R=r.sub.1 r.sub.2. . . where r.sub.i 
.epsilon.{0,1,2].sup.2. Let n=.vertline.V.vertline.. 
FNT .sup.2 Alternatively, R can be replaced by the outcome of f(x) where x is 
the input and f:{0,1}*-&gt;{0,1}* is a function such athat for all x 
.epsilon.{0,1}*, for all i&lt;.vertline.f(x).vertline., the i-th bit of f(x) 
is equally likely to be 0 or 1 with respect to any probabilistic 
polynomial time machine. Such functions can be shown to exist by standard 
diagonalization techniques over all probabilistic polynomial time 
machines. 
Let us quickly review.sup.2 one of the, by now standard proofs ([GMW1], 
[B1]) that NP is in zero-knowledge under the assumption that one-way 
functions exist. 
FNT .sup.3 the proof reviewed is from [B1[ 
Review 
The prover is attempting to convince the verifier that G is Hamiltonian. 
The prover publicizes an probabilistic encryption algorithm E (as in [GM], 
[Yao82a].sup.4) The prover and verifier repeat the following protocol n 
times: 
FNT .sup.4 The encryption algorithm E is public. We denote .gamma..epsilon.E(m) 
to mean that there exists string r such that algorithm E using r for his 
coin tosses, on input m, produces .gamma.. Given .gamma. there exists 
unique m, r such that E, on coin tosses r and input m outputs .gamma.. To 
decrypt .gamma. both m, r are revealed. 
STEP 1: prover randomly permutes the vertices of graph G (using permutation 
.pi.) to obtain graph G and sends to verifier 
.cndot. an n.times.n matrix .alpha.={a.sub.ij } where .alpha..sub.ij in 
E(b.sub.ij) and b.sub.ij =1 if edge ij is present in the G and 0 
otherwise. 
.cndot. .beta..epsilon.E(.pi.), i.e an encryption fo .pi.. 
STEP 2: verifier chooses at random coin .epsilon.{0,1}, and sends coin to 
the prover. 
STEP 3: If coin=1, prover decrypts .beta. and .alpha..sub.ij for all 
i,j.ltoreq.n and sends decryptions to verifier. If coin=0, prover decrypts 
those .alpha..sub.ij such that edge ij is in the Hamiltonian path in G. 
STEP 4: If prover is unable to preform step 3 correctly, verifier rejects. 
Otherwise, after n iterations of steps 1 through 4, verifier accept. 
End of Review 
Returning to the two prover model, prover P.sub.1 replaces the prover in 
step 1 of above protocol and prover P.sub.2 replaces the prover in step 2 
of above protocol. Algorithm E is no longer a probabilistic encryption 
algorithm based on the existence of one-way functions as in [GM] or 
]Yao86a], but rather a commitment algorithm computed as follows. 
Let .sigma..sub.0, .sigma..sub.1 : {0,1,2}-&gt;{0,1,2} be such that 
(1) for all i, .sigma..sub.o (i)=i, 
(2) .sigma..sub.1 (0)=0, .sigma..sub.1 (1)=2 and .sigma..sub.1 (2)=1. 
Let m.sub.k be the k-th bit to be committed to in the protocol. 
To commit m.sub.k : 
.cndot. V chooses at random c.sub.k .epsilon.{0,1} and sends c.sub.k to 
P.sub.1. 
.cndot. P.sub.1 sets E(c.sub.k, m.sub.k)=.sigma..sub.c.sbsp.k 
(r.sub.k)+m.sub.k mod 3, where r.sub.k .epsilon.{0,1,2} is read off the 
random tap P.sub.1 shares with P.sub.2, and sends E(c.sub.k, m.sub.k) to 
V. 
To reveal the k-th bit committed in the protocol, V and P.sub.2 engage in 
the following protocol. 
To reveal the k-th bit: 
.cndot. V sends k to P.sub.2. 
.cndot. P.sub.2 sends V the string r.sub.k. 
.cndot. V computes .sigma.c.sub.k (r.sub.k) and sets m.sub.k to (E(c.sub.k, 
m.sub.k)-.sigma.c.sub.k (r.sub.k)) mod 3. 
Note: P.sub.2 does not know c.sub.k and has never seen E(c.sub.k, m.sub.k). 
We prove two properties of the above pair of commit-reveal protocols. First 
since P.sub.2 sees neither E(c.sub.k, m.sub.k) nor c.sub.k, but knows 
exactly what P.sub.1 's program is, the probability that P.sub.2 
successfully reveals a bit value different than the one P.sub.1 committed 
to is less than 1/2. 
Claim 1.1 
r.epsilon.{0,1,2}, m.epsilon.{0,1}, 
EQU prob(r is s.t. E(c,r,m)=E(c,r,m)).ltoreq.1/2 
Comment 
To decrease the probability of successfuly cheating from 1/2 to 1/2.sup.n, 
P.sub.1 preform n commits to m.sub.k and P.sub.2 preforms n reveals 
correspondingly. Knowing k, E(c.sub.k, m.sub.k) and c.sub.k gives the 
verifier no advantage in guessing m.sub.k. 
Claim 1.2 
c .epsilon.{0,1}, 
EQU prob(m=0.vertline.E(c,r,m))=prob(m=1.vertline.E(c,r,m))=1/2 
Proving now that the altered multi-prover Hamiltonian cycle protocol 
constitutes a two-prover interactive proof for the Hamiltonian cycle 
problem follows directly from [B1]'s proof and claim 1. 
Proving that the protocol is perfect-zero-knowledge is more subtle. 
To this end, we exhibit a probabilistic Turing machine M such that 
.cndot. for Hamiltonian graphs G, M(G) terminates in expected polynomial 
time. 
.cndot. for all V such that (.sub.1, P.sub.2, V) is a two-prover protocol, 
and for all Hamiltonian graphs G, 
M(G)=View.sub.P.sbsb.1.sub.,.sub.P.sbsb.2.sub., .sub.V. (where P.sub.1, 
P.sub.2 are honest provers as specified above.) 
WLOG let the number of coin tosses of verifier and prover on input G=(V, E) 
where .vertline.V.vertline.=n be be bounded by polynomial Q(n). 
SIMULATOR M program: (tailored after steps 1-4 above in [B1]'s proof) 
STEP 1 
M chooses .rho..epsilon.{0,1}.sup.Q(n) at random for the coin tosses to be 
used by V. and sets R=r.sub.1 r.sub.2. . . r.sub.k. . . , 
.vertline.R.vertline..epsilon.{0,1}.sup.Q(n) where r.sub.k 
.epsilon.{0,1,2} are chosen at random. (V(.rho.,G) will denote the program 
V on input G and coin tosses .rho..) M picks a random permutation .pi. of 
the vertices of graph G to obtain the permuted graph G and an n.times.n 
random binary matrix MAT. Next, M simulates a commitment protocol to .pi. 
and MAT as follows. To simulate a commitment protocol to the k-th bit m: M 
runs V(.rho., G) to obtain c, computes E(c,m)=.rho..sub.ck (r.sub.k)+m mod 
3 for r.sub.k .epsilon.R, and writes E(c,m) on V(.rho.,G)'s tape. 
STEP 2 
M continues running V(.rho.,G) to obtain coin. 
STEP 3 
if coin=1, M reveals .pi. (as P.sub.2 would do in real protocol) by writing 
the appropriate r .epsilon.R on V(.rho.,G)'s) tape. Revealing MAT to V is 
more involved, as follows. Let MAT={m.sub.ij 
.vertline.1.ltoreq.i,j.ltoreq.n} and .alpha.=E(c,m.sub.ij)=.rho..sub.c 
(r)+m.sub.ij mod 3 where r .epsilon.R is the r used in step 1 to commit 
m.sub.ij. Let r be such that .alpha.=.rho..sub.c (r)+m.sub.ij mod 3. Note 
that such r always exists and since M knows c (differently from P.sub.2 in 
the real protocol) M can compute it. Set 
##EQU3## 
Then M reveals r to V(.rho.,G). 
If coin=0, M selects n ij entries at random in MAT such that no two entries 
are in the same column or in the same row. Set 
##EQU4## 
Where again r .epsilon. R from step 1 such that 
.alpha.=E(c,m.sub.ij)=.rho..sub.c (r)+m.sub.ij mod 3, and r is such that 
.alpha..sub.ij =.rho..sub.c (r)+m.sub.ij mod 3. Next, M reveals r to 
V(.rho.,G). Finally, M sets R to be R with the values of r substituted for 
r used to commit the matrix MAT. 
STEP 4 
M runs V to either accept or reject. It then outputs the transcript of its 
exchanges with V followed by R. DONE 
It is clear that, M on G operates in polynomial time in the running time of 
V. Since V is assumed to be probabilistic polynomial time, so is M. 
To show that the probability space generated by m is identical to that in 
View.sub.(P.sbsb.1.sub., P.sbsb.2.sub.,.sbsb.V), we notice that for fixed 
.rho. (coin tosses of the verifier) and fixed R (joint random tape of 
P.sub.1 and P.sub.2) the output of M(G) is identical to 
View.sub.(P.sbsb.1.sub.,P.sbsb.2.sub.,.sbsb.V). This is so as M actually 
runs V to obtain his moves and therefore V's moves are guaranteed to be 
perfectly simulated, while M itself follows the moves P.sub.1, P.sub.2 
would have made on joint random tape R. since .rho. was picked by M at 
random at step 1, it remains to argue that the probability that R was 
chosen by P.sub.1 and P.sub.2 is the same as the probability that R was 
output by M. This is trivially true by claim 1.2. 
We claim, without proof here, that independent executions of the above 
protocol for any language L.epsilon.NP can be performed in parallel and 
the resulting protocol will still be a 2-prover perfect zero-knowledge 
proof-system for L. 
In the 1-prover model the question of whether it is possible in general to 
preform parallel executions of perfect zero-knowledge protocols 
maintaining perfect zero-knowledge is unresolved. In particular, it is not 
known how to parallelize the proof-systems for quadratic residuosity and 
graph isomorphism. 
5 Proof of Theorem 4: IP.sub.i =IP.sub.2 for all k.gtoreq.2 
We now show that any k-prover (P.sub.1, . . . , P.sub.k, V) interactive 
proof-system for language L can be converted into a 2-prover (P.sub.1, 
P.sub.2, V) interactive proof-system. The idea is as follows. 
Verifier V tosses all his coins and sends them to prover P.sub.1. In 
return, P.sub.1 sends V the entire history of communication that would 
have occured for theses coin tosses between the real verifier V and the k 
real provers P.sub.i 's. If this is an accepting conversation for V, V now 
uses P.sub.2 to check the validity of the conversation. This is done by V 
selecting at random an original prover P.sub.i, and simulating with 
P.sub.2 the conversation between V and P.sub.i on these coin tosses. If 
the conversation does not match the conversation sent by P.sub.1 then V 
rejects, otherwise the protocol is repeated k times (in series) and 
finally V accepts. 
Note that the number of rounds in the simulating protocol is k.sup.2 t, 
where t is the number of rounds in the k-prover interactive proof-system. 
Fortnow, Rompel and Sipser in [FRS] show that for each L.epsilon.IP.sub.2, 
there exists a 3-prover IPS for L with only a constant number of rounds. 
Theorem 5 
Let k.gtoreq.2. If L.epsilon.IP.sub.k then L.epsilon.IP.sub.2. 
proof 
Let L have a k-prover interactive proof-system (P.sub.1, . . . , P.sub.k, 
V). Let I.sub.k ={1,2, . . . k, $} and r denote the coin tosses made by 
the verifier. For a w.epsilon.L, the optimal provers P.sub.1, . . . , 
P.sub.k and the verifier V can be though of as deterministic functions 
P.sub.i : .SIGMA.*.fwdarw..SIGMA.* and V: .SIGMA.*.times.I.sub.k 
.times..SIGMA.*.orgate. {accept, reject} such that yi.sup.i =P.sub.i 
(h.sub.j-1 #x.sub.j.sup.i) denotes the j-th message of the i-th prover to 
the verifier, x.sub.j.sup.3 =V(r,i,h.sub.j-1.sup.1, . . . , 
h.sub.j-1.sup.k) denotes the j-th message of the verifier to the i-th 
prover, and h.sub.j.sup.i =#x.sub.1.sup.i #y.sub.1.sup.i #. . . 
#x.sub.j.sup.i #y.sub.j.sup.i denotes the history of communication as 
prover i sees it at round j. Let t the total number of rounds, then 
V(r,$,h.sub.t.sup.1, . . . , h.sub.t.sup.k).epsilon.{accept, reject}. Let 
Q be a polynomial such that .vertline.r.vertline., x.sub.j.sup.i 
.vertline., .vertline.y.sub.j.sup.i .vertline.&lt;Q.vertline.w.vertline.). 
We now define provers P.sub.1 and P.sub.2 and verifier V in the simulating 
two-prover protocol P.sub.1, P.sub.2, V. 
On input w, 
STEP 1 
V chooses r.epsilon.{0,1}.sup.Q(.vertline.w.vertline.) at ramdom, sends r 
to P.sub.1. 
STEP 2 
P.sub.1 sends h.sub.1.sup.1, . . . , h.sub.t.sup.k to V where the 
h.sub.t.sup.i' S are computed according to functions P.sub.1, . . . , 
P.sub.k and V. If (V(r,$,h.sub.t.sup.1, . . . , h.sub.t.sup.k)=reject then 
V rejects and halts. Otherwise V picks 1.ltoreq.i.ltoreq.k at random, sets 
j=1 and continues. 
STEP 3 
V sends u.sub.j.sup.i =V(r,i,h.sub.j-1.sup.i) to P.sub.2, where 
h.sub.j.sup.i =#u.sub.1.sup.i #v.sub.1.sup.i #. . . #u.sub.j.sup.i 
#v.sub.j.sup.i for j.ltoreq.t. if j=t and h.sub.t.sup.i =h.sub.t.sup.i 
then V accepts and halts, otherwise V rejects and halts. 
STEP 4 
P.sub.2 sends v.sub.j.sup.i =P.sub.i (h.sub.j-1.sup.i #u.sub.j.sup.i) to V. 
Set j=j+1 and GOTO 
claim 5.1 
w.epsilon.L, 
EQU prob(V accepts w)=prob(V accepts w) 
proof 
If P.sub.i follow the protocol as described above and compute the 
h.sub.t.sup.i according to the functions of the corresponding P.sub.i 's, 
then for every sequence of coin tosses r on which V would accept so would 
V. 
Claim 5.2 
If w L, prob(V accepts w).ltoreq.(prob(V accepts w)+e.sup.-k. 
proof: sume w L. Then, the prob(V accepts w).ltoreq.prob(V accepts 
w.vertline. i.ltoreq.k j.ltoreq.t, y.sub.j.sup.i =P.sub.i (h.sub.j.sup.i 
-1))+prob(V accepts w l, j s.t., y.sub.j.sup.l .noteq.P.sub.l 
(h.sub.j.sup.l -1)).ltoreq.prob(V accepts w)+ prob(V(r,$,h.sub.t.sup.1, . 
. . , h.sub.t.sup.k)=accept, and l.ltoreq.k, s.t. h.sub.t.sup.1 
.noteq.h.sub.t.sup.l, but i of step 4 is s.t. h.sub.t.sup.i 
=h.sub.t.sup.i).ltoreq.prob(V accepts w)+(1-k/l). 
If the above protocol is repeated k.sup.2 independent times, the 
probability of success is reduced to prob(V accepts w)+(1-k/l)k.sup.2 
.ltoreq.prob(V accepts w)+e.sup.-k. 
This completes the proof, and L is indeed in IP.sub.2. 
6 Proof of Theorem 5: Completeness 
Goldreich, Mansour and Sisper [GMS] showed that any L.epsilon.IP has an 
interactive proof-system for which strings in L are always accepted. We 
show the corresponding property for any L.epsilon.IP.sub.2. 
Theorem 6: 
If L.epsilon.IP.sub.2, then there exists a 2-prover proof-system (P.sub.1, 
P.sub.2, V) for L such that for all x .epsilon.L, prob(V accepts)=1. 
proof 
Suppose (P.sub.1, P.sub.2, V) is a 2-prover interactive proof-system for L 
such that .epsilon.=prob(V accepts .vertline.w not in L} and the number of 
coin tosses on input w which V makes is a polynominal 
Q(.vertline.w.vertline.). We show a simulating 2-prover interactive 
proof-system (P.sub.1, P.sub.2, V) for L which also achieves completeness. 
The simulation is done in two stages. In stage 1, we use the idea of the 
completeness proof for the 1-prover interactive proof-system model by 
Goldreich, Mansour and Sisper in [MGS] (based on Lautman's Lemma) where 
P.sub.1 plays the part of both P.sub.1 and P.sub.2. In stage 2, as in the 
proof of the theorem of section 6, V uses P.sub.2 to check the validity of 
stage 1. 
Let t denote the number of rounds in (P.sub.1, P.sub.2, V). Again, consider 
P.sub.1, P.sub.2 and V as determinstic functions as in the proof of 
theorem of section 6. 
Let r denote the coin tosses of the verifier. For i=1, 2, let h.sub.t.sup.i 
(r)=#x.sub.1.sup.i #y.sub.1.sup.i # . . . #x.sub.t.sup.i #y.sub.t.sup.i 
where x.sub.j.sup.i =V(r, i, h.sub.j-1.sup.i (r)), and y.sub.j.sup.i 
=P.sub.i (h.sub.j-1.sup.i (r)#x.sub.j.sup.i). 
Define W={r.vertline.V(r, $, h.sub.t.sup.1, h.sub.t.sup.2)=accept}. Note 
that for w.epsilon.L, 
##EQU5## 
and for w not in 
##EQU6## 
Lautman[L] shows that w.epsilon.L s.sub.1, . . . , 
s.sub.Q(.vertline..chi..vertline.), .vertline.s.sub.i 
.vertline.=Q(.vertline..chi..vertline.), s.sub.i 
.vertline.=Q(.vertline..chi..vertline.), s.t. r, 
.vertline.r.vertline.=Q(.vertline..chi..vertline.), l s.t. r .sym.s.sub.1 
.epsilon.W. We use this in a manner similar to [GMS]. On input w, 
STEP 1 
P.sub.1 sends V s.sub.1, . . . , s.sub.Q(.vertline.w.vertline.) such that 
s.sub.i .epsilon.{0, 1}.sup.Q(.vertline.w.vertline.); 
STEP 2 
V sends r to P.sub.1 where r is randomly selected in {0, 
1}.sup.Q(.vertline.w.vertline.). 
STEP 3 
P.sub.1 sends to V, h.sub.t.sup.i (s.sub.j .sym.r) for i=1, 2 and 
1.ltoreq.j.ltoreq.Q(.vertline.w.vertline.). (These are the histories of 
conversations which would have been exchanged in original protocol 
(P.sub.1, P.sub.2, V) on coin tosses r.sym.s.sub.j, 
1.ltoreq.j.ltoreq.Q(.vertline.w.vertline.).) 
STEP 4: 
if V(r.sym.s.sub.j, h.sub.t.sup.1 (r.sym.s.sub.j), h.sub.t.sup.2 
(r.sym.s.sub.j))=reject for all 1.ltoreq.j.ltoreq.k, then V rejects. If l 
s.t. V(r.sym.s.sub.l, h.sub.t.sup.1 (r.sym.s.sub.l), h.sub.t.sup.2 
(r.sym.s.sub.l))=accept, then goto STEP 5. 
STEP 5 
V chooses i.epsilon.{1, 2} at random. It then interacts with prover P.sub.2 
in the same way that V and P.sub.i would have on coin tosses 
r.sym.s.sub.l. If this interaction produces exactly the same history 
string h.sub.t.sup.i (r.sym.s.sub.l) sent by P.sub.1 in STEP 3 then V 
accepts, otherwise it rejects. 
The above protocol is repeated Q(.vertline.w.vertline.)s times, and the 
verifier accepts if and only if he accepted in any of these iterations. 
Claim 1 
prob(V accepts .vertline.w.vertline..epsilon.L)=1 
proof 
if P.sub.1, and P.sub.2 follow the program outlined above, follows directly 
from [L] and [GMS]. 
Claim 2 
prob(V accepts .vertline.w.vertline. not in L).ltoreq.1/3 
proof 
We now can not assume that P.sub.1, P.sub.2 follow the procotol. Let 
h.sub.ij, for i=1, 2, 1.ltoreq.j.ltoreq.Q(.vertline.w.vertline.) denote 
the strings sent by P.sub.1 in STEP 3. 
prob(V accepts in one iteration .vertline.w L).ltoreq..SIGMA..sub.l prob(l, 
V(r.sym.s.sub.l, h.sub.1l, h.sub.2l)=accept.vertline.P.sub.1, P.sub.2 
honest)+prob(P.sub.1, P.sub.2 not caught in step 5 but j, i, 
h.sub.t.sup.i 
(r.sym.s.sub.j).noteq.h.sub.ij).ltoreq.Q(.vertline.w.vertline.). 
##EQU7## 
Now, prob(V accepts in Q(.vertline.w.vertline.).sup.3 iterations 
.vertline.w L)= 
##EQU8## 
which is less than a 1/3 for .epsilon. sufficiently small. QED 
7 Proof of Theorem 2: Outline 
Overview 
The proof of Theorem 2 is very long and complicated. The main idea of the 
proof is the implementation of a technique we call encrypted 
conversations. This is a general technique for transforming proof systems 
into zero-knowledge proof systems. A protocol that has been transformed 
using this technique closely mirrors the original protocol. Indeed, all 
the questions and answers of the transformed protocol can be mapped to 
questions and answers in the original protocol. However, these questions 
and answers are all strongly encrypted, in an information theoretic sense, 
using keys that are known by the provers, but not by the verifier. Because 
the conversation is so strongly encrypted, the verifier gets no 
information, so the protocol is zero-knowledge. 
Two concerns such a transformation must deal with are 
.cndot. How can the verifier, who in a strong sense knows little of what 
has happened in an encrypted conversation, be convinced that the 
conversation indeed mirrors a valid conversation from the original 
protocol? Also, how can the verifier be convinced that the unencrypted 
conversation would indeed have caused the original verifier to accept? 
.cndot. How can one insure that a malicious verifier cannot subvert the 
encrypted protocol in order to acquire information in some way? 
We deal with the first concern by showing how the provers and verifier can 
take an encrypted transcript of the first i rounds of a conversation, and 
compute an encrypted transcript of the first i+1 rounds of a conversation. 
This is done in such a way that the verifier can verify with high 
probability that this is the case. We dealwith the second concern by 
insuring that the encrypted conversation, if generated at all, will mirror 
a conversation between the prover and an honest verifier. Thus, if the 
verifier follows the simulation, he will only find out whether the 
original verifier, on a random set of coin tosses, accepted. Since the 
original verifier accepts with probability 1, this is no information. 
Furthermore, we guarantee that if the verifier does not go along with the 
simulation, he will not get any information. 
In order to accomplish these goals, we use a very useful tool called 
oblivious circuit computation. This tool, first developed by Yao [Yao86a], 
is a protocol by which two parties, A and B, possess secrets i and j 
respectively, and have agreed upon some circuit f. At the end of the 
protocol, A learns nothing about j, and B learns f(i, j), but nothing more 
about i than can be inferred from knowing j and f(i, j). The provers and 
verifier can compute the next step of an encrypted conversation by 
obliviously evaluating a circuit. We sketch the reduction from encrypted 
conversations to oblivious circuit evaluation in appendix A.3. 
A large portion of our construction is devoted to implementing oblivious 
circuit evaluation. Yao's implementation of this protocol relies on 
complexity theoretic assumptions, and is therefore unsuitable for our 
purposes. More recently, however, this protocol was implemented using a 
subprotocol known as oblivious transfer in lieu of any cryptographic 
assumptions [K]. In the standard, two-party scenario, oblivious transfer 
cannot be implemented without complexity theoretic assumptions. However, 
we show that oblivious transfer can be implemented in the two-prover 
scenario without recourse to these assumptions. Our implementations uses a 
result of Barringtion [Ba] that NC.sup.1 languages can be accepted by 
bounded width branching programs. We sketch our implementation in appendix 
A.2. 
A Structure of the Transformed Protocol 
Given a 2-prover IPS, we transform it into a zero-knowledge 2-prover IPS 
that has three distinct phases. These stages will be referred to as the 
commital phase, the oblivious transfer phase, and the encrypted 
conversation phase. In the commital phase of the protocol, the two provers 
commit a set of bits to the verifier. In the oblivious transfer phase of 
the protocol, the provers and verifier create a random sequence O of 
oblivious transfer bits. Sequence O has the following three properties. 
.cndot. All of the bits of O are known to the provers. 
.cndot. Each bit in O is known to the verifier with probability 1/2. 
.cndot. Neither prover knows which bits in O the verifier knows. 
The third and final stage actually simulates the original 2 prover IPS. In 
this stage, sequence O is used to perform oblivious circuit computation, 
which then allows the use of the encrypted conversation technique. We now 
describe the three phases in greater detail. 
A.1 The Commital Phase. 
It is necessary for the two provers to be able to commit bits for use in 
the second, oblivious transfer phase of the protocol. This commital is of 
the same type as in the proof that any language in NP has a zero-knowledge 
2-prover IPS. We use the same commital protocol as is used in Section 5. 
The bits committed to in the commital phase may be random. In order to 
commit a bit b in the oblivious transfer phase, a prover can tell the 
verifier the value of b.sym.b.sub.c, where b.sub.c is a bit committed to 
in the commital phase. To decommit b, the prover can then simply decommit 
b.sub.c. 
A.2 The Oblivious Transfer Phase. 
The oblivious transfer phase of the zero-knowledge IPS consists of several 
parallel evaluations of the oblivious transfer protocol, described below. 
Introduction to Oblivious Transfer 
We can view oblivious transfer as a protocol between two parties, A and B. 
Initially, A knows some random bit b, which is unknown to B. At the end of 
the protocol, the following two conditions hold. 
1. (The Transfer Condition) One of the following two events has occured, 
each with probability 1/2. Either B learns the value of b, or B learns 
nothing. Player B knows which of the two events occurred. 
2. (The Obliviousness Condition) Player A receives no information about 
whether or not B learned the value of b. 
Oblivious transfer, first introduced by Rabin[R], is a powerful 
cryptographic primitive. Its applications include contract signing [EGL] 
and oblivious circuit evaluation ([Y], [GMW2], [GHY], [AF], [GV], [K]). 
The first implementation of oblivious transfer by Rabin [R] was based on 
the difficulty of factoring and only worked for honest parties, Fischer, 
Micali, and Rackoff[FMR] presented the first implementation based on 
factoring and robust against computationally bounded adversaries. 
Even-Goldreich-Lempel[EGL] reduced the intractibility assumption to the 
existence of trap-door permutations. 
Unfortunately, these reductions are all cryptographic in nature, and thus 
of no use to us. Our implementation, which is not based on any 
cryptographic assumptions, exploits the lack of direct communication 
between the two provers. 
A Variant of Oblivious Transfer in the 2-Prover Model. 
We implement an analog to oblivious transfer in the two-prover model. At 
the beginning of the protocol, the provers know(have chosen) some random 
bit b, which the verifier does not know. The provers and the verifier have 
also agreed on a security parameter K. At the end of the protocol, the 
following variants of the usual transfer and obliviousness conditions 
hold. 
1. (The Transfer Condition) One of the following events occurs with 
probability 1/2. Either the verifier ffully learns the value of b (i.e. 
can predict b with probability 1), or the verifier gains only partial 
knowledge of b (i.e. can predict b with probability 3/4). The verifier 
knows which of the two events occurred. 
2. (The Obliviousness Condition) Let K denote the security parameters. For 
all c&gt;0, and for K sufficiently large, if the two provers communicate less 
than K bits of information, they cannot predict, with probability 
1/2+1/K.sup.c, whether the verifier fully learned b. 
Our implementation of this oblivious transfer protocol requires a constant 
number of rounds. The total number of bits of communication between the 
provers and the verifier will by polynominal in K and the size of the 
input. 
Both the transfer and the obliviousness conditions are relaxed versions of 
the standard ones. The transfer condition is relaxed purely for ease of 
implementation. Using the techniques of Crepeau-Kilian[CK], we can show 
that achieving this weakened transfer condition is equivalent to achieving 
the ideal transfer condition. The standard obliviousness condition, 
however, cannot be implemented in this model if the two pprovers are 
allowed to freely communicate. To get around this difficulty, we show that 
for interactive proof systems, a set of bits transferred under the 
nonideal obliviousness condition may be used in place of a set of bits 
transferred under the ideal obliviousness condition. 
Branching programs 
The main idea behind the oblivious transfer protocol is a simulation of 
width 5 permutation branching programs(W5PBP), as defined in [B]. Before 
describing the protocol, we first present a slightly nonstandard way to 
specify a W5PBP. We then show a way of randomizing this specification. 
Using this randomized representation, we can then describe our oblivious 
ransfer protocol. 
W5PBP's may be formally thought of as having some polynominal p(n) levels, 
each with five nodes. On level 1 there is a distinguished start node s; on 
level p(n) there is a distinguished accept node a. For each level, i, 
1.ltoreq.i&lt;p(n), there is an input variable, which we denote by v.sub.i, 
and two 1--1 mappings, f.sub.0.sup.i and f.sub.1.sup.i that map the nodes 
at level i to the nodes at level i+1. Intuitively, the mapping 
f.sub.0.sup.i tells where to go if the input variable v.sub.i is 0, and 
f.sub.1.sup.i tells where to go if v.sub.i, is equal to 1. A branching 
program may be evaluated by on a set of inputs by computing 
##EQU9## 
If this value if equal to the accept node a, the branching program 
accepts, otherwise, it is rejects. An example of a program is in FIG. 1. 
As described above, our branching programs consist of variables, nodes, and 
functions from nodes to nodes. For our protocol, we need an alternate 
representation for branching programs. Given a W5PBP, we first pick a 
random mapping .gamma., that maps nodes to {1, . . . , 5}, subject to the 
constraint that no two nodes on the same level are mapped to the same 
number. We then replace each function f.sub.k.sup.i, k.epsilon.{0, 1}, by 
a permutation h.sub.k.sup.i, subject to the constraint 
EQU h.sub.k.sup.i (.gamma.(N))=.gamma.(f.sub.k.sup.i (N)), (A.2.1) 
for all nodes N on level i. From equations (A.2.1) and (A.2.2) we have 
##EQU10## 
This isomorphism between evaluating the permutations h.sub.k.sup.i on 
.gamma.(s) and evaluating the original branching program proves very 
useful in implementing oblivious transfer, as we will show in the next 
section. The following simple lemma is useful in analyzing the information 
transferred by the oblivious transfer protocol we will present. 
Lemma A.1 
Suppose that for each level, i, of a branching program, exactly one of the 
functions h.sub.0.sup.i or h.sub.1.sup.i is specified. Suppose also that 
for some level j, .gamma.(N) is specified for all nodes N on level j. Then 
there is exactly one way of consistently defining .gamma. and the 
functions h.sub.k.sup.i. 
Proof Outline 
First, we note that specifying .gamma. specifies all the h's. Thus we need 
only show that there is exactly one way of consistently defining .gamma.. 
By equation A.2.2, we have 
EQU .gamma.(N)=h.sub.k.sup.i-1 (.gamma.(f.sub.k.sup.i (N))), and (A.2.4) 
EQU .gamma.(N)=h.sub.k.sup.i (.gamma.(f.sub.k.sup.i-1 (N))). (A.2.5) 
If .gamma. is defined on level i, equation(A.2.4) uniquely extends it to 
level i-1, and equation (A.2.5) uniquely extends it to level i+1. 
Inductively, one can uniquely extend .gamma. from row j to the entire 
branching program. This extension is easily shown to be consistent. 
The oblivious transfer protocol 
We now outline the oblivious transfer protocol between the two provers and 
the verifier. For the exposition, we assume that the provers follow the 
protocol. It is not hard to convert this protocol to one that works with 
adversarial provers. 
Stage 1 
Let n=K.sup.2. Both provers initially start with some canonical W5PBP that, 
given two vectors x=[x.sub.1 x.sub.2 . . . x.sub.n ] and y=[y.sub.1 
y.sub.2 . . . y.sub.n ], accepts iff x.y=1. They then agree on a random 
mapping .gamma., and permutations h.sub.k.sup.i. The provers send the 
verifier the exclusive-or of b and the least significant bit of 
.gamma.(a). 
Stage 2 
The verifier and Prover 1 pick a random vector x. The verifier and Prover 2 
pick a random vector y. As a subprotocol, the prover and verifier flip an 
unbiased coin in the following manner: Prover i chooses as his bit, 
r.sub.p, one of the bits committed in the commital phase of the protocol. 
The verifier chooses a bit r.sub.v at random, and announces it to Prover 
i. Prover i then decommits r.sub.p. The bit r, defined by r=r.sub.p 
.sym.r.sub.v will be unbiased if either Prover i or the verifier obeys the 
protocol. 
Stage 3 
Prover 1 sends the verifier the permutations h.sub.v.sup.i, for all i such 
that v.sub.i =x.sub.j for some j. Likewise, Prover 2 sends the verifier 
the permutations h.sub.v.sup.i, for all i such that v.sub.i =y.sub.i for 
some j. For example, if v.sub.i =y.sub.7, and y.sub.7 =0, then Prover 2 
would send the verifier h.sub.0.sup.i, but not send him h.sub.1.sup.i. 
We now show how to convert this protocol to one in which the provers may be 
adversarial. First, we require that the provers commit their .gamma. and 
their permutations h.sub.0.sup.i and h.sub.1.sup.i at Stage 1 of the 
oblivious transfer protocol, using the commital protocol described in 
section 1. The verifier must be assured that the following two conditions 
are met. 
1. The permutations it receives correspond to those that have been 
committed, and 
2. The permutations and .gamma. correspond to a legitimate randomized 
branching program. 
The first condition is assured by having the provers decommit their 
permutations in Stage 3 of the protocol. To assure that the second 
condition is met, we have the verifier perform a "spot-check" with 
probability 1/n.sup.c, where n is the size of the input, and c is some 
positive constant. To perform a spot-check, the verifier halts the 
oblivious transfer protocol at the beginning of Stage 2. Instead of using 
the committed W5PBP to implement oblivious transfer, the verifier requests 
that .dwnarw. and all the hash functions are revealed. The verifier can 
then check whether or not the two provers gave a legitimate randomized 
W5PBP, and reject if they did not. Note that it is only necessary for the 
verifier to be able to detect cheating by the provers some polynominal 
fraction ofthe time. This probability may be amplified by successively 
running the zero-knowledge proof system sufficiently many times. 
Properties of the Oblivious Transfer Protocol 
The following theorems state that the above protocol does indeed implement 
out variant of oblivious transfer. 
Theorem 
(Transfer) After the above protocol has been executed, one of the following 
two events may occur, each with probability 1/2. 
(1) The verifier knows the value of b. 
(2) The verifier can guess the value of b with probability at most 3/4. 
Furthermore, the verifier can tell which event occurred. 
Proof Outline 
Suppose, that x.multidot.y=1. Then the verifier can compute .gamma.(a), and 
thus compute b. This corresponds to event (1). Now suppose that 
x.multidot.y.noteq.1. The verifier knows, for each level i, exactly one of 
the functions h.sub.0.sup.i or h.sub.1.sup.i. The verifier can also 
compute .gamma.(a'), where a' is also on the last level, and a'.noteq.a. 
Everything else the verifier knows can be computed from this information. 
Using Lemma 1, we have that any specification of .gamma. on the top level 
nodes can be consistently extended in exactly one way. Thus, the verifier 
has no information about .gamma.(a) other than the fact that 
.gamma.(a).noteq..gamma.(a'). The verifier's predictive ability is 
maximized when .gamma.(a') is even, in which case the conditional 
probability that .gamma.(a) is odd is 3/4. In this situation, the verifier 
can predict b with probability 3/4. 
Theorem 
(Obliviousness) Let c be a constant, c&lt;0, and K, the security parameter, be 
sufficiently large (possibly depending on c). If, after the above protocol 
has been executed, the two provers exchange only K bits of information, 
they cannot predict, with probability 1/2+1/K.sup.c, whether the verifier 
received the bit. 
Proof Outline 
We again use the observation that the verifier receives a bit iff the dot 
product of the two randomly chosen vectors is equal to 1. Determining if 
the verifier received the bit is equivalent to computing the dot product 
of two random vectors of size n. We now cite a theorem of Chor and 
Goldreich [CG] concerning the communication complexity of computing dot 
products. 
Theorem[CG] 
Let players A and B each receive random n bit boolean vectors, x and y 
respectively. If they exchange o(n) bits, they cannot predict x.multidot.y 
with probability greater than 1/2+1/n.sup.c, for any c. 
Our theorem follows directly from this result. 
Ideal versus Nonideal Oblivious Transfer Bits 
As we have mentioned above, the oblivious transfer protocol we implement is 
nonideal in the obliviousness conditions. The nonideal nature of the 
obliviousness condition is inherent to our model, if the transfer 
condition is indeed ideal in the information theoretic sense. If the two 
infinitely powerful provers are allowed to communicate freely, they can 
each learn the entire transcript of the oblivious transfer protocol, and 
thus determine everything the verifier could have learned from the 
protocol. This violates the obliviousness condition of oblivious transfer, 
yielding the following observation. 
Observation 
It is impossible to implement an ideal oblivious transfer protocol between 
two provers and a verifier if the provers are allowed to communicate 
freely after the protocol. 
The nonideal nature of the oblivious condition does not affect whether a 
protocol is zero-knowledge; the verifier learns exactly as much from a 
pseudo-oblivious source as from an oblivious one. However, using a 
pseudooblivious source of bit instead of an ideal source could conceivably 
cause a protocol to no longer be a proof system. We show that, provided 
the security parameter for our pseudo-oblivious source is sufficiently 
high, this will not be the case. 
Formalizing Proof Systems with Oblivious Transfer Channels 
In order to state our result more precisely, we first augment our 
definition of two-prover interactive proof systems by adding a fourth 
party, a transfer source. 
Definition 
A two-prover interactive protocol with oblivious transfer consists of a 
four-tuple of parties, &lt;P.sub.1, P.sub.2, V, T&gt;. Parties P.sub.1, P.sub.2, 
V may be formally described as mappings from sequences of .SIGMA.* 
(informally, the history of that party's conversation so far) to 
distributions on .SIGMA.* (informally, the next answer/question 
given/asked by the party). 
Player T may be formally described as a mapping form {0, 1}* to a 
distribution on triples (I.sub.P.sbsb.1, I.sub.P.sbsb.2, I.sub.V). The 
values I.sub.P.sbsb.1, I.sub.P.sbsb.2 may be informally thought of as 
information leaked back to the provers, P.sub.1 and P.sub.2, by a possibly 
nonideal oblivious transfer protocol. The possible values of I.sub.V on 
input O=O.sub.1, . . . , O.sub.k are elements of {0, 1, #}*, of the form 
O'.sub.1 . . . O'.sub.k, where O'.sub.i =O.sub.i or O'.sub.i =#. 
Informally, I.sub.V consists of the bits that are transferred to the 
verifier, V. 
For the rest of the discussion, we will anthromorphize our descriptions of 
the P.sub.1, P.sub.2, V and T, describing their behavior in terms of 
actions by players instead of as values of functions. 
Protocols with oblivious transfer are evaluated in nearly the same way as 
standard protocols, but for an initial oblivious transfer phase. At the 
beginning of the protocol, the provers, P.sub.1 and P.sub.2, agree on a 
sequence of bits O, which they send to the transfer mechanism, T. The 
transfer mechanism sends some of these bits to the verifier, and sends 
additional information back to the two provers. At this point, T no longer 
plays any part in the protocol, and the players P.sub.1, P.sub.2, and V 
proceed to interact in the same manner as with standard two-prover 
protocols. Players P.sub.1, P.sub.2, and V treat their views of the 
oblivious transfer phase as special inputs. 
Modeling ideal and nonideal sources in our formalism 
We now give a specification for an oblivious transfer mechanism which 
models the information received by the provers by the actual oblivious 
transfer mechanism we have implemented in the two-prover model. 
Specification 
Oblivious transfer mechanism T.sub.n,k is specified by its input from the 
provers and its output to the provers and the verifier. T.sub.n,k takes as 
input a sequence of bits O=O.sub.1, . . . , O.sub.k. It flips k coins, 
b.sub.1, . . . , b.sub.k. T.sub.n,k randomly selects two sequences of n 
element boolean vectors, x.sub.1, . . . , x.sub.k and y.sub.1, . . . , 
y.sub.k, subject to x.sub.i.y.sub.i =b.sub.i. T.sub.n,k 's output is as 
follows. 
Transfer to V 
T.sub.n,k sends the verifier sequence O'=O.sub.1 ', . . . , O.sub.k ' where 
O.sub.i '=O.sub.i iff b.sub.i =1. Otherwise, O.sub.i '=#. 
Transfer to P.sub.1 
T.sub.n,k sends P.sub.1 the sequence x.sub.1, . . . , x.sub.k. 
Transfer to P.sub.2 
T.sub.n,k sends P.sub.2 the sequence y.sub.1, . . . , y.sub.k. 
This model for our transfer channel makes the following simplifications. 
The verifier does not get any partial glimpses at bits that it hasn't 
completely received, whereas in the actual protocol, it may guess it with 
probability 3/4. Also, it does not get any record of its interactions with 
the provers in the oblivious transfer protocol. For instance, in the 
actual protocol, the verifier would also known x.sub.i 's and y.sub.i 's, 
whereas in this model it does not. These simplifications turns out to be 
irrelevant to our analysis, since the valid verifier completely disregards 
all of this extra information. 
More significantly, the provers do not receive any of the extra information 
they might obtain in the commital and oblivious transfer phases. One can 
show that any pair of provers which have any chance of fooling the 
verifier must abide by rules of the commital and oblivious transfer 
protocols. The extra information they receive from an honest run of these 
protocols is of no value to them. They may, in a certain technical sense, 
simulate all of this extra information, once given their respective vector 
sequences x.sub.1, . . . , x.sub.k and y.sub.1, . . . , y.sub.k. Thus, the 
provers cannot cheat any more effectively using our simplified channel 
than they could using the actual commital and oblivious transfer 
protocols. The details of this argument are ommitted. 
Modeling an ideal oblivious transfer mechanism 
It is fairly straightforward to model an ideal oblivious transfer mechanism 
in our formalism. We denote this transfer channel T.sub.k.sup.ideal, which 
we specify as follows. 
Specification 
Oblivious transfer mechanism T.sub.k.sup.ideal is specified by its input 
from the provers and its output to the provers and the verifier. 
T.sub.k.sup.ideal takes as input a sequence of bits O=O.sub.1, . . . , 
O.sub.k. It flips k coins, b.sub.1, . . . , b.sub.k. It randomly selects 
two sequences of n element boolean vectors, x.sub.1, . . . , x.sub.k and 
y.sub.1, . . . , y.sub.k. T.sub.k.sup.ideal 's output is as follows. 
Transfer to V 
T.sub.k.sup.ideal sends the verifier sequence O'=O.sub.1 ', . . . , O.sub.k 
' where O.sub.i '=O.sub.i iff b.sub.i =1. Otherwise, O.sub.i '=#. 
Transfer to P.sub.1 and P.sub.2 
T.sub.k.sup.ideal sends nothing to P.sub.1 or P.sub.2. 
A practical equivalence between T.sub.n,k and T.sup.ideal 
We can now state our theorem concerning the the practical equivalence of 
our oblivious transfer protocol and the ideal one. 
Theorem 
Let &lt;P.sub.1, P.sub.2, V, T.sub.p(n).sup.ideal &gt; be an interactive proof 
system with oblivious transfer. Here, p(n) denotes some polynomial in the 
size of the input. Then there exists some some polynomial q(n) such that 
&lt;P.sub.1, P.sub.2, V, T.sub.q(n),p(n) &gt; is also an interactive proof 
system with oblivious transfer. 
Brief Outline of Proof 
The proof of this theorem is somewhat involved. We show that if one could 
cheat more effectively using a T.sub.q(n),p(n) transfer channel, for q(n) 
arbitrarily large, then one could use this fact to create a protocol for 
computing the dot product of two random q(n) element boolean vectors. The 
communication complexity for this protocol will depend on V and n, but not 
on the function q. From this it is possible to use the Chor-Goldreich 
lower bound on the communication complexity of boolean dot product to 
reach a contradiction. 
In order to constuct the protocol for computing boolean dot products, we 
first define a sequence of transfer mechanisms that are intermediate 
between our nonideal and ideal transfer mechanisms. We show that if the 
provers can cheat using the nonideal transfer mechanism, then two 
consecutive transfer mechanisms in our sequence can be distinguished. We 
then show how to use these transfer mechanisms to generate two very simple 
and very similar transfer mechanisms whose behavior is distinguishable. 
Finally, we use the distinguishability of this final air of transfer 
mechanisms to create a protocol for boolean dot-product. We proceed to 
formalize this argument. 
Transfer mechanism that are intermediate between the ideal and nonideal 
models 
We specify a sequence of oblivious transfer mechanisms as follows. 
Specification 
Oblivious transfer mechanism T.sub.n,k.sup.i is specified by its input from 
the provers and its output to the provers and the verifier. 
T.sub.n,k.sup.i takes as input a sequence of bits O=O.sub.1, . . . , 
O.sub.k. It flips k coins, b.sub.1, . . . , b.sub.k. T.sub.n,k.sup.i 
randomly selects two sequences of n element boolean vectors, x.sub.1, . . 
. , x.sub.k and y.sub.1, . . . , y.sub.k. For 1.ltoreq.j.ltoreq.i, vectors 
x.sub.j and y.sub.i are subject to the constraint x.sub.i 
.multidot.y.sub.i =b.sub.j. T.sub.n,k.sup.i 's output is as follows. 
Transfer to V 
T.sub.n,k.sup.i sends the verifier a sequence O'=O.sub.1 ', . . . , O.sub.k 
' where O.sub.i '=O.sub.i iffb.sub.i =1. Otherwise, O.sub.i '=#. 
Transfer to P.sub.1 
T.sub.n,k.sup.i sends P.sub.1 the sequence x.sub.1, . . . , x.sub.k. 
Transfer to P.sub.2 
T.sub.n,k.sup.i sends P.sub.2 the sequence y.sub.1, . . . , y.sub.k. 
The only difference between T.sub.n,k and T.sub.n,k.sup.i is that the 
vectors sent to the provers by T.sub.n,k all have some correlation with 
whether the bit was sent to the verifier, whereas only the first i vectors 
sent to the provers by T.sub.n,k.sup.i are so correlated. Note that 
T.sub.n,k.sup.o is equivalent to the ideal channel T.sub.k.sup.ideal, and 
T.sub.n,k.sup.k is equivalent to T.sub.n,k. 
Analysis of cheating probabilities for different transfer mechanisms 
The sequence of oblivious transfer mechanisms we defined above is 
"continuous" in that any two consecutive mechanisms are only incrementally 
different from each other. Using an argument similar to that of [GM], we 
show that if the probability of successfully cheating using one transfer 
mechanism in the sequence is significantly greater than the probability of 
successfully cheating using a different transfer mechanism in the 
sequence, then there must be two consecutive mechanisms which differ in 
the probability of a particular cheating strategy being successful. 
Definition 
Let L be some language, and &lt;P.sub.1, P.sub.2, V, T.sub.p(n).sup.ideal &gt; a 
two-prover IPS for L, with oblivious transfer. For some x L, 
.vertline.x.vertline.=n, we define cheat.sub.ideal (x) as the probability 
that V can be tricked into accepting x. 
We wish to analyze how frequently the provers can cheat if they use a 
nonideal transfer mechanism, T.sub.q(n),p(n). Let P.sub.1,q(n), 
P.sub.2,q(n) be optimal cheating provers for the protocol &lt;P.sub.1,q(n), 
P.sub.2,q(n), V, T.sub.q(n),p(n) &gt;. For x L, .vertline.x.vertline.=n, we 
define cheat.sub.q(n).sup.i (x) as the probability that P.sub.1,q(n), 
P.sub.2,q(n) causes V to accept x in protocol &lt;P.sub.1,q(n), P.sub.2,q(n), 
V, T.sub.q(n),p(n).sup.i &gt;. Clearly, we have cheat.sub.q(n).sup.0 
(x).ltoreq.cheat.sub.ideal (x). We also have, by definition. that 
cheat.sub.q(n).sup.p(n) (x) is the maximum probability that any provers 
can trick V into accepting x, using transfer mechanism T.sub.q(n),p(n). 
Using a simple pigeonhole argument, we can show the following. 
Lemma A.2 
Let x L, and .vertline.x.vertline.=n. For all polynominals q(n), there 
exist some i, 0.ltoreq.i&lt;p(n), such that 
##EQU11## 
We now show that if for for all polynomials q(n), there exists a c&gt;0, such 
that cheat.sub.q(n).sup.i+1 (x)-cheat .sub.q(n).sup.i 
(x)&gt;1.vertline.x.vertline..sup.c for infinitely many x, then we can create 
efficient algorithms for computing dot products of random vectors. To do 
this, we first must introduce the notion of "hardwired" versions of 
transfer mechanisms T.sub.q(n),p(n).sup.i. 
Restricted versions of oblivious transfer mechanisms 
Given two easily distinguishable mechanisms T.sub.q(n),(n).sup.i and 
T.sub.q(n),p(n).sup.i+1, we would like to create even simpler pairs of 
mechanisms that are easily distinguishable, yet preserve the essential 
differences between T.sub.q(n),p(n).sup.i and T.sub.q(n),p(n).sup.i+1. We 
observe that the only difference between these two mechanisms lies in the 
distibutions imposed on the vectors x.sub.i+1 and y.sub.i+1 which are sent 
to P.sub.1,q(n) and P.sub.2,q(n). We would like to be able to fix all the 
other aspects of these channels. To do this, we make the following 
definitions. 
Definition 
A transfer restriction R .epsilon.R.sub.n,k.sup.i is a 3-tuple (R.sub.b, 
R.sub.x, R.sub.y), where 
.cndot.R.sub.b is a sequence of bits, b.sub.1, . . . , b.sub.k. 
.cndot.R.sub.x is a k-1 element sequence of n element boolean vectors, 
x.sub.1, . . . , x.sub.i-1, x.sub.+1, . . . , x.sub.k. 
.cndot.R.sub.y is a k-1 element sequence of n element boolean vectors, 
y.sub.1, . . . , y.sub.i-1, y.sub.i-1, . . . , y.sub.k. 
Furthermore, we require that for 1&gt;j&lt;i, x.sub.i .multidot.y.sub.j =b.sub.j. 
Intuitively, we can think of R.epsilon.R.sub.n,k.sup.i as a specification 
for which bits get through to the verifier, and, except fot the ith bit, 
specifications for which vectors are transmitted back to the provers. 
Definitions 
Given a transfer restriction R.epsilon.R.sub.n,k.sup.i We specify a 
restricted version of T.sub.n,k.sup.i which we denote by T.sub.n,k.sup.i 
[R], as follows. 
Specification 
Oblivious transfer mechanism T.sub.n,k.sup.i [R] takes as input a sequence 
of bits O=O.sub.1, . . . , O.sub.k. Let R.sub.b =b.sub.1, . . . , b.sub.k, 
R.sub.x =x.sub.1, . . . , x.sub.i-1, x.sub.i+1, . . . , x.sub.k, and 
R.sub.y =y.sub.1, . . , y.sub.i-1, y.sub.i+1, . . . , y.sub.k. 
T.sub.n,k.sup.i [R] randomly selects two n element boolean vectors, 
x.sub.i and y.sub.j. If j.ltoreq.i, then x.sub.j and y.sub.j are chosen 
s.t x.sub.j .multidot.y.sub.j =b.sub.j. T.sub.n,k.sup.i [R]'s output is as 
follows. 
Transfer to V 
T.sub.n,k.sup.i [R] sends the verifier sequence O.sub.1 ', . . . , O.sub.k 
' where O.sub.i '=O.sub.i iffb.sub.i =1. Otherwise, O.sub.i '=#. 
Transfer to P.sub.1 
T.sub.n,k.sup.i [R] sends P.sub.1 the sequence x.sub.1, . . . , x.sub.k. 
Transfer to P.sub.2 
T.sub.n,k.sup.i [R] sends P.sub.2 the sequence y.sub.1, . . . , y.sub.k. 
Analysis of cheating with respect to restricted transfer mechanisms 
Recall that provers P.sub.1,q(n) and P.sub.2,q(n) cheat optimally, given 
oblivious transfer mechanism T.sub.q(n),p(n). We would like to described 
what happens when these provers are run using restricted transfer 
mechanisms. To this end, we define cheat.sub.q(n).sup.i [R](x) as the 
probability that P.sub.1,q(n), P.sub.2,q(n) causes V to accept x in 
protocol &lt;P.sub.1,q(n), P.sub.2,q(n), V, T.sub.q(n),p(n).sup.i [R]&gt;. 
Using a simple probabilistic argument, we prove the following important 
lemma. 
Lemma A.3 
Let x L, and .vertline.x.vertline.=n. Let 1.ltoreq.i&lt;p(n). For all 
polynomials q(n), there exists a restriction 
R.epsilon.R.sub.q(n),p(n).sup.i+1) such that 
##EQU12## 
Using T.sub.q(n),p(n).sup.i [R], T.sub.q(n),p(n).sup.i+1 [R] to compute dot 
products 
Recall that a restriction R.epsilon.R.sub.q(n),p(n).sup.i+1) defines the 
entire input/output properties of a restricted transfer protocol 
T.sub.q(n),p(n).sup.i [R], but for the output vectors x.sub.i, y.sub.i 
transmitted back to the provers. If the two provers have a source 
M.sub.q(n), which produces vector pairs x,y, of size q(n) and sends them 
to Prover1 and Prover2, respectively, we can use it to stimulate 
T.sub.q(n),p(n).sup.i [R]. 
We also note that, if allowed to communicate directly, two provers can 
"simulate" the verifier in the following way. They can send to each other 
the messages they would have sent to the verifier. By knowing the set of 
transfer bits, which bits were received by the verifier, and a transcript 
of the conversation so far between the verifier and the provers, the 
provers can determine exactly what the verifier's next question in the 
conversion will be. 
We now can explicitly write down a protocol for computing the dot product 
of random boolean vectors. The assume that the two parties P.sub.1 and 
P.sub.2 have agreed on some x(x L..vertline.x.vertline.=n), q, i, and 
R=(R.sub.b, R.sub.x, R.sub.y) .epsilon. R.sub.q(n),p(n).sup.i+1). The 
protocol is specified as follows. Player P.sub.1 receives a random boolean 
vector x, and player P.sub.2 receives a random boolean vector y. At the 
end of the protocol, player P.sub.1 outputs a 0 or 1, which hopefully 
corresponds to x.multidot.y. 
Protocol 
Dot-Product(x,y)/* P.sub.1 knows x, P.sub.2 knows y, and 
.vertline.x.vertline.=.vertline.y.vertline.=q(n)*/ P.sub.1 and P.sub.2 
simulate the protocol &lt;P.sub.1,q(n), P.sub.2,q(n), V, 
T.sub.q(n),p(n).sup.i [R]&gt;, on input x. They treat vectors x and y as 
substitutes for x.sub.i+1, y.sub.i+1 (which are not defined by R). 
If the simulated verifier accepts, then P.sub.1 outputs b.sub.i+1, were 
R.sub.b =b.sub.1, . . . , b.sub.p(n). Otherwise it outputs the complement 
of b.sub.i+1. 
We now analyze the communication complexity of this protocol. 
Definition 
Given a two-prover protocol P=P.sub.1, P.sub.2, V, T&gt;, and some input x, we 
define the leakage L(P,x) as the total number of bits transmitted from the 
provers to the verifier. 
The following lemma follows immediately from the definition of Dot-Product. 
Lemma A.4 
Let P=&lt;P.sub.1,q(n), P.sub.2,q(n), V, T.sub.q(n),p(n).sup.i [R]&gt;. Then 
protocol Dot-Product requires L(P,x) bits of communication. 
Finally, we can bound below Dot-Product's success rate on random vectors by 
the following lemma. 
Lemma A.5 
Given q(n) bit vectors x, y distributed uniformly, the probability that 
Dot-Product (x,y)=x.multidot.y is at least 
##EQU13## 
Proof 
Our proof is by a straightforward calculation of conditional probabilities, 
which we outline below. We define the variables good and bad by 
##EQU14## 
The probability the Dot-Product yields the correct answer is equal to 
##EQU15## 
We now solve for good and bad in terms of cheat.sub.q(n).sup.i [R](x) and 
cheat.sub.q(n).sup.i+1 [R[(x). Using our definitions for 
cheat.sub.q(n).sup.[ [R](x) and cheat.sub.q(n).sup.i+1 [R](x), we have 
##EQU16## 
Solving for good and bad, we have 
##EQU17## 
Substituting equations (A.2.12) and (A.2.13) into equation A.2.9), and 
simplifying, we get equation (A.2.8). 
A.3 Implementing zero-knowledge with circuits 
In this section we outline a technique we call the method of encrypted 
conversations. This technique represents a fairly general methodology for 
converting protocols into zero-knowledge protocols. Its main requirement 
is the ability of the parties involved to perform oblivious circuit 
evaluation. 
A normal form for two-prover IPS's 
For ease of exposition, we consider a normal form for two-prover 
interactive proof systems (IPS's). This normal form consists of three 
stages, as described below. 
Notation 
Throughout this section, q.sub.i (x,r,.,.,.) will denote that i-th question 
of the verifier computed on his random coin tosses r, the input x, and the 
history of the communication so far. (a.sub.i correspond to the provers 
answers). 
Stage 1 
On input x, where .vertline.x.vertline.=n, the verifier generates a 
sequence r=r.sub.1, . . . , r.sub.p(n) of random bits. The verifier 
computes his first question, q.sub.1 =q.sub.1 (x,r). 
Stage 2 
The verifier sends q.sub.1 to Prover 1. Prover 1 sends its answer, a.sub.1 
back to the verifier. The verifier computes his second question, q.sub.2 
=q.sub.2 (x,r,a.sub.1). 
Stage 3 
The verifier sends q.sub.2 to Prover 2. Prover 2 sends its answer, a.sub.2, 
back to the verifier. The verifier computes its decision predicate, 
accept(x,r,a.sub.1,a.sub.2), and accepts iff accept(x,r,a.sub.1,a.sub.2) 
evaluates to "true". 
We use the following result. 
Theorem(normal form for 2 prover IPS's) 
Given any two prover IPS P for a language L, there exists an IPS P', with 
the following 2 properties. 
1. If x.epsilon.L then prob(P'(x) accepts)=1. 
2. There exists some c&gt;0 such that if x L then prob(P'(x) 
accepts).ltoreq.1-1/.vertline.x.vertline..sup.c. 
Remark 
It is currently open whether the .ltoreq.1-1/.vertline.x.vertline..sup.c 
failure probability can be reduced. However, if greater reliability is 
desired, one may run a normal form protocol several times serially to 
achieve an exponentially low probability of failure. 
We now need to show how to convert an IPS in normal form into a 
zero-knowledge IPS. 
Conceptually, we would like to have the use of a black box into which the 
verifier inputs an encrypted history of the communication, the prover 
inputs its answer to the question and the output which is given to the 
verifier is the encrypted answer of the prover and the encrypted next 
question of the verifier. See FIG. 2. 
The encryption scheme used to encrypt the questions and answers should be 
an information theoretically strong encryption scheme with respect to the 
verifier, while the provers will be given the ability to decrypt. 
We describe how this is achieved in the following section A.3.1. The box is 
achieved by the technique of oblivious circuit evaluation as described in 
section A.3.2. 
A.3.1 Strong encryption using 2-universal hash functions 
We need a cryptographic system (call it E for the sake of discussion) which 
is both unbreakable, and existentially unforgeable. By unbreakable, we 
means that if one is given E(x), an encryption of x, but one does not have 
the decryption key, then one cannot infer anything about x. By 
existentially unforgeable, we mean that if one is given E(x), an 
encryption of x, but one does not have the decryption key, then one cannot 
produce any string forge such that forge=E(y) for some y. These security 
requirements are information theoretic, and must apply to someone with 
arbitrary computational power. 
To accomplish this, we use the notion of universal hash functions, first 
introduced by Carter and Wegman[CW]. In addition, we require the following 
property of our universal sets. 
Definition 
A family of 2-universal sets H.sub.n of functions h:{0,1}.sup.n 
.fwdarw.{0,1}.sup.n is almost self-inverse iff for all c, and for all n 
sufficiently large (with respect to c), a function h, picked uniformly 
from H, will have an inverse h.sup.-1 .epsilon.H with probability 
&gt;1-n.sup.-c. 
One example of an almost self-inverse 1-universal set of hash functions is 
the set of linear equations over GF(2.sup.n). As there is a trivial 
correspondence between {0,1}.sup.n and GF(2.sup.n). As there is a trivial 
corresondence between {0,1}.sup.n and GF(2.sup.n), we treat all our 
elements as being in {0,1}.sup.n. 
For our encryption system, we require that all legal message m are padded 
with a number of trailing 0's equal to the length of the original message. 
We encrypt a message m.epsilon.{0,1}.sup.n by applying some uniformly 
selected function h.epsilon.H.sub.n to it. We can decrypt h(m) by by 
applying its h.sup.-1 to it. For our purposes, we can safely ignore the 
possibility that a uniformly chosen h isn't invertible. The following 
lemma shows that this encryption scheme is unbreakable and unforgeable. 
Lemma 
Let h be chosen uniformly from H.sub.n. Then 
EQU (unbreakability) (x,y.epsilon.{0,1}.sup.n)prob(h(x)=y)=2.sup.-n. (1) 
EQU (unforgeability) (x,y,z.epsilon.{0,1}.sup.n)prob(w.epsilon.{0,1}.sup./2 
0.sup.n/2)h(w)=z.vertline.h(x)=y)=2.sup.-n/2. (2) 
Proof 
Both properties follow immediately from the definition of 2-universal hash 
functions. 
In the protocol the provers will agree on four random hash functions 
h.sub.1, h.sub.2, h.sub.3, h.sub.r .quadrature.H.sub.p(n). At the end of 
the protocol, the verifier will possess the values of h.sub.1 (r), h.sub.2 
(q.sub.1), and h.sub.3 (a.sub.1), but will not possess any extra 
information about which functions h.sub.1, h.sub.2 and h.sub.3 actually 
are. However, knowing the value of h(x) gives no information, in the 
information theoretic sense, about the value of x. This is roughly how the 
zero-knowledge aspect of our protocol is achieved. 
A.3.2 Use of oblivious circuit evaluation 
We use the reduction of Kilian[K] from oblivious transfer to oblivious 
circuit computation. This reduction maintains the usual security 
properties desired of oblivious circuit evaluation, without recourse to 
any intractibility assumptions..sup.5 Its sole requirement is a sequence 
O=O.sub.1, . . . , O.sub.p(n) of bits, all of which are known to A, and 
half of which are known to B(a more detailed description of this condition 
is given in section A.2). This set of bits (or, more technically, a 
reasonable approximation to such a set) is provided by the oblivious 
transfer protocol outlined in section A.2 for the rest of this discussion, 
we treat oblivious circuit evaluation as a primitive operation. 
FNT .sup.5 Goldreich-Vainish describe a simple reduction from oblivious circuit 
evaluation to oblivious transfer, without any intractibility assumptions. 
However, this reduction only works for honest parties, and is thus 
unuseable by us. 
A.3.3 Outline of the Zero-Knowledge Protocol 
We can now describe our zero-knowledge transformed protocol For our 
expositions, we still treat oblivious circuit computation of as a 
primitive. (A description of circuits C.sub.o, C.sub.1, C.sub.2 and 
C.sub.3 is given following the protocol.) Note the similarity between this 
description and the description of the normal-form for protocols given 
above. 
On input x, where .vertline.x.vertline.=n. 
Step O 
Provers 1 and 2 agree on random invertible hash functions h.sub.1, h.sub.2, 
h.sub.3, h.sub.4 .epsilon.H.sub.2p(n), and random string r.sub.1 
.epsilon.{0,1}.sup.p(n). The verifier selects a random string r.sub.2 
.epsilon.{0,1}.sup.p(n). The verifier and Prover 1 evaluate r'=C.sub.o 
[x](r.sub.1,r.sub.2,h.sub.1). (/r will the random coin tosses to be used 
by the verifier). 
Step 1 
The verifier and Prover 1 then evaluate q.sub.1 '=C.sub.1 
[x](r',h.sub.i.sup.-1,h.sub.2), the encrypted version of the verifier's 
first question. 
Step 2 
The verifier sends q.sub.1 ' to Prover 1. If h.sub.2.sup.-1 (q.sub.1 ') 
does not decrypt to a legitimate message, then Prover 1 halts the 
conversation. Otherwise, Prover 1 computes his answer, a.sub.1, and sends 
the verifier a.sub.1 '=h.sub.3 (a.sub.1). The verifier and Prover 1 
evaluate q.sub.1 '=C.sub.2 [x](r',a.sub.1 
',h.sub.1.sup.-1,h.sub.3.sup.-1,h.sub.4), the encrypted version of the 
verifiers second question. 
Step 3 
The verifier sends q.sub.2 ' to Prover 2. If h.sub.4.sup.-1 (q.sub.2 ') 
does not decrypt to a legitimiate message, then Prover 2 halts the 
conversation. Otherwise, Prover 2 computes his answer, a.sub.2. The 
verifier and Prover 2 evaluate decision=C.sub.3 [x](r',a.sub.1 
',a.sub.2,H.sub.1.sup.-1,h.sub.3.sup.-1). 
At the end of this protocol, verifier accepts iff decision=true. 
We now describe circuits C.sub.i for i=0,1,2,3. 
For each circuit, we give the input from the prover, the input from the 
verifier, and the output given to the verifier. We adopt the convention 
that .vertline.x.vertline.=n, and assume without loss of generality that 
all strings being exchanged in the protocol are of length p(n), for some 
polynomial p. We use the following simple functions to simplify our 
exposition. Function pad.sub.n :{0,1}.sup.n .fwdarw.{0,1}.sup.2n pads an 
extra n zeros onto the end of an n-bit string Function strip.sub.n 
:{0,1}.sup.2n .fwdarw.{0,1}.sup.n, which removes the last n bits from a 
2n-bit string. Predicate legal.sub.n :{0,1}.sup.2n .fwdarw.{true,false} is 
true iff the last n bits of the input string are equal to 0. 
C.sub.o [x] 
Input from the prover 
A sequence of bits, b=b.sub.1, . . . , b.sub.p(n), and a hash function 
h.epsilon.H.sub.2p(n). 
Input from the verifier 
A sequence of bits c=c.sub.1, . . . , C.sub.p(n). 
Output to the verifier: Output(h(pad.sub.n (b.sym.c))). 
Circuit C.sub.o [x] is the initialization circuit that creates the 
verifiers random bits in Stage 1 of the protocol described above. 
______________________________________ 
C.sub.1 [x]: 
Input from the prover: 
Hash functions h.sub.1.sup.-1, h.sub.2 .epsilon. H.sub.2p(n). 
Input from the verifier: 
String r' .epsilon. {0;1}.sup.2p(n). 
Output to the verifier: 
r = h.sub.1.sup.-1 (r') 
If legal.sub.p(n) (r) = false 
Then Output(O.sup.2p(n)) 
Elde r = strip.sub.p(n) (r) 
q.sub.1 = q.sub.1 (x,r) 
Output(h.sub.2 (pad.sub.p(n) (q.sub.1))) 
______________________________________ 
Circuit C.sub.1 [x] is used to implement Stage 1 of the protocol described 
above. 
______________________________________ 
C.sub.2 [x]: 
Input from the prover: 
Hash functions h.sub.1.sup.-1, h.sub.4 .epsilon. H.sub.2p(n) 
Input from the verifier: 
Strings r', a'.sub.1 .epsilon. {0,1}.sup.2p(n) 
Output to the verifier: 
r = h.sub.1.sup.-1 (r') 
a.sub.1 = h.sub.3.sup.-1 (a.sub.1 ') 
If (legal.sub.p(n) (r) and legal.sub.p(n) (a.sub.1) = false 
Then Output(O.sup.2p(n)) 
Else r = strip.sub.p(n) (r) 
a.sub.1 = strip.sub.p(n) (a.sub.1) 
q.sub.2 = q.sub.2 (x,r,a.sub.1) 
Output(h.sub.4 (pad.sub.p(n) (q.sub.2))) 
______________________________________ 
Circuit C.sub.2 [x] is used to implement Stage 2 of the protocol described 
above. 
______________________________________ 
C.sub.3 [x]: 
Input from the prover: 
Hash functions h.sub.1.sup.-1, h.sub.3.sup.-1 .epsilon. H.sub.2p(n), 
String a.sub.2 .epsilon. {0,1}.sup.p(n) 
Input from the verifier: 
Strings r', a'.sub.1 .epsilon. {0,1}.sup.2p(n). 
Output to the verifier: 
r = h.sub.1.sup.-1 (r') 
a.sub.1 = h.sub.3.sup.-1 (a.sub.1 ') 
If(legal.sub.p(n) (r) and legal.sub.p(n) (a.sub.1)) = false 
Then Output(O.sup.2p(n)) 
Else r = strip.sub.p(n) (r) 
a.sub.1 = strip.sub.p(n) (a.sub.1) 
Output(accept(x,r,a.sub.1,a.sub.2)) 
______________________________________ 
Circuit C.sub.3 [x] is used to implement Stage 3 of the protocol described 
above. 
The two obvious questions we must deal with are, "Is this protocol still a 
proof system?", and "Is this protocol zero-knowledge?" 
Is this protocol a proof system? 
If the verifier is honest, and if the provers input the correct hash 
functions, and their inverses, into the circuits being evaluated, then one 
can map transcripts of conversations in this protocol into transcripts of 
the original protocol (with possibly cheating provers). In this case, the 
provers cannot cheat any more effectively they could in the original 
protocol, and the new protocol will remain a proof system if the original 
one was. 
If the provers do not input consistent sets of hash functions, then nothing 
can be guarenteed about whether the protocol remains a proof system. 
However, using the machinery developed in [K], it is possible for the 
provers to commit, at the beginning of the protocol, all the hash 
functions they input to the circuits, along with a zero-knowledge proof 
that these inputs are consistent with each other. 
Is this protocol zero-knowledge? 
The proof that this protocol is zero-knowledge is, while not overly complex 
or difficult, relies too heavily on machinery from [K] to be concisely 
presented here. We make the following intuitive argument for why the 
protocol is zero-knowledge. 
First, note that the verifier's actions are severely restricted by the use 
of circuits and the encryption scheme. Except for its random bits, all the 
inputs it gives to the provers or the circuits are encrypted with an 
unforgeable system. If the verifier ever attempts to give an incorrect 
string to a prover, the prover will detect the forgery will probability 
exponentially close to 1. Likewise, if the verifier inputs an incorrect 
string to a circuit, it will almost certainly output either 0.sup.2p(n) or 
false. This rules out any active attack on the part of the verifier. 
Second, we show that passive attacks by the verifier do not yield ay 
information. The intermediate outputs of circuits C.sub.1, . . . , C.sub.3 
are all uniformly distributed, and thus yield no information. 
F Applications of the two-processor system to general protocols 
Our two-processor system can be used to solve problems more general than 
simple identification. A two-processor smart card (or other similar 
system) can interact with another agency in any general two-party 
protocol. Let X designate a string, number, or other encoding of some 
information possessed by a two-processor smart card (or other similar 
system). Let Y designate a string, number, or other encoding of some 
information possessed by a second party. This second party may have the 
ability to isolate the two processors on the smart card (or other similar 
system), or the processors may be isolated by some further external 
mechanism. 
Let F be any function which may be described by a circuit. Then the 
two-processor smart card (or other similar system) can interact with the 
second party, so that the following conditions hold. 
1. The second party learn the value of F(X,Y). 
2. For as long as the two processors on the smart card (or other similar 
system) cannot compute any information about Y. Thus, subject to the 
isolation condition being maintained, the second party's security is 
unconditionally protected in this phase of the interaction. This security 
does not depend on any assumptions about the intractability of computing 
special functions. 
3. The second party learns no further information about X than may be 
inferred from knowing Y and F(X,Y). This security condition remains even 
after the isolation of the two processors has terminated. 
The technique for implementing general protocols satisfying the above 
security conditions is described in the document, Multi-Prover Interactive 
Proof Systems: Eliminating Intractability Assumptions. 
References [BC] Brassard, Gilles and Claude Crepeau. "Zero-Knowledge 
Simulation of Boolean Circuits," Proceedings of the 27th FOCS, IEEE, 1986, 
188-195. 
[GM] Goldwasser S., and Micali S., "Probabilistic Encryption", JCSS, vol. 
28, no. 2, 1984, pp. 270-299. 
[GHY] Galil Z., Haber S., and Yung M., "A Private Interactive Test of a 
Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystem", 
Proceedings of the 26th FOCS, 1985, pp. 360-371. 
[GMW] Goldreich, Oded, Silvio Micali, and Avi Wigderson. "Proofs that Yield 
Nothing but the Validity of the Assertion, and a Methodology of 
Cryptographic Protocol Design," Proceedings of the 27th FOCS, IEEE, 1986, 
174-187. 
[GMR] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The Knowledge 
Complexity of Interactive Proof-Systems," Proceedings of the 17th STOC, 
ACM, 1985, 291-304. 
[AL] Angluin, Dana and David Lichtenstein. "Provable Security of 
Cryptosystems: a Survey," YALEU/DCS/TR-288, 1983. Proceeding of the 17th 
STOC, 1985, pp. 421-429. 
[Ba] Barrington, D. "Bounded Width Polynomial Size Branching Programs 
Recognize Exactly Those Languages in NC.sup.1 ", Proceedings of 18th STOC, 
1986, pp. 1-5. 
[Bl] Blum, M., Private Communication. 
[BC] Brassard, Gilles and Claude Crepeau. "Zero-Knowledge Simulation of 
Boolean Circuits," Proceedings of the 27th FOCS, IEEE, 1986, 188-195. 
[BHZ] Boppana, Ravi, Johan Hastad, and Stathis Zachos. "Does CoNP Have 
Short Interactive Proofs?," IPL, 25, 1987, 127-132. 
[CDvdG] Chaum, David, Ivan Damgard, and Jeroen van de Graaf. "Multiparty 
Computations Ensuring Secrecy of Each Party's Input and Correctness of the 
Output," Proceedings of CRYPTO '87. Proceedings of CRYPTO '85, 
Springer-Verlag, 1986, 477-488. 
[CG] Chor, B, Goldreich G, "Unbiased Bits from Sources of Weak Randomness 
and Probalistic Communication Complexity", Proceedings of the 26th FOCS, 
1985. 
[Ck] Crepeau C., Kilian J., Private Communication. 
[CW] Carter L., Wegman M., "Universial Classes of Hash Functions", JCSS 18, 
1979, pp. 143-154. 
[C] Crepeau Claude, "On the Equivalence of Two Types of Oblivious 
Transfer", Crypto87. 
[FST] Feige, U., Shamir, A., Tennenholz, M., "The Noisy Oracle Problem", 
Private Communication of Manuscript 
[F] Fortnow, Lance. "The Complexity of Perfect Zero-Knowledge," Proceedings 
of the 19th STOC, ACM, 1987, 204-209. 
[FRS] Fortnow, Lance., Rompel J., Sipser M., "On the Power of Multi-Prover 
Interactive Proofs" In preparation. 
[FMR] Fischer M., Micali S., Rackoff C., and Wittenberg S., "An Oblivious 
Transfer Protocol Equivalent to Factoring", In Preparation. 
[GM] Goldwasser S., and Micali S., "Probabilistic Encryption", JCSS, vol. 
28, no. 2, 1984, pp. 270-299. 
[GHY] Gali Z., Haber S., and Yung M., "A Private Interactive Test of a 
Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystem", 
Proceedings of the 26th FOCS, 1985, pp. 360-371. 
[EGL] Even S., Goldreich O., and A. Lempel, A Randomized Protocol for 
Signing Contracts, CACM, vol. 28, no. 6, 1985, pp. 637-647. 
[GMS] Goldreich O.,, Mansour Y.,, and Sipser M.,, "Interactive Proof 
Systems: Provers that Never Fail and Random Selection", Proceedings of the 
28th FOCS, 1987, pp. 449-462. 
[GMW1] Goldreich, Oded, Sivio Micali, and Avi Wigderson. "Proofs that Yield 
Nothing but the Validity of the Assertion, and a Methodology of 
Cryptographic Protocol Design," Proceedings of the 27th FOCS, IEEE, 1986, 
174-187. 
[GMW2] Goldreich, Oded, Silvio Micali, and Avi Wigderson. "How to Play ANY 
Mental Game," Proceedings of the 19th STOC, ACM, 1987, 218-229. 
[GV] Goldreich, O., Vainish, R. "How to Solve any Protocol Problem: An 
Efficiency Improvement", Crypto 87. 
[GMR] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The Knowledge 
Complexity of Interactive Proof-Systems," Proceedings of the 17th STOC, 
ACM, 1985, 291-304. 
[HM] Hastad J., Mansour Y., "Private Communication" 
[K] Kilian, J. "On the Power of Oblivious Transfer," Proceedings of this 
conference 
[L] Lautemann C., "BPP and the Plynomial Time Hierarchy", IPL, 14, 1983, 
pp. 215-217. 
[R] Rabin, M., "How to exchange secrets by oblivious transfer", Tech. Memo 
TR-81, Aiken Computation Laboratory, Harvard University, 1981. 
[Yao82] Yao, Andrew C. "Protocols for Secure Computations," Proceedings of 
the 23rd FOCSA, IEEE, 1982, 160-164. 
[Yao86a] Yao, Andrew C. "How to Generate and Exchange Secrets," Proceedings 
of the 27th FOCS, IEEE, 1986, 162-167. 
[Yao86b] Yao, Andrew C. "Theory and Applications of Trapdoor Functions", 
Proc. of the 23rd FOCS, 1982, IEEE, pp. 80-91.