Cryptography Reference
In-Depth Information
be specified that is able to distinguish the output of the PRBG from the output of a
true random bit generator with a success probability that is nonnegligibly larger than
1
/
2. Put in other words, there is no PPT algorithm that can distinguish the output of
a PRBG and the output of a random bit generator (of the same length) considerably
better than guessing.
In practice, PRBGs are important because they are used in many applications
to replace true random bit generators. This is advantageous because PRBGs use
much less randomness than true random bit generators (they still need randomness
and hence the quote of von Neumann still applies). Also, in an interactive setting, it is
possible to eliminate all random steps from the online computation and replace them
with the generation of pseudorandom bits based on a seed selected and fixed offline
(or at set-up time). The underlying assumption is that a cryptographic system that is
secure when the parties use a true random bit generator remains secure when they use
(only) a PRBG. For cryptographically secure PRBGs, we can have a “good feeling”
about this assumption; for practically relevant (or strong) PRBGs, we can at least
hope that the assumption holds. As soon as there is evidence that the assumption may
not hold, there is a strong incentive to replace these PRBGs with cryptographically
secure ones. In either case, if one has the choice, then there is good reason to go
for PRBGs that are cryptographically secure. In either case, it is a good idea to
periodically reseed the PRBG (even if it is a cryptographically secure one).
References
[1]
Knuth, D.E.,
The Art of Computer Programming—Volume 2: Seminumerical Algorithms
,3rdedi-
tion. Addison-Wesley, Reading, MA, 1997.
[2]
Plumstead, J., “Inferring a Sequence Generated by a Linear Congruence,”
Proceedings of the 23rd
IEEE Symposium on Foundations of Computer Science
, IEEE, Chicago, 1982, pp. 153-159.
[3]
Krawczyk, H., “How to Predict Congruential Generators,”
Journal of Algorithms
, Vol. 13, No. 4,
1992, pp. 527-545.
[4]
American National Standards Institute,
American National Standard X9.17: Financial Institution
Key Management
, Washington, DC, 1985.
[5]
U.S. National Institute of Standards and Technology (NIST),
Digital Signature Standard (DSS)
,
FIPS PUB 186, May 1994.
[6]
Kelsey, J., et al., “Cryptanalytic Attacks on Pseudorandom Number Generators,”
Proceedings of
the Fifth International Workshop on Fast Software Encryption
, Springer-Verlag, March 1998, pp.
168-188.
[7]
Gutmann, P., “Software Generation of Practically Strong Random Numbers,”
Proceedings of the
Seventh USENIX Security Symposium
, June 1998, pp. 243-255.
