Obfuscation: building the final boss of cryptography (Part I)

Special thanks to Sora Suegami, Janmajaya Mall, Aayush Jain and Fun Killer for feedback and review.

特别感谢 Sora Suegami、Janmajaya Mall、Aayush Jain 和 Fun Killer 的反馈和审查。

The most powerful primitive that has been conceived in cryptography is obfuscation .

密码学中最强大的原语是混淆。

Obfuscation lets you convert a program \(P\) into an "encrypted program" \(Obf(P)\) such that you can run \(Obf(P)\) on cleartext inputs and get the same cleartext outputs that \(P\) gives you, but the internal workings of \(P\) are hidden.

混淆可以让您将程序 \(P\) 转换为“加密程序”\(Obf(P)\)，这样您就可以在明文输入上运行 \(Obf(P)\) 并获得与 \(P\) 提供的相同的明文输出，但 \(P\) 的内部工作原理是隐藏的。

The precise formalism typically used, indistinguishability obfuscation (iO), says that if you are given obfuscations of two different programs that have the same functionality, you can't tell which is which.

通常使用的精确形式主义，不可区分混淆（iO），表示如果给你两个具有相同功能的不同程序进行混淆，你将无法区分哪个是哪个。

Effectively, it's hiding the code, not the data.

实际上，它隐藏的是代码，而不是数据。

Obfuscation is powerful because it comes very close to the theoretical ideal of a universal "trustless trusted third party":

混淆之所以强大，是因为它非常接近普遍的“不信任的可信第三方”的理论理想：

Cryptography protocols are often described by first imagining a protocol that relies on a trusted third party who sees everyone's messages and responds honestly, and then figuring out some way to do the same thing without the trust.

加密协议通常是这样描述的：首先想象一个协议依赖于一个可信的第三方，该第三方可以看到每个人的消息并诚实地响应，然后找出某种方法在没有信任的情况下做同样的事情。

Obfuscation (technically, obfuscation plus hashes) lets you make a simulated trusted third party for basically any protocol , so it can replace both of the above and much much more.

混淆（从技术上讲，混淆加哈希）可以让您为基本上任何协议创建一个模拟的可信第三方，因此它可以取代上述两者以及更多。

There is only one major exception: an obfuscated program can't prevent itself from being copied, so it can't do "stateful" things like money - and that's exactly the gap that blockchains are well-placed to fill.

只有一个主要的例外：混淆的程序无法防止自身被复制，因此它无法执行“有状态”的事情，例如金钱 - 而这正是区块链可以很好地填补的空白。

And so if you have obfuscation and a blockchain, you can do some pretty magical things.

因此，如果你有混淆和区块链，你就可以做一些非常神奇的事情。

Like, say, a secure, private and collusion-resistant voting system that has almost no trust assumption at all - no M-of-N threshold committee required.

比如说，一个安全、私密且抗共谋的投票系统，几乎没有任何信任假设——不需要 M-of-N 阈值委员会。

Or basically anything from this list from 2014 , without any M-of-N trust assumption.

或者基本上是 2014 年此列表中的任何内容，没有任何 M-of-N 信任假设。

A fairly general-purpose way to combine obfuscation and blockchains to make something very close to a "trustless trusted third party"

一种相当通用的方法，将混淆和区块链结合起来，使之非常接近“不可信的可信第三方”

So what's the catch?

那么有什么问题呢？

Well, it turns out that making a secure form of obfuscation is really really hard .

好吧，事实证明，制作一种安全的混淆形式确实非常困难。

There has been a decades-long tradition of insecure obfuscation: people shuffling around the logic in compiled programs to make it harder to see what's going on - admittedly, often to prevent users from modifying proprietary programs like games.

不安全的混淆已经存在了数十年的传统：人们在编译的程序中修改逻辑，让人们更难看出正在发生的事情——诚然，通常是为了防止用户修改游戏等专有程序。

This is the equivalent of things like the Caesar cipher for encryption - and, like Caesar-style ciphers, it regularly gets broken.

这相当于用于加密的凯撒密码——而且，像凯撒式密码一样，它经常被破解。

As a result, there has also been a decades-long tradition of trying to create an obfuscation protocol that we can mathematically prove is secure.

因此，数十年来一直试图创建一种我们可以在数学上证明安全的混淆协议。

But almost from the beginning, this ran into a problem.

但几乎从一开始，这就遇到了问题。

In 2001, we got a famous result that creating an ideal form of obfuscation - obfuscate \(P\) in such a way that running \(Obf(P)\) reveals nothing beyond what you can learn by querying an API that gives \(P(x)\) for any user-supplied \(x\) - is impossible.

2001 年，我们得到了一个著名的结果：创建一种理想的混淆形式 - 以运行 \(Obf(P)\) 的方式混淆 \(P\)，除了通过查询为任何用户提供的 \(x\) 提供 \(P(x)\) 的 API 可以了解到的内容之外，什么也没有透露 - 是不可能的。

The core idea is that a code instantiation of \(P\) always reveals at least something beyond its outputs to user-supplied inputs: at the very least, you can learn things by applying \(P\) to its own code .

核心思想是，\(P\) 的代码实例化至少总是会向用户提供的输入揭示超出其输出的内容：至少，您可以通过将 \(P\) 应用于其自己的代码来学习一些东西。

From that point, researchers shifted to trying to prove the second-best target: indistinguishability obfuscation (iO).

从那时起，研究人员开始尝试证明第二好的目标：不可区分性混淆（iO）。

This has been a twenty-year project, with many failed attempts, many constructions of protocols that build on top of an ingredient that does not yet exist , many people trying to build that ingredient, failed attempts of that , and so on.

这是一个长达二十年的项目，有许多失败的尝试，许多协议的构建建立在尚不存在的成分之上，许多人试图构建该成分，但失败的尝试等等。

But in the last few years, we finally have some good news: we know how to achieve iO under reasonable security assumptions.

但在过去的几年里，我们终于有了一些好消息：我们知道如何在合理的安全假设下实现 iO。

But within the good news, there is bad news: the run time is literally galactic .

但在好消息中，也有坏消息：运行时间简直是银河般的。

It's technically polynomial, but it involves stacking many layers of "take one thing that's vaguely like fully homomorphic encryption, now put the circuit for evaluating that into another thing that's vaguely like fully homomorphic encryption, run that in plain old regular fully homomorphic encryption once for each bit generating an intermediate multi-megabyte value, and oh yeah, did I mention that you have to put that whole thing into another thing that's vaguely like fully homomorphic encryption, and then run all that once for each bit in the input?" As a result, runtimes for these "sort of provably-secure iO schemes" are somewhere over λ 10 (where λ is the "security parameter", ie.

从技术上讲，它是多项式，但它涉及堆叠多层“采用一个模糊地像完全同态加密的东西，现在将用于评估它的电路放入另一个模糊地像完全同态加密的东西中，在普通的旧常规完全同态加密中为每个位运行一次，生成中间多兆字节值，哦，是的，我是否提到过你必须将整个东西放入另一个模糊地像完全同态加密的东西中，然后运行一次对于输入中的每一位？”因此，这些“某种可证明安全的 iO 方案”的运行时间超过 λ 10（其中 λ 是“安全参数”，即

the logarithm of how long it takes to break the scheme; it's standard to say λ = 100 or 120)

破解该计划所需时间的对数；标准说法是 λ = 100 或 120)

There are two hopeful stories that you can tell here.

您可以在这里讲述两个充满希望的故事。

