# 密码学答疑系列（1）：困难假设和安全模型的强弱以及安全归约的方向
==[Crypto means Cryptography!](https://www.schneier.com/blog/archives/2021/11/crypto-means-cryptography-not-cryptocurrency.html)==

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

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

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

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

## 关于困难假设的强弱
一个数学问题可以分成**计算性的**（输出解）或**判定性的**（输出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](https://en.wikipedia.org/wiki/Digital_signature_forgery#Existential_forgery) 和[SUF-CMA](https://en.wikipedia.org/wiki/Digital_signature_forgery#Weak_existential_forgery_(strong_existential_unforgeability,_strong_unforgeability;_sEUF,_or_SUF))为例，前者只要求敌手不可伪造出对新消息$m$的签名，后者要求敌手不可伪造出新的消息-签名对$(m,\sigma)$。对于已有旧消息$m_i$，伪造出新的合法签名$\sigma_i^\prime$的攻击，对于达到前者安全性质的方案来说依然是可能的，而对于后者来说是已经被排除在外的。

## 关于安全归约的方向
假设有两个计算问题 $A, B$。 $B \leq_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）