BFV是把Bra12的LWE版本推到了RLWE版本，Bra12也可以叫做BFV。

经典的RLWE的公钥加密算法回顾

对比以前的Regev的LWE公钥加密方案，其实几乎只是把明文空间换了，也就是在最大比特编码的时候把2换成t，即，Δ=⌊q/t⌋\Delta = \lfloor q/t \rfloorΔ=⌊q/t⌋。同时这里的qqq是没有限制的，也就是可以使用2的幂次来简化运算。

这里可以这样看s=(1,s)\mathbf s = (1,\mathbf s)s=(1,s),ct=(c0,c1)\mathbf {ct}=(\mathbf c_0,\mathbf c_1)ct=(c0​,c1​)。
对于正确性验证
c0+c1⋅s=p0⋅u+e1+Δ⋅m+p1⋅u+e2=−a⋅s⋅u+e⋅u+e1+Δ⋅m+a⋅s⋅u+e2⋅s=Δ⋅m+e⋅u+e1+e2⋅s(modq)\begin{aligned}\mathbf c_0+\mathbf c_1 \cdot \mathbf s &= \mathbf p_0 \cdot \mathbf u +\mathbf e_1 + \Delta \cdot \mathbf m + \mathbf p_1 \cdot \mathbf u +\mathbf e_2 \\ &= -\mathbf a \cdot \mathbf s \cdot \mathbf u + \mathbf e \cdot \mathbf u +\mathbf e_1 + \Delta \cdot \mathbf m + \mathbf a \cdot \mathbf s \cdot \mathbf u + \mathbf e_2 \cdot \mathbf s \\ &= \Delta \cdot \mathbf m +\mathbf e \cdot \mathbf u +\mathbf e_1 + \mathbf e_2 \cdot \mathbf s (\mod q) \end{aligned}c0​+c1​⋅s​=p0​⋅u+e1​+Δ⋅m+p1​⋅u+e2​=−a⋅s⋅u+e⋅u+e1​+Δ⋅m+a⋅s⋅u+e2​⋅s=Δ⋅m+e⋅u+e1​+e2​⋅s(modq)​
可以看到这里的噪声似乎与u\mathbf uu和s\mathbf ss有关，如果将这两个取的小一点，能够一定程度上减低噪声。
另外，将噪声用v=e⋅u+e1+e2⋅s\mathbf v = \mathbf e \cdot \mathbf u +\mathbf e_1 + \mathbf e_2 \cdot \mathbf sv=e⋅u+e1​+e2​⋅s表示，能够得到[c0+c1⋅s]q=Δ⋅m+v[\mathbf c_0+\mathbf c_1 \cdot \mathbf s ]_q =\Delta \cdot \mathbf m + \mathbf v[c0​+c1​⋅s]q​=Δ⋅m+v，与此同时若取样的χ≤B\chi \le Bχ≤B的话，我们将得到噪声的界限，即v≤2⋅B2⋅δR+B\mathbf v \le 2\cdot B^2 \cdot \delta_R+Bv≤2⋅B2⋅δR​+B，其中δR\delta_RδR​表示扩张因子
δR=max⁡{∥a⋅b∥∥a∥⋅∥b∥:a,b∈R}\delta_{R}=\max \left\{\frac{\|a \cdot b\|}{\|a\| \cdot\|b\|}: a, b \in R\right\}δR​=max{∥a∥⋅∥b∥∥a⋅b∥​:a,b∈R}，其中的∣∣a∣∣=maxi∣ai∣||a||=max_i|a_i|∣∣a∣∣=maxi​∣ai​∣为无穷范数。

同态方案

方案是基于前面的LPR.ES方案的，作为优化，该方案增加了一个重线性化，将u\mathbf uu和s\mathbf ss的取值范围变为R2\mathbb R_2R2​，即它们的范数为1，其他基本一致
借用BV11里面的思想，将解密过程看作一个解密函数，即得到，
[ct(x)]q=[c0+c1⋅x]q[\mathbf {ct}(\mathbf x)]_q=[\mathbf c_0+\mathbf c_1 \cdot \mathbf x ]_q[ct(x)]q​=[c0​+c1​⋅x]q​
代入密钥就能得到明文
[ct(s)]q=Δ⋅m+v[\mathbf {ct}(\mathbf s)]_q= \Delta \cdot \mathbf m + \mathbf v[ct(s)]q​=Δ⋅m+v

