Obfuscation (Part III): Local Mixing

liumuhui 4小时前阅读数 1 #区块链

混淆（第三部分）：局部混合

特别感谢 Nicholas Ho、Ran Canetti 和 Janmajaya Mall 的反馈与审阅

在本系列的上一部分和两个部分中，我们介绍了密码学混淆（iO）协议的两大主要流派：主流且保守的路线，试图基于 somewhat-close-to-standard 的密码学假设来构建它，但代价是巨大的开销；以及 diamond iO，它引入了更多新颖的基于格的假设，并大幅降低了开销——但仍不足以使其具备实际运行的可行性。在本文中，我们将介绍当今正在研究的第三个主要流派，称为“局部混合”（local mixing）。

关于局部混合，首先要注意的是这是一种完全不同的密码学实现方式。这里没有椭圆曲线，没有质因数分解，也没有格。事实上，“常规”密码学中最接近这里所发生的事情的是_对称_密码学——加密和哈希函数设计。

在对称加密和哈希函数设计中，没有向结构良好的数学问题的清晰归约，比如“如果你能破解这个，那就意味着你可以快速分解非常大的数字”。相反，这里有长达五十年的传统：人们尝试创建伪随机函数，数学家对其进行攻击，人们找出抵御这些攻击的设计技巧，直到整个领域趋于稳定，才有了今天像 SHA 和 BLAKE 这样的安全哈希。局部混合的目标是采用_那种_传统，并将其思想应用于_电路_ —— 实现对称密码学家已经了解到其核心构建模块需要实现的属性 —— 同时保持功能不变。

这是一个疯狂而冒险的赌注；它坐落在白盒密码学失败尝试的墓地之上。局部混合作者的希望是，如果我们在这个方向上投入更多精力，并且更加聪明，包括使用 AI 来加速运行哈希函数稳定下来所花费的三十年，并在几年内达到同等的成熟度，同时我们接受更高的开销，那么我们就可以做出一些可行的东西。

局部混合是如何工作的？

局部混合的目标是获取一个电路 $C$（由逻辑门组成，例如 XOR、AND、NOT），然后对其应用一系列变换，这些变换保持 $C$ 的功能，但逐步消除任何查看其内部逻辑的能力。

六个彩色方框从左到右连接：原始电路、增加可逆性、加固、小工具化（gadgetization）、混合、混淆电路。原始电路增加可逆性加固小工具化（gadgetization）混合 $Obf(C)$ 生成混合拆分与交叉遍历最终压缩

在高层次上，最重要的想法正是你可能从“局部混合”这个名字中猜到的：添加大量垃圾门，打乱所有东西，并反复用具有相同功能的不同门集替换电路的小部分。

但正如你所看到的，这只是流水线中的一步——混合步骤。大部分巧妙之处在于流水线的其他步骤——那些为电路进行混合做好准备的步骤，以及经过优化以消除底层电路中某些难以通过混合完全解决的信息泄露的步骤。

让我们逐一介绍这些步骤。我们将从增加可逆性开始，因为该步骤对于为混合以及夹层化（sandwiching）奠定基础是必要的。然后，我们将讨论混合是如何工作的。在那之后，我们将讨论当今混合的局限性，并描述为了弥补这一缺陷而加入的主要辅助手段：小工具化（gadgetization）。

增加可逆性

作为我们的例子，我们将使用你在本系列前面可能已经见过的相同电路：两位加法器。

第一步是将电路 $C$ 转换为_可逆_电路：一种既可以向后运行也可以向前运行的电路。

这样做的主要原因是可逆电路对混合要友好得多。单个可逆门可以被任意数量的其他可逆门替换，这些门加起来具有与原始门相同的功能。用 AND 和 OR 来做到这一点要困难得多。

一个关键原因是不可逆计算会使熵坍缩：AND 将 $00$、$01$ 和 $10$ 折叠为相同的输出，OR 对 $01$、$10$ 和 $11$ 也是如此。因此，默认情况下，长的不可逆门链会破坏大量信息，其数量与电路长度成正比。一个足够大的随机可逆电路可以说是一个安全的密码学置换，而一个足够大的随机不可逆电路会退化为只有少数几种可能的输出。

