关于归约方向

有同学对此有疑问，在此简要答疑

假设有两个计算问题, 。的意思是：如果存在PPT算法解决问题，则存在PPT算法解决问题。比如，如果问题是-complete的，so is ; and if is in , so is 。这就是在计算复杂性理论中的一个标准的多项式时间归约。小于等于号就是其字面意思：问题的固有难度不超过问题.

所以在计算复杂性理论中归约方向是很明确的： is reduced to

以下是Sipser教材中的原话可以为证：

When problem is efficiently reducible to problem , an efficient solution to can be used to solve efficiently.

在密码学中同样的道理，依然是应当是 is reduced to 。

只不过问题在密码学中是一个「通过安全定义转换为一个计算问题的密码方案」，变为了攻破方案的敌手（adversary）；

是某个困难性假设，是利用解决的算法，我们称 为一个Reduction.

• 密码方案的安全性是说“一个密码方案是符合其安全定义的”，即不存在PPT算法解决问题
• 困难假设是说“假设某一个问题是（计算）困难的”，即不存在PPT算法解决问题

我们可以说

• 对于困难假设的解决 归约到  对于密码方案的攻破 （这种说法和上述复杂性理论中是一致的）

也可以说

• 密码方案的安全性 归约到 假设的困难性

请牢记“归约到”的意思永远都是如果后半句的条件满足，则前半句的条件满足。故第二种说法本质是在说“如果不存在PPT算法解决问题，则不存在PPT算法解决问题”。这就是第一种说法的「逆否命题」，故两种说法是等价的。

很多人平时会说或在论文里会写 “密码方案是基于(based on)某个假设的”或者说“密码方案 归约到 假设”。这两种其实都只是上述第二种说法的不严谨表述。

另外注意，在安全归约中困难假设的困难程度是攻破方案困难程度的「下界」而非「上界」。