同态乘法

来看看核心的乘法运算

该定理表明，乘法时，噪声不是呈平方增长，而是大致上乘以了一个系数2⋅t⋅δR2⋅∣∣s∣∣2\cdot t\cdot \delta_R^2\cdot||\mathbf s||2⋅t⋅δR2​⋅∣∣s∣∣，也就是线性增长，从表达式里能看到，对噪声有显著影响的是ttt和s\mathbf ss的范数。（具体引理证明感兴趣可以去原文看看😇）

重线性化

然后用BV11中的函数思想，两个函数相乘得到的将是三项，成为二次函数，需要执行重线性化让它还原为两项也就是一次式。
假设一个二阶的密文为[c0,c1,c2][\mathbf c_0,\mathbf c_1,\mathbf c_2][c0​,c1​,c2​]，线性化的目的是将它变成一阶的[c0′,c1′][\mathbf c'_0,\mathbf c'_1][c0′​,c1′​]即[c0+c1⋅s+c2⋅s2]q=[c0′+c1′⋅s+r]q\left[\mathbf{c}_{0}+\mathbf{c}_{1} \cdot \mathbf{s}+\mathbf{c}_{2} \cdot \mathbf{s}^{2}\right]_{q}=\left[\mathbf{c}_{0}^{\prime}+\mathbf{c}_{1}^{\prime} \cdot \mathbf{s}+\mathbf{r}\right]_{q}[c0​+c1​⋅s+c2​⋅s2]q​=[c0′​+c1′​⋅s+r]q​，其中r\mathbf rr很小。
由于s2\mathbf s^2s2是不可知的，所以这里选用的方式是加密一手。
为此，这里引入了一个重线性化密钥rlk=([−(a0⋅s+e0)+s2]q,a0)rlk=([-(\mathbf a_0 \cdot \mathbf s +\mathbf e_0)+\mathbf s^2]_q,\mathbf a_0)rlk=([−(a0​⋅s+e0​)+s2]q​,a0​),满足rlk[0]+rlk[1]⋅s=s2+e0rlk[0]+rlk[1]\cdot \mathbf s =\mathbf s^2 +\mathbf e_0rlk[0]+rlk[1]⋅s=s2+e0​

方案一（T进制分解）

