同态加密科普

全文分三层：

1. 通俗理解：不需要任何数学
2. 实际用处：隐私云计算、医疗与基因、银行联合风控、隐私机器学习、电子投票、私有信息检索，以及业界现状和性能代价
3. 数学原理：RSA、Paillier、ElGamal、环同态、LWE/RLWE、噪声、模切换、自举、BGV/BFV/CKKS，并附小数字手算例子

第一层：通俗理解

1.1 带着手套操作上锁的箱子

想象一个珠宝商，手下有个工匠，但珠宝商不信任他，怕他偷金子。于是珠宝商这样安排：

1. 把金料放进一个上了锁的透明手套箱，箱子侧面伸出一副手套。
2. 工匠把手伸进手套，可以在箱子里把金料熔化、拉丝、焊接成项链。
3. 但工匠打不开锁，所以碰不到金子，也拿不走。
4. 做完后箱子还给珠宝商，只有珠宝商有钥匙，打开就得到成品。

对应关系：

关键在于：工匠全程都在干活，却从头到尾不知道金子长什么样。普通加密只能做到"锁起来存放和运输"，一旦要计算就必须先开锁；同态加密做到了"锁着也能加工"。

1.2 什么叫"直接对密文做运算"

用一个最简单的例子说明。你有两个数 $3$ 和 $5$，想让云服务器帮你算 $3+5$，但又不想让服务器知道这两个数。

服务器看到的只是两串乱码，它对乱码执行某种"密文加法"，得到第三串乱码。你把第三串乱码解密，得到的恰好是 $8$。服务器既不知道输入是 $3$ 和 $5$，也不知道结果是 $8$。

注意，"密文加法"一般不是把两串数字直接相加。对 Paillier 来说，它是把两个密文相乘；对格密码方案来说，它确实是向量或多项式的相加。具体是什么运算取决于方案，第三层会讲。

1.3 三个级别：PHE、SHE、FHE

任何计算最终都能拆成加法和乘法（在比特上就是异或和与门），所以关键问题是：密文上能做哪些运算，能做多少次。

可以这样记：

• PHE：手套箱里只有一把锤子，能一直敲，但只能敲。
• SHE：工具齐全，但每做一步箱子里就积一点灰（数学上叫噪声），灰积到一定程度就看不清了，再也打不开。
• FHE：在 SHE 的基础上加一个"不开锁也能除灰"的办法（自举，bootstrapping），于是可以无限干下去。

1.4 为什么叫"同态"

"同态"（homomorphism）是数学词，字面意思是"相同的形状"。在抽象代数里，环同态 $\varphi: R \to S$ 是满足

$$\varphi(a+b) = \varphi(a) + \varphi(b),\qquad \varphi(ab) = \varphi(a)\varphi(b)$$

的映射。它把 $R$ 中的运算"搬运"到 $S$ 中：先运算再映射，等于先映射再运算。

同态加密说的正是这件事。只是方向通常反过来看：从密文映射到明文的解密保持运算，即

$$\mathrm{Dec}(c_1 \oplus c_2) = \mathrm{Dec}(c_1) + \mathrm{Dec}(c_2),\qquad \mathrm{Dec}(c_1 \otimes c_2) = \mathrm{Dec}(c_1)\cdot \mathrm{Dec}(c_2),$$

其中 $\oplus, \otimes$ 是密文空间里对应的运算。换句话说，"在密文世界算"和"在明文世界算"是同一个形状，所以叫同态。

不过严格讲，现代全同态方案里的解密只是一个近似的同态，因为每次运算都会带进一点噪声，这一点在第三层细讲。

第二层：实际用处

2.1 隐私云计算（外包计算）

这是同态加密最原始的动机。公司想用云上的算力，但数据是敏感的（财务、病历、用户行为）：

• 传统做法：上传明文，或者在云上解密后再算，于是云厂商和入侵云的黑客都能看到数据。
• 同态加密：上传密文，云在密文上算完把密文结果发回来，云从头到尾只碰过密文。

它保护的是"使用中的数据"（data in use）。传输加密（TLS）保护"传输中的数据"，磁盘加密保护"静止的数据"，计算的那一刻正好是这两者都管不到的空白。

2.2 医疗和基因数据分析

