广义 BFV 方案的实践

实践中的通用 BFV

全同态加密 (FHE) 承诺解锁对加密数据的计算，但实际方案面临着限制其现实适用性的根本局限性。BFV (Brakerski-Fan-Vercauteren) 方案是使用最广泛的 FHE 构造之一，它体现了一个塑造了该领域的关键权衡：你可以每个密文打包大量数据，或者执行深度计算，但不能同时进行。

这种限制不仅仅是一个技术上的不便，它从根本上限制了 FHE 可以服务的应用程序类型。加密数据上的机器学习推断、安全数据库查询和保护隐私的分析都需要高数据吞吐量和大量的计算深度。然而，经典的 BFV 迫使从业者在这些需求之间做出令人不舒服的选择。

通用 BFV 方案的最新进展为摆脱这种权衡提供了一条途径。通过用精心选择的多项式商代替传统的整数明文模数，这些构造可以保持大的明文空间，同时实现与密文模数成比例的乘法深度，而不是与明文大小成反比。

本文探讨了 t(X)=Xk−bt(X) = X^k - bt(X)=Xk−b 的 quotient-by-t(X)=Xk−bt(X) = X^k - bt(X)=Xk−b 构造如何摆脱经典 BFV 的根本局限性，考察了这种方法的数学基础和实际影响。

经典 BFV：基础

设 N=2nN = 2^{n}N=2n 为分圆指数。经典 BFV 方案在以下范围内运行：

• 密文环： Rq=Zq[X]/(XN+1)R_{q} = \mathbb{Z}_{q}[X]/(X^{N}+1)Rq​=Zq​[X]/(XN+1)
• 明文模数： 整数 t≪qt\ll qt≪q
• 缩放因子： Δ=⌊q/t⌋≃q/t\Delta = \lfloor q/t \rfloor \simeq q/tΔ=⌊q/t⌋≃q/t
• 密钥/误差： s←R2s \leftarrow R_{2}s←R2​ 和 e←χe \leftarrow \chie←χ
• 中心化约简： ⌊x⌉t∈(−t/2,t/2]\lfloor x \rceil_{t} \in (-t/2,t/2]⌊x⌉t​∈(−t/2,t/2]

核心操作遵循熟悉的模式：

KeyGen： 选择: a←Rqa \leftarrow R_{q}a←Rq​, s←R2s \leftarrow R_{2}s←R2​, e←χe \leftarrow \chie←χ; 设置 b=−(as+e)∈Rqb = -(as + e) \in R_{q}b=−(as+e)∈Rq​。公钥 (b,a)(b, a)(b,a)；私钥 sss。

加密 m∈Zt[X]/(XN+1)m \in \mathbb{Z}_{t}[X]/(X^{N}+1)m∈Zt​[X]/(XN+1):

ct=(\[Δm+as+e\]q,−a)∈Rq2\\mathrm{ct}=\\,\\bigl(\[\\Delta m + as + e\]\_{q},\\; -a\\bigr)\\in R\_{q}^{2}

解密 ct=(c0,c1)\mathrm{ct}=(c_{0},c_{1})ct=(c0​,c1​):

m=⌊c0+c1sΔ⌉tm = \\Bigl\\lfloor \\frac{c\_{0}+c\_{1}s}{\\Delta} \\Bigr\\rceil\_{t}

根本瓶颈

经典 BFV 的核心限制源于其噪声增长行为。增加明文模数 ttt 以每个密文打包更多数据会带来高昂的代价：最大乘法深度大致受 log⁡q/log⁡t\log q / \log tlogq/logt 的限制，因此更大的明文空间会直接降低计算能力。为了在增加 ttt 的同时保持深度，我们必须成比例地增加 qqq，但是更大的密文模数会使每个操作更加昂贵：密钥需要更多内存，多项式算术需要更慢的 NTT，以及更昂贵的密钥切换。

结果是一个不可避免的选择：具有大 ttt 的高吞吐量应用会牺牲乘法深度，而深度计算则被限制在小的明文空间中。

有关基础 BFV 构造和安全性分析，请参阅“某种程度上实用的全同态加密"

关键突破：通用 BFV

突破来自于认识到明文模数不必是整数。我们可以使用 t(X)=Xk−bt(X) = X^k - bt(X)=Xk−b 形式的多项式商构造明文环，而不是对 t∈Zt \in \mathbb{Z}t∈Z 取模，其中 bbb 是一个小整数，kkk 划分了分圆多项式的某些结构参数。

