Cryptography Reference
In-Depth Information
subset sum, we refer to
addition over integers
; in the case of linear codes, we have
addition in vector spaces over a finite field
(typically of two elements); and in the case
of integer lattices,
the addition is of real vectors
(or of rational or integer vectors).
We mention that the decoding of random linear codes is a long-standing open prob-
lem in coding theory [207]. Regarding the complexity of lattice problems, there seems
to be a huge gap between the theoretical upper bounds [148] and the performance in
practice [195].
We refer the reader to a fascinating result by Ajtai [3] (cf. [101]): If certain com-
putational problems regarding integer lattices are hard
in the worst case
, then one-way
functions exist. This result is unique in translating possible worst-case hardness into
average-case hardness.
In view of the general efficient transformation of one-way functions to hard-core
predicates presented in Section 2.5, we did not present proofs that certain natural
predicates are hard-cores for specific popular candidates for one-way functions. Details
on hard-core predicates for the RSA and Rabin functions are available [82; cf. 5], as
are details on hard-core predicates for various “DLP functions” [141; cf. 36].
Tradition attributes to Yao a proof of the existence of hard-core predicates based on
any one-way function. The alleged proof proceeds in two steps. First, one proves the
existence of a mild form of a hard-core predicate; specifically, given a one-way function
f
, one construct a one-way function
f
and a polynomial-time-computable predicate
b
such that any probabilistic polynomial-time predictor given
f
(
U
n
)
fails
to guess
b
(
U
n
)
with probability
at least
1
,
i
) and
b
(
x
,
i
)bethe
i
th bit of
x
). The second step, which is the main one and is called
Yao's XOR Lemma
,istoprove
that taking many independent copies of such a “mild hard-core predicate” and XORing
them together will yield a hard-core predicate. That is, for
t
/
2
n
(e.g., let
f
(
x
,
i
)
=
(
f
(
x
)
=|
w
1
|
2
=···=|
w
t
|
2
,
we let
b
(
w
t
)) and
prove that
b
is a hard-core of
f
. Yao's XOR Lemma has found other applications in
complexity theory [114, 134].
The theory of average-case complexity, initiated by Levin [149], is somewhat related
to the notion of one-way functions. Surveys of this theory are available [24, 96]. Loosely
speaking, the difference is that in our context hard (on the average) instances can easily
be solved by the (efficient) “generator” of those instances, whereas in Levin's work
the instances are hard (on the average) to solve even for the “generator.” However,
the notion of average-case reducibility introduced by Levin is also relevant in our
context.
Further details about expander graphs and random walks on them are available
from [6, 167]. In particular, Lemma 2.6.5 is a special case of Kahale's Corollary 6.1
[139]. Explicit constructions of expander graphs have been published [85, 154], as has
the specific construction mentioned at the end of Section 2.6 [154].
w
1
,...,w
t
)
=⊕
i
1
b
(
w
i
) and
f
(
w
1
,...,w
t
)
=
(
f
(
w
1
)
,...,
f
(
=
2.7.3. Open Problems
As discussed in Section 2.1,
NP
\
BPP
= ∅
is a necessary condition for the existence
of one-way functions. However,
is not known to imply any practical
consequences (i.e., it may be that hard instances exist but occur very rarely with respect
NP
\
BPP
= ∅
