1.4 基于格的后量子密码

在现有的后量子密码方案中，格密码（Lattice-Based Cryptography，LBC）依靠独特的困难问题规约结果，被认为是最有可能成为下一代公钥密码标准的新型密码结构，引起了很多研究者的高度关注和重视。格的概念最早由Guass于18世纪提出，后经过Lageange等人的发展，逐渐形成了一套关于格的数学理论[8]。在相当长的一段时间内，密码界的研究者更侧重于研究解决格困难问题的算法和格理论在密码分析中的应用[9]。在密码学中，格理论最初仅仅是一种对公钥密码算法进行安全性分析的工具。1996年，Ajtai开创性地提出了一种构造一类随机格的方法，给出了格困难问题从最坏情况到平均情况的规约证明[31]。基于Ajtai的这项研究，研究者随后便开始利用随机格构建单向陷门函数、公钥加密、抗碰撞的哈希函数和数字签名等一系列的密码方案。1997年，Ajtai和Dwork提出了具有里程碑意义的首个基于格的公钥加密方案——Ajtai-Dwork密码体制[32]。该方案的安全性规约工作于2003年得到了Regev的完善[33]。同年，Goldreich、Goldwasser和Halevi等人提出了更易理解且实用的GGH密码体制。这是一种基于格的公钥加密和数字签名方案，缺点是缺少最坏情况下的安全性证明[34]。尽管后来Micciancio改进了GGH密码体制[35]，但它的安全性问题仍然没有得到解决。1998年，Hoffstein等人首次提出了NTRU[36]这一使用多项式环设计的密码体制，全面优化了加解密速度和密钥长度。尽管NTRU密码体制的设计利用了格的结构性，但无法找到已知的格困难问题进行严格的安全性规约分析。

使得格密码真正意义上同时兼顾实用性、高效率和可证明安全性的研究工作来自Regev于2005年发表的论文[37]。Regev给出了第一个基于误差学习（Learning With Errors，LWE）问题构造的公钥加密方案，标志着格密码进入了一个全新的时期。2010年，V.Lyubashevsky和C.Peikert等人进一步基于环域上的LWE（Ring-LWE）问题设计了Ring-LWE公钥加密方案[38]，有效缓解了LWE公钥加密方案中过大的密钥尺寸而带来的存储问题。2011年，R.Lindner和C.Peikert对Ring-LWE公钥加密方案进行了更为全面的安全性分析，平衡了算法的时间复杂度，给出了不同安全等级下安全参数的计算，使得基于Ring-LWE问题设计的格密码方案有更加易于实现的密钥和密文尺寸[39]。2017年，Albrecht等人给出了MLWE到RLWE的规约证明[16]，为基于MLWE问题构建密码方案的安全性提供了理论基础。LWE问题及其变体一直都是格密码学中最为热门的研究领域。研究者基于LWE问题及其变体构建了许多公钥密码方案，包括公钥加密方案[17-18]、密钥交换协议（如NewHope[19]、Frodo[20]、Kyber[21]）、数字签名方案[22-23]和伪随机数生成函数[24-25]等。

基于LWE问题及其变体的密码方案虽然兼具了安全性和高效性，但也存在固有的缺陷。LWE方案的安全性主要依赖向公钥和密文引入随机、独立的误差。该误差来自对噪声分布的采样。这就导致基于LWE问题及其变体的方案始终存在公钥和密文体积较大的问题，在实现时需要消耗大量的存储空间和带宽来保存和传输数据。为了解决这个问题，Banerjee等人于2012年提出了带舍入学习困难（Learning With Rounding，LWR）问题，并证明在特定的参数选取下，LWR问题和LWE问题的复杂度等价[26]。在此基础上，Alwen[27]、Bogdanov[28]和Alperin-Sheriff[29]等人陆续对LWR问题的安全性进行了进一步的证明。LWR问题可以看作LWE问题的“去随机化版本”。与LWE问题不同的是，LWR问题中的误差是通过模域的转换结合四舍五入运算而确定性地引入的。这种方法避免了向每个样本的内积添加随机误差项，减小了公钥和密文的体积。LWR问题也演变出RLWR问题和MLWR问题等变体，均可以看作LWE体系中对应问题的衍生。LWR问题及其变体的提出为格密码方案的设计提供了新的思路，但由于LWR问题特殊的参数选取导致了一些能够应用到LWE问题中的高效数学算法，如NTT变换，无法应用到LWR问题中，以至于基于LWR问题的密码方案面临运算效率较低的问题。在相当长的一段时间内，基于LWR问题构建密码算法并不属于格密码学中热门的研究内容。随着许多优化方法的提出和一些优秀的实现实例的证明，这种状况正在逐渐发生改变。

随着格密码的不断发展，公钥长度与密文长度得到了更好的优化，运算性能得到了全面的提升，安全性分析也更加完备。具体而言，格密码的优点主要体现在三个方面：

（1）拥有完备的安全性证明。当前的格密码方案主要是基于SIS、LWE、Ring-LWE和Module-LWE等问题构建的，其安全性均已被证明建立在解决最坏情况下最短向量问题（Shortest Vector Problem，SVP）和最短线性无关向量问题（Shortest Independent Vector Problem，SIVP）等格困难问题的困难程度上。

（2）高效且易于实现。格密码方案通常仅需要十几位的向量、矩阵和多项式模运算，相较于RSA、ECC等需要几百位以上的大数模乘、模幂运算的密码方案，更易于实现。格密码方案的运算流程简单，有更高的运算速度。

（3）灵活性强，用途广泛。格密码的安全参数易于设计并选取，能被广泛应用于多样化、具有不同安全需求的密码系统。另外，格密码不仅可以用于构造公钥加密、密钥封装机制和数字签名等方案，还能用于构建单向陷门函数（Trapdoor Functions）、属性加密方案（Attribute-Based Encryption）和同态加密方案（Homomorphic Encryption）等高级密码学应用。

表1-3中列出了NIST PQC项目中各类后量子密码方案的实际性能及数量的具体对比。可以看到，在众多的后量子密码方案中，基于格的后量子密码方案，即格密码方案，凭着自身众多优异的特点，在NIST PQC项目的三轮评选中方案总数始终保持第一，毫无疑问地成为最有潜力的一类后量子密码方案。目前，在经过第三轮PQC标准化会议的评审后，剩余的7个主选方案中，基于格的方案有CRYSTALS-KYBER（简称Kyber）、NTRU（Theory Research Unit）、SABER（也称Saber）、FALCON和CRYSTALS-DILITHIUM等5个，占据了绝大多数；基于编码的方案为Classic McEliece；基于多变量的方案为Rainbow。

后量子时代下的信息安全如图1-3所示。可以预见，在传统公钥密码体制面临安全隐患的未来，从无处不在的物联网终端设备到超大规模的云计算平台、智能电网、工业应用、车辆联网、医学检测等，都有望部署格密码来保障后量子时代下的信息安全。