这种看似简单的改变对噪声增长和乘法深度产生了深远的影响，为摆脱经典 BFV 的根本局限性提供了一条途径。

数学设置

我们保持密文环与经典 BFV 完全相同，使用一个 NTT 友好的素数：

Rq=Zq\[X\]/(XN+1),q≡1(mod2N)R\_q = \\mathbb{Z}\_q\[X\]\\big/(X^{N}+1),
        \\qquad q\\equiv1\\pmod{2N}

对于明文环，我们引入一个 二项式 关系。 写成 m=2Nm=2Nm=2N，并设：

• r=rad⁡(m)r=\operatorname{rad}(m)r=rad(m) - mmm 的根(划分 mmm 的不同素数的乘积)
• k∣(m/r)k\mid (m/r)k∣(m/r) - 我们选择的二项式度数
• t(X)=Xk−bt(X)=X^{k}-bt(X)=Xk−b，基数很小 ∣b∣≪q|b|\ll q∣b∣≪q

构建新的明文空间

我们利用分圆多项式的经典恒等式：

Φm(X)=Φr(Xm/r)\\Phi\_{m}(X)=\\Phi\_{r}\\bigl(X^{\\,m/r}\\bigr)

证明

符号和基本定义

rad(n):=∏p∣np\mathrm{rad}(n) := \prod_{p \mid n} prad(n):=∏p∣n​p (划分 nnn 的不同素数的乘积)；等效地，rad(n)\mathrm{rad}(n)rad(n) 是 nnn 的最大无平方因子。

Euler totient φ(n)=∣{1≤k≤n:gcd⁡(k,n)=1}∣\varphi(n) = |\{1 \le k \le n : \gcd(k,n) = 1\}|φ(n)=∣{1≤k≤n:gcd(k,n)=1}∣。

莫比乌斯函数 μ(1)=1\mu(1)=1μ(1)=1；如果 nnn 可被一个平方数整除，则 μ(n)=0\mu(n)=0μ(n)=0； 如果 nnn 是 rrr 个不同素数的乘积，则 μ(n)=(−1)r\mu(n)=(-1)^rμ(n)=(−1)r。

nnn-th 分圆多项式 Φn(X):=∏1≤k≤ngcd⁡(k,n)=1(X−e2πik/n)\displaystyle \Phi_n(X) := \prod_{1 \le k \le n \ \gcd(k,n)=1}\bigl(X - e^{2\pi i k/n}\bigr)Φn​(X):=1≤k≤ngcd(k,n)=1∏​(X−e2πik/n) 其根是 1 的本原 nnn-th 根的唯一首一多项式。它具有 φ(n)\varphi(n)φ(n) 的次数和整数系数。

证明中使用的定理

定理 如果算术函数 f,gf,gf,g 满足 f(n)=∏d∣ng(d)对于每个 n≥1,f(n) = \prod_{d\mid n} g(d)\quad\text{对于每个 }n\ge1,f(n)=∏d∣n​g(d)对于每个 n≥1, 则 g(n)=∑d∣nf(n/d)μ(d).g(n) = \sum_{d\mid n} f\bigl(n/d\bigr)^{\mu(d)}.g(n)=∑d∣n​f(n/d)μ(d)。

证明。假设 f(n)=∏d∣ng(d)f(n)=\prod_{d\mid n} g(d)f(n)=∏d∣n​g(d)。考虑 P:=∏d∣nf(n/d)μ(d).P := \prod_{d\mid n} f(n/d)^{\mu(d)}.P:=∏d∣n​f(n/d)μ(d)。插入 fff 的定义：P=∏d∣n(∏e∣n/dg(e))μ(d).P = \prod_{d\mid n} \Bigl(\prod_{e\mid n/d} g(e)\Bigr)^{\mu(d)}.P=∏d∣n​(∏e∣n/d​g(e))μ(d)。 重新索引：每个 de∣nde\mid nde∣n 的对 (d,e)(d,e)(d,e) 出现一次；写成 n=de⋅mn=de\cdot mn=de⋅m，其中 m=1m=1m=1。P=∏e∣ng(e)∑d∣n/eμ(d).P = \prod_{e\mid n} g(e)^{\sum_{d\mid n/e}\mu(d)}.P=∏e∣n​g(e)∑d∣n/e​μ(d)。 但是对于 m>1m>1m>1，∑d∣mμ(d)=0\sum_{d\mid m}\mu(d)=0∑d∣m​μ(d)=0，对于 m=1m=1m=1 则 =1=1=1。因此，除了 e=ne=ne=n 时，所有指数都消失，给出 P=g(n)P=g(n)P=g(n)。

