《A Gentle Introduction to Lattice-Based Cryptography》格密码学温和入门是密码学界知名学者、滑铁卢大学University of Waterloo教授Alfred Menezes编写的一份高质量开源讲义。这份讲义专门为高年级本科生和初入学的研究生设计旨在用最通俗易懂、循序渐进的方式揭开后量子密码学Post-Quantum Cryptography, PQC中“格密码”的神秘面纱。目录2.1 基本定义2.2 示例2.3 格的基2.4 连续最小长度Successive minima2.5 基础格问题2.1 基本定义向量的“大小”范数本文介绍了两种测量向量长度的方法欧几里得范数这就是我们初高中学过的“两点间距离公式”。无穷范数它不走直线而是看这个向量在所有坐标轴上绝对值最大的那个分量。通俗地说格lattice可以被看作是实数空间中点的一种规则的、重复的排列。在正式定义中格的定义如下。定义2.1中的一个格lattice,是指由个线性无关的向量的所有整数线性组合构成的集合其中。这个有序集合被称为的一组基basis我们记作。的维数dimension为的秩rank为。格由所有具有以下形式的向量组成其中基可以用一个的基矩阵basis matrix来表示同样记作该矩阵的每一列就是基向量通过这种符号表示格可以被简练地描述为定义 2.2一个格lattice是的一个离散加法子群discrete additive subgroup。离散加法子群意味着是的一个非空子集且对向量的加法和减法封闭定义 2.3中的一个全秩格full-rank lattice是指秩为的格。简单来说全秩格就是在维空间中由条不同方向的“直尺”横平竖直或倾斜地刻画出来的一套无限延伸的、整齐的网格交点集定义 2.4设和为中的格。若则称是的一个子格sublattice为了证明是的子格只需验证的一组基中的每一个向量都是中的元素也就是说它们可以被表示为的一组基中向量的整数线性组合。2.2 示例示例2.5基。由生成的格为其中因此纯粹就是平面上的整数网格如图 2.1(a) 所示。定义2.6设是中的一个全秩格其基为。的基本平行多面体fundamental parallelepiped相对于基定义为等价地可以表示为。基本平行多面体的几何直观极其简单它就是由基向量当成“边”所围出来的那个最小瓷砖基本单元。假设你有两个示例2.5中的基向量和。以原点为起点分别沿着和的方向拉出两条边然后把它们拼成一个平行四边形。这个半开半闭的平行四边形区域包含左边和下边的边界不包含右边和上边的边界就是。如下图所示图中浅绿色的阴影区域就是基本平行多面体。图 2.1R^2 中的三个全秩整数格及其基本平行多面体。示例 2.7二维格考虑基。由生成的格为其中格及其基本平行多面体如图 2.1(b) 所示。接下来证明是的一个子格并且证明的基向量为的基向量为我们要看看能不能找到整数系数让的基向量组合出和对于有其中系数是2和0均为整数所以。同理可证对于也有因为的所有种子基向量和都属于那么根据格的加减封闭性由它们整数相加减繁衍出来的所有的格点也必然都在里面。因此成立。接下来证明两个格不相等只需找出中的一个不属于的向量即可。例如由于的基向量线性无关向量(1,0)表示为的线性组合形式是唯一的。显然唯一的组合如下所示示例2.8二维格考虑基。由生成的格为其中格及其基本平行多面体如图 2.1(c) 所示。图 2.1(b) 和 2.1(c) 表明和实际上是同一个格。这可以通过验证它们互为对方的子格来得到证实。证明过程可以参考上一个例子。一般而言格上计算难题的难度很大程度上取决于用来表示该格的基的质量。例如考虑最短向量问题SVP其要求在给定格的一组基的情况下找出该格中的一个最短非零向量。观察基可以立刻发现就是的一个最短非零向量。相反如果用基来呈现那么要找出这样一个最短向量将会变得极其不直观。解决格问题的一种常用方法是先为所研究的格寻找一组“好”基这意味着这组基的向量相对较短且接近正交。用于完成这项任务的最著名的算法是LLL 算法。2.3 格的基设是中的一个维格其有序基为。以下操作可以将转换为同一个格的另一组基(i) 交换两个基向量。(ii) 将一个基向量替换为其相反向量。(iii) 将一个基向量的整数倍加到另一个基向量上其中。通过重复应用这些操作人们可以为同一个格获得无穷多个不同的基。定理 2.9格基的刻画设是一个维格。一个的矩阵同样是的一组基当且仅当其中是一个元素均为整数且行列式为的矩阵。满足这样条件的矩阵被称为幺模矩阵unimodular matrix。证明已知和生成的是同一个格子。要证把它们连结起来的变换矩阵不仅元素要是整数行列式还必须是。假设和都是格的基。由于它们各自也都是向量空间的基因此必然存在一个可逆矩阵满足。因为的每一列都属于格所以中的元素必须全是整数(根据格的定义格子里的点必须由基向量通过纯整数组合出来。)即。同理必然存在一个可逆矩阵满足。进行代入可得。由于是可逆的则可以同时消去等式左右两边的由此可得。两边取行列式我们得到这意味着或者。因此是幺模矩阵且。已知且是个幺模矩阵。要证它们生成的格子完全一样。因为且的元素全是整数。也就是说的基向量可以用纯整数凑出来。根据定义2.4这直接证明了生成的格子完全被包裹在的格子里面。现在我们想倒过来把用表示那就是。但是我们需要证明里面都是整数否则不符合幺模矩阵定义。由逆矩阵公式知。是伴随矩阵里面的元素全是靠的整数加减乘除算出来的所以铁定全是整数。分母。因为是幺模矩阵只能是 1 或 -1。这就保证了里面的数字居然奇迹般地没有出现任何分数全保住了整数身份既然也是纯整数矩阵那么的基向量也能被纯整数凑出来即。双向包含成立两个格子完全重合。示例2.10一个格的两组基正如我们在示例 2.7 和 2.8 中所看到的矩阵都是中同一个格的基。实际上我们可以验证其中是一个幺模矩阵unimodular matrix。定义2.11一个格的体积volume定义为。体积是一个格不变量lattice invariant这意味着它独立于选择用来表示该格的具体基。证明如果是的任何其他一组基则对于某个幺模矩阵有。因此从而。由此可得。用大白话理解这里的“体积”指的是“人均居住面积”或者“平均每个点占用的空间”。2.4 连续最小长度Successive minima定义 2.12设是一个格。对于每个第个连续最小长度定义为满足以下条件的最小实数格包含个线性无关的向量且每个向量的长度最多为。第一连续最小长度简而言之就是格中最短非零向量的长度。这样的向量并不是唯一的例如如果的长度为那么的长度也是。我们以二维空间为例首先第一阶段寻找即第一个最短非零向量。以原点为圆心画圆当圆的半径从0开始增加刚好达到某个值时圆的边缘第一次撞上了格点在图 2.2 中是撞上了内圈虚线圆上的那两个点。从原点到这两个点的向量就是格子里最短的非零向量。它的长度就是。这个向量不唯一如图2.2所示往右上方有一个往左下方对称的位置也有一个。接下来寻找即方向不同的第二短向量。让圆的半径继续增加直到圆的边界撞上了一个不在原来直线上的新格点对应图 2.2 外圈虚线圆上的点。此时你手里终于握住了两个方向不同线性无关的向量其中较长的那根向量的长度就是。图 2.2 展示了一个二维格的前两个连续最小长度。根据定义连续最小长度构成一个非递减序列图 2.2连续最小长度定义 2.13对于每个整数埃尔米特常数Hermite constant定义为其中最大值是针对所有全秩格full-rank lattices来计算的。由公式 (2) 可以直接得出每一个中的全秩格都满足埃尔米特证明了从而导出了的一个上界1896年闵可夫斯基Minkowski为第一个连续最小长度给出了一个大为改进的上界。定理 2.14闵可夫斯基定理设为一个满秩格子。则有闵可夫斯基定理立刻给出了埃尔米特常数的一个线性上界linear upper bound埃尔米特常数的精确值仅在少数几个低维空间中被明确确定如表 2.1 所示。表 2.1已知精确保留的埃尔米特常数值更一般地紧确的渐近界表明随呈线性增长在此类格中最短非零向量的期望长度大约为定理 2.15闵可夫斯基第二定理设是一个全秩格。则2.5 基础格问题在下文中一个格由一组基来指定并且所有格都被假设为维度为的满秩整数格。定义 2.16最短向量问题Shortest Vector Problem, SVP定义如下给定一个格寻找一个非零的格向量使其长度达到最小值。SVP 已被证明是NP-hardNP困难的(意味着目前在数学和计算机界找不到任何一种可以在“合理时间内”完美求解它的算法。)因此假设它在最坏情况下是困难的是合理的。在实际的密码学应用中我们往往不需要那么死板地非要找到绝对最短的那根向量严格的 SVP 太难了难到连加密解密自己都费劲。所以密码学里经常退而求其次使用近似 SVP不一定要最短只要找一个“足够短”的向量就行。定义 2.17近似最短向量问题Approximate Shortest Vector Problem,或定义如下给定一个格寻找一个非零的格向量其长度至多为其中是近似因子。对于常数级的近似因子依然是 NP-hardNP困难的。然而当时基本不太可能是 NP困难的。另一个重要的格问题是寻找许多个短的线性无关向量。定义 2.18最短独立向量问题Shortest Independent Vectors Problem, SIVP定义如下给定一个格寻找个线性无关的格向量使得其中每一个向量的长度至多为。定义 2.19近似最短独立向量问题Approximate Shortest Independent Vectors Problem,或定义如下给定一个格寻找个线性无关的格向量使得其中每一个向量的长度至多为。需要特别强调的是的解不一定非要构成该格的一组基求得的这组向量虽然线性无关但它们可能并不能通过整数线性组合张成span出整个完整的格。和的计算复杂度状态与及非常相似。具体来说当为常数近似因子时以及都是NP-hardNP困难的此外目前已知存在一种约化关系这进一步凸显了这些基础格问题之间的紧密联系。注意这里“” 的意思是“问题可以约化到问题”即“如果我手里有一个能解决的黑盒子Oracle那我顺手就能把给解了”。也就是说的难度的难度。也就是说只要有的解决方法只要稍作修改就能够解决我们接下来要讨论的基础格问题是寻找一个离给定目标向量最近的格向量。定义 2.20距离的定义设且设。从到的距离定义为给你一个由无数个格点组成的“网格”格再给你空间中任意一个目标点目标向量。这个目标点可能刚好在格点上但大概率卡在格点之间的空隙里。表示的意义就是在整个格中离这个目标点最近的那个格点与之间的绝对距离。定义 2.21最近向量问题 (Closest Vector Problem, CVP)定义如下给定一个格和一个目标向量寻找一个格向量使其最接近也就是说满足定义 2.22近似最近向量问题 (Approximate Closest Vector Problem, 简写为或)定义如下给定一个格和一个目标向量寻找一个格向量满足CVP最近向量问题和 SIVP最短独立向量问题密切相关。已知对于每一个都有并且。CVP 和 SVP最短向量问题也密切相关已知的关系包括对于每一个有以及。图 2.3 总结了 SVP、SIVP、CVP 及其近似版本之间已知的关系。图 2.3SVP、SIVP、CVP 及其近似版本之间已知的关系。 箭头 A→B 表示问题 A 可以在多项式时间内归约到问题 B即 A≤B。由归约导致的近似因子approximation factor的任何损失都会显示在箭头旁边具体解释如下文所述。直箭头没有标注损耗如果你能解决因子为的 CVP你就能无损解决同样因子的 SVP。带标号的弯箭头有因子损耗即文中写的如果你有解决的算法那么你就能用来解决。但是代价很大——解决的的近似因子会平方并乘以变成。在格的理论中因子损耗是不同几何问题在互相转换时因为空间结构不完全等价而支付的“几何代价”。箭头上的损耗公式如就是数学家计算出来的、最精准的“汇率”。
A Gentle Introduction to Lattice-Based Cryptography 格密码学温和入门学习笔记第二章：格
发布时间：2026/6/8 8:21:34
《A Gentle Introduction to Lattice-Based Cryptography》格密码学温和入门是密码学界知名学者、滑铁卢大学University of Waterloo教授Alfred Menezes编写的一份高质量开源讲义。这份讲义专门为高年级本科生和初入学的研究生设计旨在用最通俗易懂、循序渐进的方式揭开后量子密码学Post-Quantum Cryptography, PQC中“格密码”的神秘面纱。目录2.1 基本定义2.2 示例2.3 格的基2.4 连续最小长度Successive minima2.5 基础格问题2.1 基本定义向量的“大小”范数本文介绍了两种测量向量长度的方法欧几里得范数这就是我们初高中学过的“两点间距离公式”。无穷范数它不走直线而是看这个向量在所有坐标轴上绝对值最大的那个分量。通俗地说格lattice可以被看作是实数空间中点的一种规则的、重复的排列。在正式定义中格的定义如下。定义2.1中的一个格lattice,是指由个线性无关的向量的所有整数线性组合构成的集合其中。这个有序集合被称为的一组基basis我们记作。的维数dimension为的秩rank为。格由所有具有以下形式的向量组成其中基可以用一个的基矩阵basis matrix来表示同样记作该矩阵的每一列就是基向量通过这种符号表示格可以被简练地描述为定义 2.2一个格lattice是的一个离散加法子群discrete additive subgroup。离散加法子群意味着是的一个非空子集且对向量的加法和减法封闭定义 2.3中的一个全秩格full-rank lattice是指秩为的格。简单来说全秩格就是在维空间中由条不同方向的“直尺”横平竖直或倾斜地刻画出来的一套无限延伸的、整齐的网格交点集定义 2.4设和为中的格。若则称是的一个子格sublattice为了证明是的子格只需验证的一组基中的每一个向量都是中的元素也就是说它们可以被表示为的一组基中向量的整数线性组合。2.2 示例示例2.5基。由生成的格为其中因此纯粹就是平面上的整数网格如图 2.1(a) 所示。定义2.6设是中的一个全秩格其基为。的基本平行多面体fundamental parallelepiped相对于基定义为等价地可以表示为。基本平行多面体的几何直观极其简单它就是由基向量当成“边”所围出来的那个最小瓷砖基本单元。假设你有两个示例2.5中的基向量和。以原点为起点分别沿着和的方向拉出两条边然后把它们拼成一个平行四边形。这个半开半闭的平行四边形区域包含左边和下边的边界不包含右边和上边的边界就是。如下图所示图中浅绿色的阴影区域就是基本平行多面体。图 2.1R^2 中的三个全秩整数格及其基本平行多面体。示例 2.7二维格考虑基。由生成的格为其中格及其基本平行多面体如图 2.1(b) 所示。接下来证明是的一个子格并且证明的基向量为的基向量为我们要看看能不能找到整数系数让的基向量组合出和对于有其中系数是2和0均为整数所以。同理可证对于也有因为的所有种子基向量和都属于那么根据格的加减封闭性由它们整数相加减繁衍出来的所有的格点也必然都在里面。因此成立。接下来证明两个格不相等只需找出中的一个不属于的向量即可。例如由于的基向量线性无关向量(1,0)表示为的线性组合形式是唯一的。显然唯一的组合如下所示示例2.8二维格考虑基。由生成的格为其中格及其基本平行多面体如图 2.1(c) 所示。图 2.1(b) 和 2.1(c) 表明和实际上是同一个格。这可以通过验证它们互为对方的子格来得到证实。证明过程可以参考上一个例子。一般而言格上计算难题的难度很大程度上取决于用来表示该格的基的质量。例如考虑最短向量问题SVP其要求在给定格的一组基的情况下找出该格中的一个最短非零向量。观察基可以立刻发现就是的一个最短非零向量。相反如果用基来呈现那么要找出这样一个最短向量将会变得极其不直观。解决格问题的一种常用方法是先为所研究的格寻找一组“好”基这意味着这组基的向量相对较短且接近正交。用于完成这项任务的最著名的算法是LLL 算法。2.3 格的基设是中的一个维格其有序基为。以下操作可以将转换为同一个格的另一组基(i) 交换两个基向量。(ii) 将一个基向量替换为其相反向量。(iii) 将一个基向量的整数倍加到另一个基向量上其中。通过重复应用这些操作人们可以为同一个格获得无穷多个不同的基。定理 2.9格基的刻画设是一个维格。一个的矩阵同样是的一组基当且仅当其中是一个元素均为整数且行列式为的矩阵。满足这样条件的矩阵被称为幺模矩阵unimodular matrix。证明已知和生成的是同一个格子。要证把它们连结起来的变换矩阵不仅元素要是整数行列式还必须是。假设和都是格的基。由于它们各自也都是向量空间的基因此必然存在一个可逆矩阵满足。因为的每一列都属于格所以中的元素必须全是整数(根据格的定义格子里的点必须由基向量通过纯整数组合出来。)即。同理必然存在一个可逆矩阵满足。进行代入可得。由于是可逆的则可以同时消去等式左右两边的由此可得。两边取行列式我们得到这意味着或者。因此是幺模矩阵且。已知且是个幺模矩阵。要证它们生成的格子完全一样。因为且的元素全是整数。也就是说的基向量可以用纯整数凑出来。根据定义2.4这直接证明了生成的格子完全被包裹在的格子里面。现在我们想倒过来把用表示那就是。但是我们需要证明里面都是整数否则不符合幺模矩阵定义。由逆矩阵公式知。是伴随矩阵里面的元素全是靠的整数加减乘除算出来的所以铁定全是整数。分母。因为是幺模矩阵只能是 1 或 -1。这就保证了里面的数字居然奇迹般地没有出现任何分数全保住了整数身份既然也是纯整数矩阵那么的基向量也能被纯整数凑出来即。双向包含成立两个格子完全重合。示例2.10一个格的两组基正如我们在示例 2.7 和 2.8 中所看到的矩阵都是中同一个格的基。实际上我们可以验证其中是一个幺模矩阵unimodular matrix。定义2.11一个格的体积volume定义为。体积是一个格不变量lattice invariant这意味着它独立于选择用来表示该格的具体基。证明如果是的任何其他一组基则对于某个幺模矩阵有。因此从而。由此可得。用大白话理解这里的“体积”指的是“人均居住面积”或者“平均每个点占用的空间”。2.4 连续最小长度Successive minima定义 2.12设是一个格。对于每个第个连续最小长度定义为满足以下条件的最小实数格包含个线性无关的向量且每个向量的长度最多为。第一连续最小长度简而言之就是格中最短非零向量的长度。这样的向量并不是唯一的例如如果的长度为那么的长度也是。我们以二维空间为例首先第一阶段寻找即第一个最短非零向量。以原点为圆心画圆当圆的半径从0开始增加刚好达到某个值时圆的边缘第一次撞上了格点在图 2.2 中是撞上了内圈虚线圆上的那两个点。从原点到这两个点的向量就是格子里最短的非零向量。它的长度就是。这个向量不唯一如图2.2所示往右上方有一个往左下方对称的位置也有一个。接下来寻找即方向不同的第二短向量。让圆的半径继续增加直到圆的边界撞上了一个不在原来直线上的新格点对应图 2.2 外圈虚线圆上的点。此时你手里终于握住了两个方向不同线性无关的向量其中较长的那根向量的长度就是。图 2.2 展示了一个二维格的前两个连续最小长度。根据定义连续最小长度构成一个非递减序列图 2.2连续最小长度定义 2.13对于每个整数埃尔米特常数Hermite constant定义为其中最大值是针对所有全秩格full-rank lattices来计算的。由公式 (2) 可以直接得出每一个中的全秩格都满足埃尔米特证明了从而导出了的一个上界1896年闵可夫斯基Minkowski为第一个连续最小长度给出了一个大为改进的上界。定理 2.14闵可夫斯基定理设为一个满秩格子。则有闵可夫斯基定理立刻给出了埃尔米特常数的一个线性上界linear upper bound埃尔米特常数的精确值仅在少数几个低维空间中被明确确定如表 2.1 所示。表 2.1已知精确保留的埃尔米特常数值更一般地紧确的渐近界表明随呈线性增长在此类格中最短非零向量的期望长度大约为定理 2.15闵可夫斯基第二定理设是一个全秩格。则2.5 基础格问题在下文中一个格由一组基来指定并且所有格都被假设为维度为的满秩整数格。定义 2.16最短向量问题Shortest Vector Problem, SVP定义如下给定一个格寻找一个非零的格向量使其长度达到最小值。SVP 已被证明是NP-hardNP困难的(意味着目前在数学和计算机界找不到任何一种可以在“合理时间内”完美求解它的算法。)因此假设它在最坏情况下是困难的是合理的。在实际的密码学应用中我们往往不需要那么死板地非要找到绝对最短的那根向量严格的 SVP 太难了难到连加密解密自己都费劲。所以密码学里经常退而求其次使用近似 SVP不一定要最短只要找一个“足够短”的向量就行。定义 2.17近似最短向量问题Approximate Shortest Vector Problem,或定义如下给定一个格寻找一个非零的格向量其长度至多为其中是近似因子。对于常数级的近似因子依然是 NP-hardNP困难的。然而当时基本不太可能是 NP困难的。另一个重要的格问题是寻找许多个短的线性无关向量。定义 2.18最短独立向量问题Shortest Independent Vectors Problem, SIVP定义如下给定一个格寻找个线性无关的格向量使得其中每一个向量的长度至多为。定义 2.19近似最短独立向量问题Approximate Shortest Independent Vectors Problem,或定义如下给定一个格寻找个线性无关的格向量使得其中每一个向量的长度至多为。需要特别强调的是的解不一定非要构成该格的一组基求得的这组向量虽然线性无关但它们可能并不能通过整数线性组合张成span出整个完整的格。和的计算复杂度状态与及非常相似。具体来说当为常数近似因子时以及都是NP-hardNP困难的此外目前已知存在一种约化关系这进一步凸显了这些基础格问题之间的紧密联系。注意这里“” 的意思是“问题可以约化到问题”即“如果我手里有一个能解决的黑盒子Oracle那我顺手就能把给解了”。也就是说的难度的难度。也就是说只要有的解决方法只要稍作修改就能够解决我们接下来要讨论的基础格问题是寻找一个离给定目标向量最近的格向量。定义 2.20距离的定义设且设。从到的距离定义为给你一个由无数个格点组成的“网格”格再给你空间中任意一个目标点目标向量。这个目标点可能刚好在格点上但大概率卡在格点之间的空隙里。表示的意义就是在整个格中离这个目标点最近的那个格点与之间的绝对距离。定义 2.21最近向量问题 (Closest Vector Problem, CVP)定义如下给定一个格和一个目标向量寻找一个格向量使其最接近也就是说满足定义 2.22近似最近向量问题 (Approximate Closest Vector Problem, 简写为或)定义如下给定一个格和一个目标向量寻找一个格向量满足CVP最近向量问题和 SIVP最短独立向量问题密切相关。已知对于每一个都有并且。CVP 和 SVP最短向量问题也密切相关已知的关系包括对于每一个有以及。图 2.3 总结了 SVP、SIVP、CVP 及其近似版本之间已知的关系。图 2.3SVP、SIVP、CVP 及其近似版本之间已知的关系。 箭头 A→B 表示问题 A 可以在多项式时间内归约到问题 B即 A≤B。由归约导致的近似因子approximation factor的任何损失都会显示在箭头旁边具体解释如下文所述。直箭头没有标注损耗如果你能解决因子为的 CVP你就能无损解决同样因子的 SVP。带标号的弯箭头有因子损耗即文中写的如果你有解决的算法那么你就能用来解决。但是代价很大——解决的的近似因子会平方并乘以变成。在格的理论中因子损耗是不同几何问题在互相转换时因为空间结构不完全等价而支付的“几何代价”。箭头上的损耗公式如就是数学家计算出来的、最精准的“汇率”。
![[MAF预定义的AIContextProvider-12]FileMemoryProvider：为Agent提供可解释、可回溯的记忆能力](http://pic.xiahunao.cn/yaotu/[MAF预定义的AIContextProvider-12]FileMemoryProvider：为Agent提供可解释、可回溯的记忆能力)