One is that this is similar to where SNARKs were in 2010, and now that we know it's possible, smart people (and bots) will start coming up with clever workarounds to each bottleneck, and chopping off orders of magnitude from the runtime one after the other, and eventually we'll get to something that "only" takes a day on a heavy GPU to run (that may still sound prohibitive, but it's actually enough for many interesting applications).

一是这与 2010 年 SNARK 的情况类似，现在我们知道这是可能的，聪明的人（和机器人）将开始针对每个瓶颈提出巧妙的解决方法，并逐个将运行时间削减几个数量级，最终我们将得到“只”需要在重型 GPU 上运行一天的东西（这可能听起来仍然令人望而却步，但实际上对于许多有趣的应用程序来说已经足够了）。

Another is that we will see more work on a different strategy toward the same goal: getting much better at developing new cryptographic assumptions , and getting better at telling which new assumptions are likely to be actually safe.

另一个是，我们将看到更多针对同一目标的不同策略的工作：更好地开发新的加密假设，并更好地判断哪些新假设可能实际上是安全的。

If you add in the more heuristic approaches, there are roughly three (not-yet-dead) families of obfuscation protocols so far, and you can place them on a "tradeoff frontier" of efficiency vs bravery on security assumptions:

如果添加更多启发式方法，到目前为止大约有三个（尚未消亡）混淆协议系列，您可以将它们置于安全假设的效率与勇敢的“权衡边界”上：

This post will describe in detail the most galactic, but also the most rigorous, family so far: the one that's in blue in the diagram above.

这篇文章将详细描述迄今为止最银河，但也是最严格的家庭：上图中蓝色的家庭。

Just a warning: there will be a lot of math .

只是警告：会有很多数学知识。

Obfuscation is hard because it basically requires stacking almost every primitive that cryptographers have invented in the past twenty years, except for the primitives that you already know about if you're a blockchain developer, such as SNARKs and STARKs .

混淆很困难，因为它基本上需要堆叠密码学家在过去二十年中发明的几乎所有原语，除了您作为区块链开发人员已经了解的原语，例如 SNARKs 和 STARKs 。

The underlying math will also be different: whereas SNARKs and STARKs tend to have a lot of polynomials, hashes and elliptic curves, obfuscation will have a lot of lattices, vectors and matrices.

底层数学也将有所不同：SNARK 和 STARK 往往有大量多项式、散列和椭圆曲线，而混淆将有大量格子、向量和矩阵。

The "reasonably provably secure" obfuscation protocols that are built today are built on top of a decade-old tower of constructions: the AJ15 / BV15 / LPST15 / LPST16 lineage.

今天构建的“合理证明安全”的混淆协议建立在十年前的结构塔之上：AJ15 / BV15 / LPST15 / LPST16 谱系。

AJ15 and BV15 are two roughly simultaneous papers that both discovered roughly the same way to build obfuscation on top of a primitive called functional encryption : an "authority" publishes keys tied to a function \(F\) , and once those keys exist, anyone with the encryption key can encrypt \(x%\) in such a way that anyone with the decryption key can recover \(F(x)\) .

AJ15 和 BV15 是两篇大致同时发生的论文，它们都发现了在称为函数式加密的原语之上构建混淆的大致相同的方法：“权威”发布与函数 \(F\) 相关的密钥，一旦这些密钥存在，任何拥有加密密钥的人都可以加密 \(x%\)，这样任何拥有解密密钥的人都可以恢复 \(F(x)\) 。

LPST15 came up with something similar.

LPST15 也提出了类似的想法。

But the functional encryption required needed to have very strong properties which were not yet available.

但功能性加密需要具有非常强大的属性，但目前尚不可用。

Fortunately, a year later, LPST16 discovered a way to build obfuscation on top of something similar, sublinear compact randomized encoding , and then built it on top of an already-known "succinct-but-not-compact" functional encryption scheme plus a new primitive called XiO - obfuscation that is only slightly smaller in size than publishing a table of the outputs of the function on all possible inputs.

幸运的是，一年后，LPST16 发现了一种在类似的亚线性紧凑随机编码之上构建混淆的方法，然后将其构建在已知的“简洁但不紧凑”函数加密方案之上，加上一个名为 XiO 的新原语 - 混淆，其大小仅比在所有可能的输入上发布函数输出表略小。

The bulk of the work since then has been figuring out ways to actually implement XiO (though some protocols take other routes, eg.

从那时起，大部分工作一直在寻找实际实现 XiO 的方法（尽管有些协议采用其他路线，例如

JLS20 ).

JLS20）。

There are several ways to build an obfuscation protocol on top of succinct FE and XiO, and they are all roughly equal in their high-level principles and their properties.

有多种方法可以在简洁的 FE 和 XiO 之上构建混淆协议，并且它们在高级原理和属性方面都大致相同。

So I will stick to a simplified version of the LPST15 design.

所以我将坚持使用 LPST15 设计的简化版本。

Note that in this post, we will often use "function" and "circuit" interchangeably.

请注意，在这篇文章中，我们经常互换使用“函数”和“电路”。

A circuit is a set of AND, OR, NOT, etc gates with wires linking them that can be used to evaluate a function.

电路是一组“与”、“或”、“非”等门，并用电线将它们连接起来，可用于评估函数。

To get a better intuition of circuits, I recommend this post explaining garbled circuits (a primitive that we will need later anyway).

为了更好地了解电路，我推荐这篇文章解释乱码电路（无论如何我们稍后都会需要这个原语）。

First, let us define succinct FE and XiO, so we understand the properties of these gadgets.

首先，让我们定义简洁的 FE 和 XiO，以便我们了解这些小工具的属性。

Authority generates circuit-independent public parameters, and circuit-specific decryption keys for a publicly-known function with a single-bit output with circuit \(C\) .

权威机构为具有电路 \(C\) 的单位输出的公众已知函数生成电路无关的公共参数和电路特定的解密密钥。

Encryptor can use the encryption keys to encrypt \(x\) .

加密器可以使用加密密钥来加密 \(x\) 。

The runtime of this step does not increase (or increases only slightly) with the circuit size of \(C\) , though it does scale linearly with input length.

此步骤的运行时间不会随着 \(C\) 的电路大小而增加（或仅略微增加），尽管它确实随输入长度线性缩放。

Decryptor can use the decryption keys to learn \(C(x)\) and nothing else about \(x\) .

解密器可以使用解密密钥来学习 \(C(x)\) 而无需了解 \(x\) 的其他内容。

The runtime of this step does scale with the circuit size of \(C\) .

此步骤的运行时间确实与\(C\) 的电路大小成比例。

In other words: someone does a trusted setup , I encrypt \(x\) , you can decrypt \(C(x)\) (different from fully homomorphic encryption: in FHE, anyone who can decrypt \(C(x)\) can also decrypt \(x\) or any other function of \(x\) )

换句话说：有人进行了可信设置，我加密 \(x\) ，你可以解密 \(C(x)\) （与完全同态加密不同：在 FHE 中，任何可以解密 \(C(x)\) 的人也可以解密 \(x\) 或 \(x\) 的任何其他函数）

Functional encryption is not on its own sufficient for obfuscation, because (i) it doesn't hide the function, and (ii) each published encryption is bound to one input and can only decrypt the function evaluated on that one input.

函数加密本身不足以进行混淆，因为 (i) 它不会隐藏函数，并且 (ii) 每个已发布的加密都绑定到一个输入，并且只能解密在该输入上评估的函数。

But it gets you a lot of the way there.

但它可以让你走很多路。

Note that the more common definition of succinct FE requires the FE to tolerate high circuit size , not high circuit depth .

请注意，更常见的简洁 FE 定义要求 FE 能够承受高电路尺寸，而不是高电路深度。

In our usage, however, we do need to tolerate high depth.

然而，在我们的使用中，我们确实需要容忍高深度。

Fortunately, depth-independent succinct FE is a fairly simple wrapper on top of depth-bounded succinct FE (we will get into this later), so in this post we will just assume that the succinct FE that we use is also depth-independent.

幸运的是，深度无关的简洁 FE 是深度有界简洁 FE 之上的一个相当简单的包装器（我们稍后会讨论这个问题），因此在这篇文章中，我们将假设我们使用的简洁 FE 也是与深度无关的。

Generator chooses parameters for a hidden function with circuit \(C\) that has a single-bit output.

生成器为具有单位输出的电路 \(C\) 的隐藏函数选择参数。

They generate an encoding of that function.

他们生成该函数的编码。

This step is allowed to take as long as evaluating \(C\) on all possible inputs or even longer, but the output must be smaller than the truth table (the set of outputs for all possible inputs)

此步骤允许花费与在所有可能的输入上评估 \(C\) 一样长的时间甚至更长，但输出必须小于真值表（所有可能输入的输出集）

Evaluator evaluates the encoding to learn \(C(x)\) for any input \(x\) .

评估器评估编码以学习任何输入 \(x\) 的 \(C(x)\) 。

The class of functions that XiO is designed for is functions that are really best understood as zero-input functions (aka " thunks ") that produce a large but manageably-sized output.

XiO 设计的函数类别实际上最好理解为零输入函数（又名“thunks”），它产生大量但可管理大小的输出。

Given a thunk \(() \rightarrow X\) , we can think of it as being a function \(i \rightarrow X[i]\) , ie.

给定一个 thunk \(() \rightarrow X\) ，我们可以将其视为一个函数 \(i \rightarrow X[i]\) ，即。

the function which takes as input an index \(i\) as input, and returns the i'th output of the thunk.

该函数将索引 \(i\) 作为输入，并返回 thunk 的第 i 个输出。

These are two different views of the same object; in this post we will regularly bounce back and forth between these views.

这是对同一物体的两种不同看法；在这篇文章中，我们将定期在这些观点之间来回切换。

For example, you could imagine taking a function that generates a STARK (a roughly 128-512 kB sized cryptographic proof) and turning it into a function that takes as input an index \(0 \le i \lt 2^{22}\) , generates the STARK internally, and then outputs the i'th bit of the STARK.

例如，您可以想象采用一个生成 STARK（大约 128-512 kB 大小的加密证明）的函数，并将其转换为一个以索引 \(0 \le i \lt 2^{22}\) 作为输入的函数，在内部生成 STARK，然后输出 STARK 的第 i 位。

The goal of the XiO is that it's a gadget smaller than the STARK (though note: even a STARK may be too small to actually allow known XiO protocols to shrink it) that lets you generate that STARK, without being able to learn anything else about the underlying process that's generating it.

XiO 的目标是，它是一个比 STARK 更小的小工具（但请注意：即使是 STARK 也可能太小，无法实际允许已知的 XiO 协议缩小它），让您生成 STARK，而无需了解有关生成它的底层过程的任何其他信息。

Now, we combine succinct FE and XiO into a primitive called a sublinear compact randomized encoding :

现在，我们将简洁的 FE 和 XiO 组合成一个称为次线性紧凑随机编码的原语：

Let's walk through this carefully.

让我们仔细分析一下。

The goal here is to create a "randomized encoding" of \(P()\) - that is, a gadget that enables executing \(P()\) - which is asymptotically smaller than the runtime of \(P\) and asymptotically smaller than its output, and which hides \(P\) .

这里的目标是创建 \(P()\) 的“随机编码” - 即能够执行 \(P()\) 的小工具 - 它渐近小于 \(P\) 的运行时间并渐近小于其输出，并且隐藏 \(P\) 。

This is slightly different than the usual presentation of randomized encodings , which operate over \(P(x)\) and hide \(x\) but not \(P\) (eg.

这与通常的随机编码略有不同，随机编码在 \(P(x)\) 上运行并隐藏 \(x\) 但不隐藏 \(P\) （例如

garbled circuits work this way), but this is what we need for our use case - obfuscation is all about hiding the function.

乱码电路就是这样工作的），但这正是我们的用例所需要的——混淆就是隐藏函数。

The primitives that we will be working with do not hide the function.

我们将使用的原语不会隐藏该函数。

To do this, we make the "outer" function that these primitives are operating over just be a virtual machine (or "Turing machine") - basically, a function \(VM\) which takes circuits as input, so \(VM(P, X) = P(x)\) .

为此，我们使这些原语所操作的“外部”函数只是一个虚拟机（或“图灵机”）——基本上，一个以电路作为输入的函数 \(VM\) ，因此 \(VM(P, X) = P(x)\) 。

The circuit evaluating \(VM\) is often called a universal circuit .

评估\(VM\)的电路通常称为通用电路。

This way, \(P\) becomes just another input, which can be made private.

这样，\(P\) 就变成了另一个输入，可以将其设为私有。

One nuance in terms of asymptotic complexity: \(VM\) needs to be instantiated as a circuit , and the size of a circuit must be proportional to its runtime (because circuits do not allow looping).

渐近复杂度方面的一个细微差别是：\(VM\) 需要实例化为电路，并且电路的大小必须与其运行时间成正比（因为电路不允许循环）。

Hence, the size of the \(VM\) circuit must be proportional to the runtime of \(P\) .

因此，\(VM\) 电路的大小必须与 \(P\) 的运行时间成正比。

Fortunately, succinct FE allows generation to be fast even if the circuit is large and deep.

幸运的是，即使电路又大又深，简洁的 FE 也可以快速生成。

However, the output may have size and encryption cost that scales with the size of \(P\) .

但是，输出的大小和加密成本可能会随着 \(P\) 的大小而变化。

This is the reason why \(P\) must be expressed in a language other than circuits (such as a Turing machine ): its size must be fixed even if the computations get large.

这就是为什么 \(P\) 必须用电路以外的语言（例如图灵机）来表达的原因：即使计算量变大，它的大小也必须是固定的。

We do a trusted setup of succinct functional encryption, where the creator publishes public params and decryption keys for \(VM\) .

我们对简洁的功能加密进行了可信设置，其中创建者发布 \(VM\) 的公共参数和解密密钥。

This allows anyone to encrypt \((P, x)\) in such a way that anyone else can decrypt \(VM(P, x) = P(x)\) , but without learning \(P\) or \(x\) .

这允许任何人以其他人都可以解密 \(VM(P, x) = P(x)\) 的方式加密 \((P, x)\) ，但无需学习 \(P\) 或 \(x\) 。

To generate this randomized encoding, the creator wraps the two primitives I mentioned above inside each other: they do an XiO of a succinct FE encryption of \(VM(P, x)\) .

为了生成这种随机编码，创建者将我上面提到的两个原语相互包​​装起来：它们对 \(VM(P, x)\) 进行简洁的 FE 加密的 XiO。

The succinct FE encryption hides \((P, x)\) , and it's fast to generate even if \(P\) takes a long time to run.

简洁的 FE 加密隐藏了 \((P, x)\) ，即使 \(P\) 需要很长时间运行，生成速度也很快。

But succinct FE is not output-compressing: if the output is big, the succinct FE encryption is even bigger (and this is an unavoidable limitation of that type of construction).

但简洁 FE 不是输出压缩：如果输出很大，简洁 FE 加密甚至更大（这是该类型构造的不可避免的限制）。

The XiO cuts the size back down.

XiO 缩小了尺寸。

The creator makes a circuit \(C_{sfe}(i)\) that outputs the i'th bit of the succinct FE encryption, and does XiO over that.

创建者制作了一个电路 \(C_{sfe}(i)\) 来输出简洁 FE 加密的第 i 位，并对其进行 XiO。

Its size is now asymptotically smaller, and it's asymptotically faster to generate, than the program \(P\) itself (note "asymptotically": at small sizes, the overhead of the scheme dominates, the key property we want is that for sufficiently large circuits, \(xIO(sFE(VM(P, x))))\) becomes smaller than \((P, x)\) itself, both in byte size and in generation time.

现在，它的大小比程序 \(P\) 本身渐近更小，并且生成速度渐近更快（注意“渐近”：在小尺寸下，方案的开销占主导地位，我们想要的关键属性是，对于足够大的电路，\(xIO(sFE(VM(P, x))))\) 变得比 \((P, x)\) 本身更小，无论是字节大小还是生成时间。

Notice that here we already have our first glimpse of obfuscation: the creator themselves can both do the trusted setup and publish the xIO, and others can execute it without being able to learn the program being run.

请注意，在这里我们已经第一次看到了混淆：创建者自己可以进行可信设置并发布 xIO，而其他人可以执行它而无需了解正在运行的程序。

But we have a big problem: this only works for one pre-configured input.

但我们有一个大问题：这只适用于一个预先配置的输入。

Now, we get to the next part: the final obfuscation construction.

现在，我们进入下一部分：最终的混淆构造。

Essentially, we take the sublinear compact RE primitive, and we apply it recursively, recursing on the number of bits of input going into the function you are trying to obfuscate.

本质上，我们采用次线性紧凑 RE 原语，并递归地应用它，递归进入您试图混淆的函数的输入位数。

At the base case (zero inputs), we just use the sublinear compact RE as above.

在基本情况（零输入）下，我们只使用上面的次线性紧凑 RE。

To add one bit, we make a sublinear compact RE of the process of generating two obfuscations one level lower: obfuscate the function \(P_0(x)\) which executes \(P\) but with the first input bit fixed to \(0\) , and \(P_1(x)\) which executes \(P\) but with the first input bit fixed to \(1\) .

为了添加一位，我们对生成两个混淆的过程做了一个低一级的次线性紧凑 RE：混淆执行 \(P\) 但第一个输入位固定为 \(0\) 的函数 \(P_0(x)\) 和执行 \(P\) 但第一个输入位固定为 \(1\) 的 \(P_1(x)\) 。

Remember the key properties of the two building blocks of sublinear compact RE:

请记住次线性紧凑 RE 的两个构建块的关键属性：

Both properties are needed to ensure the recursion avoids blowup.

需要这两个属性来确保递归避免爆炸。

To evaluate an obfuscated program, you evaluate the top-level RE to get your two new obfuscations (both with one fewer input bit required), then choose either left or right based on the first input bit, then keep recursing further down, until you bottom out with a thunk that generates \(P(x)\) for the \(x\) that is the full path you walked down.