定理 对于每个 n≥1n\ge1n≥1，Xn−1=∏d∣nΦd(X).X^n - 1 = \prod_{d\mid n} \Phi_d(X).Xn−1=∏d∣n​Φd​(X)。

证明。 nnn-th 本原根 ζ\zetaζ 也是 d∣nd\mid nd∣n 时的 ddd-th 根，因此 ζ\zetaζ 是右边乘积的根。两个多项式都是 nnn 次首一多项式，因此相等。

定理 对于 n≥1n\ge1n≥1 和 X≠±1X\neq \pm1X=±1,

Φn(X)=∏d∣n(Xn/d−1)μ(d)=∏d∣n(Xd−1)μ(n/d).\\Phi\_n(X) = \\prod\_{d\\mid n} \\bigl(X^{n/d} - 1\\bigr)^{\\mu(d)} = \\prod\_{d\\mid n} \\bigl(X^d - 1\\bigr)^{\\mu(n/d)}.

证明。将第一个定理应用于算术函数 f(n)=Xn−1f(n)=X^n-1f(n)=Xn−1。

主要定理

陈述。 对于每个 n≥1n\ge1n≥1，Φn(X)=Φrad(n)(Xn/rad(n)).\Phi_n(X) = \Phi_{\mathrm{rad}(n)}\bigl(X^{n/\mathrm{rad}(n)}\bigr)。

证明。 写成 r=rad(n)r=\mathrm{rad}(n)r=rad(n) 和 k=n/rk=n/rk=n/r (因此 k≥1k\ge1k≥1 且 gcd⁡(k,r)=1\gcd(k,r)=1gcd(k,r)=1)。

我们有 Φn(X)=∏d∣n(Xn/d−1)μ(d).\Phi_n(X) = \prod_{d\mid n} \bigl(X^{n/d} - 1\bigr)^{\mu(d)}.Φn​(X)=∏d∣n​(Xn/d−1)μ(d)。 因为只要 ddd 不是无平方的，μ(d)=0\mu(d)=0μ(d)=0，则唯一贡献的除数 ddd 是无平方的，即 d∣rd\mid rd∣r。用 (kr)/d(kr)/d(kr)/d 代替 n/dn/dn/d：

Φn(X)=∏d∣r(Xkr/d−1)μ(d)=∏d∣r((Xk)r/d−1)μ(d).\\Phi\_n(X) = \\prod\_{d\\mid r} \\bigl(X^{k r / d} - 1\\bigr)^{\\mu(d)} = \\prod\_{d\\mid r} \\bigl((X^k)^{r/d} - 1\\bigr)^{\\mu(d)}.

现在将第 3 个定理的公式与在 XkX^kXk 处评估的 Φr\Phi_rΦr​ 进行比较： Φr(Xk)=∏d∣r((Xk)r/d−1)μ(d).\Phi_r(X^k) = \prod_{d\mid r} \bigl((X^k)^{r/d} - 1\bigr)^{\mu(d)}.Φr​(Xk)=∏d∣r​((Xk)r/d−1)μ(d)。 因此 Φn(X)=Φr(Xk)=Φr(Xn/r)\Phi_n(X)=\Phi_r(X^k)=\Phi_r\bigl(X^{n/r}\bigr)，正如所要求的。

为了构建我们的新明文环，我们通过替换 Xk=bX^{k}=bXk=b 来将 Φm(X)\Phi_{m}(X)Φm​(X) 模 t(X)t(X)t(X) 化简。 因为 k∣(m/r)k\mid(m/r)k∣(m/r)，所以这种替换产生一个常数：

p=Φr(bm/(rk))∈Zp = \\Phi\_{r}\\bigl(b^{\\,m/(rk)}\\bigr)\\in\\mathbb{Z}

因此，联合理想 (Φm(X),t(X))⊂Z[X](\Phi_{m}(X),t(X))\subset\mathbb{Z}[X](Φm​(X),t(X))⊂Z[X] 崩溃为 (t(X),p)(t(X),p)(t(X),p)，得到：

Rp,t=Z\[X\]/(t(X),p)≅Zp\[X\]/(Xk−b)R\_{p,t} = \\mathbb{Z}\[X\]\\big/(t(X),p)\\;\\cong\\;\\mathbb{Z}\_{p}\[X\]\\big/(X^{k}-b)

