How to generate cryptographically strong sequences of pseudo-random bits. (English) Zbl 0547.68046
Summary: We give a set of conditions that allow one to generate 50-50 unpredictable bits. Based on those conditions, we present a general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits. We give an implementation of our scheme and exhibit a pseudo-random bit generator for which any efficient strategy for predicting the next output bit with better than 50-50 chance is easily transformable to an ”equally efficient” algorithm for solving the discrete logarithm problem. In particular: if the discrete logarithm problem cannot be solved in probabilistic polynomial time, no probabilistic polynomial-time algorithm can guess the next output bit better than by flipping a coin: if ”head” guess ”0”, if ”tail” guess ”1”.
MSC:
68P25 | Data encryption (aspects in computer science) |
94A60 | Cryptography |
65C10 | Random number generation in numerical analysis |