格密码学基础（四）：多项式环上的加密

The variable $h$ represents the height, and $x$ is the width. When $h > 0$, the formula is $f(m) = h$.

第2.3节中基于LWE的加密方案的主要低效之处在于,它需要相当大的密文来加密一个比特——具体地,密文扩展是线性于安全参数。第2.4节中的方案通过使密文扩展仅为安全参数的平方根,但以公钥按相同因子膨胀为代价,在一定程度上缓解了这种低效率。在本节中,我们将展示如何通过考虑不是在$\mathbb{Z}_q$上而是在更高次多项式环上的LWE问题，来消除这种平方根膨胀。

4.1 多项式环

多项式环$(\mathbb{Z}[X], +, \times)$,带有不定元$X$,由形如$a(X) = \sum_{i=0}^{\infty} a_i X^i$的元素组成,其中$a_i \in \mathbb{Z}$,具有通常的多项式加法和乘法运算。为方便起见,我们通常会省略不定元$X$,简单地写$a$而不是$a(X)$。$a$的次数,记为$\deg(a)$,是使$a_i \neq 0$的最大$i$。多项式$a$是 首一 的,如果$a_{\deg(a)} = 1$;如果不能写成$a = bc$,其中$b, c \in \mathbb{Z}[X]$且$\deg(b), \deg(c) < \deg(a)$,则它是不可约的。

我们在第2节中看到的加密方案涉及环$(\mathbb{Z}, +, \times)$上的运算。这个环的推广,也是我们在本章剩余部分将要使用的,是环$(\mathcal{R}_f, +, \times)$,其中$f \in \mathbb{Z}[X]$是次数为$d$的首一多项式。

❝

在格理论文献中，这个环通常被写作 $\mathbb{Z}[X]/(f(X))$。

$\mathcal{R}f$的元素是多项式$a = \sum{i=0}^{d-1} a_i X^i$,其中$a_i \in \mathbb{Z}$。$\mathcal{R}_f$中两个元素的和简单地涉及对$\mathbb{Z}$中相应系数求和。即,

$$ a + b = \sum_{i=0}^{d-1} (a_i + b_i) X^i $$

因此$\mathcal{R}_f$中多项式的加法可以看作$\mathbb{Z}^d$上向量的加法。因此,多项式乘以$\mathbb{Z}$中的元素也具有与向量乘以常数相同的解释。

$\mathcal{R}_f$中两个多项式的乘法涉及执行正常的多项式乘法,然后模$f$约简。模$f$约简意味着(就像对整数一样),执行除以$f$后的余数。特别地,任何多项式$a \in \mathcal{R}_f$可以唯一地写成$a = bf + r$,其中$b, r \in \mathcal{R}_f$且$\deg(r) < d$。因此$a \bmod f = r$。

