姓名：王镭璋
学号：19011110177
部分内容转载自：
https://www.zhihu.com/question/284149874/answer/437454719
https://zhuanlan.zhihu.com/p/45662344
导语：
由于大规模实用的量子计算机终有一天会被制造出来。而传统的，但被广泛应用于网络和系统安全的现行公钥密码算法方案如：RSA、Diffie-Hellman、椭圆曲线等，完全无法抵抗Shor算法在大规模实用的量子计算机上的攻击。因此设计能够抵抗量子计算机的密码方案就成了密码学家们不得不面对的问题，而首要的问题就是寻找能够抵抗量子计算机的底层数学困难问题。由于量子计算机的能力无法预估，因此只能先考虑已知的量子算法不能求解的问题。这样的密码方案是为量子计算机出现后的世界服务的，因此被称作后量子密码学。实现后量子密码算法主要分为以下 4 种途径 [1]：基于编码的、基于哈希的、基于多变量的和基于格的等等，下面一一进行介绍。
基于哈希(Hash-based)的方案
最早出现于 1979 年，基于哈希的签名算法由 Ralph Merkel 提出，被认为是传统数字签名 (RSA、DSA、ECDSA 等 ) 的可行代替算法之一 [2]。基于哈希的签名算法由一次性签名方案演变而来，并使用 Merkle 的哈希树认证机制。哈希树的根是公钥，一次性的认证密钥是树中的叶子节点。基于哈希的签名算法的安全性依赖哈希函数的抗碰撞性。由于没有有效的量子算法能快速找到哈希函数的碰撞，因此（输出长度足够长的）基于哈希的构造可以抵抗量子计算机攻击。此外，基于哈希的数字签名算法的安全性不依赖某一个特定的哈希函数。即使目前使用的某些哈希函数被攻破，则可以用更安全的哈希函数直接代替被攻破的哈希函数此外， SPHINCS，XMSS 也都是基于哈希的公钥密码方案。由于（密码学的）哈希函数的性质，这样的方案天然地具有抗量子的特性。
基于编码(Code-based)的方案
最早出现于 1988 年，主要基于编码的算法使用错误纠正码对加入的随机性错误进行纠正和计算。一个著名的基于编码的加密算法是 McEliece [3]。McEliece 使用随机二进制的不可约 Goppa 码作为私钥，公钥是对私钥进行变换后的一般线性码。Courtois、Finiasz 和Sendrier 使用 Niederreiter 公钥加密算法构造了基于编码的签名方案 [4]。基于编码的算法（例如 McEliece）的方案基于一般线性分组码的解码问题，而该问题是NP难的，这保证了其理论安全性。其算法包括加密、密钥交换等。但基于编码的算法的主要问题是公钥尺寸过大。
基于多变量(Multivariate-based)的方案
基于多变量的算法使用有限域上具有多个变量的二次多项式组构造加密、签名、密钥交换等算法 [5]。多变量密码的安全性依赖于求解非线性方程组的困难程度，即多变量二次多项式问题。该问题被证明为非确定性多项式时间困难。目前没有已知的经典和量子算法可以快速求解有限域上的多变量方程组。与经典的基于数论问题的密码算法相比，基于多变量的算法的计算速度快，但公钥尺寸较大，因此适用于无需频繁进行公钥传输的应用场景，例如物联网设备等。
基于格(Lattice-based)的方案
最早出现于 1996 年，主要用于构造加密、数字签名、密钥交换，以及众多高级密码学应用，如：属性加密 (Attribute-based encryption)、陷门函数 (Trapdoor functions)、伪随机函数 (Pseudorandom functions)、同态加密 (Homomorphic Encryption) 等。基于格的算法由于在安全性、公私钥尺寸、计算速度上达到了更好的平衡，被认为是最有前景的后量子密码算法之一 [6]。与基于数论问题的密码算法构造相比，基于格的算法可以实现明显提升的计算速度、更高的安全强度和略微增加的通信开销 [7]。与其他几种实现后量子密码的方式相比，格密码的公私钥尺寸更小，并且安全性和计算速度等指标更优 [8]。此外，基于格的算法可以实现加密、数字签名、密钥交换、属性加密、函数加密、全同态加密等各类现有的密码学构造。基于格的算法的安全性依赖于求解格中问题的困难性。在达到相同（甚至更高）的安全强度时，基于格的算法的公私钥尺寸比上述三种构造更小，计算速度也更快，且能被用于构造多种密码学原语，因此更适用于真实世界中的应用。近年来，基于 LWE (Learning with Errors) 问题[9] 、 RLWE (Ring-LWE) 问题[10] 、SIS（Shortest Integer Solution）和RSIS（Ring-SIS）的格密码学构造发展迅速，被认为是最有希望被标准化的技术路线之一。
这 4 类途径是最能构造出公钥密码学中已有的各类算法的后量子版本，甚至还能超越（例如基于格的(全)同态加密）等。
当参数选取适当时，目前没有已知的经典和量子算法可以快速求解这些问题。
再次强调，这些算法的安全性，依赖于有没有可以快速求解其底层数学问题或直接对算法本身的高效攻击算法。这也正是量子计算机对于公钥密码算法有很大威胁的原因。
除这 4 种问题之外，还有基于超奇异椭圆曲线 (Supersingular elliptic curve isogeny)、量子随机漫步 (Quantum walk)等技术的后量子密码构造方法。另外，对称密码算法在密钥长度较大时 (例如 AES-256)，也可被认为是后量子安全的。
应用场景
从 NIST 的后量子密码标准征集可以看到，NIST，作为美国国家标准技术研究所，最关心的是最基础且广泛应用的密码学算法：公钥加密、数字签名、密钥交换。现有的几十个提案，用 4 种不同的后量子密码实现方法，完成了这 3 个功能。因此，这些后量子密码算法中的佼佼者可以直接代替现有的公钥加密、数字签名、密钥交换算法，包括：RSA 加密/签名、Diffie-Hellman 密钥交换、椭圆曲线加密/签名等。
简单的讲：后量子密码算法能覆盖到的密码学原语/应用是至少不比现有的公钥密码算法少的。
与现有的公钥密码算法一样，后量子密码可以被应用于更高层次一些的协议/应用，包括：HTTPS (TLS)、数字证书 (PKI)、SSH、VPN、IPsec、比特币等数字货币、U 盾、桌面/移动操作系统等各个领域和应用中。现在用到公钥密码算法的应用，基本可以使用后量子密码算法进行代替。
此外，后量子密码还可以实现更高级的密码学应用，例如同态加密（基于格问题）等。
什么是同态加密？举个例子：你想让财务计算你的年收入，但又不想让财务知道每个月的工资/年终奖等拿了多少，你可以用同态加密对每个数字进行加密，并要求对方运行同态加密的加法/乘法等算法，从而对你加密后的数字进行求和，返回给你被加密的年收入，并且只有你能解密，而财务看到的只是一堆乱七八糟没有任何意义（与均匀随机不可区分）的数字。是不是很神奇？这对于隐私保护等方面尤为重要。对全同态加密感兴趣可以看我对全同态加密的一些概述https://www.jianshu.com/p/a1c245fbf34c。
当然，这只是后量子密码可以实现的高级密码学应用的一个例子。有更广阔的应用等待发掘。
参考文献
[1] Bernstein D J. Introduction to post-quantum cryptography. Proceedings of Post-quantum cryptography. Springer, 2009: 1–14.
[2] Merkle R C, Charles R, et al. Secrecy, authentication, and public key systems[J]. 1979.
[3] Mceliece R J. A public-key cryptosystem based on algebraic[J]. Coding Thv, 1978, 4244:114–116.
[4] Courtois N T, Finiasz M, Sendrier N. How to achieve a McEliece-based digital signature scheme[C]. Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2001. 157–174.
[5] Ding J, Gower J E, Schmidt D S. Multivariate public key cryptosystems[M], volume 25. Springer Science & Business Media, 2006.
[6] Micciancio D, Regev O. Lattice-based cryptography. Proceedings of Post-quantum cryptography. Springer, 2009: 147–191.
[7] Peikert C. Lattice cryptography for the internet[C]. Proceedings of International Workshop on Post-Quantum Cryptography. Springer, 2014. 197–219.
[8] Preliminary Baseline Numbers for Mandatory Optimized Implementations - Google 网上论坛.https://groups.google.com/a/list.nist.gov/forum/#!searchin/pqc-forum/Preliminary$20Baseline$20Numbers$20for$20Mandatory$20Optimized$20Implementations/pqc-forum/CyQPHm Lv3k/JD3 XmgDAgAJ.
[9] Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM (JACM), 2009, 56(6):34.
[10] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[C]. Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2010. 1–23.
