格密码学基础（二）：加密

❝

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

作者：Vadim Lyubashevsky

译者：Kurt Pan

格密码学基础（一）：前言

备战后量子：格密码学初学者指南

我们通过构造一个CPA安全(即选择明文攻击安全)的公钥加密方案来开始我们对基于格的密码学的研究。回顾一下,CPA安全的加密方案由三个算法组成:密钥生成、加密和解密。密钥生成算法输出一个公钥/私钥对。加密算法接受公钥和消息作为输入,并产生密文。反过来,解密算法接受密文和私钥,并输出消息。如果对于敌手选择的任意两条消息,这两条消息的加密在计算上不可区分,则该方案被称为CPA安全的。

我们在本节中只讨论CPA安全的加密,因为存在通用的转换(例如Fujisaki-Okamoto [FO99])可以将CPA安全的加密方案转换为CCA安全的方案(其中敌手还可以访问解密预言机)以及针对主动攻击者安全的密钥交换协议(第4.8节)。

我们指出,本章中的方案与它们基于离散对数和因数分解的类似方案不同,最有效的实例化方式会产生解密错误。也就是说,即使密钥生成和加密算法被正确运行,产生的密文也可能以非常小的概率无法解密为被加密的消息。一般来说,具有足够小的解密错误(比如大约)似乎不会损害方案的实际安全性;只需要在转换的证明中考虑这些(例如[HHK17, SXY18])。

❝

如果"正确"处理，解密错误不会导致任何安全问题。另一方面，如果忽略它们的存在，那么CPA安全的方案在CCA安全模型中将变得平凡地不安全。在某些场景中，如全同态加密方案(FHE)，其中方案仅是CPA安全的，需要意识到它们在实践中引起的安全影响（参见[LM21]）。

• https://link.springer.com/chapter/10.1007/978-3-030-77870-5_23

2.1 一些记号

本节中的所有运算都将在环中执行,其中使用通常的整数模的加法和乘法。对于集合,我们写表示从集合中均匀随机选择。对于任何正整数,我们定义集合

这个记号自然地扩展到向量(和矩阵),例如表示一个矩阵,其系数在中。默认情况下,所有的向量都是列向量。也可以通过写来表示向量在中。对于整数,表示最接近的整数,平局时向上取整。

当在后面的章节中使用固定次数的多项式时,我们写表示所有整数系数都从中均匀选择。类似地,对于向量,表示这样的分布:向量中的每个多项式都按选择。有时候,我们会想要从某个分布中采样,而不是从集合中均匀采样。在这种情况下,我们类似地写或,其中是整数或多项式,是整数或多项式的向量。

2.2 一个启发性例子

我们暂时假设对正整数和,以下两个分布在计算上是不可区分的(在与相关的安全参数中):

1. ,其中且
2. ,其中且

也就是说,我们假设不存在有效的算法可以判断给定的样本来自第一个还是第二个分布。这个不可区分性假设显然是错误的,因为人们可以使用高斯消元来求逆(或的一个子矩阵),并检查是否确实存在一个满足。请容忍这个例子,因为这个假设的一个略微修改版本构成了大多数格密码学的基础。我们现在将使用这个假设来构造一个简单的CPA安全的公钥加密方案,它非常类似于基于离散对数的ElGamal加密方案。该方案的私钥和公钥是

要加密消息,加密者选择一个随机向量并输出密文,其中

要解密,只需计算

方案的正确性如下,因为

❝

将此与EIGamal加密方案进行比较！在那里，私钥是  ，公钥是  。密文是  ，解密是  ．  。解密工作的原理完全相同，除了在我们的例子中，我们没有交换律，因此在左侧乘以向量  ，在右侧乘以  。

方案的安全性由我们的假设和混合论证得出。根据假设,公钥与均匀分布不可区分。因此公钥矩阵与均匀分布不可区分,再次使用我们的假设,得到分布基于相同的假设(只是和互换了)也与均匀分布不可区分。因此,分布与均匀分布不可区分,因此该方案是CPA安全的。

