密码学中的归约证明过程

证明过程

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

想要证明某构造方案\(\Pi\)安全,假设已知问题\(\mathsf{X}\)难以解决,将成功攻破该方案\(\Pi\)的有效敌手\(\mathcal{A}\)转化为成功解决问题\(\mathsf{X}\)的有效算法\(\mathcal{A}'\),这与假设相矛盾,所以方案\(\Pi\)无法攻破,方案是安全的。具体过程如下:

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

第3步归约中的概率\(1/p(n)\)我是这么理解的,它表示从\(\mathcal{A}'\)的输入到\(\mathcal{A}\)的输入以及从\(\mathcal{A}\)的输出到\(\mathcal{A}'\)的输出这两个交互过程成功的概率。只有整个过程全部成功,才认为\(\mathcal{A}'\)成功解决问题的实例\(\mathsf{x}\),总的概率为\(1/p(n)\)乘以\(\mathcal{A}\)攻破\(\Pi\)的概率\(\varepsilon(n)\)

简单的例子

伪随机数发生器(pseudorandom generator, PRG)输入长度为\(n\)的种子\(s\),算法\(G\)输出长度为\(l(n)\)的字符串。满足\(l(n)>n\)称为扩展性,即用短的种子生成长的字符串。无法区分它和均匀随机选择的字符串称为伪随机性,用数学语言描述就是,对于概率多项式时间的区分器\(\mathcal{D}\)来说,存在可忽略函数\(\mathsf{negl}\)满足: \[ \left| \mathrm{Pr}[D(r)=1] - \mathrm{Pr}[D(G(s))=1] \right| \le \mathsf{negl}(n) \] 其中\(r\)是从\(\left\{ 0,1 \right\}^{l(n)}\)中均匀随机选择的,种子\(s\)是从\(\left\{ 0,1 \right\}^{n}\)中均匀随机选择的。

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

我们用归约方法证明:如果\(F(s)\)是伪随机数发生器,则\(G(s)=F(s)\oplus 1^n\)也是。关键在于将证明\(G(s)\)的伪随机性转化为证明\(F(s)\)的伪随机性,过程如下:

  1. 指定概率多项式时间的区分器\(\mathcal{D}\)\(\mathcal{D}\)成功区分\(G(s)\)\(r\)的概率 \[ \varepsilon(n) = \mathrm{Pr}[D(r)=1] - \mathrm{Pr}[D(G(s))=1] \]
  2. 假设:问题\(\mathsf{X}\)难以解决,即成功区分\(F(s)\)\(r\)的概率可忽略
  3. 归约:构造算法\(\mathcal{D}'\)区分\(F(s)\)\(r\)\(\mathcal{D}'\)\(\mathcal{D}\)作为子程序运行,计算\(\mathcal{D}'\)成功区分的概率 \[ \begin{align} \mathrm{Pr}[D'(r)=1] - \mathrm{Pr}[D'(F(s))=1] & = \mathrm{Pr}[D(r\oplus 1^n)=1] - \mathrm{Pr}[D(F(s)\oplus 1^n)=1] \\ & = \mathrm{Pr}[D(r)=1] - \mathrm{Pr}[D(G(s))=1] \\ & = \varepsilon(n) \end{align} \]
  4. 矛盾:若\(\mathcal{D}'\)成功区分\(F(s)\)\(r\)的概率\(\varepsilon(n)\)不可忽略,则与假设矛盾
  5. 结论:\(\mathcal{D}\)无法以不可忽略的概率区分\(G(s)\)\(r\)\(G(s)\)也是伪随机数发生器,得证

上面的例子中\(1/p(n)\)的值为\(1\),可以认为\(\mathcal{D}'\)\(\mathcal{D}\)的交互过程非常「顺利」。

参考资料

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