第一种使用rlkrlkrlk来转换密文的方法是令c0′=c0+rlk[0]⋅c2\mathbf c'_0 = \mathbf c_0+rlk[0]\cdot\mathbf c_2c0′​=c0​+rlk[0]⋅c2​和c1′=c1+rlk[1]⋅c2\mathbf c'_1 = \mathbf c_1+rlk[1]\cdot\mathbf c_2c1′​=c1​+rlk[1]⋅c2​这样得到的噪声r=e0⋅c2\mathbf r=\mathbf e_0 \cdot \mathbf c_2r=e0​⋅c2​（独立于密文的噪声，只是重线性化带来的噪声），但是由于c2∈Rq\mathbf c_2 \in R_qc2​∈Rq​,直接使用的话，会导致噪声被放大很多很多，所以需要进行分解。
那么这里的方法是选择一个基（独立于ttt），将c2\mathbf c_2c2​切片。即令
c2=∑i=0ℓTi⋅c2(i)\mathbf c_2 = \sum_{i=0}^{\ell} T^i \cdot \mathbf c_2^{(i)}c2​=∑i=0ℓ​Ti⋅c2(i)​,其中ℓ=⌊log⁡T(q)⌋\ell=\lfloor\log_T(q) \rfloorℓ=⌊logT​(q)⌋,且c2(i)\mathbf c_2^{(i)}c2(i)​系数均在RTR_TRT​中，与此对应的设置重线性化密钥为rlk=[([−(ai⋅s+ei)+Ti⋅s2]q,ai):i∈[0..ℓ]]rlk=\left[\left(\left[-\left(\mathbf{a}_{i} \cdot \mathbf{s}+\mathbf{e}_{i}\right)+T^{i} \cdot \mathbf{s}^{2}\right]_{q}, \mathbf{a}_{i}\right): i \in[0 . . \ell]\right]rlk=[([−(ai​⋅s+ei​)+Ti⋅s2]q​,ai​):i∈[0..ℓ]]
由此得到更新后的密文为
c0′=[c0+∑i=0ℓrlk⁡[i][0]⋅c2(i)]qand c1′=[c1+∑i=0ℓrlk⁡[i][1]⋅c2(i)]q\mathbf{c}_{0}^{\prime}=\left[\mathbf{c}_{0}+\sum_{i=0}^{\ell} \operatorname{rlk}[i][0] \cdot \mathbf{c}_{2}^{(i)}\right]_{q} \quad \text { and } \quad \mathbf{c}_{1}^{\prime}=\left[\mathbf{c}_{1}+\sum_{i=0}^{\ell} \operatorname{rlk}[i][1] \cdot \mathbf{c}_{2}^{(i)}\right]_{q}c0′​=[c0​+∑i=0ℓ​rlk[i][0]⋅c2(i)​]q​ and c1′​=[c1​+∑i=0ℓ​rlk[i][1]⋅c2(i)​]q​
最终得到的噪声将为r=∑i=0ℓc2(i)⋅ei\mathbf r = \sum_{i=0}^\ell \mathbf c_2 ^{(i)}\cdot \mathbf e_ir=∑i=0ℓ​c2(i)​⋅ei​。
这样操作的结果是TTT越大，rlkrlkrlk越小，噪声r\mathbf rr就越大，但是TTT越小，rlkrlkrlk就会越大，那么计算速度就会变慢。同时由于重线性化的噪声独立于密文噪声，为了良好的同态，应该让噪声r\mathbf rr的值在密文噪声的附近。
动态线性化：先选取足够小的TTT来获取足够小的误差，当几次乘法导致误差变大后，可以选择对T2T^2T2进行线性化进行加速，也就是计算包含T2T^2T2的rlkrlkrlk，由此rlkrlkrlk中应当包含所需的所有信息。（有点懵还，原文是这么写的）

方案二（模切换）

先给出一个能大模数的能够容纳较大误差噪声的加密版本的s2\mathbf s^2s2，然后再进行缩放来获取所需要的。
更新rlk=(−[(a⋅s+e)+p⋅s2]p⋅q,a)rlk = (-[(\mathbf a \cdot \mathbf s + \mathbf e)+p \cdot \mathbf s^2]_{p \cdot q},\mathbf a)rlk=(−[(a⋅s+e)+p⋅s2]p⋅q​,a)，其中a∈Rp⋅qa \in R_{p \cdot q}a∈Rp⋅q​和e←χ′\mathbf e \leftarrow \chi'e←χ′（和前面是不一样的分布）。同时密文也要更新为，
c0′′=[⌊c2⋅rlk[0]p⌋]q\mathbf c_0'' = \left[\left\lfloor\frac{\mathbf{c}_{2} \cdot \mathbf{r l k}[0]}{p}\right\rfloor\right]_{q}c0′′​=[⌊pc2​⋅rlk[0]​⌋]q​,c1′′=[⌊c2⋅rlk[1]p⌋]q\mathbf c_1''=\left[\left\lfloor\frac{\mathbf{c}_{2} \cdot \mathbf{r l k}[1]}{p}\right\rfloor\right]_{q}c1′′​=[⌊pc2​⋅rlk[1]​⌋]q​
简单计算能得到c0′′+c1′′⋅s=c2′′⋅s2+r\mathbf c_0''+\mathbf c_1'' \cdot s = \mathbf c_2'' \cdot \mathbf s^2 +\mathbf rc0′′​+c1′′​⋅s=c2′′​⋅s2+r
粗略的估算能得到∥r∥ 动态线性化：选择足够大的ppp来获取足够小的误差，多次乘法噪声增大后就可以通过提取p′/pp'/pp′/p，切换模数，来形成有效rlkrlkrlk进行加速。

同态方案

这里方案和前面的LPR方案很类似，不同的是，s\mathbf ss和u\mathbf uu的取值范围是R2R^2R2（这是为了减小噪声），多了重线性化密钥（缩减密文规模的）。
密文的形式是ct=(c0,c1)\mathbf ct=(\mathbf c_0,\mathbf c_1)ct=(c0​,c1​)，乘法其实就是两个密文对应项的乘，然后类似Bra12中的一样乘以一个缩放系数t/qt/qt/q用于减小噪声
然后是重线性化，和之前描述的一样

