Cryptography Reference
In-Depth Information
+
,
X
n
and
Y
n
refer to probability
be two probability ensembles. For every
n
∈
N
n
,
and
t
is selected according to the probability distribution
X
n
(
Y
n
). We then say that
X
is
poly-time indistinguishable
from
Y
if for every PPT algorithm
D
and every
polynomial
p
, there exists a
n
0
∈
N
n
.Bysaying
t
distributions on
{
0
,
1
}
∈
X
n
(
t
∈
Y
n
), we mean that
t
∈{
0
,
1
}
+
such that for all
n>n
0
1
p
(
n
)
.
|
Pr
t∈X
n
[
D
(
t
)=1]
−
Pr
t∈Y
n
[
D
(
t
)=1]
|≤
This means that for sufficiently large
t
, no PPT algorithm
D
can tell whether
it was sampled according to
X
n
or
Y
n
. In some literature, the PPT algorithm
D
is
also called
polynomial-time statistical test
or
distinguisher
(the letter “D” is chosen
to refer to a distinguisher). In either case, it is important to note that such a definition
cannot make sense for a single string
t
(as it can be drawn from either distribution).
In computational complexity theory, it is assumed and widely believed that
computationally indistinguishable probability ensembles exist. This assumption is
sometimes referred to as the general indistinguishability assumption.
Having the general indistinguishability assumption in mind, we say that
{
X
n
}
is
pseudorandom
if it is poly-time indistinguishable from
{
U
n
}
,where
U
n
denotes
n
. More specifically, this means that
for every PPT algorithm
D
and every polynomial
p
, there exists a
n
0
∈
N
the uniform probability distribution on
{
0
,
1
}
+
such
that for all
n>n
0
1
p
(
n
)
.
|
Pr
t∈X
n
[
D
(
t
)=1]
−
Pr
t∈U
n
[
D
(
t
)=1]
|≤
We are now ready to formally define the notion of a cryptographically secure
PRBG. This is done in Definition 12.1.
Definition 12.1 (Cryptographically secure PRBG)
Let
G
be a PRBG with stretch
function
l
:
N
→
N
(i.e.,
l
(
n
)
>n
for all
n
∈
N
).
G
is
cryptographically secure
if it
satisfies the following two conditions:
}
∗
;
•|
G
(
s
)
|
=
l
(
|
s
|
)
for every
s
∈{
0
,
1
•{
G
(
U
n
)
}
is pseudorandom (i.e., it is poly-time indistinguishable from
{
U
l
(
n
)
}
).
The first condition captures the stretching property of the PRBG (i.e., the fact
that the output of the PRBG is larger than its input), and the second condition cap-
tures the property that the generated pseudorandom bit sequence is computationally
