格密码学基础（四）：多项式环上的加密
❝原文：https://eprint.iacr.org/2024/1287
作者：Vadim Lyubashevsky
译者：Kurt Pan
第2.3节中基于LWE的加密方案的主要低效之处在于,它需要相当大的密文来加密一个比特——具体地,密文扩展是线性于安全参数。第2.4节中的方案通过使密文扩展仅为安全参数的平方根,但以公钥按相同因子膨胀为代价,在一定程度上缓解了这种低效率。在本节中,我们将展示如何通过考虑不是在上而是在更高次多项式环上的LWE问题，来消除这种平方根膨胀。
4.1 多项式环
多项式环,带有不定元,由形如的元素组成,其中,具有通常的多项式加法和乘法运算。为方便起见,我们通常会省略不定元,简单地写而不是。的次数,记为,是使的最大。多项式是首一的,如果;如果不能写成,其中且,则它是不可约的。
我们在第2节中看到的加密方案涉及环上的运算。这个环的推广,也是我们在本章剩余部分将要使用的,是环,其中是次数为的首一多项式。
❝在格理论文献中，这个环通常被写作 。
的元素是多项式,其中。中两个元素的和简单地涉及对中相应系数求和。即,
因此中多项式的加法可以看作上向量的加法。因此,多项式乘以中的元素也具有与向量乘以常数相同的解释。
中两个多项式的乘法涉及执行正常的多项式乘法,然后模约简。模约简意味着(就像对整数一样),执行除以后的余数。特别地,任何多项式可以唯一地写成,其中且。因此。
要看到任何确实可以以这种方式分解,我们使用归纳法。如果,那么(且),我们就完成了。现在假设所有次数至多为的可以写成,并令的次数为。那么的次数至多为,根据归纳假设可以写成对于某些和。因此可以写。
要证明的上述分解是唯一的,假设存在矛盾的不同使得。这意味着。由于,必须有。那么我们知道如果,则。因此,有矛盾。
注意,上述和存在性的证明产生了一个计算的非常简单的算法——将乘以适当的单项式并从中减去它以创建次数较小的多项式,并继续直到得到次数小于的多项式。例如,如果我们想要将模约简,我们写
作为一个简单的观察,注意通常的环是环的一个特殊实例,其中多项式被定义为(事实上,对于任何也可以)。
4.1.1 多项式与线性代数
一个有用的观察是,模的多项式乘法可以写成中的矩阵与中的向量的乘法。观察到乘积可以写成:
由于每个是次数小于的多项式,它可以被视为中的向量。因此乘法可以看作这个向量的线性组合(权重为),因此可以表示为矩阵-向量乘法。例如,乘积
可以写成
当将多项式视为向量和矩阵时,使用记号和会很方便,其中
我们没有将作为和的记号的一部分,但应该总是从上下文中显而易见。
使用这个记号,可以重写为
我们还可以将上述记号扩展到多项式的矩阵。对于向量和矩阵,我们定义和为
从上述定义,可以验证对于任何和,我们有
4.1.2 系数增长
当和是整数时,它们乘积的大小很容易计算——就是的绝对值。对于,界定乘积的大小会更复杂一些,并且严重依赖于多项式。因为乘法可以写成,乘积的最大系数的一个简单界是,其中是最大系数的绝对值。通过计算的最大奇异值,可以获得更好的界(在范数中)。但无论哪种方式,对中系数大小的影响对于界定乘积都是至关重要的。
就保持小而言,我们能希望的最好情况是。只有两个多项式能满足这一点,即。对于形如和的多项式,我们有。这里是对于多项式,针对几个次数为4的的一些矩阵的例子。
也有一些多项式使得。不出所料,如果本身有大系数,那么也会如此。但也有一些具有小系数的产生系数比指数级大的——一个这样的例子是。导致矩阵的系数远大于的多项式对于密码学目的是无用的。一般来说,我们更喜欢使用导致和之间的比率为1或2的多项式。
4.2 广义LWE和SIS问题
我们现在提出定义在一般环上而不仅仅是在定义1中的上的LWE问题的一个版本。类似地,我们将在环上工作,它类似于环,只是多项式系数在中而不是在中。环在格文献中通常写作。
❝定义5. 对于正整数和环, 问题要求区分以下两个分布:
,其中 ,其中且
与之前一样,参数对问题的难度没有任何已知的影响,除非它很大,因此我们通常只写。前述广义LWE问题的定义和以下密码系统遵循的研究线(将其安全性与某些格问题的最坏情况实例联系起来)是[LPR10, BV11, LPR13b, LS15]这些工作。
我们可以类似地推广[PR06, LM06, LS15]定义4中的SIS问题如下:
❝定义6. 对于正整数和,以及环, 问题要求对于随机选择的矩阵,找到向量和(不都是)使得。
在文献中,广义LWE/广义SIS问题通常被称为环LWE/环SIS或模LWE/模SIS。在NIST为格标准选择的名称ML-KEM和ML-DSA中,"ML"部分就代表"模格"(Module Lattice)。
4.3 广义LWE加密
加密方案的描述与第2.3.1节中的几乎相同,只是环被替换为。该方案的主要优势是消息在中,允许我们将比特打包进去。
要加密系数在中的消息,加密者采样和,并输出
基于的安全性论证与第2.3.1节中基于的证明相同。
要解密,计算
要计算解密错误,我们可以将上述方程(不包括)重写为
然后应用第2.3.2节中的技术来计算个系数中没有一个的幅度大于的概率。当时,对于个系数中的每一个,计算这个概率与我们在整数上工作时相同,因为和的每一行中的系数都是独立的。然后应用并集界来界定所有个解密错误都很小的概率。对于其他多项式上的环,如果可以将矩阵-向量乘法重写为独立随机变量的和,仍然可以应用第2.3.2节中的技术。
4.3.1 优化和效率
广义LWE方案的主要优势是不需要像第2.4节那样增加公钥的大小就能加密更大的消息。当的次数为时,环自然支持加密比特。因此只要我们设置,这是使用公钥加密会加密的AES(或任何对称密码)密钥的长度,就能够使用最优小的公钥。类似地,不需要像第2.5.4节那样每个系数打包多于一个消息比特。第2.5.1节中的优化仍然非常有用,并且以与之前完全相同的方式应用。带舍入的学习问题和密码系统(第2.5.3节),以及非交互式密钥交换(第2.6节),也类似地为环定义。
4.3.2 安全性与整数格的联系
中多项式运算与上线性代数之间的联系允许我们在第3.1节中看到的格与上一节中定义中涉及的多项式方程的(短)解之间建立有用的联系。基于LWE的加密方案的难度依赖于区分与均匀随机的难度,对于随机和系数很小的整数向量。我们在第3.3节中看到,在格
中找到短向量允许我们构建这样的区分器,我们将LWE加密方案的具体安全性基于后一个问题的难度。
本节中更高效加密方案的安全性类似地基于区分与均匀随机的难度,对于随机和系数很小的多项式向量。这等价于区分与均匀随机。由于这个区分问题现在是在上,我们可以将其转换为关于在整数格中找到短向量的问题——即如上所述在格中找到系数很短的向量。
因为是一个整数矩阵,格
的维度是。如果的代数结构没有表现出任何弱点(见下面的第4.5节),那么在这个格中找到短向量的难度与格中的相同,其中和。因此,对于问题,重要的值是——中的次数与的列数的乘积。类似地,对于问题,重要的值是——的次数与中行数的乘积。
4.4 NTRU
NTRU密码系统[HPS98]是第一个真正高效的基于格的加密方案,也是第一个提议使用多项式环——特别是——在基于格的密码学中的方案。该方案最初被提出作为陷门单向函数,可以看作是OW-CPA密码系统。
❝一个加密方案是 OW-CPA 安全的，如果一个拥有公钥的攻击者无法从随机选择的消息的密文中恢复出该消息。
还有一个简单的修改允许我们构造CPA安全的加密方案[SS11]。然而,在大多数使用情况下,陷门单向函数就足够了,因为存在从这种原语到CCA安全加密方案的黑盒转换(参见[Den02])。
https://link.springer.com/chapter/10.1007/978-3-540-40974-8_12
4.4.1 NTRU陷门单向函数
在前面的章节中,我们使用了广义LWE问题的判定版本,但定义其搜索版本也很自然。这个问题可以陈述为在给定时找到,其中和。注意如果在中可逆,那么找到立即也意味着找到。
NTRU问题与上述非常相似,除了多项式不是从中随机选择,而是整数与多项式和的乘积,其中(条件是可逆)并且与互质(例如是一个流行的选择)。NTRU背后的难度依赖于这样的假设:每当不是均匀随机而是乘积时,搜索问题(其中)仍然是困难的。
NTRU问题正式定义如下:
❝定义7. 令。给定,其中,对于且在和中可逆,找到。
基于上述问题的假定难度,我们可以如下构造陷门单向函数族:要从该族生成随机元素,选择秘密可逆多项式,其中在和中可逆,并将公钥设置为
私钥是。
将映射到的单向函数计算
观察到为了从恢复和,足以模恢复这些,因为在中的元素与模的剩余之间存在一一对应。要使用私钥模恢复,首先计算
等式在环上简单地从和的定义得出。因为和的系数相对于足够小,等式不仅在中成立,而且在上也成立。因此当两边都模约简时它也成立,所以只剩下。如果上式成立,那么也有
乘以在中的逆。一旦有,这与相同,我们也可以计算
我要敦促第一次看到NTRU的读者,再看一次并欣赏它的微妙之处。特别是,尽管使用两个互质模数进行模运算上式仍成立,而这种做法通常很少能导出任何有意义的结果！
4.4.2 安全性
如果我们不假设多项式有任何特殊结构,那么恢复与对广义LWE实例的公钥的攻击相同,其中我们试图在格
中找到短向量。也可以尝试通过寻找格
中的短向量从恢复私钥(或与其相关的某些其他短多项式)。
这两个格看起来非常相似,唯一相关的区别是第一个存在一个额外的向量。因此有些令人惊讶的是,在某些情况下,当显著大于时(但不是大到明显在通用格约简算法工作的空间中),在第二个格中找到短向量比在第一个中显著容易[ABD16, CJL16, KF17]。虽然这些攻击不会转化为对NTRU参数的攻击,但它们确实阻止NTRU假设用于需要大模数和小噪声的高级原语(例如FHE)。由于这个原因,在这些情况下使用基于广义LWE的方案(其安全性本质上依赖于第一个格。
4.5 利用代数结构...进行攻击
假设我们在环上工作,其中。因为是的因子,存在从到的环同态,它将元素映射到。因为环恰好是具有通常模加法和乘法的环,实际上有从到的环同态。这个同态特别特殊的地方在于,如果的系数很小,那么同态下的像也很小(即只能大倍)。这意味着对问题的以下简单攻击,其中给定并被要求判断是否存在系数在中的满足(这个攻击首次针对问题在[PR06, LM06]中给出,我们在这里将其改编为对的攻击):
令是在同态下的像。如果确实存在和满足,那么存在满足。因为和相当小,我们就剩下求解一个小维LWE问题,可以如第3.3节那样完成。
使上述对的攻击成为可能的最关键元素是存在到较小次数环的同态,该同态不会大幅增加系数大小。如果有一个因子,例如,那么上述攻击将不起作用,因为同态会将元素映射到,因此将在指数依赖于的范围内。有趣的是,表明求解和意味着在理想/模格中找到短向量的最坏情况到平均情况归约[PR06, LM06, LPR13a, LS15, PRS17]只要求在环而不是上不可约(或至少在的情况下有大次数不可约因子)。正如我们将在下一节中看到的,就实现效率而言,在环上工作实际上是相当有利的,其中多项式在中有许多低次因子。
4.6 利用代数结构...提高效率(数论变换)
加密方案中计算量最大的代数运算是中多项式的乘法。两个次数为的多项式的基本"小学"多项式乘法需要次运算。有更好的方法,如Karatsuba和Toom-Cook,大约需要时间。在中执行多项式乘法的最高效方法只需要次对的运算,这是通过NTT(数论变换)实现的,它是在域而不是在复数上执行的FFT的特例。使用支持NTT的特殊环来加速基于格的原语的想法首次用于SWIFFT抗碰撞哈希函数[LMPR08],现在广泛用于其他原语(如加密方案(例如[ADPS16, BDK+18])和数字签名(例如[DKL+18, PFH+17]))的实际实例化中。
我们现在将解释多项式环上的NTT算法,其中且是2的幂。假设在中有平方根,因此我们可以写。那么计算可以通过中国剩余定理完成。即,我们可以首先计算
然后逐分量相乘得到
然后可以使用上述来重构。
在引理5中,我们表明分解上两式需要次加法和次对的乘法,从上式重构需要相同数量的运算。因此计算乘积需要次加法,次乘法,以及两次在环上的乘法。由于后者环上的乘法仍然是时间,目前还不清楚我们取得了进展——但如果多项式可以进一步分解为(类似地),那么我们可以递归地计算!
特别是,我们现在可以使用递推关系计算整个算法的运行时间,其中是在中乘两个多项式的时间,和分别是计算中一次整数加法和乘法所需的时间。从上述讨论,这个递推关系是
如果是2的幂并且和在中有次根,那么我们可以继续递归直到分解为线性因子,因此上述递推对是良定义的。
❝为了看为什么这样，设 使得 和 。我们将通过归纳法证明这个声明。在递归的每一层，不变量是所有因子都是 的形式，其中 是2的幂且 。这个不变量由基础情况满足：。我们现在进行到归纳步骤：因为 ，如果 是一个整数，那么 也是，因此形式为 的项分解为 ，而形式为 的项分解为 。将 代入，前面的两个因子是 的形式。因为 和 ，我们有 ，下一层的不变量得到满足。当 时递归停止。
因此这个递推的解是
其中。所以在环中计算乘积可能只需要次整数加法和次对的乘法。
当时,上述给出了环中的高效乘法算法。为了能够将多项式一直分解到线性项,需要有次根,或者换句话说,乘法群有次单位根。
❝回顾一下，一个元素 是 次本原单位根，如果 且对所有 有 。如果 是 次本原单位根，那么必然有 。
每当模数是满足的素数时,这样的单位根就存在(见引理7)。应该注意的是,即使不满足后者,NTT算法仍然可以执行;只是我们将无法一直递归到线性多项式。例如,如果,那么多项式可以分解为二次项的乘积。这意味着在底层,逐分量乘法将在环中进行,对于某些。虽然这个基础乘法需要超过对的1次乘法,但仍然可以用小常数次乘法和加法(即对的5次乘法和2次加法)执行。并且因为我们少做一层分解,总运算次数实际上相同。
❝在我们不能一直往下到线性因子的情况下，可以容易地求解递推式。
也不一定需要多项式是才能从NTT中受益。还有其他(分圆)多项式具有与非常相似的分解树。例如,对于某些和素数,多项式模分解为,然后可以应用NTT递归算法在环上相乘——主要区别是由于不是2的幂,我们将无法将分解为1次多项式,而是分解为3次多项式。但总体上,在这样的环上(参见[LS19])几乎可以像在上一样高效地执行乘法。也可以通过在上相乘然后模约简,对任意的环利用NTT乘法。上的乘法可以通过在上乘法来执行,其中次数被选择得足够高,使得模的约简永远不会发生(即设置为大于的整数)——这个算法通常仍然是在多项式环上乘两个元素的最高效方法(参见[CHK+21])。
我们现在证明上面提到的引理,它表明计算所需的运算次数,以及从CRT表示重构环中元素,需要次加法和次乘法。
❝引理5. 假设多项式可以写成
❝并定义函数,
❝如果和是预先计算的,那么和各自可以使用次对的加法/减法和次乘法来计算。
证明. 如果我们写
那么可以看到对于所有,
因此计算需要次乘以和次加法(或减法)来计算。对于反向,可以通过从上面观察到对于所有,
来重构。上述两个运算类似地需要次加法(或减法)和次乘法。□
在上述引理的陈述中需要注意的一点是,我们不是计算逆,而是。我们这样做的原因是它节省了乘法。在递归算法中,引理中的过程运行若干次(比如)迭代,逆的加倍将不断累积,使得最终结果是正确答案的倍。然后我们只在最后一层乘以。所以不是在每个层执行额外的乘以,我们只在最后一层执行。
4.6.1 环的有用代数性质
在上一节中,我们看到了在环上乘法的非常高效的算法,我们还看到为了安全性,多项式在上不可约是很好的。在本节中,我们陈述并证明环的一些有用性质。第一个引理指出,多项式在整数上不可约当且仅当是2的幂。
❝引理6. 多项式在上不可约当且仅当是2的幂。
证明. 令是第个分圆多项式,并回忆对于任何
因此,因此
如果对于某个非负整数,那么从上面得出,因此是不可约的(因为所有分圆多项式都是不可约的)。另一方面,如果,其中是奇数,那么和都整除,但都不整除。所以和是的不同因子。□
下一个引理对于选择模数使得多项式分解为低次多项式很有用。
❝引理7. 令,其中且是素数。那么存在个不同的满足使得
证明. 因为素数使得,我们有,所以存在阶为的元素,因此。此外,对于所有奇数,所有模都是不同的并且满足。因此个元素是的根,因此我们有。通过在前面的等式中用代替,引理得证。□
最后一个引理在本教程中没有使用,但我们在这里陈述它以保证完整性,因为对于一些高级应用记住它很有用。它指出对于所有素数,多项式永远不是不可约的;所以(不幸地)永远不是域。如果想要一个"几乎是域"的环,可以设置环参数(见[LS18])使得多项式分解为形如的两个不可约多项式。
❝引理8. 令是奇素数,是4的倍数。那么多项式在上至少分解为2个多项式。
证明. 如果,那么模的因子如引理7中设置时所示。
如果,那么对于所有,恰好或之一是模的二次剩余。
❝为了看到这一点，假设它们都是二次非剩余或二次剩余，因此它们的乘积必须是二次剩余，所以存在一个 使得 。存在一个整数 使得 ，我们将前面的同余式的两边都提升到 次幂，得到 。因为 ，费马小定理蕴含 和 都同余于 1，因此我们得到矛盾 。
如果2是模的二次剩余,则设,如果是,则设。最后令使得。那么
如所声称。□
4.7 加密方案CRYSTALS-Kyber(ML-KEM)
在本节中,我们将把所有内容放在一起,给出NIST标准化的CRYSTALS-Kyber(被NIST命名为ML-KEM)方案的完整描述,该方案基于广义LWE问题的难度。该方案在环上工作,私钥的分布是从二项分布中抽取的,而不是我们迄今为止一直使用的均匀分布。使用二项分布(我们将其表示为正整数的)的主要原因仅仅是因为它更容易采样。
❝定义8. 对于整数,从二项分布生成的元素如下:生成随机并输出。这个定义自然地扩展到多项式,其中对于,我们写表示的每个整数系数都根据独立采样。类似地,对于维度为的向量(多项式的),我们写表示每个元素都根据采样。
CRYSTALS-Kyber CCA安全KEM的核心是CPA安全加密方案。从后者到CCA安全KEM的转换是通用的,我们在第4.8节中简要描述它。然而,在本节的其余部分,我们只关注CPA安全加密。
CPA安全加密方案Kyber呈现在图3中。Kyber的安全参数是,其中是在安全级别之间变化的主要参数。参数和指定密文的不同部分被舍入到的集合(参见图1))的(对数)大小。这些值决定了密文大小和解密错误。
公共参数:
图3: CRYSTALS-Kyber CPA安全加密方案
密钥生成过程与之前完全相同,除了私钥向量是根据二项分布而不是均匀分布生成的。要加密二进制多项式,加密过程从二项分布生成向量和环元素(可能使用不同的值——我们稍后会解释其直觉),并如之前计算未压缩的密文。然后我们对密文应用压缩函数(见第2.5.1节和第2.5.2节)以减少密文大小。解密函数使用压缩函数，恢复0/1系数。
正确性和解密错误
要计算解密错误,我们查看项
对于,其系数对应于引理1中的。将替换为,我们得到
如果
的所有系数在幅度上小于,则上述结果将是。计算这个概率如第2.3.2节中那样完成。我们已经在第4.3节中讨论了如何将这些技术适应环设置。唯一区别是还包括由压缩和解压缩操作产生的项和。通过假设被压缩的项是均匀随机的,可以计算和的每个系数的精确概率分布——即对于随机,的概率分布(相应地用代替)。一旦我们计算出一个系数的精确错误概率,我们可以应用并集界(即乘以256)来获得错误概率的上界。这些值在表3中给出。
表3: Kyber三个实例化的参数。三个方案的安全性在实践中应该不比AES-128、AES-192和AES-256分别差。
安全性
Kyber的安全性基于问题的难度。安全性证明的工作方式与第2.3.1节和第4.3节中方案的证明完全相同。需要注意的一点是,在Kyber-512中,的值设置为3,而。这意味着区分公钥与均匀随机的基于的难度,而区分密文与均匀的难度基于"混合"分布,其中的系数从选择,而和的系数从选择。这至少与问题一样困难,但注意我们不是输出,而是。这意味着像带舍入的学习问题(见第2.5.3节)那样添加了一些额外的误差。来自的系数和通过从3329压缩到大小为的集合创建的误差的总组合误差实际上比稍大。所以虽然技术上区分密文与均匀字符串的难度基于的难度,但在实践中,我们获得了一些额外的启发式安全性比特,问题应该与一样困难。我们为从而不是采样的系数从而实现这种额外启发式安全性所付出的代价是解密错误增长。
计算效率
有几个技巧可以用来显著优化图3中方案的效率。首先,不需要存储公钥部分,因为它是均匀随机生成的。因此可以简单地存储256比特种子并将创建为,其中是某个密码哈希函数(例如SHAKE),它可以将种子扩展为任意长度的看起来随机的字符串。因此公钥将仅由组成。
如第4.6节所讨论,每当的形式(引理7)允许分解为低次多项式时,NTT算法允许在形如的环中进行非常高效的乘法。Kyber中的模数(即3329)模256同余于1,因此多项式分解为形如的2次多项式的乘积。
❝选择素数3329作为Kyber的原因是，不存在类似大小的素数能将多项式 分解为线性因子（即不存在素数同余于1模512）。虽然如第4.6节所述，在一个不能完全分裂的环中实现NTT乘法在实现上有些复杂，但在 分裂为线性因子或二次项之间在计算上基本没有差别。
作为记号,对于多项式,让我们用表示其NTT表示:
将转换为(以及转换为)需要次运算。虽然这已经相当快,但NTT表示的存在允许我们进一步优化。
注意组成矩阵的多项式是随机采样的。为了有效地进行乘法,我们需要首先将多项式转换为它们的NTT表示。简单的观察是,因为多项式与其NTT表示之间存在一一对应,我们可以直接以其NTT表示随机采样!此外,公钥可以以其NTT表示存储,因此在乘法后不需要进行逆NTT。而且由于的NTT表示在加密算法中计算时无论如何都需要,这是双赢。
另一方面,注意我们不能直接以其NTT表示采样和,因为它们的分布不是均匀随机的。当元素处于其NTT表示时,我们也不能执行压缩操作。因此一些NTT计算将是必要的。尽管如此,因为矩阵由个多项式组成,通过直接以NTT形式采样它,我们避免了执行次NTT计算——这是非常可观的节省。
4.8 从CPA加密到CCA-KEM
密钥封装机制(KEM)允许两方交换随机消息(共享密钥)。它由三个算法组成——KEM-KeyGen、KEM-Encaps和KEM-Decaps。密钥生成算法输出私钥和公钥。封装算法接受公钥作为输入并输出共享密钥和密文。解封装算法反过来接受密文和私钥作为输入并产生与输出相同的共享密钥。CPA安全的KEM是这样的:当给定公钥和密文时,对手无法区分共享密钥与均匀分布。这样的KEM可以从任何CPA安全的公钥加密方案构造,只需加密随机消息并将其设置为共享密钥。
❝为了实现稍微更"高级"的安全概念（这里我们不讨论），人们不仅仅输出消息作为共享密钥，而是用公钥对其进行哈希，如图4所示。在大多数密码协议中，将所有公共参数作为密码哈希函数的输入也是良好的密码学实践。
公共参数: 来自图3的CPA加密方案的公共参数
图4: 使用Fujisaki-Okamoto变换构造的CCA安全密钥封装方案。函数和被建模为随机预言机。CPA-KeyGen、CPA-Encrypt和CPA-Decrypt算法如图3所示(尽管构造相当通用),添加到CPA-Encrypt输入的值表示过程中使用的随机硬币,用于生成。
要被认为是CCA安全的,即使当对手可以访问解封装预言机(它可以在除给定密文之外的任何东西上使用)时,共享密钥与随机的不可区分性也应该被保持。
从CPA安全的公钥加密方案到CCA安全KEM的转换遵循Fujisaki-Okamoto(FO)变换。Fujisaki-Okamoto变换背后的直觉是使解封装预言机对对手"无用",使得它产生非输出的唯一时间是当它被给定对手已经知道消息的密文时。实现后者的方法是使构造密文中使用的随机性依赖于消息,并让解封装算法首先解密密文以获得消息,然后重新加密它,如果密文不匹配则输出。这个通用转换在图4中呈现。
❝这使得加密方案是确定性的，但这不会造成问题，因为我们总是在加密随机消息。
专门针对格加密的一些小修改
由于格加密的特殊性,标准化的ML-KEM(即Kyber)中对图4进行了一些修改。与离散对数方案不同,基于格的方案中的公钥相当大( KB),使用NTT的代数运算与经典密码学中慢得多的幂运算或椭圆曲线乘法运算相比非常快。因此在封装和解封装函数中对公钥进行哈希实际上是一个计算上非常明显的操作,当使用AVX-2指令实现方案时,可能占运行时间的30%到50%之间。因为在许多实际场景中,解封装算法比密钥生成运行得更频繁(例如,一方的公钥可能是固定的),我们可以在KEM-KeyGen算法中预先哈希公钥为并存储它,然后在KEM-Encaps算法中使用作为的输入(这里没有节省),并在KEM-Decaps算法中使用而不是。在后一个算法中,节省意味着只哈希32字节而不是 KB。
Kyber KEM中的另一个变化是永远不输出,而是在密文不匹配的情况下,输出一个随机密钥,该密钥是输入密文和密钥生成期间创建的某个随机秘密值的哈希。这样做的理由有些技术性,并且实际上并不清楚这在实践中是否增加了任何安全性。
❝Kurt Pan: 如您喜歡，請打賞支持我！👇
讓我們一起向付費圍牆花園和廣告推薦注意力經濟宣戰，讓賽博空間重新清朗！