要评估混淆程序，您需要评估顶层 RE 以获得两个新的混淆（两者都需要较少的输入位），然后根据第一个输入位选择左或右，然后继续向下递归，直到您用一个 thunk 触底，该 thunk 为您走下的完整路径生成 \(P(x)\)。

For programs with an n-bit input, there is a depth-n, size \(2^n\) tree of all possible evaluations.

对于具有 n 位输入的程序，存在一个包含所有可能评估的深度为 n、大小为 \(2^n\) 的树。

However, most of this tree is never evaluated.

然而，这棵树的大部分内容从未被评估过。

The whole thing is a tree of "thunks", and so the exponential cost of creating the tree is never paid because all the thunks that are not on the path to the specific input you care about never actually get instantiated.

整个事情是一棵“thunk”树，因此创建树的指数成本永远不会被支付，因为所有不在您关心的特定输入路径上的 thunk 永远不会真正被实例化。

The only thing that does get instantiated is the obfuscation at each step along with path going from the root to the input.

唯一被实例化的是每一步的混淆以及从根到输入的路径。

And at a very high level, that's it, that's the core design.

在非常高的层面上，就是这样，这就是核心设计。

Note that the original LPST15 and LPST16 papers describe what is going on slightly differently (but equivalently): they do not recurse on obfuscation directly, rather they recurse on a "node program" .

请注意，原始 LPST15 和 LPST16 论文描述的情况略有不同（但等效）：它们不会直接在混淆上递归，而是在“节点程序”上递归。

One nice property of that approach is that the node program captures the "bits of the input so far", so you don't have to manipulate or wrap \(P\) itself; \(P\) stays unchanged throughout the whole process in their version.

该方法的一个很好的特性是节点程序捕获“到目前为止的输入位”，因此您不必操纵或包装 \(P\) 本身；在他们的版本中，\(P\) 在整个过程中保持不变。

Another thing that the above description elided is that for obfuscation to be secure, it needs to be randomized.

上述描述忽略的另一件事是，为了保证混淆的安全，它需要被随机化。

So actually, it's not \(iO(P)\) , it's \(iO(P, seed)\) , where the \(seed\) is a value that is hashed to generate (pseudo-)randomness needed by primitives like garbled circuits.

所以实际上，它不是 \(iO(P)\) ，而是 \(iO(P, seed)\) ，其中 \(seed\) 是一个经过哈希处理以生成乱码电路等原语所需的（伪）随机性的值。

Randomized encoding, XiO and succinct functional encryption also all take a \(seed\) as an argument.

随机编码、XiO 和简洁函数加密也都以“种子”作为参数。

When one of these functions calls any other as a subroutine, it should generate the seed for the subroutine via a hash from its own seed, and take care to provide a unique different seed for each one.

当这些函数之一调用任何其他函数作为子例程时，它应该通过其自己的种子的哈希值生成子例程的种子，并注意为每个函数提供唯一的不同种子。

To make the security proofs clean, the hash must technically be a puncturable PRF , though with the interesting property that the punctured version of the hash needs to be possible to construct but never actually gets run.

为了使安全证明干净，哈希在技术上必须是可穿孔的 PRF ，尽管有一个有趣的特性，即哈希的穿孔版本需要可以构建，但永远不会真正运行。

The bad news: the succinct FE scheme is a complicated tower of constructions, one stacked on top of the other.

坏消息：简洁的有限元方案是一座复杂的建筑塔，一个堆叠在另一个之上。

The good news: these constructions are relatively well-understood, use very standard cryptographic assumptions ("just" lattices ), and the pipeline to build succinct FE has been understood since roughly 2014.

好消息：这些构造相对容易理解，使用非常标准的加密假设（“只是”格），并且自 2014 年左右以来，构建简洁 FE 的管道就已被理解。

Let's go through these one by one.

让我们一一回顾一下。

The two most fundamental building blocks are garbled circuits and fully homomorphic encryption.

两个最基本的构建块是乱码电路和全同态加密。

Here is a post where I explain garbled circuits in more detail.

这是我更详细地解释乱码电路的帖子。

The basic summary is:

基本总结是：

Garbled circuits can only safely be executed once.

乱码电路只能安全执行一次。

If you give someone the labels for two inputs, they are able to compute much more than two outputs.

如果你给某人两个输入的标签，他们就能够计算出两个以上的输出。

Garbled circuits were originally developed as a 2-of-2 multi-party-computation primitive: I have a circuit \(C\) , you know \(x\) , I send you a garbling of \(C\) , for each input wire I help you learn one of the two input wires without learning which one using a technique called oblivious transfer , and then you walk the circuit to compute the output \(C(x)\) .

乱码电路最初是作为 2-of-2 多方计算原语开发的：我有一个电路 \(C\) ，你知道 \(x\) ，我向你发送一个乱码 \(C\) ，对于每条输入线，我帮助你学习两条输入线中的一条，而无需使用一种称为不经意转移的技术来了解哪一条，然后你走遍电路来计算输出 \(C(x)\) 。

A basic rough description of how oblivious transfer works: you send me two public keys \(A\) and \(B\) that have to add up to some random hash so only one of them can have a valid private key but I don't know which one, I encrypt one label with \(A\) and one with \(B\) , you decrypt the label that you have a private key for, but I can't tell which one that is.

关于不经意传输如何工作的基本粗略描述：您向我发送两个公钥 \(A\) 和 \(B\)，它们必须添加到一些随机散列，因此只有其中一个可以拥有有效的私钥，但我不知道哪一个，我用 \(A\) 加密一个标签，用 \(B\) 加密一个标签，您解密您拥有私钥的标签，但我无法分辨是哪一个。

Here, however, we are not doing 2-of-2 computation.

然而，这里我们不进行 2-of-2 计算。

Rather, we are using garbled circuits as an ingredient to get the properties that we need for succinct FE.

相反，我们使用乱码电路作为成分来获得简洁有限元所需的属性。

Garbled circuits have many valuable properties.

乱码电路有许多有价值的特性。

Notably:

值得注意的是：

Garbling hides some information about the circuit, but not enough to be meaningfully useful for anything where you want function-hiding.

乱码隐藏了有关电路的一些信息，但不足以对您想要隐藏功能的任何地方产生有意义的作用。

When function-hiding is required (eg.

当需要隐藏功能时（例如

the 2-of-2 MPC use case), a typical solution is to garble a universal circuit (aka virtual machine) and have the circuit provider also provide the actual circuit \(C\) they want to run as labels that become part of the input.

2-of-2 MPC 用例），一个典型的解决方案是混淆通用电路（又名虚拟机），并让电路提供商也提供他们想要作为输入一部分的标签运行的实际电路 \(C\)。

For our use case, we don't care about garbling leaking details of the function, in fact precisely because we are employing this "wrap it in a VM" trick.

对于我们的用例，我们并不关心函数细节的乱码泄漏，事实上正是因为我们正在采用这种“将其包装在虚拟机中”的技巧。

Here is a post where I talk about FHE in more detail.

这是我更详细地讨论 FHE 的帖子。

Because the details matter for the other constructions later in this post, I will provide a basic summary.

因为细节对于本文后面的其他结构很重​​要，所以我将提供一个基本的总结。

FHE is based on a cryptographic assumption called learning with errors (LWE).

FHE 基于称为错误学习 (LWE) 的加密假设。

Basically, if you have an approximate solution to a system of linear equations modulo some number (ie.

基本上，如果您有线性方程组模某个数的近似解（即

a matrix \(A\) , vectors \(s\) and \(b\) , modulus \(q\) such that \(b = (A*s + e) % q\) modulo \(q\) , where \(e\) is a "small" (aka "low-norm") error vector, so each value in \(e\) is much smaller than \(q\) ), then given \(b\) and \(A\) you can't extract \(s\) .

矩阵 \(A\) 、向量 \(s\) 和 \(b\) 、模 \(q\) 使得 \(b = (A*s + e) % q\) 模 \(q\) ，其中 \(e\) 是一个“小”（又名“低范数”）误差向量，因此 \(e\) 中的每个值都比 \(q\) 小得多），然后给定 \(b\) 和 \(A\) 你无法提取 \(s\) 。

If you have an exact equation \(s * A = b\) , then that's a system of linear equations ( modulo q ), which can be done reasonably cheaply with Gaussian elimination .

如果你有一个精确的方程 \(s * A = b\) ，那么它就是一个线性方程组（模 q ），可以通过高斯消去法以相当便宜的方式完成。

But with errors added, doing this inversion is computationally infeasible.

但随着误差的增加，这种反演在计算上是不可行的。

There are many FHE algorithms built on top of this assumption that have different properties.

有许多建立在这一假设之上的 FHE 算法，它们具有不同的属性。

The simplest idea involves randomly choosing a private key \(s\) , generating a random matrix \(A\) , and computing \(b = A * s + e + m * \frac{q}{2}\) modulo \(q\) as the encryption of a single bit \(m\) (here, adding a bit to a vector adds that value to every element of the vector).

最简单的想法包括随机选择一个私钥 \(s\) ，生成一个随机矩阵 \(A\) ，并计算 \(b = A * s + e + m * \frac{q}{2}\) 模 \(q\) 作为单个位 \(m\) 的加密（这里，向向量添加一个位会将该值添加到向量的每个元素）。

The creator can then publish encryptions of \(0\) and \(1\) computed this way.

然后，创建者可以发布以这种方式计算的\(0\) 和\(1\) 的加密。

To decrypt, you can compute \(b - A * s\) which equals \(e + m * \frac{q}{2}\) ; the higher-order bit encodes the message and the lower-order bits encode the error which can be thrown away.

要解密，您可以计算 \(b - A * s\) ，它等于 \(e + m * \frac{q}{2}\) ；高阶位对消息进行编码，低阶位对可以丢弃的错误进行编码。

If you have two ciphertexts \(b_1\) and \(b_2\) that are valid encryptions of \(x_1\) and \(x_2\) , then \(b_1 + b_2\) (again, all modulo \(q\) ) is a valid encryption of \(x_1 + x_2\) .

如果您有两个密文 \(b_1\) 和 \(b_2\) ，它们是 \(x_1\) 和 \(x_2\) 的有效加密，则 \(b_1 + b_2\) （同样，所有模 \(q\) ）是 \(x_1 + x_2\) 的有效加密。

Notice also that the above design as written can support encrypting vectors of bits in the message slot, and not just single bits.

还请注意，上述设计可以支持加密消息槽中的位向量，而不仅仅是单个位。

But there's one critical thing that the above design does not actually support: multiplication.

但上述设计实际上并不支持一件关键的事情：乘法。

Multiplication is trickier than addition, for a few reasons.

由于某些原因，乘法比加法更棘手。

First, you can't multiply two vectors by each other and get a vector; you can only do that to other structures like matrices or polynomials.

首先，你不能将两个向量相乘并得到一个向量；您只能对矩阵或多项式等其他结构执行此操作。

Second, whereas adding two three-term values \(A * s + e + m * \frac{q}{2}\) gives you another three-term value, multiplying two three-term values gives you a nine-term value, so you're still getting something of a different "shape".

其次，将两个三项值相加 \(A * s + e + m * \frac{q}{2}\) 会得到另一个三项值，而将两个三项值相乘会得到一个九项值，因此您仍然会得到不同“形状”的东西。

Third, you end up multiplying the "small" error by "large" other things, which makes the error blow up after only one round of multiplication.

第三，你最终将“小”误差乘以“大”其他东西，这使得误差在一轮乘法后就放大了。

There is no one easy solution to this.

对此没有一种简单的解决方案。

There are several families of solutions, that all have different drawbacks.

有多种解决方案，它们都有不同的缺点。

The ones that use polynomials are based off of a stronger assumption called Ring LWE ; a commonly-used scheme is BFV .

使用多项式的那些基于称为 Ring LWE 的更强假设；常用的方案是 BFV 。

The scheme that is most convenient to FHE usage is based on matrices, and is called GSW .

最方便FHE使用的方案是基于矩阵的方案，称为GSW。

To show how it works, I will first show a simplified version that makes the basic arithmetic work, but does not deal with the error issue, so it breaks if you have nonzero error.

为了展示它是如何工作的，我将首先展示一个简化版本，它使基本算术工作，但不处理错误问题，因此如果出现非零错误，它就会中断。

First, generate a secret \(s\) .

首先，生成一个秘密 \(s\) 。

To encrypt a value \(m\) , first generate an otherwise-random matrix \(A\) where \(s * A\) equals some "small" or "low-norm" error \(e\) .

