Cryptography Reference
In-Depth Information
Negligible Probability
A few words concerning the notion of negligible probability are in order. The foregoing
definition and discussion consider the success probability of an algorithm to be
neg-
ligible
if, as a function of the input length, the success probability is bounded above
by every polynomial fraction. It follows that repeating the algorithm polynomially (in
the input length) many times yields a new algorithm that also has negligible success
probability. In other words, events that occur with negligible (in
n
) probability remain
negligible even if the experiment is repeated for polynomially (in
n
) many times. Hence,
defining a negligible success rate as “occurring with probability smaller than any poly-
nomial fraction” is naturally coupled with defining feasible computation as “computed
within polynomial time.”
A “strong negation” of the notion of a negligible fraction/probability is the notion
of a noticeable fraction/probability. We say that a function
is
noticeable
if there exists a polynomial
p
(
·
) such that for all sufficiently large
n
's, it holds that
µ
(
n
)
>
ν
:
N → R
1
p
(
n
)
. We stress that functions may be neither negligible nor noticeable.
2.2.2. Weak One-Way Functions
One-way functions, as defined earlier, are one-way in a very strong sense. Namely, any
efficient inverting algorithm has negligible success in inverting them. A much weaker
definition, presented next, requires only that all efficient inverting algorithms fail with
some noticeable probability.
Definition 2.2.2 (Weak One-Way Functions):
A function f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
is called
weakly one-way
if the following two conditions hold:
1.
Easy to compute:
As in the definition of a strong one-way function.
2.
Slightly hard to invert:
There exists a polynomial p
(
)
such that for every proba-
bilistic polynomial-time algorithm A
and all sufficiently large n's,
·
1
p
(
n
)
[
A
(
f
(
U
n
)
1
n
)
f
−
1
(
f
(
U
n
))]
Pr
,
∈
>
We call the reader's attention to the order of quantifiers: There exists a
single
poly-
nomial
p
(
p
(
n
) lower-bounds the failure probability of
all
probabilistic
polynomial-time algorithms trying to invert
f
on
f
(
U
n
).
Weak one-way functions fail to provide the kind of hardness alluded to in the earlier
motivational discussions. Still, as we shall see later, they can be converted into strong
one-way functions, which in turn do provide such hardness.
·
) such that 1
/
2.2.3. Two Useful Length Conventions
In the sequel it will be convenient to use the following two conventions regarding the
lengths
of the pre-images and images of one-way functions. In the current section we
justify the use of these conventions.