注意我们使用了两次不可区分性假设——一次用于论证公钥看起来是随机的,另一次用于论证密文是随机的。我们可以从(其中)中随机选择,而不是从中选择。如果我们设置,那么可以证明公钥实际上在统计上接近于均匀分布(见第2.5.5节)。但是形成密文仍然需要我们使用那个荒谬的不可区分性假设。因此至少使用一次假设是不可避免的。

2.3 LWE问题

我们现在将对上一节的假设做一个"小"调整,这将使其看起来更为有效一点,且仍然允许我们按照相同的大纲构造一个密码系统。我们现在定义带错误学习问题(LWE)[Reg09]的一个简单版本,许多格密码学都基于此。

❝

定义1. 对于正整数和, 问题要求区分以下两个分布:

1. ,其中,,
2. ,其中且

使困难的关键部分是额外的"错误（误差）"向量的存在,这使得高斯消元攻击不适用。问题的确切难度取决于参数和,我们在第3节中对此进行了更详细的讨论。现在,只需要知道随着和的增长,问题变得更困难就足够了。参数对问题的难度没有很大影响,除了在极端情况下（大约为）,在这种情况下可以通过线性化技术[AG11]在大约的时间内构建一个区分器。在将在本章中展示的构造中,永远不需要那么大。由于参数不会特别重要,我们有时在陈述困难假设时会省略它,只写。

对于私钥和错误项使用均匀分布并没有什么特别之处——只是使表述更简单,所以我们选择使用这个分布作为说明的目的。在LWE的原始定义中,误差分布被选择为舍入的高斯分布——也就是说,生成一个具有某个标准差的以0为中心的连续随机高斯分布,并将其舍入到最接近的整数。这个分布对于平均情况到最坏情况的归约证明[Reg09, Pei09]是必要的,这些证明表明LWE至少与某些最坏情况格问题一样困难。这个限制后来被证明不是严格必要的,例如可以使用均匀分布[DM13, MP13]。一些实际实现,特别是Kyber,使用二项分布来生成误差(见第4.7节),因为在实践中有时生成一串比特并将它们相加比生成中的均匀元素更快。

为了考虑可以使用的不同分布,我们可以相对于私钥分布定义LWE问题为:

❝

定义2. 对于正整数和分布, 问题要求区分以下两个分布:

1. ,其中,,
2. ,其中且

为具体起见,我们将主要使用定义1中的LWE,但是一旦考虑了的特定性质(特别是这个分布生成的私钥的期望范数),我们所说的一切同样适用于定义2中的问题。

需要注意的是,在LWE的定义中,我们没有对和的相对大小设置任何条件。因此,某些选择可能导致平凡困难的LWE实例。例如,如果且足够大,那么分布确实可能在统计上接近。然后显然不应该能够仅基于这个假设构建加密方案,因为我们将拥有一个无条件安全的公钥加密方案。为什么事情确实不会成功的原因在我们考虑解密的正确性时会变得清楚。当然也可以设置参数使得LWE不是一个困难问题。例如,如果,那么不难弄清楚是否接近向量的倍数。我们将在第3节中讨论LWE问题的难度。

另一个注意事项是,也可以定义LWE,其中私钥被选择为在中均匀分布(小心然后取足够大,使得LWE问题不会变得平凡困难);这确实是[Reg09]中LWE最初定义的方式。在[ACPS09]中,已经表明从与相同的分布中取会产生一个本质上同样困难的问题。对于应用,取更小通常更高效,所以我们只考虑这个版本的LWE问题。

正如在前一节中已经明确的那样,区分与均匀分布也是LWE问题,只是和互换了——即问题。类似地,通过混合论证,区分

与均匀分布的难度 (区分优势最多增加倍) 等同于或中较容易的那个。

2.3.1 基于LWE的加密方案

在本节的其余部分,我们将展示源于[Reg09]中原始工作的密码系统,并通过各种后续工作中的一系列观察得到改进和推广(参见[ACPS09, Pei09, LPS10, LP11, BCD16])。我们可将本节中的方案视为2.2节中加密方案的修改,但基于的难度,而不是那里明显错误的假设。第一个修改将是消息——它不再是中的任意元素,而是来自集合。密钥生成被修改为:

要加密消息,加密者选择和,并输出

