BFV/BGV全同态加密方案浅析

本文主要为翻译内容,原文地址:Introduction to the BFV encryption scheme、https://www.inferati.com/blog/fhe-schemes-bgv

之前的一篇博客我们翻译了CKKS全同态加密方案的内容,但该篇上下文中有一些知识要点,作者在BFV/BGV中已经做了讲解,所以做了省略;为了补齐这部分知识,我们今天将这两篇的内容结合到一篇进行更全面的阐述。

BGV和BFV是“算术FHE”系列中的两种方案。自2011年/2012年首次发表以来的十年里,BGV和BFV已经进行了调整和重新分析,并被确定为基本上是等效的,其在实现、效率和噪声传播方面存在细微差异,因不同参数选择而异。并且方案的许多高级技巧也被用于CKKS。

1、介绍

        Fan-Vercauteren(FV)方案[Bra12, FV12](也称为 Brakerski-Fan-Vercauteren(BFV)方案)被认为是第二代全同态加密(FHE)方案之一,它是基于带错误学习环(RLWE)问题构建的[LPR13]。BrakerskiGentry-Vaikuntanathan (BGV) [BGV14] 方案是另一种基于错误环学习的密码系统,可提供对加密数据的计算。BGV 和 BFV 提供相同的功能,即对整型消息进行精确计算,但是它们的构造存在一些差异。

        BFV 在两个环上实例化:明文环,包括未加密或可理解消息的编码;密文环,包括加密消息。与任何其他全同态加密方案类似,BFV 允许不可信方在无法访问解密密钥的情况下对加密数据进行有意义的计算。这是由于同态属性使得在明文和密文空间之间存在一个映射(或函数),该映射保留了这两个空间中的运算。

        BGV 与 BFV 方案类似,也定义了明文环和密文环。加密过程将明文环中的输入明文元素映射到密文环中的密文元素。广义地讲,加密是通过使用几乎随机的掩码隐藏明文消息来实现的,该掩码是使用公钥(或对称密钥操作模式下的私钥)计算得出的。加密的输出通常是密文空间的两个元素;第一个元素包含被掩码的明文数据,而第二个元素包含可在解密过程中使用的辅助信息。解密使用私钥和密文中的辅助信息来移除掩码并恢复明文消息。对于熟悉 ElGamal 加密(将单个明文元素映射到成对密文元素)的读者来说,这可能听起来很熟悉。

        在基于环上带误差学习的全同态加密方案中,一个关键概念是误差,也称为噪声,它在加密过程中被添加到明文消息中。该误差对于满足RLWE困难性假设至关重要,否则RLWE将变成一个可以由商用计算机解决的简单计算问题,其结果是,基于此类简单问题构建的全同态方案将容易被攻破。同时当我们执行同态计算(主要是同态加法和同态乘法)时,误差幅度会增大。且同态乘法产生的误差增长速度比同态加法产生的误差增长速度比快。

        到目前为止,我们讨论了BFV和BGV之间的相似之处。在接下来的段落中,我们将描述这两种方案的不同之处。首先,BFV方案通常是尺度不变(或尺度无关)的,也就是说,在同态计算过程中密文模数不会改变。另一方面,BGV是一种尺度相关的方案,它定义了多个密文模数,每个层级有一个模数。正如我们在图1中看到的,BGV定义了一系列“小”模数链Q = \{p_0, p_1, \ldots, p_L\}。每个层级0\leq l\leq L相关联的,是一个密文大模数 q_l。请注意,小模数 p_l 的选择以及大模数 q_l 的集合不是任意的,其背后的原理将在本文后面阐述。在执行同态计算时,密文不断从一个层级移动到另一个层级。密文的典型流程如下:一个新加密的密文从层级 L 开始,我们将其称为用于演示的加密层级。当我们对密文进行计算时,它从较高层级 l 移动到较低层级 l-1。最终,在解密之前,密文处于层级1。应该指出的是,上述向下受限的流程是BGV分层版本中的典型流程。在可自举的 BGV 中,密文可以根据需要在两个方向(向上或向下)移动。

图1. 尺度相关的BGV密文模数

        我们注意到,前面关于加密和解密具有固定层级的描述是相当简化的,因为在0\leq l\leq L的任何层级进行加密或解密都是可能的。还应当指出的是,BFV方案也可以实例化为尺度相关的方案,这使得这两种方案之间的这种差异存在争议。

        BFV和BGV之间另一个争议较小的区别在于密文结构以及明文消息的加密方式。图2展示了BFV和BGV的密文结构。在BFV中,明文消息被放置在密文系数的最高有效位(MSB)一侧。这是通过在加密过程中用相当大的值 \Delta = \left\lfloor\frac{q}{t}\right\rfloor对消息进行缩放来实现的。另一方面,BGV将消息放置在密文系数的最低有效位(LSB)一侧。重要的是,在同态计算过程中,明文和噪声永远不会重叠,以便解密能够恢复预期的计算结果。

图 2. BFV 和 BGV 中的密文结构
MSB 代表最高有效位,q 是密文模数,t 是明文模数。摘自 [CKKS17]

2、明文空间和密文空间

        BFV中的明文和密文空间是在两个不同的多项式环上定义的,分别记为P = R_{t}=\mathbb{Z}_{t}[x] /(x^{n}+1)C = R_{q} \times R_{q},其中R_{q}=\mathbb{Z}_{q}[x] /(x^{n}+1)n \in \mathbb{Z}是环的维度, t \in \mathbb{Z}以及q \in \mathbb{Z}分别是明文和密文的系数模数。记号\mathbb{Z}_{a}[x] /(x^{n}+1)可以看作是整数系数模 a(x^{n}+1)的多项式集合,即系数在\{\left \lceil -\frac{a}{2} \right \rceil, \cdots,\left\lfloor\frac{a - 1}{2}\right\rfloor \}中且次数小于 n。出于效率考虑,n通常设置为2的幂次方整数。注意,在实际应用中, q通常远大于t,因此, C的基数远大于P的基数,这也意味着P中的一个明文消息M可以映射到C中的多个有效密文。 R_{t}R_{q}中的阶(或不同元素的数量)分别为 t^{n}q^{n}

