Chapter 8 基于混淆电路的协议

1 姚氏混淆电路（Yao's Garbled Circuits）

1. 1 协议流程

小输入域函数的查表直觉

若 \(F(x,y)=x+y\)，其中 \(x\in\{1,2\}\)、\(y\in\{0,1,2\}\)，则可以先列出所有 \((x,y,F(x,y))\)。

• 生成方为 \(X,Y\) 中每个可能取值分别生成随机密钥
• 用对应输入密钥加密表项 \(F(x,y)\)
• 随机打乱整张加密表
• 计算方拿到自己真实输入对应的密钥后，只能打开对应表项

当输入域变大时，完整查找表指数级膨胀，因此 Yao GC 改为把 \(F\) 写成布尔电路，并逐个门混淆。

考虑一个与门 \(z=x\land y\)，为输入导线 \(x,y\) 分别准备 \(k_X^0, k_X^1\) 和 \(k_Y^0, k_Y^1\) 两把密钥。

加密后的门表

发送方构造四个密文：

\[ \begin{aligned} &Enc_{k_X^0}(Enc_{k_Y^0}(0))\\ &Enc_{k_X^0}(Enc_{k_Y^1}(0))\\ &Enc_{k_X^1}(Enc_{k_Y^0}(0))\\ &Enc_{k_X^1}(Enc_{k_Y^1}(1)) \end{aligned} \]

再把四行随机打乱后发送给计算方。

姚氏混淆电路协议

• 对 \(C\) 中每条线路，随机选取两个线路标签 \(W_0, W_1\)，分别对应 \(0, 1\) 值

• 用线路标签替换真值表中的 \(0, 1\) 值

• 用输入标签加密输出标签

• 随机打乱真值表的各行

每个加密真值表被称为混淆表，所有的混淆表的组合即为布尔电路 \(C\) 对应的混淆电路。

1. 2 混淆方案的抽象定义（L4 补充）

Garbled Scheme: \((Gb,En,Ev,De)\)

• \(Gb(1^\kappa,f)\)：输入函数 \(f\)，输出混淆电路 \(F\)、编码信息 \(e\)、解码信息 \(d\)
• \(En(e,x)\)：把明文输入 \(x\) 编码成输入导线标签 \(X\)
• \(Ev(F,X)\)：在混淆电路上求值得到输出标签 \(Y\)
• \(De(d,Y)\)：用解码信息把输出标签解码成 \(y=f(x)\) 或 \(\bot\)

三类安全性质

• 可模拟隐私性（Simulatable Privacy）：存在模拟器 \(S(f,y)\)，只给定函数和输出，也能生成与真实 \((F,X,d)\) 不可区分的对象
• 可模拟不经意性（Simulatable Obliviousness）：存在模拟器 \(S(f)\)，不需要知道 \(x\) 或 \(y\)，也能模拟混淆电路与输入标签
• 真实性（Authenticity）：给定 \(F\) 和合法输入标签 \(X\)，敌手难以伪造一个不同于真实求值结果、但仍可被 \(De\) 接受的输出标签

模拟隐私的经典门级直觉

对一个 XOR 门 \(c=a\oplus b\)，若模拟器只知道输出位 \(y=1\) 而不知道输入 \((a,b)\)，它可为所有四行都加密同一个输出标签 \(C^1\)。只要底层加密 / PRP 让门表看起来伪随机，真实门表与“恒输出活跃标签”的门表在混合论证下不可区分。

2 混淆电路正确性所需的加密性质

2. 1 可验证 / 不可知密文空间

计算方用错密钥去解密别的行时，希望不会泄露明文，且能够高效识别这是错的。

• 不可知密文空间（Elusive Range）：攻击者难以伪造一个看起来像合法密文空间里的密文
• 可验证密文空间（Efficiently Verifiable Range）：给定密钥 \(k\) 和密文 \(c\)，能高效检查 \(c\) 是否属于 \(Range_n(k)\)

形式化定义

若加密算法的密文空间记为 \(Range_n(k)\)，则常见形式化要求是：

• 不可知密文空间：对任意 PPT 算法 \(\mathcal{A}\)、任意多项式 \(p(\cdot)\)，当安全参数足够大时，

