密码学中的归约证明过程

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

证明过程

归约证明（proof by reduction）是现代密码学中证明方案安全性的重要方法，甚至是一些教材中使用的唯一方法。它的思路是，假设某个问题难以解决，然后证明基于该问题的构造方法在该假设下是安全的。

想要证明某构造方案安全，假设已知问题难以解决，将成功攻破该方案的有效敌手转化为成功解决问题的有效算法，这与假设相矛盾，所以方案无法攻破，方案是安全的。具体过程如下：

归约证明示意图
  1. 指定概率多项式时间的敌手攻击方案，成功的概率为
  2. 假设：问题难以解决，即无法在概率多项式时间内以不可忽略的概率解决
  3. 归约：构造有效算法，它将当作子程序运行，从问题的实例模拟出一个的实例，输入给，如果成功攻破，则成功解决实例的概率至少为多项式的倒数
  4. 矛盾：那么解决问题的概率为，若不可忽略，则也不可忽略，这与假设相矛盾
  5. 结论：敌手无法以不可忽略的概率攻破方案，或者说是计算安全的

第3步归约中的概率我是这么理解的，它表示从的输入到的输入以及从的输出到的输出这两个交互过程成功的概率。只有整个过程全部成功，才认为成功解决问题的实例，总的概率为乘以攻破的概率。

简单的证明例子

伪随机数发生器（pseudorandom generator, PRG）输入长度为的种子，算法输出长度为的字符串。满足称为扩展性，即用短的种子生成长的字符串。无法区分它和均匀随机选择的字符串称为伪随机性，用数学语言描述就是，对于概率多项式时间的区分器来说，存在可忽略函数满足： 其中是从中均匀随机选择的，种子是从中均匀随机选择的。

伪随机数发生器的归约证明

我们用归约方法证明：如果是伪随机数发生器，则也是。关键在于将证明的伪随机性转化为证明的伪随机性，过程如下：

  1. 指定概率多项式时间的区分器，成功区分和的概率
  2. 假设：问题难以解决，即成功区分和的概率可忽略
  3. 归约：构造算法区分和，将作为子程序运行，计算成功区分的概率
  4. 矛盾：若成功区分和的概率不可忽略，则与假设矛盾
  5. 结论：无法以不可忽略的概率区分和，也是伪随机数发生器，得证

上面的例子中的值为，可以认为与的交互过程非常「顺利」。

经典算法对应的基础问题

通过归约可将要证明的结论等价为更基础的问题，上面的例子将的伪随机性等价为的伪随机性。类似地，很多密码方案的安全性可以等价为一些基础问题的困难性。比如，RSA算法之所以安全是因为大整数质因数分解很困难，ElGamal算法之所以安全是因为离散对数求解困难。所以，在证明方案的安全性时，可将安全性证明归约到求解基础问题的困难性上。

参考资料

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