无止境的PRNG从PRNG与特定的伸展？

Question

我见过的伪随机生成器的每一个定义都说它使用n位字符串，并给出了poly(n)-bit字符串。

是否有证据证明，如果存在这样的伪随机生成器，那么就有一个伪随机生成器，它接受n位种子并根据请求重复输出位？

对于答案来说，我会好奇的事情并不重要：

• 它能被随机访问吗？(例如，人们可以有效地找到它的第m个输出)
• 能否使国家妥协不会提供关于早期产出的有用信息？

Answer 1

多项式(N)实际上是可证明密码学中形式主义的产物，实际意义不大。实际上，在PRNG循环之前，您可以从它获得固定数量的位。

从形式上讲，密码证明处理的并不是真的。在实践中，什么是多项式，什么不是多项式(注意，通常这并不意味着某些特定的多项式，对于任意的多项式)是没有意义的，因为n是固定的，并且有一些多项式将返回您想要的位数:多项式毕竟可以变得任意大。只有当我们谈到增长率时，它们才起到约束作用。

PRNG的形式定义是理论攻击者无法与实际RNG(即盖革计数器或其他东西)区分的函数，具有任何合理的可能性。

显然，拥有无限资源的攻击者只需尝试PRNG的所有可能种子，并查看它是否从PRNG获得输出。所以我们必须约束攻击者的能力。

按照通常的做法，我们说攻击者只能在多项式时间内作为某个安全参数(通常为n)的函数计算事物。由此可以看出，必须将函数的输出限制在n上的多项式上。