Cryptography Reference
In-Depth Information
existence of zero-knowledge proof systems for languages that are hard to approxi-
mate (in some average-case sense) implies the existence of one-way functions (but not
of non-uniformly one-way functions). In the rest of this subsection we merely provide
precise statements of these results.
Non-Triviality of ZK Implies Weak Forms of One-Wayness.
By the non-triviality of
zero-knowledge we mean the existence of zero-knowledge proof systems for languages
outside of
(as the latter have trivial zero-knowledge systems in which the prover
does nothing). Let us clarify what we mean by “weak forms of one-wayness.” Our
starting point is the definition of a collection of one-way functio
ns
(i.e., Definition 2.4.3).
Recall that these are collections of functions, indexed by some
I
⊆{
0
,
1
}
∗
, that are easy
to s
am
ple and evaluate but
typically
hard to invert. That is, a typical function
f
i
(for
i
∈
I
) is hard to invert on a typical image. Here we require only that there exist functions
in the collection that are hard to invert on a typical image.
BPP
Definition 4.5.4 (Collection of Functions with One-Way Instances):
A collec-
tion of functions
}
∗
}
i
∈
I
is said to
have one-way instances
if there
exist three probabilistic polynomial-time algorithms I , D, and F such that the
following two conditions hold:
{
f
i
:
D
i
→{
0
,
1
1.
Easy to sample and compute:
As in Definition 2.4.3.
2.
Some functions are hard to invert:
For every probabilisti
c
polynomial-time algo-
rithm A
, every polynomial p
(
·
)
, and infinitely many i
∈
I,
Pr
A
(
i
(
f
i
(
X
i
))
<
1
p
(
f
−
1
i
,
f
i
(
X
i
))
∈
|
i
|
)
where X
i
=
D
(
i
)
.
Actually, because the hardness condition does not refer to the dist
ri
bution induced by
I
, we can omit
I
from the definition and refer only to the index set
I
. Such a collection
contains infinitely many functions that are hard to invert, but there may be no efficient
way of selecting such a function (and thus the collection is of no real value). Still, we
stress that the hardness condition has an average-case flavor; each of these infinitely
many functions is hard to invert in a strong probabilistic sense, not merely in the worst
case.
Theorem 4.5.5:
If there exist zero-knowledge proofs for languages outside of
BPP
, then there exist collections of functions with one-way instances.
We remark that the mere assumption that
is not known to imply any
form of (average) one-wayness. Even the existence of a language in
BPP
⊂
IP
NP
that is not
in
does not imply any form of average-case hardness; it merely implies the
existence of a function that is easy to compute but hard to invert
in the worst case
(see
Section 2.1).
BPP