Obfuscation (Part III): Local Mixing

Special thanks to Nicholas Ho, Ran Canetti and Janmajaya Mall for feedback and review

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

In the last two parts of this series, we have gone through two of the major families of cryptographic obfuscation (iO) protocols: the mainstream and conservative line that tries to build it from somewhat-close-to-standard cryptographic assumptions, but at the cost of galactic overhead, and diamond iO, which adds more novel lattice-based assumptions, and reduces the overhead massively - but still not by enough to make it viable to run.

在本系列的最后两部分中，我们了解了密码混淆 (iO) 协议的两个主要系列：主流和保守的系列，试图从某种程度上接近标准的密码假设构建它，但以银河系开销为代价；钻石 iO，它添加了更多新颖的基于晶格的假设，并大幅减少了开销 - 但仍然不足以使其能够运行。

In this post, we will go through the third major family being worked on today, called "local mixing".

在这篇文章中，我们将介绍今天正在研究的第三个主要系列，称为“本地混合”。

The first thing to note about local mixing is that this is a totally different way of doing cryptography .

关于本地混合，首先要注意的是，这是一种完全不同的加密方式。

There are no elliptic curves, no prime factorization and no lattices anywhere here.

这里没有椭圆曲线，没有质因数分解，也没有格子。

In fact, the closest thing that "regular" cryptography has to what is going on here is symmetric cryptography - encryption and hash function design.

事实上，“常规”密码学与这里发生的事情最接近的是对称密码学 - 加密和哈希函数设计。

In symmetric encryption and hash function design, there are no clean reductions to well-structured mathematical problems like "if you can crack this, that would imply you can quickly factor very large numbers".

在对称加密和哈希函数设计中，对于结构良好的数学问题没有明确的简化，例如“如果你能破解这个问题，那就意味着你可以快速分解非常大的数字”。

Instead, there is a fifty-year-long tradition of people attempting to create functions that are pseudorandom, mathematicians attacking them, and people figuring out design tricks that protect against those attacks, until the whole thing stabilized and we have secure hashes like SHA and BLAKE today.

相反，有一个长达五十年的传统：人们试图创建伪随机函数，数学家攻击它们，人们找出防止这些攻击的设计技巧，直到整个事情稳定下来，我们今天有了像 SHA 和 BLAKE 这样的安全哈希。

The goal of local-mixing is to take that tradition, and apply its ideas to circuits - achieving the properties that symmetric cryptographers have learned that their core building blocks need to achieve - while being functionality-preserving .

本地混合的目标是继承这一传统，并将其思想应用于电路 - 实现对称密码学家已经了解到的其核心构建块需要实现的属性 - 同时保留功能。

This is a wild and risky bet; it sits on a graveyard of failed attempts at white-box cryptography .

这是一个疯狂而冒险的赌注；它坐落在白盒密码学失败尝试的坟墓上。

The local mixing authors' hope is that if we push even more effort into this direction, and are smarter about it, including using AI to speed-run the three decades that hash functions took to stabilize and get to equal maturity in a few years, and at the same time we accept higher overhead, then we could make something that works.

本地混合作者的希望是，如果我们在这个方向上投入更多的努力，并且在这方面更加聪明，包括使用人工智能来加速哈希函数在几年内稳定并达到同等成熟度所需的三十年，同时我们接受更高的开销，那么我们就可以做出一些有用的东西。

The goal of local mixing is to take a circuit \(C\) (made up of logic gates, eg.

局部混合的目标是采用电路\(C\)（由逻辑门组成，例如

XOR, AND, NOT), and then apply a series of transformations to it, which preserve the functionality of \(C\) , but progressively remove any ability to see its internal logic.

XOR、AND、NOT），然后对其应用一系列转换，这保留了 \(C\) 的功能，但逐渐消除了查看其内部逻辑的任何能力。

At a high level, the most important idea is exactly what you might guess from the name "local mixing": add a whole bunch of junk gates, shuffle everything around, and repeatedly replace small portions of the circuit with different sets of gates that have the same functionality.

在高层次上，最重要的想法正是您可能从“本地混合”这个名称中猜到的：添加一大堆垃圾门，将所有内容打乱，并用具有相同功能的不同门组重复替换电路的一小部分。

But as you can see, that is only one step in the pipeline - the mixing step.

但正如您所看到的，这只是管道中的一个步骤 - 混合步骤。

The bulk of the cleverness is in the other steps in the pipeline - the steps that set up for circuit to be friendly to mixing, and that are optimized to remove some information leakage in the underlying circuit that is difficult for mixing to fully address.

大部分的聪明之处在于管道中的其他步骤——这些步骤为电路设置了对混音友好的步骤，并且经过优化以消除底层电路中难以完全解决混音的一些信息泄漏。

Let us go through these steps one by one.

让我们一一完成这些步骤。

We will start off with adding reversibility, because that step is necessary to set the stage for mixing, and then sandwiching.

我们将从添加可逆性开始，因为该步骤对于为混合和夹层奠定基础是必要的。

Then, we will talk about how mixing works.

然后，我们将讨论混合是如何工作的。

After that, we will talk about the limits of mixing as it stands today, and describe the major helper that was added to compensate: gadgetization.

之后，我们将讨论当今混合的局限性，并描述为弥补而添加的主要助手：小工具化。

As our example, we will use the same circuit that you may have already seen earlier in this series: the two-bit adder.

作为我们的示例，我们将使用您可能已经在本系列前面看到的相同电路：两位加法器。

The first step is to convert the circuit \(C\) into a reversible circuit: a circuit that can be run backwards as well as forwards.

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

The main reason why this is done is that reversible circuits are far more friendly to mixing.

这样做的主要原因是可逆电路对混合更加友好。

A single reversible gate can be replaced with an arbitrarily large number of other reversible gates that all add up to having the same functionality as the original gate.

单个可逆门可以替换为任意数量的其他可逆门，所有这些可逆门加起来具有与原始门相同的功能。

Doing that with eg.

这样做，例如。

AND and OR is much more difficult.

“与”和“或”要困难得多。

A key reason why is that irreversible computation collapses entropy : AND collapses 00, 01 and 10 into the same output, and likewise with OR and 01, 10 and 11.

一个关键原因是不可逆计算会折叠熵：AND 将 00、01 和 10 折叠成相同的输出，OR 和 01、10 和 11 也同样如此。

And so, long chains of irreversible gates will by default destroy huge amounts of information, proportional to the length of the circuit.

因此，不可逆门的长链默认会破坏大量信息，与电路的长度成正比。

A big-enough random reversible circuit is plausibly a secure cryptographic permutation, a big-enough random irreversible circuit degenerates into having only a few possible outputs.

一个足够大的随机可逆电路似乎是一种安全的密码排列，一个足够大的随机不可逆电路退化为只有几个可能的输出。

There are ways to generate big irreversible circuits that don't have this property.

有一些方法可以生成不具有此特性的大型不可逆电路。

For example, if the two-bit adder above returned both \(a+b\) and \(b\) itself, and avoided returning the x100 digit of \(a+b\) (so the addition becomes wraparound), then it would be a reversible circuit made out of irreversible gates: every output would have a single valid corresponding input.

例如，如果上面的两位加法器返回 \(a+b\) 和 \(b\) 本身，并避免返回 \(a+b\) 的 x100 位（因此加法变成环绕式），那么它将是由不可逆门组成的可逆电路：每个输出将有一个有效的相应输入。

But such techniques basically end up reinventing reversible circuits, and so it's easier to just use reversible circuits as the base medium directly.

但这些技术基本上最终会重新发明可逆电路，因此直接使用可逆电路作为基础介质会更容易。

The choice to go with reversible circuits echoes time-worn wisdom from symmetric cryptography: even in irreversible applications like hash functions, the core underlying building block is a reversible permutation, and the irreversibility comes from a thin layer on top, precisely in order to make sure that for as long as possible, the full "state space" of the circuit is actually reachable.

