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

《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 attack4.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.1 容错学习问题注4.2LWE中的分布选择在定义 4.1 中秘密向量是从上均匀随机采样的而误差向量是从范围中均匀随机采样的。更一般地和可以从任何分布中采样。LWE 问题的陈述中隐式地假设了其解是唯一的。事实上只要矩阵的行数显著大于其列数该解就有压倒性的概率overwhelming probability是唯一的。为了支持这一论点请注意将矩阵与一个向量相乘会得到空间中的一个向量。该向量空间总共包含个元素。对于每一个秘密向量定义一个以为中心的球体为请注意每个球体内的向量数量为。只有当这个球体中没有任何两个球体发生重叠交叠时LWE 解的唯一性才能得到保证参见图 4.2。图4.2 LWE问题的唯一性通过原文的证明可知这个趋近于 0 的极小概率被称为 可忽略的概率Negligible Probability。这就完美证明了 LWE 问题的解在实际应用中是绝对唯一、不会产生歧义的。例 4.3LWE 实例令且。考虑以下实例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.7ss-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如下这里表示不大于的最大整数即下取整。例如例如图4.3 舍入方程在 Lindner-Peikert 加密方案算法 4.12中我们假设参数满足该条件保证了解密过程的正确性。此外表示最接近的整数如果恰好在两个整数中间则向上取整。图4.4 Lindner-Peikert 加密算法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-OkamotoFO变换来解决第 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.5BDDα 问题定义 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 等现代算法无效。4.4.4 LWE 的平均情况困难性 (Average-case hardness of LWE)Regev 证明了在最坏情况下假设 approx-SIVP近似最短独立向量问题是量子困难的即在量子计算机和经典计算机上都无法攻克那么 LWE 在平均情况下就是困难的。