目录

3.3.1 Pseudorandom Generators

DEFINITION 3.14 伪随机发生器的定义

Example 3.15 不安全的发生器的例子

3.3.1 Pseudorandom Generators

伪随机发生器G是一种有效的、确定性的算法，用于将一个短的、均匀的字符串（称为种子）转换为一个更长的、“看起来是均匀的”（或“伪随机”）输出字符串。换句话说，伪随机发生器使用少量的真实随机性来产生大量的伪随机性。当需要大量的随机比特时，这是很有用的，因为生成真正的随机位通常是困难和缓慢的。伪随机发生器至少在20世纪40年代就开始被研究了，当时它们被用于运行统计模拟。正如不可分辨性是完善保密性的计算松弛一样，伪随机性也是真实随机性的计算松弛。

DEFINITION 3.14 伪随机发生器的定义

设G是一个确定性的多项式时间算法。对于任何n和任何输入s∈{0,1}^n，G(s)是长度为l(n)的字符串。如果以下条件成立，G是一个伪随机发生器：

1.扩张性：对于任意的 n 有 l(n)>n

2.伪随机性：对于任何ppt算法D，有一个可忽略函数negl，使得

Pr[D(G(s)) = 1] − Pr[D(r) = 1]≤ negl(n)

其中第一个概率是取s∈{0,1}^n的均匀选择和D的随机性，第二个概率是考虑r∈{0,1}^l(n)的均匀选择和D的随机性

我们称l(n)是G的膨胀系数

Example 3.15 不安全的发生器的例子

假设某个G(s)算法是在输入字符串的最后添加一位，这一位是前面 n 位的异或的结果。考虑以下有效的区分器D：输入为某个字符串w，当且仅当w的最后一个位等于w之前所有位的XOR时，该区分器输出1。因此我们的得到

 Pr[D(G(s)) = 1] = 1

但是对于均匀的字符串r，其最后一个比特位也是随机的

 Pr[D(r) = 1] = 1/2

此时Pr[D(G(s)) = 1] − Pr[D(r) = 1]=1/2，为一个常数，这是不可忽略的。所以G不是一个伪随机发生器