Cryptography Reference
In-Depth Information
via
parallel
repetitions is problematic (in general) in this context; see the suggestions
for further reading at the end of the chapter.
The notion of zero-knowledge (for multi-prover systems) remains exactly as in the
one-prover case. Actually, we make the definition of perfect zero-knowledge more strict
by requiring that the simulator never fail (i.e., never outputs the special symbol
⊥
).
31
Namely:
Definition 4.11.3:
We say that a (two-prover) proof system
(
P
1
,
V
)
for a
language L is
perfect zero-knowledge
if for every probabilistic polynomial-time
interactive machine V
∗
there exists a probabilistic polynomial-time algorithm
M
∗
such that for every x
P
2
,
V
∗
(
x
)
and M
∗
(
x
)
∈
L the random variables
P
1
,
P
2
,
are identically distributed.
Extension to the auxiliary-input (zero-knowledge) model is straightforward.
4.11.2. Two-Sender Commitment Schemes
The thrust of the current section is toward a method for constructing perfect zero-
knowledge two-prover proof systems for every language in
NP
. This method makes
essential use of a commitment scheme
for two senders and one receiver
that possesses
information-theoretic secrecy and unambiguity properties (i.e., is perfectly hiding and
perfectly binding). We stress that it is impossible to achieve information-theoretic
secrecy and unambiguity properties simultaneously in the single-sender model.
4.11.2.1. A Definition
Loosely speaking, a two-sender commitment scheme is an efficient
two-phase
protocol
for the two-partner model through which the partners, called
senders
, can commit
themselves to a
value
such that the following two conflicting requirements are satisfied:
1.
Secrecy
: At the end of the
commit phase
, the solitary, called the
receiver
, does not gain
any
information
about the senders' value.
2.
Unambiguity
: Suppose that the commit phase is successfully completed. Then if later
the senders can perform the
reveal phase
such that the receiver accepts the value 0 with
probability
p
, then they cannot perform the
reveal phase
such that the receiver accepts
the value 1 with probability substantially greater than 1
p
. We stress that no interaction
is allowed between the senders throughout the
entire
commit and reveal process. (We
comment that for every
p
the senders can always conduct the commit phase such that
they can later reveal the value 0 with probability
p
and the value 1 with probability
1
−
−
p
. See Exercise 35.)
Instead of presenting a general definition, we restrict our attention to the special case of
two-sender commitment schemes in which only the first sender (and the receiver) takes
part in the commit phase, whereas only the second sender takes part in the (canonical)
reveal phase. Furthermore, we assume, without loss of generality, that in the reveal
31
Recall that in Definition 4.3.1, the simulator was allowed to fail (with probability at most
1
2
).
