基于规则单项函数的伪随机产生器构造
(0) 本文研究基于规则单向函数的伪随机产生器,并提出了以下构造:(1)在任意已知规则度的(输入长度为n比特的)ε困难的单向函数基础上,为众所周知的伪随机产生器构造给出了一个简洁并且更紧致的证明,该构造的种子长度为O(n),并且只调用一次单项函数。(2)在任意未知规则度的ε困难的单向函数基础上,提出了一个新的构造,种子长度为O(n),并且调用单向函数的次数为O(n/log(1/ε)).这里的调用次数匹配了Holenstein和Sinha在FOCS2012给出的下界,因此是理想的。以上两个构造都要求ε是已知的,但可以去除对ε的依赖,与此同时保持几乎相同的参数。在后一个构造中,可以得到基于任意未知规则度单向函数的种子长度为O(n)且调用次数为O(n/log n)的伪随机产生器。这里的记号O忽略了一个可以任意接近常数的因子。构造优于Haitner等人在CRYPTO2006年上提出的构造,其构造要求种子长度为O(n *logn).
单项函数 伪随机产生器 可证明安全 计算复杂度
郁昱 李祥学 翁健
上海交通大学计算机系 上海 200240 华东师范大学计算机系 上海 200241 暨南大学信息科学技术学院 广州 510632
国内会议
西安
中文
1-16
2014-09-19（万方平台首次上网日期，不代表论文的发表时间）