伪随机数发生器定理

1.1 伪随机性

如果没有有效的计算方法能够以不可忽略的优势将某种分布与真实的均匀分布区分开来，则该分布被认为是伪随机的。形式上，分布族Dn是伪随机的条件是，如果对于任何多项式大小电路C和n中的任何ε逆多项式：

|Prob _x∈U [ C（ x)=1] − Prob _x∈D [ C（ x)=1] | ≤ ε.

1.2 伪随机发生器

函数 G_l  : {0，1}^l → {0，1}^m，如果:满足下面的条件，而且l < m ，则G_l 是伪随机发生器，

• 可以用l中的多项式时间计算G_l
• 当 x 是均匀随机时，G_l（x)是伪随机的。

1.3 一个附加伪随机比特意味着多项式更多的伪随机比特

可以证明，如果有伪随机发生器 G_l 满足以下内容: {0，1}^l → {0，1}^l+1, 即 仅添加一 个伪随机位的生成器，那么对于任何 m = poly（l)，有一个伪随机发生器 g '_l 满足: {0，1}^l → {0，1}^m。

证明的想法如下: 第一个来自均匀分布U_l 的s位比特被用作的第一个实例G_l的种子， 称为伪随机发生器。接下来 ，将G_l 的第一个实例的输出分为两个部分:第一 l 位被馈送到的第二个实例中 的G_l 作为种子，而最后一位成为输出的第一位。重复此过程 m 次，产生的输出是 m 个伪随机位。

可以证明的是G'_l, 包括 m 个实例 G_l，实际上是伪随机发生器，可以使用如下的混合方法并通过矛盾方法证明 :

假设 m+1 中间分布 H_i: 0  ≤  i  ≤  m，其中从均匀分布中选择第一个i 位，从G'_l 输出中选择最后m − i 位。这样，H₀ 是 G'_l 的全部输出，而H_m 是真正的均匀分布 U_m。因此，分布 H_i 和 H_i+1 仅在一位(位数 i+1)上存在差异。

现在，假设 G'_l 不是伪随机分布；也就是说，存在一些电路 C 以有优势 ε  =   1/ Poly（l) 区分G'_l 和U_m 。换句话说，这个电路可以区分 H₀ 和 H_m。因此，存在这样的 i ，使电路 C 可以至少 以 ε / m 区分 H_i 和 H_i+1 。请注意，既然m是l 多项式， 那么 ε / m 也是l 多项式, 并且仍然是以不可忽视的优势区分。

现在，假设 l+1 位 要么从 G_l 中输出，要么从均匀分布中抽取。让我们重用从实例G_l 中构建大型伪随机发生器的方法，并构造一串长度为m−i−1的伪随机比特，同样使用第一个l 位作为种子。然后，让我们创建一个从均匀分布中提取的i 位，构成的字符串， 将其与最后一个给定的位连接，然后是创建的 m−i−1 位。结果输出是 H_i 或者 H_i+1，其中i+1 位或者来自均匀分布或者来自 G_l。因为假设我们可以以不可忽略 优势区分 H_i 和 H_i+1 ，那么我们可以区分 U 和 G_l，这意味着 G_l 不是伪随机发生器，这与假设是矛盾的。证明完毕。

现在，让我们举例说明，如果存在不需通过随意扔硬币的方式区分 G_l 和 U_l+1 。如上所示，如果存在电路 C 用于区分 G'_l 和 U_m，其中 m = Poly（l)，则存在一个电路C' 使用 i 随机位区分G_l和U_l+1。对于这个电路C' ：| Prob_{u, s} [C' (u₁,...,u_i,G_l(s)) = 1 ] − Prob_{u, y} [C' (u₁,>,...,u_i,y) = 1] | ≥ ε / m,

其中u是一串 i 均匀随机位，s 是一串 l 均匀随机位，以及 y 是一串 l+1个均匀随机位。

然后，

Prob_u[ | Prob_s [C' (u₁,...,u_i,G_l(s)) = 1] - Prob_y [C' (u₁,...,u_i,y) = 1] | ] ≥ ε / m；

也就是说，存在一些固定的i 位的字符串 u ，可以用作C' 的“建议”用于区分 G_l 和 U_l+1。

伪随机发生器的存在与单向函数和硬核谓词相关.形式上，仅当单向函数存在时，伪随机发生器才存在，或者

PRG ↔ OWF

2.1 定义

单向函数

直观地单向功能是易于计算且难以反转的函数。换句话说，函数的复杂性(或电路尺寸)比它的反向推导小得多。形式上，如果满足条件：对于任何电路C 满足其大小≤ S, Prob[ƒ(C(ƒ(x))) = ƒ(x)] ≤ ε，函数(S,ε)： {0，1}ⁿ → {0，1}ⁿ 是单向函数。

此外，单向函数还满足下面结果

• 可以用多项式时间计算
• 如果(Poly（n)是单向，1/Poly（n)) 也是单向

核心谓词

函数 B : {0，1}ⁿ → {0，1} 如果对函数ƒ满足下面条件就是一个硬核谓词

• B 可以用多项式时间计算
• 对于任何多项式大小的电路C 和任何不可忽略的 ε = 1/poly(n), Prob_x~U [C(ƒ(x))  = B(x)] ≤ 1/2+ε

换句话说，很难通过 ƒ(x)来预测 B（x)

2.2 证明

