密码学答疑系列（1）：困难假设和安全模型的强弱以及安全归约的方向

Crypto means Cryptography!

如果一个Crypto行业的从业者对于密码学只是采取敬而远之，当作工具利用，甚至轻视的态度，在我看来这是堪称「Web 3.0迷惑行为」的。因为没有密码学就没有了这个行业的技术根基，精神根基。对于根基，应该再怎么重视都不为过。

“但是密码学太TM难了！”这是同学们的心声，我对此完全感同身受。不过我还是要在这里小幽默一下：密码学“难”就对了！如果这个宇宙中没有hardness，那密码学也就不存在了。密码学正是在利用这个宇宙中存在的计算困难性，来为一个更安全更自由更平等的社会添砖加瓦！

Just kidding. 这个系列是对密码学中的常见概念的辨析，面向以严肃心态学习密码学的初学者。个人能力有限所以请DYOR并欢迎指正。

也欢迎小伙伴们提出下一期的答疑点，我会尽力去解答。（注意要求是真的「密码学」问题，不包括「财富密码」……

）

关于困难假设的强弱

一个数学问题可以分成计算性的（输出解）或判定性的（输出1/0）。存在概率多项式时间（PPT）算法解决的问题我们称之为简单的，不存在PPT算法解决的问题称之为困难的。对于目前还没有已知PPT算法的问题，我们不能（无条件）证明不存在这样的算法（除非

$\mathcal{P}\ne \mathcal{NP}$得以证明），故而我们只能「假设」这些问题是困难的，称之为「困难假设」。然后再基于这些困难假设去构造密码方案。困难假设同样可以分成计算性的（如离散对数假设，CDH）和判定性的（如DDH）。

困难假设又可以（不精确地）分为弱假设（又称标准假设） 和强假设。对于群上假设来说，一个基准假设就是「离散对数假设(DL)」。如果一个假设和DL的安全级别相当，且安全级别只和生成底层数学原语的安全参数相关，则称这样的假设为弱假设（比如说CDH）。反之，如果安全级别低于DL的安全级别，且与其他参数比如问题实例大小相关，则称这类假设为强假设（比如q-SDH）。

攻破弱困难假设的时间开销要远远大于强困难假设。弱假设相对强假设更安全可靠，所以弱困难假设要好于强困难假设。

关于安全模型的强弱

密码学中，我们一般不去一一考虑一系列的攻击（比如重放攻击，共谋攻击等）去分析密码方案的安全性，而是去在一个安全模型中去写一个安全归约来证明一个方案的安全性。安全模型是对可能敌手行为的抽象，描述了给定敌手的资源以及要求敌手达到的目标。给定敌手的资源越少，对敌手的限制越少，要求敌手达到的目标越高，安全模型越强。

对于安全目标

$A$和

$B$（敌手资源也同理），如果满足

$B$后的方案相比满足

$A$的方案，可以排除的可能的攻击向量更多，剩下的可能的攻击向量更少，则称

$B$对应的安全模型比

$A$更强。当然越强的安全模型越难有构造方案可以达到，而一旦达到，强安全模型比弱安全模型更好（和上述安全假设强弱正相反）。一个在强安全模型中证明安全的方案我们说其满足强安全性。

以签名的两种常见安全性EUF-CMA 和SUF-CMA为例，前者只要求敌手不可伪造出对新消息

$m$的签名，后者要求敌手不可伪造出新的消息-签名对

$(m,\sigma )$。对于已有旧消息

$m_i$，伪造出新的合法签名

${\sigma }_i^{\prime }$的攻击，对于达到前者安全性质的方案来说依然是可能的，而对于后者来说是已经被排除在外的。

关于安全归约的方向

假设有两个计算问题

$A,B$。

$B{\le }_{p}A$ 的意思是：如果存在PPT算法

$\mathcal{A}$ 解决问题

$A$, 则存在PPT算法

$\mathcal{B}$ 解决问题

$B$ 。比如, 如果问题

$B$ 是

$\mathcal{N}\mathcal{P}$-complete的, 那么

$A$也是；如果

$A\in \mathcal{P}$那么

$B$也属于

$\mathcal{P}$。这就是在计算复杂性理论中的一个标准的多项式时间归约。小于等于号就是其字面意思：问题

$B$ 的固有难度不超过问题

$A$。

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

$B$ is reduced to 

$A$.

以下是Sipser教材中的原话：

When problem

$B$  is efficiently reducible to problem 

$A$, an efficient solution to

$A$ can be used to solve

$B$ efficiently.

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

$B$ is reduced to 

$A$ 。

只不过问题

$A$在密码学中是一个「通过安全定义转换为一个计算问题的密码方案」，

$\mathcal{A}$ 变为了攻破方案的敌手（adversary）；

$B$是某个困难性假设；

$\mathcal{B}$是利用

$\mathcal{A}$解决

$B$的算法，我们称为一个Reduction.

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

于是我们可以说：

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

也可以说：

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

请牢记“归约到”的意思永远都是如果后半句的条件满足，则前半句的条件满足。故第二种说法本质是在说“如果不存在PPT算法

$\mathcal{B}$ 解决问题

$B$，则不存在PPT算法

$\mathcal{A}$ 解决问题

$A$”。这就是第一种说法的「逆否命题」，故两种说法是等价的。

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

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

---

预告：下节课答疑点：紧致归约，理想模型，随机预言模型（random oracle model）