2.2 格难题及其在密码学中的应用

Ajtai在他具有开创性意义的研究工作 ^[1] 中证明了将基于格的数学问题应用于构建密码方案的可行性。具体而言，Ajtai证明了求解一些平均情况（Average-Case）下NP-Hard的格难题（如最短向量问题）与求解对应最坏情况（Worst-Case）下的假设有相同的困难性。例如，想要求解格中最短向量问题（Shortest Vector Problem，SVP），应当求解在给定任意一组基向量时所对应的SVP，即格中SVP的所有实例都需要被计算求解。因此，根据文献[2]中的证明，可以推测出目前不存在任何一个概率多项式时间算法可以在多项式时间内近似计算格中的一些困难数学问题。这也是基于格的后量子密码（格密码，Lattice-Based Cryptography，LBC）安全性的基础。由文献[3]可知，目前能够最快求解SVP的算法的时间和内存复杂度是2 O （ n ）。

2.2.1 经典格难题

格中常见的三种困难问题（格难题）分别是最短向量问题（Shortest Vector Problem，SVP）、最近向量问题（Closest Vector Problem，CVP）和最短线性无关向量问题（Shortest Independent Vector Problem，SIVP）。接下来将主要根据文献[4]给出的定义对它们一一进行具体介绍。

1.SVP

SVP有三种变体可以相互进行归约：第一种是找到格中最短非零向量，第二种是找到最短非零向量的长度，第三种是确定最短非零向量的长度是否比一个给定的实数短。假设 B 为格 L 的基向量构成的矩阵，定义格 L （ B ）中的最短非零向量 v ∈L （ B ）\{0}，并且其长度为|| v ||= λ ₁ （ L （ B ））。SVP的输出是格中确定且唯一的最短非零向量，且SVP可以使用任意的范数（Norm）进行定义，但通常会使用L2范数即欧几里得范数来计算R ⁿ 中两个点的距离。在 γ -近似SVP（SVP _γ ）中，对于 γ ≥1，目标是找到最短非零向量 v ∈L （ B ）\{0}且|| v ||≤ λ ₁ （ L （ B ））；对于 γ =1这一特殊情况，与SVP完全等价。判定型 γ -近似SVP（G _AP SVP _γ ）被定义为判断不等式 d ＜ λ ₁ （ L （ B ））≤ γ 是否成立，其中 d 是一个正实数。

2.CVP

假设 B 为格 L 的基向量构成的矩阵， t 为连续空间中任意的一个目标点（可能不是 L （ B ）中的格点），CVP被定义为找到一个向量 v ∈L （ B ），使得 v 到目标点 t 的距离（|| v -t ||）最短。在 γ -近似CVP（CVP _γ ）中，对于 γ ≥1，目标是找到向量 v ∈L （ B ）满足|| v -t ||≤ γ· dist（ t ， L （ B ）），其中dist（ t ， L （ B ））=inf{|| v -t ||： v ∈L （ B ）}是指目标点 t 到 L （ B ）的距离。

3.SIVP

假设 B 为格 L 的基向量构成的矩阵， q 为一个素数，SIVP被定义为在格中找到 n 个线性无关的向量{ v = v ₁ ， v ₂ ，…， v _n ： v _i ∈L （ B ），1≤ i ≤ n }，并使得其中最长向量|| v ||=max _i || v _i ||的长度最短。给一个定近似因子 γ ≥1， γ -近似SIVP（SIVP _γ ）被定义为找到 n 个线性无关的向量{ v = v ₁ ， v ₂ …， v _n ： v _i ∈L （ B ）}，并且其中最长向量满足max _i || v _i ||≤ λ _n （ L （ B ））， λ _n 为第 n 个可行的最小值。具体而言，在一个 n 维格中，第 i 个可行的最小值 λ _i 是指包含了格中 i 个线性无关向量的最小球体的半径（以格点为球心）。判断型 γ -近似SIVP（G _AP SIVP _γ ）被定义为判断不等式 d ＜ λ _n （ L （ B ））≤ γ· d 是否成立，其中 d 是一个正实数。

笛卡儿坐标系中二维格SVP和CVP的简化示意图如图2-2所示。 B ₀ =（ b ₀ ， b ₁ ）和 B ₁ =（ b ₂ ， b ₃ ）是格 L 的一组基向量，SVP则是找到最短非零向量 λ ₁ =2 B ₀ -B ₁ 。给定一个目标点 C =（ c ₀ ， c ₁ ）（可能并不在 L 中的格点上），CVP则是找到 L 中与 C 最近的点 D 和其对应的向量 λ ₂ =（ d ₀ ， d ₁ ）。

2.2.2 应用于密码学的格难题

在格密码学中，两类重要的平均情况（Average Case）问题是模线性方程组中的小整数解（Small Integer Solution，SIS）问题和机器学习理论中的误差学习（Learning With Errors，LWE）问题，均与经典格难题（SVP和CVP等）有紧密的联系。

1.SIS问题

随机选取矩阵 A =（ a ₁ ， a ₂ ，…， a _n ） ∈ Z ^m×n ， q 为一个素数，SIS问题被定义为找到向量 z ∈ Z ⁿ ，使得 z ₁ · a ₁ + z ₂ · a ₂ +…+ z _n · a _n =0（mod q ），通常 z _i 的取值范围为 z _i ∈ {-1，0，1}。同样，若随机选取矩阵 ，则可以计算生成对应的 q 阶随机格 ，其中 。这样SIS问题就变为在格 中找到最短向量的问题。根据Ajtai的理论 ^[1] ，如果存在一个多项式时间算法A可以求解SIS问题，那么就一定存在一个高效的算法B可以在多项式时间内解决任意 n 阶格中的SVP或SVIP。

