矩阵天生会算：Gentry 的原生矩阵全同态加密方案

TL;DR

全同态加密的发明人 Craig Gentry 回来了。时隔 16 年，他与韩国 DESILO 的 Yongwoo Lee 交出了第一个”为矩阵运算原生设计”的 FHE 方案（GL scheme）：给多项式环开出 X、Y、W 三个变量，让一个多项式天然编码一批 n×n 矩阵，再用一个”同态 trace”技巧把密文矩阵乘法直接归约成 4 次明文矩阵乘法——全程不需要 slot↔系数转换，也不需要 ring switching。实测 16 个 256×256 复矩阵的密文-密文乘法只要 7.24 秒，key switching 开销摊到每个 slot 只有 Hadamard 乘法的约 2.8 倍。论文已被 CRYPTO 2026 接收。

论文信息卡

标题：Fully Homomorphic Encryption for Matrix Arithmetic
作者：Craig Gentry（Cornami）、Yongwoo Lee（DESILO Inc. / Inha University）
会议：CRYPTO 2026（据 DESILO 官方新闻稿确认接收，proceedings 待出版）；preprint 存档于 ePrint 2025/1935（2025-10-16，CC BY）
原文链接：https://eprint.iacr.org/2025/1935

背景

为什么矩阵乘法值得一个 FHE 方案”原生”为它设计？先说应用。全同态加密这几年最被看好的落地场景是隐私 AI：数据加密上传，云端在密文上跑模型，返回加密结果。但 Transformer 里到处都是矩阵乘法——注意力机制里的 QKᵀ、softmax 后的加权求和，全是矩阵乘矩阵。更关键的是，即使模型权重是明文，注意力分数本身也是密文，论文引用的 MYJK24 指出：隐私 LLM 推理绕不开密文-密文（ct-ct）矩阵乘法。这是刚需，不是选配。

再说痛点。传统做法有两条路，都难受。第一条路是 SIMD 拼装：把矩阵元素塞进 CKKS/BGV 的 slot 里，用大量 rotation 加 Hadamard 乘积”拼”出矩阵乘法。问题是 rotation 在 FHE 里出了名的贵——后面实验数据会看到，一次 rotation 的 key switching 开销就能顶好几次乘法，拼一个 n×n 矩阵乘法要 O(n) 量级的 rotation，账根本算不过来。第二条路是系数编码：把矩阵编进多项式系数域，乘法倒是便宜了，但代价是昂贵的 slot↔系数转换（还附带 bit-reversal 排序的麻烦）和 ring switching，等于把账从一处挪到另一处。

Gentry 这篇的野心是换一条路：让环本身就”懂”矩阵。

方法拆解

先换个视角：高斯整数眼中的分圆环

第一步是个漂亮的观察。大家熟悉的环 Z[X]/⟨X^N+1⟩（N 为 2 的幂），其实可以看成高斯整数上的多项式环：Z[X]/⟨X^N+1⟩ ≅ Z[i][X]/⟨X^{N/2}−i⟩。把 X^{N/2} 认作”虚数单位的平方根”——一个 8 次单位根——整个环就活了：复数运算天然地住进了环里。这就是”高斯整数视角”，后面所有构造都站在它上面。

三个变量，一个矩阵宇宙

第二步，Gentry 和 Lee 直接给环开了三个变量：

R_q = Z_q[i][X,Y,W] / ⟨X^n − i, Y^n − i, Φ_p(W)⟩

其中 n 是 2 的幂，p 是奇数。X 和 Y 负责矩阵的行和列，W（带着分圆多项式 Φ_p）负责”分批”：一个多项式 m 在 (ζ^j, ζ^k, η^ℓ) 处的求值，恰好就是第 ℓ 批矩阵的第 (j,k) 个元素。于是一个多项式同时编码 φ(p) 个 n×n 矩阵，天然支持复数矩阵和整数矩阵的批量运算。

直觉上可以这么想：以前是把矩阵”塞”进一个为向量设计的环里，现在环的三个维度分别对应”行、列、批次”，矩阵住进来是拎包入住，不用削足适履。

关键一击：同态 trace

真正的高光时刻是矩阵乘法的处理。两个编码矩阵 M_0、M_1 的乘积，可以写成：

M_0 · M_1 = Tr_Z( m̄_0(Y,Z,W) · m_1(X,Z,W) )

这里 m̄_0 是 m_0 的共轭多项式，Z 是一个辅助变量，Tr_Z 是对 Z 的 trace（迹）运算——把含 Z 的部分”求和”掉。

为什么这招妙？因为密钥里不含辅助变量 Z 的分量，密钥和 trace 运算可以交换顺序。于是这个 trace 可以直接在同态下计算：先把两个密文多项式乘起来（一次普通的密文乘法），再对结果做同态 trace，得到的正是乘积矩阵的编码。矩阵乘法被”降维”成了一个代数恒等式。

归约完成：4 次明文矩阵乘法

展开这个 trace，加密的 n×n 矩阵乘法最终被归约成 4 次 Z_q[i] 上的 n×n 明文矩阵乘法（利用高斯整数乘法的结构，底层的 Z_q 乘法次数还能进一步压缩）。划重点：整个过程不需要 slot↔系数转换，不需要 ring switching。以前两条路的账单（rotation 海、转换税）在这里直接消失了。方案还顺手兼容现有的 bootstrapping 算法，深层电路照样能跑。