医院和研究机构之间的数据共享受法律严格限制（如美国 HIPAA、欧盟 GDPR）。同态加密可以让：

• 多家医院把加密后的病历汇总，研究者在密文上做统计（均值、回归、卡方检验）；
• 个人把加密的基因组发给检测公司，公司在密文上比对疾病风险位点，只有本人能看到报告。

学术界从 2014 年起每年举办 iDASH 隐私保护基因组分析竞赛，同态加密一直是主要赛道之一，题目包括密文上的全基因组关联分析（GWAS）和逻辑回归训练。

2.3 银行之间的联合风控与反洗钱

洗钱者常把资金拆散在多家银行之间流转，每家银行只看到自己那一段，看不出全貌；但银行之间又不能随便共享客户数据。

同态加密的用法是：各家银行把交易特征加密后交给一个联合分析方，在密文上拼出跨行的资金流图、计算风险评分，最后只把"这个账户可疑"这一结论解密出来。类似的思路也用于联合信用评分和跨机构黑名单查询。实际系统里，同态加密常和安全多方计算（MPC）、私有集合求交（PSI）一起使用。

2.4 隐私机器学习推理

模型在服务器上，数据在用户手里，双方都不想把自己的东西交出去：

1. 用户把输入（比如一张胸片、一段语音特征）加密后发给服务器；
2. 服务器用明文模型在密文输入上跑推理，矩阵乘法用同态加法和乘法实现；
3. 返回加密的预测结果，只有用户能解密。

难点在于激活函数。ReLU、sigmoid 这类非多项式函数不能直接算，常见办法是用低次多项式近似（CKKS 擅长这个），或者用 TFHE 的可编程自举（programmable bootstrapping）直接查表。Zama 的 Concrete ML 就是把 scikit-learn 和 PyTorch 模型自动编译成 FHE 电路的工具。

2.5 电子投票

投票是同态加密最早的成功应用之一，用的是加法同态：

• 每张选票是 $\mathrm{Enc}(0)$ 或 $\mathrm{Enc}(1)$；
• 计票方把所有密文"加"起来，得到 $\mathrm{Enc}(\text{总票数})$；
• 只解密总数，任何单张选票都不会被解密。

开源的 Helios 投票系统就采用指数 ElGamal（见 3.3 节）来做同态计票，并配合零知识证明，确保每张选票确实是 $0$ 或 $1$，而不是 $\mathrm{Enc}(1000)$ 这种作弊票。

2.6 私有信息检索（PIR）

你想从一个公开数据库里查一条记录，又不想让数据库知道你查的是哪一条。

用同态加密的办法：把查询编码成一个加密的"选择向量" $\mathrm{Enc}(0), \dots, \mathrm{Enc}(1), \dots, \mathrm{Enc}(0)$（只有第 $i$ 位是 $1$），服务器计算

$$\sum_j \mathrm{Enc}(e_j)\cdot \mathrm{DB}_j = \mathrm{Enc}(\mathrm{DB}_i).$$

服务器对每条记录都做了同样的操作，所以完全不知道 $i$ 是多少。实际方案会把选择向量压缩、递归分层，以降低通信量。

2.7 业界现状

主要开源库

真实部署：Apple

• Live Caller ID Lookup（iOS 18，2024）：来电时，手机要向服务器查询"这个号码是谁、是不是骚扰电话"。Apple 用基于 BFV 的私有信息检索，手机发出的是加密后的号码查询，服务器在密文上完成查表，返回加密结果，服务器不知道你接到了谁的电话。
• Enhanced Visual Search（照片里识别地标）：同样用同态加密做加密的最近邻搜索，配合差分隐私和匿名网络中继。

此外，Google 开源了 FHE 编译器（HEIR 等），Intel 提供了加速库 HEXL，DARPA 的 DPRIVE 项目在资助专用的 FHE 加速芯片。标准化方面，ISO/IEC 18033-6 已经收录了 ElGamal 和 Paillier 这类部分同态方案，全同态方案的标准化（由 HomomorphicEncryption.org 社区推动）还在进行中。

2.8 性能代价

同态加密的主要问题是慢和大。

举个数量级的例子：参数 $n = 2^{14}$、$\log_2 q \approx 438$ 时，一个密文由两个多项式组成，大小约为

