当前位置：首页 > news >正文

A Gentle Introduction to Lattice-Based Cryptography 格密码学温和入门学习笔记第四章：容错学习（LWE）问题

news 2026/7/15 20:26:48

《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)	几何路线。寻找距离噪声点最近的唯一格点。	转化为 BDDuSVP，用格规约（BKZ）硬解。	受限于格规约算法在高维下的指数级复杂度。
对偶攻击 (Dual)	统计过滤。寻找短向量消除密钥，利用噪声大小做决策。	寻找 SIS 短解作为过滤器，区分 LWE 与随机数。	同样受限于寻找短向量（格规约）的极高复杂度。
Arora-Ge 攻击	代数路线。利用误差的有限范围构造多项式消除误差。	转化为非线性方程组，线性化后求解。	需要极其庞大的样本量，对 Kyber 等现代算法无效。