Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

第五十三 同态加密

数据不解密也能算：让加密数据“活“起来

在传统的密码学应用中，数据必须先解密才能进行计算。这意味着处理敏感数据时，必须在安全的环境中解密，计算完成后再重新加密。如果数据需要交由第三方（如云计算服务商）处理，就必须将明文暴露给对方，带来潜在的隐私泄露风险。

同态加密（Homomorphic Encryption, HE）打破了这一限制。它允许在密文上直接进行计算，计算结果解密后与在明文上计算的结果一致。换句话说，数据始终保持加密状态，却能“参与“运算——这是密码学领域最具颠覆性的技术之一。

53.1 什么是同态加密

直观理解

想象你有一位不信任的会计，你需要让他帮你计算年度总支出，但又不想让他看到每一笔具体的开支金额。同态加密就像给每一张账单都套上一个不透明的信封，会计可以在信封上进行某种“魔法操作“，最终得到一个结果信封。你打开结果信封，里面正是所有账单金额的总和——而会计自始至终都没有看到任何一张账单的具体数字。

形式化定义

一个加密方案称为同态的，如果满足：

Decrypt( Evaluate( f, Encrypt(m1), Encrypt(m2), ..., Encrypt(mn) ) ) = f(m1, m2, ..., mn)

其中 f 是任意计算函数。也就是说，对密文进行计算后再解密，等于先解密再计算。

同态性的分类

根据支持的运算类型和深度，同态加密分为三个层次：

部分同态加密（PHE, Partially Homomorphic Encryption）

只支持无限次的某一种运算（加法或乘法），但不能同时进行两种运算。

  • 加法同态：支持任意次数的密文相加

    • 典型代表：Paillier、Benaloh、Naccache-Stern
    • 应用：电子投票、隐私保护求和

  • 乘法同态：支持任意次数的密文相乘

    • 典型代表：RSA（未经填充的原始RSA）、ElGamal
    • 应用：隐私保护乘积计算

somewhat 同态加密（SHE, Somewhat Homomorphic Encryption）

同时支持加法和乘法运算，但运算深度有限。随着计算步骤的增加，密文中的“噪声“会累积，超过一定阈值后就无法正确解密。

  • 典型代表：BGV（Brakerski-Gentry-Vaikuntanathan）的早期版本
  • 特点：可以计算任意多项式，但多项式的次数受限

全同态加密（FHE, Fully Homomorphic Encryption）

支持任意次数的加法和乘法运算，理论上可以计算任何可计算函数。这是密码学的“圣杯“，直到2009年才由 Craig Gentry 首次实现。

  • 典型代表：
    • Gentry 方案（基于理想格）
    • BGV/BFV 方案（基于环上学习 with 错误，RLWE）
    • CKKS 方案（支持浮点数近似计算）
    • TFHE 方案（快速布尔电路计算）
类型加法乘法运算深度效率成熟度
PHE无限次0次 或 无限次无限制（单一运算）高成熟
SHE有限次有限次受限中较成熟
FHE无限次无限次无限制低快速发展中

53.2 Paillier 算法简介

Paillier 加密系统是由 Pascal Paillier 于1999年提出的概率公钥加密方案，是目前最著名且应用最广泛的加法同态加密算法。

核心特性

  1. 加法同态性：

    E(m1) * E(m2) = E(m1 + m2)

    两个密文相乘，解密后得到明文之和。

  2. 明文乘法：

    E(m)^k = E(m * k)

    密文的 k 次幂，解密后得到明文与 k 的乘积。

  3. 概率加密：相同的明文加密后会产生不同的密文，提供语义安全性。

数学基础

Paillier 的安全性基于合数剩余类问题（Composite Residuosity Assumption）：给定合数 n = pq（两个大素数之积），区分 n² 阶的 n 次剩余和非剩余是困难的。

密钥生成

1. 选择两个大素数 p 和 q，满足 gcd(pq, (p-1)(q-1)) = 1
2. 计算 n = p * q，λ = lcm(p-1, q-1)
3. 选择随机整数 g ∈ Z*_{n²}
4. 计算 μ = (L(g^λ mod n²))^{-1} mod n，其中 L(x) = (x-1)/n
5. 公钥：(n, g)，私钥：(λ, μ)

53.3 应用场景

隐私计算（Privacy-Preserving Computation）