\[ \Pr[k\leftarrow Gen(1^n),\ c\leftarrow\mathcal{A}(1^n): c \in Range_n(k)] < \frac{1}{p(n)} \]

即攻击者很难伪造像是合法密文的字符串

• 可验证密文空间：存在 PPT 算法 \(M\)，满足

\[ M(1^n,k,c)=1 \iff c\in Range_n(k) \]

即接收方能高效判断某次解密结果是否合法

2. 2 双重加密安全

因为门表里的每一行通常是“双层加密”，所以除了 IND-CPA 外，还需要保证用一层错误密钥解另一层时不会泄露明文差异。

选择明文攻击下的双重加密安全（Secure under Chosen Double Encryption）

如果对任意概率多项式时间的敌手 \(\mathcal{A}\)，都存在一个可忽略函数 \(\text{negl}\)，使得

\[ \Pr\left[\text{Game}_{\mathcal{A}}^{\text{double}}(n) = 1\right] \le \frac{1}{2} + \text{negl}(n) \]

那么，我们说对称加密方案 \((\text{Gen}, \text{Enc}, \text{Dec})\) 在选择明文攻击下具有双重加密安全。

选择明文攻击下的不可区分性（IND-CPA Secure）

如果对任意概率多项式时间的敌手 \(\mathcal{A}\)，都存在一个可忽略函数 \(\text{negl}\)，使得

\[ \Pr\left[\text{Game}_{\mathcal{A}}^{\text{CPA}}(n) = 1\right] \le \frac{1}{2} + \text{negl}(n) \]

那么，我们说对称加密方案 \((\text{Gen}, \text{Enc}, \text{Dec})\) 在选择明文攻击下具有不可区分性。

通过混合游戏可证明，若对称加密方案 IND-CPA 安全，则其满足混淆电路所需的双重加密安全。

证明思路

1. \(\text{double} \approx \text{mod}\)：
   • 在 mod 中总是加密 \(y_0\): \(\langle E(k_0, k_1', x_b), E(k_0', k_1, y_0), E(k_0', k_1', z_b)\rangle\)
     • 当 \(b=0\) 两游戏相同
     • 当 \(b=1\) 区分它们等价于区分 \(E(k_0', k_1, y_0)\) 与 \(E(k_0', k_1, y_1)\)
