Cryptography Reference
In-Depth Information
indistinguishable, then
S
1
and
S
2
are not computationally indistinguishable. Incor-
porating
M
∗
into the distinguisher, it follows that
{
(
X
n
,
Z
n
)
}
n
∈N
and
{
(
X
n
,
Z
n
)
}
n
∈N
are not computationally indistinguishable either.
4.6.1.2. Witness-Hiding
We now turn to the notion of witness-hiding. Intuitively, a proof system for a language
in
NP
is witness-hiding if after interacting with the prover it is still infeasible for the
verifier to find an
NP
-witness for the common input. Clearly, such a requirement can
hold only if it is infeasible to find witnesses from scratch. Because each
NP
language
has instances for which witness-finding is easy, we must consider the task of witness-
finding for specially selected hard instances. This leads to the following definitions.
Definition 4.6.4 (Distribution of Hard Instances):
Let L
∈
NP
, and let R
L
def
={
X
n
}
n
∈N
be a probability ensemble such
be a witness relation for L. Let X
that X
n
ranges over L
n
. We say that X is
hard for
R
L
if for every
probabilistic polynomial-time (
witness-finding
) algorithm F , every polynomial
p
(
∩{
0
,
1
}
·
)
, all sufficiently large n's, and all z
∈{
0
,
1
}
poly(
n
)
,
1
p
(
n
)
Pr
[
F
(
X
n
,
z
)
∈
R
L
(
X
n
)]
<
For example, if
f
is a (length-preserving and non-uniformly) one-way function, then
the probability ensemble
{
f
(
U
n
)
}
n
∈N
is hard for the witness relation
{
(
f
(
w
)
,w
):
w
∈
}
∗
}
n
.
{
0
,
1
, where
U
n
is uniform over
{
0
,
1
}
Definition 4.6.5 (Witness-Hiding):
Let
(
P
,
V
)
,L
∈
NP
, and R
L
be as in the
foregoing definitions. Let X
={
X
n
}
n
∈N
be a hard-instance ensemble for R
L
.We
say that
(
P
V
)
is
witness-hiding for
the relation
R
L
under
the instance ensemble
X if for every probabilistic polynomial-time machine V
∗
, every polynomial p
(
,
·
)
,
all sufficiently large n's, and all z
∈{
0
,
1
}
∗
,
1
p
(
n
)
Pr
V
∗
(
z
)
[
P
(
Y
n
)
,
(
X
n
)
∈
R
L
(
X
n
)]
<
where Y
n
is arbitrarily distributed over R
L
(
X
n
)
.
We remark that the relationship between the two privacy criteria (i.e., witness indistin-
guishability and witness-hiding) is not obvious. Yet zero-knowledge proofs (for
)
are also witness-hiding (for any corresponding witness relation and any hard distribu-
tion). We mention a couple of extensions of Definition 4.6.5:
NP
1.
One can say that (
P
V
)
is witness-hiding for
R
L
under every ensemble of hard instances for
R
L
. (Alterna-
tively, one can require only that (
P
,
V
)is
universally witness-hiding for R
L
if the proof system (
P
,
,
V
) be witness-hiding for
R
L
under every
efficiently
constructible
17
ensemble of hard instances for
R
L
.)
17
See Definition 3.2.5.