引理： 设 m≥3m\ge3m≥3 且 r=rad⁡(m)r=\operatorname{rad}(m)r=rad(m)。选择 0<k<φ(m)0<k<\varphi(m)0<k<φ(m)，其中 k∣(m/r)k\mid(m/r)k∣(m/r)，并设 t(X)=Xk−bt(X)=X^{k}-bt(X)=Xk−b。对于 p=Φr(bm/(rk))p = \Phi_{r}\bigl(b^{m/(rk)}\bigr)p=Φr​(bm/(rk))，假设 ppp 是素数且 p∤mp\nmid mp∤m。写成 d=ord⁡m(p)d=\operatorname{ord}_{m}(p)d=ordm​(p)。

则 t(X)t(X)t(X) 在 Fp\mathbb{F}_{p}Fp​ 上分裂成 ℓ′=kd\ell' = \tfrac{k}{d}ℓ′=dk​ 个不同的 ddd 次不可约因子。 Galois 群是 G={x↦xi∣i≡1(modm/k)}\mathcal{G} = \{x\mapsto x^{i}\mid i\equiv1\pmod{m/k}\}G={x↦xi∣i≡1(modm/k)}。

为什么噪声保持小

通用 BFV 的关键优势来自于我们在新环中表示明文的方式。当加密 μ∈Rp,t\mu\in R_{p,t}μ∈Rp,t​ 时，我们使用关系 Xk=bX^{k}=bXk=b 来找到具有小系数的表示：

∥\[μ\]R∥∞≤b\\lVert\[\\mu\]\_{R}\\rVert\_{\\infty}\\le b

这是可能的，因为二项式关系允许我们将大幂“携带”成指数形式，从而使所有系数都以 b−1b-1b−1 为界。

经过 LLL 次乘法后，最坏情况的系数增长像 [公式]，从而给出深度界限：

L≲log⁡qlog⁡bL \\lesssim \\frac{\\log q}{\\log b}

由于 log⁡b≪log⁡t\log b \ll \log tlogb≪logt (我们选择 bbb 很小)，所以这大大改进了经典 BFV 的 log⁡q/log⁡t\log q / \log tlogq/logt 界限。二项式模数 t(X)=Xk−bt(X)=X^{k}-bt(X)=Xk−b 能够实现更大的乘法深度，而无需扩大密文素数 qqq。

通用 BFV 中的 SIMD 结构

有关 FHE 中 SIMD 操作的全面介绍，请参阅我们之前的帖子“一个密文，多个消息：FHE 中的 SIMD 操作"。

经典 BFV 享有 lll 个独立的 SIMD 插槽：

Rp=Zp\[X\]/(XN+1)=Zp\[X\]/(F1(X))×⋯×Zp\[X\]/(Fl(X))R\_p = \\mathbb{Z}\_p\[X\]/(X^{N}+1)
= \\mathbb{Z}\_{p}\[X\]\\big/(F\_{1}(X)\\big)
\\times
\\cdots
\\times
\\mathbb{Z}\_{p}\[X\]\\big/(F\_{l}(X)\\big)

添加二项式关系 Xk=bX^{k}=bXk=b 从根本上改变了这种结构。我们可以通过分槽思考来理解效果：

对于每个槽，我们“将 t(X)t(X)t(X) 的商”局部应用：

1. 评估 在生成该槽的单位根 α\alphaα 处的 t(X)t(X)t(X)
2. 通过理想 (t(α))(t(\alpha))(t(α)) 商 该插槽的因子环

这会产生两种可能性：

因此，一个 当且仅当 它的单位根 α\alphaα 是 bbb 的 kkk-th 根时，一个槽才能幸存。计算这些根会产生精确的 kd\tfrac{k}{d}dk​ 个幸存槽，每个槽都在 Fpd\mathbb{F}_{p^{d}}Fpd​ 上运行。

将 GBFV 视为经典 BFV 的子空间

可以通过辅助素数 p=Φr(bm/(rk))p = \Phi_r\bigl(b^{\,m/(rk)}\bigr)p=Φr​(bm/(rk)) 来理解通用 BFV 和经典 BFV 之间的关系。

由于 ppp 位于理想 (Φm(X),t(X))(\Phi_m(X),t(X))(Φm​(X),t(X)) 中，我们可以将其表示为：

a(X)Φm(X)+b(X)t(X)=pa(X)\\,\\Phi\_m(X) + b(X)\\,t(X) = p

其中 a(X)a(X)a(X) 和 b(X)b(X)b(X) 是整数多项式。模 Φm\Phi_mΦm​ 化简，这变为：