$$2 \times 2^{14} \times 438 \ \text{bit} \approx 1.4\times 10^{7}\ \text{bit} \approx 1.8\ \text{MB}.$$

好在借助批处理（batching，见 3.7 节），一个密文可以同时装几千个数做 SIMD 并行运算，摊下来的代价会低很多。

第三层：数学原理

3.1 RSA 的乘法同态

教科书式 RSA：选两个大素数 $p, q$，令 $n = pq$，$\varphi(n) = (p-1)(q-1)$，取 $e$ 满足 $\gcd(e, \varphi(n)) = 1$，再取 $d \equiv e^{-1} \pmod{\varphi(n)}$。

$$\mathrm{Enc}(m) = m^e \bmod n,\qquad \mathrm{Dec}(c) = c^d \bmod n.$$

乘法同态几乎是显然的：

$$\mathrm{Enc}(a)\cdot \mathrm{Enc}(b) = a^e b^e = (ab)^e = \mathrm{Enc}(ab) \pmod n.$$

用抽象代数的语言说，$x \mapsto x^e$ 是乘法幺半群 $(\mathbb{Z}_n, \cdot)$ 到自身的同态（限制到单位群 $\mathbb{Z}_n^\times$ 上是群自同构）。但它不保持加法：一般 $(a+b)^e \neq a^e + b^e$。所以 RSA 只是 PHE。

为什么教科书式 RSA 不安全

1. 确定性：同一个 $m$ 每次加密结果都一样。如果明文空间很小（比如投票只有"是/否"），攻击者把所有可能的明文都加密一遍对照就能破解。安全的公钥加密必须是随机化的，才能达到语义安全（IND-CPA）。
2. 可延展性（malleability）：攻击者不知道 $m$，但可以把 $c$ 换成 $c \cdot 2^e$，于是对方解密得到 $2m$。在"转账金额"这类场景里这是灾难。注意，同态性本身就是可延展性，所以任何同态加密都不可能达到最强的 IND-CCA2 安全，只能追求 IND-CPA。
3. 小明文攻击：若 $e = 3$ 且 $m^3 < n$，则 $c = m^3$ 在整数上根本没取模，直接开立方根就得到 $m$。

实际使用的 RSA 都会先做随机填充（如 OAEP），而填充恰好破坏了同态性。所以 RSA 的同态性更多是教学例子，而不是实用工具。

3.2 Paillier：加法同态

Paillier（1999）是最常用的加法同态方案，基于合数剩余假设：在 $\mathbb{Z}_{n^2}^\times$ 中区分 "$n$ 次幂" 与 "随机元" 是困难的。

密钥生成：取大素数 $p, q$，$n = pq$，$\lambda = \operatorname{lcm}(p-1, q-1)$，$g = n + 1$。定义 $L(x) = \dfrac{x - 1}{n}$，并令 $\mu = \lambda^{-1} \bmod n$。公钥 $(n, g)$，私钥 $(\lambda, \mu)$。

加密：明文 $m \in \mathbb{Z}_n$，随机选 $r \in \mathbb{Z}_n^\times$，

$$\mathrm{Enc}(m; r) = g^m r^n \bmod n^2.$$

解密：

$$\mathrm{Dec}(c) = L\!\left(c^\lambda \bmod n^2\right)\cdot \mu \bmod n.$$

为什么能解密：

• 二项式定理给出 $(1+n)^m = \sum_k \binom{m}{k} n^k \equiv 1 + mn \pmod{n^2}$，因为 $n^2$ 及更高次项都消失了。
• 由中国剩余定理 $\mathbb{Z}_{n^2}^\times \cong \mathbb{Z}_{p^2}^\times \times \mathbb{Z}_{q^2}^\times$，两个因子的阶 $p(p-1)$、$q(q-1)$ 都整除 $n\lambda$，所以每个元素的阶都整除 $n\lambda$，即 $r^{n\lambda} \equiv 1 \pmod{n^2}$。
• 于是 $c^\lambda = (1+n)^{m\lambda} r^{n\lambda} \equiv 1 + m\lambda n \pmod{n^2}$，$L(c^\lambda) = m\lambda \bmod n$，再乘 $\mu = \lambda^{-1}$ 就得到 $m$。

加法同态：