表1展示了参数n = 4和t = 5时的有效明文消息示例。

        BGV的明文和密文空间与BFV中的类似。明文多项式环定义为P = R_{t}=\mathbb{Z}_{t}[x] /(x^{n}+1),即次数小于n且系数在\mathbb{Z}_t中的多项式集合,其中明文模数t和环维度n均为整数。密文多项式环定义为C = R_{q_l}\times ×R_{q_l},其中R_{q_l}=\mathbb{Z}_{q_l}[x]/(x^n + 1)q_l\in\mathbb{Z}是 l 层的密文模数。出于效率考虑,n通常像我们在BFV讨论中那样被设置为2的幂整数。此外, q通常远大于t,这会影响加密后的消息扩展率。

        BFV的明文空间为R_t密文格式为 (a,as+e+\Delta m), \Delta = \lfloor\frac{q}{t}\rfloorBGV的明文空间为R_t密文格式为(a,as+te+m)

3、参数

        我们在此描述BFV中使用的主要参数。除了在第3节中介绍的明文和密文空间参数(t, q, n)之外,BFV还使用了一些随机分布: R_{2}\chiR_{q}【随机分布可参考《CKKS全同态加密方案浅析》关于参数的介绍】。

        我们注意到参数(t, q, n)的选择是特定于应用场景的,并且也由所需的安全级别驱动。对于一组当前被接受的参数,我们建议读者参考同态加密标准[ACC^{+}_{18}]中的表1和表2。

[ACC^{+}_{18}]: https://homomorphicencryption.org/wp-content/uploads/2018/11/HomomorphicEncryptionStandardv1.1.pdf

4、编码和解码

        BFV和BGV在编码上类似回想一下,明文空间是多项式环R_{t}。这意味着消息需要被转换为R_{t}中的多项式。这种转换被称为编码。文献中包含了许多为全同态加密提出的编码方案。我们在这里回顾两种针对整数数据类型的简单方案。

        设 m 表示我们想要在全同态加密中加密的一个整数消息。第一种编码方案(我们称之为朴素编码方案)将明文元素构造为:M = m + 0x + 0x^{2} + \cdots + 0x^{n - 1}。也就是说,我们将 M 设置为一个常数多项式,其中 m 为常数项。虽然这种编码方案原则上很简单,但特别是对于大消息 m 来说效率极低。原因是在对密文执行同态运算时,明文系数的大小会增大。为了确保同态求值的结果与感兴趣计算的预期结果相匹配,我们需要确保明文系数不会超出t^{2}的范围。因此,我们需要确保t比要在全同态中实现的计算的输入、任何中间结果和输出都足够大。朴素编码方案呈现出系数快速增长的情况。我们注意到这种编码方案存在一个更严重的局限性,即浪费了明文多项式中的 n - 1 个系数。这种方案的解码通过简单读取解密后得到的明文多项式的常数项来实现。其他更高效的编码方案会利用一个子集甚至所有系数,称为打包或批量编码方案

        我们要介绍的另一种编码方案,称为整数编码方案,其工作方式如下:

  1. 用二进制表示m,即m = a_{n - 1}\cdots a_{2}a_{1}a_{0}

  2. 构造M = a_{n - 1}x + \cdots + a_{2}x^{2} + a_{1}x + a_{0}。由于在实际中n太大,未使用的位被设置为0。

        由于明文系数的量级较小,在同态求值过程中系数的增长通常较慢。请注意,使用这种编码进行同态求值可能会导致明文多项式的次数增加。为了确保同态求值的结果与感兴趣的计算的预期结果相匹配,我们需要确保明文系数的次数不会超出 n 的范围,并且系数不会超出 t 的范围。

        注意,对于整数编码方案,可以选择除2以外的任何整数分解基数,例如三进制、四进制或k进制基数分解。整数编码方案的解码通过在k处计算明文多项式来实现,即计算M(k)

5、密钥生成

私钥SK是从R_{2}中生成的一个随机三元多项式,它是一个次数为 n 且系数在 {-1、0、+1}中的多项式。

BFV的公钥 PK 是一对多项式(PK_{1}, PK_{2}),计算如下:PK_{1}=[-1(a \cdot SK + e)]_{q}PK_{2}=a,其中 a 是R_{q} 中的随机多项式,e是从 \chi 中随机抽样的误差多项式。

符号[\cdot]_{q}意味着多项式算术应该在模 q 下进行。请注意,由于PK_2 在 \mathbb{R}_{q}  中,多项式算术也应该在环多项式模(x^{n}+1)下进行。

BGV的公钥PK也是一对多项式(PK_{1}, PK_{2}),计算如下: PK_{1}=[-1(a\cdot SK+t\cdot e)]_{q_{L}}PK_{2}=a,其中 a 是 R_{q_{l}} 中的随机多项式,e是从\chi中采样的随机误差多项式。

符号[\cdot]q_{l} 表示多项式模 q_{l} 下进行计算。请注意,与BFV中的密钥生成不同,这里的误差是由 t 缩放的