这里给出了概要的证明。请参阅参考资料了解详细证明。

PRG → OWF

考虑伪随机发生器 G_l: {0,1}^l → {0,1}^2l。让我们创建以下单向函数:  {0，1}ⁿ → {0，1}ⁿ 它使用 G_l 输出的前半部分作为它的输出。形式上，

ƒ(x,y) → G_l(x)

证明这种选择合理的一个关键现象是函数的图像大小为2ⁿ ，并且是大小为2ⁿ 的预图像空间中可以忽略的一部分。

为了证明ƒ确实是单向函数，让我们来构造一个矛盾。假设存在一个电路 C 作用于ƒ 满足下面的ε:

Prob[ƒ(C(ƒ(x,y)))  = ƒ(x,y)] > ε

然后我们可以创建以下算法来区分 G_l 和均匀分布，这与假设相矛盾。该算法需要输入2n 位z 和计算(x,y) = C(z)。如果 G_l(x) = z ，则算法会接受，否则会拒绝。

现在，如果 z 取自均匀分布，上述算法接受的概率≤ 1/2^l,，因为图像的大小是1/2^l 前图像的大小。然而，如果 z 是从G_l的输出中提取的，那么假设电路的存在 C，其接受的概率是> ε 。因此，电路的优点是 C 区分均匀分布 U 和输出 G_l > ε − 1/2^l, 这是不可忽略的，因此与我们设定的G_l 作为伪随机发生器的假设相矛盾 。证明完毕。

OWF → PRG

对于这种情况，我们证明了定理较弱的版本:

单向的排列 →伪随机发生器

单向排列是单向函数，也是输入位的排列。伪随机发生器可以由单向排列构成，如下所示:

G_l: {0,1}^l→{0,1}^l+1  =  ƒ(x).B(x)，其中B 是ƒ 和"."的核心谓词，是串联运算符。注意，根据上面证明的定理，只需要证实只添加一个伪随机位的发生器的存在。

核心谓词 → PRG

首先，让我们证明如果B 是一个核心谓词， G_l 确实是伪随机的。同样，我们将通过构造一个矛盾来证明这个论点。

假设 G_l 不是伪随机发生器；也就是说，存在多项式大小的电路C 以优势≥ε区别G_l(x) =ƒ(x).B(x)和U_l+1 ，同时ε 不可忽视。请注意，由于ƒ(x)是一个置换，那么如果 x 是从均匀分布中得出的。因此， U_l+1 相当于ƒ(x).b，这里 b 是独立的从均匀分布抽取的一个位。形式上，

Prob_x~U [C(G(x))=1] − Prob_x~U,b~U [C(x.b)=1]  ≥ ε

让我们构造以下算法 C：

1. Given z=f(x) guess bit b 
2. Run C on z.b
3. IF C(z.b)=1
4.     output b
5. ELSE
6.     output 1-b

给定ƒ的输出，算法首先通过投掷随机硬币猜测位b，即 Prob[b=0] = Prob[b=1] = 0.5。然后，算法(电路) C 运行f(x).b 如果结果是1，那么 b 输出，否则1-b返回。

那么C' 猜对B(x)的概率为:

Prob_x~U [C'(z)=B(x)] =

Prob[b=B(x) ∧ C(z.b)=1] + Prob[b≠B(x) ∧ C(z.b)=0] =

Prob[b=B(x)]⋅Prob[C(z.b)=1 | b=B(x)] + Prob[b≠B(x)]⋅Prob[C(z.b)=0 | b≠B(x)] =

1/2⋅Prob[C(z.b)=1 | b=B(x)] + 1/2⋅Prob[C(z.b)=0 | b≠B(x)] =

(1−1/2)⋅Prob[C(z.b)=1 | b=B(x)] + 1/2⋅(1−Prob[C(z.b)=1 | b≠B(x)]) =

1/2+Prob_z.b~G(x) [C(z.b)=1] − 1/2⋅(Prob[C(z.b)=1 | b=B(x)]+Prob[C(z.b)=1 | b≠B(x)]) =

1/2+Prob_z.b~G(x) [C(z.b)=1] − Prob_z.b~U [C(z.b)=1] ≥ 1/2+ε

这意味着电路C' 能够以概率大于1/2 + ε预测 B（x)，这意味着 B 不可能是ƒ的核心谓词，这与假设是矛盾的。证明完毕。

OWP → 硬核谓词

概要的证明如下:

如果ƒ{0,1}ⁿ→{0,1}ⁿ 是单向排列，那么 ƒ'{0,1}²ⁿ→{0,1}²ⁿ也是单向排列，根据定义其中ƒ'(x,y)=ƒ(x).y。然后 B(x,y)=x⋅y 是ƒ'的核心谓词，其中 ⋅ 是一个向量点积。为了证明它确实是硬核，让我们假设不是这样，并证明与ƒ是单向函数假设的矛盾。如果 B 不是一个核心谓词，那么就存在一个电路C 可以预测，所以

Prob_x,y[C(ƒ(x),y)=x⋅y] ≥  1/2+ε. 这个事实可以用通过巧妙的使用来自x 孤立的位输入来构建排列y 来恢复 x 。事实上，对于 x，有一个多项式时间算法列出O(1/&epsilon²) 所有有效的候选x。因此，算法可以用多项式时间反转ƒ(x)的不可忽略的部分x。这与假设相矛盾。