《A Gentle Introduction to Lattice-Based Cryptography》格密码学温和入门是密码学界知名学者、滑铁卢大学University of Waterloo教授Alfred Menezes编写的一份高质量开源讲义。这份讲义专门为高年级本科生和初入学的研究生设计旨在用最通俗易懂、循序渐进的方式揭开后量子密码学Post-Quantum Cryptography, PQC中“格密码”的神秘面纱。目录5.1 多项式环5.2 模小整数解问题Module-SIS5.3 模容错学习MLWE5.1 多项式环设为素数为正整数。多项式环由中次数小于的多项式组成其乘法通过约简多项式来进行。要将两个多项式相乘具体步骤为首先在中按照普通的多项式乘法将它们相乘得到一个最高次数不超过的多项式然后用除以得到一个最高次数不超过的余数多项式。与在环中的乘积即为该余数多项式。例 5.1多项式环设且。则由中最高次数不超过 3 的多项式组成。设以及。则它们在中的和与差分别为以及和在中的乘积是一个 6 次多项式将除以的运算可以通过将替换为、替换为、替换为然后进行化简来实现。我们得到因此和在中的乘积为多项式表示为向量 (Polynomials as vectors).设。环中的多项式可以用其长度为的系数向量表示为例 5.2将多项式表示为向量设则商环为。设以及。和的向量表示形式分别为可以验证和在中的和sum、差difference以及积product的向量表示形式分别为基于矩阵的多项式乘法在环中的多项式乘法可以表示为矩阵与向量的乘积。设并设则现在观察因为在模的意义下。因此的向量表示正好是向量表示的右循环移位且循环过来的元素取相反数变负号。由式 (17) 可知若则上述矩阵被称为反循环矩阵anti-circulant matrix / 斜循环矩阵记作。例 5.3中乘法的矩阵表示设$n 5$则商环为。设。则的向量表示形式为因此在中。定义 5.4设为奇整数。整数的大小size也称为的无穷范数infinity norm定义为其中表示普通实数的绝对值。注意。例如若则。我们有以及。定义 5.5多项式的大小size定义为这也被称为的无穷范数infinity norm。定义 5.6设为一个远小于的正整数。中小多项式small polynomials组成的集合定义为如下文所示小多项式的乘积也相对较小。定理 5.7固定商环。设和为正整数满足。若且则例 5.8小多项式设则商环为。设。的中心化模表示形式为因此是一个相对于的小多项式。类似地设为一个相对于的小多项式。则和在中的乘积为其中心化模表示形式为其属于。注意乘积的范数界限满足5.2 模小整数解问题Module-SIS模Module 将向量空间Vector Space的概念进行了推广即将向量空间的标量域Field替换为了一个环Ring。这里我们关心的模是它由长度为的多项式向量组成。对于模元素其大小范数定义为其中多项式的大小已在定义 5.5Definition 5.5中给出。中元素的加法和减法是逐分量componentwise进行的确保计算结果仍然落在内。中两个向量和的内积Inner Product定义为其计算结果是中的一个多项式。例 5.9模运算设因而且模维度。设和为则且内积为MSIS模小整数解问题 是 SIS小整数解问题的一种变体其中中的元素被替换为环中的多项式。给定模中一组随机选择的元素MSIS 的目标是找到这些多项式向量的一个非零线性组合等于 0且该线性组合的标量系数乘子均为小多项式。定义 5.10模小整数解问题Module Short Integer Solution problem定义如下给定从中均匀随机选取的矩阵寻找一个非零向量使得在中满足且满足以及。这里要求且。注意MSIS 的解不是唯一的。实际上若是 MSIS 的一个解则同样也是一个解。因此一个已知解可以额外导出多达个不同的其他解。参数含义密码学意义多项式环的维度中次方通常取 256控制多项式乘法展开后的维度系数模数Modulus控制所有系数的算术范围矩阵的行数和列数矩阵维度决定方程组大小解的范数上界Bound,约束解向量必须足够“短/小”例 5.11MSIS 实例设因此商环为且范数上界。考虑如下 MSIS 实例给定任务是寻找一个非零向量使得在中满足且范数满足。回顾在中的多项式乘法可以表示为矩阵与向量的乘积。因此该 MSIS 实例的一个等价形式是针对非零向量在模 71 下求解方程其中为如下的整数中的各个子块正是对应于中各个多项式的反循环矩阵Anti-circulant matrices。在模 71 意义下对进行高斯消元可得到如下秩为 8 的简化行梯形矩阵RREF由于的零空间Null space维度为因此方程的解的总数为个。检索并检查所有这 2500 万余个解最终找到16 个所有坐标均落在范围内的非零解。若除去乘以所导出的等价变体这两个基础 MSIS 解分别为以及其中第一个解还原为多项式向量的形式即为定义 5.12模非齐次小整数解问题Module Inhomogeneous Short Integer Solution problem定义如下给定均匀随机选择的矩阵和目标向量寻找一个向量使得在中满足且满足以及。这里要求且。定义 5.13标准型模非齐次小整数解问题normal-form MISIS problem定义如下给定均匀随机选择的矩阵和目标向量寻找一个向量使得满足且。5.3 模容错学习MLWE定义 5.14模容错学习问题定义如下设以及。这里且。给定和求。矩阵的列向量属于模。MLWE 要求在允许微小误差的情况下将模元素表示为的线性组合其中线性组合的系数为多项式。例5.15 MLWE实例设因此且。随机选择定义为给定MLWE 挑战是求解出和使得。回想一下中的多项式乘法可以表示为矩阵与向量的乘积。因此该 MLWE 实例的一个等价形式是在下求解其中未知数噪声且中每个的子块都是中对应多项式所生成的反循环矩阵Anti-circulant matrix而中的子块则是中多项式的向量表示。事实证明该问题存在两个MLWE 解第一个解的多项式形式为。第二个解则是最初用来构造此 MLWE 实例的原始对。定义 5.16判定性模容错学习问题定义如下 设并设。 设以的概率等于以的概率等于。 给定和判定且成功概率显著大于是等于还是等于。定义 5.17短秘密模容错学习问题定义如下 设以及。 这里且。 给定和求解出。定义 5.18短秘密判定性模容错学习问题定义如下 设并设。 设以的概率等于以的概率等于。 给定和判定且成功概率显著大于是等于还是等于。
