CPA安全的公钥方案肯定多次加密安全

字数统计: 2.5k字   |   阅读时长≈ 11分

    前面的博文已经写过CPA安全，也证明了一个CPA安全的方案，但一个方案在单次加密下是安全的，就一定在多次加密下是安全的吗？实际上答案是否定的，对于私钥密码来说，是存在单次加密安全，多次加密不安全的密码方案的，但对于公钥方案来说，CPA安全的公钥方案肯定多次加密安全。这篇博文就给出这个定理的证明，主要是用到了混合分布的思想。

CPA-多次加密的安全性定义

    和以前一样，想要描述某种安全性的话，就要给出这种安全性的标准定义，这里还是通过实验给出的安全性定义。对于加密方案$\Pi$，以及敌手$\mathcal{A}$，实验定义如下：
1，
2，$\mathcal{A}$得到$pk$，输出一对消息向量和，满足对于所有成立，$t$是任意确定的关于$\lambda$的多项式
3，选择，计算，发送给$\mathcal{A}$
4，$\mathcal{A}(\vec C, pk)$输出一个比特
5，输出$b’$
如果则说$\mathcal{A}$成功，则这个方案不是CPA-多次加密安全的。在此实验的基础上给出CPA-多次加密的安全性定义：
    满足下面条件的公钥加密系统$\Pi$称为具有窃听敌手不可分辨的多次加密(也就是CPA-多次加密安全)：对于任一$PPT$敌手$\mathcal{A}$，存在一个可忽略的函数$negl$使得

证明过程

    这个的证明过程较为繁琐，需要用到混合分布，混合分布之前理论密码学老师讲过，甚至这个定理老师也讲过，但和公钥密码学的证明有一点小区别。既然是混合分布，那就需要先定义两头的分布，定义如下：

1，
2，$\mathcal{A}$得到$pk$，输出一对消息向量和，满足对于所有成立，$t$是任意确定的关于$\lambda$的多项式
3，选择，计算，发送给$\mathcal{A}$
4，$\mathcal{A}(\vec C, pk)$输出一个比特
5，输出$b’$

1，
2，$\mathcal{A}$得到$pk$，输出一对消息向量和，满足对于所有成立，$t$是任意确定的关于$\lambda$的多项式
3，选择，计算，发送给$\mathcal{A}$
4，$\mathcal{A}(\vec C, pk)$输出一个比特
5，输出$b’$

    定义了这样两个实验之后，就有如下等式：

所以根据CPA-多次加密的安全性定义，为了证明CPA-多次加密的安全性，只需证明存在可忽略函数$negl$使得下式成立即可：

    到现在为止，混合分布的两头分布已经定义好了，接下来就要定义混合分布中间的分布，定义如下()：

1，
2，$\mathcal{A}$得到$pk$，输出一对消息向量和，满足对于所有成立，$t$是任意确定的关于$\lambda$的多项式
3，选择，计算，发送给$\mathcal{A}$
4，$\mathcal{A}(\vec C, pk)$输出一个比特
5，输出$b’$

非常直观的就可以看到：

所以只需证明存在可忽略函数$negl$使得下式成立即可：

    接下来，我们主要考虑这个式子，根据绝对值的性质，有：

如果对于任意$1 \leq i \leq t$都存在可忽略函数$negl_i$使得下式成立：

则因为$t$是多项式大小的，所以一定是可忽略函数，则有

这样命题就证毕了，只要我们能证明对于任意$1 \leq i \leq t$都存在可忽略函数$negl_i$使得下式成立即可：

    为了证明，首先给出实验和实验的具体流程如下;

1，
2，$\mathcal{A}$得到$pk$，输出一对消息向量和，满足对于所有成立，$t$是任意确定的关于$\lambda$的多项式
3，选择，计算，发送给$\mathcal{A}$
4，$\mathcal{A}(\vec C, pk)$输出一个比特
5，输出$b’$

1，
2，$\mathcal{A}$得到$pk$，输出一对消息向量和，满足对于所有成立，$t$是任意确定的关于$\lambda$的多项式
3，选择，计算，发送给$\mathcal{A}$
4，$\mathcal{A}(\vec C, pk)$输出一个比特
5，输出$b’$

可以发现，这两个实验的$\vec {C^i}$仅仅在于第$i$个元素不同，实验的第$i$个元素是，实验的第$i$个元素是，由此就可以利用单次加密的CPA安全。

    我们想证明，而且我们知道这两个实验仅仅在于$\vec {C^i}$的第$i$个元素不同，由此，我们构造窃听单个加密的敌手$\mathcal{A}’$，$\mathcal{A}’$参加下面的分辨实验：

1，
2，$\mathcal{A}’$得到$pk$，输出一对等长的消息
3，选择，计算
4，输出一个比特作为对$b$的猜测
5，输出$b’$

接下来给出$\mathcal{A}’$的具体结构如下：

1，得到公钥$pk$，调用$\mathcal{A}(pk)$得到和
2，$\mathcal{A}’$任意选择，从和中输出
3，当$\mathcal{A}’$得到一个密文时，$\mathcal{A}’$令，并且对于$0 \leq j \leq i-1$计算，对于$i+1 \leq j \leq t$计算，最后令
4，$\mathcal{A}’$运行$\mathcal{A}(c)$，输出$\mathcal{A}$的输出

所以对于窃听单个加密的分辨实验来说，显然有：

我们前面的假设就是方案$\Pi$在单次加密下是CPA安全的，所以一定有可忽略函数$negl_i$使得：

则有

至此，原命题全部得证。

一些感想

    首先这个命题是公钥理论中非常基础的证明，也利用了混合分布，在博文里认真写一写也能加深自己对混合分布的理解。需要注意的地方是，在下面这两个式子里：

我们仅仅考虑概率的相等性，怎么说呢，就是这个实验与这个实验是否判断正确我们是不考虑的，可能用的是加密，但输出一个1，这些都是有可能的，我们不去关注这些多余的东西，仅仅关注它们的概率大小是不是相等就可以了，从算法构造上来看，它们的确相等，这样便于我们进行概率分析，往CPA安全的定义上靠近，进而完成我们的证明。

赏

谢谢你请我喝冰露

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

一个理论密码的学习者，现在主要在学习量子密码的基础理论，也在学习基础的可证明安全理论。但说到底还是一条懒狗。