Cryptography Reference
In-Depth Information
In a similar manner, one can modify all constructions presented in Section 3.4 to obtain
variable-output pseudorandom generators. In fact, in all constructions one can maintain
a hidden state that allows production of the next bit in the sequence in time polynomial
in the length of the seed, regardless of the number of bits generated thus far. This leads
to the notion of an on-line generator, as defined and studied in Exercise 21.
3.3.4. The Applicability of Pseudorandom Generators
Pseudorandom generators have the remarkable property of being efficient “ampli-
fiers/expanders of randomness.” Using very little randomness (in the form of a randomly
chosen seed) they produce very long sequences that look random with respect to any
efficient observer. Hence, the output of a pseudorandom generator can be used instead
of a “truly random sequence” in any efficient application requiring such (i.e., “random”)
sequences, the reason being that such an application can be viewed as a distinguisher.
In other words, if some efficient algorithm suffers non-negligible degradation in per-
formance when replacing the random sequences it uses by a pseudorandom sequence,
then this algorithm can be easily modified into a distinguisher that will contradict the
pseudorandomness of the latter sequences.
The generality of the notion of a pseudorandom generator is of great importance in
practice. Once we are guaranteed that an algorithm is a pseudorandom generator, we
can use it in every efficient application requiring “random sequences,” without testing
the performance of the generator in the specific new application.
The benefits of pseudorandom generators in cryptography are innumerable (and only
the most important ones will be presented in the subsequent chapters). The reason that
pseudorandom generators are so useful in cryptography is that the implementation of
all cryptographic tasks requires a lot of “high-quality randomness.” Thus the process
of producing, exchanging, and sharing large amounts of “high-quality random bits”
at low cost is of primary importance. Pseudorandom generators allow us to produce
(resp., exchange and/or share) poly( n ) pseudorandom bits at the cost of producing
(resp., exchanging and/or sharing) only n random bits!
3.3.5. Pseudorandomness and Unpredictability
A key property of pseudorandom sequences that is used to justify the use of such
sequences in some cryptographic applications is the unpredictability of a sequence.
Loosely speaking, a sequence is unpredictable if no efficient algorithm, given a prefix
of the sequence, can guess its next bit with a non-negligible advantage over
1
2 . Namely:
Definition 3.3.6 (Unpredictability): An ensemble { X n } n ∈N is called unpredict-
able in polynomial time if for every probabilistic polynomial-time algorithm A,
every positive polynomial p ( · ) , and all sufficiently large n's,
A 1 | X n | ,
X n =
next A ( X n ) <
1
2 +
1
p ( n )
Pr
where next A ( x ) returns the i
+
1 bit of x if on input (1 | x | ,
x ) algorithm A reads
Search WWH ::




Custom Search