标签：Pr CPA tilde 分组 cpa Pi 加密算法 Priv

分组加密算法的CPA安全性证明

CPA安全模型

构造分组加密算法

令\(F\)是伪随机函数，定义一个消息长度为\(n\)的对称加密方案如下：

• Gen：输入：安全参数\(n\)，输出\(k\)，\(k\)是一个\(\{0,1\}^n\)均匀分布中随即取出的整数
• Enc：输入：\((k,m)\)，输出\(c=(c_1,c_2)\leftarrow (r,F_k(r)\oplus m),r\leftarrow \$\{0,1\}^n\)
• Dec：输入\((k,(c_1,c_2))\)，输出\(m\leftarrow F_k(c_1)\oplus c_2\)

证明

猜想：如果\(F\)是一个为随机函数，则构造的加密算法对定长消息是CPA安全的。

归约证明：假设存在概率多项式时间内能攻破加密方案\(\Pi\)的CPA敌手\(A\)，那么我们可以构造多项式时间的区分器算法D以不可忽略的优势区分\(F_k(\cdot)\)，和\(f(\cdot)\)（构造出矛盾）

证明：

首先构造一个理想方案，即利用随机函数\(f\)替换构造方案中的伪随机函数\(F_k\)，记作加密方案\(\tilde{\Pi}=（\widetilde{Gen},\widetilde{Enc},\widetilde{Dec}）\)，

• Gen：输入：安全参数\(n\)，输出\(k\)，\(k\)是一个\(\{0,1\}^n\)均匀分布中随即取出的整数
• Enc：输入：\((k,m)\)，输出\(c=(c_1,c_2)\leftarrow (r,f(r)\oplus m),r\leftarrow \$\{0,1\}^n\)
• Dec：输入\((k,(c_1,c_2))\)，输出\(m\leftarrow f(c_1)\oplus c_2\)

先证明PPT敌手A与该方案的CPA攻击的成功概率为

\[Pr[Priv_{A,\tilde{\Pi}}^{cpa}(n)=1]=\dfrac{1}{2} + negl(n). \]

按照CPA模型，若生成挑战密文所用的随机数\(r^*\)在其它询问过程中使用过（记为事件"REPEAT"），则敌手很容易猜中\(b\)，事件"REPEAT"发生的概率为\(\dfrac{p(n)}{2^n}\)；若\(r^*\)在其他询问过程中未被使用过，则敌手成功的概率为\(\dfrac{1}{2}\)，则

\[\begin{aligned} Pr[Priv_{A,\tilde{\Pi}}^{cpa}(n)=1] &= Pr[Priv_{A,\tilde{\Pi}}^{cpa}(n)=1\wedge REPEAT] + Pr[Priv_{A,\tilde{\Pi}}^{cpa}(n)=1 \wedge REPEAT]\\ &\leq Pr[REPEAT] + Pr[Priv_{A,\tilde{\Pi}}^{cpa}(n)=1 | \overline{REPEAT}]\\ & \leq \dfrac{p(n)}{2^n} + \dfrac{1}{2} \end{aligned} \]

即\(Pr[Priv_{A,\tilde{\Pi}}^{cpa}(n)=1]=\dfrac{1}{2} + negl(n)\)，下面证明\(|Pr[Priv_{A,\Pi}^{cpa}(n)=1] - Pr[Priv_{A,\tilde{\Pi}}^{cpa}(n)=1]| \leq negl(n)\).

其中，\(Pr[D^{F_k(\cdot)}(1^n)=1]=Pr[Priv_{A,\Pi}^{cpa}(n)=1]\)，\(Pr[D^{f(\cdot)}(1^n)=1]=Pr[Priv_{A,\tilde{\Pi}}^{cpa}=1]\)，由\(F(\cdot)\)的伪随机性得，\(|Pr[Priv_{A,\Pi}^{cpa}(n)=1] - Pr[Priv_{A,\tilde{\Pi}}^{cpa}(n)=1]| \leq negl(n)\)，得证.

标签：Pr,CPA,tilde,分组,cpa,Pi,加密算法,Priv
From： https://www.cnblogs.com/euler0525/p/16885470.html