密码学中的归约证明过程
证明过程
归约证明(proof by reduction)是现代密码学中证明方案安全性的重要方法,甚至是一些教材中使用的唯一方法。它的思路是,假设某个问题难以解决,然后证明基于该问题的构造方法在该假设下是安全的。
想要证明某构造方案\(\Pi\)安全,假设已知问题\(\mathsf{X}\)难以解决,将成功攻破该方案\(\Pi\)的有效敌手\(\mathcal{A}\)转化为成功解决问题\(\mathsf{X}\)的有效算法\(\mathcal{A}'\),这与假设相矛盾,所以方案\(\Pi\)无法攻破,方案是安全的。具体过程如下:
- 指定概率多项式时间的敌手\(\mathcal{A}\)攻击方案\(\Pi\),成功的概率为\(\varepsilon(n)\)
- 假设:问题\(\mathsf{X}\)难以解决,即无法在概率多项式时间内以不可忽略的概率解决
- 归约:构造有效算法\(\mathcal{A}'\),它将\(\mathcal{A}\)当作子程序运行,从问题\(\mathsf{X}\)的实例\(\mathsf{x}\)模拟出一个\(\Pi\)的实例,输入给\(\mathcal{A}\),如果\(\mathcal{A}\)成功攻破,则\(\mathcal{A}'\)成功解决实例\(\mathsf{x}\)的概率至少为多项式的倒数\(1/p(n)\)
- 矛盾:那么\(\mathcal{A}'\)解决问题\(\mathsf{X}\)的概率为\(\varepsilon(n)/p(n)\),若\(\varepsilon(n)\)不可忽略,则\(\varepsilon(n)/p(n)\)也不可忽略,这与假设相矛盾
- 结论:敌手\(\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)\)的伪随机性,过程如下:
- 指定概率多项式时间的区分器\(\mathcal{D}\),\(\mathcal{D}\)成功区分\(G(s)\)和\(r\)的概率 \[ \varepsilon(n) = \mathrm{Pr}[D(r)=1] - \mathrm{Pr}[D(G(s))=1] \]
- 假设:问题\(\mathsf{X}\)难以解决,即成功区分\(F(s)\)和\(r\)的概率可忽略
- 归约:构造算法\(\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} \]
- 矛盾:若\(\mathcal{D}'\)成功区分\(F(s)\)和\(r\)的概率\(\varepsilon(n)\)不可忽略,则与假设矛盾
- 结论:\(\mathcal{D}\)无法以不可忽略的概率区分\(G(s)\)和\(r\),\(G(s)\)也是伪随机数发生器,得证
上面的例子中\(1/p(n)\)的值为\(1\),可以认为\(\mathcal{D}'\)与\(\mathcal{D}\)的交互过程非常「顺利」。
经典算法对应的基础问题
通过归约可将要证明的结论等价为更基础的问题,上面的例子将\(G(s)\)的伪随机性等价为\(F(s)\)的伪随机性。类似地,很多密码方案的安全性可以等价为一些基础问题的困难性。比如,RSA算法之所以安全是因为大整数质因数分解很困难,ElGamal算法之所以安全是因为离散对数求解困难。所以,在证明方案的安全性时,可将安全性证明归约到求解基础问题的困难性上。