Pseudorandom Number Generators Based on One-Way Functions

Pseudorandom number generators (referred as PRNG) is an important cryptographic primitive that was first introduced and formalized as BMY generator in 1982. The PRNG based on one-way functions is constructed by iterating a one-way function (OWF) on a random seed and generating pseudorandom sequences periodically. The seed length and the property of the one-way function are two important factors of this kind PRNG, which measure the efficiency and the security of the PRNG. The security of the latest PRNG of this type relies on one-way function of length preserving or one-way permutation that is hard to be obtained. This paper revisits the current randomized iteration technique and makes improvement on the iteration process by expanding the outputs of one-way function. The new technique, which is called expanded randomized iteration, eliminates the length preserving property of the one-way function. On the basis of the expanded randomized iteration, our construction uses the general compression regular one-way function and universal hash function as the main components. In the BMY case, a hardcore-bit of each iteration step is taken as the output of the pseudorandom sequence. Our scheme adopts the similar structure as the current ones but relaxes the requirement of the property of the one-way function, reduces the seed length and improves the efficiency. Finally, the security of the iteration is proved irreversible and the security of the proposed pseudorandom generator is proved undistinguishable from the real random sequence.