一个新的伪随机生成器构造方案

Construction of a new pseudorandom generator

伪随机生成器(pseudorandom generator,PRG)是当代密码学研究的一个基本结构。新方案基于格理论中的经典问题的困难性来构造PRG。首先根据多维子集和问题(multidimensional subset sum简称MSS)构造MSS单向函数,再使用单向迭代函数的方法构造新的PRG。使用一般单向函数的PRG构造方案,若单向函数输入长度是m,则要求种子长度达到O(m7)。相比之下,由于MSS单向函数有"大致正规"特性,新方案仅要求种子长度达到O(mlog m)。

Pseudorandom generator （PRG）is one of the fundamental primitives for modern cryptography study.The new con-struction is based on classical hard lattice problem.First the one-way function of multidimensional subset sum （MSS）is construc-ted.Then we complete the PRG construction by using the one-way iteration method.PRG construction for general one-way func-tion requires a seed length of O（m7 ）,where m is the input length of the one-way function.In contrast,since MSS one-way func-tion is almost regular,the new construction only requires a seed length of O（m log m）.