$$\mathrm{Enc}(m_1; r_1)\cdot\mathrm{Enc}(m_2; r_2) = g^{m_1+m_2}(r_1 r_2)^n = \mathrm{Enc}(m_1 + m_2;\ r_1 r_2) \pmod{n^2}.$$

密文乘法对应明文加法。顺带还有数乘：$\mathrm{Enc}(m)^k = \mathrm{Enc}(km)$。所以 Paillier 能算"加密数据的线性组合"，比如加权求和、平均值，但不能算两个密文明文的乘积。

3.3 ElGamal：乘法同态，以及"指数"版本的加法同态

设 $G = \langle g \rangle$ 是一个离散对数困难的循环群（如 $\mathbb{Z}_p^\times$ 的子群或椭圆曲线群）。私钥 $x$，公钥 $h = g^x$。

$$\mathrm{Enc}(m; k) = (g^k,\ m h^k),\qquad \mathrm{Dec}(c_1, c_2) = c_2 \cdot c_1^{-x}.$$

它天然是随机化的（每次选新的 $k$），在 DDH 假设下是 IND-CPA 安全的。分量相乘得到

$$(g^{k_1}, m_1 h^{k_1})\cdot (g^{k_2}, m_2 h^{k_2}) = (g^{k_1+k_2},\ m_1 m_2\, h^{k_1+k_2}) = \mathrm{Enc}(m_1 m_2;\ k_1 + k_2),$$

所以 ElGamal 是乘法同态的。

指数 ElGamal：把明文放到指数上，加密 $g^m$ 而不是 $m$：

$$\mathrm{Enc}(m; k) = (g^k,\ g^m h^k).$$

这样相乘得到 $g^{m_1+m_2}$，就变成了加法同态。代价是解密只能得到 $g^m$，还要再解一个离散对数才能拿到 $m$，所以只适合 $m$ 很小的情况。投票计票正好满足这一点（总票数不超过选民人数），这就是 Helios 的做法。

3.4 环同态，以及加密为什么只是"近似环同态"

回顾定义：环 $R, S$ 之间的映射 $\varphi: R \to S$ 若满足

$$\varphi(a + b) = \varphi(a) + \varphi(b),\qquad \varphi(ab) = \varphi(a)\varphi(b),\qquad \varphi(1) = 1,$$

就称为环同态。

为什么想要环同态：任何函数 $f: \mathbb{F}_2^k \to \mathbb{F}_2$ 都可以写成 $\mathbb{F}_2$ 上的多项式（加法 $=$ 异或，乘法 $=$ 与门），对 $\mathbb{Z}_t$ 上的函数也类似。若解密 $\mathrm{Dec}$ 是环同态，那么对任意多项式 $P$，

$$\mathrm{Dec}\big(P(c_1, \dots, c_k)\big) = P\big(\mathrm{Dec}(c_1), \dots, \mathrm{Dec}(c_k)\big).$$

即"在密文上算 $P$"等于"在明文上算 $P$"，这就能算任意函数，也就是全同态。

为什么不能真的是环同态：如果 $\mathrm{Enc}$ 本身是一个确定性的环同态 $\varphi: \mathbb{Z}_t \to S$，那么攻击者可以拿公开的运算做代数攻击。比如环同态必然满足 $\varphi(1) = 1_S$，而 $1_S$ 是公开的，于是攻击者能自己算出 $\varphi(2) = 1_S + 1_S$、$\varphi(3) = 1_S + 1_S + 1_S$……把所有明文的密文列成一张表，拿到任何密文一查便知，毫无安全性可言。用抽象代数的话说，由第一同构定理 $\operatorname{im}\varphi \cong \mathbb{Z}_t/\ker\varphi$，像的结构完全由公开的代数数据决定。

解决办法：加入噪声。现代方案中，

• 每个明文对应很多个密文（加密是随机的），
• 解密 $=$ "先做一个真正的环同态，再四舍五入去掉小噪声"。

真正保持运算的是相位（phase）映射，它是一个精确的同态；而"四舍五入"只在噪声足够小的时候才和运算相容。所以说加密是一个近似环同态：只要噪声没长太大，同态性就成立。

3.5 LWE 与 RLWE

