基于PRG构造的加密方案的安全性证明
![](https://images.cnblogs.com/cnblogs_com/blogs/727814/galleries/2166023/o_221112111414_PRG3.1.png)
若\(\tilde{b}=0\),则与敌手交互的是一个完善保密方案,即密钥长度为\(l(n)\)的一次一密的加密方案,敌手猜中\(\tilde{b}=b\)的概率是\(\dfrac{1}{2}\),即
\[Pr[b'=b|\tilde{b}=0]=\dfrac{1}{2} \]若\(\tilde{b}=1\),则与敌手交互的事基于PPRG构造的加密方案,此时假设该方案是不安全的,即敌手猜对的概率为\(\dfrac{1}{2}+\sigma(n)\),其中\(\sigma(n)\)是不可忽略函数
\[Pr[b'=b|\tilde{b}=1] = \dfrac{1}{2} + \sigma(n) \]区分器D根据敌手的成功与否决定自己的输出,\(\tilde{b'}=1 \iff b'=b\),则
\[\begin{aligned} Pr[\tilde{b'}=\tilde{b}] &= Pr[\tilde{b}=1]\cdot Pr[\tilde{b'}=1|\tilde{b}=1] + Pr[\tilde{b}=0]\cdot Pr[\tilde{b'}=0 | \tilde{b}=0]\\ &=\dfrac{1}{2}(Pr[\tilde{b'}=1|\tilde{b}=1] + Pr[\tilde{b'}=0 | \tilde{b}=0])\\ &=\dfrac{1}{2}(Pr[b'=b|\tilde{b}=1] +1- Pr[\tilde{b'}=1 | \tilde{b}=0])\\ &=\dfrac{1}{2}(Pr[b'=b|\tilde{b}=1] +1- Pr[b'=b | \tilde{b}=0])\\ &=\dfrac{1}{2} (\dfrac{1}{2} + \sigma(n) + 1- \dfrac{1}{2})\\ &= \dfrac{1}{2} + \dfrac{1}{2}\sigma(n)\\ \end{aligned} \]而伪随机数生成器是唯密文攻击下安全的,矛盾,则假设不成立。最终证明基于PRG构造的加密方案是安全的。
标签:Pr,PRG,加密,dfrac,tilde,sigma,安全性 From: https://www.cnblogs.com/euler0525/p/16884499.html