免费赠品：旋转、转置、共轭

一旦矩阵住进了环的结构里，很多运算变成了”免费”的：环自同构（把变量映射到它的幂次）直接给出行/列旋转和批次间旋转，不用花钱做 rotation；转置只需交换 X 和 Y 两个变量；加法、Hadamard 乘积、共轭都是编码天然支持的；整数矩阵用 BGV 式的编码同样处理。

flowchart LR
    A["矩阵 M0, M1<br/>(φ(p) 批 n×n)"] --> B["编码为多项式<br/>m0, m1 ∈ R_q"]
    B --> C["密文多项式相乘"]
    C --> D["同态 trace Tr_Z<br/>(密钥与 trace 可交换)"]
    D --> E["4 次明文矩阵乘法<br/>(FLINT 加速)"]
    E --> F["乘积矩阵的密文编码"]

（文字摘要：矩阵先被编码进三元多项式环；密文相乘后做一次同态 trace，把问题归约到明文域的 4 次矩阵乘法；全程无 slot↔系数转换、无 ring switching。）

安全性：没有新假设

经自然同构 R_q ≅ Z_q[X]/⟨Φ_{4np}(X)⟩，这个看起来花哨的多元环本质上就是标准分圆环，安全性等价于标准 RLWE 假设，没有引入任何新假设。这对一个”新编码”方案来说是重要的定心丸。

实验与数据

论文给了完整实现（128-bit 安全参数）和实测，不是纸上谈兵。参数：n=256，p=17，ternary 密钥，σ=3.2，log q=140 分成 3 条 CRT 链。测试机：Intel i9-11900K 单线程、64GB 内存、Ubuntu 22.04，明文矩阵乘法用 FLINT 3.3.1（高度优化的数论库）。

核心结果：16 个 256×256 复矩阵的 ct-ct 乘法，总耗时 7.24 秒（朴素 O(n³) 实现则是 11.58 秒）。其中 key switching 占 3.32 秒。作为参照：同样参数下一次 Hadamard 乘法的 key switching 是 1.17 秒——矩阵乘法约为其 2.8 倍，正好落在论文摘要”2–4 倍”的论断区间里。

摊到每个 slot 看（这才是公平的比较口径）：

操作	每 slot key switching 开销
GL 矩阵乘法	3.16 µs
GL Hadamard 乘法	1.15 µs
OpenFHE v1.4.0 rotation	0.82 µs

矩阵乘法的 key switching 开销约为自家 Hadamard 的 2.8 倍、OpenFHE 一次 rotation 的 3.8 倍。换句话说，一次 ct-ct 矩阵乘法的辅助开销，和做几次 rotation 是一个数量级——而传统 SIMD 拼装法光 rotation 就要 O(n) 次。

怎么读这个数据：最值得玩味的是论文里的一句话——即使 FLINT 已经高度优化，明文矩阵乘法仍然是总耗时的大头。这说明方案的辅助开销（编码、trace、key switching）已经被压得足够小，瓶颈回到了”矩阵乘法本身”。而 key switching 的复杂度只有 O(pn log np)，这意味着未来任何更快的矩阵乘法算法（比如 Coppersmith–Winograd 的 O(n^2.375)）都能被这个方案直接”吃到红利”，天花板还很高。

局限与开放问题

论文第 6 节自己列得很坦诚：

高级矩阵运算还没影：矩阵求逆、矩阵分解（LU、QR 这类）尚未支持，线性代数工具箱还不全；
实验只有单线程 CPU：GPU 和专用 FHE 芯片上的加速是开放方向，真实部署的性能数字还待补；
深层电路仍依赖 bootstrapping：方案兼容现有 bootstrapping 算法，但专用的 GL bootstrapping 是另一篇姊妹篇（Crockett、Gentry、Kim、Lee，同样被 CRYPTO 2026 接收）；
一个必须说明的口径问题：DESILO 新闻稿里”比 SOTA 基线快 80 倍”的说法，在论文正文里找不到对应出处——全文没有任何”× faster than baseline”式的论断，唯一的量化比较就是上面的 2–4 倍 key switching 开销。这是厂商口径，不能当成论文结论；
产业侧的真实进展：2026 年 4 月 DESILO 已把 GL 方案集成进其商用 DESILO FHE 库（同样来自新闻稿，非论文内容）。

一点思考

一句话判断：FHE 这十几年的叙事是”万能但慢”，这篇论文换了个问法——不是把通用 FHE 做快一点，而是为最重要的 workload（矩阵）重造代数地基；隐私 LLM 推理要真正落地，靠的不会是一个万能加速器，而是这样一堆 workload 原生的构造，矩阵是第一块多米诺骨牌。给工程侧的实操建议：评估 FHE 矩阵方案时别只看总耗时，盯住”每 slot key switching 开销”——它直接决定你的方案是在”和 Hadamard 一个量级”还是”和 rotation 海一个量级”，这是工程账本上最诚实的一行。而 2–4 倍这个数字本身值得再想一层：它第一次把 ct-ct 矩阵乘法做进了和 Hadamard 乘法同一个数量级的账本里，隐私 Transformer 的推理延迟，第一次有了算得过来的希望。

原文链接

论文全文（ePrint 2025/1935，CC BY）：https://eprint.iacr.org/2025/1935
PDF 直链：https://eprint.iacr.org/2025/1935.pdf