LWE 问题（Learning With Errors，Regev 2005）：取模数 $q$，秘密向量 $s \in \mathbb{Z}_q^n$。给你很多组

$$(a_i,\ b_i = \langle a_i, s\rangle + e_i \bmod q),$$

其中 $a_i$ 均匀随机，$e_i$ 是很小的随机误差。要求找出 $s$（搜索版本），或者区分这些 $(a_i, b_i)$ 和均匀随机的数对（判定版本）。

• 若没有误差 $e_i$，这只是一个线性方程组，高斯消元就能解。
• 加了小误差以后，消元会把误差放大到不可控的程度，问题就变得很难。Regev 证明了，平均情况的 LWE 至少和格上某些最坏情况问题（如近似 GapSVP、SIVP）一样难。
• 目前没有已知的量子算法能有效解 LWE，所以格密码属于后量子密码，FHE 天然就是抗量子的。

一个最小的 LWE 加密（对称密钥，加密一个比特 $m \in \{0, 1\}$）：令 $\Delta = \lfloor q/2 \rfloor$，

$$\mathrm{Enc}(m) = (a,\ b) = \big(a,\ \langle a, s\rangle + e + \Delta m\big),\qquad \text{相位 } \varphi_s(a, b) = b - \langle a, s\rangle = \Delta m + e.$$

解密时看相位离 $0$ 近还是离 $\Delta$ 近。关键观察：相位映射 $\varphi_s$ 是 $\mathbb{Z}_q$-线性的（模同态），所以两个密文相加，相位也相加：

$$\varphi_s(c_1 + c_2) = \Delta(m_1 + m_2) + (e_1 + e_2).$$

RLWE（Ring-LWE，Lyubashevsky–Peikert–Regev 2010）：把向量换成多项式环

$$R_q = \mathbb{Z}_q[x]/(x^n + 1),\qquad n = 2^k.$$

样本变成 $(a,\ b = a\cdot s + e) \in R_q^2$，其中 $a, s, e$ 都是多项式，$e$ 的系数很小。好处有两个：

• 紧凑：一个多项式就相当于 LWE 里的 $n$ 个样本，密钥和密文都小得多；
• 快：多项式乘法可以用数论变换（NTT，即有限域上的 FFT）在 $O(n \log n)$ 内完成。

为什么是 $x^n + 1$：当 $n$ 是 $2$ 的幂时，$x^n + 1 = \Phi_{2n}(x)$ 是第 $2n$ 个分圆多项式，在 $\mathbb{Q}$ 上不可约（Eisenstein 判别法作用在 $x \mapsto x+1$ 后的多项式上）。由于 $x^n \equiv -1$，这个商环里的乘法是"负循环卷积"，计算方便，而且它的几何性质（典范嵌入）很好，能保证噪声增长可控。这正是抽象代数里的商环 $F[x]/(f)$。

3.6 噪声增长、模切换、自举

密文乘法与"代值同态"

在 RLWE 方案中，可以把一个密文 $(c_0, c_1)$ 看成关于未知量 $y$ 的一次多项式 $c(y) = c_0 + c_1 y \in R_q[y]$。解密的第一步就是代入 $y = s$：

$$\mathrm{ev}_s: R_q[y] \to R_q,\qquad c(y) \mapsto c(s) = c_0 + c_1 s.$$

这正是抽象代数里的代值同态（evaluation homomorphism），它是一个精确的环同态。于是两个密文的乘积就定义为多项式乘积：

$$c(y)\cdot c'(y) = c_0c_0' + (c_0c_1' + c_1c_0')\,y + c_1c_1'\, y^2,$$

它代入 $s$ 后恰好等于 $c(s)\cdot c'(s)$。乘完以后密文变成 $y$ 的二次式（三个分量），再用重线性化（relinearization，借助公开的 $s^2$ 的加密，即 key-switching key）把它变回一次式。

噪声如何增长：以 BGV 风格为例，设相位 $c(s) = m + t e$（明文在"低位"，模 $t$ 读出）。

加法让噪声线性增长，乘法让噪声平方级增长。连续做 $L$ 层乘法，噪声大约变成 $B^{2^L}$，指数爆炸。一旦噪声超过 $q/2$ 量级，取模就会"绕回"，解密出错。这就是 SHE 只能做有限次乘法的原因。

