Cryptography Reference
In-Depth Information
}
∗
→{
}
∗
be a polynomial-time computable function
:{
,
,
Definition 3.7
Let
G
0
1
0
1
: N → N
with stretch
. We say that
G
is
unpredictable
(or that
G
passes all next-bit
tests) if for every predictor
A
there exists a negligible function
negl
such that, for
every
s
,
G
(
s
)
and
i
as in the previous definition:
1
n
Pr
(A(
,
y
1
y
2
...
y
i
)
=
y
i
+
1
)
≤
1
/
2
+
negl
(
n
).
The interest of this definition is due to the following result of Yao [203] accord-
ing to which
unpredictability implies pseudo-randomness
([86, Theorem 3.3.7],
[6, Theorem 9.11] or [90, Theorem 3.10]):
}
∗
→{
}
∗
be a polynomial-time computable function
Theorem 3.3
Let G
:{
0
,
1
0
,
1
with stretch
: N → N
. Then G is a PRG if and only if G is unpredictable.
The distinguisher in the definition of PRG (Definition 3.4) may be regarded as a
statistical test trying to distinguish truly random sequences from sequences gener-
ated by
G
. Since the classical statistical tests are implemented as polynomial-time
algorithms, the previous theorem is sometimes stated in the following way:
G passes
all next-bit tests if and only if G passes all statistical tests
.
Exercise 3.10
Let
G
H
be pseudo-random generators with the same stretch func-
tion. Determine which of the following are also PRGs (you may have to consider
whether there is some correlation between the two PRGs):
,
(i)
¬
G
, where
¬
denotes the Boolean NOT or Boolean complement.
(ii)
G
∨
H
, where
∨
is the Boolean OR.
(iii)
G
⊕
H
.
3.3.2 One-Way Functions
We have already mentioned one-way functions which, as we shall see, are perhaps
the most important cryptographic primitive because they are necessary for such basic
things as secure encryption and digital signatures. The concept of one-way function
emerged from the development of public-key cryptography but later it was shown
that their existence is essentially equivalent to the existence of nontrivial private-key
cryptography: for example, the existence of one-way functions is equivalent to the
existence of pseudo-random generators. However, there are no unconditional proofs
of the existence of one-way functions and we do not know how to prove it even
assuming
which is only a necessary condition. But as we shall see later,
the existence of one-way functions can be proved under reasonable assumptions
relative to the hardness of certain computational problems.
Aone-way function is, informally speaking, a function
f
which is easy to compute
but hard to invert. Inmore precise terms this means that any PPT algorithmattempting
to invert the function on an element in its image, will succeed only with negligible
P
=
NP