确实有方法可以生成不具备此属性的大型不可逆电路。例如，如果上面的两位加法器同时返回 $a+b$ 和 $b$ 本身，并且避免返回 $a+b$ 的 $x_{100}$ 位（这样加法就变成了回绕/wraparound），那么它将是一个由不可逆门组成的可逆电路：每个输出都有一个唯一的有效对应输入。但这些技术基本上最终会重新发明可逆电路，所以直接使用可逆电路作为基础介质更容易。

选择使用可逆电路呼应了对称密码学中久经考验的智慧：即使在像哈希函数这样的不可逆应用中，核心底层构建模块也是一个可逆置换，而不可逆性来自于顶部的薄层，正是为了确保在尽可能长的时间内，电路的完整“状态空间”实际上是可达的。

对于我们的两位加法器，使其可逆看起来像这样：

十四条水平线：四个输入位，一条固定为 1 的线，一条固定为 0 的线，以及八条从零开始的辅助线。十六个 r57 门被分组为八个虚线框，每个框有两个门，对应原始加法器的每个门。底部三条线承载三个和位。XOR AND XOR OR AND XOR AND OR a [x1] a [x10] b [x1] b [x10] 1 0 0 0 0 0 0 0 0 0 a [x1] a [x10] b [x1] b [x10] 1 0 a₁∧b₁ a₁₀⊕b₁₀ a₁₀∨b₁₀ a₁₀∧b₁₀ c₁∧(a₁₀∨b₁₀) a+b [x1] a+b [x10] a+b [x100] 正控制负控制活动引脚如果正控制为 1 或负控制为 0，则翻转活动引脚。虚线框 = 原始加法器的一个门，现在是两个 r57 门。

注意这里的几点：

新电路由许多**“r57”门**副本组成，它有三个输入和三个输出。核心逻辑是：除非导线 $A$ 等于 0 且导线 $B$ 等于 1，否则翻转导线 $C$。导线 $A$ 和 $B$ 上的输出保持不变。每个“标准”的两输入一输出门都可以用两个 r57 门来实现。
我们现在以一种更容易进行数学推理的风格来绘制电路。在执行的每个点都有一个明确定义的“状态”——在电路上画一条垂直线，就是每条导线与该垂直线相交时的值。门从左到右按顺序排列。每个门都有三个坐标，代表它所作用的三个导线的位置。
该电路需要一大堆额外的“垃圾”输入，其中其中一个预期为 1，其余预期为 0。其中两个垃圾输入（最上面的 0 和 1）协助通过 r57 门构建“标准”门。其他的保存中间计算的结果。底部的那些是写入输出的空间。

你现在有了一个可以向前或向后运行的两位加法器——算是吧。如果你试图只在输出位置放入 $101$ 并在其他位置放入零，然后从右到左走过各个门，你不会得到输入位置的 $010 + 011$ 或 $100 + 001$，你会得到完全的垃圾。真正能够向后运行_原始计算_的能力不仅取决于最终的输出，还取决于电路上每条中间导线的最终值。

在这一步中，我们获得的主要是一个对象，它的功能与 $C$ 相同，但其格式天然对混合友好得多。

加固

下一步是加固步骤。我们以一个可逆电路 $C$ 作为起点——要么是前一个可逆化步骤的输出，要么是某个“原生可逆”电路。目标是对其进行转换，使得在不操纵门的情况下，除了在某个输入上执行 $C$ 并获得输出之外，没有办法以其他任何方式使用该电路。

有两种情况会违反此条件：

可逆化通常（如上所述）会创建辅助导线（通常称为“ancillas”），它们必须为零。如果 ancillas 被设置为非零值，则可能以任意方式泄露 $C$ 的内部行为。
$C$ 的可逆化版本可以，嗯，反向运行。我们实际上并不想要这样。我们想使用可逆电路_作为一种介质_，但我们不希望 $C$ 可以反向运行。

处理这个问题的主要技术称为加固 Toffoli 技术，其工作原理如下。

我们增加了两组新的导线：

一根额外的 ancilla 导线，称为 $u_\delta$，以及它的辅助线 $u_1...u_j$。该构造_不假设关于_ $u_\delta$ 值的任何内容——它可以以 0 或 1 进入，并且以进入时的相同值离开。$u_1...u_j$ 可以以任何值进入，并保持不变地离开。
输出导线，即输出被复制到的新导线 $y_1...y_k$。同样，该构造对这些导线的内容不做任何假设：它只是将 $C(\text{inputs})$ 异或到这个位置，因此如果它们以 $y_1...y_k=X$ 进入，它们就会以 $y_1...y_k=X \oplus C(\text{inputs})$ 离开

