CPA安全方案的构建与安全性证明

安全性定义

选择明文攻击(Chosen-Plaintext Attack)指敌手能够选择不同的明文作为输入提供给加密算法,得到相应的密文,以此确定其他密文对应的明文,从而破解方案。

攻击过程可形式化为,允许敌手𝒜\mathcal{A}和加密预言机(encryption oracle)自由交互,𝒜\mathcal{A}访问预言机𝒪\mathcal{O}的过程记为𝒜𝒪(⋅)\mathcal{A}^{\mathcal{O}(\cdot)},如果𝒪\mathcal{O}是加密算法𝖤𝗇𝖼k\mathsf{Enc}_k,则记为𝒜𝖤𝗇𝖼k(⋅)\mathcal{A}^{\mathsf{Enc}_k(\cdot)}。𝒜\mathcal{A}提供明文消息mm作为输入,预言机返回密文c←𝖤𝗇𝖼k(m)c\gets\mathsf{Enc}_k(m)作为回复,这便是一次询问过程。安全性的定义要求:即使𝒜\mathcal{A}能访问加密预言机,也无法区分两条任意消息的密文。

对称密钥加密方案Π=(𝖦𝖾𝗇,𝖤𝗇𝖼,𝖣𝖾𝖼)\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec}),CPA不可区分实验记作𝖯𝗋𝗂𝗏𝖪𝒜,Π𝖼𝗉𝖺(n)\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n),定义如下:

  1. 生成密钥k←𝖦𝖾𝗇(1n)k\gets\mathsf{Gen}(1^n)
  2. 𝒜\mathcal{A}能访问预言机𝖤𝗇𝖼k(⋅)\mathsf{Enc}_k(\cdot),输入1n1^n给𝒜\mathcal{A},𝒜\mathcal{A}输出一对长度相等的消息m0m_0和m1m_1
  3. 选择随机比特b←{0,1}b\gets\{0,1\},计算出密文c←𝖤𝗇𝖼k(mb)c\gets\mathsf{Enc}_k(m_b)交给𝒜\mathcal{A},cc称为挑战密文
  4. 𝒜\mathcal{A}继续访问预言机,输出一个比特b′b'
  5. 如果b=b′b=b',则该实验输出11,否则输出00
CPA不可区分实验

定义描述了敌手𝒜\mathcal{A}利用预言机𝖤𝗇𝖼k(⋅)\mathsf{Enc}_k(\cdot)攻击方案Π\Pi的过程,当𝖯𝗋𝗂𝗏𝖪𝒜,Π𝖼𝗉𝖺(n)=1\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1时,𝒜\mathcal{A}成功攻破方案。如果对任意概率多项式敌手𝒜\mathcal{A},存在可忽略函数𝗇𝖾𝗀𝗅\mathsf{negl},使得 Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π𝖼𝗉𝖺(n)=1]≤12+𝗇𝖾𝗀𝗅(n) \mathrm{Pr} \Big[\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1\Big] \le \frac{1}{2} + \mathsf{negl}(n) \tag{1}

则方案是选择明文攻击条件下的不可区分加密,或者说是CPA安全的。

伪随机函数

从密码学中的归约证明过程一文可知,伪随机数发生器能够保证窃听者存在时的安全性,伪随机函数(pseudorandom function)则可以用来构造CPA安全的加密方案。

伪随机函数

现研究将nn长度字符串映射到另一个nn长度字符串的伪随机函数。带密钥的函数FF是双输入函数: F:{0,1}*×{0,1}*→{0,1}* F:\{0,1\}^* \times \{0,1\}^* \to \{0,1\}^*

第一个输入为密钥kk,第二个输入才是输入。一般来说,密钥kk一旦选择好就固定了,于是考虑单输入函数: Fk:{0,1}*→{0,1}* F_k:\{0,1\}^* \to \{0,1\}^* Fk(x)=defF(k,x) F_k(x) \overset{\mathrm{def}}{=} F(k,x)

通常假设FF是定长的,即密钥kk、输入xx和函数值Fk(x)F_k(x)的长度相同。那么伪随机函数Fk(⋅)F_k(\cdot)通过固定密钥k∈{0,1}nk\in\{0,1\}^{n}将nn长度的字符串映射到另一个nn长度的字符串。每个密钥对应一种函数分布,所以FkF_k最多可从2n2^n个不同的函数分布中选择。

