BFV原理(seal库)

大家好，欢迎来到IT知识分享网。

BFV原理(seal库)

设定三个模量

噪声预算由加密的参数所决定；同态操作会消耗掉噪声预算。全同态加密有两种操作，加法和乘法，其中加法基本从原理上几乎不消耗预算，消耗的预算最主要取决于乘法，如果乘法运算进行的太多，噪声预算归零，密文不能解密。

需要设置三个加密参数:

1. poly_modulus_degree(多项式模度);
2. 系数模量([密文]系数模量);
3. 明文模量(明文模量;只适用于BFV方案)。

EncryptionParameter parms(scheme_type::BFV); 

第一个参数是‘多项式模’的次数。这一定是2的正次幂，表示2的幂次多项式的次数;较大的poly_modulus_degree使密文的大小更大，所有的操作都更慢，但允许更复杂的加密计算。推荐值为1024、2048、4096、8192、16384、32768。

size_t poly_modulus_degree = 4096; parms.set_poly_modulus_degree(poly_modulus_degree); 

系数模量(coeff_modules)。该参数是一个大整数，它是不同素数的乘积，每个素数的大小最大为60位。它被表示为这些素数的一个向量，每个素数由smallmodules类的一个实例表示.coeff_modules的位长是指它的质数因子的位长之和。更大的coeff_模数意味着更大的噪声预算，因此更加密的计算能力。然而，coeff_modulus_degree确定了coeff_modul_modules总比特长度的上限，对于seal库，具体如下:

明文模量是特定于BFV方案的，在使用CKKS方案时无法设置，它决定了明文的大小范围，同时也影响着加密操作的安全性和效率

生成公钥和私钥

BFV的公钥使用随机种子生成，私钥SK是 random ternary polynomial, 也就是系数取自$R_2=-1,0,1$ 的多项式。

公钥PK是$R_q$上的多项式，由一对多项式构成：$(P{K}_1,P{K}_2)$, 定义如下
$$\begin{array}{rl}{\mathsf{PK}}_1& =[-1(a\cdot \mathsf{SK}+e){]}_q\\ {\mathsf{PK}}_2& =a\end{array}$$

其中$a$是采样自$R_q$上的随机多项式，$e$是采样自$\chi$的随机多项式。符号$[\cdot {]}_q$表示多项式的系数运算以$q$为模数进行。总之，$a$定义$R_q$上，所有运算都定义在$Z_q$上面模$(x^n+1)$的多项式环。

加解密

·加密：明文$M$,产生三个小的随机多项式，$u\in R_2,e_1,e_2\in \mathcal{X}$,加密结果$\mathcal{C}=({\mathcal{C}}_1,{\mathcal{C}}_2)$,其中缩放系
数$\Delta =\lfloor \frac{q}{t}\rfloor$,用于将明文$M$从$Z_t$扩展到密文的模空间$Z_q$上：
$$\begin{array}{rl}& {\mathsf{C}}_1=[{\mathsf{PK}}_1\cdot u+e_1+\Delta \mathsf{M}{]}_q\\ & {\mathsf{C}}_2=[{\mathsf{PK}}_2\cdot u+e_2{]}_q\end{array}$$
·解密：解密过程如下，最后并将加密时应用的缩放系数倒置：
$$\mathsf{M}={\left[\lfloor \frac{t[{\mathsf{C}}_1+{\mathsf{C}}_2\cdot \mathsf{SK}{]}_q}{q}\rceil \right]}_t$$
·解密过程是可验证的：
$$\begin{array}{rl}{C}_1+C_2\cdot SK& ={\mathsf{PK}}_1\cdot u+e_1+\Delta \mathsf{M}+({\mathsf{PK}}_2\cdot u+e_2)\cdot \mathsf{SK}\\ & =-(a\cdot \mathsf{SK}+e)\cdot u+e_1+\Delta \mathsf{M}+a\cdot u\cdot \mathsf{SK}+e_2\cdot \mathsf{SK}\\ & =-a\cdot u\cdot \mathsf{SK}-e\cdot u+e_1+\Delta \mathsf{M}+a\cdot u\cdot \mathsf{SK}+e_2\cdot \mathsf{SK}v\\ & =\Delta \text{М}-e\cdot u+e_1+e_2\cdot \text{SK}\\ & =\Delta \mathsf{M}+v\end{array}$$
解密中的四舍五入 (rounding) 取整可以去除$\frac{t}{q}\cdot v$,最后模t运算去除$t\cdot r$并恢复得到M。要保证解密成功，必须保证误差多项式$v$：$\frac{t}{q}\cdot |v|<\frac{1}{2}$。

同态加

同态加，需要将对应的多项式相加：

$$\mathsf{EvalAdd}({\mathsf{C}}^{(1)},{\mathsf{C}}^{(2)})=([{\mathsf{C}}_1^{(1)}+{\mathsf{C}}_1^{(2)}{]}_q,[{\mathsf{C}}_2^{(1)}+{\mathsf{C}}_2^{(2)}{]}_q)=({\mathsf{C}}_1^{(3)},{\mathsf{C}}_2^{(3)})={\mathsf{C}}^{(3)}$$
注意到这里随机误差相加，最坏情况是误差都增长一倍（概率很小），但是一般来说，这两个误差不会累加增大。

同态乘

同态乘过程相比加法很复杂，，由于上述解密过程用的是${(\mathcal{C}}^{(1)}\cdot {\mathcal{C}}^{(2)})(\mathcal{S}\mathcal{K})$, 也就是我们要计算
$$({\mathsf{C}}_1^{(1)}+{\mathsf{C}}_2^{(1)}\cdot \mathsf{SK})\cdot ({\mathsf{C}}_1^{(2)}+{\mathsf{C}}_2^{(2)}\cdot \mathsf{SK})$$
因此如果想要用$SK$进行解密，我们需要保留三项中间结果，即密文维度扩展了一维变成三维。

线性重构

这就是之前得到的同态乘法对应的正确解密结果加一个误差值，值得注意的是，论文中描述最后一个误差项${\mathbb{C}}_3^{\ast }\cdot e$可能很大，因为${\mathbb{C}}_3^{\ast }$的系数定义在$Z_q$上。