首先讨论一点记号。我们在中工作,但上面的方程有一个看起来奇怪的项。我们的意思是中最接近有理数的元素(例如,如果,则)。所以除法运算不在中——即我们不是乘以或2的逆元。(如果我们想在中进行除法,我们将把它写成乘以逆元)。出于表述目的,我们通常会省略符号,简单地写,因为意思应该是清楚的。

在讨论解密之前,我们先看看安全性论证,看看为什么该方案基于的难度。论证与第2.2节中的相同。公钥与上的均匀分布的不可区分性直接源于假设。将公钥重写为矩阵,我们看到假设再次意味着分布也与均匀分布不可区分。因此,基于,对于任何,与均匀分布不可区分。注意,我们使用了两次假设,参数在论证公钥看起来随机时作为的列数发挥作用,然后在论证密文看起来随机时作为的行数发挥作用。这直观地解释了为什么在试图最小化公钥加密中公钥和密文的组合大小时,将中的行数和列数设置为相等是有意义的。我们在第2.4节中进一步讨论这个话题,并在第2.5.5节中也讨论一些应用和一个稍微修改的密码系统,在这些情况下可能不想让行数等于列数。

要解密,计算。但是,我们不像之前那样干净地得到消息,而是得到了

上述方程中的项相互抵消; 然而我们留下了一些"错误"项的组合。幸运的是,所有这些错误项的系数都由限定,因此向量积和各自由个大小最多为的项组成。因此可以重写为,其中,因此如果参数设置为,解密者可以通过检查前面的值是更接近0还是来从确定。

2.3.2 精确界定总错误

上面计算的值是错误大小的上界。由于和的系数是从以0为中心的范围中随机选择的,误差实际上不太可能那么大。由于抵消,它实际上会更接近。一般来说,我们可以得到误差的界,使得以非常高的概率(比如)误差将低于。这意味着解密错误的概率最多为。这样小的错误在应用中以及在将这个CPA加密方案用作其他构造的组件时(例如CCA安全加密)是可以容忍的。

有渐近的方法来近似计算这样的界,但是当处理具体参数并且不太大时,可以(使用简单的脚本)得到精确值

使用这样的事实:随机变量和的概率分布可以建模为多项式的乘积。假设和是有限集上的随机变量(可能具有不同的分布)。对于所有,令(相应地)是(相应地)等于的概率。现在定义多项式

令

是和的乘积。现在可以在系数和的概率之间建立直接联系。特别地,

这意味着

这直接延续到计算上述所要求的概率,注意到分布为个独立随机变量的和,其中

而只是上的均匀分布随机变量。所以,例如,那么

而所有其他都是0。如果我们然后写

那么所求概率恰好是,其中再次是中与相关的系数。通过设置,我们将获得第2.3.1节中的解密算法正确解密的概率。

2.4 公钥和密文大小的权衡

我们现在知道如何相对于彼此设置参数,以使得第2.3.1节中的加密方案以压倒性概率正确解密。我们还没有讨论应该如何设置参数以使其安全,我们将把这个问题推迟到稍后。但我们仍然可以根据参数计算公钥和密文的大小。

公钥由一个随机矩阵和一个向量组成。由于是完全随机的,因此不需要存储它——如果通过选择256比特种子然后使用某个密码学PRF(例如基于SHA-3函数的SHAKE)将定义为的扩展来创建,那么只需要存储256比特而不是的比特。在加密和解密时需要从扩展,但这样做而不是存储通常是值得权衡的——特别是当该方案用作密钥封装机制时,人们更愿意传输而不是整个。公钥的另一部分依赖于私钥,因此不能以类似的方式压缩,因此总公钥大小为比特。密文可以使用比特表示。具体的安全参数设置将需要取和,因此仅加密一个明文比特就如此庞大是有些低效的。我们现在将给出LWE加密方案的一个推广,它允许在公钥和密文大小之间进行各种权衡。

当前基于LWE的加密方案具有如此大的密文扩展的原因是由比特组成。为了减少密文扩展,我们将给出该方案的一个变体,它在许多消息的加密之间分摊密文部分[PVW08,MR09, BCD+16]。权衡是公钥会更大。假设我们想加密比特,我们将其排列成矩阵。密钥生成过程现在将是

