《A Gentle Introduction to Lattice-Based Cryptography》（格密码学温和入门）是密码学界知名学者、滑铁卢大学（University of Waterloo）教授Alfred Menezes编写的一份高质量开源讲义。
这份讲义专门为高年级本科生和初入学的研究生设计，旨在用最通俗易懂、循序渐进的方式，揭开后量子密码学（Post-Quantum Cryptography, PQC）中“格密码”的神秘面纱。
目录
4.1 问题陈述
4.2 Lindner-Peikert 公钥加密方案
4.3 LWE格
4.4 LWE的困难性
4.4.1 原始攻击（Primal attack）
4.4.2 对偶攻击 (Dual attack)
4.4.3 Arora-Ge 攻击 (Arora-Ge attack)
4.4.4 LWE 的平均情况困难性 (Average-case hardness of LWE)
4.1 问题陈述
LWE 问题由四个参数决定：正整数和
（其中
），一个素数模数
，以及一个满足
的噪声界限（noise bound）
。
定义 4.1容错学习问题（The Learning With Errors problem），记作，其定义如下：随机选择一个矩阵
，一个秘密向量
，以及一个误差向量
，并令
。已知数对
，目标是恢复出秘密向量
；参见图 4.1。参数
是 LWE 样本的数量。
：表示“从某个集合中均匀随机地选择（Randomly and uniformly chosen from）”。
：表示模
的整数集合（即
）。所有的计算都是在这个“时钟世界”（模运算）里进行的。
矩阵
：这是一个公开的随机矩阵，由
行
列的数字组成。
秘密向量
：这是需要保护的秘密（密钥），外界无法直接得知。
误差向量
：这是故意引入的“噪音（Noise）/ 误差”。它的每一个数字都在
的一个小范围内选择（
是边界）。正是因为有了它，这个问题才变得极难破解。
向量
：它是通过矩阵乘法加上噪音计算出来的公开结果，即
。
：样本数量，也就是公开给你的线性方程组的个数。
注4.2（LWE中的分布选择）在定义 4.1 中，秘密向量是从
上均匀随机采样的，而误差向量
是从范围
中均匀随机采样的。更一般地，
和
可以从任何分布中采样。
LWE 问题的陈述中隐式地假设了其解是唯一的。事实上，只要矩阵
的行数
显著大于其列数
，该解就有压倒性的概率（overwhelming probability）是唯一的。
为了支持这一论点，请注意：将矩阵与一个向量
相乘，会得到
空间中的一个向量
。该向量空间总共包含
个元素。
对于每一个秘密向量，定义一个以
为中心的球体为：
请注意，每个球体内的向量数量为。只有当这
个球体中没有任何两个球体发生重叠（交叠）时，LWE 解的唯一性才能得到保证（参见图 4.2）。
通过原文的证明可知，这个趋近于 0 的极小概率被称为 可忽略的概率（Negligible Probability）。这就完美证明了 LWE 问题的解在实际应用中是绝对唯一、不会产生歧义的。
例 4.3（LWE 实例）令且
。考虑以下
实例：
LWE 的挑战目标是找到一个秘密向量和一个误差向量
，使得
。
结果表明，这个 LWE 实例有三个解：
,
；
,
；
,
。
这个例子用具体的数字展示了如果参数选得不合适（比如样本数太小），LWE 的解确实会出现“不唯一”的情况。
判定性 LWE 问题（Decisional LWE problem）。在 LWE 的判定性变体中，挑战目标是区分一个合法的 LWE 实例与一个纯随机的实例
，其中
是完全随机选择的。
在后一种情况（纯随机实例）下，人们预期方程是没有 LWE 解的。本质上，判定性问题就是去判定一个解是否存在。
定义 4.4判定性容错学习问题，记作，其定义如下：随机选择一个矩阵
，一个秘密向量
，一个误差向量
，以及一个纯随机向量
。令
。以各占
的等概率，设置目标向量
或者
。已知一个问题实例
，目标是去判定（要求成功概率显著大于
）到底是
还是
。
定理 4.5LWE 与 DLWE 在计算上是等价的（computationally equivalent）。
短秘密 LWE 问题（Short-secret LWE problem）。在 LWE 问题的一种短秘密变体中，秘密向量的各个分量（坐标）是从与误差向量
的各个分量完全相同的分布中采样得到的。下面给出定义的完整版：
定义 4.6短秘密容错学习问题，记作，其定义如下：随机选择一个矩阵
，一个秘密向量
，以及一个误差向量
，并定义
。已知数对
，目标是恢复出秘密向量
。
与标准 LWE 的情况不同，这里不需要（
远小于
）这一条件，就能保证 ss-LWE 以极高的概率拥有唯一解（参见习题 4.3）。
例 4.7（ss-LWE 实例）令且
。考虑以下
实例：
ss-LWE 的挑战目标是找到在范围内的
和
，使得
。
结果表明，这个 ss-LWE 实例拥有唯一解：
- 它用实际的数据验证了我们刚刚讨论过的理论：在短秘密变体中，即使样本数
不远大于未知数个数
（这里甚至完全相等，
），解依然以极高的概率是唯一的。
定理 4.8LWE 与 ss-LWE 问题在计算上是等价的（computationally equivalent）。更准确地讲，
并且
4.2 Lindner-Peikert 公钥加密方案
定义 4.9判定性短秘密容错学习问题（Decisional short-secret Learning With Errors problem），记作，其定义如下： 随机选择一个矩阵
，一个秘密向量
，一个误差向量
，以及一个随机向量
。定义
。 令
的概率为
，
的概率为
。 已知数对
，目标是以显著大于
的成功概率来判定
还是
。
定义 4.10令为一个奇整数，且令
。定义
的对称模
（symmetric mod q）为：
mods运算自然地延伸到所有整数：如果，那么：
- 举例：如果给你一个很大或者很小的整数
（比如
）
第一步（普通求余）：
第二步（对称映射）：
所以，
。
定义 4.11令为一个奇整数，且令
。我们定义舍入函数（rounding function）
如下：
这里表示不大于
的最大整数（即下取整）。
- 例如：
- 例如：
在 Lindner-Peikert 加密方案（算法 4.12）中，我们假设参数满足：
该条件保证了解密过程的正确性。此外，表示最接近
的整数，如果恰好在两个整数中间，则向上取整。
算法4.12Lindner-Peikert 公钥加密方案
定义域参数 (Domain parameters):，其中
。
1. 密钥生成 (Key generation)
Bob 执行以下操作：
随机选择矩阵
，秘密向量
，以及噪声向量
。
计算
。
Bob 的加密钥（公钥）为
；他的解密钥（私钥）为
。
公钥方程：。如果没有噪声
，这就是一个普通的线性方程组。给定
和
，任何人都用高斯消元法轻松算私钥
。但加上了微小的随机噪声
后，它就变成了 LWE 问题。在数学上，只要矩阵足够大，想要从
中反推出
极其困难，这就保证了公钥的安全。
2. 加密 (Encryption)
为了给 Bob 加密一个明文消息，Alice 执行以下操作：
- 获取 Bob 公钥
的真实副本。
- 随机选择向量
，噪声向量
，以及噪声标量
。
- 计算
以及
（参见图 4.4）。
- 输出密文
。
使用 Bob 的公钥，并引入了自己这一侧的随机数
和新噪声
。计算
：
计算
：
最后打包出来的密文是包含两个部分的组合：
。
3. 解密 (Decryption)
为了解密密文，Bob 执行以下操作：
- 计算
。
Bob 收到后，利用私钥
计算
：我们把 Alice 计算的
和
带入这个解密公式展开来看：
因为公钥，所以其转置为
。代入进去：
消去共同项之后，结果变为：
其中为一堆噪声的总和
：
如果
，结果就是
（一个很小的数字）。
如果
，结果就是
（一个接近半模的数字）。
只要那个著名的公式 (12) 成立，就能保证这个总噪声绝对不会跨越
的界限。此时 Bob 只需要使用
（模四舍五入函数），看看结果更靠近
还是更靠近
，就能完美剔除噪声， 100% 还原出正确的
。
例4.13(Lindner-Peikert 加密)
定义域参数：（模数），
（维度），且
（错误/噪声边界）。
密钥生成：Bob 选择：
并计算：
Bob 的加密钥（公钥）为，他的解密钥（私钥）为
。
加密：为了给 Bob 加密明文消息，Alice 选择：
并计算：
密文为。
解密：为了解密，Bob 使用他的解密钥
计算：
并对其进行舍入（取最接近的明文信号）以恢复出明文。
Lindner-Peikert 加密方案有两个主要缺点：
第一，它仅支持单个比特（single bit）的加密。
第二，它实现了抗选择明文攻击（CPA）的安全性，但无法抵抗选择密文攻击（CCA）
第一个问题可以通过使用 Module-LWE（代数模容错学习） 变体来解决（在第 5 节中介绍）。第二个问题可以通过应用 Fujisaki-Okamoto（FO）变换来解决（第 6.4 节）。
4.3 LWE格
与 SIS（短整数解问题）一样，LWE 问题也可以用格（lattices）来进行一种自然的几何解释。
定义 4.14给定一个的实例
，其关联的 LWE 格 定义为：
设表示由矩阵
的前
行组成的
子矩阵。在随机选择矩阵
的情况下，矩阵
在模
下是可逆的（以压倒性的极高概率成立）。在本节的后续部分中，我们均假设该条件成立。
定理 4.15LWE 格是一个满秩（full-rank）的
元整数格（
-ary integer lattice），其体积（volume）为：
定义 4.16设是
中的一个满秩格。
的对偶格（dual）定义为：
设是
的一组基。可以证明
是一个满秩格，其基矩阵为
。此外，
定理 4.17设，则：
4.4 LWE的困难性
本节介绍了针对 LWE 的三种攻击方法，并简要讨论了 LWE 的平均情况困难性（average-case hardness）。
4.4.1 原始攻击（Primal attack）
格向量非常接近目标向量
。这一观察很自然地将 LWE 问题与有界距离译码（Bounded Distance Decoding, BDD）问题联系在了一起（如图 4.5 所示），BDD 问题旨在寻找一个接近给定目标向量的格向量。
定义 4.18有界距离译码问题（Bounded Distance Decoding Problem），记作，其定义如下： 给定一个格
以及一个向量
，并保证在距离
不超过
的范围内存在唯一的格点
，求该格点
。
我们可以通过 Kannan 嵌入技术，把这个“找圆圈内唯一红点”的游戏，转化为在高维格里“找最短向量（uSVP）”的游戏。这就是学术界破解 LWE 密钥时，最常用的原始攻击（Primal Attack）路线。
4.4.2 对偶攻击 (Dual attack)
该攻击将 DLWE（决策型 LWE）问题规约到（Short Integer Solution，短整数解问题，见定义 3.13），然后使用 §3.3.1 中描述的对偶攻击进行求解。
4.4.3 Arora-Ge 攻击 (Arora-Ge attack)
当误差边界固定时，针对 LWE 的 Arora-Ge 攻击可以在多项式时间内运行。然而，它在实际中是低效的，因为其运行时间函数是一个关于
的极高次数的多项式。此外，该攻击对于 Kyber 和 Dilithium 中产生的 LWE 实例是无效的，因为它需要大量的 LWE 样本（要求
），而在 Kyber 和 Dilithium 中，样本数量仅为
。
| 攻击方法 | 核心思想 | 解决方式 | 缺点/局限 |
| 原始攻击 (Primal) | 几何路线。寻找距离噪声点最近的唯一格点。 | 转化为 BDD | 受限于格规约算法在高维下的指数级复杂度。 |
| 对偶攻击 (Dual) | 统计过滤。寻找短向量消除密钥，利用噪声大小做决策。 | 寻找 SIS 短解作为过滤器，区分 LWE 与随机数。 | 同样受限于寻找短向量（格规约）的极高复杂度。 |
| Arora-Ge 攻击 | 代数路线。利用误差的有限范围构造多项式消除误差。 | 转化为非线性方程组，线性化后求解。 | 需要极其庞大的样本量 |
4.4.4 LWE 的平均情况困难性 (Average-case hardness of LWE)
Regev 证明了：在最坏情况下，假设 approx-SIVP（近似最短独立向量问题）是量子困难的（即在量子计算机和经典计算机上都无法攻克），那么 LWE 在平均情况下就是困难的。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