下面是门的样子：

运行 $C$
如果 $u_\delta=0$，设置 $y_1...y_k \oplus= C(\text{inputs})$
反向运行 $C$，清除 $C$ 的所有辅助导线
如果所有必须为零的辅助导线都为零（且所有必须为一的辅助导线都为一），则翻转 $u_\delta$，否则保持原样
再次重复上述四个步骤

或者，以图表形式：

我们可以走查它在正常情况以及每种“异常”情况下的行为：

正常情况：
- $u_\delta$ 以 0 或 1 进入。
- 如果所有辅助导线都具有正确的值，它会在中间被翻转。
- 因此，在两个 $S'$ 块之一中，$C(\text{inputs})$ 被异或到输出导线中，而在另一个中，什么也没有发生。
- 在每个 $S'$ 块中，首先计算 $C(\text{inputs})$，然后（在两次运行之一中）将其异或到输出导线中，然后它被“取消计算”，这将除输出导线之外的所有导线设置回它们的原始值，从而允许中间块忠实地检查它们。
某些辅助项的值不正确：
- $u_\delta$ 在中间没有被翻转，因此它要么两次为 0，要么两次为 1
- 因此，$C(\text{inputs})$ - 或者更确切地说，在某个辅助导线被翻转的情况下 $C(\text{inputs})$ 的混乱执行 - 要么从未被异或到输出导线中，要么被异或了两次，在这种情况下，副本相互抵消
反向运行：
- 完整电路的反向运行与正向运行所做的完全相同！
  - 每个 $S'$ 块都是一个完美的回文
  - 每个 $T$ 块在其门排列上不是回文，但它被设计为在正向和反向运行时表现相同
  - 当你反向运行时，第二个 $T$ 块在 $S'$ 之前运行这一事实并不重要，因为那只是翻转 $u_\delta$，我们已经确定这不会改变最终结果（它只是翻转两个 $S'$ 块中的哪一个触发）

作者的2026 年工作包含了一种不同的方法，称为夹层化（sandwiching）。你可以把夹层化看作是一种加固 Toffoli 的形式，针对没有可逆化步骤的使用场景进行了优化，并且它直接混淆了一个随机排列（最直接的用例是构建公钥加密）。

两半共二十八根导线。上半部分携带自由输入 $x$，由与切片门交织的随机排列 $C$ 作用，然后由与更多切片门交织的独立随机电路 $D$ 作用。在它们之间，十四个 CNOT 将上半部分复制到下半部分，下半部分是固定为零的切片寄存器。x₀ x₁ x₂ x₃ x₄ x₅ x₆ x₇ x₈ x₉ x₁₀ x₁₁ x₁₂ x₁₃ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 C 与 S₁ 交织 N: y ⊕= x D 与 S₂ 交织垃圾 C(x) 上半部分：$x$，随机排列 $C$ 的自由输入。每根导线都是实际输入——没有固定的 ancillas。下半部分：$y$，切片寄存器，固定为 0。正控制负控制活动引脚（如果 ≥1 个控制成立则翻转）活动引脚（如果 2 个控制成立则翻转）

夹层化的开销约为 $\approx 2$x 而不是 $\approx 4$x，并且不需要额外的 $u_\delta$ 导线 - 它只执行一次类似 $S'$ 的步骤。它不需要防御输入上的非零 ancillas，因为它旨在对没有必须为零 ancillas 的随机排列进行操作。它确实能防御_输出导线上_的非零输入，但为此它使用了一个更简单的技巧：一组随机的“切片”门确保如果这些导线非零进入，输入就会被完全打乱。“反向计算 $C$”步骤也被任意的随机电路 $D$ 所取代。

混合

混合在概念上非常容易理解：它是一次对电路的一小部分反复进行变换。每次变换在保持功能的同时，破坏（或者更确切地说，混淆和扩散）一定量的关于结构的可见信息。经过数百万轮变换后，原始电路中的每个门都将经历了数百次混合步骤。

在当前的代码中，混合是通过多种技术的组合完成的，我们将依次描述这些技术。

生成混合

生成混合的工作原理如下：

