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
Search WWH ::




Custom Search