要加密值 \(m\) ，首先生成一个随机矩阵 \(A\) ，其中 \(s * A\) 等于某个“小”或“低范数”误差 \(e\) 。

One way to do this is to generate both in two parts:

一种方法是分两部分生成：

Then, compute \(c = A + m * I\) (where \(I\) is the identity matrix).

然后，计算 \(c = A + m * I\)（其中 \(I\) 是单位矩阵）。

And to decrypt the ciphertext, read off \((s * C)[-1]\) (ie.

要解密密文，请读取 \((s * C)[-1]\) （即

the last value of \(s * C\) ).

\(s * C\) 的最后一个值）。

If you are a mathematician, you might notice that we are "hiding" \(m\) in an igon value eigenvalue of C: \(s\) is the eigenvector, so it satisfies \(s * C \approx s * m\) .

如果您是一名数学家，您可能会注意到我们将 \(m\) “隐藏”在 C 的 igon 值特征值中：\(s\) 是特征向量，因此它满足 \(s * C \approx s * m\) 。

They are not quite an exact eigenvector and eigenvalue; they're eigenvectors and eigenvalues with errors.

它们并不是一个精确的特征向量和特征值；它们是带有错误的特征向量和特征值。

But first, we can set aside the errors, and note some properties that make eigenvalues special.

但首先，我们可以抛开错误，并注意一些使特征值变得特殊的属性。

\(C_1 + C_2\) satisfies \((s * (C_1 + C_2))[-1] \approx (m_1 + m_2)\)

\(C_1 + C_2\) 满足 \((s * (C_1 + C_2))[-1] \approx (m_1 + m_2)\)

Eigenvalues are basically the only attribute of a matrix that has both an additive and a multiplicative property like this, and even there we are restricting to matrices that have the same eigenvector.

特征值基本上是同时具有加法和乘法属性的矩阵的唯一属性，即使如此，我们也仅限于具有相同特征向量的矩阵。

Now, let's bring back error tolerance .

现在，让我们恢复容错能力。

The mechanism above, as written, has a fatal flaw: if you write out the full equations with error, you end up multiplying error by elements of \(C\) and \(s\) , which can be anywhere in the full range \([0, q-1]\) .

正如所写的，上面的机制有一个致命的缺陷：如果你写出带有错误的完整方程，你最终会将错误乘以 \(C\) 和 \(s\) 的元素，这些元素可以是整个范围 \([0, q-1]\) 中的任何位置。

Hence, this immediately blows up error to the maximum.

因此，这立即将错误放大到最大。

Additionally, even decryption cannot tolerate error.

此外，即使解密也不能容忍错误。

To plug the first hole (we'll get back to the second at the end), actual GSW relies on a gadget matrix mechanism.

为了堵住第一个漏洞（我们最后会回到第二个漏洞），实际的 GSW 依赖于小工具矩阵机制。

On its own this looks nice but it does not make much sense.

就其本身而言，这看起来不错，但没有多大意义。

However, it is intended to be paired with an operation (not a matrix) that it cancels out: the matrix bit decomposition operation:

然而，它旨在与它抵消的操作（不是矩阵）配对：矩阵位分解操作：

Every adjacent four values in the output of this operation (which we call " \(G^{-1}\) ") is the (least-significant-bit first) binary encoding (aka.

此操作的输出中的每相邻四个值（我们称之为“\(G^{-1}\)”）是（最低有效位在前）二进制编码（又名。

bit decomposition) of the correspondingly-placed value in the input.

位分解）输入中相应位置的值。

You can see the latter intuitively.

你可以直观地看到后者。

If you trace the highlighted bit-decomposition of 2 ( 0 1 0 0 ) in the above example through the computation, then it gets multiplied by 1 2 4 8 from the gadget, and the result is \((0 * 1) + (1 * 2) + (0 * 4) + (0 * 8) = 2\) .

如果通过计算追踪上例中突出显示的 2 ( 0 1 0 0 ) 的位分解，那么它会从小工具中乘以 1 2 4 8，结果为 \((0 * 1) + (1 * 2) + (0 * 4) + (0 * 8) = 2\) 。

That is, if you apply the gadget matrix to a bit decomposition, it "evaluates" the bit decomposition to get back the original value.

也就是说，如果您将小工具矩阵应用于位分解，它会“评估”位分解以返回原始值。

In those places where we used the identity matrix ( \(I\) ) in the simplified description above, in the actual protocol we use \(G\) .

在上面的简化描述中我们使用单位矩阵（ \(I\) ）的地方，在实际协议中我们使用 \(G\) 。

That is, ciphertexts are of the form \(A + m * G\) .

也就是说，密文的形式为 \(A + m * G\) 。

We multiply two ciphertexts by computing \(C_1 * G^{-1}(C_2)\) .

我们通过计算 \(C_1 * G^{-1}(C_2)\) 将两个密文相乘。

The message is being hidden in something that's no longer quite an eigenvalue-with-errors, but we still preserve the needed properties.

该消息隐藏在不再完全是带有错误的特征值的东西中，但我们仍然保留所需的属性。

The math ends up working the same way, but because the error never gets multiplied by large numbers, multiplication actually works.

数学最终以同样的方式工作，但由于误差永远不会乘以大数，因此乘法实际上有效。

Specifically:

具体来说：

Note one subtlety in the decryption.

请注意解密过程中的一个微妙之处。

The last column of \(G\) contains \(\frac{q}{2}\) as its only nonzero entry, and so multiplying by \(G\) actually gives us an object containing \(m * \frac{q}{2} + e\) (and not \(m + e\) ).

\(G\) 的最后一列包含 \(\frac{q}{2}\) 作为其唯一的非零条目，因此乘以 \(G\) 实际上给出了一个包含 \(m * \frac{q}{2} + e\) 的对象（而不是 \(m + e\) ）。

This is what gives us error tolerance in decryption.

这就是我们在解密时具有容错能力的原因。

This is also why we are now dividing by \(\frac{q}{2}\) when we encrypt.

这也是我们加密时除以 \(\frac{q}{2}\) 的原因。

Note that this method as written requires \(q\) to be a power of two.

请注意，这种方法的编写要求 \(q\) 是 2 的幂。

If you want, you can make \(q\) be something else, but this requires tweaking the decryption procedure slightly.

如果需要，您可以将 \(q\) 设为其他内容，但这需要稍微调整解密过程。

We can check the correctness of multiplication.

我们可以检查乘法的正确性。

Let's start with just the algebra.

让我们从代数开始。

First for addition:

首先补充一下：

Now, we have to show that the first two terms are both valid "pads", in the same way that the original \(A_1\) and \(A_2\) were valid pads.

现在，我们必须证明前两项都是有效的“pad”，就像原始的 \(A_1\) 和 \(A_2\) 是有效的 pad 一样。

The core property we need is that multiplying \(s * A\) leaves only a small low-norm error.

我们需要的核心属性是乘以 \(s * A\) 只会留下一个小的低范数误差。

The second term is easy: \(A_2\) is a valid pad ( \(s * A_2\) is low-norm), and we multiply it by \(m_1\) , which is small, so \(m_1 * A_2\) is also low norm and hence a valid pad.

第二项很简单：\(A_2\)是一个有效的pad（\(s * A_2\)是低范数），我们将它乘以\(m_1\)，它很小，所以\(m_1 * A_2\)也是低范数，因此是一个有效的pad。

For the first term, let us unpack \(s * A_1 * G^{-1}(C_2)\) .

对于第一项，让我们解压 \(s * A_1 * G^{-1}(C_2)\) 。

\(s * A_1\) returns a "small" error.

\(s * A_1\) 返回一个“小”错误。

\(G^{-1}(C_2)\) returns a matrix of ones and zeroes.

\(G^{-1}(C_2)\) 返回一个由 1 和 0 组成的矩阵。

Hence, \(s * A_1 * G^{-1}(C_2)\) is a small error multiplied by a matrix of ones and zeroes, which is still a small error.

因此，\(s * A_1 * G^{-1}(C_2)\) 是一个小误差乘以 1 和 0 的矩阵，这仍然是一个小误差。

The error in the second pad blows up by roughly the size of the message space (so, 0 or 1).

第二个 pad 中的错误大约会增加消息空间的大小（即 0 或 1）。

The error in the first pad blows up by roughly the size of the matrix.

第一个 pad 中的误差大约增大了矩阵的大小。

Hence, each multiplication blows up the error by a constant factor, and so we can predict how many multiplications the FHE can survive before the error gets too high.

因此，每次乘法都会将误差放大一个常数因子，因此我们可以预测在误差变得过高之前 FHE 可以存活多少次乘法。

At that point, you would need to reset the error by bootstrapping: evaluate the FHE decryption circuit inside FHE.

此时，您需要通过引导来重置错误：评估 FHE 内部的 FHE 解密电路。

Finally, one more nuance: to keep the error blowup bounded, we need to require messages to stay small; specifically, they must be 0 or 1 (we can also accept eg.

最后，还有一个细微差别：为了限制错误爆炸，我们需要要求消息保持较小；具体来说，它们必须是 0 或 1（我们也可以接受例如

-1 or 2).

-1 或 2)。

Addition and multiplication do not respect size limitations, and unlike BGV, here we do not have native "wraparound" modulo 2.

加法和乘法不考虑大小限制，并且与 BGV 不同，这里我们没有本机“环绕”模 2。

So to make the above algorithm safe, you would need to use circuits with "logic gates" implemented like this:

因此，为了使上述算法安全，您需要使用具有如下实现的“逻辑门”的电路：

This is only one way to do it; it's not optimal; there are ways to do it more efficiently, and that is part of the art of FHE optimization.

这只是一种方法；这不是最佳的；有一些方法可以更有效地做到这一点，这是 FHE 优化艺术的一部分。

Here is some python code that follows along this style of GSW, though note that it uses a slightly different technique where \(A * R\) is the "pad" instead of \(A\) (this has all of the properties above, plus an extra property that we will need later).

下面是一些遵循这种 GSW 风格的 Python 代码，但请注意，它使用了稍微不同的技术，其中 \(A * R\) 是“pad”而不是 \(A\)（它具有上面的所有属性，加上我们稍后需要的额外属性）。

https://gist.github.com/vbuterin/f0f8a9eb09633226ada20c21a98d537e

https://gist.github.com/vbuterin/f0f8a9eb09633226ada20c21a98d537e

It's worth playing around with this kind of FHE, because it helps build intuitions for some of the other primitives that we are going to use below.

这种 FHE 值得尝试，因为它有助于为我们下面将使用的其他一些原语建立直觉。

Authority generates keys for a function with circuit \(C\) , they generate a "master public key" \(mpk\) (public), and a secret key \(sk_C\) (given to decryptor) that depends on \(C\)

权威机构使用电路 \(C\) 为函数生成密钥，它们生成一个“主公钥”\(mpk\)（公开），以及依赖于 \(C\) 的秘密密钥 \(sk_C\)（提供给解密器）

Encryptor knows \(m\) (a message to encrypt), they know a \(tag\) for that message, they do not necessarily know \(C\) but they do know \(mpk\) .

加密器知道 \(m\) （要加密的消息），他们知道该消息的 \(tag\) ，他们不一定知道 \(C\) 但他们确实知道 \(mpk\) 。

They produce a ciphertext \(T\)

他们产生密文\(T\)

A decryptor given such a \(T\) and \(sk_C\) can decrypt to recover \(m\) if \(C(tag) = 0\) , otherwise they cannot.

给定这样的 \(T\) 和 \(sk_C\) 的解密器可以解密以恢复 \(m\) 如果 \(C(tag) = 0\) ，否则它们不能。

Usually, attribute-based encryption is justified by examples like: \(m\) might be medical records at some hospital \(H\) , \(tag\) might be an object that represents "you work at \(H\) AND you have a medical degree", so it becomes easy to encrypt the medical records in such a way that only the intended doctors can see them.

通常，基于属性的加密可以通过以下示例来证明：\(m\) 可能是某家医院 \(H\) 的医疗记录，\(tag\) 可能是表示“您在 \(H\) 工作并且拥有医学学位”的对象，因此可以轻松地以只有指定医生才能看到的方式对医疗记录进行加密。

As far as I can tell, however, the number of use cases that map well to this paradigm and can't easily be solved with much simpler public key encryption is very small.

然而，据我所知，能够很好地映射到这种范例并且无法通过更简单的公钥加密轻松解决的用例数量非常少。

And so ABE has not been used much in practice.

因此ABE在实际中并没有得到太多的应用。

.

。

But here, we have very good news: ABE has some valuable properties that make it very useful in building functional encryption!

但在这里，我们有一个非常好的消息：ABE 具有一些有价值的特性，这使得它在构建函数式加密时非常有用！

