Efficient And Secure Pseudo-Random Number Generation
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 458-463
- https://doi.org/10.1109/sfcs.1984.715948
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 (n/sup 2/ 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 x/sup 2/ mod N generator satisfy boolean predicates of these bits are secure. Furthermore, we strengthen the security of the x/sup 2/ mod N generator, which being a Trapdoor Generator, has several applications, by proving it as hard as Factoring.Keywords
This publication has 7 references indexed in Scilit:
- A Simple Unpredictable Pseudo-Random Number GeneratorSIAM Journal on Computing, 1986
- RSA/Rabin Bits are 1/2 + 1 / Poly (Log N) SecurePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Trapdoor pseudo-random number generators, with applications to protocol designPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- How discreet is the discrete log?Published by Association for Computing Machinery (ACM) ,1983
- Theory and application of trapdoor functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Why and how to establish a private code on a public networkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- How to generate cryptographically strong sequences of pseudo random bitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982