0x01 量子计算 ​

在量子计算机诞生之后，现有的 RSA、椭圆曲线等公钥密码体制的安全性将可能会被动摇。一些文章将其原因解释为“量子计算机拥有远超经典计算机的计算能力”。这样的简单陈述很难令我们理解为什么研究后量子密码的原因，即解答下面的问题：如果我们无法通过增加密钥长度使得 RSA 可抵抗量子攻击，为什么却可以找到新的密码体制，在密钥长度类似的前提下，可免受量子计算机的威胁？

有的科普文章将量子计算机称作“可无限制并行计算的计算机”。这一说法体现了一部分量子计算机的特征，但并不准确。和经典比特只能同时取 0 或 1 其中的一个值不同，在量子计算机中，一个量子比特（qubit）可能处于 0 和 1 的叠加态（superposition）。对于叠加态的量子比特进行计算，即可视为同时对输入 0 和 1 进行并行计算。然而，由于量子力学中著名的测不准原理，我们无法得知处于叠加态的量子比特的值：在经过观测（measurement）之后，叠加态将坍缩为经典态。亦即：尽管我们可以进行无限制的并行计算，但最终只能随机地获取到其中的一个运算结果，而这事实上无法体现出量子计算相对于经典计算的优势。

如果需要使用量子计算机实现经典计算机无法完成的计算，我们必须应用量子力学中另外一个著名的效应：量子干涉效应。正如在双缝干涉实验中，可以通过双缝投影出亮暗不均的干涉波纹，我们也可以通过干涉效应，使得“量子并行计算”的若干个计算结果中，一部分的计算结果被量子干涉所强化，而另外一部分被量子干涉所抵消。这将导致观测到特定结果的概率增加，从而使得量子计算机以更高的概率输出我们想要得到的计算结果。

Shor 算法 ​

而想要恰当地利用量子干涉效应，就必须通过精心设计的量子算法来实现。尽管有大量理论计算机科学家投入了量子算法的研究工作当中，但目前真正可用的量子算法还不多。其中最著名的一个，是 Peter Shor 于 1994 年提出的 Shor 算法。

Shor 算法可以用量子计算机以多项式时间求解周期函数的周期，而 RSA、椭圆曲线等密码体制所基于的困难问题：大整数分解和离散对数求解，都可以转化为周期函数求解周期的问题，因而可以通过 Shor 算法求解。这也是为什么量子计算机可以攻击现有的公钥密码体制的原因。

隐患 ​

由于对量子算法的研究目前尚不成熟，故仍然存在这样的可能性：某一问题之前被认为是量子计算下困难的，但随着新的量子算法出现，这一问题最终被证明可通过量子计算机求解。

后量子密码 ​

针对量子计算机的威胁，密码学家们提出了“后量子密码”这一概念。从广义的角度上说，后量子密码学研究量子计算机出现后将对密码学产生的影响；从狭义的角度上说，后量子密码主要关注于设计可抵抗量子计算威胁的密码算法，尤其是公钥加密和数字签名算法。

正如我们上面提到的，RSA、椭圆曲线等密码体制会被量子计算机所攻击，是因为其基础的数学困难问题，即大整数分解、椭圆曲线离散对数等问题，可以被量子计算机上运行的 Shor 算法所求解。那么，设计后量子密码，最重要的关键点就在于，如何提出不会被量子计算机求解的数学困难问题。

0x02 脱离安全假设来谈安全都是在耍流氓 ​

所谓安全假设，比如我们说一个系统的权限隔离做得无比精确，每一个用户只能看到被授权的信息，但是这基于一个安全假设：管理员账号没有被破解。又比如在手机银行软件里，只能通过短信认证码，才能完成转账功能，这也基于一个安全假设：你的手机 SIM 卡没有被克隆。如果我们深入地分析每一个我们感觉安全的系统，都存在大量的似乎不那么稳固的安全假设。比特币私钥安全吗？比特币账户的安全假设也不少：首先你的助记词不能让别人知道，手机钱包里私钥保存加密算法足够强，密钥派生算法正规，你不能忘记助记词，等等等。

几乎所有密码算法/协议的安全性（如可信/可靠性，隐私等）都源于底层问题（假定中的）计算困难性。

计算型难题 ​

判定型难题 ​

0x03 计算困难性 ​

安全性证明 ​

一切安全都有前提的，必须证明其安全性。

传统安全认为只有经过数学证明/形式化证明之后，大家才能够确信这个算法/方案的安全性基于一些非常明确的「安全假设」。

是否可解 ​

曾提出了 23 个最重要的数学问题的数学家大卫·希尔伯特（“我们必须知道，我们必将知道。”）试图对某一形式语言系统的无矛盾性给出绝对的证明，以克服悖论引起的危机，一劳永逸地消除对数学基础以及数学推理方法可靠性的怀疑。