注意公钥大小现在增加到比特。加密算法类似地进行,其中加密者选择和,并输出密文

它由比特组成。为了在公钥和密文大小之间获得权衡,可以改变参数和,同时保持它们的乘积(总比特数)固定。为了获得最小的组合公钥和密文大小,应该设置。这样,加密比特需要大约比特,在实践中将由项主导,因为通常不需要使用公钥加密来加密超过比特就可以切换到对称加密。

这个密码系统的安全性再次直接基于。注意公钥可以重写为,其中和分别是和的第列。那么与均匀分布的不可区分性直接由使用通常的混合论证得出,安全性损失比特。

❝

与混合论证的许多应用一样，在这种情况下不清楚是否存在真正的安全性损失，还是仅仅是证明的副产品。

写,我们再次使用假设(和混合论证)注意到分布与均匀分布不可区分,因此

对于任何固定消息都与均匀分布不可区分。解密的方式与我们在本节中一直为所有其他方案所做的完全相同。给定密文,解密者计算

从上面观察,的第个系数等于

其中和是和的第行,和是和的第列,而和是和的第个位置。由于所有向量都在中,并且它们的所有系数都是从中均匀选择的,我们处于与之前完全相同的情况,因此可以以与以前完全相同的方式设置参数以具有小的解密错误。

❝

注意现在解密错误概率将针对的每个系数（并且概率不是独立的），因此应该使用并集界来界定总解密错误。

2.5 一些变化和优化

前一节中提出的方案更多是一个在实践中会做什么的一般框架。当用具体参数实例化这样的方案时,有几种可能的优化可以考虑,我们将在接下来描述。如果不实际尝试一些可能性并查看获得什么安全性/输出大小,就不容易弄清楚究竟可以使用哪些优化以及如何最优地精确设置参数。

2.5.1 通过删除低阶部分来减少密文大小

密文部分为总密文大小贡献了比特。假设加密者不想将的每个系数的所有比特作为密文的一部分发布,而是想每个系数仅传输比特。这是可能的,但会给解密方程增加进一步的误差。将加法群可视化为圆上的点(参见图1),我们想选择一个大小为的集合,使得中相邻点之间的最大距离(以它们之间的点数测量)尽可能小。注意是我们能希望的最小值,所以我们想尽可能接近这个数字。可以将这样的集合定义为

图1:在圆上的点表示。如果我们定义集合，那么它由四个点组成。因此可以用2比特表示，并且中的每个点距的某个元素的距离都在以内。

如果,则所有相邻点之间的距离都相同。否则,所有距离彼此相差1以内,这是能希望的最好情况。

集合的关键特征是每个都在的某个元素的距离之内。让我们定义为中最接近的元素,为。然后,不是将作为密文的一部分传输,可以传输。注意存在一个使得。

如果密文以这种方式创建,那么解密将产生

与之前解密的唯一区别是项的存在。注意对解密错误的影响有限,因为其他错误项涉及内积,在上式中产生更大的系数。在实践中,通常可以将设置为小常数,如3或4,而不会使解密错误增加太多。这意味着不是为密文贡献比特,而是仅贡献比特。假设是均匀分布的,我们可以获得的精确分布,然后使用与第2.3.2节中完全相同的技术计算解密错误概率。

在某些情况下,对密文部分使用类似的比特缩减过程也可能有意义。然而,在这里,不能在不显著增加解密错误的情况下删除比特,因为添加到的任何误差都会乘以,因此我们会在上式中得到一个额外的项,其中的定义类似于。但是因为是密文大小的主要来源,即使稍微减少中的比特数也可能产生显著差异。然后的技巧是使用试错来平衡解密错误和密文大小。

2.5.2 模切换/压缩/解压缩

我们现在使前一节关于压缩的讨论更加具体。首先定义一个将元素从一个集合映射到另一个集合的操作。当目标集合较小时,这可以看作是舍入或压缩。当目标集合较大时,这可以看作是提升或解压缩。

❝

定义3. 对于元素和某个正整数,我们定义从到的映射为