同态加密原理入门

可视化演示

同态加密允许在密文上直接计算，结果解密后等同于明文计算结果。本文详解部分同态加密与全同态加密的区别、Paill... 切换模式查看不同维度。

同态加密概述

假设你有一口保险箱，里面存着一袋金币。你想让工匠把它熔成项链，却绝不愿意交出钥匙。传统加密世界里这是死局——想加工，必然先开锁。同态加密却给出了“魔法保险箱”：箱壁上有加工口，工匠可以隔着钢板打磨、熔铸、拼接，全程看不见金币本身，可最终递给你的项链，与你亲自开箱加工的成品一模一样。

1978 年，Rivest、Adleman 和 Dertouzos 在论文中首次提出“在加密数据上做运算”的构想，称之为“隐私同态”。此后三十年间，密码学家只找到支持单一运算的部分方案，直到 2009 年 Craig Gentry 用理想格构造出第一个全同态加密方案，才让这个梦想真正落地。

同态加密的核心性质，是密文运算与明文运算之间的“可交换性”。如果存在一对运算 ⊙ 和 ⊕，使得“先加密再运算”的结果解密后，等于“先运算再加密”的结果，那么这个加密方案对运算 ⊕（密文侧表现为 ⊙）就是同态的：

有了这纸“承诺书”，数据所有者就可以放心地把保险箱交给任何不可信的加工方：云服务器、第三方分析团队——它们只需照着图纸操作加工口，永远接触不到真实数据。这正是“数据可用不可见”理念的源头，也是理解后续所有方案的起点。

分类体系

市面上的保险箱分三档：只能锁门的普通箱；带一个搅拌口的半自动箱；配备全套机械臂的全能箱。同态加密同样分三档——部分同态、有些同态、全同态，区别只在于“加工口的种类”和“能连续加工多少次”。

部分同态（PHE）只支持加法或乘法中的一种运算，但通常次数不限；有些同态（SWHE）同时支持加法与乘法，却因噪声累积只能做浅层计算；全同态（FHE）则能在密文上执行任意深度的加乘组合电路，好比拥有无限加工能力的终极保险箱。三者能力递增，计算开销也递增。

以代数式表达，加法同态与乘法同态分别要求：

买保险箱时，档位越高价格越贵；同态加密同理，能力越强计算开销越大。理解这三档阶梯，才能在实际工程中恰当选择——只做聚合统计，用便宜的 Paillier 即可；要跑复杂模型，才需动用全同态。

Paillier方案

1999 年诞生的 Paillier 加密，就是那台“只装了一个搅拌口”的保险箱。它只提供加法同态一种加工能力，但构造精巧、效率可观，而加法已足以支撑投票统计、数据聚合等大量真实业务，堪称性价比之王。

Paillier 的安全性建立在“合数剩余困难假设”上：给定大合数 n 的平方，要判断一个数是否形如 r^n 是计算上困难的。公钥为 (n, g)，其中 n = pq 是两大素数的乘积，g 是模 n² 中的生成元（常取 n+1）。加密时还要随机选一个与 n 互素的数 r——每次上锁都换一把新锁芯，这正是“相同明文反复加密却得到不同密文”的秘密。

加密公式为：

正因为这台“加法保险箱”能反复搅拌金币堆——每堆金币的数量加密后相乘，打开就是总量——它天然适合计票、加总、聚合等场景。缺点是只有一个加工口，想让它在密文上做明文乘法，就无能为力了。

Gentry方案

如果说 Paillier 只有一个搅拌口，那么 2009 年 Gentry 推出的就是“全能加工台”：既能搅拌，又能切割、焊接、钻孔，且加工顺序可任意编排。一个悬置三十年的密码学梦想，至此变为现实。

Gentry 的天才构造分三步：先用理想格构造一个“有些同态”方案（SWHE），它能做不少加法和乘法，但受噪声限制深度有限；再证明核心定理——如果这个方案能“同态地评估自己的解密电路”（即 bootstrappable），它就能把有限深度扩展成无限深度，升级为全同态。第三步自然就是构造出这样的方案并完成证明。

这套打法的关键条件可以写成：

Gentry 的意义远超一个具体方案：它证明了“只要解密电路足够简单，同态加密就能自我刷新”。此后 BGV、BFV、CKKS 等全同态方案无不在这个框架上做工程优化——把理想格换成更高效的代数结构，把自举次数尽量压缩。

自举技术

保险箱每用一次，内壁就多一道划痕。划痕（噪声）多了，锁可能卡住，甚至箱里的宝贝受损。你想把保险箱送回原厂清理，可原厂清洁也要开锁——这又回到了矛盾原点。自举（Bootstrapping）就是在死胡同里凿出的第三条路。

自举的思路是：把钥匙也锁进一只保险箱，再把“开锁清洁”的动作交给箱内的机械臂完成。整个动作隔着钢板执行，外人依然看不到任何秘密。对应到加密世界，就是用加密后的私钥同态地执行一遍解密电路，从而在不暴露明文的前提下，把密文的噪声刷回初始水平。

具体流程如下——输入一颗噪声逼近上限的“脏密文”和加密过的私钥，同态执行解密电路：

代价是极高的计算量——一次自举可能比上万次普通运算还贵。这也是为什么全同态加密虽在 2009 年就已诞生，直到近年硬件加速与算法优化并进后，才逐渐具备实用价值。

