第一章 问题背景与核心挑战
1.1 什么是秘密加法
在安全多方计算（MPC）中，两个参与方（Alice 和 Bob）各自持有一个二进制数的秘密份额，想要计算两个数的和，但不能泄露任何一个操作数的明文。这里的"秘密份额"指的是布尔秘密共享：一个比特 x 被拆成两个份额 x₁ 和 x₂，满足 x = x₁ ⊕ x₂，其中 ⊕ 是异或运算。Alice 持有 x₁，Bob 持有 x₂，任何一方单独看自己的份额都是一个均匀随机的比特，无法推断出 x 的真实值。
二进制加法的核心困难在于进位：第 i 位的进位依赖于第 i-1 位的进位，形成了链式依赖。如果朴素地逐位串行计算，n 位的加法需要 O(n) 轮通信，这在 MPC 中是不可接受的。本文将详细介绍如何用前缀运算将其压缩到 O(log n) 轮。
1.2 布尔秘密共享中的线性与非线性
在布尔秘密共享中，XOR（异或）是线性运算，完全免费，不需要任何通信。AND（与）是非线性运算，每次计算都需要消耗一个 Beaver 三元组和一轮通信。这是理解整个协议的基础。
XOR 为什么是免费的： 假设 x = x₁ ⊕ x₂，y = y₁ ⊕ y₂。要计算 z = x ⊕ y 的份额，只需每方本地异或自己的两个份额：Alice 计算 z₁ = x₁ ⊕ y₁，Bob 计算 z₂ = x₂ ⊕ y₂。验证：z₁ ⊕ z₂ = (x₁ ⊕ y₁) ⊕ (x₂ ⊕ y₂) = (x₁ ⊕ x₂) ⊕ (y₁ ⊕ y₂) = x ⊕ y。异或的结合律和交换律使得份额可以各自独立操作，结果自动正确。
AND 为什么不免费： 展开 (x₁ ⊕ x₂) ∧ (y₁ ⊕ y₂) = (x₁∧y₁) ⊕ (x₁∧y₂) ⊕ (x₂∧y₁) ⊕ (x₂∧y₂)。其中 x₁∧y₁ Alice 可以本地计算，x₂∧y₂ Bob 可以本地计算，但 x₁∧y₂ 和 x₂∧y₁ 是"交叉项"，双方各持一个因子，必须通过通信才能计算。这就是 Beaver 三元组和 OT 发挥作用的地方。
第二章 Beaver 三元组与秘密 AND 门
2.1 Beaver 三元组的定义
Beaver 三元组是一组预处理的随机值 (u, v, w)，满足 w = u AND v。这组值与实际计算的输入完全无关，是提前随机生成的。它被秘密共享给两方：Alice 持有 (u₁, v₁, w₁)，Bob 持有 (u₂, v₂, w₂)，满足 u₁ ⊕ u₂ = u，v₁ ⊕ v₂ = v，w₁ ⊕ w₂ = w。
2.2 用 Beaver 三元组计算秘密 AND
假设 Alice 和 Bob 要计算 [x] AND [y] 的秘密份额。协议如下：
第一步：计算并公开遮罩差值。 每方本地计算 d 的份额 d_i = x_i ⊕ u_i，以及 e 的份额 e_i = y_i ⊕ v_i。然后双方互相发送各自的 d 和 e 份额，重构出明文的 d = x ⊕ u 和 e = y ⊕ v。这里 d 和 e 是安全的，因为 u 和 v 是完全随机的，起到了一次性密码本的作用，d 和 e 不泄露 x 和 y 的任何信息。
第二步：本地计算最终份额。 利用代数恒等式 x ∧ y = (d ⊕ u) ∧ (e ⊕ v) = (d∧e) ⊕ (d∧v) ⊕ (u∧e) ⊕ (u∧v)，其中 d∧e 是公知常数，u∧v = w 已知。所以：
Alice 计算：z₁ = (d AND e) ⊕ (d AND v₁) ⊕ (u₁ AND e) ⊕ w₁
Bob 计算：z₂ = (d AND v₂) ⊕ (u₂ AND e) ⊕ w₂
注意：d∧e 这个常数项只由 Alice 一方加入，否则会被 XOR 抵消。
验证：z₁ ⊕ z₂ = (d∧e) ⊕ (d∧v) ⊕ (u∧e) ⊕ w = x ∧ y。整个过程只需要一轮通信（双方各发送 2 bit）加一个 Beaver 三元组。
2.3 具体数字示例
以 x = 1, y = 1（所以 x AND y = 1）为例。假设秘密共享为：Alice 持有 x₁=1, y₁=0，Bob 持有 x₂=0, y₂=1。预处理三元组 (u=1, v=0, w=0)，Alice 持有 (u₁=0, v₁=1, w₁=1)，Bob 持有 (u₂=1, v₂=1, w₂=1)。
Alice: d₁ = x₁⊕u₁ = 1⊕0 = 1, e₁ = y₁⊕v₁ = 0⊕1 = 1
Bob: d₂ = x₂⊕u₂ = 0⊕1 = 1, e₂ = y₂⊕v₂ = 1⊕1 = 0
公开: d = d₁⊕d₂ = 1⊕1 = 0, e = e₁⊕e₂ = 1⊕0 = 1
Alice: z₁ = (0∧1) ⊕ (0∧1) ⊕ (0∧1) ⊕ 1 = 0⊕0⊕0⊕1 = 1
Bob: z₂ = (0∧1) ⊕ (1∧1) ⊕ 1 = 0⊕1⊕1 = 0
验证: z₁ ⊕ z₂ = 1 ⊕ 0 = 1 = x AND y ✓
第三章 用不经意传输（OT）生成 Beaver 三元组
3.1 问题：没有可信第三方怎么办
前一章假设三元组已经存在，但实际中没有可信第三方来生成它。两方需要自己"凭空"生成。关键工具是 1-out-of-2 不经意传输（OT）。
3.2 不经意传输的定义
1-out-of-2 OT 涉及两个角色：发送者准备两条消息 m₀ 和 m₁，接收者有一个选择位 c ∈ {0, 1}。执行后，接收者只能看到 m_c（根据 c 选中的那条消息），看不到另一条 m_{1-c}；发送者不知道接收者选了哪条。可以想象成一个双门保险箱：发送者往两个抽屉各放一个信封，接收者用钥匙只能打开一个抽屉，发送者不知道他开了哪个。OT 的具体实现可以用 RSA、椭圆曲线等公钥密码学构建，这里我们把它当作黑盒使用。
3.3 AND 的本质是"二选一"
理解 OT 如何计算 AND 的关键直觉是：u₁ AND v₂ 的结果只取决于 v₂。当 v₂=0 时，不管 u₁ 是什么，结果都是 0；当 v₂=1 时，结果就是 u₁ 本身。AND 天然就是一个"二选一"的结构，而 OT 恰好就是"安全二选一"的密码学工具，两者完美对应。
3.4 展开 w 的交叉乘积
两方各自随机选取 u 和 v 的份额后，需要协作算出 w = u AND v 的份额：
w = (u₁⊕u₂) AND (v₁⊕v₂)
= (u₁∧v₁) ⊕ (u₁∧v₂) ⊕ (u₂∧v₁) ⊕ (u₂∧v₂)
───── ───── ───── ─────
Alice 交叉项 交叉项 Bob
本地算 本地算
u₁∧v₁ Alice 自己能算，u₂∧v₂ Bob 自己能算。难点在两个交叉项：u₁∧v₂（Alice 有 u₁，Bob 有 v₂）和 u₂∧v₁（Bob 有 u₂，Alice 有 v₁）。双方各持有一个因子，谁也不能把自己的发给对方。
3.5 用 OT 计算交叉项 u₁ ∧ v₂ 的份额
Alice 有 u₁，Bob 有 v₂。协议如下：
- Alice 随机选取一个完全独立的随机比特 r。这个 r 和 u₁ 没有任何关系，纯粹是抛硬币得到的。r 将成为 Alice 的输出份额。
- Alice 根据自己的 u₁ 准备两条消息：m₀ = r（如果 v₂=0，乘积=0，Bob 应得到 r，使得 r⊕r=0），m₁ = r ⊕ u₁（如果 v₂=1，乘积=u₁，Bob 应得到 r⊕u₁，使得 r⊕(r⊕u₁)=u₁）。
- Bob 用 v₂ 作为选择位执行 OT，拿到 t = m_{v₂}。他看不到另一条消息，Alice 不知道他选了哪条。
- 结果：Alice 的份额 = r，Bob 的份额 = t。两者 XOR 起来恰好等于 u₁ AND v₂。
正确性验证：
情况1: v₂ = 0
Bob 拿到 t = m₀ = r
Alice份额 ⊕ Bob份额 = r ⊕ r = 0 = u₁ AND 0 ✓
情况2: v₂ = 1
Bob 拿到 t = m₁ = r ⊕ u₁
Alice份额 ⊕ Bob份额 = r ⊕ (r ⊕ u₁) = u₁ = u₁ AND 1 ✓
为什么 r 必须是独立随机的： r 扮演了一次性密码本的角色。如果 r 与 u₁ 有任何关联（比如 r = u₁，或 r 总是 0），Bob 看到 m_{v₂} 后可能能推算出 u₁。举例：若 r 总是 0，则 m₁ = u₁，当 v₂=1 时 Bob 直接看到 u₁ 明文。而当 r 是真正随机的，不管 u₁ 是 0 还是 1，m₀ 和 m₁ 各自看起来都是均匀随机的比特，Bob 无法区分。
3.6 用 OT 计算另一个交叉项 u₂ ∧ v₁
方法完全对称，只是角色互换：Bob 当 OT 发送者（他有 u₂），随机选 s，准备 m₀ = s、m₁ = s ⊕ u₂；Alice 当接收者（她有 v₁），用 v₁ 作为选择位。Alice 得到 t’ = m_{v₁}，份额分配为 Alice 持有 β₁ = t’，Bob 持有 β₂ = s。
3.7 组装最终的 w 份额
四项都有了份额，各方本地 XOR 组装：
Alice: w₁ = (u₁ ∧ v₁) ⊕ α₁ ⊕ β₁
Bob: w₂ = α₂ ⊕ β₂ ⊕ (u₂ ∧ v₂)
验证: w₁ ⊕ w₂
= (u₁∧v₁) ⊕ (α₁⊕α₂) ⊕ (β₁⊕β₂) ⊕ (u₂∧v₂)
= (u₁∧v₁) ⊕ (u₁∧v₂) ⊕ (u₂∧v₁) ⊕ (u₂∧v₂)
= (u₁⊕u₂) ∧ (v₁⊕v₂) = u ∧ v = w ✓
每个 Beaver 三元组的生成需要 2 次 OT。工程上可用 OT Extension 技术，只需约 128 次基础公钥 OT，即可用纯对称加密扩展出百万级的廉价 OT。
3.8 具体数字完整示例
假设 Alice 有 u₁=1, v₁=1，Bob 有 u₂=0, v₂=0。真实值 u=1, v=1, w=1∧1=1。
═══ 本地项 ═══
Alice 本地: u₁∧v₁ = 1∧1 = 1
Bob 本地: u₂∧v₂ = 0∧0 = 0
═══ OT 交叉项 u₁∧v₂ ═══
Alice 选 r=1, 准备 m₀=1, m₁=1⊕1=0
Bob 用 v₂=0 选择 → 拿到 t=m₀=1
份额: α₁=1, α₂=1, 验证 1⊕1=0=u₁∧v₂ ✓
═══ OT 交叉项 u₂∧v₁ ═══
Bob 选 s=0, 准备 m₀=0, m₁=0⊕0=0
Alice 用 v₁=1 选择 → 拿到 t'=m₁=0
份额: β₁=0, β₂=0, 验证 0⊕0=0=u₂∧v₁ ✓
═══ 组装 w 的份额 ═══
Alice: w₁ = 1 ⊕ 1 ⊕ 0 = 0
Bob: w₂ = 1 ⊕ 0 ⊕ 0 = 1
验证: w₁ ⊕ w₂ = 0 ⊕ 1 = 1 = u ∧ v ✓
最终各方持有的完整 Beaver 三元组份额：Alice (u₁=1, v₁=1, w₁=0)，Bob (u₂=0, v₂=0, w₂=1)。没有可信第三方参与，完全由两方自行生成。
第四章 生成位与传播位：用 g 和 p 表示进位
4.1 单比特全加器的进位公式
对于第 i 位，两个加数的该位为 a_i 和 b_i，低位传来的进位为 c_i。进位输出为：
c_{i+1} = (a_i AND b_i) OR (c_i AND (a_i XOR b_i))
定义：
- g_i = a_i AND b_i（生成位）： 两个比特都是 1 时，该位必定产生进位，不管低位传来什么。
- p_i = a_i XOR b_i（传播位）： 两个比特恰好一个是 1 时，该位会把低位的进位原样传播上去。
- 当 a_i = b_i = 0 时，g=0 且 p=0，该位既不产生进位，也会"吞掉"低位传来的进位。
代入得到简洁的递推式：c_{i+1} = g_i OR (p_i AND c_i)。
在 MPC 中，g_i 的计算需要一次秘密乘法（AND，消耗一个 Beaver 三元组），p_i 的计算是纯本地 XOR（免费）。所有位可以并行，只需 1 轮通信。
4.2 递推展开：进位的完整表达式
从 c₀ = 0 开始逐层展开：
c₁ = g₀
c₂ = g₁ OR (p₁ ∧ g₀)
c₃ = g₂ OR (p₂ ∧ g₁) OR (p₂ ∧ p₁ ∧ g₀)
c₄ = g₃ OR (p₃ ∧ g₂) OR (p₃ ∧ p₂ ∧ g₁) OR (p₃ ∧ p₂ ∧ p₁ ∧ g₀)
一般公式：c_{i+1} 是多个 OR 项的叠加，每一项代表一条"接力路径"——进位在第 k 位由 g_k 诞生，然后经过 p_{k+1}, p_{k+2}, …, p_i 连续传播到顶部。所有路径里只要任意一条通了，进位就存在。
每一项的含义：
第 k 项 = p_i · p_{i-1} · ... · p_{k+1} · g_k
读法: "进位在第 k 位诞生，然后连续穿过第 k+1, k+2, ..., i 位，
最终从第 i 位顶部出去"
想象一个接力赛：
g_k 是起跑者（进位在这里产生）
p_{k+1}, p_{k+2}, ..., p_i 是接力队员（每人传一棒）
所有接力队员都得在场（AND），进位才能到达终点
4.3 g 和 p 的互斥性：OR 退化为 XOR
一个关键的代数性质：对任意一位，g_i = 1 和 p_i = 1 不可能同时成立。因为 g_i = 1 意味着 a_i = b_i = 1，而此时 p_i = a_i XOR b_i = 1 XOR 1 = 0。直觉上，一位要么自己生成进位，要么传播别人的进位，不可能同时做两件事。
这个互斥性传递到区间：如果 G_{i:j} = 1，意味着区间内某位 g_k = 1，那该位 p_k = 0，P_{i:j} 的连乘中就有了一个 0 因子，整段 P 必然为 0。任何区间的 G 和 P 都不可能同时为 1。
这意味着合并公式中的 OR 是免费的！ 合并公式 G_合并 = G_高 OR (P_高 AND G_低) 中，如果 G_高 = 1，则 P_高 = 0，另一项必为 0；反过来也一样。两个操作数互斥，a AND b 恒等于 0，所以 a OR b = a XOR b XOR 0 = a XOR b，退化为纯 XOR，完全免费。每次合并只需要 2 次 AND（而不是 3 次），节省了 1/3 的三元组消耗。
第五章 前缀运算：从 O(n) 到 O(log n)
5.1 区间的含义
一个区间 [j, i] 的 (G, P) 回答两个问题：G_{i:j} 表示"假设从位 j 的入口进来的进位是 0，那么从位 i 的出口出去的进位是多少？“P_{i:j} 表示"如果从位 j 的入口进来了一个进位 1，它能否一路穿过所有位直到从位 i 出去？”
单独一位的 (g_i, p_i) 就是最小的区间 [i, i]。目标是算出从位 0 到位 i 的完整区间 (G_{i:0}, P_{i:0})，此时 G_{i:0} 就直接等于进位 c_{i+1}（因为初始进位 c₀=0）。
5.2 合并运算符 ◇
定义组合运算符 ◇，将相邻区间拼成更长的区间：
(G_高, P_高) ◇ (G_低, P_低) = (G_高 XOR (P_高 AND G_低), P_高 AND P_低)
其中 G_合并 = G_高 XOR (P_高 AND G_低) 表示"要么高段自己生成了进位，要么低段生成的进位被高段传播上来"；P_合并 = P_高 AND P_低 表示"外部进位要穿过整段，必须低段和高段都能传播"。注意这里的 OR 已经用 XOR 替代（因为互斥性）。
这个运算符满足结合律，意味着可以任意分组并行计算，这直接导出了前缀树结构。每次合并需要 2 次 AND（秘密乘法），同层的多个合并可以并行执行，只需 1 轮通信。
5.3 前缀树的具体过程（4 位示例）
以 A=1011 + B=0111 为例（答案 18 = 10010）。
初始化： 各位并行计算 g 和 p（1 轮通信）：
位0: a=1, b=1 → g₀=1, p₀=0 (生成，不传播)
位1: a=1, b=1 → g₁=1, p₁=0 (生成，不传播)
位2: a=0, b=1 → g₂=0, p₂=1 (不生成，传播)
位3: a=1, b=0 → g₃=0, p₃=1 (不生成，传播)
第 1 层（跨度 1，1 轮通信）： 相邻两位合并，两个合并并行执行。
[1:0] = (g₁,p₁) ◇ (g₀,p₀) = (1 XOR (0∧1), 0∧0) = (1, 0)
→ 位0和位1合起来自己会产生进位
[3:2] = (g₃,p₃) ◇ (g₂,p₂) = (0 XOR (1∧0), 1∧1) = (0, 1)
→ 位2和位3合起来不产生进位，但能传播
第 2 层（跨度 2，1 轮通信）： 把第 1 层结果再合并。
[3:0] = (G_{3:2},P_{3:2}) ◇ (G_{1:0},P_{1:0}) = (0,1) ◇ (1,0)
= (0 XOR (1∧1), 1∧0) = (1, 0)
→ 位1:0 产生的进位被位3:2 传播上来，整段产生进位
5.4 提取最终进位和求和
c₁ = G_{0:0} = g₀ = 1，c₂ = G_{1:0} = 1，c₃ = G_{2:0} = 1，c₄ = G_{3:0} = 1。然后每位的和为 s_i = p_i XOR c_i（纯本地 XOR，0 通信）：
s₀ = p₀ ⊕ c₀ = 0 ⊕ 0 = 0
s₁ = p₁ ⊕ c₁ = 0 ⊕ 1 = 1
s₂ = p₂ ⊕ c₂ = 1 ⊕ 1 = 0
s₃ = p₃ ⊕ c₃ = 1 ⊕ 1 = 0
溢出进位 c₄ = 1
结果: 10010 = 18 = 11 + 7 ✓
5.5 通信复杂度汇总
| 步骤 | 操作 | 通信轮数 |
|---|---|---|
| 计算 g, p | n 次并行 AND + n 次本地 XOR | 1 轮 |
| 前缀树合并 | 每层若干并行 AND | O(log n) 轮 |
| 提取进位 | 本地读取 | 0 轮 |
| 计算求和 | 本地 XOR | 0 轮 |
| 总计 | O(log n) 轮 |
第六章 安全性分析：没有任何进位被揭露
6.1 全程份额追踪
整个计算过程中，所有中间比特均以秘密份额的形式存在。初始的 a, b 是份额，算出的 g, p 是份额，前缀树每一层合并出的 G, P 是份额，最终的进位 c 和求和 s 还是份额。没有任何一步需要"先恢复明文再继续算"。
6.2 唯一公开的信息：Beaver AND 中的 (d, e)
每次 Beaver AND 会公开一对 (d, e)，其中 d = x ⊕ u，e = y ⊕ v。由于 u 和 v 是完全随机且只使用一次的三元组分量，d 和 e 的分布与真实输入完全无关——这就是一次性密码本的安全性，是信息论级别的，不依赖任何计算复杂度假设。
以 4 位加法为例，全程公开的信息为：初始 g, p 计算公开 4×2 = 8 个 (d,e)，第 1 层合并公开 4×2 = 8 个 (d,e)，第 2 层合并公开 2×2 = 4 个 (d,e)，共 20 个公开比特。这 20 个比特全部等于"真实数据 ⊕ 独立随机三元组"，等于 20 个独立均匀随机比特，零信息。
6.3 安全性结论
Alice 在整个过程中看到的全部信息包括：自己的输入份额、自己的三元组份额、公开的 (d,e) 值、自己计算的中间份额。这些信息的联合分布与 Bob 的真实输入完全无关。换句话说：无论 Bob 的输入是什么，Alice 看到的分布完全相同。进位 c₁ 到 c₄ 没有被任何一方揭露过，最终的和 s 也是直到主动"打开"时才揭露。
总结：完整的技术链路
本文介绍的整个技术链路可以用一句话串起来：
- 布尔秘密共享中，XOR 是免费的线性运算，AND 是需要通信的非线性运算。
- 每次秘密 AND 消耗一个 Beaver 三元组，一轮通信：公开被随机遮罩的 (d, e)，然后本地组装结果份额。
- Beaver 三元组由两方用 OT 自行生成：将 AND 的交叉项分解为"二选一"问题，用独立随机 r 遮罩后通过 OT 安全执行。
- 二进制加法的进位被拆解为生成位 g 和传播位 p，它们的互斥性让合并中的 OR 退化为免费的 XOR。
- 前缀树利用合并运算符的结合律，把链式依赖的进位计算重组为树状并行结构，从 O(n) 轮压缩到 O(log n) 轮。
- 全程所有中间值均以秘密份额形式存在，唯一公开的 (d, e) 被一次性密码本完美隐藏，达到信息论级别的安全性。
从底层的 OT 原语，到 Beaver 三元组，到秘密 AND 门，到 g/p 的计算，到前缀树的并行合并，每一层都建立在上一层之上，最终实现了在不泄露任何一个比特明文的前提下，在 O(log n) 轮通信内完成二进制加法的全部进位计算。