环域上SIS（Ring-SIS）问题：令矩阵 A =（ a ₁ ， a ₂ ，…， a _n ），其中 a _i ∈ Z _q [ x ]/（ x ⁿ +1），对应 q 阶随机格 ，Ring-SIS问题就是在格 中找到最短向量的问题。

2.LWE问题

选取一个矩阵 和秘密向量 ，系数分别在 和 中满足均匀分布，其中 n 和 q 分别为格的维度和模数（通常为素数）， m 为样本数；再选取误差向量 ，系数满足 中的某种公开的误差分布 χ ，并通过计算得到向量 ，满足 b = As + e 。LWE问题的主要计算过程如图2-3所示。搜索型LWE问题就是根据矩阵 A 和向量 b ，计算还原出秘密向量 s 。Regev提出的公钥加密方案就是使用搜索型LWE问题设计的 ^[5] 。从另一个角度而言，搜索型LWE问题可以看作在维度为 m 的 q 阶格 上，找到以 b 为目标向量的最近向量，其中 。判断型LWE问题则是需要去区分LWE系统实际计算得到的向量 b 和系数在 中满足均匀分布的向量 b 。根据Regev的证明，如果存在一个多项式时间算法C可以求解LWE问题，那么就一定存在能求解G _AP SVIP和SIVP的有效量子算法D。LWE问题最大的优势在于，其最坏情况下的困难假设在量子归约和经典归约下都得到了证明。另外，根据文献[6]可知，如果向量 b 与向量 e 是在相同的误差分布中采样得到的，那么LWE问题的困难假设仍然有效成立。

3.环域上LWE（Ring-LWE）问题

定义整数多项式环 R _q =Z _q [ x ]/（ x ⁿ +1），其中 n 是2的幂，模数 q ≡1 mod 2 n 是一个大素数。选取任意多个多项式 a _i ∈R _q （ i ≥1）和一个秘密多项式 s ∈R _q ， a _i 和 s 的系数均在 R _q 上满足均匀分布，再选取对应数量的误差多项式 e _i ∈R _q ，其系数满足 R _q 上某种公开的误差分布 χ ，可以计算得到 i 组多项式 b _i ∈R _q ，满足 b _i = a _i s + e _i 。搜索型Ring-LWE问题就是根据任意组多项式对＜ b _i ， a _i ＞找出秘密多项式 s ；判定型Ring-LWE问题则能以不可忽略的优势区分出任意组独立的多项式 b _i 是由Ring-LWE系统计算得到的，还是由均匀分布采样得到的。可见，Ring-LWE问题和LWE问题在基本形式上是非常相似的，Lyubashevsky和Peikert证明了两项与安全性证明有关的重要结果 ^[7] ：

（1）理想格中最坏情况下的近似SVP到搜索型Ring-LWE问题的量子规约。

（2）如果（1）中的搜索问题是难解的，则Ring-LWE分布实际上是伪随机的。

因此，他们给出了以下结论：在给定的多项式参数下，如果近似求解理想格中最坏情况，搜索型SVP对于多项式时间量子算法是困难的，那么对于任何多项式时间的攻击者而言（即使是量子算法），从Ring-LWE分布中得到的任意组多项式样本都是伪随机的。

4.Module-LWE问题

记 R _q 的阶数（格的维度）为 n ，定义Module（元素为多项式的向量或者矩阵） 的秩（Rank）为 d 。当 d =1、 R _q =Z _q [ x ]/（ x ⁿ +1）时，Module-LWE问题的困难程度基于Ring-LWE问题和Ring-SIS问题；当 d ＞1、 R _q =Z _q 时，则与LWE问题和SIS问题有关。可见，Module-LWE问题是LWE问题和Ring-LWE问题在参数为 R _q =Z _q [ x ]/（ x ⁿ +1）和 d ＞1时的归一化方案 ^[8] ，且 M 中格难题的安全规约取决于 N = n × d （对应Module Lattice的维度）。对于LWE这类问题而言， d =1且 R _q 的维度为 n （即Ring-LWE问题）与 d = i 且 R _q 的维度为 n / i （Module-LWE问题）这两种情况的安全归约是相同的。假设 M 是一个 d × d 大小的随机多项式矩阵（矩阵元素为 n 次多项式），在上述前者的情形中， M 包括 n 个属于Z _q 的系数；对于后者， M 则由 i ² ×（ n / i ）个属于Z _q 的系数组成。具体而言，对 的均匀分布采样得到多项式矩阵 A ，对 某种公开的误差分布 χ ^d 采样得到秘密多项式向量 s 和误差多项式向量 e ，可以计算得到多项式向量 ，满足 b = As + e 。搜索型Module-LWE问题就是根据多项式矩阵 A 和多项式向量 b ，计算还原出秘密多项式向量 s 的。

LWE、Module-LWE和Ring-LWE中随机矩阵（向量）的数据量对比如图2-4所示。在格的维度 n =9时，LWE问题中需要 m × n =81个属于Z _q 的系数；Module-LWE问题需要 d ² ×（ n / d ）=27个属于Z _q 的系数；Ring-LWE问题仅需要 n =9个属于Z _q 的系数。Module-LWE问题是介于LWE问题和其环域上的变体Ring-LWE问题之间的一个中间问题，降低了标准格中的数据计算和数据带宽的需求，提升了理想格中数学难题的安全性。由于LWE、Module-LWE和Ring-LWE问题有相同的基础运算，因此Module-LWE提供了安全性和成本（计算与存储）之间的折中。