基于任意单向函数的伪随机产生器关键理论与方法研究

The construction of pseudorandom generators from one-way functions constitutes one of the central pieces in cryptography. Currently, the research mainly follows two lines: one is the parallel construction that bases the generator on an arbitrary one-way function with the the HILL generator as a typical example; the other is the sequential construction that builds the generator from special one-way functions (e.g., one-way permutations, regular one-way functions) with examples being the BMY generator, the "randomized iterate" and the YLW construction recently presented at Asiacrypt 2013. For any one-way function on security parameter n, the seed length is the most important criteria for the efficiency of the construction, and is optimally linear in n. As for the latter, best known constructions already achieve linear seed length. This research project focuses on the first line of research, namely, to build more efficient generators from any one-way functions, and to improve upon the existing consructions by resolving issues such as large seed length (we aim at reducing seed length to n square or even less), inefficient constructions, and complicated and loose proofs. This makes the proposed project both of theoretic interest and application value.

从单向函数构造伪随机产生器是密码学中最重要的基本问题之一，所构造伪随机产生器的种子长度是评价伪随机产生器效率的最重要指标。该问题当前的研究方向主要包括两类：一是基于一般单向函数的并行方法，以HILL构造以及后续的系列优化工作为代表；二是基于某些特殊单向函数（如单向置换、规则单向函数等）的串行方法，以BMY构造、随机重复构造、申请人在Asiacrypt2013年会提出的构造为代表。后者目前已经达到理想的线性种子长度（即O(n)），前者则存在构造复杂、种子长度长（至少要n的三次）、证明归约松散、不具备实际应用价值等问题。因此，本项目重点研究基于任意单向函数的伪随机产生器并行构造，优化种子长度、单向函数的调用次数等参数，降低种子长度至n平方或以下，以构造的简单高效性和归约证明的紧致性为目标，使构造不仅具有较强的理论价值，也具有较高的实用价值。

单向函数是密码学的最基础假设，伪随机数生成器是密码学重要原语之一，本项目旨在研究如何基于单向函数构造高效的伪随机数生成器，之前给出的方案存在构造复杂、种子长度过大、证明归约松散、效率等问题限制了其实用价值。本项目主要研究目标包括：基于任意单向函数并行构造伪随机数生成器；基于特殊的规则单向函数构造高效实用的伪随机数生成器。在本项目执行期内，取得了如下成果：(1)基于任意单向函数的种子长度为O(n*log n)的伪随机数生成器；(2) 基于任意单向函数的种子长度为O(n)及只需一次调用单向函数的理想伪随机数生成器；(3)基于LPN困难问题构造了常数电路深度的伪随机数生成器和可在任意(渐进意义下)超常数(如logloglogN)的电路深度内实现的伪随机函数，紧致匹配了俄罗斯科学院院士Razborov在发表于STOC 1994的2007年哥德尔奖获奖论文 “Natural Proofs”中给出的“任意常数深度电路中不存在伪随机随机函数”的负面结论；(4)改进了马里兰大学教授Katz和MIT教授Vaikuntanathan在ASIACRYPT 2009提出的三轮PAKE认证协议，提出了首个二轮PAKE认证协议；(5) 利用图灵奖得主Goldwasser的“随机子空间采样”技术解决了Dodis等人在STOC 2009上提出的LPN在辅助输入模型下安全性的公开问题，并在此基础上进一步基于标准LPN IND-CCA安全的公钥加密方案，解决了Aleknovich在FOCS 2003上留下的“常数噪声LPN是否蕴含公钥密码”的公开问题。此外，设计的伪随机数生成器还具有抗旁路泄漏的鲁棒性等优点，具有较好的实用价值。在项目执行期内，项目负责人入选了2016教育部青年长江学者，在密码学顶级会议CRYPTO、EUROCRYPT上一作发表3篇论文，此外还发表了包括CCF A类的TIFS等SCI期刊9篇，EI论文15篇，均标注本项目资助。

内容获取失败，请点击重试