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

继续分析第二个例子定理如果FFF是一个安全的PRFPRFPRF族那么ZZZ是一个安全的PRFPRFPRF族。FFF和ZZZ的区别如下Zk(x):Z_k(x):Zk​(x):如果xkxkxk返回0否则返回Fk(x)F_k(x)Fk​(x)。根据上一篇博客的证明方法展开证明。证明如果存在一个PPT敌手AAA他在一个随机函数中区分出ZkZ_kZk​方面简单说就是它可以打破ZZZ的安全性有不可忽略的优势那么我们就可以构造一个PPT敌手BBB在一个随机函数中区分FkF_kFk​方面(简单说就是他可以打破FFF的安全性)具有不可忽略的优势。下面就是画盒子了先看盒子内部AAA的目的是要攻破ZZZ因此盒子内部是关于ZZZ的游戏。AAA首先被给与安全参数1n1^n1nAAA可以做多项式次问询xxxBBB负责返回给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^n1nBBB可以问询多项式次数的x′xx′挑战者负责返回给BBB结果y′Fk(x′)yF_k(x)y′Fk​(x′)y′yy′要么是一个随机产生的秘钥kkk得到的函数Fk(x′)F_k(x)Fk​(x′)要么是F(x′)F(x)F(x′)。BBB去猜测y′yy′究竟是伪随机的还是真随机的。BBB负责把盒子内外的接口对齐它从盒子内接收到敌手AAA的问询xxx之后设置x′xxxx′x问询盒子外的挑战者得到y′yy′然后设置yy′yyyy′返回给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)。红色部分的交流时间包括往返信息xx′xxxx′以及yy′yyyy′所以总时间就是2p(n)2p(n)2p(n)。当然还有两次传输安全参数的时间2所以B′running timep(n)∗O(1)q(n)2p(n)2poly(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)2poly(n)​(1)再证明B的模拟跟真实挑战者不可区分即AAA与BBB的交互应该与AAA和方案Z的真实挑战者的交互相似。对于任意的x≠kx\neq kxkBBB计算Zk(x)Z_k(x)Zk​(x)。BBB与真实挑战者的唯一不同之处在于如果敌手问询xkxkxk真实的挑战者会返回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 xk]p(n)∣k∣neg(n)(2) \begin{aligned} Pr[B\text{ running time }xk] \frac{p(n)}{|k|}neg(n) \end{aligned} \tag{2}​Pr[Brunning timexk]∣k∣p(n)​neg(n)​(2)所以A能够区分是真实世界挑战者还是BBB模拟的概率是可忽略的。最后是成功概率BBB能够从F′FF′区分FkF_kFk​的概率就等于AAA从Z′ZZ′中区分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族。