5.1 整数玩具 FHE：草稿纸上的同态

5.1 整数玩具 FHE：草稿纸上的同态

同态加密允许直接在密文上做运算：\text{Dec}(c_1 + c_2) = m_1 + m_2、\text{Dec}(c_1 \times c_2) = m_1 \times m_2。本节用一个奇数模的整数玩具方案把这两条性质在纸面上算出来，并亲眼看着噪声在乘法下按"相乘"速度膨胀——同态的魔力与它的天敌，一页纸都装得下。

承接第 4 章：你已经熟悉"真值加小噪声再藏进模数"的套路；本节把这个套路推到极限——让密文直接参与四则运算。读完本节你将带着"深度受限"这个痛点进入 5.2 节，Gentry 蓝图的一切动机都从这一页的数字里长出来。

方案只有五行

选一个奇数大整数 p 作密钥（奇数是解密能判奇偶的前提）。加密一个比特 m \in \{0,1\}：

其中 r 是随机小整数（噪声源），q' 是随机大整数（把 p 藏进数量级）。解密两步：先对 p 取余，再取奇偶——c \bmod p = m + 2r（只要 |2r| < p/2），而 m + 2r 与 m 奇偶相同，除 2 取整即还原 m。定义噪声 \varepsilon(c) = (c \bmod p) - m，解密成功的唯一条件：|\varepsilon(c)| < p/2。把一切记号压实到例子上：p = 67。

• 加密 m_1 = 1：取 r = 3、q' = 19，c_1 = 1 + 6 + 1273 = 1280。核对：1280 \bmod 67 = 7，奇数，解出 1。噪声 \varepsilon_1 = 7。
• 加密 m_2 = 0：取 r = 2、q' = 5，c_2 = 0 + 4 + 335 = 339。核对：339 \bmod 67 = 4，偶数，解出 0。噪声 \varepsilon_2 = 4。

同态加法：纸面五秒

直接把两段密文相加：c_1 + c_2 = 1280 + 339 = 1619。不解密它，先当它是普通密文处理：1619 \bmod 67：67 \times 24 = 1608，余 \mathbf{11}。11 是奇数，解密得 1——恰好等于 m_1 + m_2 = 1。噪声也升级了：11 = 1 + 2 \times 5，新噪声 11 = \varepsilon_1 + \varepsilon_2 = 7 + 4。加法让噪声线性叠加，账很好算。

同态乘法：噪声开始翻倍

相乘：c_1 \times c_2 = 1280 \times 339 = 433920。取余：433920 \bmod 67 = \mathbf{28}（67 \times 6476 = 433892）。偶数，解出 0 = m_1 \times m_2，性质成立。看噪声：展开代数式 (m_1 + \varepsilon_1)(m_2 + \varepsilon_2) = m_1 m_2 + (m_1 \varepsilon_2 + m_2 \varepsilon_1) + \varepsilon_1 \varepsilon_2，本例 7 \times 4 = 28，与纸面完全一致。规律浮出水面：乘法让噪声近似相乘。这次是 7 乘 4 得 28 不起眼，但若再乘一个噪声 9 的密文，噪声立刻到 252——离 p/2 = 33.5 的红线其实早已越界（这个玩具的 p 小到只够演示一次乘法）。工程版把 p 取成几千比特的大数，才能攒出几十层的深度。三个整数玩具的完整代码：

p = 67                                  # 密钥：奇数
def enc(m, r, k):                       # c = m + 2r + k*p
    return m + 2 * r + k * p
def dec(c):
    e = c % p
    e = e if e <= p // 2 else e - p     # 居中余数
    assert abs(e) < p / 2, "噪声越界，解密失败"
    return e % 2

c1, c2 = enc(1, 3, 19), enc(0, 2, 5)
print("密文:", c1, c2)                          # 1280 339
print("密文相加解密:", dec(c1 + c2))            # 1  = 1+0
print("密文相乘解密:", dec(c1 * c2))            # 0  = 1*0
print("噪声: 加法后", (c1 + c2) % p - 1,
      " 乘法后", (c1 * c2) % p - 0)             # 11 28
​

为什么这玩具不能直接上线

三个理由各对应一条升级路径。理由一，不安全：本方案对"选择明文攻击"毫无抵抗——攻击者加密已知的 0 拿到 c_0 = 2r + pq'，对已知 1 的密文 c 做 c - c_0 立刻暴露 p 的影子；真实方案（BGV、BFV）必须搬进多项式环并配语义安全变换。理由二，深度浅：噪声按乘法膨胀，第 5.2 节的自举是解药。理由三，一次一个比特：真实方案用批处理把一个密文变成几千个"槽"，一次并行运算一整排数据（SIMD），吞吐差四个数量级。三处升级后，玩具的骨架逻辑原封不动地保留在 BFV 与 BGV 的最底层——你在纸面上算过的每一条性质，都在工程库里活着。

噪声红线值得再压一句重点：噪声膨胀与安全强度是两本账，不能挪用。p 变大既加深深度又提升安全，看似双赢，但安全预算按第 3 章的攻击成本核定后，p 与 q' 的位数就锁死了，深度只能从"压缩噪声"上想办法——这正是下一节的主角。

把深度账算成一张表

顺手把玩具参数的深度预算算穷尽。设初始噪声 \varepsilon_0（上下对称，量级取 \varepsilon_0），红线 p/2。纯加法电路：噪声线性累加，k 个密文相加后噪声约 k\varepsilon_0，可加层数约 p/(2\varepsilon_0)——相对宽裕。一次乘法：噪声升到 \varepsilon_0^2 量级；连乘 k 次：噪声 \varepsilon_0^{2^k}，双指数膨胀。代入小数字感受：\varepsilon_0 = 2、p \approx 2^{20}，纯加法能叠五十万项；连乘到第三层就是 2^8，第五层 2^{32}，第七层 2^{128} 已穿红线。深度预算是按乘法层指数烧的，工程师评估电路时第一件事永远是数乘法层数，其次才是优化加法树（把求和排成平衡树能把加法深度从线性压到对数）。这张表的工程结论只有一行：FHE 成本的主宰变量是乘法深度，不是数据量。

下一节：解密电路本身被同态求值一遍，噪声应声下降——Gentry 的"自举"是全同态梦想的破壁一击。