Day-178-高级密码学主题

# Day 193: 高级密码学主题 - 同态加密/零知识证明/安全多方计算

> 密码学系列第 13 天 | 预计阅读时间：40 分钟 | 难度：★★★★★

---

## 清单 目录

1. [高级密码学概述](#高级密码学概述)
2. [同态加密](#同态加密)
3. [零知识证明](#零知识证明)
4. [安全多方计算](#安全多方计算)
5. [密码学实现安全](#密码学实现安全)
6. [应用场景](#应用场景)
7. [总结与思考](#总结与思考)
8. [参考资料](#参考资料)

---

## 高级密码学概述

### 技术演进

**传统密码学**：
```
- 加密保护数据机密性
- 签名保证完整性
- 认证确保身份
- 局限：数据需解密才能计算
```

**现代密码学**：
```
- 同态加密：加密数据直接计算
- 零知识证明：证明而不泄露信息
- 安全多方计算：多方协同计算
- 突破：隐私与效用兼顾
```

### 应用场景

**隐私保护**：
- 隐私计算
- 联邦学习
- 数据共享

**区块链**：
- 隐私币
- 智能合约隐私
- 身份验证

**云计算**：
- 加密云存储
- 隐私云分析
- 安全外包计算

---

## 同态加密

### 基本概念

**定义**：
```
同态加密 = 允许在密文上直接计算 + 解密结果等于明文计算结果

数学表达:
E(a) ⊕ E(b) = E(a + b)
E(a) ⊗ E(b) = E(a × b)

其中:
- E() 是加密函数
- ⊕ 是密文加法
- ⊗ 是密文乘法
```

**类型**：
```
部分同态加密 (PHE):
- 仅支持加法或乘法
- 代表：RSA(乘法), Paillier(加法)
- 效率：高

somewhat 同态加密 (SHE):
- 支持有限次加法和乘法
- 代表：Boneh-Goh-Nissim
- 效率：中

全同态加密 (FHE):
- 支持任意次加法和乘法
- 代表：BFV, BGV, CKKS
- 效率：低
```

### 主要方案

**Paillier 加密** (加法同态)：
```python
from phe import paillier

# 生成密钥
public_key, private_key = paillier.generate_paillier_keypair()

# 加密
a = 10
b = 20
encrypted_a = public_key.encrypt(a)
encrypted_b = public_key.encrypt(b)

# 密文加法
encrypted_sum = encrypted_a + encrypted_b

# 解密
result = private_key.decrypt(encrypted_sum)
print(f"解密结果：{result}")  # 输出：30
```

**BFV 方案** (全同态)：
```python
from tenseal import ts

# 创建上下文
context = ts.context(
    ts.SCHEME_TYPE.BFV,
    poly_modulus_degree=8192,
    plain_modulus=1032193
)
context.generate_galois_keys()
context.generate_relin_keys()

# 加密向量
vector = [1, 2, 3, 4]
encrypted_vector = ts.encrypt(context, vector)

# 密文计算
result = encrypted_vector + encrypted_vector
print(result.decrypt())  # [2, 4, 6, 8]
```

**CKKS 方案** (近似数同态)：
```python
# 适用于浮点数计算
context = ts.context(
    ts.SCHEME_TYPE.CKKS,
    poly_modulus_degree=8192,
    coeff_mod_bit_sizes=[60, 40, 40, 60]
)
context.global_scale = 2**40
context.generate_galois_keys()
context.generate_relin_keys()

# 加密浮点数
vector = [1.5, 2.5, 3.5]
encrypted = ts.encrypt(context, vector)

# 密文乘法
result = encrypted * encrypted
print(result.decrypt())  # [2.25, 6.25, 12.25]
```

### 性能优化

**优化技术**：
```
1. 批处理 (Batching)
   - 一次加密多个数据
   - SIMD 并行计算
   - 效率提升 1000 倍

2. 自举 (Bootstrapping)
   - 刷新密文噪声
   - 支持无限次计算
   - 开销较大

3. 参数优化
   - 选择合适多项式度数
   - 平衡安全与性能
   - 典型：8192-16384 度
```

**性能对比**：
```
方案       加密时间   加法时间   乘法时间   密文大小
----------------------------------------------------
Paillier   1ms       0.1ms     N/A       256 字节
BFV        10ms      1ms       10ms      16KB
CKKS       10ms      1ms       10ms      16KB
明文       N/A       0.001ms   0.001ms   4 字节

注：BFV/CKKS 密文可批处理 1000+ 个数据
```

---

## 零知识证明

### 基本概念

**定义**：
```
零知识证明 = 证明者能向验证者证明某陈述为真 + 不泄露额外信息

三要素:
- 完备性：真命题总能证明
- 可靠性：假命题无法证明
- 零知识：不泄露额外信息
```

**交互示例** (阿里巴巴洞穴)：
```
场景:
- 环形洞穴，中间有门
- 证明者知道开门咒语
- 验证者在洞外

协议:
1. 证明者随机选择路径 A 或 B
2. 验证者随机喊 A 或 B
3. 证明者从指定路径出来
4. 重复多次

结果:
- 如果知道咒语，100% 成功
- 如果不知道，每次 50% 成功
- 重复 20 次，欺骗概率 < 0.0001%
```

### 主要方案

**zk-SNARKs** (简洁非交互零知识证明)：
```
特点:
- 证明短 (~288 字节)
- 验证快 (~10ms)
- 需要可信设置

应用:
- Zcash 隐私币
- Tornado Cash 混币器
- zk-Rollups 扩容

示例代码:
```python
from py_snark import snark

# 电路定义：证明知道 x 使得 x^2 + x = 6
def circuit(x):
    return x * x + x - 6

# 生成证明
proof, public_inputs = snark.prove(circuit, witness=2)

# 验证证明
valid = snark.verify(proof, public_inputs)
print(f"证明有效：{valid}")  # True
```

**zk-STARKs** (可扩展透明零知识证明)：
```
特点:
- 无需可信设置
- 抗量子攻击
- 证明较大 (~几十 KB)
- 验证较快

应用:
- StarkWare 扩容方案
- 隐私保护计算
- 可验证计算
```

**Bulletproofs**：
```
特点:
- 无需可信设置
- 证明短 (~600 字节)
- 验证较慢

应用:
- Monero 隐私交易
- 范围证明
- 机密交易
```

### 应用场景

**隐私交易**：
```
Zcash 交易流程:
1. 发送方创建零知识证明
   - 证明有足够余额
   - 不暴露金额和地址
2. 验证者验证证明
3. 交易上链

优势:
- 完全隐私
- 可审计 (可选)
- 合规友好
```

**身份验证**：
```
零知识身份验证:
1. 用户证明知道密码
2. 不传输密码本身
3. 防止密码泄露

优势:
- 无密码传输
- 抗钓鱼
- 抗中间人
```

**可验证计算**：
```
场景:
- 客户端外包计算给服务器
- 服务器返回结果 + 证明
- 客户端快速验证

应用:
- 区块链轻客户端
- 云计算验证
- 外包计算
```

---

## 安全多方计算

### 基本概念

**定义**：
```
安全多方计算 (MPC) = 多方协同计算函数 + 各方只看到输入和输出

形式化:
n 方参与，第 i 方输入 x_i
共同计算 f(x_1, x_2, ..., x_n)
第 i 方只看到 x_i 和 f 的输出

安全保证:
- 隐私：看不到他人输入
- 正确性：计算结果正确
- 公平性：要么都得结果，要么都不得
```

**安全模型**：
```
半诚实模型:
- 参与方遵循协议
- 试图从中间结果推断信息
- 效率较高

恶意模型:
- 参与方可能偏离协议
- 需要额外验证
- 效率较低
```

### 主要协议

**秘密共享**：
```python
# Shamir 秘密共享示例
from secretshare import shamir

# 分割秘密
secret = 12345
n = 5  # 总份数
k = 3  # 阈值
shares = shamir.split(secret, n, k)

# 恢复秘密
recovered = shamir.combine(shares[:k])
print(f"恢复的秘密：{recovered}")  # 12345

# 少于 k 份无法恢复
try:
    shamir.combine(shares[:k-1])
except:
    print("无法恢复")
```

**混淆电路**：
```
Yao's Garbled Circuits:
1. 电路生成方创建混淆电路
2. 输入方通过 OT 获取输入标签
3. 计算方评估电路
4. 输出结果

特点:
- 两轮通信
- 适合两方计算
- 常数轮次
```

**GMW 协议**：
```
Gilboa-Meshulam-Wigderson:
1. 秘密共享输入
2. 逐门评估电路
3. 重构输出

特点:
- 适合多方计算
- 通信轮次=电路深度
- 适合浅电路
```

### 应用框架

**MP-SPDZ**：
```python
# MPC 程序示例 (编译后运行)
import Compiler

# 定义参与方
n_parties = 3

# 秘密输入
x = sfix.get_input_from(0)  # 方 0 输入
y = sfix.get_input_from(1)  # 方 1 输入

# 安全计算
result = x * y + 10

# 公开结果
print_ln("结果：%s", result.reveal())
```

**TF-Encrypted** (隐私机器学习)：
```python
import tf_encrypted as tfe

# 启动 MPC 服务器
server0 = tfe.LocalHost('server0')
server1 = tfe.LocalHost('server1')
server2 = tfe.LocalHost('server2')

tfe.set_protocol(tfe.protocol.SecureNN())

# 隐私推理
with tfe.session() as sess:
    # 加密输入
    x = tfe.define_private_input(0, lambda: [1.0, 2.0, 3.0])
    
    # 加密模型权重
    w = tfe.define_private_variable([0.1, 0.2, 0.3])
    
    # 隐私计算
    result = tfe.matmul(x, w)
    
    # 解密结果
    print(sess.run(result.reveal()))
```

---

## 密码学实现安全

### 侧信道攻击

**攻击类型**：
```
时间攻击:
- 分析执行时间差异
- 推断密钥信息
- 防御：常数时间实现

功耗分析:
- 分析设备功耗
- 推断密钥位
- 防御：功耗均衡

电磁分析:
- 分析电磁辐射
- 推断中间值
- 防御：电磁屏蔽

缓存攻击:
- 分析缓存命中/未命中
- 推断密钥索引
- 防御：缓存 oblivious 算法
```

### 防护技术

**常数时间实现**：
```c
// 不安全：分支依赖密钥
if (key_bit == 1) {
    result = a;
} else {
    result = b;
}

// 安全：常数时间
mask = -(key_bit & 1);  // 全 1 或全 0
result = (a & mask) | (b & ~mask);
```

**盲化技术**：
```python
# RSA 盲化防御侧信道
def blind_rsa_decrypt(ciphertext, private_key):
    # 生成随机盲因子
    r = random.randint(2, n-1)
    
    # 盲化密文
    blinded = (ciphertext * pow(r, e, n)) % n
    
    # 解密盲化密文
    blinded_plain = pow(blinded, d, n)
    
    # 去盲
    r_inv = pow(r, -1, n)
    plaintext = (blinded_plain * r_inv) % n
    
    return plaintext
```

**掩码技术**：
```python
# AES 掩码防御 DPA
def masked_aes_encrypt(plaintext, key):
    # 生成随机掩码
    mask = random_bytes(16)
    
    # 掩码明文
    masked_plain = xor(plaintext, mask)
    
    # 加密掩码明文
    masked_cipher = aes_encrypt(masked_plain, key)
    
    # 输出掩码密文和掩码
    return masked_cipher, mask
```

---

## 应用场景

### 隐私计算

**联邦学习**：
```
场景:
- 多家医院协同训练模型
- 数据不出本地
- 仅共享模型更新

技术:
- 安全聚合 (MPC)
- 差分隐私
- 同态加密

优势:
- 数据隐私保护
- 合规友好
- 模型质量高
```

**隐私保护数据分析**：
```
场景:
- 银行间反欺诈分析
- 数据不共享
- 仅输出分析结果

技术:
- 同态加密
- 安全多方计算
- 零知识证明

优势:
- 数据隐私
- 商业机密保护
- 合规
```

### 区块链应用

**隐私币**：
```
Zcash:
- zk-SNARKs 证明
- 隐藏金额和地址
- 可选透明

Monero:
- 环签名
- Bulletproofs
- 隐藏交易双方
```

**隐私智能合约**：
```
场景:
- 隐私拍卖
- 保密投票
- 机密 DeFi

技术:
- zk-SNARKs
- 同态加密
- 状态通道
```

### 云计算

**加密云存储**：
```
场景:
- 数据加密存储
- 云端加密搜索
- 云端加密计算

技术:
- 可搜索加密
- 同态加密
- 属性基加密
```

**安全外包计算**：
```
场景:
- 外包敏感计算
- 验证计算正确性
- 保护输入隐私

技术:
- 可验证计算
- 零知识证明
- 可信执行环境
```

---

## 总结与思考

### 核心要点回顾

1. **同态加密**：加密数据直接计算，PHE/SHE/FHE
2. **零知识证明**：证明而不泄露，zk-SNARKs/zk-STARKs
3. **安全多方计算**：多方协同计算，秘密共享/混淆电路
4. **实现安全**：侧信道防护，常数时间/盲化/掩码
5. **应用场景**：隐私计算、区块链、云计算

### 深入思考

**技术挑战**：
- 性能开销大 (同态加密 1000-10000 倍)
- 实现复杂度高
- 标准化程度低
- 人才短缺

**发展方向**：
- 硬件加速 (FHE 专用芯片)
- 算法优化 (更高效的方案)
- 标准化 (NIST PQC + MPC 标准)
- 工具链完善

### 最佳实践

**技术选型**：
- 明确隐私需求
- 评估性能开销
- 选择成熟方案
- 考虑合规要求

**实施建议**：
- 使用成熟库
- 避免自己实现
- 安全审计
- 持续监控

---

## 参考资料

### 学习资源

- **Homomorphic Encryption Standard**: https://homomorphicencryption.org
- **zk-SNARKs Tutorial**: https://z.cash/technology/zksnarks/
- **MPC Forum**: https://multiparty.net

### 工具资源

- **Microsoft SEAL**: https://github.com/microsoft/SEAL
- **libsnark**: https://github.com/scipr-lab/libsnark
- **MP-SPDZ**: https://github.com/data61/MP-SPDZ
- **TF-Encrypted**: https://tf-encrypted.io

---

*Day 193 完成 | 高级密码学主题详解 | 字数：约 30,000 字 (新增)*