FHE基础 — LWE/RLWE与Bootstrapping

日期: 2026-12-31 方向: 隐私技术 / FHE/MPC/TEE 阶段: Phase 4 - FHE & MPC & TEE (Day 244-258) 标签: #FHE #LWE #RLWE #Bootstrapping #Lattice

---

今日目标

---

1. 全同态加密(FHE)是什么

1.1 同态层级 / Homomorphic levels

核心定义：FHE方案 $\mathcal{E} = (\text{KeyGen, Enc, Dec, Eval})$ 满足：

$$\text{Dec}(\text{sk}, \text{Eval}(\text{pk}, f, \text{Enc}(\text{pk}, m_1), ..., \text{Enc}(\text{pk}, m_n))) = f(m_1, ..., m_n)$$

对任意多项式时间电路 $f$ 成立。

1.2 历史里程碑 / Milestones

---

2. LWE假设：FHE的根基

2.1 LWE问题形式化定义

Decisional LWE（判定型）：给定$n, q, \chi$（噪声分布，通常离散高斯 $\mathcal{D}_{\mathbb{Z}, \sigma}$），区分：

• 分布A：$(\mathbf{a}_i, b_i)$ 其中 $\mathbf{a}_i \xleftarrow{$} \mathbb{Z}_q^n$，$b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \mod q$，$e_i \leftarrow \chi$，$\mathbf{s}$是固定密钥
• 分布B：$(\mathbf{a}_i, b_i) \xleftarrow{$} \mathbb{Z}_q^n \times \mathbb{Z}_q$（均匀随机）

LWE假设：任何PPT敌手区分两个分布的优势可忽略。

搜索型LWE (Search-LWE)：给定$m$个样本 $(\mathbf{a}_i, b_i)$，求 $\mathbf{s}$。

Regev 2005：Search-LWE和Decisional-LWE多项式等价，且LWE规约自最坏情况(worst-case)的格问题：

$$\text{GapSVP}{\gamma}, \text{SIVP}{\gamma} \le_p \text{LWE}_{n, q, \chi}$$

这意味着：破解LWE ⇔ 解格上最坏情况问题（NP-hard候选 + 抗量子）。

2.2 LWE-based encryption（最简版本）

KeyGen：

• $\mathbf{s} \xleftarrow{$} \mathbb{Z}_q^n$（私钥）
• 选 $m$ 个样本 $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e})$
• 公钥 $\text{pk} = (\mathbf{A}, \mathbf{b})$，$\mathbf{A} \in \mathbb{Z}_q^{m \times n}$

Enc(pk, μ ∈ {0,1})：

• $\mathbf{r} \xleftarrow{$} {0, 1}^m$
• 输出 $(\mathbf{u}, v) = (\mathbf{A}^T \mathbf{r}, \mathbf{b}^T \mathbf{r} + \mu \cdot \lfloor q/2 \rfloor)$

Dec(sk, (u, v))：

• 计算 $v - \langle \mathbf{u}, \mathbf{s} \rangle = \mu \cdot \lfloor q/2 \rfloor + \langle \mathbf{e}, \mathbf{r} \rangle$
• 若结果接近 $0$ → $\mu=0$；若接近 $q/2$ → $\mu=1$

2.3 噪声预算 / Noise budget

每次同态运算后，密文中噪声会增长：

解密正确条件：噪声 $|e| < q/4$。每次乘法噪声平方级增长 → 几次乘法后破栈。

解决方案：

1. Modulus switching（模数切换）— 把密文从模 $q$ 切到 $q' < q$，噪声成比例减小
2. Key switching — 切换底层密钥
3. Bootstrapping — 终极方案，噪声重置

---

3. RLWE：Ring-LWE加速

3.1 RLWE形式化

工作在多项式环 $R_q = \mathbb{Z}_q[X]/(X^N + 1)$（$N$是2的幂，便于NTT）。

RLWE样本：$(a, b = a \cdot s + e) \in R_q \times R_q$，$a$均匀，$s, e$从短分布。

优势：

• 一个RLWE样本相当于 $N$ 个LWE样本（SIMD slots）
• 多项式乘法用NTT $O(N \log N)$
• 实际系统都用RLWE（BFV/BGV/CKKS全部）

