Efficient and Secure Pseudo-Random Number Generation (Extended Abstract)

Cryptographically secure pseudo-random number generators known so far suffer from the handicap of being inefficient; the most efficient ones can generate only one bit on each modular multiplication (n2 steps). Blum, Blum and Shub ask the open problem of outputting even two bits securely. We state a simple condition, the XOR-Condition, and show that any generator satisfying this condition can output logn bits on each multiplication. We also show that the logn least significant bits of RSA, Rabin’s Scheme, and the x2 mod N generator satisfy this condition. As a corollary, we prove that all boolean predicates of these bits are secure. Furthermore, we strengthen the security of the x2 mod N generator, which being a Trapdoor Generator, has several applications, by proving it as hard as Factoring.