6、加密和解密

        首先我们来介绍下BFV的加解密过程:

        在 P 中加密明文消息 M,首先生成三个小的随机多项式,从 R_{2} 生成 \mu,从 \chi 生成 e_{1} 和 e_{2},然后返回密文 C=(C_{1},C_{2}) 如下:

C_{1}=[PK_{1}\cdot u + e_{1}+\Delta M]_{q},\ C_{2}=[PK_{2}\cdot u + e_{2}]_{q}     (1)

参数\Delta被定义为 q 除以 t 的商,即 \Delta=\left\lfloor\frac{q}{t}\right\rfloor。它用于缩放消息。

        解密是通过在密钥上对密文进行评估来执行的,如下所示,并反转加密中应用的缩放因子:

M=\left[\left\lfloor\frac{t\left[C_{1}+C_{2} \cdot SK\right]_{q}}{q}\right\rceil\right]_{t}     (2)

        为了检查解密为何起作用以及在哪些条件下起作用,让我们将等式(2)展开如下:

\begin{aligned} C_{1}+C_{2} \cdot SK & =PK_{1} \cdot u+e_{1}+\Delta M+\left(PK_{2} \cdot u+e_{2}\right) \cdot SK \\ & =-(a \cdot SK+e) \cdot u+e_{1}+\Delta M+a \cdot u \cdot SK+e_{2} \cdot SK \\ & =-a \cdot u \cdot SK-e \cdot u+e_{1}+\Delta M+a \cdot u-s K+e_{2} \cdot SK \\ & =\Delta M-e \cdot u+e_{1}+e_{2} \cdot SK \\ & =\Delta M+v\end{aligned}     (3)

        需要注意的是,v 的无穷范数(即多项式 v 中最大的绝对系数,用 \|v\|表示)非常小,因为 e, e_1, e_2 和 SK 都是小多项式。更具体地说,鉴于这些小多项式都受参数 \beta 的限制,可以很容易地证明 \|v\| \leqslant n\beta^{2}+\beta + n\beta^{2}=2n\beta^{2}+\beta

        为了继续进行证明,我们需要展开模 q 下的等式(3)并完成对解密函数的求值。可以如下进行:

C_1 + C_2\cdot SK=\Delta M + v + q\cdot r     (4)

        其中 r 是某个多项式。将等式(4)乘以 \frac{t}{q} 得到 M+\frac{t}{q}\cdot v+t\cdot r。解密中的取整函数去除 \frac{t}{q}\cdot v,最后的模 t 运算去除 t\cdot r并恢复 M。简而言之,为了使解密正确地恢复 M,我们需要确保 \frac{t}{q}\cdot\|v\|<\frac{1}{2},否则噪声将会溢出并破坏消息。

        接下来我们介绍BGV的加解密过程,整体类似,会一些小差异:

        加密算法将明文消息M和公钥PK作为输入,并输出密文 C=(C_{1},C_{2}),从而对输入消息进行加密。加密过程如下:我们生成三个小的随机多项式,从 R_{2} 生成 \mu,从 \chi 生成 e_{1} 和 e_{2},并计算:

C_1 = [PK_1\cdot u + t\cdot e_1 + M]_{q_l}; \ C_2 = [PK_2\cdot u + t\cdot e_2]_{q_l}     (5)

        注意 C_1 中的误差多项式是如何被明文模数 t 缩放的。这与我们之前在图2中展示的情况一致,即消息位于密文系数的低位,而噪声可以在高位增长。

        解密过程通过将密文和私钥 SK 作为输入来逆转加密过程。如果在计算过程中噪声没有增长到无法控制的程度,它将输出明文消息 M。解密过程如下:

M=\left[\left[C_{1}+C_{2} \cdot SK\right]_{q_{I}}\right]_{t}     (6)

        为了检查解密为何起作用以及在哪些条件下起作用,让我们将等式(5) 展开如下:

\begin{aligned} C_{1}+C_{2} \cdot SK & =PK_{1} \cdot u+t \cdot e_{1}+M+\left(PK_{2} \cdot u+t \cdot e_{2}\right) \cdot SK \\ & =-(a \cdot SK+t \cdot e) \cdot u+t \cdot e_{1}+M+a \cdot u \cdot SK+t \cdot e_{2} \cdot SK \\ & =\_-a-t \cdot e \cdot u+t \cdot e_{1}+M+a \cdot u \cdot sK+t \cdot e_{2} \cdot SK \\ & =M-t \cdot e \cdot u+t \cdot e_{1}+t \cdot e_{2} \cdot SK \\ & =M+t \cdot v \end{aligned}     (7)

        通过将上述结果对 t 取模,我们去除了噪声向量 v 并恢复出没有噪声的 M。但这里有一个与v的范数相关的注意事项。只要 \|v\|_{\infty}<\frac{q_{l}}{2t},解密就有效,其中\|v\|_{\infty} 定义为v中最大的绝对系数。设置这个边界是为了使噪声的幅度不会增长过多而破坏消息。

7、同态计算

        在本节中,我们将解释BFV和BGV在同态计算求值过程中是如何工作的。在这里,我们研究两个主要的同态操作:加法和乘法。

BFV的同态加法

        让我们以同态加法为参考来理解同态加法是如何工作的。这个过程非常简单,我们只需将每个密文中相应的多项式相加,如等式(8)所示:

EvalAdd(C^{(1)}, C^{(2)}) \\=([C_{1}^{(1)} + C_{1}^{(2)}]_{q},[C_{2}^{(1)} + C_{2}^{(2)}]_{q})=(C_{1}^{(3)}, C_{2}^{(3)})=C^{(3)}     (8)

        为了理解为什么这样可行,让我们将等式(8)进行如下拆解:假设 C^{(1)}C^{(2)} 分别是对 M^{(1)} 和 M^{(2)} 的新的加密结果。从代数角度来看,它们可以如下表示,参见等式(1)