p=β⋅t(X)p = \beta \cdot t(X)p=β⋅t(X)

其中 β\betaβ 是模 Φm(X)\Phi_m(X)Φm​(X) 化简的 b(X)b(X)b(X)。这给了我们基本关系：(p)=(β)⋅(t)(p) = (\beta) \cdot (t)(p)=(β)⋅(t) 作为 RRR 中的理想。

在商环 Rp=R/(p)R_p = R/(p)Rp​=R/(p) 中，我们有 p≡0p \equiv 0p≡0，这意味着：

0=p=β⋅t(X)0 = p = \\beta \\cdot t(X)

由于每个槽的行为都像一个域，因此 β\betaβ 或 ttt 中必须恰好一个在每个槽中为零：

通过中国剩余定理：

Rp≅R/(β)×R/(t)=Rβ×RtR_p \cong R/(\beta) \times R/(t) = R_{\beta} \times R_{t}Rp​≅R/(β)×R/(t)=Rβ​×Rt​

通用 BFV 在这里做出了关键选择：它仅保留 RtR_tRt​ 块，消除了所有 β\betaβ-槽，并且仅保留 t(X)=0t(X) = 0t(X)=0 的 ttt-槽。

Hensel 提升槽

某些应用程序，尤其是自举，需要以素数 ppp 的幂 pep^{e}pe 定义的明文空间，而不仅仅是一个素数 ppp。

我们的二项式环构造可以无缝地适应此要求。Hensel 引理允许我们提升分解：

Φm(X)=β(X)t(X)(modp)\\Phi\_{m}(X)=\\beta(X)\\,t(X)\\pmod{p}

到每一个幂 pep^{e}pe，而不会改变 CRT 槽结构。

我们从域级别的插槽 Fpd\mathbb{F}_{p^{d}}Fpd​ 过渡到 Galois 环：

R/(Φm,pe,t)≅∏i∈SGR ⁣(pe,d)R / \\bigl(\\Phi\_m,\\,p^{e},\\,t\\bigr)
\\;\\cong\\;
\\prod\_{i \\in S} \\mathrm{GR}\\!\\left(p^{e},\\,d\\right)

这保留了相同的 kd\tfrac{k}{d}dk​ 个 SIMD 通道，同时提供了模 pep^{e}pe 的系数。Hensel 提升提供了自举所需的 ppp-adic 精度，但没有引入额外的噪声。刷新密文后，我们可以减小到模数 ppp 并继续进行 GBFV 计算，同时保持其所有低噪声优势。

自举通用 BFV

自举通用 BFV 的主要挑战源于其受限的结构：GBFV 在子环 R/(p,t)⊂R/(p)R/(p,t) \subset R/(p)R/(p,t)⊂R/(p) 中运行，这严重限制了可用于自举的自同构数量。

核心问题：缺少旋转

标准 BFV 自举依赖于对完整自同构群的访问：

{σℓ:X↦Xℓ∣ℓ∈(Z/mZ)×}\\{\\sigma\_\\ell : X \\mapsto X^\\ell \\mid \\ell \\in (\\mathbb{Z}/m\\mathbb{Z})^\\times\\}

这些旋转对于以下各项至关重要：

• 数字提取中的分槽排列
• 婴儿步/巨人步线性变换
• 迹映射和对角化

但是，在 t(X)=Xk−bt(X) = X^k - bt(X)=Xk−b 的 GBFV 的商环 R/(p,t)R/(p,t)R/(p,t) 中，只有保留理想 (t)(t)(t) 的旋转才有效。这大大减少了可用的自同构群：

G={σℓ:ℓ≡1(modm/k)}\mathcal{G} = \{\sigma_\ell : \ell \equiv 1 \pmod{m/k}\}G={σℓ​:ℓ≡1(modm/k)}

我们只能在 RtR_tRt​ 块中旋转，我们无法访问会在完整 BFV 环的 RtR_tRt​ 和 RβR_\betaRβ​ 组件之间移动的旋转。

解决方案：提升、打包、自举、投影

关键的见解是临时将 GBFV 密文提升回完整 BFV 环 R/(p)R/(p)R/(p), 在那里所有必要的旋转都可用。

第 1 步：打包多个 GBFV 密文

我们不是自举单个 GBFV 密文（这将浪费 RβR_\betaRβ​ 槽），而是将多个 GBFV 密文打包到一个 BFV 密文中。这确保了每个 BFV 槽都包含来自某个 GBFV 密文的有意义的数据，从而最大限度地提高了自举操作的效率。

