Cryptography Reference
In-Depth Information
(1) The distribution X (in our case {G ( U n ) } n∈ N ) is pseudoran-
dom (i.e., is computationally indistinguishable from a uni-
form distribution (on
U ( n ) } n∈ N )).
(2) The distribution X is unpredictable in polynomial-time; that
is, no feasible algorithm, given a prefix of the sequence, can
guess its next bit with a non-negligible advantage over
{
1
2 .
Clearly, pseudorandomness implies polynomial-time unpredictabil-
ity (i.e., polynomial-time predictability violates pseudorandomness).
The converse is shown using a hybrid argument, which refers to
hybrids consisting of a prefix of X followed by truly random bits
(i.e., a su x of the uniform distribution). Thus, we focus on prov-
ing that G ( U n ) is polynomial-time unpredictable, where G ( s )=
b ( f ( |s| ) 1 ( s ))
b ( s ) is the reverse of G ( s ).
Suppose towards the contradiction that, for some j< de = ( n ),
given the j -bit long prefix of G ( U n ) an algorithm A can predict the
j +1 st
···
b ( f ( s ))
·
b ( f −j ( s )), algo-
rithm A predicts b ( f ( j +1) ( s )), where s is uniformly distributed in
{
bit of G ( U n ). That is, given b ( f 1 ( s ))
···
n ,given y = f ( x )
one can predict b ( x )byinvoking A on input b ( f j− 1 ( y ))
n . Then, for x uniformly distributed in
0 , 1
}
{
0 , 1
}
b ( y )=
b ( f j ( x )) ···b ( f ( x )), which in turn is polynomial-time computable from
y = f ( x ). In the analysis, we use the hypothesis that f induces a per-
mutation over
···
n , and associate x with f ( j +1) ( s ).
We mention that the existence of a pseudorandom generator with
any stretch function (including the very minimal stretch function
( n )= n + 1) implies the existence of pseudorandom generators
for any desired stretch function. The construction is similar to the
one presented in Theorem 3.3. That is, for a pseudorandom gener-
ator G 1 ,let F ( x )(resp , B ( x )) denote the first
{
0 , 1
}
|
x
|
bits of G 1 ( x )
+1 st
|x|
bit of G 1 ( x )), and consider G ( s )= B ( s )
·
(resp., the
B ( F ( |s| ) 1 ( s )), where is the desired stretch. Although F is
not necessarily 1-1, it can be shown that G is a pseudorandom generator
(65, Sec. 3.3.2).
We conclude this section by mentioning that pseudorandom gen-
erators can be constructed from any one-way function (rather than
merely from one-way permutations, as above). On the other hand, the
B ( F ( s ))
···  Search WWH ::

Custom Search