Cryptography Reference
In-Depth Information
any distribution that we please, and draw adequate conclusions (as we
have done).
output sequence
seed
Gen
?
a truly random sequence
Fig. 3.1 Pseudorandom generators - an illustration.
3.2
Pseudorandom generators
Loosely speaking, a
pseudorandom generator
is an ecient (determinis-
tic) algorithm that on input of a short random
seed
outputs a (typically
much) longer sequence that is computationally indistinguishable from a
uniformly chosen sequence. Pseudorandom generators were introduced
by Blum, Micali and Yao (31; 123), and are formally defined as follows.
Definition 3.2.
(pseudorandom generator (31; 123)):
Let
:
N
→
N
satisfy
(
n
)
>n
, for all
n
.A
pseudorandom generator
,with
stretch
function
,isa
(deterministic)
polynomial-time algorithm
G
satisfying
the following:
∈
N
}
∗
, it holds that
(1) For every
s
∈{
0
,
1
|
G
(
s
)
|
=
(
|
s
|
).
(2)
{
U
(
n
)
}
n∈
N
are computationally indistin-
guishable, where
U
m
denotes the uniform distribution over
{
G
(
U
n
)
}
n∈
N
and
{
m
.
0
,
1
}
Indeed, the probability ensemble
{
G
(
U
n
)
}
n∈
N
is called
pseudorandom
.
Thus, pseudorandom sequences can replace truly random sequences
not only in “standard” algorithmic applications but also in crypto-
graphic ones. That is,
any
cryptographic application that is secure
when the legitimate parties use truly random sequences, is also secure
