格密码学基础（三）：LWE和其他格问题的难度

❝

原文：https://eprint.iacr.org/2024/1287

作者：Vadim Lyubashevsky

译者：Kurt Pan

我们现在将给出LWE问题的几何视角。虽然这种联系对于理解大多数密码构造如何工作并不是真正必要的,但它对于理解它们的安全性至关重要。

3.1 格

LWE问题的几何解释的核心是被称为格的对象。一个维整数格简单地说是群的一个子群。这样的群可以通过称为基的生成集来描述。特别地,由(满秩)基定义的格是

在本章中,我们将只限制自己研究称为元整数格的特殊类型的格,因为这些是在密码构造中使用的格。它们还具有很好的理论性质,即渐近地,在这些格的随机实例上求解某个问题与在任何格上求解某个问题一样困难。这是著名的最坏情况到平均情况归约研究路线[Ajt96, Reg09],它构成了基础并推动了基于格的密码学的发展。

对于矩阵,由定义的元格是

不难看出,在通常的向量加法运算下,上述集合是一个群。对于熟悉线性码的读者来说,上述两个格的定义类似于使用生成矩阵或奇偶校验矩阵来描述一个码。更具体地说,我们将处理的格是

其中是单位矩阵。这不是太大的限制,因为如果包含列在上线性独立(不失一般性,假设,其中是可逆的),那么我们可以写并且,其中后者就是上式形式。对于上式形式的格,在"生成"矩阵表示和"奇偶校验"矩阵表示之间切换也很容易。容易验证

特别地,如果,那么存在某个向量使得。则

上述表明中的所有向量也在中,反之亦然。

3.1.1 商群和行列式

满秩格的行列式,记为,是在空间中密度的倒数。也就是说,如果我们定义集合,那么

如果对于满秩矩阵,那么,其中右边是的通常的矩阵行列式。例如,维格的行列式是。满秩维格的行列式的另一个等价定义是商群的大小。

格的奇偶校验表示,,便于检查中的两个向量是否在的同一陪集中。特别地,和在同一陪集中当且仅当。有了这个观察,很容易看出当时,恰好有个陪集;这与我们之前观察到的格的行列式是一致。

3.1.2 到格的距离

对于维格和任何向量(不一定在中),从到格的范数距离定义为

观察到对于属于的同一陪集的任意两个元素和,,因此距离对于陪集来说也是良定义的概念。因此,如果并且定义了陪集,那么

为清晰起见,写而不是来表示是陪集在下的像,而不是某个陪集代表。

我们现在将证明一些关于随机格中短向量的(不)存在性的命题。为简单起见,我们只在是素数的情况下证明它们,但更仔细地,可以对所有证明类似的命题。引理2和3表明随机陪集远离随机元格,并且元格没有非常短的向量。引理4证明了部分逆命题,给出了任何元格中最短向量长度的下界。

❝

引理2. 对于任何素数和任何,

证明. 由于非零,的某个系数也必须非零。不失一般性,假设它是第一个。那么对于固定的,我们有

其中存在是因为我们假设。由于中有个可能的向量,引理中的命题由并集界得出。

❝

推论1.

其中。

格密码学中的一些"流行"设置是素数和是2的幂。在这两种情况下,概率界中的第一项在中都是可忽略的(分别为和)。因此,每当时,随机陪集将距离超过距离。

下一个引理指出,在选择时,格具有短非零向量的概率很小。我们只对素数证明这个引理,因为对于其他选择会有些混乱。引理的证明与引理2几乎相同。

❝

引理3. 对于任何素数,

下一个引理是上面那个的逆命题;它给出了现有非零向量长度的下界。

❝

引理4. 对于任何和任何,

证明. 证明使用鸽笼原理。中系数在0和之间的向量有超过个。由于的值只有种可能性,必须存在两个不同的,其系数在上述范围内,使得。因此并且。

根据引理3和4,我们看到在中存在系数在中的向量与以高概率不存在这样的向量之间的边界相当明确。引理4指出当时,这样的向量总是存在。另一方面,如果我们设置,那么中存在系数在中的向量的概率小于。

3.2 在随机格中寻找短向量(SIS问题)

关于格可以提出的一个基本计算问题是在其中找到一个"短"(非零)向量。当专门针对我们上面处理的格时,问题简单地变成找到一个非零使得。引理4指出当时,这样的向量肯定存在,但证明没有给我们任何找到它的方法。到目前为止,所有已知的(量子)算法用于找到这样的向量(对于均匀随机的)都需要时间(参见[AKS01, ADRS15, AS18])。

随着增加,问题确实变得更容易。显然,如果,那么通过将与相乘的的系数设置为目标系数,问题就被平凡地解决了。对于较小的值,人们会运行一个算法,该算法找到格中比最小向量大某个因子的向量。所有现代高效(即多项式时间)算法用于找到这样的短向量都是著名的LLL算法[LLL82]的后代,该算法保证找到长度最多为格中最短向量长度倍的向量。然后引理4意味着对于随机,LLL算法将在中找到向量。

虽然LLL算法保证找到的向量的长度比最短向量的长度大指数倍(在格的维度中),但在实践中,这个指数不太大。在运行足够高维度(至少100)的格实验之前,甚至不清楚LLL对随机格的真实近似因子是指数的还是线性的。事实证明,近似因子确实在维度上是指数的,但指数的底数相当小。

[GN08, MR09]中的实验表明,可以在形如上文所述的随机格(维度为)中找到长度约为

的非平凡向量(即那些不是的倍数的向量),其中取决于算法需要多少时间。为特定的值推导LLL类型算法运行时间的良好近似相当复杂(参见[ACD+18, ADH+19]),超出了本教程的范围。作为一个非常粗略的经验法则,被认为在可及范围内,而可能永远不会在足够高维度的格(例如超过500)上实现。

注意,如果格的维度非常大,可以从中任意删除许多列并在得到的格上运行LLL。特别地,最优的格维度是

(见[MR09, 第3章]),这导致找到的非平凡向量的范数为

❝

[MR09]仅声称当找到的向量的-范数小于时此界是有效的，并且对于超过时不做任何声明。然而，从渐近意义上看，当例如试图找到-范数有界且远小于的短向量时，此界似乎仍然相当准确。那么仍然可以使用该向量对应的-范数的此界。存在一些已知的小优化（例如见[DKL+18]），但作为粗略指南，此界仍然相当好。

在随机格中找到短向量的问题被称为SIS(短整数解)问题。已知求解这个问题的随机实例至少与求解所有格中的某些相关问题一样困难[Ajt96, MR07]。我们将写为当给定如前文所述随机格时找到系数在中的向量的问题。

❝

定义4. 对于正整数和,问题要求对于随机选择的矩阵,找到向量和使得。

注意,根据引理3,当时,问题是平凡困难的,而根据上文随着增长问题变得更容易。还要注意到,一旦大于,它对问题的难度就没有影响,因为它不出现在找到的向量大小的公式中。这与问题的情况非常相似,其中参数不太重要。正如在那种情况下,我们只写。

在定义4中定义的问题使用范数,而上文找到向量的难度是在范数中。在范数中定义问题的原因是因为在Dilithium签名方案中,该方案被设计为避免复杂的操作,困难问题自然地在范数中。可以得出关于范数中问题难度的某些结论的一种方法是注意到找到范数为的向量至少需要找到范数乘以维度的平方根的格向量。

❝

Dilithium签名方案中的所有采样都是从均匀分布进行的。如果从计算上稍微复杂一些的分布进行采样，可以获得更高效的签名方案版本（例如[Lyu12, DFPS22]）。