但哥德尔证明了希尔伯特方案是不可能实现的：对于足够强有力的自我描述系统，其中必然存在某些命题，既不能被该系统内部所证明，也不能被该系统内部证明其否定。

哥德尔不完备性定理表明任何数学理论都无法证明其自身的一致性，也象征着数学家大卫・希尔伯特将数学建立在绝对确定性的基础上计划的坍塌。

形式化数学推理的关键从问题是否可解转向了研究求解它们的难度有多大，这是非常重要的转折点，从中诞生了计算复杂性理论这样对数学问题更深刻的洞察研究学科。

计算困难问题 ​

如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。——维基百科

计算困难问题并不是不可解，它在理论上可以是可解的，但解法需要耗费大量的时间或空间，以至于无法在实践中应用。

依靠可获得的计算资源和所需要的解的形式，难解性可以有多种形式。例如，一个大部分时候容易算、偶尔很难算的问题，仅在最坏情况下是难解的。或者一个问题在超级计算机上是容易算的，而在个人计算机上可能需要过量的时间。而我们关注的是那些最坏情况下的复杂性是如此巨大，以至于在任何所能想象建造出来的计算机上所耗费的时间，都将超过宇宙的余生的问题。

计算复杂性理论 ​

计算复杂性理论的研究对象是算法在执行时所需的计算资源，而为了讨论这一点，我们必须假设算法是在某个计算模型上运行的。

常讨论的计算模型包括图灵机（Turing machine）和电路（circuit），它们分别是一致性（uniform）和非一致性（non-uniform）计算模型的代表。而计算资源与计算模型是相关的，对图灵机我们一般讨论的是时间、空间和随机源，而对电路我们一般讨论电路的大小。

• 时间复杂性

• 空间复杂性

• 电路复杂性

• 中央处理器的数量

• 通信量

• …… ​

计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其它复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。

时间复杂性类 ​

确定性图灵机（Deterministic Turing machine，DTM）指每一步都唯一确定的图灵机

• 多项式时间类 $P = \bigcup\limits_{c \geqslant 1} TIME(n^c)$，能在多项式时间内解决的问题
• 指数时间类 $EXPTIME = \bigcup\limits_{c \geqslant 1} TIME(2^{n^c})$

非确定图灵机（Non-deterministic Turing machine，NTM）可以简单定义为具有两个迁移函数 $\delta_1$ 和 $\delta_2$ 的图灵机，在运行时刻，可以毫无章法地选择迁移函数 $\delta_1$ 或迁移函数 $\delta_2$ 进行计算。

非确定图灵机不是物理可实现的，但这类图灵机在理论研究中扮演着非常重要的角色，特别是对我们研究验证问题非常有用。

• 非确定多项式时间类 $NP = \bigcup\limits_{c \geqslant 1} NTIME(n^c)$，一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确

• 非确定指数时间类 $NEXPTIME = \bigcup\limits_{c \geqslant 1} NTIME(2^{n^c})$

知道答案相当于知道了迁移路径，其实就变成了确定性图灵机，因此可以在多项时间内验证

时间谱系定理 ​

一般感觉给图灵机更多的时间或空间就能扩大它所能解的问题类，比如图灵机在时间 $n^3$ 内应该能比在时间 $n^2$ 内判定更多的语言。在一定条件下，这种直觉是正确的，层次定理/谱系定理形式化并且证明了这种直觉。

图灵机是非确定图灵机的特例，所以 $P \subseteq NP$，$EXPTIME \subseteq NEXPTIME$

在指数时间，通用图灵机可以把一台多项式时间的非确定图灵机的所有计算路径都走一遍，用确定性时间来模拟非确定性时间，要有指数级的增长，所以 $NP \subseteq EXPTIME$

所以 $P \subseteq NP \subseteq EXPTIME \subseteq NEXPTIME$

（1）确定性时间谱系定理

若 $f$ 和 $g$ 是时间可构造的且 $f(n)logf(n)=o(g(n))$，

则 TIME(f(n))⊊TIME(g(n))

由确定性谱系定理可以得到 P⊊EXPTIME

（2）非确定性时间谱系定理

若 $f$ 和 $g$ 是时间可构造的且 $f(n+1)=o(g(n))$，

则 NTIME(f(n))⊊NTIME(g(n))

由非确定性谱系定理可以得到 NP⊊NEXPTIME

空间复杂性类 ​

对数空间：

到目前为止，我们只考虑了时间和空间复杂性界限至少是线性的情况，即界限 $f(n)$ 至少是 $n$，现在考察更小的亚线性空间界限

