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.