Chapter 1 引言¶
1 安全多方计算（MPC）概览¶
- 核心问题：一组互不信任的参与方 \(P_{1}, ..., P_{n}\)，各自持有隐私输入 \(x_{i}\)，需在不泄露隐私的前提下，协同计算函数 \(y=f(x_{1}, ..., x_{n})\)
理想世界 VS 现实世界
| 理想世界（Trusted Third Party, TTP） | 现实世界（Real World） |
|---|---|
| 参与方将 \(x_{i}\) 发送给可信第三方 \(T\)，\(T\) 计算并发布 \(y\) | 去中心化（无 \(TTP\)），参与方直接协同计算 |
| 缺点：单点故障，现实中无完全可信的 \(TTP\) | \(\textbf{·}\) 正确性（Correctness）：输出 \(y\) 正确 \(\textbf{·}\) 隐私性（Privacy）：仅泄露 \(y\)，不泄露任何 \(x_{i}\) |
第一价格密封拍卖（First-price sealed-bid auction）
- 输入：竞拍者 \(P_i\) 的出价 \(x_i\)（保密）
- 函数：\(f(x_1, \dots, x_n) = (\max(x_i), \text{winner}\_\text{id})\)
- 要求：只公布最高价和赢家，严禁泄露失败者的出价
电子投票
- 输入：\(x_i \in \{0, 1\}\)（反对/赞成）
- 函数：\(y = \sum x_i\)
- 要求：统计总票数，不暴露个人投票情况
2 安全加法协议（Secure Addition）¶
秘密分享（Secret Sharing）
- 目标：将秘密 \(x \in \mathbb{Z}_{p}\) 由 \(P_1\) 分享给 \(P_1、P_2、P_3\)
- 可重构：秘密可通过份额恢复，\(x = r_1 + r_2 + r_3\)
- 隐私性：任意单个参与方因缺失一个分量，无法恢复秘密 \(x\)（信息论安全）
- 目标：安全计算所有参与方输入的和 \(y=\sum x_{i}\)
- 前提：参与方 \(P_1、P_2、P_3\) 已对各自输入 \(x_i\) 完成秘密分享
- 执行步骤：
- 本地求和：每个参与方将其持有的所有 \(x_i\) 的对应份额分别相加
- 例：\(P_1\) 持有 \((r_{i,2}, r_{i,3})\)（\(i=1,2,3\)），计算 \(s_2=\sum_{i} r_{i,2}\)、\(s_3=\sum_{i} r_{i,3}\)
- 份额公布：\(P_1\) 公布 \(s_2、s_3\)，\(P_2\) 公布 \(s_1、s_3\)，\(P_3\) 公布 \(s_1、s_2\)
- 结果重构：所有参与方共同计算 \(y = s_1 + s_2 + s_3 \mod p\)
- 本地求和：每个参与方将其持有的所有 \(x_i\) 的对应份额分别相加
安全性证明思路
基于模拟（Simulation），给定输出 \(y\) 和输入 \(x_i\)，可模拟出所有中间计算视图，无额外隐私泄露。
3 安全乘法协议（Secure Multiplication）¶
- 目标：安全计算两个秘密的乘 \(y = a \cdot b \mod p\)
- 公式：\(a=\sum a_{i}\)，\(b=\sum b_{i}\)，\(a \cdot b=\left(a_{1}+a_{2}+a_{3}\right)\left(b_{1}+b_{2}+b_{3}\right)=\sum\limits_{i=1}^{3} \sum\limits_{j=1}^{3} a_{i} b_{j}\)
- 执行步骤：
- 本地计算项：利用复制秘密分享的特性，各参与方本地计算指定乘积和：
- \(P_1\)（持下标 \(2,3\)）：\(u_1 = a_2b_2 + a_2b_3 + a_3b_2\)
- \(P_2\)（持下标 \(1,3\)）：\(u_2 = a_3b_3 + a_1b_3 + a_3b_1\)
- \(P_3\)（持下标 \(1,2\)）：\(u_3 = a_1b_1 + a_1b_2 + a_2b_1\)
- 安全加法：调用安全加法协议，计算 \(y = u_1 + u_2 + u_3 \mod p\)
- 本地计算项：利用复制秘密分享的特性，各参与方本地计算指定乘积和：
隐私配对
- 场景：Alice (\(a\)) 和 Bob (\(b\)) 互选
- 输入：\(a, b \in \{0, 1\}\)（\(1 =\) 感兴趣，\(0 =\) 不感兴趣）
- 计算：\(y = a \cdot b\)
- \(y = 1 \implies\) 配对成功
- \(y = 0 \implies\) 至少一方不感兴趣（但不暴露是谁）
- 角色：引入服务器作为 \(P_3\) 协助计算（但不获取隐私）
4 恶意行为防范（Malicious Model）¶
- 输入替换（Input Substitution）
- 行为：参与方故意替换输入（如 Alice 始终输入 \(a=1\) 试探 Bob）
- 结论：无法通过协议防止，需通过博弈论或外部机制解决
- 违背协议（Protocol Deviation）
- 行为：协议执行中发送错误份额、计算错误结果（如安全加法中伪造份额）
- 解决方案：一致性检查（Consistency Check）
- 利用复制秘密分享的特性，每份数据由两人持有，\(P_2\) 和 \(P_3\) 可互相验证来自 \(P_1\) 的数据是否一致
- 加入一致性检查后成为恶意安全（Malicious Security） 模型
通用解决方案
- 通用性:
- \(\mathbb{Z}_p\) 上的加法 + 乘法 = 完备集
- 上一步的秘密份额可用于安全计算下一步
- 任何函数均可表示为加法和乘法电路，MPC 可安全计算任意函数
- 局限性：
- 安全乘法协议无法检测参与方违背协议的行为
- 上述协议仅考虑三个参与方的简单场景
- 假设无两个及以上参与方串通
- 假设参与方之间可安全通信
隐藏函数：是否可能让参与方在不知道函数 \(f\) 的情况下完成计算？（Universal Circuit / FHE）
可以，但代价通常更高。
常见思路包括：
- Universal Circuit（通用电路）：将函数 \(f\) 编码为电路描述，把“函数本身”当作输入之一，在固定通用电路上执行 MPC，从而尽量隐藏真实函数结构
- FHE（全同态加密）：可在密文上直接计算；若再结合函数加密、程序混淆或隐藏电路技术，可进一步实现函数隐私（Function Privacy）
这类问题通常称为 Private Function Evaluation, PFE，可行，但相比普通 MPC，通信和计算开销都会明显增加。
随机化函数：如何安全地计算概率函数（如共同抛硬币）？
核心方法是把“随机性”也当作协议中的受保护资源。
- 各方先联合生成随机数 \(r\)（如 commit-then-open 共同抛硬币，或分布式生成随机份额）
- 再把原来的随机函数写成确定性函数 \(y = f(x_1, \dots, x_n; r)\)
- 最后用普通 MPC 安全计算该确定性函数
关键要求是：随机数 \(r\) 需要对各方都不可预测、不可单方操纵、可验证一致；否则恶意参与方可能通过偏置随机性影响结果。
其他属性：除了隐私性和正确性，特定场景下还需要什么特性？（如公平性 Fairness, 可审计性 Auditability）
除了隐私性和正确性，实际系统中常见的额外目标还包括：
- 公平性（Fairness）：任何一方都不能只让自己先拿到输出而让别人拿不到
- 保证输出交付 / 鲁棒性（Guaranteed Output Delivery / Robustness）：即使部分参与方中途捣乱，诚实方仍能得到结果
- 可审计性 / 可验证性（Auditability / Verifiability）：事后可检查协议是否被正确执行
- 可追责性（Accountability / Identifiable Abort）：若协议中止，可识别是谁导致中止
- 输入独立性（Input Independence）：参与方不能先观察他人行为再自适应修改自己的输入
具体需要哪些属性，取决于应用场景：例如电子投票更强调公平性和可审计性，金融清算更强调鲁棒性和可追责性。