考虑所有将nn长度字符串映射到nn长度字符串的函数,它们构成的集合记作𝖥𝗎𝗇𝖼n\mathsf{Func}_n,将函数看成查找表(look-up table),可得集合的大小为2n⋅2n2^{n\cdot 2^n}。从中均匀随机选择一个函数f∈𝖥𝗎𝗇𝖼nf\in\mathsf{Func}_n,那么ff是「真正的」随机函数。

如果对所有的多项式时间区分器DD,存在可忽略函数𝗇𝖾𝗀𝗅\mathsf{negl},满足 |Pr[DFk(⋅)(1n)=1]−Pr[Df(⋅)(1n)=1]|≤𝗇𝖾𝗀𝗅(n) \left| \mathrm{Pr} \big[ D^{F_k(\cdot)}(1^n)=1 \big] - \mathrm{Pr} \big[ D^{f(\cdot)}(1^n)=1 \big] \right| \le \mathsf{negl}(n) \tag{2}

则称FF是伪随机函数,其中k←{0,1}nk\gets\{0,1\}^n是均匀随机选择的,ff是从所有将nn长度字符串映射到nn长度字符串的函数集合𝖥𝗎𝗇𝖼n\mathsf{Func}_n中均匀随机选择的。前者是从2n2^n个不同的函数分布中选择出来的,后者是从2n⋅2n2^{n\cdot 2^n}个不同的函数分布中选择出来的,但任意区分器都无法在多项式时间内区分到底是在和FkF_k还是ff交互。

基于伪随机函数构建CPA安全的加密方案,方案安全性证明的关键点在于,如果敌手能够攻破该方案,则它能将伪随机函数和真正的随机函数区分开来。我们能在后面的归约证明过程中看到这一点。

方案构建

令FF是伪随机函数,定义消息长度为nn的对称密钥加密方案Π=(𝖦𝖾𝗇,𝖤𝗇𝖼,𝖣𝖾𝖼)\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})如下:

  • 𝖦𝖾𝗇\mathsf{Gen}:输入1n1^n,均匀随机选择密钥k←{0,1}nk\gets\{0,1\}^n
  • 𝖤𝗇𝖼\mathsf{Enc}:输入密钥k∈{0,1}nk\in\{0,1\}^n,以及消息m∈{0,1}nm\in\{0,1\}^n,均匀随机选择r←{0,1}nr\gets\{0,1\}^n,输出密文 c:=⟨r,Fk(r)⊕mb⟩ c:=\left \langle r, F_k(r) \oplus m_b \right \rangle
  • 𝖣𝖾𝖼\mathsf{Dec}:输入密钥k∈{0,1}nk\in\{0,1\}^n,以及密文c=⟨r,s⟩c=\left \langle r, s \right \rangle,输出明文消息 m:=Fk(r)⊕s m:=F_k(r)\oplus s
加密过程

简单定义𝖤𝗇𝖼k(m)=Fk(m)\mathsf{Enc}_k(m)=F_k(m)是不可行的,因为𝖤𝗇𝖼k(⋅)=Fk(⋅)\mathsf{Enc}_k(\cdot)=F_k(\cdot)是确定函数(deterministic function),给定相同的输入一定会得到相同的输出。敌手经过多次实验尝试,总能找到某个明文对应的密文与挑战密文相同,从而破解方案。任何CPA安全的加密方案必须是概率的(probabilistic),随机性必须是加密过程的一部分,以保证相同的明文得到不同的密文。

该构造方案是概率的,通过伪随机函数将随机值rr映射到另一个字符串,然后将字符串与明文异或,得到密文。Fk(r)F_k(r)对于观察密文⟨r,s⟩\left\langle r,s \right\rangle的敌手来说,看上去是完全随机的。因此,该加密方案和「一次一密」非常相似,只要rr没有在之前某次加密中使用过。

安全性证明

攻破方案的概率

将加密方案Π\Pi中的伪随机函数FkF_k替换成随机函数f←𝖥𝗎𝗇𝖼nf\gets\mathsf{Func}_n,得到的加密方案记为Π̃=(𝖦𝖾𝗇̃,𝖤𝗇𝖼̃,𝖣𝖾𝖼̃)\widetilde{\Pi}=(\widetilde{\mathsf{Gen}},\widetilde{\mathsf{Enc}},\widetilde{\mathsf{Dec}})。除了真正的随机函数ff取代了FkF_k之外,Π̃\widetilde{\Pi}与Π\Pi完全相同。敌手𝒜\mathcal{A}最多向加密预言机询问q(n)q(n)次,其中q(⋅)q(\cdot)是多项式。那么𝒜\mathcal{A}攻破Π̃\widetilde{\Pi}的概率 Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π̃𝖼𝗉𝖺(n)=1]≤12+q(n)2n \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\widetilde{\Pi}}^{\mathsf{cpa}}(n)=1 \Big] \le \frac{1}{2}+\frac{q(n)}{2^n} \tag{3}

