19011110177王镭璋（原创）
在之前发文章中已经阐明了研究后量子（抗量子）公钥密码的重要性和紧迫性，基于格的构造的后量子公钥密码体制目前最看好的构造的方法之一。以下我将首先介绍有关格上高斯采样技术的核心思想以及格上高斯采样技的应用，然后我将对今年最新的有关格上高斯采样技术研究的欧密论文Integral Matrix Gram Root and Gaussian Sampling without floats[1]的核心思想和具体技术步骤进行介绍。（欧洲密码学会议是密码学界三大顶级会议之一）。
许多基于格构造的高级密码系统如：基于身份体制加密、基于属性加密、函数加密和群签名等等，都需要从某个离散高斯分布中提取格点或者格的陪集中的点[1]。一个经典的例子就是Peikert在GPV08中提出的格上的签名方案[2]。在Peikert的签名改进方案[3]中，Peikert通过对初始陷门格基抽样出的椭圆型（非球型）高斯分布与对应的另一椭圆型（非球型）高斯分布进行卷积，从而获得球型高斯分布。最后对以消息m的哈希值为球心的球型高斯分布的抽样作为消息m经哈希函数作用后的签名值。如此Peikert的格基签名方案能够有效地抵御利用大量的签名和消息对来暴露陷门格基几何形状从而获得有关陷门格基的有效信息的攻击。Peikert在改进方案[3]中最关键的一步便是：求出与初始陷门格基抽样出的椭圆型高斯分布相对应的，决定另一椭圆型高斯分布的矩阵。因为只有求出矩阵才能从椭圆型高斯分布中采样获得所需添加的扰动。其中矩阵是协方差矩阵的Gram平方根矩阵，其中s为最终采样的高斯分布宽度。Peikert在论文[3]中的做法是对正定矩阵进行Cholesky分解得到方阵。这样一来Peikert在论文[3]中的方案就存在高精度浮点数运算和存储问题。因为在一般情况下若限定正定矩阵的Gram平方根矩阵是方阵，则Cholesky分解得到的Gram平方根矩阵中的元素大概率是无理数。在签名方案的实际实现中，从n阶实数矩阵对应的椭圆型高斯分布中采样需要存储至少n(n+1)/2个长度很长的浮点数，以保证高精度的浮点计算结果与理论结果的误差可忽略。（根据安全性分析，为保证采样的准确性，至少需要保留n阶方阵中每个元素小数点后位，随着安全参数的增长，计算和存储方面的开销均会迅速增长，其中s为最终采样的高斯分布宽度）。此外还需要繁琐的数值稳定性分析并讨论由于舍入误差造成的安全性损失。对密码系统所基于一般的（通用的）判别性问题的高效数值稳定性分析仍是一个公开问题。
为了克服这些缺点，2020年欧密论文Integral Matrix Gram Root and Gaussian Sampling without floats[1]提出一种新的求正定矩阵的整数Gram平方根矩阵的方法。（即利用本文的方法最后求得的的Gram平方根矩阵是整数矩阵）从而避免了浮点数矩阵的存储和最后需要在高精度浮点数矩阵上抽样时所造成的繁杂运算和分析的问题。为了将正定矩阵分解为整数Gram平方根矩阵，欧密[1]使用了两种算法：1.对小特征值整数正定矩阵递归分解求其对应的整数Gram平方根矩阵算法；2.正定矩阵特征值约减算法。
算法1的核心思想是利用拉格朗日四平方和定理和整数gadget基可用整数向量表示整数的方法，通过递归调用自身，将输入的整数正定矩阵一列（行）一列（行）地逐步分解为对应的Gram平方根矩阵。具体来说就是：第一次调用时会对一开始输入的n维正定矩阵的第一列（第一行）（正定矩阵是对称矩阵）的所有元素进行分解。具体分解为：对第一列（第一行）的所有非对角元元素分解为整数gadget基向量与非对角元元素在整数gadget基下的坐标向量c内积的形式。对角元元素则是利用Rabin&Shallit的算法[4]在多项式时间内分解为四个整数平方和的形式。随后将第一列（第一行）元素的分解记录到中。如此经过一次调用，就将求n维正定矩阵的整数Gram平方根矩阵问题化为求维正定矩阵的整数Gram平方根矩阵问题。如此循环调用n次算法1就可以求出n维正定矩阵的整数Gram平方根矩阵问题（一维的情况，或者说是最底层的情况则是利用Rabin&Shallit的算法[4]将整数分解为四个整数平方和）。
算法1的计算过程不涉及任何浮点数的运算和存储。只使用算法1似乎就能无需使用浮点数运算就求出正定矩阵的整数Gram平方根矩阵的任务。但算法1有一个缺点：算法1在每一次递归调用自身时，虽然将输入正定矩阵的第一列（行）元素进行了分解，但需要对输入矩阵的未分解的剩余部分加上分解正定矩阵才能保证最后递归输出结果的正确性，而这将增大作为下一次递归调用输入的正定矩阵的特征值。当初始的输入的整数正定矩阵的维数n较大时，会导致最后采样签名的球型高斯分布的宽度过大致使整个密码系统的开销过大。
因此欧密[1]的做法是先调用（至多两次）特征值约减算法先将初始输入的正定矩阵分解成一个特征值足够的小的整数正定矩阵和剩余正定矩阵部分。剩余正定矩阵在调用特征值约减算法的过程中已被分解为，其中下三角型整数矩阵均在运行特征值约减算法的过程中已求出。的分解共同组成了的整数Gram平方根矩阵，再利用算法1求出特征值已足够的小的整数正定矩阵对应的整数Gram平方根矩阵。最后组合和就求出了初始输入的正定矩阵的整数Gram平方根矩阵。
但需要指出的是[1]中所采用的正定矩阵特征值约减算法中一定精度的浮点数运算仍未避免，因为该算法的关键步骤是对某个整数正定矩阵进行Cholesky分解：，再对中各个元素取其最近整数得到的近似整数Gram平方根矩阵。本文仍需要一定精度的浮点计算，这让人担心是否又会出现Peikert方案[3]中的诸多问题。这里需要说明的是本文的优势在于：1.特征值约减算法求整数正定矩阵的近似整数Gram平方根矩阵时，所需的浮点计算对精度的要求远低于抽样时对精度的要求，也就是说只需较低的精度该算法就能完成矩阵特征值约减任务。2.特征值约减算法运行过程中所需记录的和等中间变量矩阵以及最后求得整数Gram平方根矩阵均是整数矩阵，无需存储浮点数形式的矩阵，节省了存储方面的开销。3.特征值约减算法和算法1组合最后求得的整数Gram平方根矩阵是整数矩阵，这意味着求签名采样时是在整数上的高斯采样，这避免了需要高精度浮点数计算逼近的实数上的高斯采样，节省了计算、存储的开销。同时也无需额外的复杂的数值稳定性分析和安全损失讨论。
由于算法1和算法2的组合算法是在整数环上进行高斯采样，无法利用2的幂次分圆环的代数结构进一步提高存储和计算效率。同之前的想法一致，本文使用不破坏环结构的递归分解算法和特征值约减算法，充分利用2的幂次分圆环结构带来的存储和计算效率的提升的优势的同时，实现无需浮点数运算的高斯采样。
具体来说就是从求原先定义在整数环上的正定矩阵的整数Gram平方根矩阵问题变成了求定义在2的幂次分圆环上的正定矩阵的整数Gram平方根矩阵问题。求解的思路同之前一样，需要一个迭代算法将求n维的正定矩阵的整数Gram平方根矩阵问题，逐步迭代，逐步投影（约减）到更低一维的正定矩阵的整数Gram平方根矩阵问题上，只是正定矩阵中的元素从整数变成了2的幂次分圆环上的元素。为实现上述的迭代降维算法，同时不破坏环的结构，本文将2的幂次分圆环的初始正定矩阵的第一列（行）上非对角元环元素用环上gadget基分解表示，对角元则经过不断的投影到更小的子环上直到最终投影到的最底层情况，就可以利用Rabin&Shallit的算法[3]在多项式时间内将整数分解为四个整数的平方和。如此n次调用迭代降维算法就能得到上的正定矩阵的整数Gram平方根矩阵。
同时与之前一样，由于迭代算法会在迭代过程中不断增大输出的（下一次的输入）正定矩阵的特征值，同样需要一个对环元素矩阵特征值进行约减的算法。解决方法也与之前一样，利用保持环结构的Cholesky分解方法先求得一些近似逼近f环元素根gg*，再对f与gg*的差（特征值足够小的部分）调用上述迭代降维算法求得上的正定矩阵的整数Gram平方根矩阵。
总结一下，相较于Peikert[3]中的方案，今年欧密的这篇论文[1]提出的整数上高斯采样算法避免了浮点数矩阵的存储和最后所必需的高精度高斯采样时所造成的繁杂运算和分析的问题。相较于Genise-Micciancio[5]中的方案，本文提出的2的幂次分圆环环上高斯采样算法在保持了环结构带来的存储和计算效率的提升的优势的同时，避免了所必需的高精度浮点数运算，整体来看本文提出的高斯采样算法更简单，更高效。
关键词：格上高斯采样；整数矩阵整数Gram根；拉格朗日四平方和定理；Cholesky分解；Gadget基
参考文献