制作一个包含所有具有相同功能的小型电路的巨型表（注意：这将不可避免地包含“小型电路”，其中包括彼此完全不交互的子块对）
反复从电路中抓取门集，这些门集要么是连续的，要么中间没有任何干扰其功能的门
在表中检查你选择的门集属于哪个“类”，并用同一个类中的另一个随机小型电路替换它
弄清楚新子电路被允许处于的合法位置范围，然后再移动太远以至于功能破坏（例如，输入移动到最后更新它的输出导线之前）。将该门移动到该范围内的随机位置。
重复

局部混合仓库中的大量工作都是关于优化此过程的：有一个规范化步骤，它使用一些技巧在表之前自动识别相同的小型电路，然后转换为多项式形式，然后是一种“彩虹表”机制，以节省空间的方式存储所有内容并使查询快速。

下面是生成混合工作原理的简化图（生产版本需要约 7-10 个门的组，彩虹表大小达数百 GB，但也提供了小得多的“精选表”）：

五层：原始四门电路、规范类、分类到桶中的多项式状态、匹配桶的彩虹表条目，以及拼接后的替换。所选路径为蓝色；汇聚到同一类或桶的同级路径为蓝灰色。· · · 共计 331 776 个 · · · 共计 12 123 个类桶 0 $x_0'=1+x_0+x_1$ $x_1'=x_0+x_1+x_2$ $x_2'=x_1+x_2+x_3$ 桶 1 $x_2'=x_0+x_1+x_2$ $x_3'=x_0+x_1+x_3$ $x_1'=x_0+x_1+x_3$ 桶 2 $x_0'=1+x_0+x_2+x_1x_2$ $x_2'=1+x_1+x_2+x_0x_1$ $x_3'=x_1+x_2+x_3$ $x_2'=x_0+x_2+x_3$ 桶 3 $x_0'=x_0+x_2$ $x_0'=x_0+x_2x_3$ $x_3'=x_0+x_2+x_3$ · · · 密钥 $x_0'=1+x_0+x_2+x_1x_2$ · $x_2'=1+x_1+x_2+x_0x_1$ 窗口密钥 $x_3'=x_1+x_2+x_3$ 密钥 $x_2'=x_0+x_2+x_3$ 四个门中有三个发生了变化，写入的导线也随之改变两种拼写都不包含抵消对——这不是重新排序 1 · 最多四根导线上的原始四门电路 2 · 规范化 3 · 评估多项式状态，哈希，分类到桶中 4 · 彩虹表 — 为该桶存储的条目 5 · 拼接 — 功能相同，门不同

生成混合是流水线中最强大的步骤。它能够整体改变窗口内值的表示方式。这使得它成为引入非线性最有效的步骤——达到原始电路中的任何值 $x$ 仅由混淆电路中值的非线性函数表示的程度。生成混合还可以潜在地将原始计算图中相距很远的电路的两个部分“粘合在一起”，将这些部分的组合子电路替换为交织它们的子电路——然后进一步的几代混合将使这种交织难以检测和逆转。

流水线进行了大量的生成混合轮次，目标是多次覆盖电路中的每个门。它还分多个阶段进行：一个偏向于扩展电路，另一个偏向于保持大小不变，最后最终将其稍微缩小。

拆分

拆分用更广泛的一控制和二控制门集替换了 r57 门。这里有一系列技术。

($\oplus$ 表示异或，$\vee$ 表示或，$\wedge$ 表示与，$\neg$ 表示非)

首先，你可以将 $a \oplus= b \vee \neg c$ 替换为 $a \oplus= b$；$a \oplus= \neg b \wedge \neg c$ 或者 $a \oplus= \neg c$；$a \oplus= b \wedge c$。

左边三根导线上的单个 r57 门，箭头指向其上下右侧的两个等效双门分解，右边的真值表显示每次拆分的两半在不相交的行上触发。a b c $a \oplus= b \vee \neg c$ 除非 $b=0$，$c=1$ 否则触发拆分 1 $a \oplus= b$ 然后 $a \oplus= \neg b \wedge \neg c$ a b c 拆分 2 $a \oplus= \neg c$ 然后 $a \oplus= b \wedge c$ a b c b c r57 拆分 1 拆分 2 0 01– – 0 10– –– – 1 01 – – 1 11 –– 正控制负控制如果 ≥1 个控制成立则翻转如果所有控制都成立则翻转

其次，对于任何导线，你可以执行以下操作：

