基于单向函数的伪随机数发生器

Pseudorandom Number Generators Based on One-Way Functions

伪随机数发生器(pseudorandom number generator,PRNG)是重要的密码学概念.基于单向函数的伪随机数发生器起始于1982年的BMY发生器,将单向函数反复迭代,周期性地输出伪随机序列.单向函数的性质和种子长度关系到发生器的可实现性和安全性,是此类发生器的2个重要参数.在分析现有工作的基础上,改进了单向函数的随机化迭代方式,基于不可逆性证明了迭代过程的安全性.迭代方式的改进消除了单向函数的长度保持性质,采用一般的压缩规范单向函数和通用散列函数构建伪随机数发生器.输出级与BMY发生器结构类似,以迭代函数的核心断言作为伪随机序列.基于与真随机序列的不可区分性,证明了伪随机数发生器的安全性.所构建的伪随机数发生器与现有同类发生器结构类似,但放松了对单向函数性质的要求,增强了可实现性,减小了种子长度,提高了效率.

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 （（）WF） 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.