第 2 步：执行标准 BFV 自举

在所有槽都填充后，我们运行标准的 BFV 自举过程。自举操作与我们的打包方案无关，它仅刷新完整 R/(p)R/(p)R/(p) 环中的所有槽，所有必需的旋转都在其中可用。

第 3 步：投影回和解包

要恢复单个 GBFV 密文：

1. 使用商映射将刷新的 BFV 密文 投影 回 R/(p,t)R/(p,t)R/(p,t)
2. 根据需要 旋转 以提取所需的特定 GBFV 实例

投影自然会消除 RβR_\betaRβ​ 块，同时保留 RtR_tRt​ 块。通过在解包期间执行适当的旋转，我们可以检索打包到原始 BFV 密文中的任何 GBFV 密文。

通过同时批量自举多个密文，此方法将 GBFV 的根本局限性（其受限的自同构群）转变为优势。

具体例子

让我们通过一个具体的示例来说明实践中的理论。

参数

• 分圆指数（Cyclotomic index）： m=8m=8m=8，所以 Φ8(X)=X4+1\Phi_8(X)=X^4+1Φ8​(X)=X4+1
• 二项式（Binomial）： t(X)=X2−bt(X)=X^2-bt(X)=X2−b，其中 b=4b=4b=4 且 k=2k=2k=2
• 根基（Radical）： r=rad(m)=2r=\mathrm{rad}(m)=2r=rad(m)=2
• 明文素数（Plaintext prime）： p=Φr ⁣(bm/(rk))=Φ2(48/(2⋅2))=Φ2(42)=Φ2(16)=16+1=17p = \Phi_{r}\!\bigl(b^{\,m/(rk)}\bigr) = \Phi_{2}(4^{\,8/(2\cdot2)}) = \Phi_2(4^2)=\Phi_2(16)=16+1=17p=Φr​(bm/(rk))=Φ2​(48/(2⋅2))=Φ2​(42)=Φ2​(16)=16+1=17
• 剩余度（Residue degree）： 因为 p≡1(modm)p\equiv1\pmod{m}p≡1(modm)，所以我们有 d=ord⁡m(p)=1d=\operatorname{ord}_m(p)=1d=ordm​(p)=1
• BFV槽位（BFV slots）： n=φ(m)/d=φ(8)/1=4n=\varphi(m)/d=\varphi(8)/1=4n=φ(m)/d=φ(8)/1=4

经典的BFV槽位结构（Classical BFV Slot Structure）

我们工作在：

Rp=Z[X]/(Φ8(X),p)≅F17[X]/(X4+1)R_p = \mathbb{Z}[X] / \bigl(\Phi_8(X),p\bigr) \cong \mathbb{F}_{17}[X] / (X^4+1)Rp​=Z[X]/(Φ8​(X),p)≅F17​[X]/(X4+1)

存在一个本原的888次单位根 α=2∈F17\alpha=2\in\mathbb{F}_{17}α=2∈F17​，因为 28≡12^8\equiv128≡1 且 24≡−1(mod17)2^4\equiv-1\pmod{17}24≡−1(mod17)。

四个 BFV槽位（BFV slots） 对应于 αj\alpha^jαj 处的求值，其中 j∈{1,3,5,7}=Z8∗j\in\{1,3,5,7\}=\mathbb{Z}_8^{*}j∈{1,3,5,7}=Z8∗​：

f(X)⟼(f(α),f(α3),f(α5),f(α7))∈F174f(X) \longmapsto \bigl(f(\alpha), f(\alpha^3), f(\alpha^5), f(\alpha^7)\bigr)\in\mathbb{F}_{17}^4f(X)⟼(f(α),f(α3),f(α5),f(α7))∈F174​

等价地，我们有完全分解：

X4+1=(X−2)(X−8)(X−15)(X−9)X^4+1 = (X-2)(X-8)(X-15)(X-9)X4+1=(X−2)(X−8)(X−15)(X−9)

确定槽位存活（Determining Slot Survival）

为了确定在对 t(X)t(X)t(X) 取商后哪些槽位得以保留，我们使用严格的逐个槽位分析：对 t(X)t(X)t(X) 取商会消除那些 t(α)≠0t(\alpha)\neq0t(α)=0 的 BFV 槽位，并保留那些 t(α)=0t(\alpha)=0t(α)=0 的槽位。

步骤 1： 约简 t(X)=X2−4mod17t(X) = X^2-4 \mod 17t(X)=X2−4mod17 并在四个根 α∈{2,8,15,9}\alpha\in\{2,8,15,9\}α∈{2,8,15,9}处求值：