下面分析如何得到(3)(3)的结果。

令rcr_c为生成挑战密文c=⟨rc,f(rc)⊕mb⟩c=\left\langle r_c,f(r_c) \oplus m_b \right\rangle时用到的随机值。𝒜\mathcal{A}向加密预言机询问q(n)q(n)次可得到{⟨ri,f(ri)⟩}\{\left\langle r_i,f(r_i) \right\rangle\},因为返回给𝒜\mathcal{A}的密文ci=⟨ri,si⟩c_i=\left\langle r_i,s_i \right\rangle,f(ri)=si⊕mif(r_i)=s_i\oplus m_i,其中i=1,…,q(n)i=1,\dots,q(n)。根据随机值rcr_c是否被重复使用,分两种情况讨论:

  1. 加密预言机在回答𝒜\mathcal{A}的询问时至少用到过一次rcr_c,记作事件𝖱𝖾𝗉𝖾𝖺𝗍\mathsf{Repeat}。这种情况下𝒜\mathcal{A}能轻易判断出哪条消息被加密,只需根据询问预言机得到的⟨rc,f(rc)⟩\left\langle r_c,f(r_c) \right\rangle计算m0m_0和m1m_1对应的密文,其中必有一条与挑战密文cc相同。rc∈{ri}r_c\in\{r_i\}的概率最多为q(n)/2nq(n)/2^n,所以该事件发生的概率最多为q(n)/2nq(n)/2^n。
  2. 加密预言机在回答𝒜\mathcal{A}的询问时从未用到过rcr_c,记作事件¬𝖱𝖾𝗉𝖾𝖺𝗍\lnot\mathsf{Repeat}。那么𝒜\mathcal{A}和加密预言机的交互过程中没有掌握任何关于f(rc)f(r_c)的信息,这意味着f(rc)f(r_c)和mbm_b做异或后的值完全随机(与「一次一密」类似),所以𝒜\mathcal{A}输出b′=bb'=b的概率是1/21/2。

综合这两种情况,可得𝒜\mathcal{A}攻破Π̃\widetilde\Pi的概率 Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π̃𝖼𝗉𝖺(n)=1]=Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π̃𝖼𝗉𝖺(n)=1∧𝖱𝖾𝗉𝖾𝖺𝗍]+Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π̃𝖼𝗉𝖺(n)=1∧¬𝖱𝖾𝗉𝖾𝖺𝗍]≤Pr[𝖱𝖾𝗉𝖾𝖺𝗍]+Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π̃𝖼𝗉𝖺(n)=1|¬𝖱𝖾𝗉𝖾𝖺𝗍]≤q(n)2n+12 \begin{align} \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\widetilde{\Pi}}^{\mathsf{cpa}}(n)=1 \Big] & = \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\widetilde{\Pi}}^{\mathsf{cpa}}(n)=1 \wedge \mathsf{Repeat} \Big] + \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\widetilde{\Pi}}^{\mathsf{cpa}}(n)=1 \wedge \lnot\mathsf{Repeat} \Big] \\ & \le \mathrm{Pr} \big[ \mathsf{Repeat} \big] + \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\widetilde{\Pi}}^{\mathsf{cpa}}(n)=1 \big | \lnot\mathsf{Repeat} \Big] \\ & \le \frac{q(n)}{2^n}+\frac{1}{2} \end{align}

即得到(3)(3)的结果。从上面的分析可知,该方案安全性的关键在于,避免生成挑战密文cc时所用到的随机值rcr_c在加密预言机回答敌手询问时被使用,但即使是重复使用了,概率也是可以忽略的。

定义函数 ε(n)=defPr[𝖯𝗋𝗂𝗏𝖪𝒜,Π𝖼𝗉𝖺(n)=1]−12 \varepsilon(n) \overset{\mathrm{def}}{=} \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1 \Big] - \frac{1}{2} \tag{4} 根据ε\varepsilon的定义,𝒜\mathcal{A}攻破Π\Pi的概率可表示为 Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π𝖼𝗉𝖺(n)=1]=12+ε(n) \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1 \Big] = \frac{1}{2} + \varepsilon(n) \tag{5} 只有当ε(n)\varepsilon(n)为可忽略函数时,方案Π\Pi才是安全的。

