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

程宽; 毕经国

0
0
浏览
下载

摘要
关键词
基金信息
论文图表
同行评议
相关论文
评论

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

首发时间：2014-05-20

程宽 ¹
程宽（1988—），男，硕士研究生，主要研究方向为密码学
毕经国 ²
毕经国，博士后，主要研究方向为密码学

1、清华大学计算机科学与技术系, 北京 100084
2、清华大学高等研究院, 北京 100084

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

关键词：计算复杂性理论伪随机生成器格问题单向函数

For information in English, please click here

Construction of a new pseudorandom generator

Cheng Kuan ¹
程宽（1988—），男，硕士研究生，主要研究方向为密码学
Bi Jingguo ²
毕经国，博士后，主要研究方向为密码学

1、Department of Computer Science, Tsinghua University, Beijing 100084, China
2、Institute for Advanced Study, Tsinghua University, Beijing 100084, China

Abstract：Pseudorandom generator (PRG) is one of the fundamental primitives for modern cryptography study. The new construction is based on classical hard lattice problem. First the one-way function of multidimensional subset sum (MSS) is constructed. Then we complete the PRG construction by using the one-way iteration method. PRG construction for general one-way function requires a seed length of O(m7), where m is the input length of the one-way function. In contrast, since MSS one-way function 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

基金：

论文图表：

引用

导出参考文献

.txt

.ris

.doc

程宽，毕经国. 一个新的伪随机生成器构造方案[EB/OL]. 北京：中国科技论文在线 [2014-05-20]. https://www.paper.edu.cn/releasepaper/content/201405-341.

No.4597231222691399****

同行评议

未申请同行评议

全部评论

0/1000

论文编号	201405-341
论文题目	一个新的伪随机生成器构造方案
文献类型
收录期刊	上传封面中文期刊英文期刊期刊名称（中文）期刊名称（英文）年，卷（）上传封面中文专著英文专著书名（中文）书名（英文）出版地出版社出版年上传封面中文译著英文译著书名（中文）书名（英文）出版地出版社出版年上传封面中文论文集英文论文集编者.论文集名称（中文） [c]. 出版地出版社出版年， - 编者.论文集名称（英文） [c]. 出版地出版社出版年，- 上传封面中文文献英文文献期刊名称（中文）期刊名称（英文）日期-- 在线地址http:// 上传封面中文文献英文文献文题（中文）文题（英文）出版地出版社,出版日期-- 上传封面中文文献英文文献文题（中文）文题（英文）出版地出版社,出版日期--
英文作者写法：中外文作者均姓前名后，姓大写，名的第一个字母大写，姓全称写出，名可只写第一个字母，其后不加实心圆点“.”, 作者之间用逗号“，”分隔，最后为实心圆点“.”, 示例1：原姓名写法：Albert Einstein,编入参考文献时写法：Einstein A. 示例2：原姓名写法：李时珍；编入参考文献时写法：LI S Z. 示例3：YELLAND R L,JONES S C,EASTON K S,et al.