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

发表于 分类于 Waline： 本文字数： 2.9k 阅读时长 ≈ 10 分钟

安全性定义

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

攻击过程可形式化为，允许敌手和加密预言机（encryption oracle）自由交互，访问预言机的过程记为，如果是加密算法，则记为。提供明文消息作为输入，预言机返回密文作为回复，这便是一次询问过程。安全性的定义要求：即使能访问加密预言机，也无法区分两条任意消息的密文。

对称密钥加密方案，CPA不可区分实验记作，定义如下：

  1. 生成密钥
  2. 能访问预言机，输入给，输出一对长度相等的消息和
  3. 选择随机比特，计算出密文交给，称为挑战密文
  4. 继续访问预言机，输出一个比特
  5. 如果，则该实验输出，否则输出
CPA不可区分实验

定义描述了敌手利用预言机攻击方案的过程，当时，成功攻破方案。如果对任意概率多项式敌手，存在可忽略函数，使得

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

伪随机函数

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

伪随机函数

现研究将长度字符串映射到另一个长度字符串的伪随机函数。带密钥的函数是双输入函数：

第一个输入为密钥，第二个输入才是输入。一般来说，密钥一旦选择好就固定了，于是考虑单输入函数：

通常假设是定长的，即密钥、输入和函数值的长度相同。那么伪随机函数通过固定密钥将长度的字符串映射到另一个长度的字符串。每个密钥对应一种函数分布，所以最多可从个不同的函数分布中选择。

考虑所有将长度字符串映射到长度字符串的函数，它们构成的集合记作，将函数看成查找表（look-up table），可得集合的大小为。从中均匀随机选择一个函数，那么是「真正的」随机函数。

如果对所有的多项式时间区分器，存在可忽略函数，满足

则称是伪随机函数，其中是均匀随机选择的，是从所有将长度字符串映射到长度字符串的函数集合中均匀随机选择的。前者是从个不同的函数分布中选择出来的，后者是从个不同的函数分布中选择出来的，但任意区分器都无法在多项式时间内区分到底是在和还是交互。

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

方案构建

令是伪随机函数，定义消息长度为的对称密钥加密方案如下：

  • ：输入，均匀随机选择密钥
  • ：输入密钥，以及消息，均匀随机选择，输出密文
  • ：输入密钥，以及密文，输出明文消息
加密过程

简单定义是不可行的，因为是确定函数（deterministic function），给定相同的输入一定会得到相同的输出。敌手经过多次实验尝试，总能找到某个明文对应的密文与挑战密文相同，从而破解方案。任何CPA安全的加密方案必须是概率的（probabilistic），随机性必须是加密过程的一部分，以保证相同的明文得到不同的密文。

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

安全性证明

攻破方案的概率

将加密方案中的伪随机函数替换成随机函数，得到的加密方案记为。除了真正的随机函数取代了之外，与完全相同。敌手最多向加密预言机询问次，其中是多项式。那么攻破的概率

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

令为生成挑战密文时用到的随机值。向加密预言机询问次可得到，因为返回给的密文，，其中。根据随机值是否被重复使用，分两种情况讨论：

  1. 加密预言机在回答的询问时至少用到过一次，记作事件。这种情况下能轻易判断出哪条消息被加密，只需根据询问预言机得到的计算和对应的密文，其中必有一条与挑战密文相同。的概率最多为，所以该事件发生的概率最多为。
  2. 加密预言机在回答的询问时从未用到过，记作事件。那么和加密预言机的交互过程中没有掌握任何关于的信息，这意味着和做异或后的值完全随机（与「一次一密」类似），所以输出的概率是。

综合这两种情况，可得攻破的概率

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

定义函数 根据的定义，攻破的概率可表示为 只有当为可忽略函数时，方案才是安全的。

归约证明

构造区分器，它将当作子程序运行。访问使用某函数的预言机，要判断该函数是「伪随机的」（即）还是「随机的」（即）。模拟的不可区分性实验，观察成功与否，以确定使用的是伪随机函数还是随机函数。

向输入和可访问的预言机，让执行CPA不可区分实验：

  1. 可以访问，对输入，输出一对长度相等的消息和
  2. 随机选择，均匀随机选择，向询问得到，将交给
  3. 继续访问，继续回答的询问，最终输出一个比特
  4. 如果，则该实验输出，否则输出

那么，作为的子程序运行时的视图与攻击加密方案时的视图相同，而且过程完全一样。使用伪随机函数与加密方案对应，使用随机函数与加密方案对应，所以 综合、、、可得

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

归约证明示意图

  1. 指定敌手攻击方案，成功的概率与的差值为

  2. 假设：问题难以解决，无法在概率多项式时间内以不可忽略的概率区分和

  3. 归约：构造区分器，它将当作子程序运行，执行CPA不可区分实验，可得到结论

  4. 矛盾：若不可忽略，则上面得到的概率也不可忽略，这与假设相矛盾

  5. 结论：无法以不可忽略的概率攻破方案，方案是CPA安全的

参考资料

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