常规单向函数的伪随机发生器：具有改进参数的新构造

在计算机科学领域中，伪随机数生成器（Pseudorandom Generators，简称PRGs）是一种能将短的随机种子转换为长的伪随机序列的算法。这些序列在统计性质上很难与真正的随机序列区分，但它们是由确定性算法产生的。单向函数（One-way Functions，简称OWFs）是一类函数，它们在计算上容易进行某种计算（例如，在算法上，函数的值可以被快速计算），但逆向计算却极其困难（即从函数的输出值反推输入值在计算上是不可行的）。基于单向函数构造伪随机数生成器是现代密码学的一个核心课题。 本文探讨了如何基于常规单向函数构造具有改进参数的伪随机数生成器。在给出的新构造中，研究者们首先考虑了已知正则性和已知困难度的单向函数。他们提供了一个构造方法，该方法仅通过一次调用底层单向函数，就能生成长度为Θ(n)的伪随机序列，其中n代表单向函数输入的比特数。这里的Θ(n)表示大O和小o的结合，即上界和下界都被考虑进来。对于这种构造方法，它们给出了一个简洁且严密的证明。 接着，研究者们为具有已知困难度但未知正则性的单向函数提供了一种新的构造方法。这种方法需要长度为Θ(n)的种子和O(n/log(1/ε))次函数调用，其中ε代表单向函数的难度度量。该方法的优点在于，函数调用的次数也是最优的，因为它匹配了Holenstein和Sinha在2012年提出的下限。此外，尽管这两种构造方法都需要了解ε的值，但是可以移除这种依赖性，同时保持几乎相同的参数。去除依赖性后，可以得到一个使用长度为˜O(n)的种子和˜O(n/logn)次函数调用的构造方法。这里的˜O表示忽略了一个可以任意接近常数的因子，例如logloglogn等。 文章还回顾了基础技术，比如伪熵和剩余哈希引理（leftover hash lemma），这些是之前由Håstad, Impagliazzo, Levin和Luby（HILL）在其开创性工作中提出的，它们为单向函数到伪随机数生成器的转化提供了理论基础。这些基础工具和概念在文献[2]中被提出，并已被后续研究广泛使用。 文章的另一贡献是对随机迭代方法的改进。Haitner等人在2006年提出的随机迭代方法需要O(n·logn)的种子长度和O(n/logn)的函数调用次数。而本文提出的方法在种子长度和函数调用次数上都有所改善。 在现代密码学中，伪随机数生成器的重要性不言而喻，它们被广泛应用于加密协议、密钥生成、密码系统等场合中。基于单向函数的伪随机数生成器提供了一种将单向性这一密码学基本性质转化为实践中的工具的途径。单向函数的良好定义保证了生成的序列具有必要的随机性，使得通过猜测来预测序列中的下一个比特变得不可行。 本文的成果，特别是提供了一种在种子长度和函数调用次数方面更为高效的构造方法，将有助于在实践中更为有效地利用伪随机数生成器。这对于资源受限的应用场景（如物联网设备）尤为重要，因为资源消耗的降低意味着可以将更多的计算资源用于其他任务，或者延长设备的运行时间。 总结来说，本文在理论计算机科学领域对单向函数和伪随机数生成器的关系做出了新的贡献，提出了新的构造方法，提高了构造的效率，并且对现有的方法给出了优化。这些成果对于密码学和信息安全的理论研究与实际应用都具有重要意义。