选择修改导线的两个位置 $A$ 和 $B$
在位置 $A$ 和 $B$ 处，翻转导线 - 用在完全相反的情况下修改该导线的门替换修改该导线的门
在 $A$ 和 $B$ 之间，在任何读取该导线的门中取反该导线的角色 - 如果它是正控制，则使其成为负控制，反之亦然

绘制了两次相同的八导线电路。上面，导线 $w$ 被许多门写入和读取。下面，两个针对 $w$ 的括号门通过翻转它们的引脚类型和所有控制极性来取反，并且它们之间每个读取 $w$ 的控制都被反转。在跨度内写入 $w$ 的门无需更改。之前 0 1 2 w 4 5 6 7 之后取反两个括号门，反转它们之间每个读取 w 的控制 0 1 2 w 4 5 6 7 括号括号写入 w — 未更改正控制负控制活动引脚（如果 ≥1 个控制成立则翻转）活动引脚（如果 2 个控制成立则翻转）

拆分有助于破坏关于单个导线和门_含义_的特定类型的可见信息：经过足够的轮次后，实际上无法分辨某根导线在哪里代表“$x$”，哪里代表“$\neg x$”。

通过拓宽正在使用的门集，拆分还为实施下一步创造了必要的条件，使我们能够以少得多的限制移动门的顺序。

交叉遍历

彼此不“冲突”的两个门（即一个门写入另一个门读取的值）可以自由重新排序。但是_确实_相互冲突的两个门也可以重新排序——只要你添加一个新门来补偿读写交换位置。

下面是它的工作原理，分为三种情况：

三个面板，每个面板左侧显示双门冲突，右侧显示其精确的三门重写。R1 拆分移动器，R2 拆分碰撞器，R3 具有更复杂的效果。R1 · 碰撞器写入移动器的控制 — 移动器拆分 x₀ x₁ x₂ x₃ x₄ x₀ ⊕= x₁x₄ 变为 x₁x₄ ⊕ x₂x₃x₄，因为 x₁ → x₁ ⊕ x₂x₃ R2 · 移动器写入碰撞器的控制 — 碰撞器拆分 x₀ x₁ x₂ x₃ x₄ x₂ ⊕= x₁x₃ 变为 x₁x₃ ⊕ x₀x₃x₄，因为 x₁ → x₁ ⊕ x₀x₄ R3 · 每个读取对方的目标 — 移动器转换并拆分 x₀ x₁ x₂ x₃ x₄ x₄=0 · 绿色和橙色都是无操作，所以紫色可以自由交叉 x₄=1 · 绿色做紫色以前做的事情，紫色现在是无操作紫色移动的片段 · 橙色碰撞器 · 绿色由交叉创建的部分正控制负控制活动引脚（如果所有控制都成立则翻转）

原则上，你可以随心所欲地移动一个门，为它穿过的每个门留下“残留物”。

请注意，此步骤接受带有 $k$ 个控制的门（上图显示 $k=2$，但也支持 $k \geq 3$），并输出最多带有 $2k-1$ 个控制的门。

这对于交叉遍历本身来说不是一个严重的问题。只是意味着经过多轮之后，你可能会得到具有许多控制的门。此外，在更高的控制计数下，每次交叉可能需要创建多个“残留物”门。

然而，如果我们决定_在_生成混合_期间_进行交叉遍历，而不是像现在这样仅在它之后进行，这就是一个问题，因为当前的彩虹表只包含 r57 门。人们_可以_制作一个包含更高控制数门的彩虹表，但这有可能在相同的覆盖水平下使彩虹表的大小呈指数级增长。最简单的解决方案是将每个 3+ 控制门还原为一系列二控制门。

fcompress

此步骤简化了在读取之前修改导线的一系列门。

这样做主要不是为了做更多的隐藏，而是为了缩小程序。论点是，如果我们不这样做，攻击者无论如何都可以自己做这件事，以便有一个更小的对象可以使用，所以我们不妨把同样的效率提升给予合法用户。

以下是一些简化：

混合到此结束！

这里值得一提的最后一点是小工具化交换。我们稍后将讨论的小工具化阶段包括一种“角色交换”机制，其中两根导线在电路中的某个位置交换它们的值和角色。影响输出导线的交换在最后的单一步骤中被撤销，该步骤将正确的输出导线提取到正确的位置。尽管这是在小工具化阶段完成的，我仍然认为它是一种混合类型。它允许导线“垂直”移动，补充了交叉遍历阶段完成的“水平”移动。