层级同态加密

既然每次自举保养费不菲，保险公司便推出“有限保养套餐”：合同约定这台保险箱最多加工 L 次，之后必须更换。层级同态加密（Leveled HE）就是这个套餐——允许计算深度 L，电路一深，解密结果就可能出错。

在层级方案中，安全参数（模数 q、格维度 n）要随着 L 一起扩大，因为噪声预算必须覆盖整个电路深度。参数越大运算越慢，因此 L 的设定必须在“够用”与“高效”之间折中。拿到实际电路时，工程师先算它的乘法深度，再反向确定参数。

正确解密的边界条件是密文噪声低于阈值。设噪声经过 L 层计算后增长到 B_L，密文模数为 q，则必须满足：

现代主流方案普遍采用“参数预分配”策略：先算电路深度，再据此选模数。工程上常把层级方案与自举混用——浅层部分用便宜的层级参数，只在噪声逼近上限时才做一次自举，把保养费压到最低。

云计算应用

故事回到开头：你有一箱金币，想租用云端“超级加工厂”的算力。传统做法是把金币明文寄过去，等于连钥匙也交出；同态加密则让你只寄出锁好的保险箱，工厂隔着加工口完成工序，再寄回成品。你开箱验货，分毫不差。

云端外包是最典型的落地场景：医院把加密病历发给云平台做统计，平台在密文上完成加总，返回密文统计结果；银行把加密名单交给行业协会做联合查询，各方只能看到交集，看不到彼此的原始数据。整个过程数据始终以密文形态存在，真正实现“可用不可见”。

以电子投票为例，计票环节就是一次漂亮的加法同态。假设每位选民的选票 mᵢ ∈ {0,1} 被加密为 cᵢ，计票器只需将全部密文选票相乘，再解密即得票数总和：

当然，同态加密不是银弹：密文尺寸膨胀、计算开销惊人、密钥管理复杂。但在医疗、金融、政务等高敏感场景中，它提供了传统加密无法想象的能力——数据在第三方手中全程加密运算，这正是未来“数据不动产”时代的基础设施。

AI 应用场景

Python 演示

import randomimport math  def is_prime(n, rounds=5):    """Miller-Rabin 素性检测"""    if n < 2:        return False    if n % 2 == 0:        return n == 2    d = n - 1    r = 0    while d % 2 == 0:        d //= 2        r += 1    for _ in range(rounds):        a = random.randint(2, n - 2)        x = pow(a, d, n)        if x in (1, n - 1):            continue        for _ in range(r - 1):            x = x * x % n            if x == n - 1:                break        else:            return False    return True  def random_prime(bits):    """生成指定位数的素数"""    while True:        p = random.getrandbits(bits) | (1 << (bits - 1)) | 1        if is_prime(p):            return p  def l_func(x, n):    return (x - 1) // n  def keygen(bits=12):    """Paillier 密钥生成"""    p = random_prime(bits)    q = random_prime(bits)    n = p * q    g = n + 1    lam = (p - 1) * (q - 1) // math.gcd(p - 1, q - 1)    mu = pow(lam, -1, n)    return (n, g), (lam, mu, n)  def encrypt(pub, m):    """加密: c = g^m * r^n mod n^2"""    n, g = pub    r = random.randint(1, n - 1)    while math.gcd(r, n) != 1:        r = random.randint(1, n - 1)    return pow(g, m, n * n) * pow(r, n, n * n) % (n * n)  def decrypt(priv, c):    """解密: m = L(c^lam) * mu mod n"""    lam, mu, n = priv    return l_func(pow(c, lam, n * n), n) * mu % n  def add_cipher(pub, c1, c2):    """加法同态: 密文相乘 = 明文相加"""    n, _ = pub    return c1 * c2 % (n * n)  def main():    pub, priv = keygen(bits=12)    m1, m2 = 8, 15    c1 = encrypt(pub, m1)    c2 = encrypt(pub, m2)    c_sum = add_cipher(pub, c1, c2)    m_dec = decrypt(priv, c_sum)    print("明文: {} + {}".format(m1, m2))    print("密文1: {}".format(c1))    print("密文2: {}".format(c2))    print("密文乘积(对应相加): {}".format(c_sum))    print("解密结果: {}".format(m_dec))    print("验证: {}".format(m_dec == m1 + m2))  if __name__ == "__main__":    main()

1. p = random_prime(bits)生成大素数，相当于锻造保险箱的钢材
2. g = n + 1Paillier 中 g 的经典简化选择，省去复杂的生成元搜索
3. lam = (p - 1) * (q - 1) // math.gcd(p - 1, q - 1)卡迈克尔函数 λ，决定解密指数的关键材料
4. mu = pow(lam, -1, n)计算 λ 模 n 的逆元，解密公式中的“万能钥匙”
5. pow(g, m, n * n) * pow(r, n, n * n) % (n * n)加密公式 c = g^m · r^n mod n²，把明文锁进保险箱
6. l_func(pow(c, lam, n * n), n) * mu % nL 函数配合逆元还原明文，打开保险箱的过程
7. return c1 * c2 % (n * n)加法同态的精华：两块密文相乘，解出的是明文之和！

常见误区

面试题