要看到任何$a$确实可以以这种方式分解,我们使用归纳法。如果$\deg(a) < d$,那么$a = r$(且$b = 0$),我们就完成了。现在假设所有次数至多为$k-1$的$a$可以写成$a = bf + r$,并令$a'$的次数为$k$。那么$a' - a_k' f X^{k-d}$的次数至多为$k-1$,根据归纳假设可以写成$bf + r$对于某些$b$和$r$。因此可以写$a' = (a_k' X^{k-d} + b)f + r$。

要证明$a$的上述分解是唯一的,假设存在矛盾的不同$(b, r) \neq (b', r')$使得$bf + r = b'f + r'$。这意味着$(b - b')f + (r - r') = 0$。由于$\deg(r - r') < d$,必须有$r = r'$。那么我们知道如果$(b - b') \neq 0$,则$\deg((b - b')f) = \deg(b - b') + \deg(f) \neq 0$。因此$b = b'$,有矛盾。

注意,上述$b$和$r$存在性的证明产生了一个计算$a \bmod f$的非常简单的算法——将$f$乘以适当的单项式$\alpha X^i$并从$a$中减去它以创建次数较小的多项式,并继续直到得到次数小于$d$的多项式。例如,如果我们想要将$2X^3 + 8X^2 + 5X + 1$模$f = X^2 - 2X + 1$约简,我们写

$$ \begin{aligned} 2X^3 + 8X^2 + 5X + 1 &\equiv 2(2X^2 - X) + 8X^2 + 5X + 1 \equiv 12X^2 + 3X + 1 \pmod{f} \\ &\equiv 12(2X - 1) + 3X + 1 \equiv 27X - 11 \pmod{f} \end{aligned} $$

作为一个简单的观察,注意通常的环$(\mathbb{Z}, +, \times)$是环$(\mathcal{R}_f, +, \times)$的一个特殊实例,其中多项式$f$被定义为$f = X$(事实上$f = X - \alpha$,对于任何$\alpha \in \mathbb{Z}$也可以)。

4.1.1 多项式与线性代数

一个有用的观察是,模$f$的多项式乘法可以写成$\mathbb{Z}^{d \times d}$中的矩阵与$\mathbb{Z}^d$中的向量的乘法。观察到乘积$ab \bmod f$可以写成:

$$ ab \bmod f = a \cdot \left(\sum_{i=0}^{d-1} bi X^i\right) \bmod f = \sum{i=0}^{d-1} (aX^i \bmod f) b_i $$

由于每个$aX^i \bmod f$是次数小于$d$的多项式,它可以被视为$\mathbb{Z}^d$中的向量。因此乘法$ab$可以看作这$d$个向量的线性组合(权重为$b_i$),因此可以表示为矩阵-向量乘法。例如,乘积

$$ (2X^2 - 1)(X^2 - X + 2) \bmod X^3 - X + 1 = 5X^2 - 3X $$

可以写成

$$ \begin{bmatrix} -1 & -2 & 0 \\ 0 & 1 & -2 \\ 2 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 2 \\ -1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ -3 \\ 5 \end{bmatrix} $$

当将多项式$a = \sum_{i=0}^{d-1} a_i X^i \in \mathcal{R}_f$视为向量和矩阵时,使用记号$\mathcal{V}_a \in \mathbb{Z}^d$和$\mathcal{M}_a \in \mathbb{Z}^{d \times d}$会很方便,其中

$$ \mathcal{V}_a = \begin{bmatrix} a_0 \\ a1 \\ \vdots \\ a{d-1} \end{bmatrix} \in \mathbb{Z}^d, \quad \text{且} \quad \mathcal{M}_a = \begin{bmatrix} \mathcal{V}a & \mathcal{V}{aX \bmod f} & \cdots & \mathcal{V}_{aX^{d-1} \bmod f} \end{bmatrix} \in \mathbb{Z}^{d \times d} $$

我们没有将$f$作为$\mathcal{V}_a$和$\mathcal{M}_a$的记号的一部分,但$f$应该总是从上下文中显而易见。

使用这个记号,可以重写为

$$ \mathcal{M}{2X^2 - 1} \cdot \mathcal{V}{X^2 - X + 2} = \mathcal{V}_{5X^2 - 3X} $$

我们还可以将上述记号扩展到多项式的矩阵。对于向量$\mathbf{a} = \begin{bmatrix} a_1 \\ \vdots \\ a_n \end{bmatrix} \in \mathcal{R}f^n$和矩阵$\mathbf{A} = \begin{bmatrix} a{1,1} & \cdots & a{1,m} \\ \vdots & \vdots & \vdots \\ a{n,1} & \cdots & a_{n,m} \end{bmatrix} \in \mathcal{R}f^{n \times m}$,我们定义$\mathcal{V}{\mathbf{a}}$和$\mathcal{M}_{\mathbf{A}}$为

$$ \mathcal{V}{\mathbf{a}} = \begin{bmatrix} \mathcal{V}{a1} \\ \vdots \\ \mathcal{V}{an} \end{bmatrix} \in \mathbb{Z}^{dn}, \quad \text{且} \quad \mathcal{M}{\mathbf{A}} = \begin{bmatrix} \mathcal{M}{a{1,1}} & \cdots & \mathcal{M}{a{1,m}} \\ \vdots & \vdots & \vdots \\ \mathcal{M}{a{n,1}} & \cdots & \mathcal{M}{a{n,m}} \end{bmatrix} \in \mathbb{Z}^{dn \times dm} $$

从上述定义,可以验证对于任何$\mathbf{A} \in \mathcal{R}_f^{n \times m}$和$\mathbf{b} \in \mathcal{R}_f^m$,我们有

$$ \mathcal{M}{\mathbf{A}} \cdot \mathcal{V}{\mathbf{b}} = \mathcal{V}_{\mathbf{Ab}} \in \mathbb{Z}^{dn} $$

4.1.2 系数增长

当$a$和$b$是整数时,它们乘积的大小很容易计算——就是$ab$的绝对值。对于$a, b \in \mathcal{R}_f$,界定乘积的大小会更复杂一些,并且严重依赖于多项式$f$。因为乘法$ab \in \mathcal{R}_f$可以写成$\mathcal{M}_a \mathcal{V}_b$,乘积的最大系数的一个简单界是$d|\mathcal{M}a|{\infty} \cdot |\mathcal{V}b|{\infty}$,其中$|\cdot|_{\infty}$是最大系数的绝对值。通过计算$\mathcal{M}_a$的最大奇异值,可以获得更好的界(在$\ell_2$范数中)。但无论哪种方式,$f$对$\mathcal{M}_a$中系数大小的影响对于界定乘积都是至关重要的。

就保持$\mathcal{M}_a$小而言,我们能希望的最好情况是$|\mathcal{M}a|{\infty} = |\mathcal{V}a|{\infty}$。只有两个多项式$f$能满足这一点,即$X^d \pm 1$。对于形如$X^d \pm X^{d/2} + 1$和$\sum_{i=0}^d X^i$的多项式,我们有$|\mathcal{M}a|{\infty} \leq 2|\mathcal{V}a|{\infty}$。这里是对于多项式$a = a_0 + a_1 X + a_2 X^2 + a_3 X^3$,针对几个次数为4的$f$的一些$\mathcal{M}_a$矩阵的例子。

$$ \begin{aligned} f = X^4 - 1 &\longrightarrow \mathcal{M}_a = \begin{bmatrix} a_0 & a_3 & a_2 & a_1 \\ a_1 & a_0 & a_3 & a_2 \\ a_2 & a_1 & a_0 & a_3 \\ a_3 & a_2 & a_1 & a_0 \end{bmatrix} \\ f = X^4 + 1 &\longrightarrow \mathcal{M}_a = \begin{bmatrix} a_0 & -a_3 & -a_2 & -a_1 \\ a_1 & a_0 & -a_3 & -a_2 \\ a_2 & a_1 & a_0 & -a_3 \\ a_3 & a_2 & a_1 & a_0 \end{bmatrix} \\ f = X^4 - X^2 + 1 &\longrightarrow \mathcal{M}_a = \begin{bmatrix} a_0 & -a_3 & -a_2 & -a_1 - a_3 \\ a_1 & a_0 & -a_3 & -a_2 \\ a_2 & a_1 + a_3 & a_0 + a_2 & -a_3 + a_1 \\ a_3 & a_2 & a_1 + a_3 & a_0 + a_2 \end{bmatrix} \\ f = X^4 + X^3 + X^2 + X + 1 &\longrightarrow \mathcal{M}_a = \begin{bmatrix} a_0 & -a_3 & -a_2 + a_3 & -a_1 + a_2 \\ a_1 & a_0 - a_3 & -a_2 & -a_1 + a_3 \\ a_2 & a_1 - a_3 & a_0 - a_2 & -a_1 \\ a_3 & a_2 - a_3 & a_1 - a_2 & a_0 - a_1 \end{bmatrix} \end{aligned} $$

也有一些多项式$f$使得$|\mathcal{M}a|{\infty} \gg |\mathcal{V}a|{\infty}$。不出所料,如果$f$本身有大系数,那么$|\mathcal{M}_a|$也会如此。但也有一些具有小系数的$f$产生系数比$a$指数级大的$\mathcal{M}_a$——一个这样的例子是$f = X^d + 2X^{d-1} + 1$。导致矩阵$\mathcal{M}_a$的系数远大于$a$的多项式$f$对于密码学目的是无用的。一般来说,我们更喜欢使用导致$|\mathcal{M}a|{\infty}$和$|\mathcal{V}a|{\infty}$之间的比率为1或2的多项式。

4.2 广义LWE和SIS问题

我们现在提出定义在一般环$\mathcal{R}f$上而不仅仅是在定义1中的$\mathbb{Z}$上的LWE问题的一个版本。类似地,我们将在环$\mathcal{R}{q,f}$上工作,它类似于环$\mathcal{R}_f$,只是多项式系数在$\mathbb{Z}q$中而不是在$\mathbb{Z}$中。环$\mathcal{R}{q,f}$在格文献中通常写作$\mathbb{Z}_q[X]/(f(X))$。

❝

定义5. 对于正整数$m, n, q, \beta < q$和环$\mathcal{R}{q,f}$, $\mathcal{R}{q,f}\text{-LWE}_{n,m,\beta}$问题要求区分以下两个分布:

1. $(\mathbf{A}, \mathbf{As} + \mathbf{e})$,其中$\mathbf{A} \leftarrow \mathcal{R}_{q,f}^{n \times m}, \mathbf{s} \leftarrow [\beta]^m, \mathbf{e} \leftarrow [\beta]^n$
2. $(\mathbf{A}, \mathbf{u})$,其中$\mathbf{A} \leftarrow \mathcal{R}{q,f}^{n \times m}$且$\mathbf{u} \leftarrow \mathcal{R}{q,f}^n$

与之前一样,参数$n$对问题的难度没有任何已知的影响,除非它很大,因此我们通常只写$\mathcal{R}{q,f}\text{-LWE}{m,\beta}$。前述广义LWE问题的定义和以下密码系统遵循的研究线(将其安全性与某些格问题的最坏情况实例联系起来)是[LPR10, BV11, LPR13b, LS15]这些工作。

我们可以类似地推广[PR06, LM06, LS15]定义4中的SIS问题如下:

❝

定义6. 对于正整数$m, n, q$和$\beta < q$,以及环$\mathcal{R}{q,f}$, $\mathcal{R}{q,f}\text{-SIS}{n,m,\beta}$问题要求对于随机选择的矩阵$\mathbf{A} \leftarrow \mathcal{R}{q,f}^{n \times m}$,找到向量$\mathbf{s}_1 \in [\beta]^m$和$\mathbf{s}_2 \in [\beta]^n$(不都是$\mathbf{0}$)使得$\mathbf{As}_1 + \mathbf{s}_2 = \mathbf{0} \pmod{q}$。

在文献中,广义LWE/广义SIS问题通常被称为环LWE/环SIS或模LWE/模SIS。在NIST为格标准选择的名称ML-KEM和ML-DSA中,"ML"部分就代表"模格"(Module Lattice)。

4.3 广义LWE加密

加密方案的描述与第2.3.1节中的几乎相同,只是环$\mathbb{Z}$被替换为$\mathcal{R}_f$。该方案的主要优势是消息$\mu$在$\mathcal{R}_f$中,允许我们将$d$比特打包进去。

$$ \text{sk}: \mathbf{s} \leftarrow [\beta]^m, \quad \text{pk}: (\mathbf{A} \leftarrow \mathcal{R}_{q,f}^{m \times m}, \mathbf{t} = \mathbf{As} + \mathbf{e}_1), \text{ 其中 } \mathbf{e}_1 \leftarrow [\beta]^m. $$

要加密系数在$\{0,1\}$中的消息$\mu \in \mathcal{R}_f$,加密者采样$\mathbf{r}, \mathbf{e}_2 \leftarrow [\beta]^m$和$e_3 \leftarrow [\beta]$,并输出

$$ \left(\mathbf{u}^T = \mathbf{r}^T \mathbf{A} + \mathbf{e}_2^T, \quad v = \mathbf{r}^T \mathbf{t} + e_3 + \frac{q}{2} \mu\right). $$

基于$\mathcal{R}{q,f}\text{-LWE}{m,\beta}$的安全性论证与第2.3.1节中基于$\text{LWE}_{m,q,\beta}$的证明相同。

要解密,计算

$$ \begin{aligned} v - \mathbf{u}^T \mathbf{s} &= \mathbf{r}^T(\mathbf{As} + \mathbf{e}_1) + e_3 + \frac{q}{2} \mu - (\mathbf{r}^T \mathbf{A} + \mathbf{e}_2^T) \mathbf{s} \\ &= \mathbf{r}^T \mathbf{e}_1 + e_3 + \frac{q}{2} \mu - \mathbf{e}_2^T \mathbf{s} \end{aligned} $$

要计算解密错误,我们可以将上述方程(不包括$\frac{q}{2} \mu$)重写为

$$ \mathcal{M}{\mathbf{r}^T} \mathcal{V}{\mathbf{e}1} + \mathcal{V}{e3} - \mathcal{M}{\mathbf{e}2^T} \mathcal{V}{\mathbf{s}} $$

然后应用第2.3.2节中的技术来计算$d$个系数中没有一个的幅度大于$q/4$的概率。当$f = X^d \pm 1$时,对于$d$个系数中的每一个,计算这个概率与我们在整数上工作时相同,因为$\mathcal{M}{\mathbf{r}^T}$和$\mathcal{M}{\mathbf{e}_2^T}$的每一行中的系数都是独立的。然后应用并集界来界定所有$d$个解密错误都很小的概率。对于其他多项式上的环,如果可以将矩阵-向量乘法重写为独立随机变量的和,仍然可以应用第2.3.2节中的技术。

4.3.1 优化和效率

广义LWE方案的主要优势是不需要像第2.4节那样增加公钥的大小就能加密更大的消息。当$f$的次数为$d$时,环自然支持加密$d$比特。因此只要我们设置$d \geq 256$,这是使用公钥加密会加密的AES(或任何对称密码)密钥的长度,就能够使用最优小的公钥。类似地,不需要像第2.5.4节那样每个系数打包多于一个消息比特。第2.5.1节中的优化仍然非常有用,并且以与之前完全相同的方式应用。带舍入的学习问题和密码系统(第2.5.3节),以及非交互式密钥交换(第2.6节),也类似地为环$\mathcal{R}_f$定义。

4.3.2 安全性与整数格的联系

$\mathcal{R}f$中多项式运算与$\mathbb{Z}$上线性代数之间的联系允许我们在第3.1节中看到的格与上一节中$\mathcal{R}{q,f}\text{-LWE}_{n,m,\beta}$定义中涉及的多项式方程的(短)解之间建立有用的联系。基于LWE的加密方案的难度依赖于区分$(\mathbf{A}, \mathbf{t} = \mathbf{As} + \mathbf{e})$与均匀随机$(\mathbf{A}, \mathbf{u})$的难度,对于随机$\mathbf{A} \in \mathbb{Z}_q^{n \times m}$和系数很小的整数向量$\mathbf{s} \in \mathbb{Z}_q^m, \mathbf{e} \in \mathbb{Z}_q^n$。我们在第3.3节中看到,在格

$$ \mathcal{L}_q^{\perp}([\mathbf{A}^T \mid \mathbf{I}_m]) $$

中找到短向量允许我们构建这样的区分器,我们将LWE加密方案的具体安全性基于后一个问题的难度。

本节中更高效加密方案的安全性类似地基于区分$(\mathbf{A}, \mathbf{t} = \mathbf{As} + \mathbf{e})$与均匀随机$(\mathbf{A}, \mathbf{u})$的难度,对于随机$\mathbf{A} \in \mathcal{R}{q,f}^{n \times m}$和系数很小的多项式向量$\mathbf{s} \in \mathcal{R}{q,f}^m, \mathbf{e} \in \mathcal{R}{q,f}^n$。这等价于区分$(\mathcal{M}{\mathbf{A}}, \mathcal{V}{\mathbf{t}} = \mathcal{M}{\mathbf{A}} \mathcal{V}{\mathbf{s}} + \mathcal{V}{\mathbf{e}})$与均匀随机$(\mathcal{M}{\mathbf{A}}, \mathcal{V}{\mathbf{u}})$。由于这个区分问题现在是在$\mathbb{Z}_q$上,我们可以将其转换为关于在整数格中找到短向量的问题——即如上所述在格$\mathcal{L}q^{\perp}([\mathcal{M}{\mathbf{A}}^T \mid \mathbf{I}_{dm}])$中找到系数很短的向量。

因为$\mathcal{M}_{\mathbf{A}}^T$是一个$dm \times dn$整数矩阵,格

$$ \mathcal{L}q^{\perp}([\mathcal{M}{\mathbf{A}}^T \mid \mathbf{I}_{dm}]) $$

的维度是$d(m+n)$。如果$\mathcal{R}f$的代数结构没有表现出任何弱点(见下面的第4.5节),那么在这个格中找到短向量的难度与$\text{LWE}{n',m',q,\beta}$格中的相同,其中$n' = dn$和$m' = dm$。因此,对于$\mathcal{R}{q,f}\text{-LWE}{n,m,\beta}$问题,重要的值是$dm$——$\mathcal{R}_f$中$f$的次数与$\mathbf{A} \in \mathcal{R}f^{n \times m}$的列数的乘积。类似地,对于$\mathcal{R}{q,f}\text{-SIS}_{n,m,\beta}$问题,重要的值是$dn$——$f$的次数与$\mathbf{A}$中行数的乘积。

4.4 NTRU

NTRU密码系统[HPS98]是第一个真正高效的基于格的加密方案,也是第一个提议使用多项式环——特别是$\mathcal{R}_{q,X^d-1}$——在基于格的密码学中的方案。该方案最初被提出作为陷门单向函数,可以看作是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问题的判定版本,但定义其搜索版本也很自然。这个问题可以陈述为在给定$(a, as + e)$时找到$e$,其中$a \leftarrow \mathcal{R}{q,f}$和$s, e \leftarrow [\beta]$。注意如果$a$在$\mathcal{R}{q,f}$中可逆,那么找到$e$立即也意味着找到$s$。

NTRU问题与上述非常相似,除了多项式$a$不是从$\mathcal{R}_{q,f}$中随机选择,而是整数$p = (2\beta + 1)$与多项式$g_1$和$g_2^{-1}$的乘积,其中$g_i \leftarrow [\beta]$(条件是$g_2$可逆)并且$p$与$q$互质(例如$\beta = 1$是一个流行的选择)。NTRU背后的难度依赖于这样的假设:每当$a$不是均匀随机而是乘积$pg_1 g2^{-1}$时,搜索$\mathcal{R}{q,f}\text{-LWE}_{n,m,\beta}$问题(其中$n = m = 1$)仍然是困难的。

NTRU问题 正式定义如下:

❝

定义7. 令$p = 2\beta + 1$。给定$(a, as + e)$,其中$a = pg_1 g_2^{-1}$,对于$g_1, g_2, s, e \leftarrow [\beta]$且$g2$在$\mathcal{R}{q,f}$和$\mathcal{R}_{p,f}$中可逆,找到$e$。

基于上述问题的假定难度,我们可以如下构造陷门单向函数族:要从该族生成随机元素,选择秘密可逆多项式$g_1, g_2 \leftarrow [\beta]$,其中$g2$在$\mathcal{R}{q,f}$和$\mathcal{R}_{p,f}$中可逆,并将公钥设置为

$$ a = pg_1 g_2^{-1} $$

私钥是$g_2$。

将$s, e \leftarrow [\beta]$映射到$\mathcal{R}_{q,f}$的单向函数计算

$$ b = as + e \in \mathcal{R}_{q,f} $$

观察到为了从$b$恢复$e$和$s$,足以模$p$恢复这些,因为在$[\beta]$中的元素与模$p = 2\beta + 1$的剩余之间存在一一对应。要使用私钥模$p$恢复$s, e$,首先计算

$$ g_2 b \bmod p = pg_1 s + g_2 e \bmod p = g_2 e \bmod p $$

等式$g_2 b = pg_1 s + g2 e$在环$\mathcal{R}{q,f}$上简单地从$a$和$b$的定义得出。因为$g_i, s, e$和$p$的系数相对于$q$足够小,等式$g_2 b = pg_1 s + g2 e$不仅在$\mathcal{R}{q,f}$中成立,而且在$\mathcal{R}_f$上也成立。因此当两边都模$p$约简时它也成立,所以只剩下$g_2 e$。如果上式成立,那么也有

$$ (g_2 b \bmod p) g_2^{-1} \bmod p = e $$

乘以$g2$在$\mathcal{R}{p,f}$中的逆。一旦有$e \pmod{p}$,这与$e \in [\beta]$相同,我们也可以计算

$$ (b - e) a^{-1} = s $$

我要敦促第一次看到NTRU的读者,再看一次并欣赏它的微妙之处。特别是,尽管使用两个互质模数进行模运算上式仍成立,而这种做法通常很少能导出任何有意义的结果！

4.4.2 安全性

如果我们不假设多项式$a$有任何特殊结构,那么恢复$s, e$与对广义LWE实例的公钥的攻击相同,其中我们试图在格

$$ \mathcal{L}_q^{\perp}([\mathcal{M}_a | \mathcal{V}_b | \mathbf{I}_d]) $$

中找到短向量。也可以尝试通过寻找格

$$ \mathcal{L}q^{\perp}([\mathcal{M}{p^{-1}a} | \mathbf{I}_d]) $$

中的短向量从$a = pg_1 g_2^{-1}$恢复私钥$g_1, g_2$(或与其相关的某些其他短多项式)。

这两个格看起来非常相似,唯一相关的区别是第一个存在一个额外的向量$\mathcal{V}_b$。因此有些令人惊讶的是,在某些情况下,当$q$显著大于$\beta$时(但不是大到明显在通用格约简算法工作的空间中),在第二个格中找到短向量比在第一个中显著容易[ABD16, CJL16, KF17]。虽然这些攻击不会转化为对NTRU参数的攻击,但它们确实阻止NTRU假设用于需要大模数和小噪声的高级原语(例如FHE)。由于这个原因,在这些情况下使用基于广义LWE的方案(其安全性本质上依赖于第一个格。

4.5 利用代数结构...进行攻击

假设我们在环$\mathcal{R}{q,f}$上工作,其中$f = X^d - 1$。因为$X - 1$是$X^d - 1$的因子,存在从$\mathcal{R}{q,f}$到$\mathcal{R}{q,X-1}$的环同态,它将元素$a = \sum{i=0}^{d-1} ai X^i \in \mathcal{R}{q,f}$映射到$a' = \sum_{i=0}^{d-1} ai \in \mathcal{R}{q,X-1}$。因为环$\mathcal{R}_{q,X-1}$恰好是具有通常模$q$加法和乘法的环$\mathbb{Z}q$,实际上有从$\mathcal{R}{q,f}$到$\mathbb{Z}q$的环同态。这个同态特别特殊的地方在于,如果$a$的系数很小,那么同态下$a$的像也很小(即只能大$d$倍)。这意味着对$\mathcal{R}{q,f}\text{-LWE}{m,\beta}$问题的以下简单攻击,其中给定$\mathbf{A} \in \mathcal{R}{q,f}^{n \times m}, \mathbf{t} \in \mathcal{R}{q,f}^n$并被要求判断是否存在系数在$[\beta]$中的$\mathbf{s}, \mathbf{e}$满足$\mathbf{As} + \mathbf{e} = \mathbf{t}$(这个攻击首次针对$\mathcal{R}{q,f}\text{-SIS}{n,m,\beta}$问题在[PR06, LM06]中给出,我们在这里将其改编为对$\mathcal{R}{q,f}\text{-LWE}_{n,m,\beta}$的攻击):

令$\mathbf{A}' \in \mathbb{Z}_q^{n \times m}, \mathbf{t}' \in \mathbb{Z}_q^n$是$\mathbf{A}, \mathbf{t}$在同态下的像。如果确实存在$\mathbf{s} \in [\beta]^m \subset \mathcal{R}_f^m$和$\mathbf{e} \in [\beta]^n \subset \mathcal{R}_f^n$满足$\mathbf{As} + \mathbf{e} = \mathbf{t}$,那么存在$\mathbf{s}' \in [d\beta]^m \subset \mathbb{Z}^m, \mathbf{e}' \in [d\beta]^n \subset \mathbb{Z}^n$满足$\mathbf{A}' \mathbf{s}' + \mathbf{e}' = \mathbf{t}'$。因为$m$和$n$相当小,我们就剩下求解一个小维LWE问题,可以如第3.3节那样完成。

使上述对$\mathcal{R}{q,f}\text{-LWE}{m,\beta}$的攻击成为可能的最关键元素是存在到较小次数环的同态,该同态不会大幅增加系数大小。如果$f$有一个因子,例如$X - 2$,那么上述攻击将不起作用,因为同态会将元素$a = \sum_{i=0}^{d-1} ai X^i \in \mathcal{R}{q,f}$映射到$a' = \sum_{i=0}^{d-1} a_i 2^i \in \mathbb{Z}q$,因此$a'$将在指数依赖于$d$的范围内。有趣的是,表明求解$\mathcal{R}{q,f}\text{-LWE}{m,\beta}$和$\mathcal{R}{q,f}\text{-SIS}_{n,m,\beta}$意味着在理想/模格中找到短向量的最坏情况到平均情况归约[PR06, LM06, LPR13a, LS15, PRS17]只要求$f$在环$\mathbb{Z}[X]$而不是$\mathbb{Z}q[X]$上不可约(或至少在$\mathcal{R}{q,f}\text{-SIS}{n,m,\beta}$的情况下有大次数不可约因子)。正如我们将在下一节中看到的,就实现效率而言,在环$\mathcal{R}{q,f}$上工作实际上是相当有利的,其中多项式$f$在$\mathbb{Z}_q[X]$中有许多低次因子。

4.6 利用代数结构...提高效率(数论变换)

$\mathcal{R}{q,f}\text{-LWE}{n,m,\beta}$加密方案中计算量最大的代数运算是$\mathcal{R}{q,f}$中多项式的乘法。两个次数为$d$的多项式的基本"小学"多项式乘法需要$O(d^2)$次运算。有更好的方法,如Karatsuba和Toom-Cook,大约需要$O(d^{1.5})$时间。在$\mathcal{R}{q,f}$中执行多项式乘法的最高效方法只需要$O(d \log d)$次对$\mathbb{Z}_q$的运算,这是通过NTT(数论变换)实现的,它是在域$\mathbb{Z}_q^*$而不是在复数上执行的FFT的特例。使用支持NTT的特殊环来加速基于格的原语的想法首次用于SWIFFT抗碰撞哈希函数[LMPR08],现在广泛用于其他原语(如加密方案(例如[ADPS16, BDK+18])和数字签名(例如[DKL+18, PFH+17]))的实际实例化中。

我们现在将解释多项式环$\mathbb{Z}_q[X]/(X^d + \alpha)$上的NTT算法,其中$\alpha \in \mathbb{Z}$且$d$是2的幂。假设$-\alpha$在$\mathbb{Z}_q$中有平方根$r$,因此我们可以写$X^d + \alpha \equiv (X^{d/2} - r)(X^{d/2} + r) \pmod{q}$。那么计算$ab \in \mathbb{Z}_q[X]/(X^d + \alpha)$可以通过中国剩余定理完成。即,我们可以首先计算

$$ \begin{aligned} &(a \bmod X^{d/2} - r, \quad a \bmod X^{d/2} + r) \\ &(b \bmod X^{d/2} - r, \quad b \bmod X^{d/2} + r) \end{aligned} $$

然后逐分量相乘得到

$$ (ab \bmod X^{d/2} - r, \quad ab \bmod X^{d/2} + r), $$

然后可以使用上述来重构$ab \bmod X^d + \alpha$。

在引理5中,我们表明分解上两式需要$d$次加法和$d/2$次对$\mathbb{Z}_q$的乘法,从上式重构$ab \bmod X^d + \alpha$需要相同数量的运算。因此计算乘积$ab$需要$2d$次加法,$d$次乘法,以及两次在环$\mathbb{Z}_q[X]/(X^{d/2} \pm r)$上的乘法。由于后者环上的乘法仍然是$O(n^2)$时间,目前还不清楚我们取得了进展——但如果多项式$X^{d/2} - r$可以进一步分解为$(X^{d/4} - s)(X^{d/4} + s)$(类似地$X^{d/2} + r = (X^{d/4} - t)(X^{d/4} + t)$),那么我们可以递归地计算!

特别是,我们现在可以使用递推关系计算整个算法的运行时间,其中$T(d)$是在$\mathbb{Z}_q[X]/(X^d + \alpha)$中乘两个多项式的时间,$A$和$M$分别是计算$\mathbb{Z}_q$中一次整数加法和乘法所需的时间。从上述讨论,这个递推关系是

$$ T(d) = 2 \cdot T(d/2) + 2d \cdot A + d \cdot M $$

如果$d$是2的幂并且$-1$和$-\alpha$在$\mathbb{Z}_q$中有$d$次根,那么我们可以继续递归直到$X^d + \alpha$分解为线性因子,因此上述递推对$d, d/2, d/4, \ldots, 2$是良定义的。

❝

为了看为什么这样，设 $r, s \in \mathbb{Z}_q^*$ 使得 $r^d = -\alpha$ 和 $s^d = -1$。我们将通过归纳法证明这个声明。在递归的每一层，不变量是所有因子都是 $X^k \pm s^l r^k$ 的形式，其中 $2 \le k \le d$ 是2的幂且 $k|l$。这个不变量由基础情况满足：$X^d + \alpha = X^d + s^d r^d$。我们现在进行到归纳步骤：因为 $k|l$，如果 $k/2$ 是一个整数，那么 $l/2$ 也是，因此形式为 $X^k - s^l r^k$ 的项分解为 $(X^{k/2} + s^{l/2} r^{k/2})(X^{k/2} - s^{l/2} r^{k/2})$，而形式为 $X^k + s^l r^k$ 的项分解为 $(X^{k/2} + \sqrt{-1} s^{l/2} r^{k/2})(X^{k/2} - \sqrt{-1} s^{l/2} r^{k/2})$。将 $\sqrt{-1} = s^{d/2}$ 代入，前面的两个因子是 $(X^{k/2} \pm s^{l/2+d/2} r^{k/2})$ 的形式。因为 $k|l$ 和 $k|d$，我们有 $\frac{k}{2} \mid \frac{l}{2} + \frac{d}{2}$，下一层的不变量得到满足。当 $k = 1$ 时递归停止。

因此这个递推的解是

$$ T(d) = d \cdot T(1) + 2d \log d \cdot A + d \log d \cdot M $$

其中$T(1) = M$。所以在环$\mathbb{Z}_q[X]/(X^d + \alpha)$中计算乘积可能只需要$2d \log d$次整数加法和$d(\log d + 1)$次对$\mathbb{Z}_q$的乘法。

当$\alpha = 1$时,上述给出了环$\mathcal{R}_{q,X^d+1} = \mathbb{Z}_q[X]/(X^d + 1)$中的高效乘法算法。为了能够将多项式$X^d + 1$一直分解到线性项,需要$-1$有$d$次根,或者换句话说,乘法群$\mathbb{Z}_q^*$有$2d$次单位根。

❝

回顾一下，一个元素 $r$ 是 $k$ 次本原单位根，如果 $r^k = 1$ 且对所有 $0 < j < k$ 有 $r^j \ne 1$。如果 $r$ 是 $k$ 次本原单位根，那么必然有 $r^{k/2} = -1$。

每当模数$q$是满足$q \equiv 1 \pmod{2d}$的素数时,这样的单位根就存在(见引理7)。应该注意的是,即使$q$不满足后者,NTT算法仍然可以执行;只是我们将无法一直递归到线性多项式。例如,如果$q \equiv 1 \pmod{d}$,那么多项式$X^d + 1$可以分解为二次项的乘积。这意味着在底层,逐分量乘法将在环$\mathbb{Z}_q[X]/(X^2 - r_i)$中进行,对于某些$r_i \in \mathbb{Z}_q^*$。虽然这个基础乘法需要超过对$\mathbb{Z}_q$的1次乘法,但仍然可以用小常数次乘法和加法(即对$\mathbb{Z}_q$的5次乘法和2次加法)执行。并且因为我们少做一层分解,总运算次数实际上相同。

❝

在我们不能一直往下到线性因子的情况下，可以容易地求解递推式。

也不一定需要多项式$f$是$X^d + 1$才能从NTT中受益。还有其他(分圆)多项式具有与$X^d + 1$非常相似的分解树。例如,对于某些$d = 2^k \cdot 3$和素数$q$,多项式$f = X^d - X^{d/2} + 1$模$q$分解为$(X^{d/2} - r_1)(X^{d/2} - r_2)$,然后可以应用NTT递归算法在环$\mathbb{Z}_q[X]/(X^{d/2} - r_i)$上相乘——主要区别是由于$d$不是2的幂,我们将无法将$X^{d/2} \pm ri$分解为1次多项式,而是分解为3次多项式。但总体上,在这样的环上(参见[LS19])几乎可以像在$\mathcal{R}{q,X^d+1}$上一样高效地执行乘法。也可以通过在$\mathbb{Z}q[X]$上相乘然后模$f$约简,对任意$f$的环$\mathcal{R}{q,f}$利用NTT乘法。$\mathbb{Z}q[X]$上的乘法可以通过在$\mathcal{R}{q,X^d+1}$上乘法来执行,其中次数$d$被选择得足够高,使得模$X^d + 1$的约简永远不会发生(即$d$设置为大于$2 \cdot (\deg(f) - 1)$的整数)——这个算法通常仍然是在多项式环上乘两个元素的最高效方法(参见[CHK+21])。

我们现在证明上面提到的引理,它表明计算所需的运算次数,以及从CRT表示重构环中元素,需要$d$次加法和$d/2$次乘法。

❝

引理5. 假设多项式$g(X) = X^n + \alpha$可以写成

$$ X^n + \alpha \equiv (X^{n/2} - r)(X^{n/2} + r) \pmod{q} $$

❝

并定义函数$\phi$,

$$ \begin{aligned} \phi &: \mathbb{Z}_q[X]/(X^n + \alpha) \rightarrow \mathbb{Z}_q[X]/(X^{n/2} - r) \times \mathbb{Z}_q[X]/(X^{n/2} + r) \\ \phi(a) &= (a \bmod X^{n/2} - r, \quad a \bmod X^{n/2} + r) \end{aligned} $$

❝

如果$r \pmod{q}$和$r^{-1} \pmod{q}$是预先计算的,那么$\phi$和$2 \cdot \phi^{-1}$各自可以使用$n$次对$\mathbb{Z}_q$的加法/减法和$n/2$次乘法来计算。

证明. 如果我们写

$$ \begin{aligned} a &= \sum_{i=0}^{n-1} ai X^i \\ a \bmod X^{n/2} - r &= \sum{i=0}^{n/2-1} bi X^i \\ a \bmod X^{n/2} + r &= \sum{i=0}^{n/2-1} c_i X^i \end{aligned} $$

那么可以看到对于所有$0 \leq i < n/2$,

$$ \begin{aligned} b_i &= ai + r \cdot a{i+n/2} \\ c_i &= ai - r \cdot a{i+n/2} \end{aligned} $$

因此计算$\phi$需要$n/2$次乘以$r$和$n$次加法(或减法)来计算$ai \pm r \cdot a{i+n/2}$。对于反向,可以通过从上面观察到对于所有$0 \leq i < n/2$,

$$ \begin{aligned} 2 \cdot a_i &= b_i + ci \\ 2 \cdot a{i+n/2} &= r^{-1} \cdot (b_i - c_i) \end{aligned} $$

来重构$2 \cdot a$。上述两个运算类似地需要$2n$次加法(或减法)和$n/2$次乘法。□

在上述引理的陈述中需要注意的一点是,我们不是计算逆$\phi^{-1}$,而是$2 \cdot \phi^{-1}$。我们这样做的原因是它节省了乘法。在递归算法中,引理中的过程运行若干次(比如$\log d$)迭代,逆的加倍将不断累积,使得最终结果是正确答案的$2^{\log d} = d$倍。然后我们只在最后一层乘以$d^{-1}$。所以不是在每个$\log d$层执行额外的乘以$2^{-1}$,我们只在最后一层执行。

4.6.1 环$\mathcal{R}_{q,X^d+1}$的有用代数性质

在上一节中,我们看到了在环$\mathcal{R}{q,X^d+1}$上乘法的非常高效的算法,我们还看到为了安全性,多项式$X^d + 1$在$\mathbb{Z}[X]$上不可约是很好的。在本节中,我们陈述并证明环$\mathcal{R}{q,X^d+1}$的一些有用性质。第一个引理指出,多项式$X^d + 1$在整数上不可约当且仅当$d$是2的幂。

❝

引理6. 多项式$X^d + 1$在$\mathbb{Z}[X]$上不可约当且仅当$d$是2的幂。

证明. 令$\Phi_k(X)$是第$k$个分圆多项式,并回忆对于任何$n$

$$ X^n - 1 = \prod_{k \mid n} \Phi_k(X) $$

因此$(X^d + 1)(X^d - 1) = X^{2d} - 1$,因此

$$ X^d + 1 = \frac{X^{2d} - 1}{X^d - 1} = \frac{\prod_{k \mid 2d} \Phik(X)}{\prod{k \mid d} \Phik(X)} = \prod{k: k \mid 2d, k \nmid d} \Phi_k(X). $$

如果$d = 2^\ell$对于某个非负整数$\ell$,那么从上面得出$X^d + 1 = \Phi{2d}(X)$,因此是不可约的(因为所有分圆多项式都是不可约的)。另一方面,如果$d = 2^\ell \cdot d'$,其中$d' > 1$是奇数,那么$2d$和$2d/d' = 2^{\ell+1}$都整除$2d$,但都不整除$d$。所以$\Phi{2d}(X)$和$\Phi_{2d/d'}(X)$是$X^d + 1$的不同因子。□

下一个引理对于选择模数$q$使得多项式$X^d + 1$分解为低次多项式很有用。

❝

引理7. 令$d \geq k \geq 1$,其中$k \mid d$且$q \equiv 1 \pmod{2k}$是素数。那么存在$k$个不同的$r_i \in \mathbb{Z}_q^*$满足$r_i^k \equiv -1 \pmod{q}$使得

$$ X^d + 1 \equiv \prod_{i=1}^k (X^{d/k} - r_i) \pmod{q}. $$

证明. 因为素数$q$使得$q \equiv 1 \pmod{2k}$,我们有$2k \mid q-1$,所以存在阶为$2k$的元素$r \in \mathbb{Z}q^*$,因此$r^k \equiv -1 \pmod{q}$。此外,对于所有奇数$i \in {0, \ldots, k-1}$,所有$r^{2i+1}$模$q$都是不同的并且满足$(r^{2i+1})^k \equiv -1 \pmod{q}$。因此$k$个元素$r^{2i+1}$是$X^k + 1$的根,因此我们有$X^k + 1 \equiv \prod{i=0}^{k-1} (X - r^{2i+1}) \pmod{q}$。通过在前面的等式中用$X^{d/k}$代替$X$,引理得证。□

最后一个引理在本教程中没有使用,但我们在这里陈述它以保证完整性,因为对于一些高级应用记住它很有用。它指出对于所有素数$q$,多项式$X^d + 1$永远不是不可约的;所以$\mathcal{R}_{q,X^d+1}$(不幸地)永远不是域。如果想要一个"几乎是域"的环,可以设置环参数(见[LS18])使得多项式$X^d + 1$分解为形如$X^{d/2} \pm r$的两个不可约多项式。

❝

引理8. 令$q$是奇素数,$d$是4的倍数。那么多项式$X^d + 1$在$\mathbb{Z}_q[X]$上至少分解为2个多项式。

证明. 如果$q \equiv 1 \pmod{4}$,那么$X^d + 1$模$q$的因子如引理7中设置$k = 2$时所示。

如果$q \equiv 3 \pmod{4}$,那么对于所有$x \in \mathbb{Z}_q^*$,恰好$x$或$-x$之一是模$q$的二次剩余。

❝

为了看到这一点，假设它们都是二次非剩余或二次剩余，因此它们的乘积必须是二次剩余，所以存在一个 $r$ 使得 $-x^2 \equiv r^2 \pmod{q}$。存在一个整数 $k$ 使得 $q = 3 + 4k$，我们将前面的同余式的两边都提升到 $2k+1$ 次幂，得到 $-x^{4k+2} \equiv r^{4k+2} \pmod{q}$。因为 $4k+2 = q-1$，费马小定理蕴含 $x^{4k+2}$ 和 $r^{4k+2}$ 都同余于 1，因此我们得到矛盾 $-1 \equiv 1 \pmod{q}$。

如果2是模$q$的二次剩余,则设$b = 1$,如果$-2$是,则设$b = -1$。最后令$r$使得$r^2 \equiv 2 \cdot b \pmod{q}$。那么

$$ \begin{aligned} X^d + 1 &\equiv X^d + (2b - r^2) \cdot X^{d/2} + 1 \pmod{q} \ &\equiv (X^{d/2} + b)^2 - r^2 \cdot X^{d/2} \pmod{q} \ &\equiv (X^{d/2} + b + rX^{d/4}) \cdot (X^{d/2} + b - rX^{d/4}) \pmod{q}, \end{aligned} $$

如所声称。□

4.7 加密方案CRYSTALS-Kyber(ML-KEM)

在本节中,我们将把所有内容放在一起,给出NIST标准化的CRYSTALS-Kyber(被NIST命名为ML-KEM)方案的完整描述,该方案基于广义LWE问题的难度。该方案在环$\mathcal{R}{3329,X^{256}+1}$上工作,私钥的分布是从二项分布中抽取的,而不是我们迄今为止一直使用的均匀分布。使用二项分布(我们将其表示为正整数$\eta$的$\psi\eta$)的主要原因仅仅是因为它更容易采样。

❝

定义8. 对于整数$\eta$,从二项分布$\psi_\eta$生成的元素如下:生成随机$a1, \ldots, a\eta, b1, \ldots, b\eta \leftarrow \{0,1\}$并输出$\sum a_i - \sum b_i$。这个定义自然地扩展到多项式,其中对于$a \in \mathcal{R}f$,我们写$a \leftarrow \psi\eta$表示$a$的每个整数系数都根据$\psi\eta$独立采样。类似地,对于维度为$k$的向量(多项式的),我们写$\mathbf{a} \leftarrow \psi\eta^k$表示每个元素都根据$\psi_k$采样。

CRYSTALS-Kyber CCA安全KEM的核心是CPA安全加密方案。从后者到CCA安全KEM的转换是通用的,我们在第4.8节中简要描述它。然而,在本节的其余部分,我们只关注CPA安全加密。

CPA安全加密方案Kyber呈现在图3中。Kyber的安全参数是$k, \eta_1, \eta_2$,其中$k$是在安全级别之间变化的主要参数。参数$d_u$和$d_v$指定密文的不同部分被舍入到的集合$\mathcal{S}$(参见图1))的(对数)大小。这些值决定了密文大小和解密错误。

公共参数: $k, \eta_1, \eta_2, d_u, d_v \in \mathbb{Z}^+$

CPA-KeyGen	CPA-Encrypt$(pk, m)$	CPA-Decrypt$(sk, \text{ciphertext})$
$\mathbf{A} \leftarrow \mathcal{R}_{3329,X^{256}+1}^{k \times k}$	$(\mathbf{r}, \mathbf{e}_1, e2) \leftarrow \psi{\eta1}^k \times \psi{\eta2}^k \times \psi{\eta_2}$	$\mathbf{u}' := \lceil \mathbf{u} \rfloor_{2^{d_u} \rightarrow q}$
$(\mathbf{s}, \mathbf{e}) \leftarrow \psi_{\eta1}^k \times \psi{\eta_1}^k$	$\mathbf{u}^T := \lceil \mathbf{r}^T \mathbf{A} + \mathbf{e}1^T \rfloor{q \rightarrow 2^{d_u}}$	$v' := \lceil v \rfloor_{2^{d_v} \rightarrow q}$
$\mathbf{t} := \mathbf{As} + \mathbf{e}$	$v := \lceil \mathbf{r}^T \mathbf{t} + e2 + \frac{q-1}{2} m \rfloor{q \rightarrow 2^{d_v}}$	$m' := \lceil v' - \mathbf{u}'^T \mathbf{s} \rfloor_{q \rightarrow 2}$
$pk = (\mathbf{A}, \mathbf{t}), sk = \mathbf{s}$	$\text{ciphertext} = (\mathbf{u}, v)$

图3: CRYSTALS-Kyber CPA安全加密方案

密钥生成过程与之前完全相同,除了私钥向量$\mathbf{s}, \mathbf{e} \in \mathcal{R}{X^{256}+1}^k$是根据二项分布而不是均匀分布生成的。要加密二进制多项式$m \in \mathcal{R}{X^{256}+1}$,加密过程从二项分布$\psi_\eta$生成向量$\mathbf{r}, \mathbf{e}1 \in \mathcal{R}{X^{256}+1}^k$和环元素$e2 \in \mathcal{R}{X^{256}+1}$(可能使用不同的$\eta$值——我们稍后会解释其直觉),并如之前计算未压缩的密文。然后我们对密文应用压缩函数(见第2.5.1节和第2.5.2节)以减少密文大小。解密函数使用压缩函数，恢复0/1系数。

正确性和解密错误

要计算解密错误,我们查看项

$$ \begin{aligned} \lceil v' - \mathbf{u}'^T \mathbf{s} \rfloor{q \rightarrow 2} &= \lceil \lceil v \rfloor{2^{dv} \rightarrow q} - \lceil \mathbf{u}^T \rfloor{2^{du} \rightarrow q} \mathbf{s} \rfloor{q \rightarrow 2} \ &= \lceil \lceil \lceil \mathbf{r}^T \mathbf{t} + e2 + \frac{q-1}{2} m \rfloor{q \rightarrow 2^{dv}} \rfloor{2^{d_v} \rightarrow q} - \lceil \lceil \mathbf{r}^T \mathbf{A} + \mathbf{e}1^T \rfloor{q \rightarrow 2^{du}} \rfloor{2^{du} \rightarrow q} \mathbf{s} \rfloor{q \rightarrow 2} \ &= \lceil \mathbf{r}^T \mathbf{t} + e_2 + \frac{q-1}{2} m + e' - (\mathbf{r}^T \mathbf{A} + \mathbf{e}1^T + \mathbf{e}''^T) \mathbf{s} \rfloor{q \rightarrow 2} \end{aligned} $$

对于$e' \in \mathcal{R}{X^{256}+1}, \mathbf{e}'' \in \mathcal{R}{X^{256}+1}^k$,其系数对应于引理1中的$\eta$。将$\mathbf{t}$替换为$\mathbf{As} + \mathbf{e}$,我们得到

$$ \lceil v' - \mathbf{u}'^T \mathbf{s} \rfloor_{q \rightarrow 2} = \lceil \mathbf{r}^T \mathbf{e} + e_2 + \frac{q-1}{2} m + e' - (\mathbf{e}1 + \mathbf{e}'')^T \mathbf{s} \rfloor{q \rightarrow 2} $$

如果

$$ \mathbf{r}^T \mathbf{e} + e_2 + e' - (\mathbf{e}_1 + \mathbf{e}'')^T \mathbf{s} $$

的所有系数在幅度上小于$q/4$,则上述结果将是$m$。计算这个概率如第2.3.2节中那样完成。我们已经在第4.3节中讨论了如何将这些技术适应环设置。唯一区别是还包括由压缩和解压缩操作产生的项$e'$和$\mathbf{e}''$。通过假设被压缩的项是均匀随机的,可以计算$e'$和$\mathbf{e}''$的每个系数的精确概率分布——即对于随机$x \leftarrow \mathbb{Z}q$,$\lceil \lceil x \rfloor{q \rightarrow 2^{dv}} \rfloor{2^{d_v} \rightarrow q}$的概率分布(相应地用$d_u$代替$d_v$)。一旦我们计算出一个系数的精确错误概率,我们可以应用并集界(即乘以256)来获得错误概率的上界。这些值在表3中给出。

表3: Kyber三个实例化的参数。三个方案的安全性在实践中应该不比AES-128、AES-192和AES-256分别差。

k	$\eta_1$	$\eta_2$	$d_u$	$d_v$	解密错误	公钥大小	密文大小
Kyber-512	2	3	2	10	4	$2^{-139}$	800 B	768 B
Kyber-768	3	2	2	10	4	$2^{-164}$	1184 B	1088 B
Kyber-1024	4	2	2	11	5	$2^{-174}$	1568 B	1568 B

安全性

Kyber的安全性基于$\mathcal{R}{3329,X^{256}+1}\text{-LWE}{k,\psi_2}$问题的难度。安全性证明的工作方式与第2.3.1节和第4.3节中方案的证明完全相同。需要注意的一点是,在Kyber-512中,$\eta_1$的值设置为3,而$\eta2 = 2$。这意味着区分公钥$(\mathbf{A}, \mathbf{t})$与均匀随机的基于$\mathcal{R}{3329,X^{256}+1}\text{-LWE}_{k,\psi_3}$的难度,而区分密文与均匀的难度基于"混合"分布,其中$\mathbf{r}$的系数从$\psi_3$选择,而$\mathbf{e}_1$和$e_2$的系数从$\psi2$选择。这至少与$\mathcal{R}{3329,X^{256}+1}\text{-LWE}_{k,\psi_2}$问题一样困难,但注意我们不是输出$\mathbf{r}^T \mathbf{A} + \mathbf{e}_1^T$,而是$\lceil \mathbf{r}^T \mathbf{A} + \mathbf{e}1^T \rfloor{q \rightarrow 2^{d_u}}$。这意味着像带舍入的学习问题(见第2.5.3节)那样添加了一些额外的误差。来自$\psi_2$的系数和通过从3329压缩到大小为$2^{d_u} = 1024$的集合创建的误差的总组合误差实际上比$\psi3$稍大。所以虽然技术上区分密文与均匀字符串的难度基于$\mathcal{R}{3329,X^{256}+1}\text{-LWE}_{k,\psi2}$的难度,但在实践中,我们获得了一些额外的启发式安全性比特,问题应该与$\mathcal{R}{3329,X^{256}+1}\text{-LWE}_{k,\psi_3}$一样困难。我们为从$\psi_3$而不是$\psi_2$采样$\mathbf{s}, \mathbf{e}, \mathbf{r}$的系数从而实现这种额外启发式安全性所付出的代价是解密错误增长。

计算效率

有几个技巧可以用来显著优化图3中方案的效率。首先,不需要存储公钥部分$\mathbf{A}$,因为它是均匀随机生成的。因此可以简单地存储256比特种子$\rho$并将$\mathbf{A}$创建为$\mathcal{H}(\rho)$,其中$\mathcal{H}$是某个密码哈希函数(例如SHAKE),它可以将种子扩展为任意长度的看起来随机的字符串。因此公钥将仅由$(\rho, \mathbf{t})$组成。

如第4.6节所讨论,每当$q$的形式(引理7)允许$X^d + 1$分解为低次多项式时,NTT算法允许在形如$\mathcal{R}_{q,X^d+1}$的环中进行非常高效的乘法。Kyber中的模数(即3329)模256同余于1,因此多项式$X^{256} + 1$分解为形如$(X^2 - r_i)$的2次多项式的乘积。

❝

选择素数3329作为Kyber的原因是，不存在类似大小的素数能将多项式 $X^{256} + 1$ 分解为线性因子（即不存在素数同余于1模512）。虽然如第4.6节所述，在一个不能完全分裂的环中实现NTT乘法在实现上有些复杂，但在 $X^{256} + 1$ 分裂为线性因子或二次项之间在计算上基本没有差别。

作为记号,对于多项式$a \in \mathcal{R}_{X^{256}+1}$,让我们用$\hat{a}$表示其 NTT表示 :

$$ \hat{a} = (a \bmod X^2 - r1, \ldots, a \bmod X^2 - r{128}) $$

将$a$转换为$\hat{a}$(以及$\hat{a}$转换为$a$)需要$O(d \log d)$次运算。虽然这已经相当快,但NTT表示的存在允许我们进一步优化。

注意组成矩阵$\mathbf{A}$的多项式是随机采样的。为了有效地进行乘法$\mathbf{As}$,我们需要首先将多项式$\mathbf{A}$转换为它们的NTT表示。简单的观察是,因为多项式与其NTT表示之间存在一一对应,我们可以直接以其NTT表示随机采样$\mathbf{A}$!此外,公钥$\mathbf{t}$可以以其NTT表示存储,因此在乘法后不需要进行逆NTT。而且由于$\mathbf{t}$的NTT表示在加密算法中计算$\mathbf{r}^T \mathbf{t}$时无论如何都需要,这是双赢。

另一方面,注意我们不能直接以其NTT表示采样$\mathbf{s}, \mathbf{e}, \mathbf{r}, \mathbf{e}1$和$e$,因为它们的分布不是均匀随机的。当元素处于其NTT表示时,我们也不能执行压缩操作$\lceil \cdot \rfloor{q \rightarrow p}$。因此一些NTT计算将是必要的。尽管如此,因为矩阵$\mathbf{A}$由$k$个多项式组成,通过直接以NTT形式采样它,我们避免了执行$k^2$次NTT计算——这是非常可观的节省。

4.8 从CPA加密到CCA-KEM

密钥封装机制(KEM)允许两方交换随机消息(共享密钥)。它由三个算法组成——KEM-KeyGen、KEM-Encaps和KEM-Decaps。密钥生成算法输出私钥和公钥。封装算法接受公钥作为输入并输出共享密钥和密文。解封装算法反过来接受密文和私钥作为输入并产生与输出相同的共享密钥。CPA安全的KEM是这样的:当给定公钥和密文时,对手无法区分共享密钥与均匀分布。这样的KEM可以从任何CPA安全的公钥加密方案构造,只需加密随机消息并将其设置为共享密钥。

❝

为了实现稍微更"高级"的安全概念（这里我们不讨论），人们不仅仅输出消息作为共享密钥，而是用公钥对其进行哈希，如图4所示。在大多数密码协议中，将所有公共参数作为密码哈希函数的输入也是良好的密码学实践。

公共参数: 来自图3的CPA加密方案的公共参数

KEM-KeyGen	KEM-Encaps$(pk)$	KEM-Decaps$(sk, c, h, z)$
$(pk, sk) \leftarrow$ CPA-KeyGen	$m \leftarrow \{0,1\}^{256} \in \mathcal{R}_{X^{256}+1}$	$m' := \text{CPA-Decrypt}(sk, c)$
$pk := (\mathbf{A}, \mathbf{t}), sk := \mathbf{s}$	$(K, \rho) := \mathcal{H}(m, pk) \in \{0,1\}^{512}$	$(K', \rho') := \mathcal{H}(m', pk)$

| $c := \text{CPA-Encrypt}(pk, m, \rho)$| $c' := \text{CPA-Encrypt}(pk, m', \rho')$

| 共享密钥$:= K$, ctxt $:= c$| 如果$c \neq c'$,则$K' := \perp$

|
| 共享密钥$:= K'$

_图4: 使用Fujisaki-Okamoto变换构造的CCA安全密钥封装方案。函数$\mathcal{H}$和$\mathcal{G}$被建模为随机预言机。CPA-KeyGen、CPA-Encrypt和CPA-Decrypt算法如图3所示(尽管构造相当通用),添加到CPA-Encrypt输入的值$\rho \in \{0,1\}^{256}$表示过程中使用的随机硬币,用于生成$(\mathbf{r}, \mathbf{e}_1, e2)$。

要被认为是CCA安全的,即使当对手可以访问解封装预言机(它可以在除给定密文之外的任何东西上使用)时,共享密钥与随机的不可区分性也应该被保持。

从CPA安全的公钥加密方案到CCA安全KEM的转换遵循Fujisaki-Okamoto(FO)变换。Fujisaki-Okamoto变换背后的直觉是使解封装预言机对对手"无用",使得它产生非$\perp$输出的唯一时间是当它被给定对手已经知道消息的密文时。实现后者的方法是使构造密文中使用的随机性依赖于消息,并让解封装算法首先解密密文以获得消息,然后重新加密它,如果密文不匹配则输出$\perp$。这个通用转换在图4中呈现。

❝

这使得加密方案是确定性的，但这不会造成问题，因为我们总是在加密随机消息。

专门针对格加密的一些小修改

由于格加密的特殊性,标准化的ML-KEM(即Kyber)中对图4进行了一些修改。与离散对数方案不同,基于格的方案中的公钥相当大($\approx 1$ KB),使用NTT的代数运算与经典密码学中慢得多的幂运算或椭圆曲线乘法运算相比非常快。因此在封装和解封装函数中对公钥进行哈希实际上是一个计算上非常明显的操作,当使用AVX-2指令实现方案时,可能占运行时间的30%到50%之间。因为在许多实际场景中,解封装算法比密钥生成运行得更频繁(例如,一方的公钥可能是固定的),我们可以在KEM-KeyGen算法中预先哈希公钥为$h = \mathcal{G}(pk)$并存储它,然后在KEM-Encaps算法中使用$\mathcal{G}(pk)$作为$\mathcal{H}$的输入(这里没有节省),并在KEM-Decaps算法中使用$h$而不是$pk$。在后一个算法中,节省意味着只哈希32字节而不是$\approx 1$ KB。

Kyber KEM中的另一个变化是永远不输出$\perp$,而是在密文不匹配的情况下,输出一个随机密钥,该密钥是输入密文和密钥生成期间创建的某个随机秘密值的哈希。这样做的理由有些技术性,并且实际上并不清楚这在实践中是否增加了任何安全性。

❝

Kurt Pan: 如您喜歡，請打賞支持我！👇

讓我們一起向 付費圍牆花園 和 廣告推薦注意力經濟 宣戰，讓賽博空間重新清朗！

• 本文转载自： mp.weixin.qq.com/s/7LV5Z... , 如有侵权请联系管理员删除。