在时间复杂性中，亚线性界限还不够读完输入的，所以这里不考虑它们。在亚线性空间复杂性中机器可以读完整个输入，但是它没有足够的空间存贮输入。为了使对这种情况的考虑有意义，必须修改计算模型。（标准是单带模型，对于亚线性空间界限，采用两带模型，在算法中只分配亚线性空间然后重复利用即可）

我们关注 $logn$ 空间，而不关注如 $\sqrt{n}$ 或 $log^2n$ 空间，其理由与选择多项式时空界限的理由相似，对数空间足以求解许多有趣的计算问题，而且其数学性质也富有吸引力，如当机器模型和输入的编码方法改变时保持稳健性，指向输入的指针可以在对数空间内表示（e.g. 可以使用有限数量的比特（二进制位）来表示指向输入的指针），所以考虑对数空间算法的计算能力的一种方式是考虑固定数目的输入指针的计算能力

对时间复杂性而言，最小资源类是 $P$；对空间复杂性而言，最小资源类是 $L$

确定性图灵机（Deterministic Turing machine，DTM）

• 对数空间类 $L = SPACE(log(n))$
• 多项式空间类 $PSPACE = \bigcup\limits_{c > 0} SPACE(n^c)$
• 指数空间类 $EXPSPACE = \bigcup\limits_{c > 0} SPACE(2^{n^c})$

非确定图灵机（Non-deterministic Turing machine，NTM）

• 非确定对数空间类 $NL = NSPACE(log(n))$
• 非确定多项式空间类 $NPSPACE = \bigcup\limits_{c > 0} NSPACE(n^c)$
• 非确定指数空间类 $NEXPSPACE = \bigcup\limits_{c > 0} NSPACE(2^{n^c})$

空间谱系定理 ​

设空间函数 $f$ 和 $g$ 是空间可构造的且 $f(n) = o(g(n))$，包含关系 $SPACE(f(n)) \subseteq SPACE(g(n))$ 是严格的

由空间谱系定理可以得到

$L \subsetneq PSPACE$

$PSPACE \subsetneq EXPSPACE$

萨维奇定理：

$NSPACE(f(n)) \subseteq SPACE(f^2(n))$

$NL \subseteq SPACE(log^2n)$

推论

$PSPACE = NPSPACE$

$EXPSPACE = NEXPSPACE$

$NL \subsetneq PSPACE$（因为 $SPACE(log^2n) \nsubseteq SPACE(n)$）

⚠️ 不能得出 $L = NL$，$log^2n$ 已经不属于对数层级了

• 用确定性时间来模拟非确定性时间，要有指数级的增长
• 用确定性空间来模拟非确定性空间，只有平方的增长，也就是说确定图灵机可以令人吃惊地以非常横少的空间模拟非确定图灵机，任何消耗 $f(n)$ 空间的非确定图灵机都可以转变为仅消耗 $f(n^2)$ 的确定图灵机，即 $PSPACE = NPSPACE$​

谱系总览 ​

$L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME \subseteq NEXPTIME$

0x04 后量子密码 ​

Shor 算法可以用量子计算机以多项式时间求解 RSA、椭圆曲线等密码体制所基于的困难问题：大整数分解和离散对数求解，即这两类困难问题被降至多项式时间类 $P$ 的范畴，其计算困难性大大降低。

因此，从 2016 年开始，美国国家标准局 NIST 开始了后量子密码标准的制定工作。2020 年 7 月 22 日，NIST 公布了其举办的后量子密码标准竞赛的第三轮入选算法。

NIST 第三轮的所有入选和备选算法，根据不同的困难问题可大致分为以下几类：

1. 基于格问题的密码体制
2. 基于纠错编码解码问题的密码体制
3. 基于多变量方程组求解问题的密码体制
4. 基于椭圆曲线同源问题的密码体制
5. 基于对称密码安全性的密码体制（由于对称密码算法的安全性通常不基于数学困难问题，故对称密码一般被认为是可抵抗量子攻击的）

这几类也基本涵盖了目前所有被认为是安全的后量子密码算法。其中，基于椭圆曲线同源和基于对称密码的两种密码体制，由于其实现效率较低，故并未被 NIST 列入正式入选的算法，但这两类中分别有算法被列入了 8 个备选算法当中。

在 NIST 的 7 个入选算法中，包括 4 个公钥加密/密钥封装算法和 3 个数字签名算法，其中 3 个公钥加密/密钥封装算法和 2 个数字签名算法都属于格密码的范畴，只有 1 个公钥加密/密钥封装算法为基于编码的算法，1 个数字签名算法为基于多变量的算法。尽管并非所有这些入选的格密码算法都会成为最终的胜者并得到标准化，但总体来说，格密码是所有这几类算法中得到最广泛关注的。

Reference ​

• https://zhuanlan.zhihu.com/p/234950092?utm_id=0