在云计算场景中，用户可以将加密数据上传到云端，云服务商在不知道明文的情况下完成计算并返回结果。典型应用包括：

  • 隐私保护机器学习：在加密数据上训练或推理模型
  • 加密数据库查询：SQL 查询在密文上执行
  • 安全统计分析：医院联合计算疾病发病率，不泄露患者数据

安全多方计算（MPC, Multi-Party Computation）

多个参与方希望共同计算一个函数，但各自的数据保持私密。同态加密是 MPC 的重要构建模块之一。

例如：多家银行想计算行业平均存款额，但不想暴露各自的存款数据。通过同态加密，每家银行加密自己的数据上传，计算方在密文上求平均，结果只有各方联合才能解密。

电子投票

利用加法同态性，可以设计隐私保护的电子投票系统：

  • 每个选民加密自己的选票（0或1）
  • 将所有密文相乘（同态加法）得到总票数密文
  • 只有选举委员会能解密最终结果
  • 任何中间人都无法知道单个选民的投票选择

隐私保护机器学习

在联邦学习中，各参与方上传加密的模型梯度，服务器在密文上聚合更新全局模型，无需看到任何一方的原始梯度数据。

53.4 Rust 实现

Rust 生态中有多个同态加密库可供选择。下面介绍使用 rust-paillier 进行加法同态加密的示例。

Cargo.toml 依赖

[dependencies]
paillier = "0.4"
rand = "0.8"

基础加密解密示例

use paillier::{Keypair, EncryptionKey, DecryptionKey};
use paillier::Paillier;
use rand::thread_rng;

fn main() {
    // 1. 生成密钥对（实际应用应使用更大的密钥，如2048位）
    let (ek, dk): (EncryptionKey, DecryptionKey) = Paillier::keypair(&mut thread_rng()).keys();

    // 2. 待加密的明文
    let m1 = 10u64;
    let m2 = 20u64;

    // 3. 加密
    let c1 = Paillier::encrypt(&ek, m1);
    let c2 = Paillier::encrypt(&ek, m2);

    println!("明文 m1 = {}, m2 = {}", m1, m2);
    println!("密文 c1 = {:?}", c1);
    println!("密文 c2 = {:?}", c2);

    // 4. 解密验证
    let d1 = Paillier::decrypt(&dk, &c1);
    let d2 = Paillier::decrypt(&dk, &c2);

    println!("解密 d1 = {}, d2 = {}", d1, d2);
    assert_eq!(m1, d1);
    assert_eq!(m2, d2);
}

加法同态运算

use paillier::{EncryptionKey, DecryptionKey, Paillier};
use rand::thread_rng;

fn main() {
    let (ek, dk): (EncryptionKey, DecryptionKey) = Paillier::keypair(&mut thread_rng()).keys();

    let m1 = 15u64;
    let m2 = 25u64;

    // 加密两个明文
    let c1 = Paillier::encrypt(&ek, m1);
    let c2 = Paillier::encrypt(&ek, m2);

    // 同态加法：密文相乘 = 明文相加
    let c_sum = Paillier::add(&ek, &c1, &c2);

    // 解密结果
    let m_sum = Paillier::decrypt(&dk, &c_sum);

    println!("{} + {} = {} (同态计算结果)", m1, m2, m_sum);
    assert_eq!(m_sum, m1 + m2);

    // 同态数乘：密文的 k 次幂 = 明文乘以 k
    let k = 3u64;
    let c_mul = Paillier::mul(&ek, &c1, k);
    let m_mul = Paillier::decrypt(&dk, &c_mul);

    println!("{} * {} = {} (同态计算结果)", m1, k, m_mul);
    assert_eq!(m_mul, m1 * k);
}

隐私保护求和场景

