Cryptography Reference
In-Depth Information
ZK for “Hard” Languages Yields One-Way Functions.
Our notion of hard languages
is the following:
Definition 4.5.6:
We say that a language L is
hard to approximate
if there
exists a probabilistic polynomial-time algorithm S such that for every proba-
bilistic polynomial-time algorithm A, every polynomial p
(
·
)
, and all sufficiently
large n's,
1
2
+
1
p
(
n
)
Pr
[
A
(
X
n
)
=
χ
L
(
X
n
)]
<
def
=
S
(1
n
)
, and
where X
n
χ
L
is the characteristic function of the language L (i.e.,
χ
L
(
x
)
=
1
if x
∈
L, and
χ
L
(
x
)
=
0
otherwise).
For example, if
f
is a one-way permutation and
b
is a hard-core predicate for
f
, then
the language
L
f
def
={
x
∈{
0
,
1
}
∗
:
b
(
f
−
1
(
x
))
=
1
}∈
NP
is hard to approximate (under
the uniform distribution).
Theorem 4.5.7:
If there exist zero-knowledge proofs for languages that are hard
to approximate, then there exist one-way functions.
We stress that the mere existence of languages that are hard to approximate is not known
to imply the existence of one-way functions (see Section 2.1).
4.5.3. Limitations of Statistical ZK Proofs
A theorem bounding the class of languages possessing
perfect
zero-knowledge proof
systems follows. In fact, the bound refers even to
statistical
(i.e.,
almost-perfect
) zero-
knowledge proof systems (see Section 4.3.1.4). We start with some background. By
AM
we denote the class of languages having interactive proofs that proceed as follows.
First the verifier sends a random string to the prover, next the prover answers with some
string, and finally the verifier decides whether to accept or reject based on a deterministic
computation (depending on the common input and the two strings). It is believed that
co
NP
is not contained in
AM
(or, equivalently,
NP
is not contained in co
AM
).
Additional support for this belief is provided by the fact that co
implies the
collapse of the Polynomial-Time Hierarchy. In any case, the result we wish to mention
is the following:
NP
⊆
AM
Theorem 4.5.8:
If there exists a statistical (almost-perfect) zero-knowledge proof
system for a language L, then L
AM
AM
∩
AM
∈
co
.
(
In fact, L
∈
co
.
)
The theorem remains valid under several relaxations of statistical zero-knowledge
(e.g., allowing the simulator to run in expected polynomial-time). Hence, if some
NP
NP
⊆
-complete language has a statistical zero-knowledge proof system, then co
AM
, which is unlikely.
