Chapter 3 一个安全多方计算协议的例子

1 协议概览与假设

• 本章目标：构建一个基于 Shamir 秘密分享 的通用 MPC 协议，在信息论意义下实现完美隐私性（Perfect Privacy）
• 核心思路：先把待计算函数表示为算术电路（Arithmetic Circuit），再对电路中的每条导线维护秘密份额

基本设定

• 参与方：\(n\) 个参与方 \(P_1, \dots, P_n\)
• 安全门限：\(t < n/2\)，即诚实方占多数
• 敌手模型：半诚实（Semi-honest）/ 被动安全（Passive Security）
  • 敌手会严格执行协议步骤
  • 但会记录执行过程中看到的所有信息，并试图据此推断其他人的隐私输入
• 通信假设：参与方之间存在点对点安全信道
• 计算域：协议在有限域 \(\mathbb{F}\) 上进行，通常要求 \(|\mathbb{F}| > n\)

为什么这里先研究半诚实模型？

半诚实模型是 MPC 的基础出发点。

• 它先回答：如果大家都按协议做，协议本身会不会泄露额外信息？
• 在此基础上，再通过一致性检查、MAC、零知识证明等机制，逐步增强到恶意安全（Malicious Security）

2 Shamir 秘密分享

2. 1 分享与重构

Shamir Secret Sharing

基于拉格朗日插值构造 \((t,n)\)-门限秘密分享。

• 分享（Share）：

  1. 在有限域 \(\mathbb{F}\) 中选取 \(n\) 个不同的非零点 \(\alpha_1,\dots,\alpha_n\)
  2. 对秘密 \(s \in \mathbb{F}\)，随机选取一个至多 \(t\) 次的多项式 \(f(x)\)，满足 \(f(0)=s\)
  3. 将份额 \(s_i=f(\alpha_i)\) 发送给参与方 \(P_i\)

• 重构（Reconstruct）：

  • 任意 \(t+1\) 个份额即可通过拉格朗日插值恢复多项式 \(f(x)\)，进而恢复秘密 \(s=f(0)\)
  • 若 \(S\) 是任意一个大小为 \(t+1\) 的参与方集合，则
  \[ s = f(0) = \sum_{i \in S} \lambda_i s_i \]

  其中 \(\lambda_i\) 为对应的拉格朗日系数

  

Shamir 分享的直观理解

• 秘密放在多项式的常数项 \(f(0)\) 中
• 随机性体现在其余系数中，因此同一个秘密可以对应很多不同的随机多项式
• 少于或等于 \(t\) 个份额时，攻击者看到的只是若干点，仍有无数个候选多项式与之兼容，因此得不到秘密

2. 2 线性同态性质

• 定义记号 \([a;f]_t\) 表示由 \(t\) 次多项式 \(f\) 生成的秘密 \(a\) 的份额向量：

\[ [a;f]_t = (f(\alpha_1), \dots, f(\alpha_n)) \]

引理：同态计算

对任意标量 \(c \in \mathbb{F}\)，有：

1. 加法：\([a;f]_t + [b;g]_t = [a+b;f+g]_t\)
2. 标量乘法：\(c \cdot [a;f]_t = [c \cdot a;c \cdot f]_t\)
3. 乘法（升维）：\([a;f]_t \ast [b;g]_t = [a \cdot b;f \cdot g]_{2t}\)

关键困难

直接把两个份额逐点相乘后，得到的是一个次数至多为 \(2t\) 的多项式上的点。

• 虽然其常数项确实是 \(ab\)
• 但它已经不再是 \(t\)-门限分享
• 因此无法直接作为后续门电路的输入，必须做降阶（Degree Reduction）

3 半诚实安全多方计算协议

3. 1 算术电路视角

• 将目标函数表示为由加法门和乘法门组成的算术电路
• 每条导线上的值都不直接公开，而是始终以 Shamir 份额的形式保存

协议三阶段

1. 输入分享（Input Sharing）：每个参与方 \(P_i\) 将其输入 \(x_i\) 生成份额 \([x_i]_t\) 并分发给其他参与方

2. 电路计算（Circuit Evaluation）：按电路的拓扑顺序逐门计算

   • 加法门 \((x+y)\)：各方本地把对应份额相加
   • 常数乘法门 \((c \cdot x)\)：各方本地把份额乘以常数 \(c\)
   • 乘法门 \((x \cdot y)\)：需要额外交互完成降阶

