Cryptography Reference
In-Depth Information
4.6.1.1. Witness Indistinguishability
Loosely speaking, an interactive proof for a language
L
∈
NP
is
witness-independent
(resp.,
witness-indistinguishable
) if the verifier's view of the interaction with the prover
is statistically independent (resp., “computationally independent”) of the auxiliary in-
put of the prover. Actually, we shall specialize the requirement to the case in which the
auxiliary input constitutes an
NP
-witness to the common input; namely, for a witness
relation
R
L
of the language
L
∈
NP
, we consider only interactions on common input
L
, where the prover is given an auxiliary input in
R
L
(
x
). By saying that the view
is
computationally independent
of the witness, we mean that for every two choices
of auxiliary inputs, the resulting views are computationally indistinguishable. Analo-
gously to the discussion in Section 4.3, we obtain equivalent definitions by considering
the verifier's view of the interaction with the prover or the verifier's output after such
an interaction. In the actual definition, we adopt the latter (i.e., “output”) formulation
and use the notation of Definition 4.3.10.
x
∈
Definition 4.6.1 (Witness Indistinguishability/ Independence):
Let
(
P
,
V
)
,L
∈
NP
and V
∗
be as in Definition 4.3.10, and let R
L
be a fixed witness relation
for the language L. We say that
(
P
,
V
)
is
witness-indistinguishable for
R
L
if
for every probabilistic polynomial-time interactive machine V
∗
and every two
sequences W
1
={
w
x
}
x
∈
L
and W
2
={
w
x
}
x
∈
L
, such that
w
x
,w
x
∈
R
L
(
x
)
, the
following two ensembles are computationally indistinguishable:
{
P
(
w
x
)
V
∗
(
z
)
,
(
x
)
}
x
∈
L
,
z
∈{
0
,
1
}
∗
{
P
(
w
x
)
V
∗
(
z
)
,
(
x
)
}
x
∈
L
,
z
∈{
0
,
1
}
∗
Namely, for every probabilistic polynomial-time algorithm D, every polynomial
p
(
·
)
, all sufficiently long x
∈
L, and all z
∈{
0
,
1
}
∗
, it holds that
Pr
D
x
P
x
V
∗
(
z
)
(
x
)
1
1
,
z
,
w
,
=
D
x
P
x
V
∗
(
z
)
(
x
)
1
<
1
p
(
|
x
|
)
2
−
Pr
,
z
,
w
,
=
We say that
(
P
,
V
)
is
witness-independent for
R
L
if the foregoing ensembles
are identically distributed. Namely, for every x
∈
L, every
w
1
x
2
x
,w
∈
R
L
(
x
)
, and
z
∈{
0
,
1
}
∗
, the random variables
P
(
w
x
)
,
V
∗
(
z
)
(
x
)
and
P
(
w
1
2
x
)
,
V
∗
(
z
)
(
x
)
are
identically distributed.
In particular,
z
may equal (
w
x
,w
x
). A few additional comments are in order:
•
Proof systems in which the prover ignores its auxiliary input are (trivially) witness-
independent. In particular, exponential-time provers can afford to ignore their auxiliary
input (without any decrease in the probability that they will convince the verifier) and so
can be trivially witness-independent. Yet probabilistic polynomial-time provers cannot
afford to ignore their auxiliary input (since otherwise they become useless). Hence,
for probabilistic polynomial-time provers (for languages outside
BPP
), the witness-
indistinguishability requirement may be non-trivial.