(And hence, obfuscation) In particular, even for circuits that are large, encryption is cheap .

（因此，混淆）特别是，即使对于大型电路，加密也很便宜。

This is the ultimate seed of the asymmetry that allows the "thunks" in the obfuscation to be faster to create than they are to execute, and hence makes the exponentially-sized tree possible at all.

这是不对称性的最终种子，它允许混淆中的“thunk”创建速度比执行速度更快，从而使指数大小的树成为可能。

Here is how ABE works.

以下是 ABE 的工作原理。

Here we will follow the BGG+14 construction , whose properties are ideal for the succinct FE and obfuscation use case.

在这里，我们将遵循 BGG+14 构造，其属性非常适合简洁的 FE 和混淆用例。

We work over a circuit.

我们在一个电路上工作。

To have an example in your head, take the circuit that we used in the garbled circuits example (it's a two-bit adder), but remove the "two labels per wire" piece:

为了在您的头脑中有一个示例，请采用我们在乱码电路示例中使用的电路（它是一个两位加法器），但删除“每根线两个标签”部分：

Instead, we will have only one matrix \(B_w\) per wire, plus two randomly-generated global public matrices \(A\) and \(D\) .

相反，每根导线我们只有一个矩阵 \(B_w\) ，加上两个随机生成的全局公共矩阵 \(A\) 和 \(D\) 。

The initial \(B_i\) are generated randomly.

初始\(B_i\)是随机生成的。

To generate the \(B\) matrices for the wires further down, we walk down the circuit going through each gate:

为了进一步生成导线的 \(B\) 矩阵，我们沿着电路走下去，穿过每个门：

As in FHE, we need to build OR, XOR and AND from ADD and MUL in ways that preserve the wire values staying in \(\{0, 1\}\) .

与 FHE 中一样，我们需要从 ADD 和 MUL 构建 OR、XOR 和 AND，以保留位于 \(\{0, 1\}\) 中的连线值。

The authority publishes circuit-independent \(A\) and \(D\) , and the \(B_i\) for the input wires for the circuit.

权威机构发布了与电路无关的\(A\)和\(D\)，以及电路输入线的\(B_i\)。

They also provide the decryptor with a decryption key, a low-norm matrix \(R_f\) that satisfies \((A | B_f) * R_f = D\) , where \(B_f\) is the \(B\) matrix for the wire that encodes the output (ie.

它们还为解密器提供解密密钥，即满足 \((A | B_f) * R_f = D\) 的低范数矩阵 \(R_f\) ，其中 \(B_f\) 是编码输出的线路的 \(B\) 矩阵（即

\(C(tag)\) ).

\(C(标签)\))。

Notice that the construction of \(B\) matrices is not dependent on the input to the circuit, which is why the authority is able to construct \(B_f\) in a way that is then valid for all inputs.

请注意，\(B\) 矩阵的构造不依赖于电路的输入，这就是为什么权威机构能够以对所有输入都有效的方式构造 \(B_f\)。

To make the equation between \((A | B_f) * R_f = D\) correct, \(A\) needs to be constructed in a special way that gives it a "trapdoor"; we will return to this later.

为了使 \((A | B_f) * R_f = D\) 之间的方程正确，\(A\) 需要以特殊的方式构造，赋予它一个“活板门”；我们稍后再讨论这一点。

First, let's go through the encryptor and decryptor's logic.

首先，我们来了解一下加密器和解密器的逻辑。

To encrypt, the encryptor chooses a random vector \(s\) , and computes \(c_{out} ​= s * D + e_{out} ​+ \frac{q}{2} * m\) .

为了加密，加密器选择一个随机向量 \(s\) ，并计算 \(c_{out} ​= s * D + e_{out} ​+ \frac{q}{2} * m\) 。

They also provide the input encodings, \(c_i = s * (B_i + G * tag[i]) + e_i\) , and \(c_A = s * A + e_A\) .

它们还提供输入编码 \(c_i = s * (B_i + G * tag[i]) + e_i\) 和 \(c_A = s * A + e_A\) 。

Notice how encrypting does not depend on the circuit itself; it only requires knowing and doing a few multiplications involving the input \(B_i\) and \(D\) .

请注意加密如何不依赖于电路本身；它只需要知道并执行一些涉及输入 \(B_i\) 和 \(D\) 的乘法。

The decryptor's job will be to start with these \(c_i\) values, and walk down the circuit, doing a homomorphic-encryption-like operation at each gate to convert the \(c_L\) for the left input wire and \(c_R\) for the right input wire into \(c_{out}\) for the output wire.

解密器的工作将从这些 \(c_i\) 值开始，沿着电路走下去，在每个门处执行类似同态加密的操作，将左侧输入线的 \(c_L\) 和右侧输入线的 \(c_R\) 转换为输出线的 \(c_{out}\)。

Here, the ADD case is again trivial: \(c_{out} = c_L + c_R\) .

在这里，ADD 情况再次变得微不足道： \(c_{out} = c_L + c_R\) 。

The MUL case is the harder one.

MUL 情况是更难的情况。

The formula is: \(c_{out} = x_R * ​c_L ​+ c_R * ​G^{-1}(-B_L)\)

公式为：\(c_{out} = x_R * ​c_L ​+ c_R * ​G^{-1}(-B_L)\)

\(x_R\) here is the actual value on that wire in the computation.

\(x_R\) 这里是计算中该线路上的实际值。

To see why this works, let's look at each component in turn.

要了解其原理，让我们依次查看每个组件。

For ease of exposition, I'll write \(G^{-1}(-B_L)\) as \(R_{-L}\) ; just remember that because \(G\) and \(G^{-1}\) cancel out, \(G * R_{-L} = -B_L\) :

为了便于说明，我将 \(G^{-1}(-B_L)\) 写为 \(R_{-L}\) ；只要记住，因为 \(G\) 和 \(G^{-1}\) 抵消了， \(G * R_{-L} = -B_L\) ：

If we add the two together, the \(x_R * B_L\) cancel out, and we get:

如果我们将两者相加，\(x_R * B_L\) 就会抵消，我们得到：

\(s * (x_L * x_R * G + B_R * R_{-L}) + x_R * e_L + e_R * R_{-L}\)

\(s * (x_L * x_R * G + B_R * R_{-L}) + x_R * e_L + e_R * R_{-L}\)

The \(B_R * R_{-L}\) on the left side is just \(B_R * G^{-1}(-B_L)\) , which is the definition of \(B_{out}\) for multiplication that we gave above.

左边的 \(B_R * R_{-L}\) 就是 \(B_R * G^{-1}(-B_L)\) ，这是我们上面给出的乘法 \(B_{out}\) 的定义。

And the right side is error multiplied by low-norm values, so it stays as low-norm error.

右侧是误差乘以低范数值，因此它保持为低范数误差。

And so the decryptor has everything they need to walk their way to \(c_f\) .

因此解密者拥有了到达 \(c_f\) 所需的一切。

If \(C(tag) = 0\) , then the \(s * x_f * G\) term drops off from the definition of \(c_f\) , and we just have: \(c_f = s * B_f + e_f\)

如果 \(C(tag) = 0\) ，则 \(s * x_f * G\) 项从 \(c_f\) 的定义中消失，我们只有： \(c_f = s * B_f + e_f\)

