本文深入探讨了广义BFV(Brakerski-Fan-Vercauteren)同态加密方案,该方案通过使用多项式商环代替传统的整数明文模数,突破了经典BFV方案中数据吞吐量和计算深度之间的限制。该方案在噪声控制、深度缩放、结构化插槽以及引导解决方案等方面实现了显著改进,为隐私保护机器学习、安全数据库操作和加密分析等应用开辟了新的可能性。
全同态加密 (FHE) 承诺解锁对加密数据的计算,但实际方案面临着限制其现实适用性的根本局限性。BFV (Brakerski-Fan-Vercauteren) 方案是使用最广泛的 FHE 构造之一,它体现了一个塑造了该领域的关键权衡:你可以每个密文打包大量数据,或者执行深度计算,但不能同时进行。
这种限制不仅仅是一个技术上的不便,它从根本上限制了 FHE 可以服务的应用程序类型。加密数据上的机器学习推断、安全数据库查询和保护隐私的分析都需要高数据吞吐量和大量的计算深度。然而,经典的 BFV 迫使从业者在这些需求之间做出令人不舒服的选择。
通用 BFV 方案的最新进展为摆脱这种权衡提供了一条途径。通过用精心选择的多项式商代替传统的整数明文模数,这些构造可以保持大的明文空间,同时实现与密文模数成比例的乘法深度,而不是与明文大小成反比。
本文探讨了 $t(X)=X^k - b$ 的 quotient-by-$t(X)=X^k - b$ 构造如何摆脱经典 BFV 的根本局限性,考察了这种方法的数学基础和实际影响。
设 $N=2^n$ 为分圆指数。经典 BFV 方案在以下范围内运行:
核心操作遵循熟悉的模式:
KeyGen: 选择: $a \leftarrow R_q$, $s \leftarrow R_2$, $e \leftarrow \chi$; 设置 $b = -(as + e) \in R_q$。公钥 $(b, a)$;私钥 $s$。
加密 $m \in \mathbb{Z}_t[X]/(X^{N}+1)$:
$$ ct=\bigl( [ \Delta m + as + e]_q,\; -a\bigr)\in R_q^{2} $$
解密 $\mathrm{ct}=(c{0},c{1})$:
$$ m = \Bigl\lfloor \frac{c{0}+c{1}s}{\Delta} \Bigr\rceil_{t} $$
经典 BFV 的核心限制源于其噪声增长行为。增加明文模数 $t$ 以每个密文打包更多数据会带来高昂的代价:最大乘法深度大致受 $\log q / \log t$ 的限制,因此更大的明文空间会直接降低计算能力。为了在增加 $t$ 的同时保持深度,我们必须成比例地增加 $q$,但是更大的密文模数会使每个操作更加昂贵:密钥需要更多内存,多项式算术需要更慢的 NTT,以及更昂贵的密钥切换。
结果是一个不可避免的选择:具有大 $t$ 的高吞吐量应用会牺牲乘法深度,而深度计算则被限制在小的明文空间中。
有关基础 BFV 构造和安全性分析,请参阅“某种程度上实用的全同态加密"
突破来自于认识到明文模数不必是整数。我们可以使用 $t(X)=X^k - b$ 形式的多项式商构造明文环,而不是对 $t \in \mathbb{Z}$ 取模,其中 $b$ 是一个小整数,$k$ 划分了分圆多项式的某些结构参数。
这种看似简单的改变对噪声增长和乘法深度产生了深远的影响,为摆脱经典 BFV 的根本局限性提供了一条途径。
我们保持密文环与经典 BFV 完全相同,使用一个 NTT 友好的素数:
$$ R_q = \mathbb{Z}_q[X]\big/(X^{N}+1), \qquad q\equiv1\pmod{2N} $$
对于明文环,我们引入一个 二项式 关系。 写成 $m=2N$,并设:
我们利用分圆多项式的经典恒等式:
$$ \Phi{m}(X)=\Phi{r}\bigl(X^{\,m/r}\bigr) $$
证明
$\mathrm{rad}(n) := \prod_{p \mid n} p$ (划分 $n$ 的不同素数的乘积);等效地,$\mathrm{rad}(n)$ 是 $n$ 的最大无平方因子。
Euler totient $\varphi(n) = |{1 \le k \le n : \gcd(k,n) = 1}|$。
莫比乌斯函数 $\mu(1)=1$;如果 $n$ 可被一个平方数整除,则 $\mu(n)=0$; 如果 $n$ 是 $r$ 个不同素数的乘积,则 $\mu(n)=(-1)^r$。
$n$-th 分圆多项式 $\displaystyle \Phin(X) := \prod{1 \le k \le n \ \gcd(k,n)=1}\bigl(X - e^{2\pi i k/n}\bigr)$ 其根是 1 的本原 $n$-th 根的唯一首一多项式。它具有 $\varphi(n)$ 的次数和整数系数。
定理 如果算术函数 $f,g$ 满足 $f(n) = \prod{d\mid n} g(d)\quad\text{对于每个 }n\ge1$, 则 $g(n) = \sum{d\mid n} f\bigl(n/d\bigr)^{\mu(d)}$。
证明。假设 $f(n)=\prod{d\mid n} g(d)$。考虑 $P := \prod{d\mid n} f(n/d)^{\mu(d)}$。插入 $f$ 的定义:$P = \prod{d\mid n} \Bigl(\prod{e\mid n/d} g(e)\Bigr)^{\mu(d)}$。 重新索引:每个 $de\mid n$ 的对 $(d,e)$ 出现一次;写成 $n=de\cdot m$,其中 $m=1$。$P = \prod{e\mid n} g(e)^{\sum{d\mid n/e}\mu(d)}$。 但是对于 $m>1$,$\sum_{d\mid m}\mu(d)=0$,对于 $m=1$ 则 $=1$。因此,除了 $e=n$ 时,所有指数都消失,给出 $P=g(n)$。
定理 对于每个 $n\ge1$, $X^n - 1 = \prod_{d\mid n} \Phi_d(X)$。
证明。 $n$-th 本原根 $\zeta$ 也是 $d\mid n$ 时的 $d$-th 根,因此 $\zeta$ 是右边乘积的根。两个多项式都是 $n$ 次首一多项式,因此相等。
定理 对于 $n\ge1$ 和 $X\neq \pm1$,
$$ \Phin(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)=X^n-1$。
陈述。 对于每个 $n\ge1$, $\Phin(X) = \Phi{\mathrm{rad}(n)}\bigl(X^{n/\mathrm{rad}(n)}\bigr)$。
证明。 写成 $r=\mathrm{rad}(n)$ 和 $k=n/r$ (因此 $k\ge1$ 且 $\gcd(k,r)=1$)。
我们有 $\Phin(X) = \prod{d\mid n} \bigl(X^{n/d} - 1\bigr)^{\mu(d)}$。 因为只要 $d$ 不是无平方的,$\mu(d)=0$,则唯一贡献的除数 $d$ 是无平方的,即 $d\mid r$。用 $(kr)/d$ 代替 $n/d$:
$$ \Phin(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 个定理的公式与在 $X^k$ 处评估的 $\Phi_r$ 进行比较: $\Phir(X^k) = \prod{d\mid r} \bigl((X^k)^{r/d} - 1\bigr)^{\mu(d)}$。 因此 $\Phi_n(X)=\Phi_r(X^k)=\Phi_r\bigl(X^{n/r}\bigr)$,正如所要求的。
为了构建我们的新明文环,我们通过替换 $X^{k}=b$ 来将 $\Phi_{m}(X)$ 模 $t(X)$ 化简。 因为 $k\mid(m/r)$,所以这种替换产生一个常数:
$$ p = \Phi_{r}\bigl(b^{\,m/(rk)}\bigr)\in\mathbb{Z} $$
因此,联合理想 $(\Phi_{m}(X),t(X))\subset\mathbb{Z}[X]$ 崩溃为 $(t(X),p)$,得到:
$$ R{p,t} = \mathbb{Z}[X]\big/(t(X),p)\;\cong\;\mathbb{Z}{p}[X]\big/(X^{k}-b) $$
引理: 设 $m\ge3$ 且 $r=\operatorname{rad}(m)$。选择 $0<k<\varphi(m)$,其中 $k\mid(m/r)$,并设 $t(X)=X^{k}-b$。对于 $p = \Phi{r}\bigl(b^{m/(rk)}\bigr)$,假设 $p$ 是素数且 $p\nmid m$。写成 $d=\operatorname{ord}{m}(p)$。
则 $t(X)$ 在 $\mathbb{F}_{p}$ 上分裂成 $\ell' = \tfrac{k}{d}$ 个不同的 $d$ 次不可约因子。 Galois 群是 $\mathcal{G} = {x\mapsto x^{i}\mid i\equiv1\pmod{m/k}}$。
通用 BFV 的关键优势来自于我们在新环中表示明文的方式。当加密 $\mu\in R_{p,t}$ 时,我们使用关系 $X^{k}=b$ 来找到具有小系数的表示:
$$ |[\mu]{R}|{\infty} \le b $$
这是可能的,因为二项式关系允许我们将大幂“携带”成指数形式,从而使所有系数都以 $b-1$ 为界。
经过 L 次乘法后,最坏情况的系数增长像 [公式],从而给出深度界限:
$$ L \lesssim \frac{\log q}{\log b} $$
由于 $\log b \ll \log t$ (我们选择 $b$ 很小),所以这大大改进了经典 BFV 的 $\log q / \log t$ 界限。二项式模数 $t(X)=X^{k}-b$ 能够实现更大的乘法深度,而无需扩大密文素数 $q$。
有关 FHE 中 SIMD 操作的全面介绍,请参阅我们之前的帖子“一个密文,多个消息:FHE 中的 SIMD 操作"。
经典 BFV 享有 $l$ 个独立的 SIMD 插槽:
$$ 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) $$
添加二项式关系 $X^{k}=b$ 从根本上改变了这种结构。我们可以通过分槽思考来理解效果:
对于每个槽,我们“将 $t(X)$ 的商”局部应用:
这会产生两种可能性:
| $t(\alpha)$ 上的条件 | 产生的理想 | 对槽的影响 |
|---|---|---|
| $t(\alpha)=0$ | 零理想 $(0)$ | 槽保持不变 |
| $t(\alpha)\neq0$ | 整个环 $(1)$ | 槽被完全消除 |
因此,一个 当且仅当 它的单位根 $\alpha$ 是 $b$ 的 $k$-th 根时,一个槽才能幸存。计算这些根会产生精确的 $\tfrac{k}{d}$ 个幸存槽,每个槽都在 $\mathbb{F}_{p^{d}}$ 上运行。
可以通过辅助素数 $p = \Phi_{r}\bigl(b^{\,m/(rk)}\bigr)$ 来理解通用 BFV 和经典 BFV 之间的关系。
由于 $p$ 位于理想 $(\Phi_{m}(X),t(X))$ 中,我们可以将其表示为:
$$ a(X)\,\Phi_m(X) + b(X)\,t(X) = p $$
其中 $a(X)$ 和 $b(X)$ 是整数多项式。模 $\Phi_m$ 化简,这变为:
$p = \beta \cdot t(X)$
其中 $\beta$ 是模 $\Phi_m(X)$ 化简的 $b(X)$。这给了我们基本关系:$(p) = (\beta) \cdot (t)$ 作为 $R$ 中的理想。
在商环 $R_p = R/(p)$ 中,我们有 $p \equiv 0$,这意味着:
$$ 0 = p = \beta \cdot t(X) $$
由于每个槽的行为都像一个域,因此 $\beta$ 或 $t$ 中必须恰好一个在每个槽中为零:
| 槽类型 | 条件 | 理想 |
|---|---|---|
| $\beta$-槽 | $\beta=0$, $t\neq0$ | $(\beta)$ |
| $t$-槽 | $t=0$, $\beta\neq0$ | $(t)$ |
通过中国剩余定理:
$Rp \cong R/(\beta) \times R/(t) = R{\beta} \times R_{t}$
通用 BFV 在这里做出了关键选择:它仅保留 $R_t$ 块,消除了所有 $\beta$-槽,并且仅保留 $t(X) = 0$ 的 $t$-槽。