t‾(X)=X2−4,t‾⟼(t(2),t(8),t(15),t(9))=(0,9,0,9)\overline{t}(X)=X^2-4, \quad \overline{t} \longmapsto \bigl(t(2), t(8), t(15), t(9)\bigr) = (0, 9, 0, 9)t(X)=X2−4,t⟼(t(2),t(8),t(15),t(9))=(0,9,0,9)

步骤 2： 根据中国剩余定理，由 t‾\overline{t}t 生成的主理想对应于：

⟨t‾⟩⟷⟨t(2)⟩×⟨t(8)⟩×⟨t(15)⟩×⟨t(9)⟩⊂F174\langle \overline{t}\rangle \longleftrightarrow \langle t(2)\rangle \times \langle t(8)\rangle \times \langle t(15)\rangle \times \langle t(9)\rangle \subset \mathbb{F}_{17}^4⟨t⟩⟷⟨t(2)⟩×⟨t(8)⟩×⟨t(15)⟩×⟨t(9)⟩⊂F174​

步骤 3： 在一个域 FFF 中，如果 a=0a=0a=0，则有 ⟨a⟩={0}\langle a\rangle=\{0\}⟨a⟩={0}，如果 a≠0a\neq0a=0，则有 ⟨a⟩=F\langle a\rangle=F⟨a⟩=F。因此：

⟨t(2)⟩={0},⟨t(15)⟩={0},⟨t(8)⟩=F17,⟨t(9)⟩=F17\langle t(2)\rangle=\{0\}, \quad \langle t(15)\rangle=\{0\}, \quad \langle t(8)\rangle=\mathbb{F}_{17}, \quad \langle t(9)\rangle=\mathbb{F}_{17}⟨t(2)⟩={0},⟨t(15)⟩={0},⟨t(8)⟩=F17​,⟨t(9)⟩=F17​

所以总的来说：

⟨t‾⟩⟷{0}×F17×{0}×F17\langle \overline{t}\rangle \longleftrightarrow \{0\}\times \mathbb{F}_{17}\times \{0\}\times \mathbb{F}_{17}⟨t⟩⟷{0}×F17​×{0}×F17​

步骤 4： 逐坐标取商：

Rp/⟨t‾⟩≅(F17/{0})×(F17/F17)×(F17/{0})×(F17/F17)≅F17×0×F17×0R_p / \langle \overline{t}\rangle \cong (\mathbb{F}_{17}/\{0\})\times(\mathbb{F}_{17}/\mathbb{F}_{17})\times (\mathbb{F}_{17}/\{0\})\times(\mathbb{F}_{17}/\mathbb{F}_{17}) \cong \mathbb{F}_{17}\times 0 \times \mathbb{F}_{17}\times 0Rp​/⟨t⟩≅(F17​/{0})×(F17​/F17​)×(F17​/{0})×(F17​/F17​)≅F17​×0×F17​×0

这表明槽位 1 和 3 存活（对应于根 α=2\alpha=2α=2 和 α5=15\alpha^5=15α5=15），而槽位 2 和 4 被消除。

GBFV 中可用的自同构（Available Automorphisms in GBFV）

经典的 BFV 自同构是 σi:X↦Xi\sigma_i: X\mapsto X^{\,i}σi​:X↦Xi，其中 i∈Z8∗={1,3,5,7}i\in\mathbb{Z}_8^{*}=\{1,3,5,7\}i∈Z8∗​={1,3,5,7}。

在对 t(X)t(X)t(X) 取商后，只有那些保留 (t)(t)(t)-块的自同构仍然有效。对于 t(X)=Xk−bt(X)=X^k-bt(X)=Xk−b，存活的子群是：

{i∈(Z/mZ)∗:i≡1(modm/k)}\{i\in(\mathbb{Z}/m\mathbb{Z})^{*} : i\equiv1\pmod{m/k}\}{i∈(Z/mZ)∗:i≡1(modm/k)}

这里 m/k=8/2=4m/k=8/2=4m/k=8/2=4，所以 i∈{1,5}i\in\{1,5\}i∈{1,5}。

确实，σ5\sigma_5σ5​ 交换了两个存活的槽位，而 σ3\sigma_3σ3​ 和 σ7\sigma_7σ7​ 会将存活的槽位发送到被消除的位置（使它们在 R/(p,t)R/(p,t)R/(p,t) 中无效）。

