Design and Analysis of Provably Secure Pseudorandom Generators

Random numbers are used in a lot of applications. In particular, they are essential for most of the cryptographic systems. Pseudorandom generator is a mechanism for producing random numbers on a deterministic computer. A pseudorandom generator is said to be cryptographically secure if its output cannot be distinguished from uniformly random in a reasonable time. In some cases, it is possible to prove that a pseudorandom generator is cryptographically secure under an assumption that a mathematical problem is hard to solve. Such pseudorandom generators are called provably secure. This book accomplishes several goals. First, it presents the security analysis of several existing pseudorandom generators such as the classical RSA generator and the recently developed Dual Elliptic Curve generator. Second, it describes a new family of provably secure pseudorandom generators. Third, the security of complex cryptographic systems that use pseudorandom generators is analyzed. Finally, the book revisits the problem of converting random bits into random numbers. The book is intended for both mathematicians and engineers.