某些应用程序,尤其是自举,需要以素数 $p$ 的幂 $p^{e}$ 定义的明文空间,而不仅仅是一个素数 $p$。
我们的二项式环构造可以无缝地适应此要求。Hensel 引理允许我们提升分解:
$$ \Phi_{m}(X)=\beta(X)\,t(X)\pmod{p} $$
到每一个幂 $p^{e}$,而不会改变 CRT 槽结构。
我们从域级别的插槽 $\mathbb{F}_{p^{d}}$ 过渡到 Galois 环:
$$ R / \bigl(\Phim,\,p^{e},\,t\bigr) \;\cong\; \prod{i \in S} \mathrm{GR}!\left(p^{e},\,d\right) $$
这保留了相同的 $\tfrac{k}{d}$ 个 SIMD 通道,同时提供了模 $p^{e}$ 的系数。Hensel 提升提供了自举所需的 $p$-adic 精度,但没有引入额外的噪声。刷新密文后,我们可以减小到模数 $p$ 并继续进行 GBFV 计算,同时保持其所有低噪声优势。
自举通用 BFV 的主要挑战源于其受限的结构:GBFV 在子环 $R/(p,t) \subset R/(p)$ 中运行,这严重限制了可用于自举的自同构数量。
标准 BFV 自举依赖于对完整自同构群的访问:
$$ {\sigma_\ell : X \mapsto X^\ell \mid \ell \in (\mathbb{Z}/m\mathbb{Z})^\times} $$
这些旋转对于以下各项至关重要:
但是,在 $t(X) = X^k - b$ 的 GBFV 的商环 $R/(p,t)$ 中,只有保留理想 $(t)$ 的旋转才有效。这大大减少了可用的自同构群:
$\mathcal{G} = {\sigma_\ell : \ell \equiv 1 \pmod{m/k}}$
我们只能在 $R_t$ 块中旋转,我们无法访问会在完整 BFV 环的 $Rt$ 和 $R\beta$ 组件之间移动的旋转。
关键的见解是临时将 GBFV 密文提升回完整 BFV 环 $R/(p)$, 在那里所有必要的旋转都可用。
我们不是自举单个 GBFV 密文(这将浪费 $R_\beta$ 槽),而是将多个 GBFV 密文打包到一个 BFV 密文中。这确保了每个 BFV 槽都包含来自某个 GBFV 密文的有意义的数据,从而最大限度地提高了自举操作的效率。
在所有槽都填充后,我们运行标准的 BFV 自举过程。自举操作与我们的打包方案无关,它仅刷新完整 $R/(p)$ 环中的所有槽,所有必需的旋转都在其中可用。
要恢复单个 GBFV 密文:
投影自然会消除 $R_\beta$ 块,同时保留 $R_t$ 块。通过在解包期间执行适当的旋转,我们可以检索打包到原始 BFV 密文中的任何 GBFV 密文。
通过同时批量自举多个密文,此方法将 GBFV 的根本局限性(其受限的自同构群)转变为优势。

