3.3 GSW：近似特征向量与矩阵密文

3.3 GSW：近似特征向量与矩阵密文

本节摘要：GSW 方案（二零一三年）把密文从向量换成矩阵，乘法退化为朴素的矩阵乘法、不再需要密钥交换；用近似特征向量的视角看，私钥是密文矩阵的近似特征向量，特征值就是明文。本节讲清这个视角转换、噪声增长从乘性到加性的意义、以及它作为快速自举家族地基的原因，配一个可运行的最小数值演示。

换一个视角：私钥是特征向量

线性代数课上的特征向量定义是：矩阵作用在某向量上，只把它拉长一个倍数、不改变方向。GSW 的妙处在"近似"二字：密文是一个矩阵，私钥向量作用上去的结果，近似等于明文乘上私钥自己——误差是多项式级别的小量。把这句话写成等式：密文矩阵乘私钥向量，等于明文乘私钥向量，再加一个小误差向量。明文就是（近似的）特征值。

这个视角立刻把同态乘法变得肉眼可见地简单。两个密文矩阵相乘，作用在私钥上：第一个矩阵先作用第二个的结果，展开后等于两个明文之积乘私钥，误差项只做了线性组合——误差是"加起来的"，不是"乘起来的"。对比 BGV 家族的张量积路线（乘法噪声近似相乘、必须靠模交换抢救），GSW 的噪声增长是温和的线性叠加。这个性质被称为噪声的渐进最优，它是后来 FHEW 与 TFHE 能把自举做快的数学根源：自举要在密文上跑解密电路，电路里的乘法噪声越温和，刷新过程的深度预算越宽松。

代价同样清晰。矩阵密文的尺寸是向量密文的平方倍（维度参数下大出很多），单次运算搬运的数据量按比例上涨；朴素矩阵乘对打包负载（一个密文数千槽）的摊销不友好。所以演化史的分工是：GSW 一支往下走"小明文、快自举"的布尔路线（FHEW、TFHE），BGV/BFV 一支继续走"大打包、分层算"的算术路线。一个方案不可能两头全占，GSW 用体积换来了噪声的温顺。

最小数值演示：亲眼看见近似特征向量

import random

# 教学版 GSW 近似特征向量演示（整数域，规模 n=4）
n = 4
secret = [random.randint(-5, 5) for _ in range(n)]   # 私钥向量 s

def make_ct(m, noise_bound=1):
    # 密文矩阵 = 明文单位矩阵 + 小噪声矩阵
    # 满足 C·s = m·s + E·s，E·s 保持小量
    C = [[m * (1 if i == j else 0) + random.randint(-noise_bound, noise_bound)
          for j in range(n)] for i in range(n)]
    return C

def apply(C, v):                                     # 矩阵乘向量
    return [sum(C[i][j] * v[j] for j in range(n)) for i in range(n)]

C1, C2 = make_ct(3), make_ct(5)                      # 加密明文 3 与 5

t1 = apply(C1, secret)                               # 应近似 3·s
t2 = apply(C2, secret)                               # 应近似 5·s
t12 = apply([ [sum(C1[i][k] * C2[k][j] for k in range(n)) for j in range(n)]
              for i in range(n)], secret)            # (C1·C2)·s 应近似 15·s

print("3·s =", [3 * x for x in secret])
print("C1·s =", t1, "  <- 每个分量只差 ± 几个单位")
print("15·s =", [15 * x for x in secret])
print("(C1·C2)·s =", t12, " <- 乘积密文作用后仍近似 15·s")
# 观察：一次乘法后误差仍是线性叠加量级，而非平方爆炸
​

运行后你会看到每个输出向量与目标（明文乘私钥）只差个位数——这个"差"就是误差，解密时用取整把它抹掉。把明文换成比特（零或一），这段代码的骨架就非常接近 TFHE 外积运算的整数版雏形了。

两族路线的对照

表格最后一行是演化史的判决：两条路线各自长出了完整的后代谱系，谁也没有吞并谁。第三章第五节会把这张表扩成三线对比矩阵，把 CKKS 的近似路线也放进来。

💡 关键直觉：GSW 教给社区的是"换观测视角"的价值——密文矩阵与私钥向量的关系，从"加密与解密的对抗"改写成"近似特征值问题"，同态乘法的性质立刻从矩阵乘法的结合律里免费掉出来。很多密码学进展的形状都是这样：不是造新机器，而是找到让老机器的性质自动成立的坐标系。

本节要点回顾

• 要点一：GSW 的核心等式是密文矩阵乘私钥等于明文乘私钥加小误差，明文即近似特征值
• 要点二：同态乘法退化为矩阵乘，免掉密钥交换；误差线性叠加而非相乘，为浅层自举电路提供空间
• 要点三：代价是密文平方级膨胀与打包不友好，演化上由此分出算术与布尔两条路线
• 要点四：FHEW 与 TFHE 的外积运算直接建在 GSW 结构上，本节是它们的直接前置

四、GSW 的工程回声

GSW 的近似特征向量思想看似数学炫技，实际是现代同态加密工程化的一条主干。它的第一份遗产是字宽分解：把明文与密钥的小矩阵用二进制或基-B 分解表示，密文存储膨胀一个因子（对数级），换来的是乘法后噪声增长从乘法级压到加法级——这个压噪交换比，直接决定了 leveled 方案能做多少层乘法。它的第二份遗产是自举的轻量化：FHEW 与 TFHE 把自举过程重构为 GSW 形式下的盲旋转，把布尔电路的自举时间从几十秒压到十毫秒量级——正是这个数量级跃迁，让布尔电路的同态执行第一次有了可用感。第三份遗产是安全证明的统一语言：近似特征向量的框架让不同方案的安全性可以放进同一个 LWE 归纳下比较，参数选择从此有了共同标尺。工程选型的实用结论：需要布尔电路与比较逻辑的隐私计算（隐私集合求交、数据库加密检索），优先看 TFHE 一系；需要深度算术推理（隐私机器学习推理），CKKS 与 BFV 更顺手；而所有这些方案的底层，都站着 GSW 这副骨架。读懂它，后面所有方案的性能表就都从黑话变成了因果。