3. 输出重构（Output Reconstruction）：

   • 对于输出导线 \(y\)，各方把自己的份额发送给指定接收方
   • 接收方通过插值恢复最终输出

3. 2 核心难点：乘法门

• 目标：给定 \([a;f_a]_t\) 和 \([b;f_b]_t\)，计算一个新的 \(t\)-门限份额 \([a \cdot b]_t\)

乘法门协议

1. 本地乘法

   • 每个参与方 \(P_i\) 本地计算 \(v_i = f_a(\alpha_i) \cdot f_b(\alpha_i)\)
   • 这些值正好是多项式 \(h(x)=f_a(x)f_b(x)\) 在点 \(\alpha_i\) 上的取值
   • 有 \(h(0)=ab\)，但 \(\deg(h) \le 2t\)（阶数过高）

2. 重分享（Resharing / Degree Reduction）

   • 每个参与方 \(P_i\) 将自己的 \(v_i\) 再次作为秘密做一次 Shamir 分享
   • 得到新的 \(t\)-门限份额 \([v_i;g_i]_t\)

3. 线性重组

   • 由于 \(h(x)\) 的次数至多为 \(2t\)，存在公开的重组向量 \(r=(r_1,\dots,r_n)\)，使得 \(h(0)=\sum\limits_{i=1}^{n} r_i h(\alpha_i)\)
   • 各方据此本地计算 \([ab]_t = \sum\limits_{i=1}^{n} r_i \cdot [v_i;g_i]_t\)
   • 因为右边是若干个次数至多为 \(t\) 的份额的线性组合，所以结果重新回到了次数至多为 \(t\)

乘法门为什么可行？

乘法门的关键不是“直接恢复 \(ab\)”，而是：

• 先利用逐点乘法得到关于 \(ab\) 的一个高阶分享
• 再通过重分享 + 线性重组把它压回 \(t\) 次
• 这样既保留了正确结果，又维持了后续继续计算所需的隐私门限

4 安全性分析与计算示例

4. 1 正确性（Correctness）

• 加法门和常数乘法门的正确性，直接来自 Shamir 分享的线性同态性质
• 惩罚协议利用 \(h(0)=\sum\limits_{i=1}^{n} r_i h(\alpha_i)=ab\) 确保了结果是 \(ab\)，且最终多项式阶数为 \(t\)

4.2 完美隐私性（Perfect Privacy）

证明思路：基于模拟（Simulation）

构造模拟器 \(\mathcal{S}\)，仅利用被攻陷方的输入输出以及协议公开信息，生成一个与真实执行不可区分且事实上同分布的视图。

被攻陷方从诚实方接收的信息主要有两类：

1. 输入分享阶段和乘法重分享阶段收到的份额
   • 即来自某些随机多项式的点值，例如 \([x_i;f_{x_i}]_t\) 或 \([h(\alpha_i);f_i]_t\) 中属于自己的那部分
2. 输出重构阶段收到的输出份额
   • 对于属于被攻陷方的输出 \(y\)，它会收到 \([y;f_y]_t\) 的全部份额以恢复结果

为什么这两类信息都不泄露额外隐私？

• 第一类信息：
  • 对攻击者来说，它至多掌握 \(t\) 个点
  • 而一个次数至多为 \(t\) 的随机多项式，在给定秘密之前，其这 \(t\) 个点的分布就是均匀随机
  • 因此这些份额本身不携带超出协议允许范围的隐私信息
• 第二类信息：
  • 这些份额本就是为了恢复输出而发送的
  • 给定输出值 \(y\) 以及被攻陷方自身已知的信息，这部分数据可以被它自己推导或与某个合法执行保持一致

模拟器如何工作？

• 对第一类信息，模拟器直接采样均匀随机值来模拟诚实方发送的份额
• 对第二类信息，模拟器根据输出值 \(y\) 和被攻陷方已知信息，构造一组与真实执行一致的输出份额
• 因此，敌手在真实世界看到的视图，可以完全由模拟器在“只知道合法输入输出”的情况下生成

4. 3 计算示例：加法

设 \(t=1,\ n=3\)，计算 \(c=a+b\)，假设敌手控制 \(P_1\)：

Case 1: \(a=4,\ b=4\)

变量	真实值	\(P_1\)	\(P_2\)	\(P_3\)
\(a\)	4	5	6	7
\(b\)	4	6	8	10
\(c\)	8	11	14	17

一组可能的分享多项式为：