m = 8
p = 17
k = 2
b = 4

Fp       = GF(p)          # the base field F_p
R.<x>    = Fp[]           # polynomial ring F_p[x]
Phi      = cyclotomic_polynomial(m).change_ring(Fp)   # X^4 + 1 in F_p[x]
Rp       = R.quotient(Phi, 'Xbar')                    # Rp = F_p[x]/(Phi_m)
Xbar     = Rp.gen()

### Find a primitive m-th root of unity α in F_p (requires m | p-1)
g = Fp.multiplicative_generator()       # generator of F_p^*
alpha = g^((p - 1)//m)
assert alpha.multiplicative_order() == m, "No primitive m-th root in F_p; need extension field."

print("\nFound primitive %d-th root α in F_%d:" % (m, p), int(alpha))

### Classical BFV slot exponents: units mod m
slot_exps = [j for j in range(1, m) if gcd(j, m) == 1]
alphas    = [alpha^e for e in slot_exps]
print("\nBFV slot points α^j for j in (Z/%dZ)^* = %s:" % (m, slot_exps),
      [int(a) for a in alphas])

### Factorization over F_p (use Phi for clarity)
print("\nFactorization of Phi_%d(X) over F_%d:" % (m, p))
fac = Phi.factor()
print(" ", fac)

### Extract linear roots from the factorization and verify they match {alpha^j}
roots = []
for f, e in fac:              # linear factors f = x - r
    if f.degree() != 1:
        raise RuntimeError("Phi_m did not split linearly over F_p; need extension field.")
    r = -f[0]                 # r = -constant term
    roots.append(r)

### Check sets match (as multisets)
assert set(roots) == set(alphas), "Factorization roots != {alpha^j : j∈(Z/mZ)^*}"
print("Roots (some order):", [int(r) for r in roots])

### Survival under t(X) = X^k - b (here k=2, b=4)
t = x^k - b

t_vals = [t(a) for a in alphas]
survivor_mask = [(tv == Fp(0)) for tv in t_vals]  # survive iff t(α)=0

print("\nEvaluate t(X)=X^%d-%d at slot points:" % (k, b))
for j, a, tv in zip(slot_exps, alphas, t_vals):
    status = "SURVIVES" if tv == 0 else "KILLED"
    print(f"  t(α^{j}) = t({int(a)}) = {int(tv):2d}  ->  {status}")

结论（Conclusion）

具有多项式商的广义 BFV 代表了实用全同态加密的一项重大进展。通过将经典的整数明文模数替换为精心选择的二项式关系 t(X)=Xk−bt(X) = X^k - bt(X)=Xk−b，我们摆脱了限制经典 BFV 的数据打包和乘法深度之间的根本权衡。

关键见解是：

1. 噪声控制（Noise control）： 二项式关系使得系数表示以 bbb 为界，导致噪声增长 ∼bL\sim b^L∼bL 而不是 ∼tL\sim t^L∼tL
2. 深度缩放（Depth scaling）： 乘法深度缩放为 log⁡q/log⁡b\log q / \log blogq/logb 而不是 log⁡q/log⁡t\log q / \log tlogq/logt，当 b≪tb \ll tb≪t 时，效果显着提高
3. 结构化的槽位（Structured slots）： 商构造自然地创建了一个具有良好理解的代数结构的经典 BFV 槽位的子空间
4. 引导解决方案（Bootstrapping solution）： 临时提升到完整的 BFV 环可以实现对多个 GBFV 密文进行批量引导

这些进展为既需要高吞吐量又需要深度计算的应用开辟了新的可能性，使 FHE 更加接近在保护隐私的机器学习、安全数据库操作和加密分析中的实际部署。

广义 BFV 构造表明，密码方案中的基本限制有时可以通过以下方式克服：不是放弃现有框架，而是认识并利用它们包含的更深层次的代数结构。

致谢（Acknowledgments）

这项工作建立在两篇关键论文中提出的基础研究之上，这两篇论文介绍并开发了广义 BFV 框架。 我们感谢 "用于分圆素数模的全同态加密" 和 "MatriGear：通过优化的 HE 封装，利用可扩展的素数域加速经过身份验证的矩阵三重生成" 的作者所做的贡献。 他们在多项式商构造方面的创新方法和对噪声行为的严格分析为实现本次阐述提供了理论基础。 这些工作中提出的数学见解和实践考虑显着推动了全同态加密领域的发展，并为保护隐私的计算开辟了新的可能性。

• 原文链接： hexens.io/blog/gbfv...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～