Cryptography Reference
In-Depth Information
an interaction of
V
Q
(with
P
Q
), whereas the simulated interactions are associated
with the other copies. Specifically, in ad
di
tion to the common input
x
, machine
V
∗
gets the appropriate
i
and the sequences
x
and (
w
1
,...,w
i
,w
i
+
2
,...,w
m
) as part
of its auxiliary input. For each
j
=
i
+
1, machine
V
∗
will use
x
j
as common input
and
w
j
as
au
xiliary input to the
j
th copy of
P
. Machine
V
∗
invokes
V
Q
on com-
mon input
x
and provides
it
an interface to a virtual interaction with
P
Q
. The
i
+
1
component of a message
α
=
(
α
1
,...,α
m
) sent by
V
Q
is forwarded to the prover
P
, and all other components are kept for the simulation of the other copies. When
P
answers with a message
β
, machine
V
∗
computes the answers for the other
copies of
P
(by feeding the program
P
the corresponding auxiliary input and the
corresponding sequence of incoming messages). It follows that
V
∗
can distinguish
the case in which
P
uses the witness
w
1
i
+
1
from the case in which
P
uses
w
2
i
+
1
.
This proof easily extends to the case in which several proof systems are executed
concurrently in a totally asynchronous manner (i.e., sequential and parallel executions
being two special cases).
18
The proof also extends to strong witness indistinguishability.
Thus we have the following:
Lemma 4.6.7 (Parallel Composition for Strong Witness Indistinguishability):
Let L
∈
NP
,R
L
,
(
P
,
V
)
,Q,R
L
, and P
Q
be as in Lemma 4.6.6. Then if P is
strongly witness-indistinguishable
(for
R
L
)
, then so is P
Q
(for
R
L
)
.
4.6.3. Constructions
In this section we present constructions of witness-indistinguishable and witness-hiding
proof systems.
4.6.3.1. Constructions of Witness-Indistinguishable Proofs
Using the parallel-composition lemma (Lemma 4.6.7) and the observation that zero-
knowledge proofs are (strongly) witness-indistinguishable, we derive the following:
Theorem 4.6.8:
Assuming the existence of (non-uniformly) one-way functions,
every language in
NP
has a
constant-round (strongly)
witness-indistinguishable
proof system with
negligible error probability
. In fact, the error probability can
be made exponentially small.
We remark that no such result is known for
zero-knowledge
proof systems. Namely, the
known proof systems for
NP
variously
•
are not constant-round (e.g., Construction 4.4.9), or
•
have noticeable error probability (e.g., Construction 4.4.7), or
18
That is, executions of polynomially many instances of the proof system are arbitrarily interleaved (in a
manner determined by the adversary); see suggestions for further reading in Section 4.12.2.
