Cryptography Reference
In-Depth Information
: N → R
+
>
Definition 3.3
A function
f
is
negligible
if for every constant
c
0
n
−
c
for all
n
(
)<
>
there exists a positive integer
n
0
such that
f
n
n
0
.
Remark 3.2
diminishes to zero faster than the
reciprocal of any positive polynomial
p
, i.e., that for sufficiently large values of
n
,
f
f
being negligible means that
f
(
n
)
gets arbitrarily small for sufficiently large
n
.
Example 3.1
The functions 2
−
n
2
,2
−
n
,2
−
√
n
,
n
−
ln
n
and
n
−
ln ln
n
are inverses of
functions with faster than polynomial growth and hence all of them are negligible
but, as can readily be checked using Maple, they approach zero at widely different
rates.
(
n
)<
1
/
p
(
n
)
. In particular
f
(
n
)
n
−
c
Exercise 3.7
Prove that
f
is negligible if and only if
f
(
n
)
=
o
(
)
for every
c
>
0.
In the sequel we will denote by
negl
an arbitrary negligible function. Negligible
functions behave well vis-a-vis polynomial functions:
Exercise 3.8
Prove that the sum of two negligible functions is negligible and, more
generally, that the product of a positive polynomial by a negligible function is also
negligible (here, sum and product are interpreted as pointwise operations so that, for
example,
(
f
·
g
)(
n
)
=
f
(
n
)
·
g
(
n
)
).
As a consequence of the previous exercise, if the probability that an algorithm
produces a certain output on inputs of size
n
is negligible, then the probability that
it produces this output at least once when repeated polynomially many times is also
negligible. Thus a negligible probability can be ignored for all practical purposes.
Let us now see how the outlined idea may be applied to derive a practical encryp-
tion scheme from the one-time pad. To achieve this we want to use short keys to
encrypt much longer messages by means of the Xor operation. But to do that we
need to somehow
expand
the key to obtain a string as long as the message that can
be Xor-ed with it. The problem is that then this longer string will not be random
anymore, i.e., the strings of a given length obtained by “expanding” shorter strings
will not be sampled according to the uniform distribution. But, since we are assuming
now that our adversary is polynomially bounded, we no longer need that these strings
are random but just that they look random to the adversary. This idea is expressed by
saying that the strings obey a
pseudo-random
distribution, and in order to formalize
it we will consider a
distinguisher D
, i.e., a polynomial-time algorithm that outputs
'0' or '1' according to whether or not the input strings look random to it. Then a
probability distribution is
pseudo-random
if no polynomial-time distinguisher can
detect whether it is given a string sampled according to this distribution or according
to the uniform distribution. Bearing all this in mind, what we need to obtain long
pseudo-random strings from short random strings is a
pseudo-random generator
which is defined as follows:
Definition 3.4
Let
: N → N
be a polynomial-time computable function such that
(
n
)>
n
for every
n
∈ N
.Let
G
be a deterministic polynomial-time algorithm that,
