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

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

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

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

❝

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

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

2.1 一些记号

本节中的所有运算都将在环$(\mathbb{Z}_q, +, \times)$中执行,其中使用通常的整数模$q$的加法和乘法。对于集合$S$,我们写$a \leftarrow S$表示$a$从集合$S$中均匀随机选择。对于任何正整数$\beta$,我们定义集合

$$ [\beta] = {-\beta, \ldots, -1, 0, 1, \ldots, \beta}. $$

这个记号自然地扩展到向量(和矩阵),例如$[\beta]^{n \times m}$表示一个$n \times m$矩阵,其系数在$[\beta]$中。默认情况下,所有的向量都是列向量。也可以通过写$|\mathbf{v}|_{\infty} \leq \beta$来表示向量$\mathbf{v}$在$[\beta]^m$中。对于整数$x$,$\lceil x \rfloor$表示最接近$x$的整数,平局时向上取整。

当在后面的章节中使用固定次数的多项式$a = \sum_{i=0}^{d-1} a_i X^i \in \mathbb{Z}[X]$时,我们写$a \leftarrow [\beta]$表示所有整数系数$a_i$都从$[\beta]$中均匀选择。类似地,对于向量$\mathbf{a} \in \mathbb{Z}[X]^m$,$\mathbf{a} \leftarrow [\beta]^m$表示这样的分布:向量$\mathbf{a}$中的每个多项式$a_i$都按$a_i \leftarrow [\beta]$选择。有时候,我们会想要从某个分布$\psi$中采样,而不是从集合$[\beta]$中均匀采样。在这种情况下,我们类似地写$a \leftarrow \psi$或$\mathbf{a} \leftarrow \psi^m$,其中$a$是整数或多项式,$\mathbf{a}$是整数或多项式的向量。

2.2 一个启发性例子

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

1. $(\mathbf{A}, \mathbf{As})$,其中$\mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}$且$\mathbf{s} \leftarrow [\beta]^m$
2. $(\mathbf{A}, \mathbf{u})$,其中$\mathbf{A} \leftarrow \mathbb{Z}_q^n$

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

$$ \text{sk}: \mathbf{s} \leftarrow [\beta]^m, \quad \text{pk}: (\mathbf{A} \leftarrow \mathbb{Z}_q^{m \times m}, \mathbf{t} = \mathbf{As}). $$

要加密消息$\mu \in \mathbb{Z}_q$,加密者选择一个随机向量$\mathbf{r} \leftarrow [\beta]^m$并输出密文$(\mathbf{u}, v) \in \mathbb{Z}_q^m \times \mathbb{Z}_q$,其中

$$ (\mathbf{u}^T = \mathbf{r}^T \mathbf{A}, \quad v = \mathbf{r}^T \mathbf{t} + \mu) $$

要解密,只需计算

$$ \mu = v - \mathbf{u}^T \mathbf{s} $$

方案的正确性如下,因为

$$ v - \mathbf{u}^T \mathbf{s} = \mathbf{r}^T \mathbf{t} + \mu - \mathbf{r}^T \mathbf{A} \mathbf{s} = \mathbf{r}^T \mathbf{A} \mathbf{s} + \mu - \mathbf{r}^T \mathbf{A} \mathbf{s} = \mu. $$

❝

将此与EIGamal加密方案进行比较！在那里，私钥是 $s$ ，公钥是 $A, t=A^s$ 。密文是 $u=A^r, v=t^r \cdot \mu$ ，解密是 $v / u^s=A^{s r}$ ． $\mu / A^{r s}=\mu$ 。解密工作的原理完全相同，除了在我们的例子中，我们没有交换律，因此在左侧乘以向量 $\mathbf{r}^T$ ，在右侧乘以 $\mathbf{s}$ 。

方案的安全性由我们的假设和混合论证得出。根据假设,公钥$(\mathbf{A}, \mathbf{t})$与均匀分布不可区分。因此公钥矩阵$\mathbf{A}' = [\mathbf{A} \mid \mathbf{t}] \in \mathbb{Z}_q^{m \times (m+1)}$与均匀分布不可区分,再次使用我们的假设,得到分布$(\mathbf{A}', \mathbf{r}^T \mathbf{A}')$基于相同的假设(只是$n$和$m$互换了)也与均匀分布不可区分。因此,分布$(\mathbf{A}, \mathbf{t}, \mathbf{u}, v)$与均匀分布不可区分,因此该方案是CPA安全的。

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

2.3 LWE问题

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

❝

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

1. $(\mathbf{A}, \mathbf{As} + \mathbf{e})$,其中$\mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}$,$\mathbf{s} \leftarrow [\beta]^m$,$\mathbf{e} \leftarrow [\beta]^n$
2. $(\mathbf{A}, \mathbf{u})$,其中$\mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}$且$\mathbf{u} \leftarrow \mathbb{Z}_q^n$

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

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

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

❝

定义2. 对于正整数$m, n, q$和分布$\psi$, $\text{LWE}_{n,m,q,\psi}$问题要求区分以下两个分布:

1. $(\mathbf{A}, \mathbf{As} + \mathbf{e})$,其中$\mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}$,$\mathbf{s} \leftarrow \psi^m$,$\mathbf{e} \leftarrow \psi^n$
2. $(\mathbf{A}, \mathbf{u})$,其中$\mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}$且$\mathbf{u} \leftarrow \mathbb{Z}_q^n$

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

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

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

正如在前一节中已经明确的那样,区分$(\mathbf{A}, \mathbf{s}^T \mathbf{A} + \mathbf{e}^T)$与均匀分布也是LWE问题,只是$n$和$m$互换了——即$\text{LWE}_{m,n,q,\psi}$问题。类似地,通过混合论证,区分

