Let G： K → { 0 , 1 } n K \rightarrow \{0,1\}^n K→{0,1}n
具有密钥空间K，并输出 n n n位伪随机数
[ k ← r K , o u t p u t G ( k ) ] [k \xleftarrow{r} K, output G(k)] [kr K,outputG(k)]
r 表示从聚集K中均匀选择，要证明这种伪随机字符串的分布与真正均匀的分布，是不可区分的。换句话说，如果我们只是在0到1的N次方中选择，n个字符串，并简单输出这个字符r。均匀分布可以随机输出这些字符串中的恣意一个，这就是均匀分布的界说。种子空间非常小，以是可能的输出聚集也非常的小。在 { 0 , 1 } \{0,1\} {0,1}N位中非常小。这就是这个生成器所能输出的全部。为了界说这种随机不可区分的概念，须要举行Statical Test，设定一个算法 A(x) 输出 0或1。0的意思黑白随机的，1的意思是随机的。
A ( x ) = 1 A(x) = 1 A(x)=1，当且仅当： ∣ | ∣# 0 ( x ) 0(x) 0(x) - # 1 ( x ) ∣ 1(x)| 1(x)∣ ≤ \leq ≤ 10 n 10\sqrt{n} 10n ，我们就说字符串 x x x是随机的，否则不随机。
A ( x ) = 1 A(x) = 1 A(x)=1，当且仅当： ∣ | ∣# 00 ( x ) 00(x) 00(x) - n 4 \frac{n}{4} 4n ∣ | ∣ ≤ \leq ≤ 10 n 10\sqrt{n} 10n ，我们说字符串 x x x是随机的，否则不随机。
A ( x ) = 1 A(x) = 1 A(x)=1，当且仅当： m a x − r u n − o f − 0 ( x ) max-run-of-0(x) max−run−of−0(x) ≤ \leq ≤ 10 l o g 2 n 10log_{2}n 10log2n，则字符串 x x x是随机的。 m a x − r u n − o f − 0 ( x ) max-run-of-0(x) max−run−of−0(x)是指字符串 x x x中最长的零序列。
除外，另有很多其他的统计测试，当通过了这些测试后，就会说这是一个好的生成器。
如何判定一个统计测试是好还是坏呢？
Advantage
Let G : K → { 0 , 1 } n G:K \xrightarrow{} \{0,1\}^n G:K {0,1}n 作为伪随机数生成器， A A A作为在 { 0 , 1 } n \{0,1\}^n {0,1}n范围内的统计测试。
A d v P R G [ A , G ] = ∣ P r [ A ( G ( k ) ) = 1 ] − P r [ A ( r ) = 1 ] ∣ ∈ [ 0 , 1 ] Adv_{PRG}[A,G]=|Pr[A(G(k))=1]-Pr[A(r)=1]|\in[0,1] AdvPRG[A,G]=∣Pr[A(G(k))=1]−Pr[A(r)=1]∣∈[0,1]
( k ← r K k \xleftarrow{r} K kr K， r ← R { 0 , 1 } n r \xleftarrow{R} \{0,1\}^n rR {0,1}n，k是从种子空间均匀选择的)
A d v Adv Adv close to 1，则 A A A 可以区分出G和random。 A d v Adv Adv close to 0，则 A A A 不可以区分出G和random。
假设我们有一个生成器G
K → { 0 , 1 } n K \rightarrow \{0,1\}^n K→{0,1}n for 2/3 keys in K，满足
m s b ( G ( k ) ) = 1 msb(G(k)) = 1 msb(G(k))=1对于三分之二的秘钥，生成器输出的第一位恰好是1。如果我以三分之二的概率选择一个随机秘钥，生成器将输出1作为它的第一位。
可以界说 A ( x ) A(x) A(x)：
if [msb(x)=1] output “1” else output “0”
如果给我的字符串最高位有用位是1，将认为是“1”（随机的），否则是“0”（不随机的）。那么这个测试A对于生成器G的上风是什么？
A d v P R G [ A , G ] = ∣ P r [ A ( G ( k ) ) = 1 ] − P r [ A ( r ) = 1 ] ∣ = ？ Adv_{PRG}[A,G]=|Pr[A(G(k))=1]-Pr[A(r)=1]| = ？ AdvPRG[A,G]=∣Pr[A(G(k))=1]−Pr[A(r)=1]∣=？
假设我们给一个伪随机输入，则根据G的界说，会有2/3的概率输出1。对于一个随机字符串而言，恰好会有一半的概率在最高位是1，在这种情况下，最高位输出1的概率是1/2。以是该式等价于： 2 3 − 1 2 = 1 6 \frac{2}{3}-\frac{1}{2}=\frac{1}{6} 32−21=61。这是个一个相对大的数字，意味着A能够区分伪随机数和真正的随机数，称为：A breaks G with the advantage 1/6。意味着这个生成器G欠好，有题目。
什么是安全的伪随机生成器呢？
Def: We say that G： K → { 0 , 1 } n K \rightarrow \{0,1\}^n K→{0,1}n is a secure PRG if 对于全部efficiency的统计测试A，A对于G的Adv基本可以忽略，即非常靠近于0。如果我们要求全部的统计测试，无论它们是否有用，都无法将伪随机和真正随机区分，现实上是无法满足的。
我们可否构建一个生成器，然后证明现实上它是一个安全的伪随机数？
给定生成器输出一个前缀，不可能预测出下一位。
如果PRG是可预测的，则PRG是不安全的，必然可以区分出伪随机和真实随机。
Suppose A is an efficient algorithm：
P r [ A ( G ( k ) ∣ 1 , 2 , . . . , i ) = G ( k ) ∣ i + 1 ] = Pr[A(G(k)|_{1,2,...,i})=G(k)|_{i+1}]= Pr[A(G(k)∣1,2,...,i)=G(k)∣i+1]= 1 2 + ε \frac{1}{2}+ε 21+ε
k是从秘钥空间随机选取的。 ε = 1 / 1000 ε =1/1000 ε=1/1000 已是一个伤害的预测器了。
Define statistical test B as:
B ( x ) = 1 B(x) = 1 B(x)=1 ，当且仅当 A ( x ∣ 1 , 2 , . . . , i ) = x i + 1 A(x|_{1,2,...,i}) = x_{i+1} A(x∣1,2,...,i)=xi+1，否则输出0。
r ← R { 0 , 1 } n r \xleftarrow{R} \{0,1\}^n rR {0,1}n， P r [ B ( r ) = 1 ] = 1 2 Pr[B(r)=1]=\frac{1}{2} Pr[B(r)=1]=21
k ← R K k \xleftarrow{R} K kR K， P r [ B ( G ( k ) ) = 1 ] > 1 2 + ε Pr[B(G(k))=1]>\frac{1}{2}+ε Pr[B(G(k))=1]>21+ε
可以得到 A d v P R G [ B , G ] > ε Adv_{PRG}[B,G] > ε AdvPRG[B,G]>ε
即：如果算法A能够以 ε ε ε的上风预测下一位，那么算法B能够以 ε ε ε的上风区分生成器的输出。
A是一个好的生成器，B就是一个能打破生成器的统计测试。
G如果是一个安全的生成器，那么就不存在好的统计测试。
Thm(Yao’82) an unpredictable PRG is secure
如果存在i属于{0,1,…,n-1} PRG G无法预测第i位的数值，那么G就是一个安全的PRG。
More Generally
P1、P2 是 { 0 , 1 } n \{0,1\}^n {0,1}n的两个分布，P1 和 P2在计算上是不可区分的，写作： P 1 P1 P1 ≈ P ≈_{P} ≈P P 2 P2 P2
对于全部的有用的统计测试： ∣ | ∣ P r x ← P 1 [ A ( x ) = 1 ] Pr_{x \leftarrow P1} [A(x)=1] Prx←P1[A(x)=1] - P r x ← P 2 [ A ( x ) = 1 ] Pr_{x \leftarrow P2} [A(x)=1] Prx←P2[A(x)=1] ∣ | ∣ 可以忽略不计
就说着这两个分布在计算上不可区分。
a PRG is secure if [ k ← R K , G ( k ) ] ≈ P u n i f o r m ( { 0 , 1 } n ) [k \xleftarrow{R} K, G(k)] ≈_{P} uniform(\{0,1\}^n) [kR K,G(k)]≈Puniform({0,1}n)