#![allow(unused)]
fn main() {
use paillier::{EncryptionKey, DecryptionKey, Paillier};
use rand::thread_rng;

/// 模拟隐私保护求和：多个参与方贡献数据，计算总和但不泄露各自数据
fn privacy_preserving_sum() {
    let (ek, dk): (EncryptionKey, DecryptionKey) = Paillier::keypair(&mut thread_rng()).keys();

    // 三个参与方的敏感数据
    let alice_salary = 5000u64;
    let bob_salary = 7000u64;
    let charlie_salary = 6000u64;

    // 各自加密自己的数据
    let c_alice = Paillier::encrypt(&ek, alice_salary);
    let c_bob = Paillier::encrypt(&ek, bob_salary);
    let c_charlie = Paillier::encrypt(&ek, charlie_salary);

    println!("Alice 加密了工资数据");
    println!("Bob 加密了工资数据");
    println!("Charlie 加密了工资数据");

    // 计算服务方在密文上求和（看不到任何明文）
    let c_total = Paillier::add(
        &ek,
        &Paillier::add(&ek, &c_alice, &c_bob),
        &c_charlie,
    );

    // 只有持有私钥的一方能解密结果
    let total_salary = Paillier::decrypt(&dk, &c_total);
    let expected = alice_salary + bob_salary + charlie_salary;

    println!("工资总和 = {} (期望: {})", total_salary, expected);
    assert_eq!(total_salary, expected);

    // 还可以计算平均值（同态数乘实现除法）
    let count = 3u64;
    let c_avg = Paillier::mul(&ek, &c_total, 1); // 这里简化为先解密再除，实际可用更复杂协议
    let avg_salary = Paillier::decrypt(&dk, &c_avg) / count;
    println!("平均工资 = {}", avg_salary);
}
}

全同态加密的 Rust 生态

对于需要全同态加密的场景，Rust 生态正在快速发展：

  • concrete：Zama 公司开发的全同态加密库，基于 TFHE 方案，支持布尔和整数运算
  • fhe.rs：纯 Rust 实现的 FHE 库，支持 BFV 和 BGV 方案
  • sunscreen：提供编译器将普通 Rust 代码转换为 FHE 电路
[dependencies]
concrete = "0.8"

#![allow(unused)]
fn main() {
// concrete 库的简单示例（概念演示）
use concrete::*;

fn fhe_example() -> Result<(), CryptoAPIError> {
    // 1. 定义加密参数
    let secret_key = LWESecretKey::new(&LWE128_630);
    
    // 2. 创建编码器（定义明文的数值范围）
    let encoder = Encoder::new(-10., 10., 5, 1)?;
    
    // 3. 加密明文
    let m1 = 3.;
    let m2 = 5.;
    let c1 = LWE::encode_encrypt(&secret_key, m1, &encoder)?;
    let c2 = LWE::encode_encrypt(&secret_key, m2, &encoder)?;
    
    // 4. 同态加法
    let c_add = &c1 + &c2;
    
    // 5. 解密
    let m_add = c_add.decrypt_decode(&secret_key)?;
    println!("{} + {} = {}", m1, m2, m_add);
    
    Ok(())
}
}

53.5 同态加密的挑战与展望

当前挑战

  1. 计算开销大：FHE 的密文膨胀严重，计算速度比明文慢数万到数百万倍
  2. 噪声管理：SHE/FHE 需要复杂的噪声控制机制（如自举 bootstrapping）
  3. 功能限制：部分方案只支持整数运算，浮点数支持仍在发展中
  4. 标准化不足：相比传统密码学，HE 的标准化工作仍在初期

发展趋势

  • 硬件加速：专用 FPGA/ASIC 加速器正在开发，有望将性能提升数个数量级
  • 方案优化：CKKS 方案在机器学习场景中表现优异，TFHE 在布尔电路中效率突出
  • 混合方案：将同态加密与 MPC、零知识证明等技术结合，取长补短

53.6 本章总结

概念说明典型算法/库
PHE部分同态加密，支持无限次单一运算Paillier、ElGamal
SHEsomewhat 同态加密，支持有限深度加减乘BGV（早期）、BFV
FHE全同态加密，支持任意计算CKKS、TFHE、concrete
加法同态密文相乘等价于明文相加Paillier
乘法同态密文相乘等价于明文相乘RSA、ElGamal
噪声密文中累积的计算误差，需控制或刷新Bootstrapping

练习建议

  1. 基础练习：使用 rust-paillier 实现一个加密计算器，支持密文加法和数乘运算，验证同态性质。

  2. 中级练习：模拟电子投票系统：10个选民各自加密投票（0或1），在密文上统计总票数，确保单个投票不可追踪。

  3. 高级练习：调研 concrete 或 fhe.rs 库，实现一个简单的全同态加密示例（如密文上的多项式求值），分析其性能开销。

  4. 实践项目：设计一个隐私保护的数据聚合服务：多个客户端上传加密数据，服务端在密文上计算统计指标（均值、方差），客户端联合解密结果。