要实现乘法深度为LLL的电路，需要满足
4⋅δRL⋅(δR+1.25)L+1⋅tL−1<⌊q/B⌋4 \cdot \delta_{R}^{L} \cdot\left(\delta_{R}+1.25\right)^{L+1} \cdot t^{L-1}<\lfloor q / B\rfloor4⋅δRL​⋅(δR​+1.25)L+1⋅tL−1<⌊q/B⌋

全同态方案

（这块儿有点迷糊，没咋看懂，后面有需要再补吧）
采用的是Gentry的Bootstrapping方法，即在噪声达到最大值之前，进行一次同态解密，使得密文具有固定的噪声，且之后仍能进行一次乘法运算。
同态解密的条件是解密电路的深度必须小于同态运算最大深度，由此，需要对上面方案的解密方案进行处理。
这里采用的是不允许解密运算中的噪声v\mathbf vv增长到界限，而是将它限制在Δ/μ(μ>2)\Delta/\mu(\mu>2)Δ/μ(μ>2)内，可以通过将低位全部设置为0来忽略ct[0]\mathbf ct[0]ct[0]和ct[1]\mathbf ct[1]ct[1]中的大部分，从而达到优化解密的目的。
设置后，会增加一部分误差，即，把ct[0]\mathbf ct[0]ct[0]和ct[1]\mathbf ct[1]ct[1]，替换为了c0=ct[0]+e0\mathbf c_0 =\mathbf ct[0]+\mathbf e_0c0​=ct[0]+e0​和c1=ct[1]+e1\mathbf c_1 =\mathbf ct[1]+\mathbf e_1c1​=ct[1]+e1​（∣∣ei∣∣<Δ/v||\mathbf e_i||< \Delta/v∣∣ei​∣∣<Δ/v）。
这样将得到一个增加了新噪声的密文c0+c1⋅s=Δ⋅m+v+e0+e1⋅s+q⋅r\mathbf{c}_{0}+\mathbf{c}_{1} \cdot \mathbf{s}=\Delta \cdot \mathbf{m}+\mathbf{v}+\mathbf{e}_{0}+\mathbf{e}_{1} \cdot \mathbf{s}+q \cdot \mathbf{r}c0​+c1​⋅s=Δ⋅m+v+e0​+e1​⋅s+q⋅r
为了约束新增加的噪声，这里定义了两个函数abs⁡(a(x))∈Z[x]\operatorname{abs}(a(x)) \in Z[x]abs(a(x))∈Z[x]为将系数绝对值化后的多项式，并定义函数
H(f)=max⁡{∥∑i=0d−1abs⁡(xi+jmodf(x))∥∣j=0,…,d−1}H(f)=\max \left\{\left\|\sum_{i=0}^{d-1} \operatorname{abs}\left(x^{i+j} \bmod f(x)\right)\right\| \mid j=0, \ldots, d-1\right\}H(f)=max{∥∥∥​∑i=0d−1​abs(xi+jmodf(x))∥∥∥​∣j=0,…,d−1}
对于分圆多项式如f=xd+1f=x^d +1f=xd+1，代入上面函数能得到H(f)=1H(f)=1H(f)=1,用hhh代表s\mathbf ss的汉明距离（比特中的非0个数），会得到噪声的界限是Δ/μ+(H(f)⋅h+1)⋅Δ/ν\Delta / \mu+(H(f) \cdot h+1) \cdot \Delta / \nuΔ/μ+(H(f)⋅h+1)⋅Δ/ν，当满足条件2⋅μ⋅(H(f)⋅h+1)<ν⋅(μ−2)2 \cdot \mu \cdot(H(f) \cdot h+1)<\nu \cdot(\mu-2)2⋅μ⋅(H(f)⋅h+1)<ν⋅(μ−2)时，密文能够正确解密。

参考

Fan, Junfeng and Frederik Vercauteren. “Somewhat Practical Fully Homomorphic Encryption.” IACR Cryptol. ePrint Arch. 2012 (2012): 144.
全同态加密BFV-(section 1-基础知识)
全同态加密BFV-(section 2-SHE)
全同态加密：BFV