User:Bieraaa/后量子密码学

  提示：此用户页的主题不是量子密码学。

后量子密码学（英語：Post-quantum cryptography，缩写：PQC），又称抗量子计算密码，指的是认为能够抵抗量子计算机破解的加密算法，特别是指非对称加密算法。不同于量子密码学，后量子密码学使用现有的经典计算机，本身不依靠量子力学。时至2018年，当前广泛使用的公钥加密算法均基于三个数学难题：整数分解问题、离散对数问题或椭圆曲线离散对数问题。然而，这些问题均可使用量子计算机并应用秀尔算法破解。目前量子计算机仍处于研发阶段，缺乏足够的计算能力，无法破解加密，但是许多密码学家都在未雨绸缪，尽早研发全新的公钥加密算法以应对将来的威胁。自2006年PQCrypto大会开办以来，该领域的研究工作已成为学术和业界的关注焦点。目前，许多学术和政府机构都在开展相关的研究工作，例如美国国家标准技术研究所（NIST）、欧洲电信标准机构（ETSI）和滑铁卢大学量子计算研究所。

除了公钥加密，量子计算机也威胁对称加密算法和散列函数的安全，但相比公钥加密面临的威胁而言，这一问题并不严重。借助量子计算机，格罗弗算法（Grover's algorithm）可将暴力破解对称加密的难度从$N$次尝试降低到${\sqrt {N}}$次尝试，这样，128位加密（密钥空间$2^{128}$）的安全性就变为64位。但格罗弗算法的加速仅仅是多项式级别的，并非指数级的，因此只需将密钥长度提升一倍即可抵抗这类攻击。因此面临量子计算机的威胁，公钥加密需要重新设计，对称加密则并不需要大幅度的修改。

为了推动标准化，NIST在2017年向公众征集后量子密码方案，并最终收到了各学者提交的共69个设计。

公钥密码学

目前，后量子公钥密码学主要有六个研究方向。

需要注意的是，下述的一些NP困难问题常常被用作难度假设，但NP困难仅限于它们的最坏情况（worst-case）。没有一个已知的密码系统能够将安全性直接规约为NP困难问题。因此，和密码学的其他领域一样，人们对密码系统安全性的信心不是靠NP困难证明的，而是在长期密码分析工作的基础上建立起来的。

格密码学

最短向量问题：格L给定向量空间V中的基向量和范数N，求V中由N度量的最短非零向量。图中蓝色的是基向量，红色的是最短向量。

主条目：格密码学

格密码学（Lattice-based cryptography）指的是在算法构造本身或其安全性证明中应用到格的密码学。 格，又称点阵（lattice），可以直观地理解为空间中的点以固定间隔组成的排列，它具有周期性的结构。更准确地说，是在n维空间R_n中加法群的离散子群，这一数学对象有许多应用。其中还存在几个称为“格问题”的难题，最有代表性的是最短向量问题（Shortest Vector Problem）和最近向量问题（Closest Vector Problem），它们在随机规约的情况下是NP困难的。

1997年发表的GGH加密方案和GGH签名方案是一个有代表性的早期研究。它是利用CVP构造的公钥密码系统。不幸的是，1999年Phong Q. Nguyen的密码分析工作发现了GGH中存在明文信息泄漏问题，而它的CVP问题则可以转换为一个特殊形式，其解决难度大大低于一般形式，从而破解了该加密算法。

而NTRU则是基于SVP构造的公钥密码系统，它同样包括签名和加密两个部分。其中，NTRU签名方案NTRU签名方案参考了GGH的设计，首个版本PASS于1999年首次发表，但随后的密码分析发现数字签名会泄漏关于私钥的信息，而且攻击者可以轻易伪造签名。2001年发表的新版修正了该问题。而NTRU加密方案自1996年发表以来一直未发现根本问题，同时性能高于RSA，受到了较高的评价。

数学家奥德·雷格夫（Oded Regev）在2005年证明了机器学习领域中的容错学习问题（RWE）和最坏情况的格问题一样困难，可用于构造公钥密码，开启了新的研究方向。环容错学习问题（Ring-RWE）是RWE的一个改进版本，解决了其中固有的二次开销带来的效率问题。目前，基于这一体系的有Ring-LWE密钥交换算法与Ring-LWE数字签名算法。Google的NewHope加密算法就是基于Ring-LWE密钥交换的算法。

多变量密码学

主条目：多变量密码学

多变量密码学（Multivariate cryptography）指的是应用了有限域$F$上多元多项式的密码学，包括对称加密和非对称加密。当研究对象是非对称加密时，又叫做多变量公钥密码学（Multivariate Public Key Cryptography），缩写MPKC。此外，由于它常使用二次多项式（Multivariate Quadratic），因此又可缩写为MQ。

考虑$q$阶的有限域$F_{q}$。我们在其中建立一个方程组，它由n个变量与m个方程组成。

${\begin{cases}y_{1}=G_{1}(x_{1},x_{2},...,x_{n})\\y_{2}=G_{2}(x_{1},x_{2},...,x_{n})\\...\\y_{m}=G_{m}(x_{2},x_{2},...,x_{n})\\\end{cases}}$

其中每个方程都是一个多元多项式，通常为二次多项式：

$G_{l}(x_{1},...,x_{n})=\sum _{1\leqslant i\leqslant j\leqslant n}a_{ij}^{(l)}x_{i}x_{j}+\sum _{1\leqslant i\leqslant n}b_{i}^{(l)}x_{i}+c^{(l)}\quad (l=1,2,...,m)$

如果存在一种方式$G^{-1}$能对方程组进行逆运算，我们就可以把这个方程组$G(x_{1},...,x_{n})$本身作为密码系统的公钥。这样一来，数据加密就是将明文$M=(x_{1}',...,x_{n}')$带入方程组，得到密文$(y_{1}',...,y_{n}')$。私钥$G^{-1}$用于解密数据，$M=G^{-1}(y_{1}',...y_{n}')=(x_{1}',...,x_{n}')$；同理，数字签名就是将欲签名的数据$(y_{1}',...,y_{n}')$代入$G^{-1}$求逆得到签名$(x_{1}',...,x_{n}')$，验证签名就是认证$(x_{1}',...,x_{n}')$是否为方程组$G$的解。

破解密码系统的关键就是对方程组进行直接求解。但是，解一般形式的多元多次方程组是NP困难问题，甚至在只涉及到二次多项式时也是如此，这就是MQ问题。我们可以将这个问题作为多变量公钥密码的难度假设。也可以看到，如果方程组是完全随机的，整个系统将是完全不可逆的。因此，建立一个密码系统的关键就是如何构造$G$。

为了建立这样一个系统，我们需要先从一个二次多项式映射$Q$入手。$Q$是一个非线性映射，其逆映射容易计算，这叫做系统的中心映射（central map）。接着，我们将中心映射先后加上$S$和$T$这两个仿射映射，以便隐藏中心映射的结构。最后，公钥为它们的组合形式$G=T\circ Q\circ S$，并以二次多项式方程组给出，由于$S$和$T$的存在，它一个看上去就像一个完全随机的方程组。而$Q$、$S$和$T$则构成私钥。