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

Reduction in Cryptography

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

归约

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

1 从问题出发

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

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

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