2. \(\Pr[\text{mod} = 1] \le \frac{1}{2} + \text{negl}(n)\)：
   • 假设 \(\mathcal{A}\) 已知 \(k_0'\)，收到的 \(E(k_0', k_1, y_0)\) 与 \(b\) 无关，可移除
   • 若 \(\mathcal{A}\) 在 mod 中获胜，则可构造在 \(\text{Game}_\mathcal{A}^{\text{CPA}}(n)\) 中获胜的算法
   • 对 \(\langle E(k_0, k_1', x_b), E(k_0', k_1', z_b)\rangle\) 去一层解密得到 CPA 视图

2. 3 正确性结论

若所用加密方案同时满足不可知密文空间和可验证密文空间，则给定正确输入标签，计算方可以沿拓扑顺序唯一地解出每个门的正确输出标签，最终恢复正确输出。

证明直觉

• 对每个门，正确的两把输入标签只会匹配混淆表中的唯一一行
• 其他行要么根本解不开，要么解出后不落在合法密文空间中
• 再对整个电路使用并合界（union bound），即可把“单门唯一正确”推广到“整条求值路径唯一正确”

3 独立模型（Stand-alone Model）

独立模型下的半诚实安全

对功能 \(f=(f_1,f_2)\)，若存在模拟器 \(S_1,S_2\)，使得

• \(S_1(x,f_1(x,y))\) 与 \(P_1\) 的真实视图不可区分
• \(S_2(y,f_2(x,y))\) 与 \(P_2\) 的真实视图不可区分

则协议在独立模型下对静态半诚实敌手安全。

对两方功能 \(f=(f_1,f_2)\)，若对每个真实世界可允许的非统一 PPT 敌手 \(\mathcal{A}=(A_1,A_2)\)，都存在理想世界可允许的期望多项式时间模拟器 \(\mathcal{B}=(B_1,B_2)\)，使得

\[ \{ideal_{f,\mathcal{B}}(x,y)\}_{|x|=|y|} \approx \{real_{\Pi,\mathcal{A}}(x,y)\}_{|x|=|y|}, \]

则协议 \(\Pi\) 在独立模型下对静态恶意敌手安全实现 \(f\)。

理想世界运行方式

• 诚实方把真实输入发送给可信方；恶意方可中止或提交同长度替换输入
• 可信方收到合法输入对后，先向第一个参与方发送 \(f_1(x,y)\)
• 若第一个参与方恶意，它可根据已获输出选择是否让第二个参与方收到输出；若中止，第二方得到 \(\bot\)
• 诚实方输出可信方返回的消息；恶意方可输出任意 PPT 可计算结果

这个理想功能刻画了两方恶意安全中常见的输入替换与不公平输出递送，但不允许敌手产生除此之外的效果。

独立模型不保证并发安全

假设协议 \(\Pi\) 在独立模型下安全地产生共享密钥 \(k\)，再构造新协议 \(\Pi'\)：如果收到消息等于 \(k\)，就返回 yes，否则返回 no。

若另一个并发协议用一次一密发送

\[ c = k \oplus m,\qquad m\in\{\text{buy},\text{sell}\}, \]

敌手可发送

\[ c' = c \oplus \text{buy} \]

给 \(\Pi'\)：

• 若 \(m=\text{buy}\)，则 \(c'=k\)，回复 yes
• 若 \(m=\text{sell}\)，则回复 no

于是明文被区分，隐私被破坏。

独立模型安全不自动推出并发组合安全，但在顺序组合时仍是安全的。

独立模型	UC 模型
无环境实时交互	有环境 \(Z\) 与协议实时交互
输入在开始时确定	环境可动态喂入输入与消息
恶意证明里常可倒带	UC 中模拟器通常不可倒带
只保证单次/顺序组合	保证任意并发组合

在非并发环境下，UC 安全与独立模型安全可以对应；但一旦允许并发，UC 更强。

总结

• 独立模型：单次执行时安全不安全
• UC 模型：把协议丢进任何更大的系统里反复并发调用后，是否仍像理想功能一样安全

4 姚氏混淆电路的安全性

若使用的加密方案满足 IND-CPA 安全、不可知密文空间和可验证密文空间，则姚氏混淆电路协议在 \(F_{OT}\)-混合模型下，对静态半诚实敌手安全实现单一输出确定性功能。

情况 1：生成方 \(P_1\) 被攻陷

模拟器 \(S_1\) 的输入是 \((x, f(x,y))\)，只需随机采样一份和真实分布一致的生成随机数 \(r_C\)，然后输出 \((x, r_C, f(x,y))\)。

因为生成方本来就知道自己的输入 \(x\) 和自己构造电路所用的随机性，最终输出 \(f(x,y)\)，所以：

\[ \{\mathcal{S}_1(x, f(x, y))\}_{x,y \in \{0,1\}^n} \overset{\text{comp}}{\approx} \{\text{view}_1^\Pi(x, y)\}_{x,y \in \{0,1\}^n} \]

情况 2：计算方 \(P_2\) 被攻陷

\(S_2\) 的输入只有 \((y, f(x,y))\)，并不知道 \(x\)，因此它要构造一个假的混淆电路 \(\widetilde{G}(C)\)，使得无论输入导线拿到哪组标签，最终解码出来的输出都固定为 \(f(x,y)\)。

1. 对每条导线取两把随机标签 \(k_i,k'_i\)
2. 对每个门，把四项都加密成同一把输出标签
3. 在输出导线上，通过解码表把目标输出位固定为 \(f(x,y)\)
4. 再模拟 \(P_1\) 的输入标签与 OT 输出

用混合论证把真实门表逐个替换成只加密活跃输出标签的门表，每一步的可区分性都可归约到双重加密安全，最终得到：

\[ \widetilde{G}(C) \approx G(C). \]

姚氏混淆电路不仅能实现确定性功能，也能实现任意概率功能。

单输出概率功能

可把随机性也并入输入：

\[ f'((x,r),(y,s)) = f(x,y,r\oplus s) \]

双方分别采样随机串 \(r,s\)，再安全计算确定性功能 \(f'\)。

双输出概率功能

若 \(f=(f_1,f_2)\)，可定义

\[ f'((x,r),(y,s)) = (f_1(x,y)\oplus r,\; f_2(x,y)\oplus s), \]

最后各自去掉自己加的掩码即可。

5 混淆电路优化技术

5. 1 Point-and-Permute（标识置换）

经典方案中，计算方需要尝试解密每一行，标识置换给每个标签附加一个标识位，该标识位直接告诉计算方该解哪一行。

同一导线的 \(0/1\) 标签使用不同标识位，两条输入导线的标识位组合决定门表行号。

5. 2 GRR3（4 → 3）

通过巧妙选择输出标签，使一行密文固定为全零，从而无需显式发送这一行。典型实现把加密写成

\[ Enc_{k_a,k_b}(m)=H(k_a\|k_b)\oplus m, \]

然后反过来设置某个输出标签，使第一行密文为 \(0^\kappa\)。

5. 3 GRR2（4 → 2）

利用多项式插值进一步压缩门表，对奇门（如 AND/OR）与偶门（如 XOR）采用不同构造。

对 AND 门，前三行输出同一个标签 \(C^0\)，最后一行输出 \(C^1\)。GRR2 将哈希得到的四个伪随机点嵌入两个低阶多项式，用少量额外点作为混淆表。计算方用自己输入标签对应的点与混淆表点插值，在 \(0\) 点恢复对应输出标签。

对 XOR 门也可做类似插值，因此 GRR2 能把 XOR/AND 都压到 2 行；但它破坏了 Free-XOR 所需的全局偏移结构。

奇门的构造

设 \(p_a^0 = p_b^0 = 0\)，混淆表四行中有三行对应同一输出密钥

• 对 \((1, K_1), (2, K_2), (3, K_3)\) 插值得 \(P(X)\)，设 \(K_5 = P(5), K_6 = P(6)\)
• 对 \((4, K_4), (5, K_5), (6, K_6)\) 插值得 \(Q(X)\)
• 设 \(k_c^0 = P(0)\), \(k_c^1 = Q(0)\)，混淆表仅发送 \((K_5, K_6)\) 与 \(c_r = M_r \oplus p_c^{(\cdot)}\)（4 个加密标识比特）

计算方通过多项式插值解密混淆表。

偶门的构造

• 对 \((1, K_1), (4, K_4)\) 插值得 \(P(X)\)，设 \(k_c^0 = P(0)\)
• 对 \((2, K_2), (3, K_3)\) 插值得 \(Q(X)\)，设 \(k_c^1 = Q(0)\)
• 混淆表仅发送两行 \((P(5), Q(5))\) 或 \((Q(5), P(5))\) 与 4 个加密标识比特

计算方通过多项式插值解密混淆表。

5. 4 Free-XOR

选取全局偏移量 \(\Delta \xleftarrow{}_{\$} \{0,1\}^{\kappa}\)，并令

\[ k_i^1 = k_i^0 \oplus \Delta. \]

对 XOR 门直接设置：

\[ k_c^0 = k_a^0 \oplus k_b^0,\qquad k_c^1 = k_c^0 \oplus \Delta. \]

于是 XOR 门无需混淆表，通信量为 0*，计算只需标签异或。

兼容性

Free-XOR 与 GRR2 不兼容，但可与 GRR3 配合。

5. 5 Half-Gates

• 目标：在兼容 Free-XOR 的前提下，把奇门（尤其 AND 门）开销压到 2 个密文。

对与门 \(v_c = v_a \land v_b\)，取随机比特 \(r\)，有

\[ v_c = (r\land v_a)\oplus((r\oplus v_b)\land v_a). \]

这把一个 AND 门拆成两个半门：

• 生成方半门：生成方知道 \(r\)
• 计算方半门：计算方知道 \(r\oplus v_b\)

每个半门再用 GRR 缩成 1 个密文，所以总共只需 2 个密文。

实践结论

现代 Yao GC 实现通常采用 Point-and-Permute + Free-XOR + Half-Gates：XOR 门免费，AND 门只需 2 个密文，是通信与计算之间较均衡的标准选择。

6 多方混淆电路：BMR 协议

为什么不能直接把 Yao 扩到 \(n\) 方？

若仍让少数人负责生成和计算混淆电路，一旦这些人同时被攻陷，敌手可能拿到所有人的输入标签，从而破坏全部隐私。因此必须让所有参与方共同生成混淆电路。

电路导线真实值记为 \(v_i\)，每个参与方 \(P_j\) 为每根导线选一个掩码比特 \(\lambda_{i,j}\in\{0,1\}\)，总掩码为

\[ \lambda_i = \bigoplus_{j=1}^{n}\lambda_{i,j} \]

外部值（External Value） 定义为

\[ p_i = v_i \oplus \lambda_i \]

每个参与方还为导线生成两份子标签 \(s_{i,j}^0, s_{i,j}^1\)，整条导线的标签由所有子标签拼接而成：

\[ S_i^0=s_{i,1}^0\|\cdots\|s_{i,n}^0\|0,\qquad S_i^1=s_{i,1}^1\|\cdots\|s_{i,n}^1\|1 \]

对每个门 \(g:(w_a,w_b)\to w_c\)，所有参与方通过一个底层 MPC 协议，共同计算门表项 \((A_g,B_g,C_g,D_g)\)。

每一项本质上都由各方本地 PRG 扩展值异或，再异或正确的输出标签 \(S_c^0\) 或 \(S_c^1\)这样没有单个参与方知道完整门表的生成秘密，但所有人合起来仍能得到一张有效混淆表。

对每条输入导线：

1. 先把真实输入值 \(v_i\) 做秘密分享
2. 各方共同计算并公开外部值

\[ p_i = v_i \oplus \lambda_i \]

1. 各方广播对应的子标签 \(s_{i,j}^{p_i}\)

于是得到整条导线的输入标签

\[ S_i^{p_i}=s_{i,1}^{p_i}\|\cdots\|s_{i,n}^{p_i}\|p_i. \]

所有输入导线标签一起组成 garbled inputs。

给定输入标签后，各方可本地扩展 PRG 输出，按输入导线的外部值 \((p_a,p_b)\) 选择相应门表项，本地异或得到输出标签 \(S_c^{p_c}\)，对输出导线，公开对应掩码 \(\lambda_j\)，恢复

\[ v_j = p_j \oplus \lambda_j \]

安全性来源

BMR 的安全性继承自其底层 MPC 子协议（例如 BGW）：

• 若底层协议可安全模拟
• 则整个分布式生成的混淆电路也可被模拟

效率特点

• 轮数复杂度是常数
• 包括：输入分享、并行生成门表、并行生成输入标签
• 混淆表公开后，后续求值完全本地进行

1. 为什么常数轮协议仍可能很慢？

因为轮数少不等于总工作量小。BMR 虽是常数轮，但每个门的标签、PRG、底层 MPC 都可能非常重。

2. 为什么 Half-Gates 很重要？

因为实际电路里 AND 门通常是主要成本来源，Half-Gates 在保留 Free-XOR 优势的同时，把 AND 门压到了 2 个密文，是现代 GC 实现的标准优化。

3. BMR 与 Yao 的最大区别是什么？

Yao 依赖“生成方-计算方”二元角色；BMR 则让所有参与方共同承担标签和门表生成，因此能自然扩到多方场景。

4. 混淆电路里的对称加密和随机谕示机在实践中怎么高效实现？

现代实现通常会把“加密”退化为基于固定密钥 AES、哈希压缩函数或专门相关随机函数的轻量级标签编码；随机谕示机则常由高速哈希或块密码扩展来近似。关键目标不是通用加密意义下的强功能，而是为门级标签传递提供极低延迟的伪随机映射。

5. 如果协议运行在可暂停、可倒带的虚拟机环境里，会有什么风险？

这类环境可能破坏协议对随机性、状态演化和一次性使用的假设。特别是在恶意安全或并发环境里，若敌手能观察、暂停甚至倒带本地执行，往往需要额外的状态保护、硬件假设或更强的模型来刻画安全性。