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

安全性定义

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

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

对称密钥加密方案\(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\)CPA不可区分实验记作\(\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)\),定义如下:

  1. 生成密钥\(k\gets\mathsf{Gen}(1^n)\)
  2. 敌手\(\mathcal{A}\)能访问预言机\(\mathsf{Enc}_k(\cdot)\),输入\(1^n\)\(\mathcal{A}\)\(\mathcal{A}\)输出一对长度相等的消息\(m_0\)\(m_1\)
  3. 选择随机比特\(b\gets\{0,1\}\),计算出密文\(c\gets\mathsf{Enc}_k(m_b)\)交给\(\mathcal{A}\)\(c\)称为挑战密文
  4. 敌手\(\mathcal{A}\)继续访问预言机,输出一个比特\(b'\)
  5. 如果\(b=b'\),则该实验输出\(1\),否则输出\(0\)
CPA不可区分实验

定义描述了敌手\(\mathcal{A}\)利用预言机\(\mathsf{Enc}_k(\cdot)\)攻击方案\(\Pi\)的过程,当\(\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1\)时,\(\mathcal{A}\)成功攻破方案。如果对任意概率多项式敌手\(\mathcal{A}\),存在可忽略函数\(\mathsf{negl}\),使得 \[ \mathrm{Pr}\Big[\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1\Big] \le \frac{1}{2} + \mathsf{negl}(n) \tag{1} \] 则方案是选择明文攻击条件下的不可区分加密,或者说是CPA安全的。

伪随机函数

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

伪随机函数

现研究将\(n\)长度字符串映射到另一个\(n\)长度字符串的伪随机函数。带密钥的函数\(F\)是双输入函数: \[ F:\{0,1\}^* \times \{0,1\}^* \to \{0,1\}^* \] 第一个输入为密钥\(k\),第二个输入才是输入。一般来说,密钥\(k\)一旦选择好就固定了,于是考虑单输入函数: \[ F_k:\{0,1\}^* \to \{0,1\}^* \] \[ F_k(x) \overset{\mathrm{def}}{=} F(k,x) \] 通常假设\(F\)是定长的,即密钥\(k\)、输入\(x\)和函数值\(F_k(x)\)的长度相同。那么伪随机函数\(F_k(\cdot)\)通过固定密钥\(k\in\{0,1\}^{n}\)\(n\)长度的字符串映射到另一个\(n\)长度的字符串。每个密钥对应一种函数分布,所以\(F_k\)最多可以从\(2^n\)个不同函数的分布中选择出来。

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

如果对所有的多项式时间区分器\(D\),存在可忽略函数\(\mathsf{negl}\),满足 \[ \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} \] 则称\(F\)是伪随机函数,其中\(k\gets\{0,1\}^n\)是均匀随机选择的,\(f\)是从所有将\(n\)长度字符串映射到\(n\)长度字符串的函数集合\(\mathsf{Func}_n\)中均匀随机选择的。前者是从\(2^n\)个不同的函数分布中选择出来的,后者是从\(2^{n\cdot 2^n}\)个不同的函数分布中选择出来的,但任意区分器都无法在多项式时间内区分到底是在和\(F_k\)还是\(f\)交互。

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

方案构建

\(F\)是伪随机函数,定义消息长度为\(n\)的对称密钥加密方案\(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\)如下:

  • \(\mathsf{Gen}\):输入\(1^n\),均匀随机选择密钥\(k\gets\{0,1\}^n\)
  • \(\mathsf{Enc}\):输入密钥\(k\in\{0,1\}^n\),以及消息\(m\in\{0,1\}^n\),均匀随机选择\(r\gets\{0,1\}^n\),输出密文 \[ c:=\left \langle r, F_k(r) \oplus m_b \right \rangle \]
  • \(\mathsf{Dec}\):输入密钥\(k\in\{0,1\}^n\),以及密文\(c=\left \langle r, s \right \rangle\),输出明文消息 \[ m:=F_k(r)\oplus s \]
加密过程

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

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

安全性证明

攻破方案的概率

将加密方案\(\Pi\)中的伪随机函数\(F_k\)替换成随机函数\(f\gets\mathsf{Func}_n\)得到的加密方案记为\(\widetilde{\Pi}=(\widetilde{\mathsf{Gen}},\widetilde{\mathsf{Enc}},\widetilde{\mathsf{Dec}})\),敌手\(\mathcal{A}\)最多向加密预言机询问\(q(n)\)次,那么\(\mathcal{A}\)攻破\(\widetilde{\Pi}\)的概率

\[ \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)\)的结果是如何得到的。令\(r_c\)为生成挑战密文\(c=\left\langle r_c,f(r_c) \oplus m_b \right\rangle\)时用到的随机值。\(\mathcal{A}\)向加密预言机询问\(q(n)\)次可得到\(\{\left\langle r_i,f(r_i) \right\rangle\}\),因为返回给\(\mathcal{A}\)的密文\(c_i=\left\langle r_i,s_i \right\rangle\)\(f(r_i)=s_i\oplus m_i\),其中\(i=1,\dots,q(n)\)

