Cryptography Reference
In-Depth Information
1-opening) is computed by setting
s
i
=
π
−
1
(
c
i
) (resp.,
s
i
=
π
−
1
1)) for all
i
. Note
that the receiver's view of the commit phase equals the messages exchanged by the
verifier and the first prover, and these were generated in Step 1.
(
c
i
−
r
i
r
i
Note that the simulator's messages are distributed identically to the provers' messages
in the real interaction. (The only difference is in the way these messages are generated:
In the real interaction, the
s
i
's are selected uniformly in
{
1
,
2
,
3
}
and (together with the
r
i
's and the randomly permuted coloring) determine the
c
i
's, whereas in the simulation
the
c
i
's are selected uniformly in
{
1
,
2
,
3
}
and (together with the
r
i
's and a random pair
in
{
1
,
2
,
3
}
) determine the revealed
s
i
's.)
We remark that the entire argument extends easily to the case in which polynomi-
ally many instances of the protocol are performed concurrently. Thus, we obtain the
following:
Theorem 4.11.8:
Every language in
has a perfect zero-knowledge two-
prover proof system. Furthermore, this proof system has the following additional
properties:
NP
Communication is conducted in a single round: The verifier sends a single message
to each of the two provers, which in turn respond with a single message.
The soundness error is exponentially vanishing.
The strategies of the two provers can be implemented by probabilistic polynomial-
time machines that get an
NP
-witness as auxiliary input.
Efficiency Improvement.
A dramatic improvement in the efficiency of two-prover
(perfect) zero-knowledge proofs for
NP
can be obtained by relying on results regard-
ing probabilistically checkable proofs (PCPs). In particular, such proof systems, with
negligible error probability, can be implemented in probabilistic polynomial time, so
that the total number of bits exchanged in the interaction is poly-logarithmic.
4.11.4. Applications
Multi-prover interactive proofs are useful only in settings in which the “proving entity”
can be “split” into two (or more) parts and its parts kept ignorant of one another during
the proving process. In such cases, we get perfect zero-knowledge proofs without having
to rely on complexity-theoretic assumptions. In other words, general (widely believed)
intractability assumptions are replaced by physical assumptions concerning the specific
setting in which the proving process takes place.
One natural application is to the problem of identification and specifically the identi-
fication of a
user
at some
station
. In Section 4.7 we discuss how to reduce identification
to a zero-knowledge proof of knowledge (for some
NP
-relation). Here we suggest
supplying each user with two smart-cards, implementing the two provers in a two-
prover zero-knowledge proof of knowledge. These two smart-cards have to be inserted
in two different slots of the station, and this should guarantee that the smart-cards
cannot communicate with one another. The station will play the role of the verifier in
the zero-knowledge proof of knowledge. This way, the station is perfectly protected
against impersonation, whereas the users are perfectly protected against pirate stations