\begin{aligned} C^{(1)}=\left(\left[PK_{1} \cdot u^{(1)}+e_{1}^{(1)}+\Delta M^{(1)}\right]_{q},\left[PK_{2} \cdot u^{(1)}+e_{2}^{(1)}\right]_{q}\right) \\ C^{(2)}=\left(\left[PK_{1} \cdot u^{(2)}+e_{1}^{(2)}+\Delta M^{(2)}\right]_{q},\left[PK_{2} \cdot u^{(2)}+e_{2}^{(2)}\right]_{q}\right) \end{aligned}     (9)

        通过将方程(8)中的 C^{(1)}C^{(2)} 进行代入,我们得到以下结果:

\begin{aligned} C^{(3)}=&(C_{1}^{(3)},C_{2}^{(3)})\\=&([PK_{1}\cdot(u^{(1)}+u^{(2)})+(e_{1}^{(1)}+e_{1}^{(2)})+\Delta(M^{(1)}+M^{(2)})]_{q},\\&[PK_{2}\cdot(u^{(1)}+u^{(2)})+(e_{2}^{(1)}+e_{2}^{(2)})]_{q})\\=&([PK_{1}\cdot u^{(3)}+e_{1}^{(3)}+\Delta(M^{(1)}+M^{(2)})]_{q},[PK_{2}\cdot u^{(3)}+e_{2}^{(3)}]_{q})\end{aligned}     (10)

        很容易注意到,等式(10)具有对 M^{(3)} = M^{(1)} + M^{(2)} 进行加密的有效密文形式。请注意,在最坏情况分析下, C^{(3)} 中的误差项大约是输入密文中噪声项的总和,即噪声是累加增长的。可以遵循上述用于推导 EvalAddPlain 表达式的过程。明文消息可以通过加密转换为密文形式,且没有误差项,即 e_1 = e_2 = 0

BFV的同态乘法

        同态乘法比同态加法更复杂。我们在此介绍基本过程,并请读者参考外部资源以获取更多详细信息。

        将密文写成在私钥SK 处的求值形式是有用的,参考公式(4),就像我们在推导解密过程中所做的那样:

C^{(1)}(SK)=\Delta M^{(1)}+v_{1}+q\cdot r_{1}C^{(2)}(SK)=\Delta M^{(2)}+v_{2}+q\cdot r_{2}    (11)

将密文相乘会得到:

\begin{aligned} \left(C^{(1)} \cdot C^{(2)}\right)(SK)= & \Delta^{2} M^{(1)} \cdot M^{(2)}+\Delta\left(M^{(1)} \cdot v_{2}+M^{(2)} \cdot v_{1}\right)+ \\ & q\left(v_{1} \cdot r_{2}+v_{2} \cdot r_{1}\right)+q \cdot \Delta\left(M^{(1)} \cdot r_{2}+M^{(2)} \cdot r_{1}\right)+ \\ & v_{1} \cdot v_{2}+q^{2} \cdot r_{1} \cdot r_{2} \end{aligned}    (12)

        密文看起来接近我们想要的加密形式 \Delta\cdot[M^{(1)} \cdot M^{(2)}]_{t}。我们注意到,用 \frac{1}{\Delta} 进行缩放会准确地得到我们在第一项中想要的东西,再加上一些噪声。然而,由于 q^2 不能整除 \Delta,所以最后一项 (q^{2}\cdot r_{1}\cdot r_{2}) 会产生很大的噪声。相反,我们将使用因子 \frac{t}{q} 进行缩放。现在,我们可以写成 M^{(1)}\cdot M^{(2)}=[M^{(1)}\cdot M^{(2)}]_t+t\cdot r_M。我们也可以写成 v_1\cdot v_2=[v_1\cdot v_2]_{\Delta}+\Delta\cdot r_v。用 \frac{t}{q} 进行缩放并将这些表达式代入等式(12),我们得到以下结果:

\begin{aligned}\frac{t}{q}(C^{(1)}\cdot C^{(2)})(SK)=&\Delta[M^{(1)}\cdot M^{(2)}]_t+(M^{(1)}\cdot v_2 + M^{(2)}\cdot v_1)+\\&t(v_1\cdot r_2 + v_2\cdot r_1)+r_v+(q-[q]_t)\cdot(r_M + M^{(1)}\cdot r_2 + M^{(2)}\cdot r_1)+\\&q\cdot t\cdot r_1\cdot r_2+\frac{t}{q}[v_1\cdot v_2]_{\Delta}-\\&\frac{[q]_t}{q}(\Delta M^{(1)}\cdot M^{(2)}+M^{(1)}\cdot v_2 + M^{(2)}\cdot v_1 + r_v)\end{aligned}    (13)

        推导过程的最后一步是将等式(13)q 化简,这会得到:

\begin{aligned}\frac{t}{q}(C^{(1)}\cdot C^{(2)})(SK)=&\Delta[M^{(1)}\cdot M^{(2)}]_t+(M^{(1)}\cdot v_{2}+M^{(2)}\cdot v_{1})+\\&t(v_{1}\cdot r_{2}+v_{2}\cdot r_{1})+r_{v}-\\&[q]_{t}(r_{M}+M^{(1)}\cdot r_{2}+M^{(2)}\cdot r_{1})+r_{e}\end{aligned}    (14)

        其中 r_{e} 是由等式(13)中的最后两项产生的舍入误差。

        乘法运算中的噪声增长具有近似为 2\cdot t\cdot n^{2}\cdot\|SK\| 的线性因子,即 \left\|v_{p}\right\|=\left\|v_{i}\right\|\cdot2\cdot t\cdot n^{2}\cdot\|SK\|,其中 v_{p} 是乘积密文中的噪声,v_{i} 是输入密文中的噪声。

        简而言之,为了评估同态乘法,我们计算输入密文的张量积并按 \frac{t}{q} 进行缩放,如下所示:

\begin{aligned} EvalMult\left(C^{(1)}, C^{(2)}\right)=(&\left[\left\lfloor\frac{t\left(C_{1}^{(1)} \cdot C_{1}^{(2)}\right)}{q}\right\rceil\right]_{q},\left[\left\lfloor\frac{t\left(C_{1}^{(1)} \cdot C_{2}^{(2)}+C_{2}^{(1)} \cdot C_{1}^{(2)}\right)}{q}\right\rceil\right]_{q},{\left.\left[\left\lfloor\frac{t\left(C_{2}^{(1)} \cdot C_{2}^{(2)}\right)}{q}\right\rceil\right]_{q}\right)}\end{aligned}    (15)

        可以注意到,EvalMult 将结果密文中的项数从 2 个环元素增加到了 3 个。此外,为了解密得到的密文,必须使用稍微不同的解密过程。幸运的是,这些复杂情况可以通过重线性化来解决,这将在后续部分进行描述。

BGV的同态加法

        如公式(16)所示,同态加法以两个相对于相同模数 q_l 定义的密文 C^{(1)}C^{(2)} 作为输入,并返回一个密文 C^{(3)} ,该密文包含对输入中加密的两个明文消息之和的加密,即 Decryption(C_{3},SK)=M_{1}+M_{2}\ mod\ t。只要被加数密文中的误差不是太大,这就适用。为了理解这一点,让我们分析同态加法过程。公式(5)相当简单,我们只需将每个密文中的相应多项式相加。

EvalAdd(C^{(1)},C^{(2)}) \\ =([C_{1}^{(1)}+C_{1}^{(2)}]_{q_{l}},[C_{2}^{(1)}+C_{2}^{(2)}]_{q_{l}})=(C_{1}^{(3)},C_{2}^{(3)})=C^{(3)}    (16)

        为了理解这为何可行,让我们对公式(16)进行如下拆解:假设  C^{(1)}C^{(2)} 分别是对  M^{(1)}M^{(2)} 的新的加密结果果。从代数角度来看,它们可以如下表示(参见公式(5))。

\begin{aligned} C^{(1)}=\left(\left[PK_{1} \cdot u^{(1)}+t \cdot e_{1}^{(1)}+M^{(1)}\right]_{q_{l}},\left[PK_{2} \cdot u^{(1)}+t \cdot e_{2}^{(1)}\right]_{q_{l}}\right) \\ C^{(2)}=\left(\left[PK_{1} \cdot u^{(2)}+t \cdot e_{1}^{(2)}+M^{(2)}\right]_{q_{l}},\left[PK_{2} \cdot u^{(2)}+t \cdot e_{2}^{(2)}\right]_{q_{l}}\right)\end{aligned}    (17)

        将 C^{(1)} 和 C^{(2)} 代入公式(16),我们得到以下结果:

\begin{aligned} C^{(3)}= & \left(C_{1}^{(3)}, C_{2}^{(3)}\right) \\ = & \left(\left[PK_{1} \cdot\left(u^{(1)}+u^{(2)}\right)+t\left(e_{1}^{(1)}+e_{1}^{(2)}\right)+\left(M^{(1)}+M^{(2)}\right)\right]_{q_{l}}\right. \\ & {\left.\left[PK_{2} \cdot\left(u^{(1)}+u^{(2)}\right)+t\left(e_{2}^{(1)}+e_{2}^{(2)}\right)\right]_{q_{l}}\right) } \\ = & \left(\left[PK_{1} \cdot u^{(3)}+t \cdot e_{1}^{(3)}+\left(M^{(1)}+M^{(2)}\right)\right]_{q_{l}},\left[PK_{2} \cdot u^{(3)}+t \cdot e_{2}^{(3)}\right]_{q_{l}}\right) \end{aligned}    (18)

        很容易看出公式(18)具有对 M^{(3)} = M^{(1)} + M^{(2)} 进行加密的有效密文的形式。请注意,在 C^{(3)} 中的误差项,在最坏情况分析下,大约是输入密文中噪声项的总和,即噪声是累加增长的。

BGV的同态乘法

        同态乘法以两个相对于相同模数 q_l 定义的密文 C^{(1)}C^{(2)} 作为输入,并返回一个密文$ C^{(3)} ,该密文包含对输入密文中加密的两个明文消息之积的加密,即 Decryption(C_{3},SK)=M_{1}\cdot M_{2}\ mod\ t

        在接下来的分析中,我们将解密公式解释为在私钥SK处的密文评估:

C^{(1)}(SK)=M^{(1)} + t\cdot v_1 + q_l\cdot r_1; \ C^{(2)}(SK)=M^{(2)} + t\cdot v_2 + q_l\cdot r_2    (19)

        将密文相乘会得到:

\begin{aligned} \left(C^{(1)} \cdot C^{(2)}\right)(SK)= & M^{(1)} \cdot M^{(2)}+t\left(M^{(1)} \cdot v_{2}+M^{(2)} \cdot v_{1}\right)+ \\ & q_{l} \cdot t\left(v_{1} \cdot r_{2}+v_{2} \cdot r_{1}\right)+q_{l} \cdot\left(M^{(1)} \cdot r_{2}+M^{(2)} \cdot r_{1}\right)+ \\ & t^{2} \cdot v_{1} \cdot v_{2}+q_{l}^{2} \cdot r_{1} \cdot r_{2} \\ = & M^{(1)} \cdot M^{(2)}+t\left(M^{(1)} \cdot v_{2}+M^{(2)} \cdot v_{1}+t \cdot v_{1} \cdot v_{2}\right) \end{aligned}    (20)

        密文乘积的解密公式具有对 (M^{(1)} \cdot M^{(2)})进行加密的有效密文结构,其噪声项为 v = M^{(1)} \cdot v_2 + M^{(2)} \cdot v_1 + t \cdot v_1 \cdot v_2。注意噪声项是如何随着输入密文中噪声的乘积而呈乘法增长的 t·v_1 \cdot v_2。这意味着随着我们在计算中进行得更深入,噪声呈指数增长。为了解决这个问题,BGV使用模数切换(ModSwitch)来降低乘法噪声的增长速度。模数切换将在本文后面进行描述。

        根据上述讨论,我们可以推断出\(EvalMult\)可以通过输入密文的多项式乘法进行计算,如下面的公式所示:

\begin{aligned} EvalMult\left(C^{(1)}, C^{(2)}\right)=( & {\left[C_{1}^{(1)} \cdot C_{1}^{(2)}\right]_{q_{l}},\left[C_{1}^{(1)} \cdot C_{2}^{(2)}+C_{2}^{(1)} \cdot C_{1}^{(2)}\right]_{q_{l}}, \quad} {\left.\left[C_{2}^{(1)} \cdot C_{2}^{(2)}\right]_{q_{l}}\right) } \end{aligned}    (21)

        EvalMult 将结果密文中的环元素数量从 2 增加到了 3。此外,乘积密文是相对于SK^2 而不是原始的私钥 SK定义的,也就是说,它可以使用 SK^2 进行解密。为了将元素数量恢复到 2 并使密文可以使用 SK进行解密,可以使用接下来描述的重线性化过程。

8、重线性化

        BFV的重线性化过程的主要目的是将由 EvalMult 产生的乘积密文(product ciphertexts)的大小减少回两个环元素。

        这个问题可以具体表述如下:令 C^{*}=\{C_{1}^{*}, C_{2}^{*}, C_{3}^{*}\}。我们的目标是找到 \hat{C}^{*}=\{\hat{C}_{1}^{*}, \hat{C}_{2}^{*}\},使得:

\left[C_{1}^{*}+C_{2}^{*} \cdot SK+C_{3}^{*} \cdot SK^{2}\right]_{q} \approx\left[\hat{C}_{1}^{*}+\hat{C}_{2}^{*} \cdot SK+r\right]_{q}    (22)

        通过评估密钥 EK = (-(a·SK + e)+SK^{2},a) 提供对 SK^2 的访问。请注意,这是 SK^2 的掩码版本,因为EK_1 + EK_2·SK = SK^2 - e。现在我们可以计算 C^{*} 如下:

\begin{aligned} \hat{C}_{1}^{*}=\left[C_{1}^{*}+EK_{1}\cdot C_{3}^{*}\right]_{q} \\ \hat{C}_{2}^{*}=\left[C_{2}^{*}+EK_{2}\cdot C_{3}^{*}\right]_{q}\end{aligned}      (23)

        如果我们写出方程(23)的解密公式,我们得到:

\begin{aligned} \hat{C}_{1}^{*}+\hat{C}_{2}^{*} \cdot SK & =C_{1}^{*}+EK_{1} \cdot C_{3}^{*}+SK \cdot\left(C_{2}^{*}+EK_{2} \cdot C_{3}^{*}\right) \\ & =C_{1}^{*}+C_{2}^{*} \cdot SK+C_{3}^{*} \cdot\left(EK_{1}+EK 2 \cdot SK\right) \\ & =C_{1}^{*}+C_{2}^{*} \cdot SK+C_{3}^{*} \cdot SK^{2}+C_{3}^{*} \cdot e\end{aligned}     (24)

        需要注意的是,由于 C_{3}^{*}Z_{q} 中有系数,所以项 C_{3}^{*}:e 可能会很大。不过,有一种使用基分解的技术可以减少这个误差。更多细节,我们请读者参考[FV12]。

        BGV由于与密文模数相关的一些小变化,我们在这里简要重申,相同的问题和相同的目标,使得:

\left[C_{1}^{*}+C_{2}^{*}\cdot SK+C_{3}^{*}\cdot SK^{2}\right]_{q_{l}}\approx\left[\hat{C}_{1}^{*}+\hat{C}_{2}^{*}\cdot SK+r\right]_{q_{l}}     (25)

        通过评估密钥 EK 计算 C^{*} 如下:

\begin{aligned} \hat{C}_{1}^{*}=\left[C_{1}^{*}+EK_{1}\cdot C_{3}^{*}\right]_{q_{l}} \\ \hat{C}_{2}^{*}=\left[C_{2}^{*}+EK_{2}\cdot C_{3}^{*}\right]_{q_{l}}\end{aligned}     (26)

        通过解密公式(24),我们就会得到我们想要的内容。

9、模数切换

        如前所述,模数切换(MODSWITCH)用于控制乘法噪声。这个概念最初在[BGV14]中被引入,它利用了这样一个事实:给定一个相对于模数q和私钥SK定义的密文C,它可以被转换为一个相对于另一个模数 q' 和相同私钥SK定义的等价密文 C',使得:

[C(SK)]_{q} = [C'(SK)]_{q'}     (27)

        这种转换是通过将C的系数乘以 q'/q 的量并进行适当的舍入来完成的。为了降低噪声幅度,我们选择一个比 q 小得多的 q' ,这使我们能够降低乘法噪声。

        请注意,在BGV的情境中,q可以是任何层级 l 的 q_l;而在此情境中q'简单地就是 q_{l - 1}。此外,密文模数 q_l (0\leq l\leq L)的选择使得它们对t取模是等价的。这导致在不影响加密的明文消息的情况下降低了噪声。从明文的角度看,就好像我们是按1进行缩放。

模数切换(MODSWITCH)可以按照公式(28)进行计算,其中[·]是一个合适的舍入函数。转换后的密文C'是根据新的模数q'定义的。

C' = \left[\frac{q'}{q} \cdot C\right]     (28)

10、安全性

        BFV/BGV 方案安全性源于 RLWE 问题的难度。我们注意到,选择最佳的参数以最大化性能并同时满足安全性和功能性约束是一项相当复杂的任务,最好咨询专业密码学家来进行选择。对于 BFV/BGV 的简要安全分析和一组推荐参数,我们建议读者参考同态加密标准ACC^{+}_{18}

11、总结

BFV和BGV同态加密方案的发展路径和关键里程碑:

11.1. BFV发展路径

BFV方案(Brakerski/Fan-Vercauteren)最初是由Zvika Brakerski提出的,并由Fan和Vercauteren进一步改进。其发展历程可以分为以下几个阶段:

  • 2011年Brakerski提出基于学习有噪声问题(LWE)和理想格的同态加密基础模型。这一模型首次展示了如何利用噪声增长的管理,实现多次加密操作。

  • 2012年Brakerski和Vercauteren改进了初始方案,引入了特殊模数来控制噪声增长(即现在称为BFV的方案)。此时,他们提出了新的编码方式,允许整数加法和乘法运算,特别适合用于需要高精度计算的场景。

  • 2014年Fan和Vercauteren提出了一个改进版本,通过调整参数和编码策略来进一步优化BFV的噪声管理,使得BFV方案在整数加密中更为高效稳定,这一版本正式确立了BFV的模型。

BFV:更适合低深度、精确计算,不需要模数转换。

11.2. BGV发展路径

BGV方案(Brakerski-Gentry-Vaikuntanathan)则是在BFV方案基础上,进一步通过模数转换技术改善了噪声控制和运算效率,特别适合高深度、多乘法操作的同态加密场景。BGV的发展路径主要包括以下阶段:

  • 2011年Brakerski和Vaikuntanathan提出一个非耦合模数的噪声控制技术,为后续的BGV方案打下基础。这项技术允许在不同模数下控制噪声增长,使同态乘法不至于导致噪声增长过快。

  • 2012年Brakerski、Gentry和Vaikuntanathan联合提出了BGV方案,首次引入模数转换(modulus switching)技术。该技术通过每次乘法操作后逐步减小模数来管理噪声,使得BGV方案能够支持更高深度的乘法操作。这一创新为高深度同态加密计算带来了显著的效率提升。

  • 2013年BGV方案得到进一步的优化,引入了批处理(batching)和密文旋转(ciphertext rotation)技术,允许在密文中进行向量操作,提升了批处理密文的计算效率。

BGV:在重线性化的基础上支持模数转换,适合高深度和批处理计算,噪声控制更好,密文大小管理更高效。

        因此,选择使用BFV还是BGV,取决于具体应用需求,比如精度需求和计算深度。如果需要更高的运算深度和效率,BGV会是更合适的选择,而对于低深度、精确度要求高的场景,BFV则更适用。

在《Revisiting Homomorphic Encryption Schemes for Finite Fields》这篇文章里,作者在PALISADE中做了BGV和BFV的实现:

  • BGV在大明文模数下噪声增长比较小,他们的结果是优化后的BFV和BGV在大明文模数下表现近似,稍好于BGV。

  • BFV的效率在小明文模数下较好,BGV的效率在适中或者较大的模数情况下表现较好。

  • PALISADE中的BFV实现比之前最好的实现在深层(乘法)电路的评估上快了4倍。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/464020.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

占地1.1万平,2亿投资的智能仓储系统:高架库、AGV、码垛机器人……

导语 大家好&#xff0c;我是社长&#xff0c;老K。专注分享智能制造和智能仓储物流等内容。 我国调味料市场近年来展现出惊人的增长潜力&#xff0c;各大品牌纷纷加大投入&#xff0c;力求在竞争中脱颖而出。 广东美味鲜调味食品有限公司&#xff0c;作为行业内的佼佼者&#…

EJEAS S2滑雪对讲机全球发布会圆满举办,为滑雪市场注入新活力

时光向新&#xff0c;步履向前。站在冰雪运动与科技创新的交汇点&#xff0c;深圳爱骑仕智能科技有限公司&#xff08;以下简称“EJEAS”&#xff09;于2024年11月2日在新疆阿勒泰可可托海成功举办S2滑雪对讲机全球发布会。现场汇聚了来自全国各地的两三百名嘉宾&#xff0c;包…

个人对Numpy中transpose()函数的理解

NumPy中的transpose()函数用于对数组进行转置&#xff1a; 如果函数中不传递任何参数&#xff0c;它将进行标准的矩阵转置&#xff1b; 如果传递了一个轴序列&#xff0c;NumPy将按照这个序列重新排列轴。 二维的转置很好理解&#xff0c;就是线性代数中的矩阵转置。但高纬度…

【运动的&足球】足球运动员球守门员裁判检测系统源码&数据集全套:改进yolo11-DBBNCSPELAN

改进yolo11-FocalModulation等200全套创新点大全&#xff1a;足球运动员球守门员裁判检测系统源码&#xff06;数据集全套 1.图片效果展示 项目来源 人工智能促进会 2024.10.28 注意&#xff1a;由于项目一直在更新迭代&#xff0c;上面“1.图片效果展示”和“2.视频效果展示…