根据随机值\(r_c\)是否被重复使用,分情况讨论:

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

综合这两种情况,可得\(\mathcal{A}\)攻破\(\widetilde\Pi\)的概率 \[ \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 \wedge \lnot\mathsf{Repeat} \Big] \\ & \le \frac{q(n)}{2^n}+\frac{1}{2} \end{align} \]

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

定义函数 \[ \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\)的概率可表示为 \[ \mathrm{Pr} \Big[ \mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1 \Big] = \frac{1}{2} + \varepsilon(n) \tag{5} \] 只有当\(\varepsilon(n)\)为可忽略函数时,方案\(\Pi\)才是安全的。

归约证明

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

\(\mathcal{D}\)输入\(1^n\)和可访问的预言机\(\mathcal{O}\),让\(\mathcal{A}\)执行CPA不可区分实验的步骤:

  1. \(\mathcal{A}\)能访问预言机\(\mathcal{O}\),对\(\mathcal{A}\)输入\(1^n\)\(\mathcal{A}\)输出一对长度相等的消息\(m_0\)\(m_1\)
  2. 随机选择\(b\gets\{0,1\}\),均匀随机选择\(r\gets\{0,1\}^n\),向预言机询问得到\(s'\gets\mathcal{O}(r)\),将\(c:=\left \langle r,s'\oplus m_b \right \rangle\)交给\(\mathcal{A}\)
  3. \(\mathcal{A}\)继续访问\(\mathcal{O}\)\(\mathcal{O}\)继续回答\(\mathcal{A}\)的询问,\(\mathcal{A}\)最终输出一个比特\(b'\)
  4. 如果\(b=b'\),则该实验输出\(1\),否则输出\(0\)

那么,\(\mathcal{A}\)作为\(\mathcal{D}\)的子程序运行时的视图与\(\mathcal{A}\)攻击加密方案时的视图是相同的,而且过程完全相同。\(\mathcal{O}\)使用伪随机函数\(F_k\)与加密方案\(\Pi\)对应,\(\mathcal{O}\)使用随机函数\(f\)与加密方案\(\widetilde{\Pi}\)对应,所以 \[ \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} \] \[ \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)\)\((5)\)\((6)\)\((7)\)可得 \[ \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/2\)的差值为\(\varepsilon(n)\)
  2. 假设:问题\(\mathsf{X}\)难以解决,无法在概率多项式时间内以不可忽略的概率区分\(F_k\)\(f\)
  3. 归约:构造区分器\(\mathcal{D}\),它将\(\mathcal{A}\)当作子程序运行,执行CPA不可区分实验,可得到结论 \[ \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. 矛盾:若\(\varepsilon(n)\)不可忽略,则上面得到的概率也不可忽略,这与假设相矛盾
  5. 结论:\(\mathcal{A}\)无法以不可忽略的概率攻破方案\(\Pi\),方案\(\Pi\)是CPA安全的

参考资料

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