基于PRG构造的加密方案的安全性证明
若\(\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