Cryptography Reference
In-Depth Information
2.
Variants of the foregoing definitions, in which the auxiliary input
z
is replaced by a
distribution
Z
n
that may depend on
X
n
, are of interest too. Here we consider en-
sembles
n
. Such an ensemble is
hard
for R
L
if for every probabilistic polynomial-time algorithm
F
, the probability that
F
(
X
n
,
{
(
X
n
,
Z
n
)
}
n
∈N
, where
X
n
ranges over
L
∩{
0
,
1
}
Z
n
)
∈
R
L
(
X
n
) is negligible. The system (
P
,
V
) is witness-hiding for
R
L
under
}
n
∈N
if for every probabilistic polynomial-time verifier
V
∗
, the probability that
{
(
X
n
,
Z
n
)
V
∗
(
Z
n
)
P
(
Y
n
)
,
(
X
n
)
∈
R
L
(
X
n
) is negligible.
4.6.2. Parallel Composition
In contrast to zero-knowledge proof systems, witness-indistinguishable proofs offer
some robustness under parallel composition. Specifically, parallel composition of
witness-indistinguishable proof systems results in a witness-indistinguishable system,
provided that the original prover is probabilistic polynomial-time
.
Lemma 4.6.6 (Parallel-Composition Lemma for Witness Indistinguish-
ability):
Let L
and R
L
be as in Definition 4.6.1, and suppose that P
is probabilistic polynomial-time and
(
P
∈
NP
,
V
)
is
witness-indistinguishable (resp.,
witness-independent)
for R
L
. Let Q
(
)
be a polynomial, and let P
Q
denote a
program that on common input x
1
,...,
·
x
Q
(
n
)
∈{
0
,
1
}
n
and auxiliary input
}
∗
invokes P in parallel Q
(
n
)
times, so that in the i th copy
P is invoked on common input x
i
and auxiliary input
w
1
,...,w
Q
(
n
)
∈{
0
,
1
w
i
. Then P
Q
is
witness-
indistinguishable (resp., witness-independent)
for
R
L
def
={
(
x
,w
):
∀
i
,
(
x
i
,w
i
)
∈
R
L
}
where x
=
(
x
1
,...,
x
m
)
and
w
=
(
w
1
,...,w
m
)
, so that m
=
Q
(
n
)
and
|
x
i
|=
n
for each i .
Proof Sketch:
Both the computational and information-theoretic versions fol-
low by a hybrid argument. We concentrate on the computational version. To avoid
cumbersome notation, we consider a generic
n
for which the claim of the lemma
fails. (By contradiction, there must be infinitely many such
n
's, and a precise argu-
ment will actually handle all these
n
's together.) Namely, sup
po
se that by using a
veri
fier
program
V
Q
it is feasible to distinguish the witnesses
w
1
1
1
1
=
(
w
,...,w
m
)
2
2
1
2
and
w
m
) used by
P
Q
in an interaction on common input
x
∈
L
m
. Then for some
i
, the program
V
Q
al
so distinguishes the hybrid witnesses
h
(
i
)
=
(
w
,...,w
m
) and
h
(
i
+
1)
1
1
1
i
2
i
+
1
2
1
1
1
i
+
1
2
i
+
2
2
=
(
w
,...,w
,w
,...,w
=
(
w
,...,w
,w
,...,w
m
).
Rewrite
h
(
i
)
,w
i
+
2
,...,w
m
) and
h
(
i
+
1)
=
(
w
1
,...,w
i
,w
i
=
(
w
1
,...,w
i
,w
i
,
+
1
+
1
def
=
w
def
=
w
w
i
+
2
,...,w
m
), where
2. We derive a
contradiction by constructing a verifier
V
∗
that distinguishes (the witnesses used
by
P
in) interactions with the original prover
P
. Details follow.
The program
V
∗
incorporates the programs
P
and
V
Q
and proceeds by inter-
acting with the actual prover
P
and simulating
m
w
j
j
if
j
≤
i
, and
w
j
j
if
j
≥
i
+
1 other interactions with (a
copy of program)
P
. The real interaction with
P
is viewed as the
i
−
+
1 copy in
