后量子密码学

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

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

经典的格密码学加密算法包括GGH加密方案（基于CVP，已遭破解）和NTRU加密方案（受GGH启发，基于SVP）。由于容错学习问题与格问题存在联系，因此后来基于容错学习问题（LWE）与环容错学习问题（Ring-LWE）的加密算法也属于格密码学的范畴。

编码密码学（Code-based Cryptography）是应用了编码理论与纠错码的密码学。

其中最早、最有代表性是McEliece密码系统：首先选择一种有已知高效解码算法的纠错码作为私钥，然后对私钥进行变换（用两个随机选择的可逆矩阵${\displaystyle S}$与${\displaystyle P}$“打乱”纠错码的生成矩阵），得到公钥。这样，能高效解码的特殊纠错码就被“伪装”成了一般线性码（general linear code）——一般线性码的解码十分困难，是NP困难问题。其密文就是引入随机错误的码字（codeword），有私钥者可以进行纠错得到明文，无私钥者则无法解码。

McEliece算法首次发表于1978年（仅比RSA晚一年），使用的是二元戈帕码（Binary Goppa code），经历了三十多年的考验，至今仍未能破解。但缺点是公钥体积极大，一直没有被主流密码学界所采纳。但随着后量子密码学提上日程，McEliece算法又重新成为了候选者。许多研究者尝试将二元戈帕码更换为其他纠错码，如里德-所罗门码、LDPC等，试图降低密钥体积，但全部遭到破解，而原始的二元戈帕码仍然安全。

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

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

${\displaystyle {\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}}}$

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

${\displaystyle 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)}$

解一般形式的多元多次方程组是一个计算难题，甚至在只有二次多项式时也是如此，这就是MQ问题。多变量密码学研究的就是基于这类计算难题的密码系统。

散列密码学（Hash-based Cryptography）是应用散列函数的数字签名。散列密码学的研究历史也很长，最早的研究工作包括莱斯利·兰波特于1979年提出的兰波特签名（Lamport signature），与瑞夫·墨克提出的墨克树（Markle tree）。后来以此为基础，又出现了Winternitz签名和GMSS签名，近年来的工作则包括SPHINCS签名与XMSS签名方案。

散列密码学的优点是：数字签名的安全性只取决于散列函数，而足够长的散列函数不受量子计算机威胁。其缺点是：第一，密钥体积极大，因此一直没有被主流密码学界所采纳。后量子密码学重新激发了这一领域的研究。第二，许多散列密码系统的私钥是有状态的，签名后都必须更新私钥的计数器，保证同一状态不可重用，否则签名方案就会遭到攻击者破解。例如，将同一私钥同时在两台机器上使用，就会造成巨大的安全问题。SPHINCS签名解决了这一问题。

超奇异椭圆曲线同源密码学（Supersingular elliptic curve isogeny cryptography）是利用超奇异椭圆曲线与超奇异同源图的数学性质的密码学，可以实现超奇异同源密钥交换（SIDH），具有前向安全性。其使用方法和现有的迪菲－赫尔曼密钥交换相似，有望直接替代当前的常规椭圆曲线密钥交换（ECDH）。