$$ (\mathbf{A}, \mathbf{As}_1 + \mathbf{e}_1, \ldots, \mathbf{As}_t + \mathbf{e}_t, \mathbf{s}_1'^T \mathbf{A} + \mathbf{e}1'^T, \ldots, \mathbf{s}{t'}'^T \mathbf{A} + \mathbf{e}_{t'}'^T) $$

与均匀分布的难度 (区分优势最多增加$(t + t')$倍) 等同于$\text{LWE}{n,m,q,\psi}$或$\text{LWE}{m,n,q,\psi}$中较容易的那个。

2.3.1 基于LWE的加密方案

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

$$ \text{sk}: \mathbf{s} \leftarrow [\beta]^m, \quad \text{pk}: (\mathbf{A} \leftarrow \mathbb{Z}_q^{m \times m}, \mathbf{t} = \mathbf{As} + \mathbf{e}_1), \text{ 其中 } \mathbf{e}_1 \leftarrow [\beta]^m $$

要加密消息$\mu \in {0,1}$,加密者选择$\mathbf{r}, \mathbf{e}_2 \leftarrow [\beta]^m$和$e_3 \leftarrow [\beta]$,并输出

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

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

在讨论解密之前,我们先看看安全性论证,看看为什么该方案基于$\text{LWE}_{m,q,\beta}$的难度。论证与第2.2节中的相同。公钥$(\mathbf{A}, \mathbf{t})$与$\mathbb{Z}q^{m \times (m+1)}$上的均匀分布的不可区分性直接源于$\text{LWE}{m,q,\beta}$假设。将公钥$(\mathbf{A}, \mathbf{t})$重写为矩阵$\mathbf{A}' = [\mathbf{A} \mid \mathbf{t}]$,我们看到$\text{LWE}_{m,q,\beta}$假设再次意味着分布$\left(\mathbf{A}^{\prime}, \mathbf{r}^T \mathbf{A}^{\prime}+\left[\begin{array}{l}\mathbf{e}_2 \\ e3\end{array}\right]^T\right)$也与均匀分布不可区分。因此,基于$\text{LWE}{m,q,\beta}$,对于任何$\mu \in {0,1}$,$(\mathbf{A}, \mathbf{t}, \mathbf{u}, v)$与均匀分布不可区分。注意,我们使用了两次$\text{LWE}_{m,q,\beta}$假设,参数$m$在论证公钥看起来随机时作为$\mathbf{A}$的列数发挥作用,然后在论证密文看起来随机时作为$\mathbf{A}$的行数发挥作用。这直观地解释了为什么在试图最小化公钥加密中公钥和密文的组合大小时,将$\mathbf{A}$中的行数和列数设置为相等是有意义的。我们在第2.4节中进一步讨论这个话题,并在第2.5.5节中也讨论一些应用和一个稍微修改的密码系统,在这些情况下可能不想让行数等于列数。

要解密,计算$v - \mathbf{u}^T \mathbf{s}$。但是,我们不像之前那样干净地得到消息$\mu$,而是得到了

$$ \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} $$

上述方程中的$\mathbf{r}^T \mathbf{As}$项相互抵消; 然而我们留下了一些"错误"项的组合。幸运的是,所有这些错误项的系数都由$\pm \beta$限定,因此向量积$\mathbf{r}^T \mathbf{e}_1$和$\mathbf{e}_2^T \mathbf{s}$各自由$m$个大小最多为$\beta^2$的项组成。因此可以重写为$e + \frac{q}{2} \mu$,其中$e \in [2m\beta^2 + \beta]$,因此如果参数设置为$2m\beta^2 + \beta < q/4$,解密者可以通过检查前面的值是更接近0还是$q/2$来从$v - \mathbf{u}^T \mathbf{s}$确定$\mu$。

2.3.2 精确界定总错误

上面计算的值$2m\beta^2 + \beta$是错误大小的上界。由于$\mathbf{r}, \mathbf{s}, \mathbf{e}_1$和$\mathbf{e}_2$的系数是从以0为中心的范围$[\beta]$中随机选择的,误差实际上不太可能那么大。由于抵消,它实际上会更接近$\mathcal{O}(\sqrt{m} \beta^2)$。一般来说,我们可以得到误差的界,使得以非常高的概率(比如$1-2^{-150}$)误差将低于$q/4$。这意味着解密错误的概率最多为$2^{-150}$。这样小的错误在应用中以及在将这个CPA加密方案用作其他构造的组件时(例如CCA安全加密)是可以容忍的。

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

$$ \Pr_{\mathbf{s}, \mathbf{r}, \mathbf{e}_1, \mathbf{e}_2 \leftarrow [\beta]^m, e_3 \leftarrow [\beta]^2} [\mathbf{r}^T \mathbf{e}_1 + e_3 - \mathbf{e}_2^T \mathbf{s} \in [\alpha]] $$

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

$$ A(X) = \sum_{i=-\gamma}^{\gamma} Ai X^i, \quad B(X) = \sum{i=-\gamma}^{\gamma} B_i X^i $$

令

$$ C(X) = A(X) \cdot B(X) = \sum_{i=-2\gamma}^{2\gamma} C_i X^i $$

是$A(X)$和$B(X)$的乘积。现在可以在系数$C_i$和$A+B=i$的概率之间建立直接联系。特别地,

$$ \Pr[A+B=i] = C_i $$

这意味着

$$ \Pr[A+B \in [\alpha]] = \sum{i=-\alpha}^{\alpha} C\alpha $$

这直接延续到计算上述所要求的概率,注意到$\mathbf{r}^T \mathbf{e}_1 - \mathbf{e}_2^T \mathbf{s}$分布为$2m$个 独立 随机变量$A$的和,其中

$$ Ai = \Pr[A=i] = \Pr{x,y \leftarrow [\beta]}[xy=i] $$

而$e_3$只是$[\beta]$上的均匀分布随机变量。所以,例如$\beta=2$,那么

$$ A_{-4} = A4 = \frac{2}{25}, \quad A{-2} = A2 = \frac{4}{25}, \quad A{-1} = A_1 = \frac{2}{25}, \quad A_0 = \frac{9}{25} $$

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

$$ \begin{aligned} C(X) &= \left(\frac{2}{25} X^{-4} + \frac{4}{25} X^{-2} + \frac{2}{25} X^{-1} + \frac{9}{25} + \frac{2}{25} X + \frac{4}{25} X^{2} + \frac{2}{25} X^4\right)^{2m} \cdot \left(\frac{1}{5} X^{-2} + \frac{1}{5} X^{-1} + \frac{1}{5} + \frac{1}{5} X + \frac{1}{5} X^2\right) \end{aligned} $$

那么所求概率恰好是$\sum_{i=-\alpha}^{\alpha} C_i$,其中$C_i$再次是$C(X)$中与$X^i$相关的系数。通过设置$\alpha = q/4 - 1$,我们将获得第2.3.1节中的解密算法正确解密的概率。

2.4 公钥和密文大小的权衡

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

公钥由一个随机矩阵$\mathbf{A} \in \mathbb{Z}_q^{m \times m}$和一个向量$\mathbf{t} \in \mathbb{Z}_q^m$组成。由于$\mathbf{A}$是完全随机的,因此不需要存储它——如果通过选择256比特种子$\rho$然后使用某个密码学PRF(例如基于SHA-3函数的SHAKE)将$\mathbf{A}$定义为$\rho$的扩展来创建$\mathbf{A}$,那么只需要存储256比特$\rho$而不是$\mathbf{A}$的$m^2 \log q$比特。在加密和解密时需要从$\rho$扩展$\mathbf{A}$,但这样做而不是存储$\mathbf{A}$通常是值得权衡的——特别是当该方案用作密钥封装机制时,人们更愿意传输$\rho$而不是整个$\mathbf{A}$。公钥的另一部分$\mathbf{t}$依赖于私钥,因此不能以类似的方式压缩,因此总公钥大小为$256 + m \log q$比特。密文$(\mathbf{u}, v) \in \mathbb{Z}_q^m \times \mathbb{Z}_q$可以使用$(m+1) \log q$比特表示。具体的安全参数设置将需要取$m \approx 700$和$q \approx 2^{13}$,因此仅加密一个明文比特就如此庞大是有些低效的。我们现在将给出LWE加密方案的一个推广,它允许在公钥和密文大小之间进行各种权衡。当前基于LWE的加密方案具有如此大的密文扩展的原因是$\mathbf{u}$由$m \log q$比特组成。为了减少密文扩展,我们将给出该方案的一个变体,它在许多消息的加密之间分摊密文部分$\mathbf{u}$[PVW08,MR09, BCD+16]。权衡是公钥会更大。假设我们想加密$N = k\ell$比特,我们将其排列成矩阵$\mathbf{M} \in {0,1}^{k \times \ell}$。密钥生成过程现在将是

$$ \text{sk}: \mathbf{S} \leftarrow [\beta]^{m \times \ell}, \quad \text{pk}: (\mathbf{A} \leftarrow \mathbb{Z}_q^{m \times m}, \mathbf{T} = \mathbf{AS} + \mathbf{E}_1), \text{ 其中 } \mathbf{E}_1 \leftarrow [\beta]^{m \times \ell} $$

注意公钥大小现在增加到$256 + \ell m \log q$比特。加密算法类似地进行,其中加密者选择$\mathbf{R}, \mathbf{E}_2 \leftarrow [\beta]^{k \times m}$和$\mathbf{E}_3 \leftarrow [\beta]^{k \times \ell}$,并输出密文

$$ (\mathbf{U} = \mathbf{RA} + \mathbf{E}_2, \quad \mathbf{V} = \mathbf{RT} + \mathbf{E}_3 + \frac{q}{2} \mathbf{M}) $$

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

这个密码系统的安全性再次直接基于$\text{LWE}_{m,q,\beta}$。注意公钥$(\mathbf{A}, \mathbf{AS} + \mathbf{E}_1)$可以重写为$(\mathbf{A}, \mathbf{As}_1 + \mathbf{e}1, \ldots, \mathbf{As}\ell + \mathbf{e}_\ell)$,其中$\mathbf{s}_i$和$\mathbf{e}_i$分别是$\mathbf{S}$和$\mathbf{E}1$的第$i$列。那么$(\mathbf{A}, \mathbf{T})$与均匀分布的不可区分性直接由$\text{LWE}{m,q,\beta}$使用通常的混合论证得出,安全性损失$\log \ell$比特。

❝

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

写$\mathbf{A}' = [\mathbf{A} \mid \mathbf{T}]$,我们再次使用$\text{LWE}_{m,q,\beta}$假设(和混合论证)注意到分布$(\mathbf{A}', \mathbf{RA}' + [\mathbf{E}_2 \mid \mathbf{E}_3])$与均匀分布不可区分,因此

$$ (\mathbf{A}, \mathbf{T}, \mathbf{U}, \mathbf{V}) = (\mathbf{A}', \mathbf{RA}' + [\mathbf{E}_2 \mid \mathbf{E}_3 + \frac{q}{2} \mathbf{M}]) $$

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

$$ \begin{aligned} \mathbf{V} - \mathbf{US} &= \mathbf{R}(\mathbf{AS} + \mathbf{E}_1) + \mathbf{E}_3 + \frac{q}{2} \mathbf{M} - (\mathbf{RA} + \mathbf{E}_2) \mathbf{S} \ &= \mathbf{RE}_1 + \mathbf{E}_3 + \frac{q}{2} \mathbf{M} - \mathbf{E}_2 \mathbf{S} \end{aligned} $$

从上面观察,$\mathbf{V} - \mathbf{US}$的第$(i,j)$个系数等于

$$ \mathbf{r}^T \mathbf{e}_1 + e_3 + \frac{q}{2} \mu - \mathbf{e}_2^T \mathbf{s} $$

其中$\mathbf{r}^T$和$\mathbf{e}_2^T$是$\mathbf{R}$和$\mathbf{E}_2$的第$i$行,$\mathbf{e}_1$和$\mathbf{s}$是$\mathbf{E}_1$和$\mathbf{S}$的第$j$列,而$e_3$和$\mu$是$\mathbf{E}_3$和$\mathbf{M}$的第$(i,j)$个位置。由于所有向量都在$\mathbb{Z}_q^m$中,并且它们的所有系数都是从$[\beta]$中均匀选择的,我们处于与之前完全相同的情况,因此可以以与以前完全相同的方式设置参数$m, q, \beta$以具有小的解密错误。

❝

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

2.5 一些变化和优化

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

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

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

$$ \mathcal{S} = {\lceil i \cdot q / 2^\kappa \rfloor : 0 \leq i < 2^\kappa}. $$

图1: $\mathbb{Z}{13}$在圆上的点表示。如果我们定义集合$\mathcal{S}={\lfloor i \cdot 13 / 4\rfloor : 0 \leq i<4}$，那么它由四个点$0,3,7,10$组成。因此$\mathcal{S}$可以用2比特表示，并且$\mathbb{Z}{13}$中的每个点距$\mathcal{S}$的某个元素的距离都在$\lceil 13 / 8\rceil=2$以内。

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

集合$\mathcal{S}$的关键特征是每个$v \in \mathbb{Z}q$都在$\mathcal{S}$的某个元素的距离$\lceil q/2^{\kappa+1} \rfloor$之内。让我们定义$\text{HIGH}\mathcal{S}(v)$为$\mathcal{S}$中最接近$v$的元素,$\text{LOW}\mathcal{S}(v)$为$v - \text{HIGH}\mathcal{S}(v)$。然后,不是将$\mathbf{V} \in \mathbb{Z}q^{k \times \ell}$作为密文的一部分传输,可以传输$\mathbf{V}' \in \mathcal{S}^{k \times \ell} = \text{HIGH}\mathcal{S}(\mathbf{V})$。注意存在一个$\mathbf{E}' \in [\lceil q/2^{\kappa+1} \rfloor]^{k \times \ell} = \text{LOW}_\mathcal{S}(\mathbf{V})$使得$\mathbf{V} = \mathbf{V}' + \mathbf{E}'$。

如果密文$(\mathbf{U}, \mathbf{V}')$以这种方式创建,那么解密$\mathbf{V}' - \mathbf{US}$将产生

$$ \mathbf{V}' - \mathbf{US} = \mathbf{RE}_1 + \mathbf{E}_3 - \mathbf{E}' + \frac{q}{2} \mathbf{M} - \mathbf{E}_2 \mathbf{S}, $$

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

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

2.5.2 模切换/压缩/解压缩

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

❝

定义3. 对于元素$x \in \mathbb{Z}_q$和某个正整数$p$,我们定义从$\mathbb{Z}_q$到$\mathbb{Z}_p$的映射为

$$ \lceil x \rfloor_{q \rightarrow p} = \lceil \frac{xp}{q} \rfloor \in \mathbb{Z}_p $$

应该观察到,$\mathbb{Z}_p$的结果元素与$\mathbb{Z}_q$中的精确代表元素$x$无关——也就是说,集合$x + q\mathbb{Z}$中的所有元素在$\mathbb{Z}_p$中产生相同的结果(因为$\lceil \frac{(x+q\mathbb{Z})p}{q} \rfloor = \lceil \frac{xp}{q} + p\mathbb{Z} \rfloor = \lceil \frac{xp}{q} \rfloor + p\mathbb{Z}$);因此上述定义是良定义的。我们现在证明关于如何使用上述函数有意义地压缩和解压缩数据的核心引理。特别地,它指出如果首先将$\mathbb{Z}_q$中的元素压缩到$\mathbb{Z}_p$中的元素(其中$p < q$),然后解压缩回$\mathbb{Z}_q$,结果不会离原始元素太远。

❝

引理1. 对于整数$p < q$和$x \in \mathbb{Z}_q$,有

$$ \lceil \lceil x \rfloor{q \rightarrow p} \rfloor{p \rightarrow q} = x + \eta \in \mathbb{Z}_q $$

对于某个满足$|\eta| \leq \frac{q}{2p} + \frac{1}{2}$的$\eta \in \mathbb{Z}$。

证明. 根据舍入的定义,存在$\delta \in \mathbb{Q}, |\delta| \leq \frac{1}{2}$,使得对于$x \in \mathbb{Z}_q$,

$$ \lceil x \rfloor_{q \rightarrow p} = \lceil \frac{xp}{q} \rfloor = \frac{xp}{q} + \delta \in \mathbb{Z}_p $$

因此,

$$ \lceil \lceil x \rfloor{q \rightarrow p} \rfloor{p \rightarrow q} = \lceil \frac{(\frac{xp}{q} + \delta) \cdot q}{p} \rfloor = \lceil x + \frac{\delta q}{p} \rfloor = x + \frac{\delta q}{p} + \delta' \in \mathbb{Z}_q $$

对于某个$|\delta'| \leq \frac{1}{2}$(这是舍入的结果)和$\frac{\delta q}{p} \leq \frac{q}{2p}$。

为了将定义3中的模切换操作与第2.5.1节中的例子联系起来,我们将前一节中$\mathcal{S}, \kappa, \text{HIGH}\mathcal{S}, \text{LOW}\mathcal{S}$的定义与这里引入的概念联系起来。

1. $2^\kappa = p$
2. $\mathcal{S}=\left {\lceil x\rfloor_{p \rightarrow q}\right.; \left.x \in \mathbb{Z}_p\right}$
3. $\text{HIGH}\mathcal{S}(x) = \lceil \lceil x \rfloor{q \rightarrow p} \rfloor_{p \rightarrow q}$
4. $\text{LOW}\mathcal{S}(x) = x - \text{HIGH}\mathcal{S}(x)$

引理1证明了$\text{LOW}\mathcal{S}(x) \in [[q/2p]]$。在压缩的实现中,我们当然不会发送元素$\text{HIGH}\mathcal{S}(x) \in \mathbb{Z}q$,而是$\lceil x \rfloor{q \rightarrow p} \in \mathbb{Z}p$,因为后者可以更紧凑地表示。应该将$\text{HIGH}\mathcal{S}(x) \in \mathbb{Z}_q$视为$x$的压缩的解压缩。

我们还指出,从有噪声的解密输出恢复消息$m$也可以使用压缩函数来完成。特别地,对于元素$x \in \mathbb{Z}q$,$\lceil x \rfloor{q \rightarrow 2}$将映射到0(如果$x$更接近0而不是$q/2$),否则映射到1。因此可以将解密过程重写为

$$ \lceil v - \mathbf{u}^T \mathbf{s} \rfloor_{q \rightarrow 2} $$

另一个值得一提的点是,就最小化当$\mathcal{S}$固定为某个大小时所有点$\text{HIGH}\mathcal{S}$之间的距离而言,对$\mathcal{S}$的定义对于所有$p, q$都是最优的。然而,对于某些特定的$p, q$值,可以不同地定义集合$\mathcal{S}$,同时仍然实现相同的最优性。我们可能想这样做的原因是为了避免执行$\lceil x \rfloor{q \rightarrow p}$操作,该操作需要除以(通常是素数)$q$。例如,如果我们有$p=4$和$q=33$,那么我们可以定义集合$\mathcal{S} = {0, 8, 16, 24}$。注意,为这个集合计算$\text{HIGH}_\mathcal{S}(x)$只需要模8的模约简和除法,这通常是CPU中非常高效的操作,因为只需要寄存器移位。

在Kyber加密方案(第4.7节)中,由于模数$q$很小,我们无法找到一个素数既满足我们需要的最优乘法效率条件(见第4.6节),又有一个集合$\mathcal{S}$使得对它的舍入只涉及上面的好操作。因此我们使用$\mathcal{S}$的通用定义。在Dilithium签名方案(第5.7节)中,模数$q$更大,因此我们能够设置它,使得我们有一个好的$\mathcal{S}$并且仍然有快速乘法。

2.5.3 带舍入学习（LWR）

根据LWE假设,当$\mathbf{s}$和$\mathbf{e}$的系数来自$[\beta]$时,分布$(\mathbf{A}, \mathbf{t} = \mathbf{As} + \mathbf{e}) \in \mathbb{Z}_q^{n \times m} \times \mathbb{Z}_q^n$看起来与均匀分布不可区分。如果我们将$\mathbf{t}$的每个系数舍入到某个子集$\mathcal{S} \subseteq \mathbb{Z}q$中的最近点,如第2.5.1节所示,那么$(\mathbf{A}, \text{HIGH}\mathcal{S}(\mathbf{t}))$的分布仍然与$(\mathbf{A}, \text{HIGH}\mathcal{S}(\mathbf{u}))$不可区分,其中$\mathbf{u}$是均匀随机的。现在让我们检查$\mathbf{t} = \mathbf{As} + \mathbf{e}$。由于$\mathbf{e}$的系数在小子集$[\beta]$中,结果可能是它对$\text{HIGH}\mathcal{S}(\mathbf{As} + \mathbf{e})$的值没有任何影响。特别地,当$\mathcal{S}$如(18)中定义时,$\text{HIGH}\mathcal{S}(\mathbf{As} + \mathbf{e}) = \text{HIGH}\mathcal{S}(\mathbf{As})$的概率(在$\mathbf{A}, \mathbf{s}, \mathbf{e}$的随机性上)大约是$(1 - \frac{\beta|\mathcal{S}|}{2q})^n$。要看到这一点,首先注意$\text{HIGH}\mathcal{S}(\mathbf{As} + \mathbf{e}) \neq \text{HIGH}\mathcal{S}(\mathbf{As})$只能在$\mathbf{As}$在$\mathcal{S}$中两点之间的中点的$\beta$内时发生。更准确地说,如果$\mathbf{As}$的某个系数在$\mathcal{S}$中两点之间的中点的$\beta - i$内,那么$\mathbf{e}$的该系数有$i$种可能性使得$\text{HIGH}\mathcal{S}(\mathbf{As} + \mathbf{e}) \neq \text{HIGH}\mathcal{S}(\mathbf{As})$(它们是那些将使和$\mathbf{As} + \mathbf{e}$的系数穿过到中点另一侧的整数)。所以如果我们假设$\mathbf{As}$的每个系数在$\mathbb{Z}q$中是随机的,那么某个单独系数使$\text{HIGH}\mathcal{S}(\mathbf{As} + \mathbf{e}) \neq \text{HIGH}_\mathcal{S}(\mathbf{As})$的概率是

$$ \frac{2 \cdot |\mathcal{S}|}{q} \cdot \sum_{i=1}^{\beta} \frac{i}{2\beta + 1} \approx \frac{\beta \cdot |\mathcal{S}|}{2q} $$

如果我们进一步假设$\mathbf{As}$的所有系数都是独立的,我们得到所述的$\text{HIGH}\mathcal{S}(\mathbf{As} + \mathbf{e}) = \text{HIGH}\mathcal{S}(\mathbf{As})$的概率。

所以每当$q$相对于$\beta$和$|\mathcal{S}|$很大时,添加$\mathbf{e}$就没有区别,因此首先就没有理由添加它!区分分布$(\mathbf{A}, \text{HIGH}\mathcal{S}(\mathbf{As}))$与$(\mathbf{A}, \text{HIGH}\mathcal{S}(\mathbf{u}))$(对于随机$\mathbf{u}$)被称为带舍入学习(LWR)问题 ,每当添加$\mathbf{e}$不影响舍入输出时,它至少与LWE一样困难[BPR12, AKPW13, BGM+16]——也就是每当$(\mathbf{A}, \text{HIGH}\mathcal{S}(\mathbf{As})) = (\mathbf{A}, \text{HIGH}\mathcal{S}(\mathbf{As} + \mathbf{e}))$以高概率成立时。有时这个假设在密码方案的构造中使用,即使参数不允许从LWE进行归约(即$q$不够大)。在这种情况下,它是一个单独的假设,其与LWE的关系不清楚。

在目前这个时候,对LWR没有比仅仅攻击LWE更好的攻击,其中LWE噪声向量隐式地是$\mathbf{e} = -\text{LOW}\mathcal{S}(\mathbf{As})$。也就是说,我们会考虑LWE实例$(\mathbf{A}, \mathbf{As} + \mathbf{e})$,其中$\mathbf{e}$被确定性地选择为$-\text{LOW}\mathcal{S}(\mathbf{As})$。基于当前的攻击状态,重要的是要注意,即使在我们有从LWE到LWR的归约的情况下,这个隐式噪声向量实际上在范数上(远)大于我们从归约中得到的LWE噪声——所以LWR问题很可能比归约中得到的LWE问题更困难。从LWE到LWR的归约仅仅用于提供证据,表明至少对于某组参数,LWR不可能比LWE容易得多。这提供了一些证据表明LWR问题的"结构"是合理的。

做出LWR假设的优势在于,由于它不添加误差$\mathbf{e}$,它允许更小的参数。作为说明,让我们看看2.5.1节的解密过程。添加的误差$\mathbf{E}_3$是LWE假设所需的项,而误差$\mathbf{E}'$自然地由舍入产生。由于我们已经有$\mathbf{E}'$,$\mathbf{E}_3$可能是不必要的。因此在LWR假设下,舍入执行两个功能——它添加类似均匀的误差向量并减少密文大小。类似地,不是向密文$\mathbf{U}$添加误差,我们可以简单地将其舍入到某个(不同的)集合$\mathcal{S}$,这具有向$\mathbf{U}$添加确定性误差的效果——从而使$\mathbf{E}_2$项可能是冗余和不必要的。

2.5.4 每个槽加密更多比特

我们的加密方案将$N$比特消息打包到矩阵$\mathbf{M} \in {0,1}^{k \times \ell}$中。例如,我们本可以将其打包到矩阵

$$ \mathbf{M} \in {0, 1, \ldots, 2^b - 1}^{(k/\sqrt{b}) \times (\ell/\sqrt{b})} $$

中。为了使解密成功,我们需要对加密和解密算法进行两个小改动,同时调整参数。我们将用$\frac{q}{2^b} \mathbf{M}$替换加密算法中的$\frac{q}{2} \mathbf{M}$项。计算$\mathbf{V} - \mathbf{US}$的解密算法部分将导致$\frac{q}{2}$项类似地被$\frac{q}{2^b}$替换。这意味着为了使解密产生正确结果,需要将剩余的错误项(即不涉及$\mathbf{M}$的项)控制在$[q/2^{b+1}]$中,而不是像以前那样在$[q/4]$中。

为了使解密再次工作,参数的简单修改将涉及简单地将$q$增加大约$2^{b-1}$倍。注意这可能对密文和公钥的大小产生积极影响。之前公钥的大小是$256 + \ell m \log q$比特。例如,如果我们将$q$增加$2^{b-1}$倍,但将$\ell$减少2倍,那么大小将变成$256 + \frac{\ell m}{2}(\log q + b - 1)$比特。如果$b - 1 < \log q$,这将更小。但是在保持其他一切不变的情况下增加$q$会降低安全性(如第2.3节开头所述,随着比率$\beta/q$的增长,问题变得更困难),因此我们需要增加$\beta$或增加$m$。实现最优参数的方法是尝试一些可能的选项,或者更好的是,编写一个为你做这件事的脚本。

2.5.5 具有"非方阵"公钥的LWE加密

在我们迄今为止提出的所有公钥加密版本中,安全证明都是使用LWE假设来论证公钥在计算上与均匀分布不可区分,然后使用公钥的均匀性和LWE假设再次论证密文在计算上与均匀分布不可区分。然而,有时让公钥真正均匀是有用的。或者类似地,在公钥是均匀的(计算)假设下让密文真正均匀。换句话说,对于某些应用,我们可能只想应用一次LWE假设。我们现在将解释如何构造这样的密码系统,并给出一些关于这在实践中何时可能真正有用的直觉。

为了使公钥或密文均匀,我们需要使用剩余哈希引理（Leftover Hash Lemma）[IZ89, IN96]。该引理应用于我们的场景大致表明,如果$\mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}$(其中$q$是素数)和$\mathbf{s} \leftarrow [\beta]^m$,其中$(2\beta + 1)^m \gg q^n$,那么$(\mathbf{A}, \mathbf{As})$的分布在统计上接近于$(\mathbf{A}, \mathbf{u})$的分布,其中$\mathbf{u} \leftarrow \mathbb{Z}_q^n$。换句话说,如果$\mathbf{s}$从某个集合中均匀选择,那么这个集合的大小应该大于函数$\mathbf{As}$的值域的大小。有了剩余哈希引理,很容易看出如何修改密钥生成或加密过程,以确保公钥或密文是随机的。

如果我们希望公钥是均匀随机的,我们将密钥生成替换为

$$ \text{sk}: \mathbf{S} \leftarrow [\beta']^{m \times \ell}, \quad \text{pk}: (\mathbf{A} \leftarrow \mathbb{Z}_q^{n \times m}, \mathbf{T} = \mathbf{AS}), \text{ 其中 } (2\beta' + 1)^m > q^n $$

注意,由于我们不使用LWE假设两次,不再有理由让密钥生成中的$\beta$与加密中的相同——所以我们给它们不同的名称。加密和解密方程可以保持与之前完全相同。当设置参数以确保解密返回正确答案时,应该注意这样的事实:由于$m$和/或$\beta'$比以前更大,项$\mathbf{E}_2 \mathbf{S}$更大,还应该注意这样的事实:项$\mathbf{RE}_1$是0,因为密钥生成过程中不存在$\mathbf{E}_1$。

我们希望密文在(应用LWE假设以得出的公钥与随机不可区分之后)是均匀随机的场景所需的必要修改使用完全相同的原理。特别地,$\mathbf{A}$的维度和$\mathbf{R}$的分布应该使得$([\mathbf{A} \mid \mathbf{T}], \mathbf{R}[\mathbf{A} \mid \mathbf{T}])$(其中$[\mathbf{A} \mid \mathbf{T}] \leftarrow \mathbb{Z}_q^{n \times m}$)与$([\mathbf{A} \mid \mathbf{T}], [\mathbf{U} \mid \mathbf{V}])$不可区分,其中$\mathbf{U}, \mathbf{V}$是均匀的。

不会进一步详细讨论细节,现在将触及为什么想要公钥或密文真正均匀。我们提供的两个例子绝非详尽无遗,但说明了在哪里以及为什么牺牲一些效率可能是必需的。均匀公钥的主要应用是在基于格的身份基加密构造[GPV08]中。在这种情况下,身份为$x \in {0,1}^$的用户的公钥是$(\mathbf{A}, \mathbf{t}_x)$,其中$\mathbf{t}_x = \mathcal{H}(x)$,对于将${0,1}^$映射到$\mathbb{Z}_q^n$的密码哈希函数$\mathcal{H}$(建模为随机预言机)。换句话说,$\mathbf{A}$对所有用户都是通用的,而$\mathbf{t}_x$对每个用户都是唯一的并且是均匀随机的。在IBE方案中,用户$x$的公钥应该可以由任何人计算。因此不可能从某些秘密信息(例如私钥)生成它。另一方面,需要存在一种方法将私钥与公钥关联。这个问题的解决方案是主权威机构拥有$\mathbf{A}$的"陷门",这允许他创建满足$\mathbf{As}_x = \mathbf{t}_x$的低范数向量$\mathbf{s}_x$。这个$\mathbf{s}_x$然后是用户$x$的私密解密密钥。有趣的是,注意密钥生成 不像 之前那样完成——特别是,私钥是在公钥 之后 创建的。这只有在主权威机构创建$\mathbf{A}$时带有陷门才可能。尽管密钥创建顺序的这种差异,[GPV08]的主要结果提供了算法,使得$\mathbf{A}, \mathbf{s}, \mathbf{t}$的分布将是相同的,无论是在计算$\mathbf{t}$之前选择$\mathbf{s}$还是反过来。

想要密文均匀随机的应用出现在有关于密文随机性$\mathbf{r}$的某些信息可能泄漏的情况下。在[AGV09]中观察到,可以泄漏关于$\mathbf{r}$的某些信息,根据剩余哈希引理,密文仍将保持均匀随机,因为$\mathbf{r}$中仍有足够的熵。

2.5.6 对私钥和错误使用不同的分布

对公钥加密方案的另一个可能的优化是从不同的分布中选择私钥多项式$\mathbf{s}, \mathbf{e}_1, \mathbf{e}_2, \mathbf{r}$的系数[ZYF+20]。特别地,选择$\mathbf{r}, \mathbf{s} \leftarrow \psi_1$和$\mathbf{e}_1, \mathbf{e}_2 \leftarrow \psi_2$(其中$\psi_1 \neq \psi_2$)可能是有益的。以这种方式分割事物的直觉如下。基于当前已知的最佳算法,区分$(\mathbf{A}, \mathbf{As} + \mathbf{e}_1)$与均匀分布的难度取决于向量$(\mathbf{s}, \mathbf{e}_1)$的范数(见第3.3节)。因此我们可能想要策略性地在$\mathbf{s}$和$\mathbf{e}_1$之间分配$(\mathbf{s}, \mathbf{e}_1)$的总固定范数。注意这不再是本节中定义的LWE问题,但它也许也是一个合理的假设。

要了解为什么我们可能想要使$\mathbf{s}$和$\mathbf{e}_1$的范数不同,可以看看解密过程获得的错误。要正确解密,我们希望

$$ \mathbf{r}^T \mathbf{e}_1 + \mathbf{e}_2^T \mathbf{s} $$

尽可能小——这个值越小,我们可以设置的模数$q$就越小,这既会使LWE问题更困难,又会减少公钥大小。为了说明直觉,假设所有向量都从$\mathcal{N}_\sigma$中选择——标准差为$\sigma$的以0为中心的正态分布。

❝

让我们忽略这个分布是连续的而非离散的这一事实。如果我们以某种自然的方式将分布离散化，同样的直觉仍然适用。

如果$n$维向量$\mathbf{v}$从$\mathcal{N}\sigma$中选择,那么已知$|\mathbf{v}|$紧密集中在$\sigma \cdot \sqrt{n}$附近。此外,还已知向量$\mathbf{s} \leftarrow \mathcal{N}\sigma^n$和向量$\mathbf{v} \in \mathbb{R}^n$的内积根据分布$\mathcal{N}{\sigma \cdot |\mathbf{v}|}$分布。使用上述两个事实,我们可以得出,如果$\mathbf{s}, \mathbf{r} \leftarrow \mathcal{N}{\sigma_1}$和$\mathbf{e}_1, \mathbf{e}2 \leftarrow \mathcal{N}{\sigma2}$,那么上式(大致)根据分布$\mathcal{N}{\sigma_1 \sigma_2 \cdot \sqrt{2n}}$分布。此外,还已知向量$(\mathbf{s}, \mathbf{e}_1)$和$(\mathbf{r}, \mathbf{e}_2)$的范数大约是$\sqrt{\sigma_1^2 + \sigma_2^2} \cdot \sqrt{n}$。

我们现在可以看到,如果在一种情况下$\sigma_1 = \sigma_2 = \sigma$,那么

$$ |(\mathbf{s}, \mathbf{e}_1)| = |(\mathbf{r}, \mathbf{e}2)| \approx \sigma \cdot \sqrt{2n}, \text{ 且 } 上式 \sim \mathcal{N}{\sigma^2 \cdot \sqrt{2n}}. $$

另一方面,如果我们取$\sigma_1 = \frac{4}{3} \sigma$和$\sigma_2 = \frac{\sqrt{2}}{3} \sigma$,那么我们将有

$$ |(\mathbf{s}, \mathbf{e}_1)| = |(\mathbf{r}, \mathbf{e}2)| \approx \sigma \cdot \sqrt{2n}, \text{ 且 } 上式 \sim \mathcal{N}{\frac{4\sqrt{2}}{9} \cdot \sigma^2 \cdot \sqrt{2n}} $$

所以在两种情况下,$(\mathbf{s}, \mathbf{e}_1)$和$(\mathbf{r}, \mathbf{e}_2)$的$\ell_2$范数是相同的,但在第二种情况下,上式的分布具有较小的标准差,这意味着对于$\sigma_1 \neq \sigma_2$的情况,上式中的误差更小。是否应该确实尝试设置$\sigma_1 \neq \sigma_2$取决于人们对两个LWE问题(一个如定义2中,一个是$\mathbf{s}, \mathbf{e}$具有不同分布)的难度是等价的信念。

2.6 非交互式密钥交换(NIKE)

本节中描述的加密方案可以很容易地转换为被动安全的密钥传输 方案,其中双方希望就共享的对称密钥(例如AES密钥)达成一致。该协议将简单地涉及第一方创建公钥并将其发送给第二方。然后第二方选择AES密钥并将其作为消息$\mathbf{M}$加密,并发送密文。然后第一方解密共享密钥$\mathbf{M}$。

虽然上述协议对于使用经典密钥交换(例如Diffie-Hellman)的大多数目的来说已经足够好,但协议流程有一个关键顺序。发送$\mathbf{M}$的用户不能在接收到公钥之前发送他的消息。另一方面,在经典的Diffie-Hellman协议中,任一用户都可以首先发送他的$g^{x_i}$。可以类似地从LWE问题创建具有这种性质的协议,但这将是一种效率低得多的密钥交换方式,当不需要这种任意流程性质时。

我们将描述这个简单协议用于就一个随机比特达成一致的情况。要就更多比特达成一致,将应用与第2.4节中相同的思想。有一个公共随机矩阵$\mathbf{A} \in \mathbb{Z}_q^{m \times m}$,它被每个人信任为已经诚实生成(例如,它由SHAKE从种子0扩展而来)。方$i \in {1,2}$选择向量$\mathbf{s}_i, \mathbf{e}_i \leftarrow [\beta]^m$。第一方发送$\mathbf{u}_1^T = \mathbf{s}_1^T \mathbf{A} + \mathbf{e}_1^T$,而第二方发送$\mathbf{u}_2 = \mathbf{As}_2 + \mathbf{e}_2$。在收到第二方的消息后,第一方计算$\mathbf{s}_1^T \mathbf{u}_2$,如果这个值更接近$q/2$而不是0(即它在$q/4$和$3q/4$之间),它将设置共享比特$b_1 = 1$(否则将设置$b_1 = 0$)。第二方计算$\mathbf{u}_1^T \mathbf{s}_2$并使用相同规则设置$b_2 = 0$或1。简而言之,他们最终得到

$$ \begin{aligned} \mathbf{s}_1^T \mathbf{u}_2 &= \mathbf{s}_1^T \mathbf{As}_2 + \mathbf{s}_1^T \mathbf{e}_2 \ \mathbf{u}_1^T \mathbf{s}_2 &= \mathbf{s}_1^T \mathbf{As}_2 + \mathbf{e}_1^T \mathbf{s}_2. \end{aligned} $$

并希望错误项$\mathbf{s}_1^T \mathbf{e}_2$和$\mathbf{e}_1^T \mathbf{s}_2$(其最大幅度为$m\beta^2$)不会导致$b_1 \neq b_2$。

注意$b_1 \neq b_2$的概率至多是$\mathbf{s}_1^T \mathbf{As}_2$落入$3q/4$和$q/4$附近的"危险"范围的概率。特别地,

$$ \Pr[b_1 \neq b_2] < \Pr[\mathbf{s}_1^T \mathbf{As}_2 \in [\frac{3q}{4} + m\beta^2, \frac{3q}{4} - m\beta^2] \text{ 或 } [\frac{q}{4} + m\beta^2, \frac{q}{4} - m\beta^2]] $$

$\mathbf{s}_1^T \mathbf{As}_2$是$\mathbb{Z}_q$中任何特定值的概率是$1/q$,因此上述概率至多为$4m\beta^2/q$。在实践中,将使用第2.3.2节中的技术来降低这个概率,但仍会以$\Omega(\beta^2 \sqrt{m}/q)$的概率得到$b_1$和$b_2$之间的不匹配。这与我们在加密方案中的情况非常不同,在加密方案中我们可以设置参数使得解密错误相对于$q$是指数小的(甚至是0)。在非交互式密钥协商中,获得可忽略小的错误将需要将$q$设置得非常大,这对通信大小有不利影响(参见[GdKQ+24],其中详细讨论了具体细节)。实际上,有技术原因说明为什么这种低效率对于以"自然方式"使用LWE进行非交互式密钥交换可能是固有的[GKRS22]。

• https://www.usenix.org/system/files/usenixsecurity24-gajland.pdf
• https://eprint.iacr.org/2020/1555.pdf

❝

如您喜歡，請打賞支持我👇

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

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