安全规约的例子2——PRF族

继续分析第二个例子

定理：如果FFF是一个安全的PRFPRFPRF族，那么ZZZ是一个安全的PRFPRFPRF族。
FFF和ZZZ的区别如下：
Zk(x):Z_k(x):Zk​(x):如果x=kx=kx=k，返回0；否则，返回Fk(x)F_k(x)Fk​(x)。

根据上一篇博客的证明方法，展开证明。

证明：如果存在一个PPT敌手AAA他在一个随机函数中区分出ZkZ_kZk​方面（简单说就是它可以打破ZZZ的安全性）有不可忽略的优势，那么我们就可以构造一个PPT敌手BBB在一个随机函数中区分FkF_kFk​方面(简单说就是他可以打破FFF的安全性)具有不可忽略的优势。

下面就是画盒子了

先看盒子内部，AAA的目的是要攻破ZZZ，因此盒子内部是关于ZZZ的游戏。AAA首先被给与安全参数1n1^n1n，AAA可以做多项式次问询xxx，BBB负责返回给AAA问询结果y:Zk(x)y:Z_k(x)y:Zk​(x)或者随机函数Z′(x)Z'(x)Z′(x)，最后AAA负责给BBB最终的结果R/PRR/PRR/PR，回答yyy究竟是伪随机还是真随机。

盒子BBB扮演的角色是尝试去打破FFF的安全性。盒子外围的设计就是针对FFF的游戏。首先BBB被给与安全参数1n1^n1n，BBB可以问询多项式次数的x′x'x′，挑战者负责返回给BBB结果y′=Fk(x′)y'=F_k(x')y′=Fk​(x′)，y′y'y′要么是一个随机产生的秘钥kkk得到的函数Fk(x′)F_k(x')Fk​(x′)要么是F(x′)F(x')F(x′)。BBB去猜测y′y'y′究竟是伪随机的还是真随机的。

BBB负责把盒子内外的接口对齐，它从盒子内接收到敌手AAA的问询xxx之后，设置x′=xx'=xx′=x问询盒子外的挑战者，得到y′y'y′，然后设置y=y′y=y'y=y′返回给AAA。

最后如果AAA最后返回给BBB的结果是RRR，那么BBB返回给挑战者的信息也是RRR;否则的话就是PRPRPR。

如果BBB也是PPT敌手，AAA向BBB做了多项式次的问询p(n)p(n)p(n)，那么此时BBB也向它的挑战者做了PPTPPTPPT次的预言机（后面会单独开一篇博客讲随机预言机）问询p(n)p(n)p(n)，每次AAA向BBB做问询之后，BBB也会向它的挑战者做问询。

先证明BBB是PPT的
BBB的运行时间如何计算呢？等于p(n)p(n)p(n)次预言机查询的时间+敌手AAA的运行时间+图中红色部分的交流时间。

每次预言机问询话费O(1)O(1)O(1)时间，p(n)p(n)p(n)次问询就是O(1)∗p(n)O(1)*p(n)O(1)∗p(n)。

AAA是多项式敌手，运行时间为q(n)q(n)q(n)。

红色部分的交流时间包括往返信息，x=x′x=x'x=x′以及y=y′y=y'y=y′，所以总时间就是2p(n)2p(n)2p(n)。

当然，还有两次传输安全参数的时间：2

所以
B′running time=p(n)∗O(1)+q(n)+2p(n)+2=poly(n)(1) \begin{aligned} B' \text{running time}&=p(n)*O(1)+q(n)+2p(n)+2 \\ &= poly(n) \end{aligned} \tag{1}B′running time​=p(n)∗O(1)+q(n)+2p(n)+2=poly(n)​(1)

再证明B的模拟跟真实挑战者不可区分

即AAA与BBB的交互应该与AAA和方案Z的真实挑战者的交互相似。

对于任意的x≠kx\neq kx=k，BBB计算Zk(x)Z_k(x)Zk​(x)。BBB与真实挑战者的唯一不同之处在于如果敌手问询x=kx=kx=k，真实的挑战者会返回0，而BBB将会返回Fk(x)F_k(x)Fk​(x)。

对于一个随机的kkk: 敌手AAA在不知道kkk的情况下，问询kkk的概率为敌手AAA问询的总次数，再除以秘钥空间，这里用∣k∣=2n|k|=2^n∣k∣=2n表示。所以这个概率是可忽略的。
Pr[B running time x=k]=p(n)∣k∣=neg(n)(2) \begin{aligned} &Pr[B\text{ running time }x=k] =\frac{p(n)}{|k|}=neg(n) \end{aligned} \tag{2}​Pr[Brunning timex=k]=∣k∣p(n)​=neg(n)​(2)
所以A能够区分是真实世界挑战者还是BBB模拟的概率是可忽略的。

最后是成功概率

BBB能够从F′F'F′区分FkF_kFk​的概率就等于AAA从Z′Z'Z′中区分ZkZ_kZk​的概率。

Pr[B distinguishes ]=Pr[A distinguishes ]=ϵ(n)=non-neg(n)(3) \begin{aligned} &Pr[B\text{ distinguishes }] = \\&Pr[A\text{ distinguishes }]=\\&\epsilon (n)=\text{non-neg}(n) \end{aligned} \tag{3}​Pr[Bdistinguishes]=Pr[Adistinguishes]=ϵ(n)=non-neg(n)​(3)
一开始定义的假设是AAA有不可忽略的概率可以打破ZZZ,那么下面说明此时BBB就有不可忽略的概率打破FFF。

如果FFF是一个安全的PRFPRFPRF族，那么BBB能够区分的优势ϵ(n)\epsilon (n)ϵ(n)就是一个可忽略函数，同时ϵ(n)\epsilon (n)ϵ(n)也是AAA能够区分的优势，也是可忽略的。

这也就意味着ZZZ也是一个安全的PRFPRFPRF族。