随机数提取器是一类输入伪随机源和一串真随机种子,输出真随机数的函数.1999年Trevisan等人通过分析伪随机数生成器与随机数提取器之间的关系,提出了一种构造随机数提取器的方法—Trevisan结构. Anindya De等人在2012年给出了Trevisan结构在量子边信息下的安全性分析.本文分析研究了Trevisan 随机数提取器结构的优缺点,针对其随机种子使用量较大的问题,利用输出反馈模式对随机种子进行预处理,通过结合简化的5圈DES算法对初始随机种子进行伪随机扩展的方法,一定程度上缩小了真随机种子的使用量.并将提取器结构模块化,设计了一类种子使用量较小且在量子边信息下安全的强随机数提取器.同时,给出了这类提取器在量子边信息下的安全性证明.最后,结合一比特提取器—Xor-code,给出了改进后提取器的具体实现参数及与 Trevisan 提取结构的对比分析.在理想情况下,利用输出反馈模式扩展随机种子的方法可以将真随机种子的使用量由原来的O(log3n)减少到O(logn).分析结果表明,本文设计了一类节约资源的量子边信息下安全的强随机数提取器.%An extractor is an algorithm that converts a “weak source of randomness” into an almost uniform distribution by using a small number of additional truly random seeds. In 1999, Trevisan demonstrated an unsuspected connection between extractors and pseudorandom generators and showed that every pseudorandom generator of a certain kind is an extractor——Trevisan construction. In 2012, Aninda De et al. showed that the construction for extractors proposed by Trevisan is sound in the presence of quantum side information. This paper analyzes the construction of Trevisan’s extractor. Considering the problem that the seed length used in Trevisan’s construction is large, we utilize the output feed back model for the seed preprocessing combined with simplified 5-round DES to expend the initial uniform seed and give a modular framework for randomness extractor, then we devise a short seed quantum-proof strong extractor and prove that our construction is sound in the presence of quantum side information. Finally, combined with 1-bit extractor——Xor-code, we give the concrete parameter of our extractor construction and the contrastive analysis with Trevisan’s. The results show that using the output feed back model for preprocessing, it can reduce the truly random seed from O(log3n) to O(logn). So our extractor construction is an efficient quantum-proof strong extractor which can save resources.
展开▼