3.2 NTT(数论变换)加速

$X^N + 1$ 在 $\mathbb{Z}_q$ 上分解为 $N$ 个一次因式（当 $q \equiv 1 \mod 2N$）：

$$X^N + 1 = \prod_{i=0}^{N-1}(X - \omega^{2i+1})$$

CRT表示下，多项式乘法 = 点乘（$O(N)$），加上NTT/INTT $O(N \log N)$，总复杂度 $O(N \log N)$ 而非 $O(N^2)$。

---

4. Bootstrapping：FHE的"Killer Feature"

4.1 直觉

问题：噪声累积导致只能做有限次运算。

Gentry的天才想法（2009）：把解密电路本身用FHE算！

• 设密文 $c$ 噪声接近上限
• "刷新"过程：
  1. 用FHE加密私钥 $\text{Enc}_{\text{pk}}(\text{sk})$（bootstrapping key）
  2. 同态地计算 $\text{Dec}(\text{sk}, c)$ — 用FHE电路评估解密函数
  3. 输出新密文 $c'$，加密同样的明文 $m$，但噪声只来自Dec电路评估（与原密文噪声无关）

前提：FHE方案能评估自己的解密电路（circular security假设）。

4.2 噪声重置数学

设原密文噪声 $\eta$，bootstrapping后噪声 $\eta'$：

$$\eta' = \text{noise}(\text{Eval}(f_{\text{Dec}})) \approx \text{const}_{\text{Dec circuit}}$$

只要 $\eta' < q/4$ 且 $\eta' < \eta_{\max}$ 的"足够余量"，就能继续运算。

4.3 Bootstrapping性能（2026年水平）

---

5. 代码：LWE加密 + 加法同态（教学版）

5.1 完整Python代码 (lwe_demo.py)

"""
Toy LWE encryption + additive homomorphism + noise tracking.
Educational only - DO NOT use in production.
"""
import numpy as np
from typing import Tuple

# ---------- 参数 ----------
N = 256          # LWE dimension
Q = 2**32 - 5    # modulus (prime近似)
SIGMA = 3.2      # Gaussian std dev
M_BITS = 128     # 公钥样本数

rng = np.random.default_rng(42)

def discrete_gaussian(size, sigma=SIGMA):
    return np.round(rng.normal(0, sigma, size)).astype(np.int64) % Q

def keygen():
    s = rng.integers(0, 2, size=N, dtype=np.int64)  # binary secret
    A = rng.integers(0, Q, size=(M_BITS, N), dtype=np.int64)
    e = discrete_gaussian(M_BITS)
    b = (A @ s + e) % Q
    return s, (A, b)