Once they get to \(c_f\) , they prepend \(c_A\) to get \(c'_f = (c_A\ |\ c_f)\) , which satisfies \(c'_f = s * (A\ |\ B_f) + e'_f\) .

一旦到达 \(c_f\) ，他们就会在 \(c_A\) 前面加上 \(c'_f = (c_A\ |\ c_f)\) ，满足 \(c'_f = s * (A\ |\ B_f) + e'_f\) 。

They then compute:

然后他们计算：

\(= s * D + e_{out} + \frac{q}{2} * m - s * (A\ |\ B_f) * R_f - e'_f * R_f\)

\(= s * D + e_{out} + \frac{q}{2} * m - s * (A\ |\ B_f) * R_f - e'_f * R_f\)

\(= s * D + e_{out} + \frac{q}{2} * m - s * D - e'_f * R_f\)

\(= s * D + e_{out} + \frac{q}{2} * m - s * D - e'_f * R_f\)

If the error did not blow up too much (remember, \(R_f\) is also low-norm), the decryptor can now freely recover \(m\) .

如果错误没有爆炸太多（请记住，\(R_f\) 也是低范数），解密器现在可以自由地恢复 \(m\) 。

We do not construct \(A\) randomly.

我们不会随机构造\(A\)。

Instead, we construct it as \(A = (A_{prefix}\ |\ G - A_{prefix} * R)\) , where \(R\) is a low-norm "trapdoor", and \(G\) is the gadget matrix from before.

相反，我们将其构造为 \(A = (A_{prefix}\ |\ G - A_{prefix} * R)\) ，其中 \(R\) 是低范数“活板门”，而 \(G\) 是之前的小工具矩阵。

Similarly to the FHE ciphertexts we saw, under the LWE assumption this kind of construction is computationally infeasible to distinguish from random if you do not have the trapdoor yourself.

与我们看到的 FHE 密文类似，在 LWE 假设下，如果您自己没有陷门，这种构造在计算上无法与随机的区分开来。

We've constructed a matrix \(A\) , where in some sense \(R \atop I\) is a sort of "inverse" of A (remember: \(G\) often plays the role of "pretending" to be the identity matrix in these types of LWE constructions).

我们构造了一个矩阵 \(A\) ，其中在某种意义上 \(R \atop I\) 是 A 的一种“逆”（记住：\(G\) 通常在这些类型的 LWE 构造中扮演“假装”单位矩阵的角色）。

The goal here is that we want to create matrices for which, for any known vector \(u\) , only the creator can find a low-norm vector \(r\) where \(A*r = u\) .

这里的目标是我们想要创建一个矩阵，对于任何已知向量 \(u\) ，只有创建者才能找到一个低范向量 \(r\) ，其中 \(A*r = u\) 。

That is, the trapdoor lets us "solve" the short integer solution (SIS) problem , which is closely related to LWE and is the basis for this type of cryptography working.

也就是说，陷门让我们“解决”短整数解（SIS）问题，它与 LWE 密切相关，是此类密码学工作的基础。

\(R\) , \(I\) and \(z\) are all low-norm, so this is also low-norm.

\(R\) 、 \(I\) 和 \(z\) 都是低范数，因此这也是低范数。

To see algebraically why this solves the equation, compute:

要从代数角度了解为什么这个方程可以解，请计算：

To guarantee that this is safe (in the sense of not leaking \(R\) ), real-world implementations add additional error at this step; see MP12 for more details on maximally efficient ways to do this.

为了保证这是安全的（在不泄漏 \(R\) 的意义上），现实世界的实现在这一步添加了额外的错误；有关最有效方法的更多详细信息，请参阅 MP12。

Now, let's go back to the still-unsolved puzzle from above: computing \(R_f\) .

现在，让我们回到上面尚未解决的难题：计算 \(R_f\) 。

We will interpret \(R_f\) as \(R_{top} \atop R_{bottom}\) , so we get:

我们将 \(R_f\) 解释为 \(R_{top} \atop R_{bottom}\) ，所以我们得到：

We sample a random low-norm error for \(R_{bottom}\) , so now we only need to solve:

我们对 \(R_{bottom}\) 采样一个随机低范数误差，所以现在我们只需要求解：

Here, we just use the method above row-by-row to compute each row of \(R_{top}\) .

这里，我们只是使用上面的方法逐行计算 \(R_{top}\) 的每一行。

And we're done.

我们就完成了。

An astute reader may notice a vague resemblance to ring signatures , at least for the 1-of-2 case: you compute one of the two terms "the easy way", and you compute the other value to match (which you're "not supposed to be able to do") using a trapdoor.

精明的读者可能会注意到与环签名的模糊相似之处，至少对于二分之一的情况是这样：您“简单的方法”计算两个术语之一，并使用活板门计算另一个要匹配的值（您“不应该能够做到”）。

For clarity, note that the \(R\) in the trapdoor is never given out, not even to the decryptor.

为了清楚起见，请注意陷门中的 \(R\) 永远不会给出，甚至不会给出给解密者。

\(R_f = {R_{top} \atop R_{bottom}}\) is what's given to the decryptor.

\(R_f = {R_{top} \atop R_{bottom}}\) 是提供给解密器的内容。

The main limitation of this scheme is on circuit depth : each multiplication increases error by a constant amount, and so the deeper the circuits, the bigger the values and the matrices need to be to compensate.

该方案的主要限制在于电路深度：每次乘法都会使误差增加恒定量，因此电路越深，需要补偿的值和矩阵就越大。

You can do arbitrarily deep circuits in theory, but if you try, the overhead of making the ciphertexts big enough to handle the error blows up.

理论上你可以做任意深度的电路，但如果你尝试，使密文足够大以处理错误的开销就会爆炸。

This is what leads to the depth limitation in basic succinct FE, which the wrapper we will discuss later removes.

这就是导致基本简洁有限元中深度限制的原因，我们稍后将讨论的包装器将其删除。

Surprisingly, at least for this bit, we're now done the hard math.

令人惊讶的是，至少对于这一点，我们现在已经完成了困难的数学计算。

The next section is going to be just stitching together lego bricks.

下一部分将只是将乐高积木拼接在一起。

Authority generates keys for a function with circuit \(C\) , they generate circuit-independent public params (including a public key) as well a decryption key which depends on \(C\)

权威机构使用电路 \(C\) 为函数生成密钥，它们生成与电路无关的公共参数（包括公钥）以及依赖于 \(C\) 的解密密钥

A particular property that we'll be after is succinctness : like we saw with ABE, encrypting must be cheap, even if the circuit is large .

我们要追求的一个特殊属性是简洁性：就像我们在 ABE 中看到的那样，即使电路很大，加密也必须很便宜。

Here's the process (following the GKP+13 construction ).

这是流程（遵循 GKP+13 建设）。

First the authority's work.

首先是机关工作。

The authority chooses the circuit \(C\) that they are generating parameters for.

当局选择他们为其生成参数的电路\(C\)。

An alternative to issuing \(2*w\) ABE encryptions is to modify the ABE so that it simultaneously encrypts two messages, one decryptable only if \(C(tag) = 0\) and the other only if \(C(tag) = 1\) .

发出 \(2*w\) ABE 加密的另一种方法是修改 ABE，以便它同时加密两条消息，一条消息仅当 \(C(tag) = 0\) 时才可解密，另一条消息仅当 \(C(tag) = 1\) 时才可解密。

This adds some more complexity, but saves 2x overhead.

这增加了一些复杂性，但节省了 2 倍的开销。

Now, the encryptor's work.

现在，加密器的工作。

The encryptor has a value \(x\) that they want to encrypt.

加密器有一个他们想要加密的值\(x\)。

The decryptor does the ABE decryption procedure on the encrypted \(L_{in}\) labels using \(E_x\) as the tag, and thereby learn the input labels.

解密器使用\(E_x\)作为标签对加密的\(L_{in}\)标签进行ABE解密过程，从而学习输入标签。

They run the garbling and get the output.

他们运行乱码并获得输出。

This one is a one-liner.

这是一首单行诗。

Instead of ABE-encrypting to \(C\) , you ABE-encrypt to the function that takes as input \(x\) and generates a garbled circuit for \(C(x)\) (using eg.

您不是对 \(C\) 进行 ABE 加密，而是对以 \(x\) 作为输入的函数进行 ABE 加密，并为 \(C(x)\) 生成乱码电路（例如使用

\(hash(x)\) as the randomness for the garbling).

\(hash(x)\) 作为乱码的随机性）。

Garbled circuit generation is parallelizable, so this is low-depth even if the circuit is high-depth.

乱码电路的生成是可并行的，因此即使电路深度很高，这也是低深度的。

The decryptor runs low-depth FE to obtain the garbled circuit including the appropriate input labels, and then walks the garbled circuit in the clear to obtain the outputs.

解密器运行低深度 FE 以获得包含适当输入标签的乱码电路，然后以明文方式遍历乱码电路以获得输出。

And, we're done succinct functional encryption!

而且，我们已经完成了简洁的功能加密！

To recap the whole thing, here's our original diagram again:

为了回顾整个事情，这又是我们的原始图表：

Generator chooses parameters for a hidden function with circuit \(C\) that has a single-bit output.

生成器为具有单位输出的电路 \(C\) 的隐藏函数选择参数。

They generate an encoding of that function.

他们生成该函数的编码。

This step is allowed to take as long as evaluating \(C\) on all possible inputs or even longer, but the output must be smaller than the truth table (the set of outputs for all possible inputs)

此步骤允许花费与在所有可能的输入上评估 \(C\) 一样长的时间甚至更长，但输出必须小于真值表（所有可能输入的输出集）

Evaluator evaluates the encoding to learn \(C(x)\) for any input \(x\) .

评估器评估编码以学习任何输入 \(x\) 的 \(C(x)\) 。

"XiO" technically stands for "exponentially-(in)efficient indistinguishability obfuscation", but it's best not to think of it as being obfuscation at all.

“XiO”在技术上代表“指数效率的不可区分混淆”，但最好根本不要将其视为混淆。

Instead, it's a way to compress a piece of data, in the special case where the data is generated by a program that is much smaller than the data, and where you want to hide the program.

相反，它是一种压缩数据的方法，在特殊情况下，即数据是由比数据小得多的程序生成的，并且您想要隐藏该程序。

It's designed for "thunks" (zero-input functions) that output \(n\) bits, not what you might intuitively think of as "actual functions".

它是为输出 \(n\) 位的“thunk”（零输入函数）而设计的，而不是您直观地认为的“实际函数”。

Most known constructions of XiO to date build upon a primitive called split-FHE .

迄今为止，大多数已知的 XiO 结构都建立在称为 split-FHE 的原语之上。

Here's a definition of split-FHE:

这是 split-FHE 的定义：

Generator is assumed to have the FHE encryption and decryption keys, and a specific ciphertext that they have in mind.

假设生成器具有 FHE 加密和解密密钥，以及他们所考虑的特定密文。

We assume an encryption scheme that can support efficiently encrypting vectors (and not just single bits).

我们假设一种加密方案可以支持有效地加密向量（而不仅仅是单个位）。

Given a specific ciphertext \(C\) encoding a specific vector \(v\) , they generate a hint \(h\) , which is much smaller than \(v\) .

给定编码特定向量 \(v\) 的特定密文 \(C\) ，它们会生成一个提示 \(h\) ，该提示比 \(v\) 小得多。

Decryptor , given \(C\) and \(h\) , can use the hint to decrypt \(C\) to get \(v\) , but cannot use it to decrypt any other ciphertext or learn anything else about the FHE keys or the computation that \(C\) was derived from.

给定 \(C\) 和 \(h\) ， Decryptor 可以使用提示解密 \(C\) 以获得 \(v\) ，但不能使用它来解密任何其他密文或了解有关 FHE 密钥或派生 \(C\) 的计算的任何其他信息。

If we are encoding a thunk with output size \(n\) , we treat it as a function \(Q\) that takes an index \(i \in \{1...n\}\) , and outputs the i'th bit produced by the thunk.

如果我们编码输出大小为 \(n\) 的 thunk，我们将其视为函数 \(Q\)，该函数采用索引 \(i \in \{1...n\}\) ，并输出 thunk 产生的第 i 位。

We split up the input space into \(\sqrt{n}\) buckets each of size \(\sqrt{n}\) .

我们将输入空间分成 \(\sqrt{n}\) 个桶，每个桶的大小为 \(\sqrt{n}\) 。

For each bucket, we FHE-encrypt (using GSW) each index inside that bucket (eg.

对于每个存储桶，我们使用 FHE 加密（使用 GSW）该存储桶内的每个索引（例如

\(1...\sqrt{n}\) for the first, \(\sqrt{n}+1 ...

\(1...\sqrt{n}\) 为第一个，\(\sqrt{n}+1 ...

2*\sqrt{n}\) for the second), and run \(Q\) on each index.

2*\sqrt{n}\) 为第二个），并在每个索引上运行 \(Q\)。

Then, we use a special technique to convert the \(\sqrt{n}\) ciphertexts into a packed ciphertext that holds all values.

然后，我们使用特殊技术将 \(\sqrt{n}\) 密文转换为包含所有值的打包密文。

And finally, we release a constant-size hint for it.

最后，我们为其发布了一个恒定大小的提示。

The XiO is the set of all \(\sqrt{n}\) constant-size hints.

XiO 是所有 \(\sqrt{n}\) 常量大小提示的集合。

In reality, the three are connected.

事实上，这三者是相互联系的。

We don't ever use the packing in any context other than hint generation and hint-based decryption, and the changes to GSW make it unable to decrypt in any way other than hint-based decryption, so we may as well treat it all as one algorithm.

除了提示生成和基于提示的解密之外，我们不会在任何上下文中使用打包，并且对 GSW 的更改使其无法以除基于提示的解密之外的任何方式进行解密，因此我们不妨将其全部视为一种算法。

Let's go through these in turn, following the WW21 protocol .

让我们按照 WW21 协议依次讨论这些内容。

Remember plain GSW: \(C = A + \frac{q}{2} * m * G\) , where the freshly-generated-per-message \(A\) satisfies \(s * A = e\) for low-norm \(e\) .

记住简单的 GSW： \(C = A + \frac{q}{2} * m * G\) ，其中新生成的每条消息 \(A\) 满足低范数 \(e\) 的 \(s * A = e\) 。

Here, we modify the GSW to: \(C = A * R + \frac{q}{2} * m * G + E\) , where \(A\) is a fixed "public key" matrix, and \(R\) is randomly chosen freshly each time but is low-norm.

在这里，我们将 GSW 修改为： \(C = A * R + \frac{q}{2} * m * G + E\) ，其中 \(A\) 是固定的“公钥”矩阵，而 \(R\) 每次都是随机选择的，但是低范数的。

\(E\) is a new error introduced to protect \(R\) from being revealed, also randomly chosen freshly each time but low-norm.

\(E\) 是为了保护 \(R\) 不被泄露而引入的新错误，也是每次随机选择的，但低范数。

Importantly, \(A\) is tall and narrow, and \(R\) is wide and short.

重要的是，\(A\) 又高又窄，而 \(R\) 又宽又短。

The small dimensions of the two need to match.

两者的小尺寸需要匹配。

This is important, because this dimension is what determines the size of the hint.

这很重要，因为这个维度决定了提示的大小。

The hint can't just be one value, it needs to have some width to preserve LWE security, but it can be much smaller than the sizes of the matrices, and hence the vectors it will be helping to decrypt.

提示不能只是一个值，它需要具有一定的宽度以保护 LWE 安全性，但它可以比矩阵的大小小得多，因此它可以帮助解密向量。

Also importantly, the multiply-by-s trick used to decrypt gets blown up by the new error matrix, so there is no longer a working "decryption key" .

同样重要的是，用于解密的乘以 s 技巧会被新的误差矩阵放大，因此不再有有效的“解密密钥”。

The ONLY thing you can do to ciphertexts, other than evaluating them even more, is something like the hint-based decryption mechanism.

除了进一步评估密文之外，您对密文唯一能做的就是基于提示的解密机制。

For this reason, the authors are clear to call it a homomorphic commitment scheme , and not homomorphic encryption.

因此，作者明确将其称为同态承诺方案，而不是同态加密。

Suppose you have several ciphertexts of the above form: \(C_1\) , \(C_2\) ...

假设您有几个上述形式的密文： \(C_1\) , \(C_2\) ...

\(C_k\) .

\(C_k\) 。

They all share the same \(A\) , but have different \(R_i\) matrices, and different \(m_i\) (messages).

它们都共享相同的 \(A\) ，但具有不同的 \(R_i\) 矩阵和不同的 \(m_i\) （消息）。

Let \(u_i\) to be the vector that has the same width as \(R\) and \(G\) , and that is all zeroes, except it's a 1 at the \(log(q) * i\) position (eg.

令 \(u_i\) 为与 \(R\) 和 \(G\) 具有相同宽度的向量，除了在 \(log(q) * i\) 位置处为 1 之外，它全部为零（例如

if \(q=16\) , for \(i=1\) , it's \([\ 0\ 0\ 0\ 1\ |\ 0\ 0\ 0\ 0\ |\ 0\ 0\ ...\ ]\) (separators added for clarity).

如果 \(q=16\) ，对于 \(i=1\) ，它是 \([\ 0\ 0\ 0\ 1\ |\ 0\ 0\ 0\ 0\ |\ 0\ 0\ ...\ ]\) （为了清楚起见添加了分隔符）。

Notice that the \(log(q) * i\) position is exactly where the i'th row of the \(G\) matrix has its highest value.

请注意，\(log(q) * i\) 位置正是 \(G\) 矩阵的第 i 行具有最高值的位置。

If \(q\) is not a power of 2, you have to do something slightly more complicated: instead of the i'th block of \(log(q)\) being many zeroes followed by a one, it must be the least-significant-bit-first binary encoding of \(\frac{q}{2}\) .

如果 \(q\) 不是 2 的幂，则必须做一些稍微复杂的事情：而不是 \(log(q)\) 的第 i 个块是许多零后跟一个 1，它必须是 \(\frac{q}{2}\) 的最低有效位优先二进制编码。

The former is the \(q = 2^k\) special case of the latter.

前者是后者的\(q = 2^k\)特例。

That's it.

就是这样。

To compute the raw hint , we "track" the \(R\) matrices through the additions and multiplications in the FHE along with the ciphertexts (exercise to the reader: go through the "track the \(R\) " algebra for ADD and MUL yourself; it follows closely the same \(G\) and \(G^{-1}\) based approach used with \(C\) to keep error low-norm), and then apply the exact same procedure to \(R\) : \(r_f = R_1 * u_1 + R_2 * u_2 + ...

为了计算原始提示，我们通过 FHE 中的加法和乘法以及密文“跟踪”\(R\) 矩阵（读者练习：自己完成 ADD 和 MUL 的“跟踪 \(R\)”代数；它严格遵循与 \(C\) 一起使用的基于 \(G\) 和 \(G^{-1}\) 的方法，以保持错误低范数），然后应用完全相同的过程到\(R\)：\(r_f = R_1 * u_1 + R_2 * u_2 + ...

+ R_k * u_k\)

+ R_k * u_k\)

Now, remember that \(C_i = A * R_i + m * G + E_i\) , so if you subtract \(A * R_i\) from \(C_i\) , you get \(m * G + E_i\) , which has \(m\) in \(log(q)\) adjacent positions on each row of the matrix.

现在，请记住 \(C_i = A * R_i + m * G + E_i\) ，因此如果从 \(C_i\) 中减去 \(A * R_i\) ，则会得到 \(m * G + E_i\) ，其中在矩阵每行的 \(log(q)\) 个相邻位置上有 \(m\) 。

Here, though, we are dealing with many different \(R_i\) ' values, and we want to have a single operation that reveals all \(m_i\) 's at once.

不过，在这里，我们正在处理许多不同的 \(R_i\) ' 值，并且我们希望有一个操作可以一次性显示所有 \(m_i\) ' 值。

To do this, we are employing a trick: in the i'th row, we are using \(R_i\) .

为此，我们采用了一个技巧：在第 i 行中，我们使用 \(R_i\) 。

So if you subtract \(c_f - A * r_f\) , the i'th row of the result will correctly cancel out \(A * R_i\) , and give you the value \(m_i * q/2\) that you need (plus an error).

因此，如果您减去 \(c_f - A * r_f\) ，结果的第 i 行将正确抵消 \(A * R_i\) ，并给出您需要的值 \(m_i * q/2\) （加上一个错误）。

There is only one remaining problem: the raw hint \(r_f\) on its own is not a secure hint.

只剩下一个问题：原始提示 \(r_f\) 本身并不是一个安全提示。

It reveals too much information about the \(R_i\) matrices, which are meant to be private.

它揭示了太多有关 \(R_i\) 矩阵的信息，这些信息本应是私有的。

To deal with this problem, we mask it:

为了解决这个问题，我们将其屏蔽：

\(= (A * r_f + m * G + e_1) + (A * s + e_2) - (A * r_f + A * s)\)

\(= (A * r_f + m * G + e_1) + (A * s + e_2) - (A * r_f + A * s)\)

For security, the error in the sample must be much larger than the other errors, so as to fully hide information about them.

为了安全起见，样本中的错误必须远大于其他错误，这样才能完全隐藏有关它们的信息。

So we have two layers of scale separation: the sample error is large enough to smudge the other error, and the message is large enough to avoid being corrupted by the sample error.

因此，我们有两层尺度分离：样本误差足够大，可以掩盖另一个误差，而消息足够大，可以避免被样本误差破坏。

This second version of the scheme is secure, but it has a new big problem: the sample \(b\) is full-width, not short like the hint.

该方案的第二个版本是安全的，但它有一个新的大问题：样本 \(b\) 是全角的，而不是像提示那样短。

So we make one more modification: instead of releasing \(b\) directly, we release a gadget that creates it.

因此我们又做了一项修改：我们不直接释放 \(b\)，而是释放一个创建它的小工具。

The generator makes a fresh encryption of a \(seed\) (as in, a value that you generate hashes from), and releases an FHE encryption of the seed: \(A * R_i + seed[i] * G + E_i\) for each bit in the seed

生成器对 \(seed\)（例如，从中生成哈希值的值）进行新的加密，并为种子中的每个位发布种子的 FHE 加密：\(A * R_i + seed[i] * G + E_i\)

For each bucket \(\beta\) , the generator and the decryptor can both do the following computation:

对于每个桶 \(\beta\) ，生成器和解密器都可以进行以下计算：

Compute \(A * hash(seed, \beta) + e_\beta\) inside FHE (where \(e\) itself is error generated by taking another \(hash_2(seed, \beta)\) ), and get ciphertexts: \(C_i = A * R_i + m_i * \frac{q}{2} + E_i\) , where \(m_i\) is the i'th bit of \(A * hash(seed, \beta) + e_\beta\) .

计算 FHE 内的 \(A * hash(seed, \beta) + e_\beta\) （其中 \(e\) 本身是通过另一个 \(hash_2(seed, \beta)\) 生成的错误），并得到密文： \(C_i = A * R_i + m_i * \frac{q}{2} + E_i\) ，其中 \(m_i\) 是 \(A * 的第 i 位哈希（种子，\ beta）+ e_ \ beta \）。

Apply the packing procedure we described above, but with a \(u_i\) for each of the \(k * log(q)\) columns, not just the \(k\) columns at multiples of \(log(q)\) minus one.

应用我们上面描述的打包过程，但对每个 \(k * log(q)\) 列使用 \(u_i\)，而不仅仅是 \(k\) 列，其值为 \(log(q)\) 减一的倍数。

For clarity, we'll treat this as a sum with two indices: the within-block index \(0 \le t \lt log(q)\) , and the block index \(0 \le j \lt k\) .

为了清楚起见，我们将其视为具有两个索引的总和：块内索引 \(0 \le t \lt log(q)\) 和块索引 \(0 \le j \lt k\) 。

We'll treat everything as zero-indexed here to make the math cleaner.

我们将在这里将所有内容视为零索引，以使数学更加清晰。

The output of the packing procedure is \(c_g = A * r_g + A * hash(seed, \beta) + e_\beta + e_g\) .

打包过程的输出为 \(c_g = A * r_g + A * hash(seed, \beta) + e_\beta + e_g\) 。

Notice that \(A * hash(seed, \beta) + e_\beta\) lives in the place where normally \(m * \frac{q}{2}\) would live.

请注意，\(A * hash(seed, \beta) + e_\beta\) 位于通常 \(m * \frac{q}{2}\) 所在的位置。

This is a direct result of the way that we modified the packing procedure above.

这是我们修改上述打包程序的直接结果。

The expression for \(c_g\) can be rewritten as \(c_g = A * (r_g + hash(seed,\beta)) + e\)

\(c_g\) 的表达式可以重写为 \(c_g = A * (r_g + hash(seed,\beta)) + e\)

The generator can compute \(r_g + hash(seed,\beta)\) in the clear, the evaluator can't.

生成器可以清楚地计算 \(r_g + hash(seed,\beta)\)，而评估器则不能。

So the generator uses this as the \(s\) value that they mix in to the hint.

因此生成器使用它作为它们混合到提示中的\(s\)值。

The decryptor's calculation is the same as before, except that they don't receive \(c_f\) from the generator; they generate it themselves using the method above.

解密器的计算与之前相同，只是它们不接收来自生成器的\(c_f\)；他们使用上述方法自己生成它。

The math for why it cancels is also exactly the same.

其取消原因的数学原理也完全相同。

The papers use \(prf\) ("pseudorandom function") to refer to the hash.

论文使用 \(prf\)（“伪随机函数”）来指代哈希值。

This just means that the hash needs to have strong randomness properties (much stronger than collision resistance, but weaker than random oracle); if you trust hashes to satisfy the random oracle model, then you can safely think \(prf = hash\) everywhere.

这只是意味着哈希需要具有很强的随机性属性（比抗碰撞性强得多，但比随机预言弱）；如果你相信哈希值能够满足随机预言模型，那么你就可以放心地认为 \(prf = hash\) 无处不在。

Evaluation requires re-doing the execution just for one particular bucket, then using the hint to decrypt the final vector, and finally taking out the value(s) you need from that bucket (in the obfuscation use case, the decryptor is taking out all values from all buckets).

评估需要仅针对一个特定存储桶重新执行，然后使用提示解密最终向量，最后从该存储桶中取出所需的值（在混淆用例中，解密器将从所有存储桶中取出所有值）。

There is one further optimization to maximize efficiency while guaranteeing provable security.

还有一项进一步的优化可以最大限度地提高效率，同时保证可证明的安全性。

The XiO is \(O(\sqrt{n})\) in the size \(n\) of the thunk it's encoding, but it requires publishing trusted setup parameters of size \(n\) (these exist for a technical reason: the function that generates the \(A * s + e\) samples that compensate for the hint needs to have a never-used path that accepts and uses fully random values, this allows for the security proof).

XiO 的大小为 \(O(\sqrt{n})\)，其编码的 thunk 大小为 \(n\)，但它需要发布大小为 \(n\) 的受信任设置参数（这些参数的存在是出于技术原因：生成补偿提示的 \(A * s + e\) 样本的函数需要有一个从未使用过的路径来接受和使用完全随机值，这允许安全证明）。

This trusted setup is length \(n\) .

此可信设置的长度为 \(n\) 。

If you split the XiO into \(\approx n^{\frac{1}{3}}\) separate XiOs, then the size of the XiO goes up to \(\approx n^{\frac{2}{3}}\) but the trusted setup (which can be reused by all of them) goes down to \(\approx n^{\frac{2}{3}}\) too.

如果将 XiO 拆分为 \(\approx n^{\frac{1}{3}}\) 个单独的 XiO，则 XiO 的大小会上升到 \(\approx n^{\frac{2}{3}}\)，但可信设置（可以由它们所有人重用）也会下降到 \(\approx n^{\frac{2}{3}}\)。

All parts of the obfuscation pipeline other than XiO can be justified with fairly "standard" lattice-based assumptions.

除 XiO 之外的混淆管道的所有部分都可以通过相当“标准”的基于晶格的假设来证明是合理的。

Ultimately, all cryptography is just a guess that some mathematical problem is "actually hard" and it's not just that we've been too dumb to solve it so far but we might figure it out next year.

最终，所有密码学都只是对某些数学问题“实际上很难”的猜测，这不仅是因为我们到目前为止太笨而无法解决它，而且我们明年可能会解决它。

But some guesses are more well-founded than others.

但有些猜测比其他猜测更有根据。

Among all quantum-safe primitives, the basic LWE assumption underlying lattices is typically considered less robust than hashes, but more robust than almost anything else (including more complex lattice assumptions).

在所有量子安全原语中，格子背后的基本 LWE 假设通常被认为不如哈希健壮，但比几乎任何其他东西（包括更复杂的格子假设）都更健壮。

But with all existing XiO primitives there is a problem.

但所有现有的 XiO 原语都存在一个问题。

The design above is not strictly provable under the lattice assumption.

上述设计在格假设下不能严格证明。

It is made provable under the assumption of the form "if you publish \(A * s + e\) -style ‘samples', and also publish a little bit of extra information , then we're still fine".

它是在以下形式的假设下证明的：“如果你发布 \(A * s + e\) 式的‘样本’，并且还发布了一些额外的信息，那么我们仍然没问题”。

But there's a problem: such assumptions have been broken before, and ultimately got broken here.

但有一个问题：这样的假设以前就被打破过，而且最终在这里也被打破了。

In 2013, an early candidate for multilinear maps (a very strong primitive that, if we had it, would make obfuscation far easier) was published in CLT13 .

2013 年，多线性映射的早期候选者（一个非常强大的原语，如果我们拥有它，将使混淆变得更加容易）在 CLT13 中发布。

In 2015, however, it was broken .

然而到了2015年，它就被打破了。

The object that CLT13 released was \(p_{zt} \approx z * \frac{h}{g}\) .

CLT13 释放的对象是 \(p_{zt} \approx z * \frac{h}{g}\) 。

Ciphertexts are of the form \(c = \frac{a + gr}{z}\) .

密文的形式为 \(c = \frac{a + gr}{z}\) 。

If you multiply a ciphertext of \(a=0\) with \(p_{zt}\) , you get \(c * p_{zt} = \frac{gr}{z} * z * \frac{h}{g} = r * h\) .

如果将密文 \(a=0\) 与 \(p_{zt}\) 相乘，则得到 \(c * p_{zt} = \frac{gr}{z} * z * \frac{h}{g} = r * h\) 。

\(r\) and \(h\) were both very "small" values (much smaller than the modulus), and so the two multiplied together will also be much smaller than the modulus.

\(r\) 和 \(h\) 都是非常“小”的值（比模数小得多），因此两者相乘也会比模数小得多。

Thus \(p_{zt}\) functions as a "zero check" key, which is what allows you to do pairing-check-style operations on lattice ciphertexts (which unlike pairings, can multiply to arbitrarily high depths if you scale the parameters).

因此 \(p_{zt}\) 充当“零检查”密钥，这允许您对格密文进行配对检查式操作（与配对不同，如果缩放参数，它可以乘以任意高的深度）。

The problem: \(h * r\) reveals an exact expression in the underlying secrets of the scheme over the integers, an so if you have enough such values, you can perform some matrix operations and recover the secrets.

问题：\(h * r\) 揭示了该方案的底层秘密在整数上的精确表达式，因此如果您有足够的此类值，您可以执行一些矩阵运算并恢复秘密。

The HPLS conjecture, the core new assumption in WW21, has what is on surface also a way to leak what is "just the error":

HPLS 猜想是 WW21 中的核心新假设，它表面上看也是一种泄露“只是错误”的方法：

Notice that even if extracting \(e\) is fatal, WW21's security still has another line of defense: the adversary doesn't learn either one of the fatal secrets ( \(r_f\) and \(s\) ), they learn the sum of the two, and maybe there aren't any useful combination attacks that start from that sum.

请注意，即使提取 \(e\) 是致命的，WW21 的安全性仍然有另一道防线：对手不会了解任何一个致命秘密（ \(r_f\) 和 \(s\) ），他们会了解两者的总和，并且可能没有任何从该总和开始的有用的组合攻击。

But even extracting \(e\) probably is fine.

但即使提取 \(e\) 也可能没问题。

The attack in HJL21 , which broke the HPLS assumption, managed to do one specific thing: they figured out how to adversarially construct circuits in such a way that the lowest-order bit of the error (which survives "smudging" tricks that normally protect schemes like this) encodes a variable that outputs whether the execution is "real" or a "simulated" execution used in the proving process.

HJL21 中的攻击打破了 HPLS 假设，成功地做了一件具体的事情：他们弄清楚了如何以这样一种方式来对抗性地构建电路，即错误的最低位（在通常保护此类方案的“污点”技巧中幸存下来）编码一个变量，该变量输出执行是“真实”执行还是证明过程中使用的“模拟”执行。

To summarize:

总结一下：

Hence, even if the assumption is broken in limited cases, the security of WW21 is probably fine.

因此，即使这个假设在有限的情况下被打破，WW21 的安全性也可能是好的。

A new protocol was published in 2025 , which adds some extra complexity to the "help the decryptor discover samples of the offset to the hint" piece of the WW21 technique to make it depend on lattice assumptions that are more limited than HPLS, but are still more aggressive than plain LWE.

2025 年发布了一个新协议，它为 WW21 技术的“帮助解密器发现提示偏移样本”部分增加了一些额外的复杂性，使其依赖于比 HPLS 更有限的格假设，但仍然比普通 LWE 更具侵略性。

In particular, the assumption that HJL25 uses falls into a framework of "only publish objects where the secret-bearing part gets mod-q wrapped" (which excludes both making available "raw error" and CLT13's \(r * h\) ).

特别是，HJL25 使用的假设属于“仅发布包含秘密部分被 mod-q 包装的对象”的框架（其中排除了可用的“原始错误”和 CLT13 的 \(r * h\) ）。

This is not as conservative as plain LWE, but it is a meaningful improvement.

这并不像普通的 LWE 那样保守，但它是一个有意义的改进。

The space between "plain LWE" and "the secret-bearing part must be mod-q wrapped" contains assumptions like circular security, as well as the assumption in HJL25.

“普通 LWE”和“秘密承载部分必须采用 mod-q 包装”之间的空间包含循环安全性等假设以及 HJL25 中的假设。

There are counterexamples to assumptions of this type, but they are highly contrived, and real protocols based on these types of assumptions have proven secure so far.

这种类型的假设有反例，但它们是高度人为的，并且基于这些类型假设的实际协议迄今为止已被证明是安全的。

One analogy you might have is to other "idealized black box" assumptions:

您可能会有的一个类比是其他“理想化黑匣子”假设：

The ROM has so far proven fine in practice, but researchers have designed signature schemes that are provably secure in the ROM but easily attackable if instantiated with any real hash algorithm .

迄今为止，ROM 在实践中已被证明是良好的，但研究人员设计的签名方案在 ROM 中被证明是安全的，但如果使用任何真正的哈希算法实例化，则很容易受到攻击。

And the generic-group model is known to be false in a few cases, most notably order-finding via Schoof's algorithm , and pairings .

众所周知，通用组模型在某些情况下是错误的，最明显的是通过 Schoof 算法进行的排序和配对。

Elliptic curve security rests on a shaky foundation that you can violate the generic-group model in those two ways, but not any more harmful ways .

椭圆曲线安全性建立在一个不稳定的基础上，您可以通过这两种方式违反通用组模型，但不能以任何其他有害的方式。

The one family of protocols that proves iO entirely from "standard" assumptions is JLS20 and descendants, but these are not quantum-safe.

完全从“标准”假设证明 iO 的协议系列是 JLS20 及其后代，但这些协议不是量子安全的。

Summary: cryptographic assumptions are a complicated zoo, and there are no absolutes, only different comfort levels.

总结：密码学假设是一个复杂的动物园，没有绝对的，只有不同的舒适度。

Another important note is that if we want to be provably reducible to these security assumptions, then the security proof of the obfuscation of a \(k\) -bit-input program needs to "walk over" all possible \(2^k\) inputs.

另一个重要的注意事项是，如果我们想要可证明地简化为这些安全假设，那么 \(k\) 位输入程序混淆的安全证明需要“遍历”所有可能的 \(2^k\) 输入。

For each input, you consume a little bit of security margin.

对于每个输入，您都会消耗一点安全裕度。

Thus, the proof is consuming security margin potentially way more than \(2^{128}\) times.

因此，证明消耗的安全裕度可能超过 \(2^{128}\) 倍。

For this reason, all of these obfuscation protocols require the LWE parameters to be subexponentially secure , which means the ciphertexts are many thousands of times larger than regular LWE ciphertexts (and because of the stacked nature of the protocol, this "many thousands" itself compounds on itself several times).

因此，所有这些混淆协议都要求 LWE 参数是次指数安全的，这意味着密文比常规 LWE 密文大数千倍（并且由于协议的堆叠性质，这个“数千”本身会复合多次）。

If you wish, you can "yolo and ignore this", the same way that recursive STARK protocols yolo and ignore the fact that they require the hash function to simultaneously be a random oracle and be a concrete thing that can be instantiated by a circuit.

如果你愿意，你可以“yolo 并忽略它”，就像递归 STARK 协议 yolo 并忽略这样一个事实：它们要求哈希函数同时是一个随机预言机，并且是一个可以由电路实例化的具体事物。

Doing that is plausibly okay, but if you do enough plausibly okay things for efficiency, you run into the philosophical question: why even bother to fight so hard to make obfuscation provably secure under standard assumptions, instead of adopting one of the other approaches (eg.

这样做似乎是可以的，但是如果你为了效率做了足够多看似合理的事情，你就会遇到一个哲学问题：为什么还要费尽心思去努力使混淆在标准假设下证明安全，而不是采用其他方法之一（例如

diamond iO ) that are provably secure under aggressive assumptions but have far better efficiency?

Diamond iO）在激进的假设下被证明是安全的，但效率更高？

In summary, the answer to "what cryptographic assumptions do you need to make a working obfuscation protocol" is:

总之，“需要什么密码学假设才能制定有效的混淆协议”的答案是：

Finally, another obvious but important thing to highlight: the security of obfuscated programs depends on trusted setups in a whole bunch of places, and so we are very far from being able to do fully trustless obfuscation (ie.

最后，另一个明显但重要的事情需要强调：混淆程序的安全性取决于很多地方的可信设置，因此我们距离能够进行完全不可信的混淆（即。

generate programs with internal secrets in such a way that even the obfuscator does not know the secret).

以即使混淆器也不知道秘密的方式生成具有内部秘密的程序）。

The best that we can do is replace the single party trusted setup with an N-party trusted setup.

我们能做的最好的事情就是用 N 方可信设置替换单方可信设置。

We define a generator \(G(H, s)\) which returns a two-input program \(F(\beta, x)\) with the following behavior:

我们定义一个生成器\(G(H, s)\)，它返回一个具有以下行为的双输入程序\(F(\beta, x)\)：

By convention, we will say, \(G(G, x) = G_x\) (note: this is using a trick similar to the Y-combinator ) and \(hash(s_i, r_{i+1},1) = s_{i+1}\) .

按照惯例，我们会说， \(G(G, x) = G_x\) （注意：这是使用类似于 Y 组合器的技巧）和 \(hash(s_i, r_{i+1},1) = s_{i+1}\) 。

Each participant would also run their output \(G_{s_k}\) with \(\beta = 0\) on \(P\) to obfuscate \(P\) with \(s_k\) (the mix of all previous secrets) as the secret, and publish this obfuscation.

每个参与者还将在 \(P\) 上运行其输出 \(G_{s_k}\) 和 \(\beta = 0\)，以使用 \(s_k\) （所有先前秘密的混合）作为秘密来混淆 \(P\)，并发布此混淆。

Only the last participant's obfuscation will actually mix in everyone's secrets, but in our model, we are assuming that participants come in one after the other, and none of them knows if they will be the last.

只有最后一个参与者的混淆实际上会混合每个人的秘密，但在我们的模型中，我们假设参与者一个接一个地进来，并且没有人知道他们是否会是最后一个。

This way, the setup is universal and updateable , the gold standard for trusted setups .

这样，设置是通用且可更新的，这是可信设置的黄金标准。

And to verify the correctness of each step, each participant would need to make a recursive STARK proving that (i) the previous step was recursive-STARKed, and (ii) they added their randomness correctly.

为了验证每个步骤的正确性，每个参与者都需要进行递归 STARK 证明 (i) 前一步是递归 STARK 的，并且 (ii) 他们正确添加了随机性。

However, this method is extremely expensive: it requires a STARK of obfuscation of obfuscation .

然而，这种方法非常昂贵：它需要 STARK 的混淆。

An open challenge is to figure out the ideal way to do universal and updateable trusted setups for obfuscation.

一个公开的挑战是找出进行通用且可更新的可信设置以进行混淆的理想方法。

Perhaps the most famous fact about these obfuscation protocols is that their runtimes are technically polynomial, but in practice galactic.

也许关于这些混淆协议最著名的事实是它们的运行时间在技术上是多项式的，但实际上是银河系的。

To see why, we just need to look at the full tower again:

要了解原因，我们只需再次查看完整的塔：

The total theoretical overhead here is thus roughly: \(ABE * FHE * GC * XiO * sFE_{enc}\) , where \(XiO\) is mostly FHE.

因此，这里的总理论开销大致为： \(ABE * FHE * GC * XiO * sFE_{enc}\) ，其中 \(XiO\) 大部分是 FHE。

All that per bit in the input.

输入中的所有每一位。

Now, on top of all that , the parameter choices for each individual scheme have to be very conservative for subexponential security, adding over 1000x extra overhead at each LWE layer .

现在，最重要的是，每个单独方案的参数选择对于次指数安全性来说必须非常保守，从而在每个 LWE 层增加超过 1000 倍的额外开销。

This is why these schemes are far from practical today; expected runtimes are longer than the lifetime of the universe.

这就是为什么这些计划在今天还远远不切合实际。预期的运行时间比宇宙的寿命还要长。

Routes (2) and especially (3) also imply that we get better at battle-testing such assumptions, again perhaps with AI help.

路线（2），特别是路线（3）也意味着我们可以更好地测试这些假设，也许同样是在人工智能的帮助下。

The next posts in this series will talk about what is perhaps the leading construction attempting to do (2), diamond iO , and what is perhaps the leading construction attempting to do (3), local mixing obfuscation .

本系列的下一篇文章将讨论什么可能是尝试做的主要结构（2），钻石 iO，以及可能是尝试做的主要结构（3），局部混合混淆。

If we succeed in either path, the reward is high: there is a real sense in which we will have "solved cryptography": any protocol that can be described using an idealized trusted third party, provided the adversary is allowed to rewind the clock, will be implementable securely.

如果我们在任何一条路径上取得成功，回报都会很高：从真正意义上来说，我们将“解决密码学问题”：只要允许对手倒回时钟，任何可以使用理想化的可信第三方描述的协议都将可以安全地实现。

But getting there is still a formidable challenge.

但实现这一目标仍然是一项艰巨的挑战。