Cryptography Reference
In-Depth Information
that are hard on the average. We mention that it is not known whether or not
P
=
NP
implies the existence of languages in
that are hard on the average.
Furthermore, the mere existence of problems (in
NP
NP
) that are hard on the average
does not suffice either. In order to be able to use such hard-on-the-average problems,
we must be able to generate hard instances together with auxiliary information that
will enable us to solve these instances fast. Otherwise, these hard instances will be
hard also for the legitimate users, and consequently the legitimate users will gain no
computational advantage over the adversary. Hence, the existence of secure encryption
schemes implies the existence of an efficient way (i.e., probabilistic polynomial-time
algorithm) to generate instances with corresponding auxiliary input such that
1.
it is easy to solve these instances given the auxiliary input, but
2.
it is hard, on the average, to solve these instances when not given the auxiliary input.
The foregoing requirement is reflected in the definition of one-way functions (as pre-
sented in the next section). Loosely speaking, a one-way function is a function that is
easy to compute but hard (on the average) to invert. Thus, one-way functions capture the
hardness of reversing the process of generating instances (and obtaining the auxiliary
input from the instance alone), which is responsible for the discrepancy between the
preceding two items. (For further discussion of this relationship, see Exercise 1.)
In assuming that one-way functions exist, we are postulating the existence of efficient
processes (i.e., the computation of the function in the forward direction) that are hard
to reverse. Note that such processes of daily life are known to us in abundance (e.g., the
lighting of a match). The assumption that one-way functions exist is thus a complexity-
theoretic analogue of daily experience.
2.2. One-Way Functions: Definitions
In this section, we present several definitions of one-way functions. The first version,
hereafter referred to as a strong one-way function (or just one-way function), is the
most popular one. We also present weak one-way functions, non-uniformly one-way
functions, and plausible candidates for such functions.
2.2.1. Strong One-Way Functions
Loosely speaking, a one-way function is a function that is easy to compute but hard to
invert. The first condition is quite clear: Saying that a function
f
is easy to compute
means that there exists a polynomial-time algorithm that on input
x
outputs
f
(
x
). The
second condition requires more elaboration. What we mean by saying that
a function
f is hard to invert
is that every probabilistic polynomial-time algorithm trying, on
input
y
, to find an inverse of
y
under
f
may succeed only with negligible (in
|
y
|
)
probability, where the probability is taken over the choices of
y
(as discussed later).
A sequence
{
s
n
}
n
∈N
(resp., a function
µ
:
N → R
) is called
negligible
in
n
if for every
positive polynomial
p
(
·
) and all sufficiently large
n
's, it holds that
s
n
<
1
p
(
n
)
(resp.,
1
µ
(
n
)
<
p
(
n
)
). Further discussion follows the definition.
32