选择可逆电路与对称密码学中古老的智慧相呼应：即使在哈希函数等不可逆应用中，核心底层构建块也是可逆排列，而不可逆性来自顶部的薄层，正是为了确保在尽可能长的时间内，电路的完整“状态空间”实际上是可到达的。

In the case of our two-bit adder, making it reversible looks like this:

对于我们的两位加法器，使其可逆如下所示：

You now have a two-bit adder that you can run forwards or backwards - sort of.

现在你有了一个可以向前或向后运行的两位加法器——有点像。

If you try to just put 101 into the output position and zeroes in the other positions, and walk through the gates right to left, you won't wind up with 010 + 011 in the input positions, or 100 + 001, you'll wind up with total junk.

如果你尝试将 101 放入输出位置，将 0 放入其他位置，然后从右向左穿过门，那么你最终不会在输入位置得到 010 + 011，或者 100 + 001，你最终会得到完全垃圾。

The ability to actually run the original computation backwards depends on having not just the final output, but also the final values on each intermediate wire on the circuit.

实际向后运行原始计算的能力不仅取决于最终输出，还取决于电路上每条中间线上的最终值。

The main thing that we have gained in this step is that we have an object that does the same thing as \(C\) , but in a format that is naturally much more friendly to mixing.

我们在这一步中获得的主要成果是，我们有一个与 \(C\) 执行相同操作的对象，但其格式自然对混合更加友好。

The next step is a hardening step.

下一步是硬化步骤。

We take a reversible circuit \(C\) as a starting point - either the output of the previous reversibilization step, or some "natively reversible" circuit.

我们以可逆电路 \(C\) 作为起点 - 要么是前一个可逆步骤的输出，要么是一些“本机可逆”电路。

The goal is to transform it in such a way that, without manipulating the gates, there is no way to use the circuit that does anything other than executing \(C\) on some input and getting the output.

目标是以这样的方式对其进行转换：在不操纵门的情况下，除了在某些输入上执行 \(C\) 并获取输出之外，无法使用该电路执行任何其他操作。

The main technique to deal with this is called the hardened Toffoli technique, and works as follows.

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

We can walk through its behavior in both the normal case, and each of the "unusual" cases:

我们可以了解它在正常情况和每种“异常”情况下的行为：

The full circuit run backwards just does the exact same thing as running it forwards!

整个电路向后运行与向前运行完全相同！

The authors' 2026 work includes a different approach, called sandwiching .

作者的 2026 工作采用了一种不同的方法，称为“三明治”。

You can think of sandwiching as a form of hardened Toffoli optimized for the use case where there is no reversibilization step, and it's directly obfuscating a random permutation (the most immediate use case is building public-key encryption).

您可以将三明治视为一种强化的 Toffoli 形式，针对没有可逆步骤的用例进行了优化，并且它直接混淆了随机排列（最直接的用例是构建公钥加密）。

