密码学—安全归约问题(Reduction)

Reduction in Cryptography

---

me看了很多文章，但是还是有点不太明白，总之学习之前你要有一定的密码学基础以及要记住一句话：“原命题与逆否命题同真同假！”

归约

首先用词应该是归约(reduction)，而不是规约。
归约通俗的讲，就是把一个密码方案的安全性建立在一个已知的困难问题上。我们假设存在PPT的敌手(adversary)可以以不可忽略(non-negligible)的优势(advantage)攻破此密码方案，那么通过归约(reduction)，就可以同样以不可忽略的优势破解该困难问题。这与我们对该困难问题已知的困难性(hardness)相互矛盾(contradiction)，所以不可能存在这样的敌手去攻破我们的密码方案，因此他是安全的。

1 从问题出发

假设现在我们提出了一个密码学方案或者协议$\Pi$,我们需要证明它是安全的。怎么证明？

我们的协议一般是建立在已经被证明安全的协议/方案上面，或者建立在某些困难问题（记为Y）上面，比如RSA公钥加密算法就是建立在因数分解困难问题上。为了简化证明，站在巨人的肩膀上，我们希望通过搭建下面的逻辑命题关系来完成我们的证明。

条件命题1：只要Y是安全的，那么我们的方案$\Pi$就是安全的。换句话说，若Y被有效攻破，那么$\Pi$就不再安全。

这样做的好处是，我们站在了巨人的肩膀上：我们不需要从头开始证明，而是从Y开始。大大简化我们的证明过程。

密码学中的归约证明（reduction proof）是密码学非常重要的知识。现代密码学中的几大公钥加密算法建立在几个困难问题假设上面，比如大整数因数分解困难问题（Integer factorization）和离散对数问题（Discrete log problem）。很多现代密码协议或者密码加密方案建立在这些困难问题上面，比如RSA公钥加密算法就是建立在因数分解困难问题上，因此，如果某一天该困难问题能被快速计算出来（多项式时间复杂度），那么所有建立在这个假设上面的协议/方案都变得不安全了。

如何去证明呢？

根据离散数学的条件命题的逻辑等价式，若两个命题有如下关系： $p\to q$,等价于$\rightharpoondown q\to \rightharpoonup p$ 。比如“只要晴天，我就去跑步”，等价于“如果我不去跑步，那么不是晴天”。这个命题等价式是“反证法”的基础。它被用在规约证明中证明某一个新提出的方案X的安全性（也即是下面的Thm），证明的形式为：

Thm（定理）：Y 是安全的$\to$X是安全的。

证明：

通过等价变换，也即是要证明（记为条件命题2）：X不是安全的$\to$Y不是安全的。

条件命题2进一步解释为：如果存在PPT的对手A可以攻破X，那么我们能构造一个PPT的敌手B来攻破Y。

其中，X是我们新提出的方案，Y某一个困难问题，PPT是多项式概率时间的英文缩写。“构造”一词可以理解为模拟。

如果我们能够让上面粗体的条件命题2成立，那么我们就完成了归约证明。这其实是一个反证法：若上面粗体的条件命题2成立，也意味着Thm成立，完成证明。

小结：现在我们明白了我们为什么要使用归约证明，以及使用归约证明的基本形式。接下来的问题是，如何来构造这个条件命题？

2 构造条件命题

我们将上面（B,Y）和(A,X)的关系表示成下图。其中A是试图攻破X的敌手；B是试图攻破Y的敌手。A作为B的一部分，B并不知道A是如何工作的。B是A的外部环境，它要模拟对A的输入和接收A的输出，让A完成对X的攻击游戏。密码学中经常使用Game的形式来定义一个协议的安全性。虽然A的外部环境是由B模拟的，但是，我们要求该模拟的环境等价于真实的A攻击X的game的环境（或者说A无法区分其外部环境是模拟的还是真实的）。因此，这里我们也叫B为模拟器。

除了B要完成上面的工作，它还需要应对别人（B的外部环境）对它的挑战：挑战B能否攻破Y。

结合下图，intuitively，在B接收到外部环境的挑战（chel）之后，将chel进行适当变换（图中红色部分，也即是进行模拟），将其输入给A，让A挑战X。B根据A的输出，适当地变换输出值，输出给外部环境，完成挑战。因此，B对Y的挑战转嫁到A对X的挑战上了。如果我们能够将下面条件关系关联起来，就完成了证明：A对X挑战成功->B对Y挑战成功，或者说 只要X不安全 -> 那么Y就不安全。

如何建模“挑战成功”？我们使用概率。在二选一的Game中，如果A成功的概率为1/2+non-neg(n),那么A就是成功的。neg（n）表示很小的值；而non-neg表示不是很小的值。同理，如果B要赢这个挑战Y的Game，其成功的概率也需要1/2+non-neg(n)。

小结：

证明过程需要：

（1）PPT：A是PPT的；红色部分的计算复杂度是PPT的。具体“红色部分”是什么呢？不同的协议不一样，下面会给出example。

（2）模拟：B所模拟A的外部环境需要看起来像“挑战X的game”的外部环境。

（3） 概率：通过概率计算出下面命题成立，来证明“A对X挑战成功$\to$B对Y挑战成功”：P(A) = 1/2+non-neg(n) $\to$ P(B) =1/2+non-neg(n)（它的逆反命题是：只要Y是安全 $\to$ 那么X就是安全）

如有错误，欢迎交流指正，谢谢！

reference

1. https://www.youtube.com/watch?v=zHMecblCmAM&list=PL4wmOqlgHT2lBQfChNbkNaTlJOXrqIlHe&index=3

2. 《Introduction to Modern Cryptography, second edition》, page 65.

3. 参考：https://www.zhihu.com/question/49441102/answer/1737942968