Atelier Fallenhh
图灵机掷骰子吗?

图灵机掷骰子吗?

不会,而且也不需要。只要图灵机自己觉得结果像是随机的就行了。

这就是伪随机生成器定理。如果在理念上真的存在无法被鉴别的伪随机生成器,那么一则困扰人类百年的谜语也可以得到解答。

引子


What is the purpose of our defense policy?


To defend Britain.


No, Bernard. It is to make people BELIEVE Britain is defended

伪随机性

所谓伪随机性,就是某种分布和真随机实在太像了,以至于人们没法在多项式时间内找出该分布的纰漏。

UU为一个含有若干0和1的真随机的均匀分布,DnD_{n}为我们想要验证的含有分布,CC任意的多项式规模的布尔电路(可以理解为小于多项式的时间/空间复杂度的输出为0或1的算法),ε\varepsilon 为与nn 相关的任意多项式的倒数,伪随机分布的严谨定义如下:

PrxU[C(X)=1]PrxD[C(X)=1]ε|\Pr_{x\subset U}[C(X)=1] - \Pr_{x\subset D}[C(X)=1]|\leq \varepsilon

从反面来说,如果我们能找到一个确定的多项式规模的算法,以足够大的优势鉴别出xx是从UU还是DnD_{n}中选出来的,那么我们就可以说这个分布也许欺骗不过图灵机。

e.g. 我们构造这样一个C(x)C(x),当xx中的0多余1时输出0,否则输出1。显然,PrxU[C(X)=1]=0.5\Pr_{x\subset U}[C(X)=1] = 0.5,因为真正的均匀随机分布0和1的数量应当是相等的。如果一个分布中0总是以ε\varepsilon的优势多于或是少于1,那么我们就可以说这个分布被CC所攻破了。

e.g. 我们假设DnD_{n}是一个由 RC41 算法生成的一个序列,构造C(x)C(x),如果xx的第二个byte为0则输出0,否则输出1。由于RC4算法存在相当大的偏差,当随机数种子满足一定条件的时候,第二个byte将总是为0。因此,一个非常简单的CC就能够攻破在过去很受欢迎的RC4算法。

读到这里,也许你会觉得我们的要求似乎太高了,任意的CC都无法攻破才能证明一个分布的伪随机性。

伪随机生成器

我们常常利用图灵机来帮助生成“伪随机”序列,这样的算法就被成为伪随机生成器。伪随机生成器通常需要一个种子,来帮助生成一定长度的序列。假设种子的长度为ll,那么当我们能够生成l+1l+1位的“伪随机”序列时,我们就能够构造出生成任意多项式m=poly(l)m = poly(l)长度的序列的伪随机生成器。只要第l+1l + 1位足够严谨,那么所有mm位也都会足够严谨。

这点是可以得到严格证明的,详见尾注2

我们有一个真正意义上的伪随机生成器吗?答案既不是有,也不是没有,而是不知道。我们既无法证明某一个完美的伪随机生成器存在,也无法证明它不存在。但是我们知道,如果它真的存在,那么我们不光会多了一个只会说没人能理解的胡话的算法,还能证明一个关于计算复杂性理论的百年之谜。

单向函数与伪随机生成器

单向函数 (One-way function)是一种这样的单射函数:对于每一个输入,函数值都(在多项式时间内)容易计算,但是给出一个函数值,算出原始输入却比较困难(无法在多项式时间内使用确定性图灵机计算)。单向函数的存在与否和伪随机生成器有着千丝万缕的联系。

假设某一天,我们得到了一个真正的伪随机生成器Gl:{0,1}l{0,1}2lG_{l}:\{0 ,1\}^{l} \rightarrow \{0 ,1\}^{2l},我们就可以用它构造这样一个函数ƒ:{0,1}l{0,1}lƒ: \{0 ,1\}^{l} \rightarrow \{0 ,1\}^{l},其只将GlG_{l}的前半作为其输出,那么ƒ就是一个真正的单向函数。我们可以用反证法来进行证明:

我们先可以假设这样一个电路CC可以在多项式时间内找出ƒ的逆,那么Pr[ƒ(C(ƒ(x,y)))=ƒ(x,y)]>ε\Pr[ ƒ(C(ƒ(x,y))) = ƒ(x,y) ] > \varepsilon,那么C就能够用来鉴别GlG_{l}UU的区别。因为CC只能以 12l\frac{1}{2^{l}}猜中一个真正的随机分布U,但是能够以ε\varepsilon猜中x。两者之差无法被忽视。

因此,只要伪随机生成器存在,那么单向函数就存在。同时逆命题也是成立的,只不过证明的过程更加复杂3

等等,P≠NP ?!!

是的,只要单向函数存在,那么P就不等于NP了。还是反证法,假设P=NP的话,那么找出一个单向函数的逆就和验证它的逆一样简单。只要代回到原函数就可以验证一个函数的逆,而原函数是可以在多项式时间内完成的计算,那么既然我们能在多项式时间验算它的逆,那么也可以在多项式时间找出所谓单向函数的逆。那么单向函数就不存在了!

那么

  • 伪随机生成器的存在意味着单向函数的存在,同时也意味着P≠NP。
  • 伪随机这个术语也和计算机科学这一术语一样糟糕,根据定义,真随机均匀分布具有伪随机性,因为我们当然无法分辨它和自己的区别。
  • 直到量子物理,人所能认知到的随机只存在于抽象的概念中
  • 我们大部分认为的随机,其实是非常糟糕的伪随机,是一个系统的复杂程度超出的人脑的认知时举起的白旗。