归约证明

构造区分器𝒟\mathcal{D},它将𝒜\mathcal{A}当作子程序运行。𝒟\mathcal{D}访问使用某函数的预言机𝒪\mathcal{O},要判断该函数是「伪随机的」(即Fk,k←{0,1}nF_k, k\gets\{0,1\}^n)还是「随机的」(即f←𝖥𝗎𝗇𝖼nf\gets\mathsf{Func}_n)。𝒟\mathcal{D}模拟𝒜\mathcal{A}的不可区分性实验,观察𝒜\mathcal{A}成功与否,以确定𝒪\mathcal{O}使用的是伪随机函数还是随机函数。

向𝒟\mathcal{D}输入1n1^n和可访问的预言机𝒪\mathcal{O},让𝒜\mathcal{A}执行CPA不可区分实验:

  1. 𝒜\mathcal{A}可以访问𝒪\mathcal{O},对𝒜\mathcal{A}输入1n1^n,𝒜\mathcal{A}输出一对长度相等的消息m0m_0和m1m_1
  2. 随机选择b←{0,1}b\gets\{0,1\},均匀随机选择r←{0,1}nr\gets\{0,1\}^n,向𝒪\mathcal{O}询问得到s′←𝒪(r)s'\gets\mathcal{O}(r),将c:=⟨r,s′⊕mb⟩c:=\left \langle r,s'\oplus m_b \right \rangle交给𝒜\mathcal{A}
  3. 𝒜\mathcal{A}继续访问𝒪\mathcal{O},𝒪\mathcal{O}继续回答𝒜\mathcal{A}的询问,𝒜\mathcal{A}最终输出一个比特b′b'
  4. 如果b=b′b=b',则该实验输出11,否则输出00

那么,𝒜\mathcal{A}作为𝒟\mathcal{D}的子程序运行时的视图与𝒜\mathcal{A}攻击加密方案时的视图相同,而且过程完全一样。𝒪\mathcal{O}使用伪随机函数FkF_k与加密方案Π\Pi对应,𝒪\mathcal{O}使用随机函数ff与加密方案Π̃\widetilde{\Pi}对应,所以 Pr[DFk(⋅)(1n)=1]=Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π𝖼𝗉𝖺(n)=1] \mathrm{Pr} \big[ D^{F_k(\cdot)}(1^n)=1 \big] = \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1 \Big] \tag{6} Pr[Df(⋅)(1n)=1]=Pr[𝖯𝗋𝗂𝗏𝖪𝒜,Π̃𝖼𝗉𝖺(n)=1] \mathrm{Pr} \big[ D^{f(\cdot)}(1^n)=1 \big] = \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\widetilde{\Pi}}^{\mathsf{cpa}}(n)=1 \Big] \tag{7} 综合(3)(3)、(5)(5)、(6)(6)、(7)(7)可得 Pr[DFk(⋅)(1n)=1]−Pr[Df(⋅)(1n)=1]≥ε(n)−q(n)2n \mathrm{Pr} \big[ D^{F_k(\cdot)}(1^n)=1 \big] - \mathrm{Pr} \big[ D^{f(\cdot)}(1^n)=1 \big] \ge \varepsilon(n) - \frac{q(n)}{2^n} \tag{8}

有了上面的结果,构造归约证明,过程如下:

归约证明示意图
  1. 指定敌手𝒜\mathcal{A}攻击方案Π\Pi,成功的概率与1/21/2的差值为ε(n)\varepsilon(n)

  2. 假设:问题𝖷\mathsf{X}难以解决,无法在概率多项式时间内以不可忽略的概率区分FkF_k和ff

  3. 归约:构造区分器𝒟\mathcal{D},它将𝒜\mathcal{A}当作子程序运行,执行CPA不可区分实验,可得到结论 Pr[DFk(⋅)(1n)=1]−Pr[Df(⋅)(1n)=1]≥ε(n)−q(n)2n \mathrm{Pr} \big[ D^{F_k(\cdot)}(1^n)=1 \big] - \mathrm{Pr} \big[ D^{f(\cdot)}(1^n)=1 \big] \ge \varepsilon(n) - \frac{q(n)}{2^n}

  4. 矛盾:若ε(n)\varepsilon(n)不可忽略,则上面得到的概率也不可忽略,这与假设相矛盾

  5. 结论:𝒜\mathcal{A}无法以不可忽略的概率攻破方案Π\Pi,方案Π\Pi是CPA安全的

参考资料

  1. Cryptography Course Slides
  2. 现代密码学