Sandwiching has overhead \(\approx 2x\) instead of \(\approx 4x\) and does not require the extra \(u_{\delta}\) wire - it only does an \(S'\) -like step once.

三明治的开销为 \(\approx\) 而不是 \(\approx\)，并且不需要额外的 \(u_{\delta}\) 线 - 它只执行一次 \(S'\) 类似的步骤。

It does not need to defend against nonzero ancillas on the input, because it's intended to operate on random permutations that have no must-be-zero ancillas.

它不需要防御输入上的非零辅助，因为它旨在对没有必须为零的辅助的随机排列进行操作。

It does defend against nonzero inputs on the output wires , but for that it uses a simpler trick: a set of random "slice" gates ensures that if those wires come in nonzero, the input gets completely mangled.

它确实可以防御输出线上的非零输入，但为此它使用了一个更简单的技巧：一组随机“切片”门确保如果这些线输入非零，则输入会被完全破坏。

The "compute \(C\) backwards" step is also replaced with an arbitrary random circuit \(D\) .

“向后计算\(C\)”步骤也被替换为任意随机电路\(D\)。

Mixing is conceptually very easy to understand: it's repeatedly making transformations to a small part of the circuit at a time.

混合在概念上非常容易理解：它一次重复地对电路的一小部分进行转换。

Each transformation preserves functionality while destroying (or rather, confusing and diffusing ) some amount of visible information about structure.

每个转换都保留了功能，同时破坏（或者更确切地说，混淆和扩散）有关结构的一些可见信息。

After many millions of rounds of transformation, each gate in the original circuit will have undergone mixing steps hundreds of times.

经过数百万轮的变换，原始电路中的每个门都会经历数百次混合步骤。

In the current code, mixing is done through a combination of several techniques, which we will describe in turn.

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

A large amount of the work in the local mixing repo is about optimizing this procedure: there's a canonicalization step which uses a few tricks to automatically identify small circuits that are the same even before the table, then conversion to a polynomial form, and then a "rainbow table" mechanism to store everything space-efficiently and make querying fast.

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

Here is a simplified diagram of how generation mixing works (the production version takes groups of ~7-10 gates, and the rainbow table is in the hundreds of gigabytes, though a much smaller "curated table" is also available):

这是生成混合工作原理的简化图（生产版本需要大约 7-10 个门组，彩虹表有数百 GB，尽管也可以使用更小的“策划表”）：

Generation mixing is the most powerful step in the pipeline.

生成混合是管道中最强大的一步。

It's able to change around the ways in which values inside a window are represented wholesale.

它能够改变窗口内值的整体表示方式。

This makes it the most effective step for introducing nonlinearities - getting to a point where any value \(x\) in the original circuit is represented only by a nonlinear function of the values in the obfuscated circuit.

这使得它成为引入非线性的最有效步骤 - 达到原始电路中的任何值仅由模糊电路中的值的非线性函数表示的程度。

Generation mixing can also potentially "glue together" two pieces of the circuit that are far away in the original computation graph, replacing a sub-circuit that is a combination of those two pieces with one that interleaves them - and then further generations of mixing would make the interleaving hard to detect and reverse.

生成混合还可能将原始计算图中相距较远的两块电路“粘合在一起”，用将这两块电路组合在一起的子电路替换为将它们交错的子电路，然后进一步生成混合将使交错难以检测和逆转。

The pipeline does a huge number of rounds of generation mixing, with the goal of covering each gate in the circuit many times.

该管道进行大量轮次生成混合，其目标是多次覆盖电路中的每个门。

It also does it in multiple phases: one which biases toward expanding the circuit, and the other which biases toward keeping the size the same, and at the end eventually shrinking it back down slightly.

它还分多个阶段进行：一个阶段倾向于扩展电路，另一个阶段倾向于保持大小相同，最后最终将其稍微缩小。

Splitting replaces r57 gates with a broader set of one and two-control gates.

分裂用更广泛的一组单控制门和二控制门取代了 r57 门。

There is a bundle of techniques here.

这里有很多技术。

( \(\oplus\) means xor, \(\lor\) means or, \(\land\) means and, \(\neg\) means not)

( \(\oplus\) 表示异或，\(\lor\) 表示或，\(\land\) 表示与，\(\neg\) 表示非）

First, you can replace \(a\ {\oplus}{=}\ b \lor \neg c\) with either \(a\ {\oplus}{=}\ b;\ a\ {\oplus}{=}\ \neg b \land \neg c\) or \(a\ {\oplus}{=}\ \neg c;\ a\ {\oplus}{=}\ b \land c\) .

首先，您可以将 \(a\ {\oplus}{=}\ b \lor \neg c\) 替换为 \(a\ {\oplus}{=}\ b;\ a\ {\oplus}{=}\ \neg b \land \neg c\) 或 \(a\ {\oplus}{=}\ \neg c;\ a\ {\oplus}{=}\ b \land c\) 。

Splitting helps to destroy a particular type of visible information about the meaning of individual wires and gates: after enough rounds, it would not be practical to tell where some wire represents "x" and where it represents "not-x".

分裂有助于破坏有关各个电线和门的含义的特定类型的可见信息：经过足够多的轮次后，分辨某些电线在哪里代表“x”以及在哪里代表“非x”是不切实际的。

By broadening the set of gates being used, splitting also creates the conditions that are necessary to implement the next step, which allows us to shift around the order of gates with much fewer restrictions.

通过扩大所使用的门的集合，分裂还为实施下一步创造了必要的条件，这使我们能够以更少的限制改变门的顺序。

Two gates that do not "collide" with each other, in the sense of one gate writing a value that the other reads, can be freely reordered.

两个不互相“冲突”的门，即一个门写入另一个门读取的值，可以自由地重新排序。

But two gates that do collide each other can also be reordered - as long as you add a new gate to compensate for the read and write switching places.

但是，两个确实相互冲突的门也可以重新排序 - 只要添加一个新门来补偿读写切换位置即可。

In principle, you can move a gate as far as you want, leaving behind "residues" for each gate that it crosses through.

原则上，你可以将门移动到你想要的距离，为它穿过的每个门留下“残留物”。

Notice that this step takes gates with \(k\) controls (the above diagram shows \(k = 2\) , but \(k \ge 3\) is also supported) and outputs gates with up to \(2k-1\) controls.

请注意，此步骤采用具有 \(k\) 个控制的门（上图显示 \(k = 2\) ，但也支持 \(k \ge 3\) ）并输出具有最多 \(2k-1\) 个控制的门。

This is not a serious problem for the crossing walk itself.

对于人行横道本身来说，这并不是一个严重的问题。

It just means that after many rounds of it, you might get gates with many controls.

这只是意味着经过很多轮之后，你可能会得到具有许多控制的门。

Additionally, at higher control counts, multiple "residue" gates may need to be created per crossing.

此外，在较高的控制计数下，每个交叉可能需要创建多个“残留”门。

However, it is a problem if we decide to do crossing walks during generation mixing, rather than just after it as is the case now, because the current rainbow table only contains r57 gates.

然而，如果我们决定在生成混合期间进行交叉行走，而不是像现在这样在生成混合之后进行交叉行走，则会出现问题，因为当前的彩虹表仅包含 r57 门。

One could make a rainbow table that contains higher-control-count gates, but this risks exponentially increasing the rainbow table in size for the same level of coverage.

人们可以制作一个包含更高控制计数门的彩虹表，但这存在以指数方式增加相同覆盖水平的彩虹表大小的风险。

The easiest solution would be to reduce each 3+ control gate back into a series of two-control gates.

最简单的解决方案是将每个 3+ 控制门减少回一系列两个控制门。

This step simplifies down a series of gates that modify a wire before it gets read.

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

This is primarily done not to do more hiding, but to shrink the program.

这样做主要不是为了进行更多隐藏，而是为了缩小程序。

The argument is that if we did not do this, the attacker could do it themselves anyway to have a smaller object to work with, so we might as well give the same efficiency gain to legitimate users.

争论的焦点是，如果我们不这样做，攻击者无论如何都可以自己做，以获得更小的对象来使用，因此我们不妨为合法用户提供相同的效率增益。

One final thing worth mentioning here is gadgetization swaps .

这里最后值得一提的是小工具交换。

The gadgetization phase, which we will talk about later, includes a "role swapping" mechanism where two wires get their values and their roles swapped at some position in the circuit.

我们稍后将讨论的小工具化阶段包括“角色交换”机制，其中两条线在电路中的某个位置获取其值并交换其角色。

The swaps that affect the output wires are undone at the end in a single step that extracts the right output wire to the right position.

影响输出线的交换在最后一步中被撤消，将正确的输出线提取到正确的位置。

Even though it's done during the gadgetization phase, I still think of it as being a type of mixing.

尽管它是在小工具化阶段完成的，但我仍然认为它是一种混合。

It allows wires to move "vertically", complementing the "horizontal" movement done by the crossing walk phase.

它允许电线“垂直”移动，补充交叉行走阶段所做的“水平”移动。

You can think of the different families of mixing as making "sudoku-like" transformations on the circuit that nicely complement each other:

您可以将不同的混合系列视为在电路上进行“类似数独”的转换，从而很好地相互补充：

To understand the need for this next phase, we should ask the question: what are some data leakages that inserting junk gates, shuffling and mixing are either bad at addressing, or fundamentally cannot address at all?

为了理解下一阶段的需求，我们应该问一个问题：插入垃圾门、洗牌和混合无法解决或根本无法解决的一些数据泄漏是什么？

Here's one simple answer (it's not strictly correct, but for the moment, assume it is): each "wire" in \(C\) , at each point in time, is still instantiated in the obfuscated circuit \(Obf(C)\) somewhere .

这是一个简单的答案（严格来说不是正确的，但目前假设是正确的）： \(C\) 中的每条“线路”在每个时间点，仍然在混淆电路 \(Obf(C)\) 的某处实例化。

If an attacker has the original circuit \(C\) and the obfuscated circuit \(Obf(C)\) , they can run the original circuit many times, see which wires in the obfuscated circuit are perfectly correlated with wires in the original circuit, and use that to determine the mapping from one to the other.

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

Of course, in real-world applications, the attacker does not have access to \(C\) .

当然，在现实应用中，攻击者无权访问 \(C\) 。

But in many real-world applications, they almost do .

但在许多实际应用中，它们几乎都是这样做的。

Almost all of \(C\) is public, the only thing secret is some "embedded secret key" that \(Obf(C)\) is trying to hide.

几乎所有\(C\) 都是公开的，唯一的秘密是\(Obf(C)\) 试图隐藏的一些“嵌入密钥”。

Even if the attacker has no access to \(C\) at all, they can do something like this:

即使攻击者根本无法访问\(C\)，他们也可以执行以下操作：

Adding junk gates does not affect this at all.

添加垃圾门根本不会影响这一点。

Shuffling the gates does not affect this at all.

洗牌门根本不会影响这一点。

Mixing can affect this, in principle.

原则上，混合会影响这一点。

For example, imagine you have a sub-circuit that does:

例如，假设您有一个子电路：

\(x \ {\oplus}{=}\ y \oplus z \\ y\ {\oplus}{=}\ a \lor b \\ z\ {\oplus}{=}\ a \oplus b \\ x \ {\oplus}{=}\ y \oplus z \\ y\ {\oplus}{=}\ a \lor b \\ z\ {\oplus}{=}\ a \oplus b\)

\(x \ {\oplus}{=}\ y \oplus z \\ y\ {\oplus}{=}\ a \lor b \\ z\ {\oplus}{=}\ a \oplus b \\ x \ {\oplus}{=}\ y \oplus z \\ y\ {\oplus}{=}\ a \lor b \\ z\ {\oplus}{=}\ a \oplus b\)

The behavior is exactly the same: \(x\) gets flipped only if \(a\) and \(b\) are both 1.

行为完全相同：仅当 \(a\) 和 \(b\) 均为 1 时，\(x\) 才会翻转。

But in the replacement sub-circuit, the expression \(a \land b\) never gets instantiated .

但在替换子电路中，表达式\(a\land b\)永远不会被实例化。

In principle, this kind of transformation can be done by local mixing.

原则上，这种变换可以通过局部混合来完成。

Even more complex transformations can be done by local mixing.

甚至可以通过局部混合来完成更复杂的转换。

In principle, you could mix enough times that something like this just ends up happening to every wire many times over by random chance.

原则上，您可以混合足够多的次数，这样的事情最终会随机地多次发生在每根电线上。

That was the authors' hope .

这就是作者的希望。

But, so far, mixing has not proved to be good enough.

但是，到目前为止，混合还没有被证明足够好。

There ended up being too many correlations between values in \(C\) and values in the obfuscation that remained.

最终，\(C\) 中的值与保留的混淆中的值之间存在太多相关性。

The authors visualize these correlations through heatmaps :

作者通过热图可视化这些相关性：

Gadgetization emerges as a way to more deterministically make sure that these kinds of correlations do not exist, even before any mixing starts.

小工具化的出现是一种更确定地确保此类相关性不存在的方法，即使在任何混合开始之前也是如此。

We take the problem "each wire in \(C\) must never be explicitly instantiated", and we explicitly solve for it.

我们采取“\(C\) 中的每条线都不能被显式实例化”的问题，并显式地解决它。

We replace each gate in the circuit with a "gadgetized gate".

我们用“小工具门”替换电路中的每个门。

For example, here is the simplest possible gadgetization of an r57 gate:

例如，以下是 r57 门的最简单的小工具化：

In this design, we represent each wire \(w_i\) as two wires, \(s_i\) and \(r_i\) , that satisfy \(w_i = s_i \oplus r_i\) .

在此设计中，我们将每根导线 \(w_i\) 表示为两条导线 \(s_i\) 和 \(r_i\) ，满足 \(w_i = s_i \oplus r_i\) 。

The construction in the above diagram allows us to replicate the desired behavior over representations - flipping the representation of \(w_a\) only if either \(w_b = 1\) or \(w_c = 0\) - without ever explicitly instantiating \(w_a\) , \(w_b\) or \(w_c\) .

上图中的构造允许我们在表示上复制所需的行为 - 仅当 \(w_b = 1\) 或 \(w_c = 0\) 时翻转 \(w_a\) 的表示 - 而无需显式实例化 \(w_a\) 、 \(w_b\) 或 \(w_c\) 。

The construction here borrows ideas from multi-party computation, where the goal is identical: the participants start with a secret-sharing of the inputs and get to a secret-sharing of the outputs, without ever exposing any value in the computation (input, output or intermediate) to any single machine.

这里的构造借鉴了多方计算的思想，其目标是相同的：参与者从输入的秘密共享开始，到输出的秘密共享，而无需将计算中的任何值（输入、输出或中间）暴露给任何单台机器。

The construction here is the simplest two-party case.

这里的构建是最简单的两方案例。

Another source of inspiration is the secure hardware literature, eg.

另一个灵感来源是安全硬件文献，例如。

this work .

这项工作。

In secure hardware design, a common model is the d-probing model : assume the adversary can read up to \(d\) wires, and mathematically guarantee that under this constraint they can learn nothing.

在安全硬件设计中，一个常见的模型是 d 探测模型：假设对手最多可以读取 \(d\) 条电线，并从数学上保证在这种约束下他们什么也学不到。

If we implement this kind of gadget, then we are guaranteed to get no single wire in the gadgetized output representing any specific wire of \(C\) - unless we get really unlucky and the mixing step undoes a gadgetization by sheer blind luck, which is currently very rare and mixing can be optimized to protect against further.

如果我们实现这种小工具，那么我们保证在小工具化的输出中不会得到任何代表 \(C\) 的任何特定线的单线 - 除非我们真的很不幸并且混合步骤完全通过盲目的运气取消了小工具化，这种情况目前非常罕见，并且可以优化混合以防止进一步的情况。

Now let's look at the full pipeline that makes gadgetization possible.

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

(Note: to simplify exposition, this description is mixing the secret-share gadget, which is from an older design, with a gadgetization pipeline that is as-of-today current)

（注意：为了简化说明，此描述将来自旧设计的秘密共享小工具与目前最新的小工具化管道混合在一起）

The gadgetized gates that we discussed above go into the third phase, and they get interspersed with the swaps we mentioned earlier, which switch the role of two wires.

我们上面讨论的小工具门进入第三阶段，它们散布着我们之前提到的交换，交换两条线的角色。

The remaining phases are there to provide the scaffolding the makes the whole pipeline correct:

剩下的阶段是为了提供使整个管道正确的脚手架：

Now, we have removed any direct one-to-one correspondences between wires in \(G\) (the gadgetized output) and wires in the original \(C\) .

现在，我们已经删除了 \(G\) （小工具化输出）中的连线与原始 \(C\) 中的连线之间的任何直接一对一对应关系。

We have even removed correlation : \(a \oplus b\) has zero correlation with \(a\) and with \(b\) - at least, as long as \(a\) and \(b\) are themselves independent with each other, which is approximately true with a high-quality junk-filling phase.

我们甚至删除了相关性：\(a \oplus b\) 与 \(a\) 和 \(b\) 的相关性为零 - 至少，只要 \(a\) 和 \(b\) 本身彼此独立，这对于高质量的垃圾填充阶段来说大致是正确的。

We still have one type of relationship between the pre-gadgetized circuit \(C\) and the gadgetized circuit \(G\) that is discoverable: a linear (or more precisely, affine ) relationship.

我们在预小工具化电路 \(C\) 和可发现的小工具化电路 \(G\) 之间仍然存在一种类型的关系：线性（或更准确地说，仿射）关系。

Each wire \(w_i\) in \(C\) , at some specific position in execution, corresponds to some \(g_j \oplus g_k\) in \(G\) .

\(C\) 中的每条线 \(w_i\) 在执行中的某个特定位置，对应于 \(G\) 中的某个 \(g_j \oplus g_k\) 。

And you can discover all such relationships, even if we expanded the gadgetization so there are eg.

即使我们扩展了小工具化，您也可以发现所有此类关系，例如。

ten masks going into the xor, by using linear algebra attacks .

通过使用线性代数攻击，十个掩码进入异或。

Here is how a linear algebra attack works.

以下是线性代数攻击的工作原理。

Consider \(c_{\{i,w\}}\) , wire \(w\) in the state of \(C\) after executing the first \(i\) gates.

考虑 \(c_{\{i,w\}}\) ，在执行第一个 \(i\) 个门之后，将 \(w\) 连接到 \(C\) 的状态。

Then take \(g_j\) , the state of \(G\) after executing the first \(j\) gates.

然后取 \(g_j\) ，即执行第一个 \(j\) 个门后 \(G\) 的状态。

The goal will be to find linear relationships between \(c_{\{i,w\}}\) and \(g_j\) (mathematically, these are both vectors over \(F_2\) ).

目标是找到 \(c_{\{i,w\}}\) 和 \(g_j\) 之间的线性关系（数学上，它们都是 \(F_2\) 上的向量）。

Do many executions of \(C\) and \(G\) , so you have a vector of \(c_{\{i,w\}}\) values and a matrix of \(G\) states, \(G_j\) .

多次执行 \(C\) 和 \(G\) ，因此您有一个 \(c_{\{i,w\}}\) 值向量和一个 \(G\) 状态矩阵 \(G_j\) 。

Append an extra column of all-ones to \(G_j\) to let us find dependencies that are offset-by-a-constant.

在 \(G_j\) 中附加一个额外的全一列，让我们找到偏移量为常数的依赖项。

Then, use Gaussian elimination (or, at very high dimension, slightly more efficient algorithms based on faster matmul eg.

然后，使用高斯消除（或者，在非常高的维度上，基于更快的 matmul 的稍微更有效的算法，例如

Strassen ) to solve the system of linear equations:

Strassen ）求解线性方程组：

Either this system has no solutions, or it has a solution.

这个系统要么没有解，要么有解。

If it has a solution, then take even more executions of \(C\) and \(G\) , and see for how many of these new executions it correctly predicts \(c_{\{w,i\}}\) .

如果它有解决方案，则执行更多 \(C\) 和 \(G\) ，并查看它正确预测了多少个新执行 \(c_{\{w,i\}}\) 。

If the number is very close to 0.5, then you've probably identified a spurious correlation, an accident.

如果该数字非常接近 0.5，那么您可能发现了虚假相关性，即一次事故。

If the number is significantly above 0.5, then you've discovered at least a partially effective predictor of \(c_{\{w,i\}}\) .

如果该数字明显高于 0.5，那么您至少发现了 \(c_{\{w,i\}}\) 的部分有效预测因子。

For clear linear relationships like the two-value (or any multi-value) xor, it will return a correlation of 1.

对于像二值（或多值）异或这样的清晰线性关系，它将返回相关性 1。

This attack takes far longer than more naive attacks: Gaussian elimination is \(O(N^3)\) , and Strassen-based approaches are \(O(N^{2.8})\) whereas finding perfect correlations between activations can be \(O(N*log(N))\) or even faster.

这种攻击比更简单的攻击花费的时间要长得多：高斯消除是 \(O(N^3)\) ，基于 Strassen 的方法是 \(O(N^{2.8})\) 而找到激活之间的完美相关性可以是 \(O(N*log(N))\) 甚至更快。

But that's still not good enough.

但这还不够好。

And so the solution is to make the gadget represent \(w_i\) nonlinearly .

因此解决方案是让小工具非线性地表示 \(w_i\) 。

Instead of storing wires as \((s_i, r_i)\) satisfying \(w_i = s_i \oplus r_i\) , we store them with a "carrier" wire \(c_i\) satisfying \(w_i = c_i \oplus B_{i1} \oplus B_{i2} \oplus ...\) , where each "band product" \(B_{ij}\) is itself a product of some pseudorandomly generated "band values".

我们不是将电线存储为满足 \(w_i = s_i \oplus r_i\) 的 \((s_i, r_i)\) ，而是用满足 \(w_i = c_i \oplus B_{i1} \oplus B_{i2} \oplus ...\) 的“载体”电线 \(c_i\) 存储它们，其中每个“带积” \(B_{ij}\) 本身就是一些伪随机生成的乘积“带值”。

Instead of the mask being linear, the mask is highly nonlinear.

掩模不是线性的，而是高度非线性的。

When the value of a wire changes, it's always the carrier that changes: an xor to the carrier xors the underlying value.

当线路的值发生变化时，变化的始终是载波：对载波进行异或，对基础值进行异或。

To apply a gate \(w_k\ {\oplus}{=}\ w_i \land w_j\) , the goal is to apply a series of xors to the carrier of the output wire, which sum up to \(w_i \land w_j = c_i \land c_j \oplus c_i \land M_j \oplus M_i \land c_j \oplus M_i \land M_j\) , where \(M_i\) and \(M_j\) are the two band products.

要应用门 \(w_k\ {\oplus}{=}\ w_i \land w_j\) ，目标是将一系列异或应用于输出线的载波，其总和为 \(w_i \land w_j = c_i \land c_j \oplus c_i \land M_j \oplus M_i \land c_j \oplus M_i \land M_j\) ，其中 \(M_i\) 和\(M_j\) 是两个能带的乘积。

However, we want to do this without ever instantiating this product or even any of its four cross-terms.

然而，我们希望在不实例化该产品甚至其四个交叉项中的任何一个的情况下执行此操作。

The solution is a mechanism called Gray folding:

解决方案是一种称为灰色折叠的机制：

Gray folding is very flexible: it can be naturally extended to cover higher-degree monomials or expressions where different terms have a mixture of different degrees.

灰色折叠非常灵活：它可以自然地扩展到覆盖更高阶的单项式或不同项具有不同阶数混合的表达式。

This gadget is now much more complex than the secret-sharing gadget we saw before.

这个小工具现在比我们之前看到的秘密共享小工具复杂得多。

It accomplishes the goal of immunity to exact linear attacks on rows of G, which you can see by comparing heatmaps (this time, heatmaps that check for linear attacks, and not just value-to-value correlations):

它实现了对 G 行免受精确线性攻击的目标，您可以通过比较热图来看到这一点（这次，热图检查线性攻击，而不仅仅是值与值的相关性）：

Left: secretshare14 gadget (the secret share above plus some re-mixing), right: bandproduct92 (the 92-gate nonlinear-band-product gadget)

左：secretshare14 小工具（上面的秘密共享加上一些重新混合），右：bandproduct92（92 门非线性带积小工具）

But as it turns out, even this approach is not perfect: it's still vulnerable to exact linear attacks on the whole trace of G .

但事实证明，即使这种方法也不完美：它仍然容易受到对 G 的整个轨迹的精确线性攻击。

The reason is fundamental: the series of xors applied to the carrier has to ultimately sum up to the actual output value of the gate, and no matter how much you try to put shuffles or other things into those xors, you can solve a system of linear equations to find the exact set of wires that sum up to the output value.

原因是根本性的：应用于载波的一系列异或最终必须总计为门的实际输出值，并且无论您如何尝试将洗牌或其他东西放入这些异或中，您都可以求解线性方程组以找到总计为输出值的精确导线组。

Could you remove this vulnerability too?

您也可以删除这个漏洞吗？

As it turns out, yes, but you have to do some extreme trickery: the value \(w_i\) has to be stored in multiple carriers in a nonlinear way.

事实证明，是的，但你必须采取一些极端的技巧：值 \(w_i\) 必须以非线性方式存储在多个载体中。

One winning equation is \(w_i = c_1(i) \land c_2(i) \oplus c_1(i) \land c_3(i) \oplus c_2(i) \land c_3(i) \oplus c_4(i) \oplus c_5(i)\) .

一个获胜方程是 \(w_i = c_1(i) \land c_2(i) \oplus c_1(i) \land c_3(i) \oplus c_2(i) \land c_3(i) \oplus c_4(i) \oplus c_5(i)\) 。

The evaluation of a gate also has to be done in a way that avoids ever instantiating values any subset of which sum up to \(w_i\) .

门的评估还必须以避免实例化任何子集总和为 \(w_i\) 的值的方式完成。

Instead, we take the whole expression \(C_{\{c,out\}} = encode(gate(decode(C_a), decode(C_b), decode(C_{\{c,in\}})))\) (here each \(C\) stands in for five values), break it up into monomials, and then do Gray-coding-like tricks to apply each monomial to its target.

相反，我们采用整个表达式 \(C_{\{c,out\}} =encode(gate(decode(C_a)，decode(C_b)，decode(C_{\{c，in\}})))\) （这里每个 \(C\) 代表五个值），将其分解为单项式，然后执行类似格雷编码的技巧将每个单项式应用于其目标。

Here is one implementation, which I call nonlinear291 .

这是一种实现，我将其称为非线性291。

It uses 291 gates per gadget representing a single underlying gate.

每个小工具使用 291 个门，代表一个底层门。

The simplest relationship between \(C\) and \(G\) that it does have is a 0.5 correlation between a wire value in \(C\) and an expression of three values in \(G\) .

\(C\) 和 \(G\) 之间最简单的关系是 \(C\) 中的连线值与 \(G\) 中的三个值的表达式之间的 0.5 相关性。

If you want to go full crazy, you can go even further, by stacking these constructions on top of each other.

如果你想彻底疯狂，你可以走得更远，将这些结构堆叠在一起。

Here is a secretshare14 gadget, with each individual gate replaced by a full nonlinear291 .

这是一个 SecretShare14 小工具，每个单独的门都被一个完整的非线性291 替换。

I call this monster behemoth1415 :

我称这个怪物为 behemoth1415 ：

It's not feasible to exhaustively check this, but there is a reasonable argument to believe that it does not have any correlations against weight <= 5 expressions.

详尽地检查这一点是不可行的，但有一个合理的论据相信它与权重 <= 5 表达式没有任何相关性。

Well, okay, if you want to really go full crazy, you can make a nonlinear291 with each individual gate replaced by a nonlinear 291 (some gates have one control so they might be simpler).

好吧，好吧，如果你真的想彻底疯狂，你可以制作一个非线性 291，其中每个单独的门都替换为非线性 291（有些门只有一个控制，因此它们可能更简单）。

This would have a blowup of about eighty thousand gates in \(G\) per gate in \(C\) - a ratio that sounds monstrous, until you remember that garbled circuits replace each gate with a computation including a hash, which is also around tens of thousands of gates, and fully homomorphic encryption can have a blowup in the billions or trillions.

这将导致 \(G\) 中的每个门在 \(C\) 中爆炸大约八万个门 - 这个比率听起来很可怕，直到您记得乱码电路用包含散列的计算替换每个门，这也大约有数万个门，而完全同态加密可能会导致数十亿或数万亿的爆炸。

What does "behemoth80000" get you?

“behemoth80000”会给你带来什么？

There's good reason to conjecture that it has no correlations against weight <= 8 expressions, and no exact match to linear or degree <= 3 expressions in \(G\) .

有充分的理由推测它与权重 <= 8 表达式没有相关性，并且与 \(G\) 中的线性或度 <= 3 表达式没有精确匹配。

If \(G\) is large enough (eg.

如果 \(G\) 足够大（例如

a gigabyte, or even megabytes), this already gets you to the point where the best known algorithms for finding matches to \(C\) (whether a linear attack on the fourth tensor power of \(G\) , or exhaustive search, or learning parity with noise algorithms, or " junta learning ") all take cryptographically long amounts of time.

千兆字节，甚至兆字节），这已经让您达到了这样的地步：寻找与 \(C\) 匹配的最著名的算法（无论是对 \(G\) 四次张量幂的线性攻击，还是穷举搜索，或者使用噪声算法学习奇偶校验，或者“军政府学习”）都需要花费密码学上很长的时间。

However, before we get too excited about behemoth gadget constructions, it's important to keep in mind two facts:

然而，在我们对庞然大物的结构过于兴奋之前，重要的是要记住两个事实：

Gadgetization alone buys you no security against attackers that just pattern-match: they know what kind of gadget corresponds to which underlying gate.

仅小工具化并不能为您提供针对仅模式匹配的攻击者的安全保障：他们知道哪种小工具对应于哪个底层门。

So you have to do serious mixing after gadgetization anyway.

所以无论如何，你必须在小工具化之后进行认真的混合。

The authors of the local mixing proposal are convinced that if they keep improving mixing, then mixing itself should be able to remove exact linear attacks and small-weight correlations.

局部混合提案的作者坚信，如果他们不断改进混合，那么混合本身应该能够消除精确的线性攻击和小权重相关性。

They believe that theoretically, with a good enough mixing pipeline, no gadgetization step should be needed at all.

他们认为，理论上，只要有足够好的混合管道，就根本不需要小工具化步骤。

The main weakness of mixing so far is that it is stochastic, and so empirically it often leaves many correlations and linear attacks not sufficiently removed.

到目前为止，混合的主要弱点是它是随机的，因此根据经验，它经常留下许多相关性和线性攻击没有充分消除。

The rainbow-table-based generation mixing, even with canonicalization and a heavily curated table, is currently only able to reorder very small portions of the circuit at a time.

基于彩虹表的生成混合，即使具有规范化和精心策划的表，目前也只能一次对电路的很小部分进行重新排序。

So it feels like gadgetization and mixing have complementary roles:

所以感觉小工具化和混合具有互补的作用：

That said, there is also quite a bit of overlap in their potential roles, and so a better version of one takes some pressure off the other.

也就是说，他们的潜在角色也有相当多的重叠，因此一个更好的版本可以减轻另一个的压力。

This is one of the major axes of uncertainty in the project: exactly how much of the task is done by gadgets, and how much by mixing?

这是该项目中不确定性的主要轴之一：到底有多少任务是由小工具完成的，又有多少是通过混合完成的？

The goal is to ensure a lack of detectable relationships between executions of the obfuscated circuit and executions of the original circuit.

目标是确保混淆电路的执行与原始电路的执行之间缺乏可检测的关系。

Let's re-summarize the specific attacks:

我们重新总结一下具体的攻击：

Theoretically optimal matrix multiplication algorithms are at \(O(N^{\approx 2.37})\) , but even at the very large sizes we're working at, anything more asymptotically-efficient than Strassen is not efficient in practice.

理论上最优的矩阵乘法算法为 \(O(N^{\approx 2.37})\) ，但即使在我们正在处理的非常大的尺寸下，任何比 Strassen 更渐近有效的算法在实践中都是无效的。

This once again shows the natural complementarity between gadgetization and mixing.

这再次显示了小工具化和混合之间的天然互补性。

An effective task for gadgetization is to convert circuits into representations that avoid all of these attackers.

小工具化的一项有效任务是将电路转换为能够避免所有这些攻击者的表示形式。

An effective task for mixing, in addition to doing even more smudging stochastically, is to force attackers attempting any of the above attacks to actually search through all of \(Obf(C)\) and not just an identifiable subset of it to target each individual gate.

除了随机地进行更多的涂抹之外，混合的一个有效任务是迫使尝试上述任何攻击的攻击者实际上搜索所有 \(Obf(C)\) 而不仅仅是它的可识别子集来瞄准每个单独的门。

One interesting fact to notice here is that we are naturally in a "big key cryptography" regime.

这里需要注意的一个有趣的事实是，我们自然地处于“大密钥密码学”体制中。

With "normal" cryptography, each individual cryptographic object stands by itself: to attack an FHE ciphertext, you can attack any individual value at any point in the execution of a circuit.

使用“普通”加密技术，每个单独的加密对象都是独立的：要攻击 FHE 密文，您可以在电路执行中的任何点攻击任何单独的值。

Here, each gate in the circuit is part of the noise protecting every other gate .

这里，电路中的每个门都是保护每个其他门的噪声的一部分。

If we are really conservative on parameters - say, the obfuscated circuit's trace is a terabyte ( \(2^{43}\) bits) in size (which should take a few minutes to run on consumer hardware) - then even a linear attack is not fatal.

如果我们对参数真的很保守 - 例如，混淆电路的跟踪大小为太字节（ \(2^{43}\) 位）（在消费类硬件上运行需要几分钟） - 那么即使是线性攻击也不是致命的。

A Gaussian elimination requires \(2^{129}\) steps, at best optimizable to perhaps \(2^{\approx 122}\) with Strassen, which is within bounds of what is considered cryptographically secure (not to mention that you would need \(\approx 10^{25}\) bytes to store the matrix)!

高斯消除需要 \(2^{129}\) 个步骤，最好使用 Strassen 优化到 \(2^{\approx 122}\)，这在被认为是加密安全的范围内（更不用说你需要 \(\approx 10^{25}\) 字节来存储矩阵）！

If we are okay with degree-2 attackers, then (assuming perfect mixing), megabyte-sized obfuscated circuits become sufficient - though in practice, we will want lots of headroom to account for imperfections in mixing.

如果我们可以接受 2 级攻击者，那么（假设完美混合），兆字节大小的混淆电路就足够了 - 尽管在实践中，我们需要大量的空间来解决混合中的缺陷。

There is one other attack worth worrying about: random bit flip attacks .

还有另一种攻击值得担心：随机位翻转攻击。

Here, the goal is not to learn anything about the circuit directly.

这里的目标不是直接学习有关电路的任何内容。

Instead, it's to randomly flip the evaluations of wires inside of the circuit during an execution, without knowing what you're flipping, with the goal of extracting outputs that you would otherwise not be able to extract.

相反，它是在执行过程中随机翻转电路内部电线的评估，而不知道要翻转什么，目的是提取原本无法提取的输出。

Here is one example.

这是一个例子。

Consider a program \(P(C, \pi)\) that takes two inputs: an FHE ciphertext \(C\) , and a STARK \(\pi\) .

考虑一个程序 \(P(C, \pi)\)，它接受两个输入：一个 FHE 密文 \(C\) 和一个 STARK \(\pi\) 。

This is the classic "obfuscation bootstrapping" program: given an obfuscation that can handle the single specific task of "verify a STARK and decrypt FHE", it lets you obfuscate arbitrarily complex circuits, with FHE * STARK overhead - still very high, but within reach of viability.

这是经典的“混淆引导”程序：给定一个可以处理“验证 STARK 并解密 FHE”的单一特定任务的混淆，它可以让您混淆任意复杂的电路，FHE * STARK 开销 - 仍然非常高，但在可行性范围内。

Now, suppose you have a local mixing obfuscation that uses the mechanisms described above, including very strong gadgetization and good mixing.

现在，假设您有一个使用上述机制的本地混合混淆，包括非常强大的小工具化和良好的混合。

It's still vulnerable to the following attack.

它仍然容易受到以下攻击。

They then run the obfuscated \(Obf(P)\) many times.

然后他们多次运行混淆后的 \(Obf(P)\)。

During each execution, they keep randomly flipping a bit some time during the execution.

在每次执行期间，它们都会在执行过程中的某个时间保持随机翻转。

Even though there is no observable relationship between \(Obf(P)\) and \(P\) , there is still the fact that on average, flipping a bit in the execution of \(Obf(P)\) has a \(\ge 50\%\) chance of flipping one bit in \(P\) .

尽管 \(Obf(P)\) 和 \(P\) 之间没有可观察到的关系，但仍然存在这样的事实：平均而言，在执行 \(Obf(P)\) 时翻转一位有 \(\ge 50\%\) 机会翻转 \(P\) 中的一位。

The attacker's goal: just keep doing this until the bit they flip is the "was the STARK correct?" bit.

攻击者的目标：继续这样做，直到他们翻转的部分是“STARK 正确吗？”少量。

After a number of tries roughly equal to the size of the circuit, they succeed, and out pops the secret key.

经过大约相当于电路大小的尝试次数后，他们成功了，并弹出了密钥。

There are actually many possible bit flips in the circuit that would help the attacker.

实际上，电路中有许多可能的位翻转可以帮助攻击者。

For example, if there is some bit that flips the FHE noise to zero or otherwise turns off the rounding during decryption, they could learn an exact relation \(s * C\) , and out of that recover the embedded secret \(s\) .

例如，如果有某个位将 FHE 噪声翻转为零或以其他方式在解密期间关闭舍入，则他们可以学习精确的关系 \(s * C\) ，并从中恢复嵌入的秘密 \(s\) 。

For this reason, it's worth addressing this systematically.

因此，值得系统地解决这个问题。

What we've seen so far seems to suggest two ways to solve this problem: at mixing layer and at gadgetization layer :

到目前为止，我们所看到的似乎提出了两种解决此问题的方法：在混合层和小工具化层：

In the next section, we will also see a third line of defense, at a layer wrapping the obfuscation scheme we have built so far.

在下一节中，我们还将看到第三道防线，即包裹我们迄今为止构建的混淆方案的一层。

All of this work is early stage and unproven, and the local mixing authors acknowledge this.

所有这些工作都处于早期阶段且未经证实，当地的混音作者也承认这一点。

And so right now, they are focusing on using the above pipeline for one specific narrow use case: obfuscating random circuits .

因此，现在，他们专注于将上述管道用于一个特定的狭窄用例：混淆随机电路。

There are two already-known concrete uses for this.

其有两个已知的具体用途。

First of all, obfuscation for random circuits immediately implies public key encryption (assuming the obfuscation scheme meets the RIO and SCP properties, which we will describe later).

首先，随机电路的混淆立即意味着公钥加密（假设混淆方案满足 RIO 和 SCP 属性，我们将在稍后描述）。

Generate a reversible random circuit \(R\) , with width \(2w\) .

生成一个可逆随机电路 \(R\) ，宽度为 \(2w\) 。

Keep \(R\) for yourself, and publish \(Obf(R)\) (the obfuscation should use sandwiching, so it can only be used to compute \(R\) forwards and not backwards).

自己保留\(R\)，并发布\(Obf(R)\)（混淆应使用三明治，因此只能用于向前计算\(R\)，而不能用于向后计算\(R\)）。

Anyone can encrypt a width \(w\) message \(m\) by generating randomness \(r\) and computing \(c = Obf(R)(m, r)\) .

任何人都可以通过生成随机性 \(r\) 和计算 \(c = Obf(R)(m, r)\) 来加密宽度 \(w\) 消息 \(m\) 。

Because \(R\) itself is reversible, given such a \(c\) you can decrypt it via \(R^{-1}(c )[{:}w]\) .

因为 \(R\) 本身是可逆的，给定这样的 \(c\) 你可以通过 \(R^{-1}(c )[{:}w]\) 解密它。

The reason to add a random pad when encrypting (and trim the pad after decrypting) is to avoid situations where an attacker can decrypt encrypted messages by encrypting all possible options and seeing which one matches.

在加密时添加随机填充（并在解密后修剪填充）的原因是为了避免攻击者通过加密所有可能的选项并查看哪个选项匹配来解密加密消息的情况。

This alone is very valuable: it gives us a totally different family of plausibly quantum-resistant public-key encryption algorithms .

仅这一点就非常有价值：它为我们提供了一个完全不同的看似抗量子的公钥加密算法系列。

In an era when quantum computers are about to take away RSA and elliptic curves, and there are serious (though so far unsuccessful) attempts at even attacking lattices , having a new and totally-different form of cryptography to fall back on is a valuable insurance policy.

在量子计算机即将取代 RSA 和椭圆曲线的时代，人们甚至认真地尝试过攻击晶格（尽管迄今为止尚未成功），拥有一种新的、完全不同形式的密码学可供依靠是一项有价值的保险政策。

Because this style of public-key encryption only uses classical symmetric-cryptography-style operations during decryption, it has extremely impressive performance properties:

由于这种公钥加密方式在解密过程中仅使用经典的对称加密方式操作，因此它具有极其令人印象深刻的性能特性：

But the authors also have a second use case in mind: they have found a way to (sort of) provably construct indistinguishability obfuscation (iO) of arbitrary circuits from obfuscation of random circuits .

但作者还想到了第二个用例：他们找到了一种（某种程度上）可证明地构造任意电路的不可区分性混淆（iO）和随机电路的混淆的方法。

The authors have a proof that this achieves the formal definition of iO: if two reversible circuits \(A\) and \(B\) have the same behavior on all inputs, given \(Obf(A)\) and \(Obf(B)\) you should not be able to tell which is which.

作者有一个证明，证明这实现了 iO 的正式定义：如果两个可逆电路 \(A\) 和 \(B\) 在所有输入上具有相同的行为，给定 \(Obf(A)\) 和 \(Obf(B)\)，你应该无法区分哪个是哪个。

To extend this to irreversible circuits, one need only convert the irreversible to reversible using the hardened Toffoli construction, which does the conversion in a way that structurally guarantees that it introduces no new data leakage.

要将其扩展到不可逆电路，只需使用强化的 Toffoli 结构将不可逆电路转换为可逆电路，该结构以一种在结构上保证不会引入新的数据泄漏的方式进行转换。

Here, the methodology becomes more recognizably similar to the other strands of obfuscation research: there is a core assumption that they attempt to minimize, and then a complex and high-overhead protocol built on top to make the whole thing "provable".

在这里，该方法变得更加类似于混淆研究的其他方面：有一个核心假设，他们试图最小化，然后在其之上构建一个复杂且高开销的协议，以使整个事情“可证明”。

The main difference from most other cryptography is that here, they are not reducing to well-understood assumptions many people have worked with, rather they are simultaneously designing a new protocol and a new assumption that it's based on.

与大多数其他密码学的主要区别在于，它们并没有简化为许多人都使用过的易于理解的假设，而是同时设计一个新协议和它所基于的新假设。

It's still worthwhile, because the new assumption is considerably "smaller" and easier to analyze than just saying "we assert this whole protocol is secure", but this is a downside inherent to doing pioneering work with a wholly new family of constructions.

这仍然是值得的，因为新的假设比仅仅说“我们断言整个协议是安全的”要“小得多”并且更容易分析，但这是使用全新的结构家族进行开创性工作所固有的缺点。

More heuristically, notice that this pipeline opens up a third avenue of defense to random bit flip attacks : any bit you flip will be somewhere in the middle of an obfuscation, and so it will likely propagate into a lot of junk.

更具启发性的是，请注意，该管道为随机位翻转攻击开辟了第三条防御途径：您翻转的任何位都将位于混淆中间的某个位置，因此它可能会传播到大量垃圾中。

The last step in the above pipeline, replacing \(head\ |\ tail\) with an obfuscation of itself, ends up essential here: if that step were not there, then if your bit flip lands right after the last gate of a \(\Gamma\) , you would actually have an effect equivalent to flipping a gate in \(C\) .

上述管道中的最后一步，将 \(head\ |\ tail\) 替换为自身的混淆，在这里最终至关重要：如果该步骤不存在，那么如果您的位翻转正好落在 \(\Gamma\) 的最后一个门之后，那么实际上会产生相当于翻转 \(C\) 中的门的效果。

But with that step in there, any bit flip you make ends up deep inside of a sub-obfuscation.

但随着这一步的进行，你所做的任何一点翻转最终都会陷入子混淆的深处。

The same machinery that was constructed to protect against distingushing attacks to ensure the iO property also protects against bit flip attacks.

为防止识别攻击而构建的相同机制，以确保 iO 属性也能防止位翻转攻击。

Compared to basically all cryptography that I've written about so far, the epistemology of why local mixing obfuscation might be secure is completely alien.

与我到目前为止所写的基本上所有密码学相比，为什么本地混合混淆可能是安全的认识论是完全陌生的。

In most cryptography, you try to create mathematical proofs that reduce the security of a protocol to a well-understood math problem - "if you can break this encryption algorithm, then you can factor a semiprime \(N\) into its two factors \(p*q\) ".

在大多数密码学中，您尝试创建数学证明，将协议的安全性降低为易于理解的数学问题 - “如果您可以破解此加密算法，那么您可以将半素数\(N\)分解为其两个因子\(p*q\)”。

The design here is not like that at all.

这里的设计根本不是那样的。

There is an outer wrapping layer that sort of does this at the end, but at every layer below that it's much more heuristic, combining together a grab bag of ideas that we think hide structure, together with some mathematical reasoning about specific properties that we care about avoiding.

最后有一个外包装层可以做到这一点，但在下面的每一层，它都更具启发性，将我们认为隐藏结构的想法结合在一起，以及一些关于我们关心避免的特定属性的数学推理。

The only other tradition in cryptography that is like this is symmetric cryptography, which is behind symmetric encryption algorithms and hash functions.

密码学中唯一与此类似的传统是对称密码学，它支持对称加密算法和哈希函数。

The closest second is secure hardware design , which adopts very similar principles, though it tends to focus on linear attacks less because, well, you can't multiply a physical circuit by a matrix the same way you can a virtual one.

最接近的第二个是安全硬件设计，它采用非常相似的原理，尽管它往往较少关注线性攻击，因为，你不能像虚拟电路那样将物理电路乘以矩阵。

Symmetric cryptography has developed a grab bag of tricks to use, and attacks to watch out for.

对称密码学开发了一系列可供使用的技巧和需要警惕的攻击。

For example:

例如：

But despite having what might be viewed as a lower level of rigor, many cryptographers think that hash-based cryptography is the one type of cryptography that will survive if all other cryptography gets destroyed by advances in mathematics.

但是，尽管其严格性可能被认为较低，但许多密码学家认为，如果所有其他密码学都被数学的进步摧毁，基于哈希的密码学是一种能够幸存的密码学类型。

The high-level reason why is: hashes have no structure , they're intentional chaos .

高层的原因是：散列没有结构，它们是故意的混乱。

It's much easier to believe that something intended to have no structure will continue to have no structure, than to believe that something intended to have one or two types of structure will not have some other form of structure discovered later that enables attacks.

相信本来没有结构的东西将继续没有结构，比相信本来有一种或两种类型的结构的东西不会有后来发现的能够进行攻击的其他形式的结构要容易得多。

The way that the authors of local mixing see it, they are trying to make that tradition work: to obfuscate circuits through a series of steps that destroy all structure, except by being functionality-preserving.

在局部混合的作者看来，他们正试图让这一传统发挥作用：通过一系列破坏所有结构的步骤来混淆电路，除了保留功能之外。

But there is also a different way to see the primitive being constructed here, which actually views it as an attempt to introduce a new member to the "pantheon" of cryptographic gadgets that we use as building blocks, along with structures like lattices and elliptic curves.

但还有一种不同的方式来看待这里构建的原语，它实际上将其视为向我们用作构建块的加密小工具的“万神殿”引入新成员的尝试，以及晶格和椭圆曲线等结构。

Roughly, you can see the correspondence like this:

粗略地，你可以看到这样的对应关系：

To me, this is the most impressive aspect of this whole project.

对我来说，这是整个项目最令人印象深刻的方面。

This is not just a construction aimed at achieving a specific goal.

这不仅仅是为了实现特定目标而进行的建设。

This is a serious attempt at actually inventing a new base cryptographic primitive - and, conveniently, one whose most "natural" functionality is exactly the functionality that we do not yet have: obfuscation.

这是一次认真的尝试，旨在实际发明一种新的基本加密原语 - 而且，方便的是，其最“自然”的功能正是我们尚未拥有的功能：混淆。

But this ambition is also the reason why it's appropriate to make a warning.

但这种野心也是适当发出警告的原因。

Typically, it takes decades for new cryptographic primitives to mature.

通常，新的密码原语需要几十年的时间才能成熟。

There is a whole pipeline that needs to happen, of searching for and ruling out fatal attacks that would kill the whole program, searching for non-fatal but still serious attacks, learning the tricks that get around those attacks, and refining everything to the point where it stabilizes.

需要进行一整套流程，搜索并排除会杀死整个程序的致命攻击，搜索非致命但仍然严重的攻击，学习绕过这些攻击的技巧，并将一切改进到稳定的程度。

This is also why the authors are focusing short-term on a less ambitious target: obfuscation of random circuits.

这也是为什么作者将短期重点放在一个不太雄心勃勃的目标上：随机电路的混淆。

Fortunately, as we've seen, even obfuscation of random circuits is very meaningful: if you can achieve it, then you have a new form of public key cryptography, and you even get general-purpose obfuscation, though possibly with higher overhead than necessary (each gate in \(C\) gets replaced with a full obfuscated circuit, so we're back to terabytes).

幸运的是，正如我们所见，即使是随机电路的混淆也非常有意义：如果你能实现它，那么你就拥有了一种新形式的公钥加密，甚至可以得到通用的混淆，尽管开销可能比必要的更高（\(C\) 中的每个门都被完整的混淆电路取代，所以我们又回到了 TB 级）。

One major hope here is that with AI-accelerated research, we can greatly accelerate this whole pipeline .

这里的一个主要希望是，通过人工智能加速的研究，我们可以大大加速整个流程。

Speed-running the cryptanalysis and verification that would before take decades could be done within a few years, so inventing new cryptographic building blocks might become a much more viable idea in general.

以前需要数十年才能完成的密码分析和验证的快速运行现在可以在几年内完成，因此发明新的密码构建块可能会成为一个更可行的想法。

Obfuscation is the final frontier of cryptography: any other primitive can be built from obfuscation (plus one-way functions), and there are many protocols that are most naturally expressed as obfuscated circuits.

混淆是密码学的最后前沿：任何其他原语都可以通过混淆（加上单向函数）构建，并且有许多协议最自然地表达为混淆电路。

Local mixing is potentially not only much more efficient than lattice-based obfuscation (even diamond iO), but it even has a route to be competitive in runtime with FHE protocols.

局部混合不仅可能比基于格的混淆（甚至 Diamond iO）更有效，而且它甚至有办法在运行时与 FHE 协议竞争。

Additionally, because it doesn't build on a tower of already-known building blocks, and instead is a much more "start-from-fundamentals" project, it is much easier for cryptographers without decades of experience to come in and contribute.

此外，由于它不是建立在已知构建块的塔上，而是一个更加“从基础开始”的项目，因此对于没有数十年经验的密码学家来说，加入并做出贡献要容易得多。

So I am very excited that this totally different, new and unproven and somewhat alien thread of cryptographic research is happening.

因此，我很高兴看到这种完全不同的、全新的、未经证实的、有些陌生的密码学研究线索正在发生。