你可以将不同的混合族视为在电路上进行很好地互补的“数独式”变换：

一个单独的九乘九网格，时间沿水平轴，导线沿垂直轴向下。整列、三乘三窗口、整行和单个单元格被着色，以显示每个移动族可以到达的区域。时间 → 导线 ↓ 拆分原地重写导线值小工具化交换值跨导线移动生成混合完全替换一个小窗口交叉遍历 · fcompress 门跨时间移动

小工具化：为什么我们需要它？

为了理解对下一个阶段的需求，我们应该问一个问题：插入垃圾门、打乱和混合要么不擅长解决，要么从根本上完全无法解决的数据泄露有哪些？

这里有一个简单的答案（它并非_严格_正确，但目前假设它是正确的）：$C$ 中的每一根“导线”，在每个时间点，仍然在混淆电路 $Obf(C)$ 的_某处_被实例化。

如果攻击者拥有原始电路 $C$ 和混淆电路 $Obf(C)$，他们可以多次运行原始电路，查看混淆电路中的哪些导线与原始电路中的导线完美相关，并利用这一点来确定从一个到另一个的映射。

当然，在现实世界的应用中，攻击者无法访问 $C$。但在许多现实世界的应用中，他们几乎可以做到。几乎所有的 $C$ 都是公开的，唯一的秘密是 $Obf(C)$ 试图隐藏的某个“嵌入式密钥”。即使攻击者根本无法访问 $C$，他们也可以做这样的事情：

攻击者一开始就知道 $Obf(C)$ 的哪些_输入导线_对应于 $C$ 的哪些_输入导线_
假设你有一个预言机，给定 $C$ 中的一个门，找到 $Obf(C)$ 中与之对应的门和导线（例如，这可能就是我们上面描述的基于相关性的检测器）
枚举我们已经知道的所有可能导线，以及电路中_下一个_门的所有可能选项。对于每个选项，运行预言机。如果它成功地在 $Obf(C)$ 中找到映射到该门的特征，那么该门必须存在于 $C$ 中
继续下去，利用这种攻击暴露 $C$ 中越来越深处的更多门，直到你暴露了整个电路

添加垃圾门对此完全没有影响。打乱门对此完全没有影响。

原则上，混合_可以_影响这一点。例如，想象一下你有一个执行以下操作的子电路：

$$ x \oplus= a \wedge b $$

你_可以_将其替换为：

$$ x \oplus= y \oplus z $$

$$ y \oplus= a \vee b $$

$$ z \oplus= a \oplus b $$

行为完全相同：只有当 $a$ 和 $b$ 都为 1 时，$x$ 才会被翻转。但在替换的子电路中，表达式 $a \wedge b$ 从未被实例化。

发生的事情是：

$a \wedge b$ 被 $(a \vee b) \oplus (a \oplus b)$ 替换（这是一个代数恒等式）
$a \vee b$ 和 $a \oplus b$ 通过 $y$ 和 $z$（借用然后放回原位的导线）_分别_应用，因此即使是 $a \wedge b$ 的这两个组件也相隔了几步。

原则上，这种转换可以通过局部混合来完成。更复杂的转换可以通过局部混合完成。原则上，你可以混合足够多的次数，以至于仅仅由于随机机会，这样的事情就会发生在每根导线上很多次。

那是作者的_希望_。但是，到目前为止，混合还没有被证明足够好。结果证明，$C$ 中的值与混淆中仍然存在的值之间存在太多相关性。作者通过_热力图_将这些相关性可视化：

小工具化成为一种更确定性地确保这类相关性不存在的方法，甚至在任何混合开始之前也是如此。我们提出问题“$C$ 中的每根导线绝不能被显式实例化”，并明确地解决它。

小工具化：它是如何工作的？

我们将电路中的每个门替换为一个“小工具化门”。例如，这里是 r57 门最简单可能的小工具化：

在这种设计中，我们将每根导线 $w_i$ 表示为两根导线 $s_i$ 和 $r_i$，满足 $w_i=s_i \oplus r_i$。上图中的构造允许我们在_表示_上复制所需的行为 - 仅当 $w_b=1$ 或 $w_c=0$ 时才翻转 $w_a$ 的表示 - 而无需显式实例化 $w_a$、$w_b$ 或 $w_c$。

