3.4 混淆电路优化族谱：点旁路与 Free-XOR

3.4 混淆电路优化族谱：点旁路与 Free-XOR

本节摘要：GC 从 1986 年的理论方案到今天的生产引擎，靠四代优化堆出来：点旁路省解密次数、行削减砍半密文行数、Free-XOR 让异或门零成本、半门把与门压到极致。本节逐项讲清每代优化"省的是什么代数结构"，并算清 AES 电路的带宽变迁。

核心概念

优化的总纲只有一句话：让每扇门传输的字节变少，最好不传。第一代优化"点旁路"（point-and-permit）不省字节、省的是求值时的解密尝试——给每枚标签嵌 1 比特指针，求值方拿两枚输入标签直接定位唯一候选行，一扇门只做一次解密而非四次。这个 1 比特的设计还顺手解决了 3.3 节说的"合法行识别"问题：标签最低位固定为 1，密文解出最低位为 0 即为成功。四倍解密开销变一倍，这对 CPU 侧的性能影响比省带宽还大。

第二代"行削减"（row reduction）动真格省字节。观察与门表：若把输出线的两枚标签设计成"一枚是另一枚经固定偏移可得"（比如 C1 = C0 异或一个公共偏移 R），那么知道 C0 就知道 C1，四行里有两行不用单独加密了——表从 4 行降到 2 行，64 字节变 32 字节。

第三代"Free-XOR"（2008 年 Kolesnikov 等提出）把第二步的技巧推到极限：所有导线的 1 标签统一定义为 0 标签异或全局偏移 R。于是异或门的输出标签可直接由输入标签异或得到——整扇门 0 字节、零加密、零解密。布尔电路里异或门往往占八成以上（AES 电路三万余扇门里异或门约 25000 扇），这一代优化让 GC 的成本几乎只随与门数增长。配合第二代，与门表稳定在 2 行 32 字节。

图：三代优化省下的东西各不相同

为什么 Free-XOR 不破坏安全

直觉疑问：所有 1 标签共享同一个偏移 R，标签之间"有代数关系"了，还随机吗？论证的关键是 R 从未离开生成方：求值方见到的任何标签要么是 w0（纯随机），要么是 w0 异或 R——在他没有 R 的前提下，所见集合与"全部独立随机"在计算上不可区分。安全性要求全局偏移 R 在一次电路执行内保持秘密，且绝不复用于另一次混淆。这也解释了 Free-XOR 有一个天然的边界：它依赖异或结构，只对布尔电路成立；面向算术电路（第 5 章）的混淆方案要另起炉灶。

动手演练：半门省多少

def garble_cost(and_gates, xor_gates, inputs, outputs, scheme):
    per_and = {"raw": 4, "row_reduce": 2, "half_gates": 2.5}[scheme] * 16
    per_xor = 16 if scheme == "raw" else 0
    return and_gates * per_and + xor_gates * per_xor + (inputs + outputs) * 16

aes = garble_cost(6800, 25000, 128, 128, "raw")
aes_free = garble_cost(6800, 25000, 128, 128, "row_reduce")
aes_half = garble_cost(6800, 25000, 128, 128, "half_gates")
print(aes, aes_free, aes_half)   # 440448 224256 约 177 KB 量级
​

会话输出依次约 440 KB、224 KB、177 KB。半门的每门成本是"2 行密文加半枚标签"的折算，工程数字各框架略有出入，量级不变。

💡 关键直觉：混淆电路的优化史，就是把"表的行数"逐步变成"代数关系的免费午餐"的历史——能靠结构推出来的，就不必传。这也是整个密码工程学的口味：通信是最贵的，代数是免费的。

本节要点：点旁路省解密、行削减砍半与门表、Free-XOR 消灭异或门成本、半门压榨与门；恶意安全的 40 倍复制让这些优化更具现实意义。电路路线至此完整，下一章把它推向多方。

优化选择的工程决策

四代优化不是"全都要"，而是按场景选配。判断变量有两个：电路里异或门的占比、与门的绝对数量。异或门占比越高，Free-XOR 的红利越大——AES 这类密码函数（异或门约八成）是最大受益者；与门绝对数量决定行削减与半门的收益基数——与门只有几十扇的小电路，优化与否都是几 KB，选最简单的实现反而省心。

再叠加恶意安全维度：cut-and-choose 要复制约 40 份电路，每份都要独立混淆与传输，门表单价乘 40 之后，半门那四分之一的节省突然变得非常可观——这就是为什么恶意安全的工程实现全部默认半门。选型建议照此归纳：半诚实加小电路，原始方案足矣；半诚实加大电路，Free-XOR 加行削减；恶意安全或高频调用，Free-XOR 加半门，一条不落。

最后一个工程细节：全局偏移 R 的生成要用密码学安全的随机源，且一次混淆一个 R。曾有实现图省事把 R 硬编码在代码里，等同于把所有 1 标签的"掩码"公开——门表形同明文。优化的每一分收益都对应一条新的安全前提，这是混淆电路优化史给所有密码工程上的一课。

优化思想的迁移价值

Free-XOR 值得单独再停留片刻，因为它的思想是全书复用率最高的之一：给对象族引入统一的代数结构，让运算之间的转换变成零成本操作。检验一下你已经见过多少它的化身——秘密分享里"减去均匀随机数"让加法免费（2.1 节），GMW 里"异或份额直接异或"让异或门免费（4.1 节），SPDZ 里"数乘只乘一片"让数乘免费（2.1 节），加上本节的"全局偏移异或"让异或门表免费。四处不同场景，同一个配方：找到那个能让运算闭包的结构，把贵操作归约到便宜操作上。

这个配方也是阅读密码学新论文的效率工具。新协议论文往往包装复杂，剥开包装先找"它把什么操作变得免费了、代价是引入了什么结构"——答案找到，论文的核心贡献就定位了。Free-XOR 论文当年被拒稿的故事在圈内流传甚广，理由是"贡献太小，只是个编码技巧"；几年后它成了每个 GC 实现的标配。评价一个技巧的价值要看它省的是不是协议的瓶颈项——带宽恰恰是，于是小技巧撬动大落地。

收尾留一道自测题：如果让你给"或门"设计免费化方案，你会怎么做？提示——或门等价于"对两输入先取非再与再取非"，配合标签语义对调的技巧可以完全避开与门表。能独立答出这题，说明你已经开始用优化者的眼睛看电路，第 4 章的多方世界会需要这双眼睛。