| 一个新的伪随机生成器构造方案 |
| |
| 引用本文： | 程宽,毕经国. 一个新的伪随机生成器构造方案[J]. 中国科技论文在线, 2014, 0(4): 420-424 |
| |
| 作者姓名： | 程宽 毕经国 |
| |
| 作者单位： | [1] 清华大学计算机科学与技术系,北京100084 [2] 清华大学高等研究院,北京100084 |
| |
| 摘 要： | 伪随机生成器(pseudorandom generator,PRG)是当代密码学研究的一个基本结构。新方案基于格理论中的经典问题的困难性来构造PRG。首先根据多维子集和问题(multidimensional subset sum简称MSS)构造MSS单向函数,再使用单向迭代函数的方法构造新的PRG。使用一般单向函数的PRG构造方案,若单向函数输入长度是m,则要求种子长度达到O(m7)。相比之下,由于MSS单向函数有"大致正规"特性,新方案仅要求种子长度达到O(mlog m)。
|
| 关 键 词： | 计算复杂性理论 伪随机生成器 格问题 单向函数 |
Construction of a new pseudorandom generator |
| |
| Cheng Kuan,Bi Jingguo. Construction of a new pseudorandom generator[J]. Sciencepaper Online, 2014, 0(4): 420-424 |
| |
| Authors: | Cheng Kuan Bi Jingguo |
| |
| Affiliation: | 1. Department of Computer Science, Tsinghua University, I3eijing 100084, China ; 2. Institute for Advanced Study, Tsinghua University , Bei j ing 100084, China) |
| |
| Abstract: | 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）. |
| |
| Keywords: | computational complexity theory PRG lattice problem one-way function |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