这里的构造借鉴了多方计算的思想，其目标是一样的：参与者从输入的秘密共享开始，并获得输出的秘密共享，而不向任何单台机器暴露计算中的任何值（输入、输出或中间值）。这里的构造是最简单的两方案例。另一个灵感来源是安全硬件文献，例如这项工作。在安全硬件设计中，一个常见的模型是_$d$-探测模型_：假设对手可以读取多达 $d$ 根导线，并在此约束下从数学上保证他们什么也学不到。

如果我们实现了这种类型的小工具，那么我们就能保证在小工具化输出中没有单根导线代表 $C$ 的任何特定导线 - 除非我们_真的_运气不好，混合步骤纯粹由于盲目运气撤销了一次小工具化，这种情况目前非常罕见，并且可以优化混合以进一步防范。

现在让我们看看使小工具化成为可能的完整流水线。

两半共十根导线。垃圾填充和重新填充各自反复扫过辅助半部分，多次击中几根导线。每个载体都被掩码和去掩码。小工具化部分包含一个小工具化 r57 和一次导线交换；路由部分包含另一次交换。粗橙线跟随值 2 的载体移动到带半部分又返回。垃圾填充掩码小工具化门去掩码路由重新填充 x₁ x₂ x₃ x₄ x₅ ⋮ z₁ z₂ z₃ z₄ z₅ ⋮ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ 小工具化 r57 交换交换输出垃圾粗橙线跟踪值 2 的载体：交换将其移动到 z₄，路由将其带回。每个小工具化 r57 是六根导线（三对）上的六个 r57 门；每次交换是三根导线（进、出、辅助）上的六个 r57 门。正控制负控制活动引脚（如果 ≥1 个控制成立则翻转）⋯ 省略的门

（注意：为了简化说明，本描述将来自旧设计的秘密共享小工具与截至今天当前的小工具化流水线混合在一起）

我们上面讨论的小工具化门进入第三阶段，并且它们与我们之前提到的交换交织在一起，后者切换两根导线的角色。其余的阶段是为了提供使整个流水线正确所需的脚手架：

垃圾填充 阶段用垃圾覆盖新添加的导线（图中的 $z_1...z_5$），垃圾是输入的高次函数。高次性之所以实现，是因为每个门的控制可以来自 $x$ 部分或 $z$ 部分，因此每根 $z$ 导线的次数随着它合并 $x$ 和其他 $z$ 而不断上升
掩码阶段将 $(\text{value}, \text{junk})$ 替换为 $(\text{value} \oplus \text{junk}, \text{junk})$。这将输入带入小工具化门所需的正确形式。一旦掩码阶段完成，小工具化电路中就没有单根导线直接代表 $C$ 中的导线 - 该责任现在_共享_给异或在一起等于 $C$ 中导线的两根导线。
小工具化门 阶段，如上所述，包含来自可逆化和加固电路的实际门的每一个的小工具化门，外加额外的交换
去掩码 阶段将 $(\text{value} \oplus \text{junk}, \text{junk})$ 带回 $(\text{value}, \text{junk})$，以便我们可以读出输出
路由阶段将输出移回它们应该在的位置。你可以把它看作是“撤销所有交换”，不过我们只关心代表 $C$ 输出的导线。
重新填充 阶段向所有垃圾导线添加更多垃圾。这是一个额外的预防措施，使对手更难看到垃圾值是什么，从而使反转掩码变得更加困难。

现在，我们已经消除了 $G$（小工具化输出）中的导线与原始 $C$ 中的导线之间的任何直接一一对应关系。我们甚至消除了_相关性_：$a \oplus b$ 与 $a$ 以及 $b$ 的相关性为零 - 至少，只要 $a$ 和 $b$ 彼此独立，这在高质量的垃圾填充阶段下大致是真的。

但仍然存在一种主要的攻击类型。

线性代数攻击

在小工具化前的电路 $C$ 和小工具化电路 $G$ 之间，我们仍然存在一种可发现的关系类型：线性（或者更准确地说，仿射）关系。$C$ 中的每根导线 $w_i$，在执行的某个特定位置，对应于 $G$ 中的某个 $g_j \oplus g_k$。即使我们扩展了小工具化，使得有例如十个掩码进入异或，你也可以使用_线性代数攻击_发现所有此类关系。

线性代数攻击的工作原理如下。考虑 $