让我们通过一个具体的示例来说明实践中的理论。
我们工作在:
$R_p = \mathbb{Z}[X] / \bigl(\Phi8(X),p\bigr) \cong \mathbb{F}{17}[X] / (X^4+1)$
存在一个本原的8次单位根 $\alpha=2\in\mathbb{F}_{17}$,因为 $2^8\equiv1$ 且 $2^4\equiv-1\pmod{17}$。
四个 BFV槽位(BFV slots) 对应于 $\alpha^j$ 处的求值,其中 $j\in{1,3,5,7}=\mathbb{Z}_8^{*}$:
$f(X) \longmapsto \bigl(f(\alpha), f(\alpha^3), f(\alpha^5), f(\alpha^7)\bigr)\in\mathbb{F}_{17}^4$
等价地,我们有完全分解:
$X^4+1 = (X-2)(X-8)(X-15)(X-9)$
为了确定在对 $t(X)$ 取商后哪些槽位得以保留,我们使用严格的逐个槽位分析:对 $t(X)$ 取商会消除那些 $t(\alpha)\neq0$ 的 BFV 槽位,并保留那些 $t(\alpha)=0$ 的槽位。
步骤 1: 约简 $t(X) = X^2-4 \mod 17$ 并在四个根 $\alpha\in{2,8,15,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)$
步骤 2: 根据中国剩余定理,由 $\overline{t}$ 生成的主理想对应于:
$\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$
步骤 3: 在一个域 $F$ 中,如果 $a=0$,则有 $\langle a\rangle={0}$,如果 $a\neq0$,则有 $\langle a\rangle=F$。因此:
$\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}$
所以总的来说:
$\langle \overline{t}\rangle \longleftrightarrow {0}\times \mathbb{F}{17}\times {0}\times \mathbb{F}{17}$
步骤 4: 逐坐标取商:
$Rp / \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 0$
这表明槽位 1 和 3 存活(对应于根 $\alpha=2$ 和 $\alpha^5=15$),而槽位 2 和 4 被消除。
经典的 BFV 自同构是 $\sigma_i: X\mapsto X^{\,i}$,其中 $i\in\mathbb{Z}_8^{*}={1,3,5,7}$。
在对 $t(X)$ 取商后,只有那些保留 (t)(t)(t)-块的自同构仍然有效。对于 $t(X)=X^k-b$,存活的子群是:
${i\in(\mathbb{Z}/m\mathbb{Z})^{*} : i\equiv1\pmod{m/k}}$
这里 $m/k=8/2=4$,所以 $i\in{1,5}$。
确实,$\sigma_5$ 交换了两个存活的槽位,而 $\sigma_3$ 和 $\sigma_7$ 会将存活的槽位发送到被消除的位置(使它们在 $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}")
具有多项式商的广义 BFV 代表了实用全同态加密的一项重大进展。通过将经典的整数明文模数替换为精心选择的二项式关系 $t(X) = X^k - b$,我们摆脱了限制经典 BFV 的数据打包和乘法深度之间的根本权衡。
关键见解是:
这些进展为既需要高吞吐量又需要深度计算的应用开辟了新的可能性,使 FHE 更加接近在保护隐私的机器学习、安全数据库操作和加密分析中的实际部署。
广义 BFV 构造表明,密码方案中的基本限制有时可以通过以下方式克服:不是放弃现有框架,而是认识并利用它们包含的更深层次的代数结构。
这项工作建立在两篇关键论文中提出的基础研究之上,这两篇论文介绍并开发了广义 BFV 框架。 我们感谢 "用于分圆素数模的全同态加密" 和 "MatriGear:通过优化的 HE 封装,利用可扩展的素数域加速经过身份验证的矩阵三重生成" 的作者所做的贡献。 他们在多项式商构造方面的创新方法和对噪声行为的严格分析为实现本次阐述提供了理论基础。 这些工作中提出的数学见解和实践考虑显着推动了全同态加密领域的发展,并为保护隐私的计算开辟了新的可能性。
- 原文链接: hexens.io/blog/gbfv...
- 登链社区 AI 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!