模切换（modulus switching，BGV 的核心技巧）：乘完一次后，把整个密文按比例缩小，

$$c \ \mapsto\ c' = \Big\lfloor \tfrac{q'}{q}\, c \Big\rceil,\qquad q' < q.$$

噪声也随之缩小 $q'/q$ 倍，而（经过适当的修正）明文不变。打个比方：噪声的绝对大小被压回原来的量级，代价是模数变小、"剩余空间"变少。实践中取 $q = q_0 q_1 \cdots q_L$ 为一串素数的乘积，每层乘法后"扔掉"一个素数，噪声从指数增长变成线性于层数 $L$。这串素数的表示用的就是中国剩余定理（RNS 表示），也是抽象代数的内容。

Gentry 的自举（bootstrapping）：层数用完了怎么办？Gentry 的想法是"用同态的方式运行解密算法"：

1. 事先把私钥 $s$ 用它自己（或另一把公钥）加密，公开 $\mathrm{Enc}(s)$，称为自举密钥。
2. 拿到一个噪声快满的密文 $c$。服务器把 $c$ 的每一位当作常数，把 $\mathrm{Enc}(s)$ 当作加密输入，同态地计算解密电路 $\mathrm{Dec}(\cdot, c)$： $$\mathrm{Eval}\big(\mathrm{Dec}(\cdot,\ c),\ \mathrm{Enc}(s)\big) = \mathrm{Enc}\big(\mathrm{Dec}(s, c)\big) = \mathrm{Enc}(m).$$
3. 结果仍然是 $m$ 的密文，但它的噪声只来自"计算解密电路"这一步，与原来 $c$ 里的噪声无关。

只要方案能同态地计算自己的解密电路并且还剩至少一次乘法的余量（称为 bootstrappable），就可以无限次"刷新"密文，从 SHE 升级为 FHE。

3.7 BGV、BFV、CKKS（以及 TFHE）的区别

三大主流 RLWE 方案的密文都在 $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ 上，区别在于明文放在相位的哪个位置：

CKKS 的核心想法：浮点运算本来就有舍入误差，那就干脆把加密噪声也当成舍入误差的一部分。明文 $m$ 是"真实值乘以缩放因子 $\Delta$ 再取整"，解密得到的是 $m + e$，只要 $e$ 相对于 $\Delta$ 很小，就只是丢了几位精度。乘法后相位变成 $\Delta^2 m m' + \cdots$，用 rescale（除以 $\Delta$ 并降低模数）恢复尺度，这和模切换是同一个操作。

批处理（SIMD）与中国剩余定理：对 BGV/BFV，若素数 $t \equiv 1 \pmod{2n}$，则 $\mathbb{Z}_t$ 中含有本原 $2n$ 次单位根 $\zeta$，于是 $x^n + 1$ 在 $\mathbb{Z}_t[x]$ 上分裂为 $n$ 个一次因子，由中国剩余定理得

$$R_t = \mathbb{Z}_t[x]/(x^n + 1) \;\cong\; \prod_{i=1}^{n} \mathbb{Z}_t[x]/(x - \zeta^{2i-1}) \;\cong\; \mathbb{Z}_t^n.$$

这个同构是环同构，所以 $R_t$ 里的一次乘法就等于 $n$ 个槽里各自做一次乘法。一个密文就能同时处理 $n$ 个数（$n = 2^{14}$ 时是 $16384$ 个）。CKKS 用的是类似的想法：通过典范嵌入 $R \to \mathbb{C}^{n}$ 把 $n/2$ 个复数装进一个多项式。

3.8 小结：从抽象代数看同态加密

延伸阅读

• Craig Gentry, A Fully Homomorphic Encryption Scheme, Stanford PhD thesis, 2009
• Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, 2005
• Brakerski, Gentry, Vaikuntanathan, (Leveled) Fully Homomorphic Encryption without Bootstrapping, 2012（BGV）
• Fan, Vercauteren, Somewhat Practical Fully Homomorphic Encryption, 2012（BFV）
• Cheon, Kim, Kim, Song, Homomorphic Encryption for Arithmetic of Approximate Numbers, 2017（CKKS）
• Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, 1999
• Microsoft SEAL、OpenFHE、Zama TFHE-rs 的官方文档与示例