流畅!HTMLCSS打造网格方块加载动画

效果演示 这个动画的效果是五个方块在网格中上下移动&#xff0c;模拟了一个连续的加载过程。每个方块的动画都是独立的&#xff0c;但是它们的时间间隔和路径被设计为相互协调&#xff0c;以创建出流畅的动画效果。 HTML <div class"loadingspinner"><…

面试题:JVM(二)

1. 面试题 简述 Java 类加载机制?&#xff08;百度&#xff09; JVM类加载机制 &#xff08;滴滴&#xff09; JVM中类加载机制&#xff0c;类加载过程&#xff0c;什么是双亲委派模型&#xff1f; &#xff08;腾讯&#xff09; JVM的类加载机制是什么&#xff1f; &#x…

【c++日常刷题】两个数字的交集、点击消除、最小花费爬楼梯

两个数字的交集⭐ 两个数组的交集_牛客题霸_牛客网 (nowcoder.com) 题目描述&#xff1a; 解题思路&#xff1a; 通过遍历num1&#xff0c;如果遍历到的元素如果在num2中能找到&#xff0c;则这是num1和num2的公告元素&#xff1b; 这里需要借助两个数组来实现&#xff1a;…

energy 发布 v2.4.5

更新内容 修复 energy cli install 命令安装开发环境 修复 动态库加载error未暴露 增加 JS ipc.on 监听模式&#xff0c;异步返回结果 修复 energy cli 不能强制退出问题 修复 MacOS 开发模式 debug 时不更新 helper 进程 优化 energy cli 在 MacOS 开发模式和安装包制作 link…

LeetCode 19. 删除链表的倒数第 N 个结点(java)

目录 题目描述: 代码: 第一种: 第二种: 题目描述: 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5]示例 2&#xff1a; 输入&#xff1a;h…

IMU应用于监测进食

最近&#xff0c;日本研究团队成功研发了一种创新的进食速度监测系统&#xff0c;巧妙融合IMU技术&#xff0c;旨在深入研究并有效评估个体在自由生活环境下的进食习惯。 实验中&#xff0c;科研团队把IMU传感器固定在受试者佩戴的腕带中&#xff0c;以监测并记录进食手腕时的运…

WSL开发--利用Git连接远程仓库(详细步骤)

这篇文章主要介绍了如何将本地项目推送到 GitLab 上&#xff0c;并且避免每次提交都需要输入用户名和密码。文中分步讲解了配置 GitLab SSH 密钥以及配置 Git 远程仓库地址的方法。以下是文章的优化和简洁版&#xff1a; 将本地项目推送到 GitLab 并配置 SSH 免密登录 为了方便…

LeetCode100之盛最多水的容器(11)--Java

1.问题描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量 注意 你不能倾斜容器 示例1 输入&…

算法实现 - 快速排序(Quick Sort) - 理解版

文章目录 算法介绍算法分析核心思想三个版本运行过程挖坑法Hoare 原版前后指针法 算法稳定性和复杂度稳定性时间复杂度平均情况O(nlogn)最差情况O( n 2 n^2 n2) 空间复杂度 算法介绍 快速排序是一种高效的排序算法&#xff0c;由英国计算机科学家C. A. R. Hoare在1960年提出&a…

设备搜索相关协议使用

一、实现原理 首先&#xff0c;Client -> Gateway : 发送 UDP 广播包&#xff08;含厂商自定义协议)这一步表示客户端开始向网络中发送一个包含厂商自定义协议的 UDP 广播包&#xff0c;目的是寻找本厂商的设备&#xff08;网关&#xff09;。客户端此时处于活动状态activa…

视频去水印怎么办?两种方法教会你

视频有水印的话确实很恼火&#xff0c;想要干净的去除视频水印&#xff0c;这里分享两种简单又实用的方法。 方法一&#xff1a;美图秀秀 大家都熟悉的修图神器&#xff0c;功能超全。不仅能把照片P得美美哒&#xff0c;还能去掉照片和视频上的水印呢&#xff01;用起来挺顺手…

【案例】旗帜飘动

开发平台&#xff1a;Unity 6.0 开发工具&#xff1a;Shader Graph 参考视频&#xff1a;Unity Shader Graph 旗帜飘动特效   一、效果图 二、Shader Graph 路线图 三、案例分析 核心思路&#xff1a;顶点偏移计算 与 顶点偏移忽略 3.1 纹理偏移 视觉上让旗帜保持动态飘动&a…

PHP合成图片,生成海报图,poster-editor使用说明

之前写过一篇使用Grafika插件生成海报图的文章&#xff0c;但是当我再次使用时&#xff0c;却发生了错误&#xff0c;回看Grafika文档&#xff0c;发现很久没更新了&#xff0c;不兼容新版的GD&#xff0c;所以改用了intervention/image插件来生成海报图。 但是后来需要对海报…

智慧汇聚:十款企业培训工具打造学习型企业

在当今快速变化的商业环境中&#xff0c;企业要想保持竞争力&#xff0c;就必须不断适应新技术、新市场和新的工作方式。构建一个学习型企业&#xff0c;不仅能够促进员工的个人成长&#xff0c;还能增强团队的整体能力和企业的创新能力。为了实现这一目标&#xff0c;借助先进…

「C/C++」C/C++标准库 之 #include<cstdlib> 通用工具函数库

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…

pycharm调用方法时显示为灰色

不用担心&#xff0c;亮的证明是被用过得&#xff0c;灰色的没有被用&#xff0c;引用一下就会变正常了