\[ a(x)=4+x,\quad b(x)=4+2x,\quad c(x)=8+3x \]

此时 \(P_1\) 看到的局部视图是 \((5,6,11)\)

模拟一致性：相同视图也可能对应别的输入

如果真实输入改成

\[ a=3,\quad b=5 \]

仍可构造出让 \(P_1\) 看到相同份额的分享：

\[ a'(x)=3+2x,\quad b'(x)=5+x \]

因而：

• \(a'(1)=5\)
• \(b'(1)=6\)
• \(a'+b'=8+3x\)，所以输出份额仍与原情况兼容

这说明：仅从 \(P_1\) 看到的份额，无法区分 \(4+4\) 和 \(3+5\)

Case 2: \(a=3,\ b=5\)

变量	真实值	\(P_1\)	\(P_2\)	\(P_3\)
\(a\)	3	5	7	9
\(b\)	5	6	7	8
\(c\)	8	11	14	17

可以看到，两种情况下 \(P_1\) 的可见信息完全一致，因此满足隐私性直觉。

4. 4 计算示例：乘法

设 \(t=1,\ n=3\)，计算 \(d=ab\)，假设敌手控制 \(P_1\)

取评估点 \(\alpha_1=1,\alpha_2=2,\alpha_3=3\) 时，对任意二次多项式 \(h(x)\) 都有

\[ h(0)=3h(1)-3h(2)+h(3) \]

因而这里的重组向量可以取为

\[ r=(3,-3,1) \]

Case 1: \(a=2,\ b=4\)

变量	值	\(P_1\)	\(P_2\)	\(P_3\)
\(a\)	2	3	4	5
\(b\)	4	3	2	1
\(d=ab\)	8	9	8	5
\(d_1\)	9	7	5	3
\(d_2\)	8	8	8	8
\(d_3\)	5	6	7	8
\(c=3d_1-3d_2+d_3\)	8	3	-2	-7

一种理解方式是：\(a(x)=2+x\)，\(b(x)=4-x\)，相乘得到

\[ h(x)=a(x)b(x)=8+2x-x^2 \]

因而 \(h(1)=9,\ h(2)=8,\ h(3)=5\)，再把这三个值分别重分享，并按 \(3d_1-3d_2+d_3\) 做线性重组，就得到新的 \(1\) 次分享 \(c\)

Case 2: \(a=1,\ b=8\)

变量	值	\(P_1\)	\(P_2\)	\(P_3\)
\(a\)	1	3	5	7
\(b\)	8	3	-2	-7
\(d=ab\)	8	9	-10	-49
\(d_1\)	9	7	5	3
\(d_2\)	-10	8	26	44
\(d_3\)	-49	6	61	116
\(c=3d_1-3d_2+d_3\)	8	3	-2	-7

尽管两组真实输入不同，但 \(P_1\) 在两种情况下看到的关键局部信息仍可保持一致，这再次说明：单个被攻陷方看到的局部执行记录，并不足以唯一反推出其他参与方的真实输入。

乘法例子的核心启示

• 乘法门虽然需要额外交互，但协议输出的仍然是低阶秘密分享
• 只要被攻陷方数量不超过 \(t\)，其可见视图始终可以由多个不同的真实输入解释
• 因而协议在半诚实模型下保持完美隐私

1. 为什么必须要求 \(t < n/2\)？

这是因为乘法会把多项式次数从 \(t\) 提升到 \(2t\)。

• 若要从所有参与方手中的点值中唯一恢复一个次数至多为 \(2t\) 的多项式，至少需要

\[ n \ge 2t+1 \]

• 这等价于

\[ t < \frac{n}{2} \]

• 若 \(2t \ge n\)，则乘法后得到的高阶多项式无法由现有点唯一确定，线性重组和降阶都会失去基础
• 从直观上说，这也是诚实多数条件在 BGW 类协议中的来源

2. 本协议能直接迁移到环 \(\mathbb{Z}_{2^k}\) 上吗？

通常不能直接照搬。

原因在于：

• 本协议的核心工具是 Shamir 秘密分享
• Shamir 的重构依赖拉格朗日插值
• 拉格朗日插值需要对分母求逆，而在环 \(\mathbb{Z}_{2^k}\) 中，非零元素不一定都有逆元

因此：

• 在有限域上，这套方案工作良好
• 在一般环上，需要改用专门面向环的秘密分享与 MPC 技术，而不能直接原样套用本章协议