Cryptography Reference
In-Depth Information
to any simple distribution). Any progress in showing that
implies
some form of average-case hardness, and that the latter implies the existence of one-
way functions would be of great interest.
Turning to relatively less ambitious goals, we mention two open problems that pertain
to extending the results of the type presented in this chapter. We believe that a resolution
for either of these problems will require the discovery of new important paradigms.
Firstly, in a continuation of the efficient amplification of one-way permutations (pre-
sented in Section 2.6), we seek an analogous transformation that can be applied to
arbitrary
(weak) one-way functions. Currently, we know of such transformations only
for special types of functions (e.g., regular ones [104]). We believe that providing an ef-
ficient amplification of arbitrary one-way functions is a very important open problem. It
may also be instrumental for more efficient constructions of pseudorandom generators
based on arbitrary one-way functions (see Section 3.5).
An open problem of more acute practical importance is to try to present hard-core
functions
of larger range for the RSA and Rabin functions. Specifically, assuming that
squaring mod
N
is one-way, is the function that returns the first half of
x
a hard-core
of squaring mod
N
? Some support for an affirmative answer has been provided [130].
An affirmative answer would allow us to construct extremely efficient pseudorandom
generators and public-key encryption schemes based on the conjectured intractability
of the factoring problem.
NP
\
BPP
= ∅
2.7.4. Exercises
Exercise 1:
Closing the gap between the motivating discussion and the definition of
one-wayfunctions: We say that a function h:
{
0, 1
}
∗
→{
0, 1
}
∗
is hardontheaverage
but easy with auxiliary input if there exists a probabilistic polynomial-time algorithm G
such that
1.
there exists a polynomial-time algorithm Asuch that A(x, y)
=
h(x) for every (x, y) in the
range of G (i.e., for every (x, y) such that (x, y) is a possible output of G(1
n
) for some
input 1
n
), and
2.
for every probabilistic polynomial-time algorithm A
every positive polynomial p(
·
), and
all sufficiently large n's,
1
p(n)
Pr[ A
(X
n
)
=
h(X
n
)]
<
where (X
n
, Y
n
)
def
G(1
n
) is a random variable assigned the output of G.
Prove that if there exist functions that are “hard on the average but easy with auxiliary
input,” then one-way functions exist.
Guideline:
Define a function mapping the coins used by Gto its first output.
=
Exercise 2:
One-way functions and the
P
-versus-
NP
question (Part 1): Prove that
the existence of one-way functions implies
.
Guideline:
For any polynomial-time-computable function f, define a set L
f
∈ NP
such
that if L
f
∈ P
, then there exists a polynomial-time algorithm for inverting f.
P
=
NP