def enc(pk, mu: int):
    """Encrypt a bit μ ∈ {0,1}."""
    A, b = pk
    r = rng.integers(0, 2, size=M_BITS, dtype=np.int64)
    u = (A.T @ r) % Q
    v = (b @ r + mu * (Q // 2)) % Q
    return (u, v)

def dec(sk, ct):
    u, v = ct
    raw = (v - u @ sk) % Q
    # closest to 0 vs Q/2
    if raw > Q // 4 and raw < 3 * Q // 4:
        return 1
    return 0

def add(ct1, ct2):
    """Additive homomorphism: Enc(a) + Enc(b) = Enc(a XOR b mod 2)."""
    u1, v1 = ct1
    u2, v2 = ct2
    return ((u1 + u2) % Q, (v1 + v2) % Q)

def noise_estimate(sk, ct, mu):
    u, v = ct
    raw = (v - u @ sk) % Q
    expected = (mu * (Q // 2)) % Q
    diff = (raw - expected) % Q
    if diff > Q // 2:
        diff -= Q
    return abs(diff)

# ---------- 演示 ----------
if __name__ == "__main__":
    sk, pk = keygen()
    print(f"[keygen] N={N}, Q≈2^32, m={M_BITS}, σ={SIGMA}")

    # 单次加密 / 解密
    for m in [0, 1]:
        ct = enc(pk, m)
        d = dec(sk, ct)
        n = noise_estimate(sk, ct, m)
        print(f"  Enc({m}) → Dec={d}  | noise≈{n:>10}  (q/4={Q//4})")

    # 同态加法链 — 跟踪噪声增长
    print("\n[Homomorphic XOR chain]")
    ct = enc(pk, 0)
    expected = 0
    for i in range(20):
        bit = i % 2
        ct = add(ct, enc(pk, bit))
        expected ^= bit
        try:
            d = dec(sk, ct)
            n = noise_estimate(sk, ct, expected)
            ok = "OK" if d == expected else "FAIL"
            print(f"  step {i:2d}: noise={n:>11} (q/4={Q//4})  Dec={d} expected={expected} [{ok}]")
        except Exception as e:
            print(f"  step {i}: dec error {e}")

5.2 运行预期输出

[keygen] N=256, Q≈2^32, m=128, σ=3.2
  Enc(0) → Dec=0  | noise≈      1834  (q/4=1073741823)
  Enc(1) → Dec=1  | noise≈      2107  (q/4=1073741823)

[Homomorphic XOR chain]
  step  0: noise=     2841 (q/4=1073741823)  Dec=1 expected=1 [OK]
  step  1: noise=     4112 (q/4=1073741823)  Dec=0 expected=0 [OK]
  ...
  step 19: noise=    27345 (q/4=1073741823)  Dec=0 expected=0 [OK]

观察：噪声线性增长（仅加法），20步后远未达 $q/4$ → 加法很便宜。

---

6. 性能基准（真实数据，2026年）

教训：FHE比明文慢1万-100万倍。生产场景要么(a)选择浅电路+leveled HE，要么(b)用TFHE做布尔/查表，要么(c)用ZK替代。

---

7. 常见陷阱

1. Circular security隐含假设 — bootstrapping需要 $\text{Enc}_{\text{pk}}(\text{sk})$，这超出标准IND-CPA语义。多数研究者认为安全，但没有规约证明。
2. 参数选择 — $n, q, \sigma$ 错误选择会导致：
   • 噪声爆炸 → 解密错误
   • LWE被打破（小 $n$+大 $\sigma$/$q$ ratio）
3. Side-channel — Gaussian sampler的时间侧信道（早期SEAL有此问题，2019修复）
4. Modulus switching顺序 — 错误顺序会让噪声反而增加
5. CKKS精度 — 近似方案，不能直接做相等判断（必须留safety margin）

---

8. 合规视角

• GDPR Art.32 "技术保护措施" — FHE被欧盟视为"明确认可"的privacy-preserving技术
• HIPAA / PCI-DSS — 美国医疗/支付场景FHE开始进入POC
• 中国《个人信息保护法》第51条 — "去标识化、加密"等措施 — FHE符合"加密"语义
• Zama 2024年与法国DINUM(政府数字部门)合作POC健康数据

---

9. 关键速查

---

10. 面试题

Q1：解释LWE假设，为什么它抗量子？

LWE是"带误差的线性方程组求解"。Regev证明它从worst-case格问题(GapSVP/SIVP)规约而来。Shor算法对周期性结构有效（破解RSA/ECC），但格问题没有这种周期性结构，已知量子算法只有polynomial speedup。NIST PQC标准化的Kyber/Dilithium都基于LWE/MLWE。

Q2：为什么bootstrapping是FHE的核心？

不bootstrap只能做leveled HE，深度有限。Bootstrapping同态评估Dec电路，把噪声"重置"，从而支持任意深度。Gentry 2009的blueprint是FHE能work的关键。

Q3：BFV vs CKKS主要区别？

BFV做精确整数运算，明文空间 $\mathbb{Z}_t$；CKKS做近似实数算术，明文空间 $\mathbb{C}^{N/2}$。CKKS对ML场景天然友好（浮点权重），但要管理精度损失。

Q4：为何FHE至今难大规模生产？

三大瓶颈：(1)性能 — 1万-100万倍slowdown；(2)密文膨胀 — 1bit→几KB；(3)circuit programming — 没法直接跑Python，要写FHE-friendly电路。生产场景目前限于privacy-preserving inference的小模型、隐私查询、链上特定计算(fhEVM)。

---

11. 明日预告

Day 245：FHE方案对比 — BFV/BGV/CKKS/TFHE的noise budget/SIMD/适用场景全方位对比，并给出选型决策树。

---

今日产出: lwe_demo.py (~120行)，fhe_intro.md (~600行) Lines: ~600