混淆：构建密码学的终极首领（第一部分）

RECODEX · 深度文章 Web3 前沿

特别感谢 Sora Suegami、Janmajaya Mall、Aayush Jain 和 Fun Killer 提供的反馈与审阅。

密码学中迄今设想出的最强大原语是混淆。混淆使你能够把一个程序转换成“加密程序” ，从而你可以在明文输入上运行，并得到与相同的明文输出，但的内部运作机制被隐藏起来。通常使用的精确定义是不可区分混淆（iO）：如果给你两个不同程序的混淆版本，而它们具有相同的功能，你就无法分辨哪个对应哪个。实际上，它隐藏的是代码，而不是数据。

混淆之所以强大，是因为它非常接近一种通用“无须信任的可信第三方”的理论理想：

《神级协议》（Nick Szabo），1997

密码学协议通常会先通过设想一种依赖可信第三方的协议来描述：这个第三方能够看到所有人的消息并诚实地作出回应，随后再设法在不依赖这种信任的情况下实现同样的功能。

加密很简单：“可信第三方”实际上相当于一个邮政系统，接收“我希望[recipient]看到[message]”这样的指令，然后将消息转交给接收者。
零知识证明取代的是这样一种可信第三方：它接收你的数据，对其进行检查，然后向任何提出询问的人确认这些数据在某种意义上是正确的。

混淆（严格来说，是混淆加上哈希）使你能够为几乎任何协议构造一个模拟的可信第三方，因此它既可以替代上述两者，也能实现更多得多的功能。只有一个主要例外：混淆后的程序无法阻止自身被复制，因此不能处理像货币这样“有状态”的事务——而这恰恰是区块链最适合填补的空白。

因此，如果你拥有混淆和区块链，就能做出一些近乎魔法般的事情。比如，一个安全、私密且抗串通的投票系统，几乎不需要任何信任假设——无需任何 M-of-N 门限委员会。或者，基本上可以实现这份 2014 年清单上的任何内容，同样无需任何 M-of-N 信任假设。

一种相当通用的方法，是把混淆与区块链结合起来，从而构造出某种非常接近“无需信任的可信第三方”的东西

那么，问题出在哪里？事实证明，要做出一种安全的混淆形式，真的、真的非常难。

数十年来，不安全的混淆一直是一项传统做法：人们通过打乱已编译程序中的逻辑，使外界更难看清其中发生了什么——坦率地说，这往往是为了防止用户修改游戏等专有程序。这相当于加密领域中的凯撒密码之类手段——而且就像凯撒式密码一样，它也经常被攻破。

因此，几十年来，人们也一直在尝试构建一种能够从数学上证明其安全性的混淆协议。但几乎从一开始，这条路就遇到了问题。2001 年，一项著名结果表明，创造一种理想形式的混淆是不可能的——即对进行混淆，使得运行时，除了通过查询一个 API、针对用户提供的任意返回所能获知的信息之外，不会泄露任何其他内容。其核心思想在于， P 的代码实例总会暴露出至少一些超出其对用户提供输入所产生输出的信息：至少，你可以通过将 P 应用于其自身代码来获知某些内容。

从那时起，研究人员转而尝试证明次优目标：不可区分混淆（iO）。这是一项持续了二十年的工程，其间经历了许多失败的尝试，提出了许多建立在某种尚不存在的基础构件之上的协议构造，也有许多人试图去构建这一构件，而这些尝试同样屡屡受挫，诸如此类。不过，在过去几年里，我们终于迎来了一些好消息：我们已经知道如何在合理的安全假设下实现 iO。

但在好消息之中也有坏消息：它的运行时间简直是“天文级”的。严格来说它是多项式时间，但其过程要层层堆叠许多步骤：“先拿一个有点像全同态加密的东西，再把用于对其求值的电路塞进另一个有点像全同态加密的东西里，然后在普通的全同态加密中对每一位运行一次，生成一个数兆字节大小的中间值，哦对了，我有没有提到，你还得把整套东西再塞进另一个有点像全同态加密的东西里，然后再对输入中的每一位把这一切完整跑一遍？” 因此，这些“某种意义上可证明安全的 iO 方案”的运行时间大约高于 λ ¹⁰ （其中 λ 是“安全参数”，也就是破解该方案所需时间长度的对数；通常会取 λ = 100 或 120）

这里可以讲两个令人抱有希望的故事。其一是，这有点类似于 2010 年时的 SNARK：既然我们现在已经知道它是可行的，聪明人（以及机器人）就会开始为每一个瓶颈想出巧妙的变通办法，把运行时间一个数量级接一个数量级地砍下来，最终我们会得到某种“只”需要在一块重型 GPU 上运行一天的方案（这听起来或许仍然高得难以承受，但对许多有趣的应用来说，其实已经够用了）。其二是，我们会看到围绕同一目标的另一种策略出现更多研究：大幅提升我们构造新的密码学假设的能力，并更善于判断哪些新假设真正有可能是安全的。

如果把更多偏启发式的方法也算进来，那么到目前为止，大致有三类（尚未被淘汰的）混淆协议，可以把它们放在一条“权衡前沿”上：一端是效率，另一端是对安全性假设的大胆程度。

本文将详细介绍迄今为止最“银河级”、但也最严谨的一类：也就是上图中以蓝色标示的那一类。

先提醒一句：接下来会有大量数学内容。混淆之所以困难，是因为它基本上需要把密码学家在过去二十年里发明的几乎所有原语层层叠加起来，唯独不包括那些如果你是区块链开发者通常已经熟悉的原语，比如 SNARK 和 STARK。其底层数学也会有所不同：SNARK 和 STARK 往往涉及大量多项式、哈希和椭圆曲线，而混淆则会大量使用格、向量和矩阵。

符号说明

本文中的表述基于不同论文中的多种方法综合而成，并不完全遵循其中任何一篇的写法。
在某些情况下，记号和术语的选择会与任何一篇底层文章都不完全一致
向量用小写表示，矩阵用大写表示
在这些图示中，灰色文字和虚线可作非正式理解为：“X 依赖于 Y，但你实际上不必把 Y 传入 X，因此 X 的（大小 / 运行时间）可能远小于 Y 的（大小 / 运行时间）”
“iO”指“不可区分混淆”（indistinguishability obfuscation），不同于“IO”表示“输入/输出”（input/output）；两者也都不同于英属印度洋领地，.io 顶级域名正是以此命名

标准流程

如今构建的“可在相当程度上证明安全”的混淆协议，建立在一座已有十年历史的构造高塔之上：AJ15 / BV15 / LPST15 / LPST16 这一谱系。

AJ15 和 BV15 是两篇几乎同时发表的论文，它们都发现了大致相同的方法：在一种称为功能加密的原语之上构建混淆。具体来说，一个“授权方”发布与函数绑定的密钥；一旦这些密钥存在，任何持有加密密钥的人都可以对进行加密，使得任何持有解密密钥的人都能够恢复。LPST15 也提出了类似的方法。但所需的功能加密必须具备当时尚未实现的极强属性。幸运的是，一年后，LPST16 发现了一种建立在类似原语——次线性紧凑随机编码——之上的混淆构造方法，随后又将其建立在一种此前已知的“简洁但不紧凑”的功能加密方案以及一种名为 XiO 的新原语之上。所谓 XiO，是一种混淆形式，其大小仅比直接公布该函数在所有可能输入上的输出表略小一些。此后大部分工作都集中在如何真正实现 XiO 上（尽管有些协议采取了其他路径，例如 JLS20）。

我们将把这部分说明分为三个部分：

假设你已经有一个简洁的 FE 方案和一个 XiO 方案，那么该如何构建一个混淆协议？
如何构建一个简洁的 FE 方案？
如何构建一个 XiO 方案？

假设你已经有了一个简洁 FE 方案和一个 XiO 方案，那么该如何构建一个混淆协议？

在简洁型 FE 和 XiO 之上构建混淆协议有多种方式，它们在高层原则和属性上都大致相同。因此，我将采用 LPST15 设计的一个简化版本。

请注意，在这篇文章中，我们经常会交替使用“函数”和“电路”这两个术语。电路由与门、或门、非门等门电路以及连接它们的导线组成，可用于求值一个函数。为了更直观地理解电路，我推荐阅读这篇解释混淆电路的文章（反正这是我们之后也会用到的一种原语）。

首先，让我们定义简洁函数加密（succinct FE）和 XiO，以便理解这些构件的性质。

下面是简洁型 FE：

授权方生成与电路无关的公共参数，以及针对一个公开已知、输出为单比特的函数、对应电路  的特定解密密钥。

加密方可以使用加密密钥对  进行加密。此步骤的运行时间不会随着  的电路规模增加而增长（或仅略有增长），不过会随输入长度线性扩展。

解密方可以使用解密密钥获知  ，而无法得到关于  的任何其他信息。此步骤的运行时间确实会随着  的电路规模而增长。

换句话说：有人执行可信设置，我加密，你可以解密（这与全同态加密不同：在 FHE 中，任何能够解密的人，也可以解密或的任何其他函数）

功能加密本身并不足以实现混淆，因为：（i）它并不隐藏函数；（ii）每个已发布的加密结果都绑定于一个输入，只能解密出该函数在该单一输入上的求值结果。但它已经让你离目标近了很多。

请注意，更常见的简洁函数加密（FE）定义要求 FE 能够容忍较大的电路规模，而不是较大的电路深度。然而在我们的用法中，确实需要容忍较大的深度。幸运的是，深度无关的简洁 FE 只是在有深度界限的简洁 FE 之上加了一层相当简单的封装（我们稍后会谈到这一点），因此在本文中，我们将直接假设所使用的简洁 FE 也是深度无关的。

现在，来看 XiO：

生成器为一个具有单比特输出的隐藏函数选择参数，该函数对应电路。他们生成该函数的一个编码。允许这一步耗时与对所有可能输入计算一样长，甚至更久，但输出必须小于真值表（即所有可能输入对应输出的集合）。

Evaluator 对编码进行求值，从而对任意输入得知 C(x) 。

XiO 所针对的函数类别，最适合被理解为零输入函数（也称“thunk”），它们会产生一个很大但仍可处理规模的输出。给定一个 thunk ，我们可以将其视为一个函数，即：该函数以索引作为输入，并返回 thunk 输出中的第 i 项。这是同一对象的两种不同视角；在本文中，我们会经常在这两种视角之间来回切换。

例如，你可以设想把一个生成 STARK（约 128–512 kB 大小的密码学证明）的函数，转换成一个以索引为输入、在内部生成 STARK、然后输出该 STARK 第 i 位的函数。XiO 的目标是：它是一种比 STARK 更小的装置（不过请注意：即便是 STARK，也可能仍然太小，无法让已知的 XiO 协议真正将其缩小），让你能够生成该 STARK，同时又无法获知生成它的底层过程的任何其他信息。

现在，我们将简洁函数加密（succinct FE）与 XiO 结合起来，得到一种称为次线性紧凑随机编码的原语：

让我们仔细梳理一下。这里的目标是为创建一种“随机编码”——也就是说，一个能够执行的装置——其规模在渐近意义上小于的运行时间，也在渐近意义上小于其输出规模，并且能够隐藏。

这与随机编码的通常表述略有不同。后者作用于，并隐藏，但不隐藏（例如混淆电路就是这样工作的）；但这正是我们的使用场景所需要的——混淆的核心就是隐藏函数。

我们将要使用的这些原语并不隐藏函数。为此，我们让这些原语所作用的“外层”函数只是一个虚拟机（或“图灵机”）——本质上，就是一个以电路作为输入的函数，因此。对进行求值的电路通常被称为通用电路。这样一来，就只是另一个输入，因此可以被设为私有。

关于渐近复杂度，有一个细微之处：需要被实例化为电路，而电路的大小必须与其运行时间成正比（因为电路不允许循环）。因此，电路的大小必须与的运行时间成正比。幸运的是，简洁 FE 即使在电路规模大且深度很深的情况下，也能实现快速生成。然而，输出的大小以及加密成本可能会随着的大小而扩展。这也正是为什么必须用电路以外的语言来表达（例如图灵机）：即使计算规模变得很大，它的大小也必须保持固定。

我们对简洁函数加密进行可信设置，其中创建者发布公共参数以及针对的解密密钥。这使得任何人都可以对进行加密，从而让其他任何人都能解密，但不会获知或。

为了生成这种随机化编码，构造者将我上文提到的两种原语相互嵌套：他们对的一个简洁型 FE 加密进行 XiO。这个简洁型 FE 加密隐藏了，而且即便运行需要很长时间，它的生成速度仍然很快。但简洁型 FE 并不能压缩输出：如果输出很大，简洁型 FE 加密会更大（而这是这类构造无法避免的局限）。XiO 则将其大小重新压了下来。构造者设计了一个电路，输出该简洁型 FE 加密的第 i 位，并对其进行 XiO。这样一来，它的规模在渐近意义上更小，生成速度在渐近意义上也比程序本身更快（注意这里说的是“渐近意义上”：在小规模情况下，方案的额外开销会占主导；我们想要的关键性质是，对于足够大的电路，会在字节大小和生成时间上都小于本身。

请注意，在这里我们已经第一次窥见了混淆的模样：创建者本人既可以完成可信设置并发布 xIO，其他人也可以执行它，而无法了解正在运行的程序。但这里存在一个大问题：这只适用于一个预先配置好的输入。

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

本质上，我们从次线性紧凑型 RE 原语出发，并以递归方式应用它，递归的对象是你试图混淆的函数输入比特数。在基本情形（零输入）下，我们就像上文那样直接使用次线性紧凑型 RE。为了增加一个比特，我们构造一个关于如下过程的次线性紧凑型 RE：生成两个低一层级的混淆版本——对函数进行混淆，它执行，但将第一个输入比特固定为；以及对进行混淆，它执行，但将第一个输入比特固定为。

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

XiO 确保这种混淆的体积可以小于它所生成的两个子混淆
简洁型 FE 确保其生成速度可以快于它所生成的两个子混淆。

这两个性质都是必需的，才能确保递归过程中不会发生爆炸式增长。

要对一个经混淆的程序进行求值，你先对顶层的 RE 进行求值，以得到两个新的混淆结果（两者所需输入位都各少一位），然后根据第一位输入选择左分支或右分支，再继续向下递归，直到最终落到底部，得到一个 thunk，它会为你所走过的完整路径对应的生成 P(x) 。

还有另一种等价的方式来理解这里发生的事情：

对于输入为 n 位的程序，存在一棵深度为 n、大小为的树，涵盖所有可能的求值结果。然而，这棵树的大部分实际上从未被求值。整个结构是一棵由“thunk”组成的树，因此构建这棵树的指数级成本实际上并不会真正付出，因为凡是不在你所关心的特定输入路径上的 thunk，都不会被真正实例化。唯一会被实例化的，是每一步上的混淆结果，以及从根到该输入的那条路径。从非常高的层面看，事情就是这样，这就是其核心设计。

需要注意的是，原始的 LPST15 和 LPST16 论文对其中机制的描述略有不同（但本质上是等价的）：它们并不是直接对混淆进行递归，而是对一种“节点程序”进行递归。该方法的一个优点是，节点程序能够捕捉“截至目前的输入比特”，因此你不必操作或封装本身；在它们的版本中，在整个过程中始终保持不变。

上面的描述还省略了另一点：为了让混淆具备安全性，它需要是随机化的。所以实际上，它不是，而是，其中是一个经过哈希后生成（伪）随机性所需的值，这类随机性会被混淆电路等原语使用。随机化编码、XiO 和简洁函数加密也都会将作为参数。当这些函数中的一个调用另一个作为子程序时，它应当通过对自身的种子进行哈希来为该子程序生成种子，并注意为每一个子程序提供唯一且不同的种子。为了使安全性证明更简洁，从技术上讲，这里的哈希必须是一个可穿孔 PRF，不过它还有一个有趣的性质：哈希的穿孔版本需要能够被构造出来，但实际上永远不会被运行。

如何构建一个简洁的 FE 方案？

坏消息是：简洁型 FE 方案是一座复杂的构造之塔，一层叠着一层。

好消息是：这些构造相对已经得到了较为充分的理解，使用的是非常标准的密码学假设（“只是”格），而构建简洁型 FE 的这条技术路线自大约 2014 年起就已被理解清楚。

先来看这张图：

让我们逐一来看。其中两个最基础的构建模块是混淆电路和全同态加密。

混淆电路

这里有一篇帖子，我在其中更详细地解释了混淆电路。基本总结是：

对于电路中的每一根导线，你都会生成两个标签，一个代表 0，另一个代表 1。
对于每一个门，你都会公布一张表，说明哪一对输入标签对应哪一个输出标签，并按标签排序存储，这样就无法看清哪个输入标签对应 0、哪个对应 1。
输出标签不会以“明文”形式给出；相反，它们通常会与两个输入的哈希值进行 XOR。这使得它们在需要时可以被计算出来，但会阻止你获知除你同时拥有两枚输入标签所对应的那条“分支”之外的任何信息。
要执行这一过程，你需要获取与你的输入相对应的标签，然后你“沿着电路逐步向下推进”，最终确定末端各条导线上的取值（这些是真正的数值，而不仅仅是标签）

混淆电路只能安全地执行一次。如果你把两个输入的标签都给了某人，他们就能够计算出远不止两个输出。混淆电路最初是作为一种 2 选 2 的多方计算原语被提出的：我有一个电路，你知道，我把的混淆版本发送给你；对于每条输入线，我借助一种称为遗忘传输的技术，帮助你在不知道我选择的情况下获知两条输入线中的一条；然后你沿着电路逐步计算，得到输出。

关于遗忘传输工作方式的一个粗略基本描述是：你向我发送两个公钥和，它们必须相加为某个随机哈希，因此其中只有一个能对应有效的私钥，但我并不知道是哪一个；我用加密一个标签，再用加密另一个标签；你解密你持有私钥所对应的那个标签，但我无法判断那是哪一个。

然而，在这里我们并不是在进行 2 选 2 计算。相反，我们是把混淆电路当作一种构件，用来获得简洁函数加密（FE）所需的性质。混淆电路具有许多宝贵的性质。尤其是：

你可以在不泄露输入内容的情况下，把某个输入的标签交给他人。
由于每个门上的工作都可以并行进行，为生成混淆编码电路的过程是低深度的，即使本身的深度非常高。

这两个性质都很重要。

混淆隐藏了电路的部分信息，但远不足以在任何需要隐藏函数的场景中产生真正有意义的作用。当需要隐藏函数时（例如 2-of-2 MPC 的用例），一种典型方案是对通用电路（又称虚拟机）进行混淆编码，并由电路提供方同时提供其想要运行的实际电路，将其作为标签并入输入的一部分。对于我们的用例而言，我们并不在意混淆编码会泄露函数的细节，事实上正是因为我们采用了这种“把它包进虚拟机里”的技巧。

全同态加密（FHE）

这里有一篇我更详细讨论 FHE 的文章。由于本文后面介绍的其他构造依赖这些细节，因此我会先给出一个基本总结。

FHE 建立在一种名为“带误差学习”（LWE）的密码学假设之上。基本上，如果你有一个模某个数的线性方程组的近似解（即一个矩阵、向量和，以及模数，满足模，其中是一个“小”的（也就是“低范数”的）误差向量，因此中的每个值都远小于），那么即便给定和，你也无法提取出。如果你有一个精确方程，那它就是一个线性方程组（模 q），可以用高斯消元法以相对较低的成本求解。但一旦加入误差，这种逆向求解在计算上就变得不可行。

基于这一假设，已经构建出了许多具有不同属性的 FHE 算法。最简单的思路是随机选择一个私钥，生成一个随机矩阵，并计算模意义下的，作为单个比特 m 的加密结果（这里，把一个比特加到一个向量上，意味着将该值加到向量的每个元素上）。

随后，构造者就可以按这种方式发布对和的加密。解密时，你可以计算，其等于；高位比特编码消息，低位比特编码误差，因此后者可以被丢弃。如果你有两个密文和，它们分别是对和的有效加密，那么（同样，全部模）就是对的有效加密。

还要注意，按上述写法，这一设计可以支持在消息槽中加密比特向量，而不只是单个比特。但上述设计实际上有一个关键能力并不支持：乘法。

乘法比加法更棘手，原因有几个。首先，你不能把两个向量相乘并得到一个向量；你只能对矩阵或多项式等其他结构这样做。其次，两个三项值相加，得到的仍是另一个三项值，而两个三项值相乘则会得到一个九项值，因此你得到的仍是某种不同“形状”的东西。第三，你最终会让“较小”的误差与“较大”的其他量相乘，这会使误差在仅仅一轮乘法后就迅速膨胀。

对此并不存在一个简单的解决方案。有几类不同的解决方案，但各自都有不同的缺点。使用多项式的方案基于一种更强的假设，称为 Ring LWE；一种常用方案是 BFV。对 FHE 使用而言最方便的方案则基于矩阵，称为 GSW。为了说明其工作原理，我将先介绍一个简化版本：它能让基本算术运算成立，但不处理误差问题，因此如果存在非零误差，它就会失效。

首先，生成一个秘密。要加密一个值，先生成一个其他方面随机的矩阵，其中等于某个“小”或“低范数”的误差。一种做法是将两者都分成两部分来生成：

生成一个随机的，然后令（表示拼接）
生成一个随机的，以及一个随机的低范数误差，然后令（这里是纵向拼接）

然后，计算（其中是单位矩阵）。而要解密该密文，只需读出（即的最后一个值）。

如果你是一名数学家，你可能会注意到，我们是在 C 的一个特征值中“隐藏” ：是对应的特征向量，因此满足。不过，它们并不完全是精确的特征向量和特征值；更准确地说，它们是带有误差的特征向量和特征值。但首先，我们可以先把这些误差放在一边，来看一看那些让特征值显得特殊的性质。

对密文进行加法同样易如反掌：如果

满足

然后

满足

但与之前不同的是，我们也可以对密文进行乘法：如果

则

特征值基本上是矩阵唯一同时具有这种加法性质和乘法性质的属性，即便如此，我们这里也还是将范围限制在具有相同特征向量的矩阵上。

现在，让我们把误差容忍性加回来。按上述写法，这一机制存在一个致命缺陷：如果把带误差的完整方程写出来，你最终会让误差与和中的元素相乘，而这些元素可能取自的整个范围。因此，误差会立刻膨胀到最大值。此外，甚至连解密也无法容忍误差。

为了堵上第一个漏洞（第二个我们会在最后再回头讨论），实际的 GSW 依赖一种 gadget 矩阵机制。

下面是一个 gadget 矩阵的样子：

单独来看，这看起来不错，但并没有太大意义。不过，它本来就是要与一个会被其抵消的运算（不是矩阵）配对使用：矩阵位分解运算：

该运算的输出中每相邻四个值（我们称之为“ ”）都是输入中对应位置数值的二进制编码（最低有效位在前），也称比特分解。

关于和，最重要的事实是：

的输出是“低范数”的（所有值都很小）
，对于任意

后者可以直观地理解。如果你在上面的例子中沿着计算过程追踪被高亮显示的 2 的比特分解（ 0 1 0 0 ），那么它会与 gadget 中的 1 2 4 8 相乘，结果得到。也就是说，如果你将 gadget 矩阵应用于一个比特分解，它就会对该比特分解进行“求值”，从而恢复出原始数值。

在上文简化描述中我们使用单位矩阵（）的那些地方，在实际协议中我们使用的是。也就是说，密文的形式为。我们通过计算来将两个密文相乘。消息被隐藏在某种已不完全是“带误差特征值”的结构中，但我们仍然保留了所需的属性。最终数学推导仍以同样的方式成立，但由于误差不会再被大数相乘，乘法实际上变得可行。具体来说：

加密：
解密：
相加：（显然）
乘法：

注意解密中的一个细微之处。的最后一列只包含这一项非零元素，因此乘以实际上得到的是一个包含的对象（而不是）。这正是我们在解密中获得误差容忍性的原因。这也是为什么我们现在在加密时要除以。请注意，按上述写法，这种方法要求是 2 的幂。如果你愿意，也可以让取其他值，但这需要对解密过程稍作调整。

我们可以检查乘法的正确性。先只看代数部分。首先是加法：

然后来看乘法：

现在，我们必须证明前两项也都是有效的“填充项”，就像原始的和是有效填充项那样。我们需要的核心性质是，乘以只会留下一个很小的低范数误差。

第二项很简单：是一个有效的填充项（具有低范数），我们将其乘以较小的，因此也具有低范数，从而也是一个有效的填充项。

对于第一项，我们来展开。返回一个“小”的误差。返回一个由 1 和 0 组成的矩阵。因此，就是一个小误差乘以一个由 1 和 0 组成的矩阵，其结果仍然是一个小误差。

第二个 pad 中的误差大致会按消息空间的大小放大（也就是 0 或 1）。第一个 pad 中的误差则大致会按矩阵的大小放大。因此，每次乘法都会使误差按一个常数因子增长，所以我们可以预测在误差变得过高之前，FHE 能承受多少次乘法。到了那一步，就需要通过自举来重置误差：在 FHE 内部对 FHE 的解密电路进行求值。

最后，还有一个细微之处：为了将误差膨胀控制在有界范围内，我们需要要求消息保持很小；具体来说，它们必须是 0 或 1（例如 -1 或 2 也可以接受）。加法和乘法并不遵守这种大小限制，而且与 BGV 不同，这里我们没有原生的模 2“回绕”机制。因此，要使上述算法安全，你需要使用按如下方式实现“逻辑门”的电路：

，其中是对 1 的加密。

这只是实现方式之一；并非最优；还有更高效的实现方法，而这正是 FHE 优化艺术的一部分。

下面是一段遵循这种 GSW 风格的 Python 代码，不过请注意，它采用了一种略有不同的技巧，其中用作为“pad”，而不是（这具备上述所有性质，另外还有一个我们稍后会需要的额外性质）。https://gist.github.com/vbuterin/f0f8a9eb09633226ada20c21a98d537e

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

现在，让我们进入下一个：

基于属性的加密（ABE）

不是这位 Abe。

也不是这位 Abe。

也不是这个 Abe。

下面给出基于属性的加密的定义：

权威方为一个电路为  的函数生成密钥：他们生成一个“主公钥”  （公开），以及一个依赖于  的秘密密钥 skC （交给解密者）

加密者知道  （一条待加密消息），他们知道该消息对应的  ，未必知道  ，但确实知道  。他们会生成一段密文

解密者在拿到这样的  和  后，如果  ，就能够解密并恢复 m ；否则无法解密。

通常，属性基加密的合理性会通过这样的例子来说明：可能是某家医院的病历，而可能是一个表示“你在工作，并且你拥有医学学位”的对象，这样一来，就可以很容易地以某种方式加密这些病历，使得只有目标医生才能查看它们。不过，据我所知，真正适合映射到这一范式、而且又不能通过简单得多的公钥加密轻松解决的使用场景其实非常少。因此，ABE 在实践中并没有得到太多应用。

_. 不过，这里有一个非常好的消息：ABE 具有一些宝贵的性质，使它在构建函数加密时非常有用！（因此，对混淆也同样如此。）尤其是，即使对于规模很大的电路，加密的成本也很低。这正是那种不对称性的最初源头：它使得混淆中的“thunks”创建起来比执行起来更快，因此也才使得指数级大小的树成为可能。

下面介绍 ABE 的工作原理。这里我们将采用 BGG+14 构造，其性质非常适合用于简洁 FE 和混淆的应用场景。

我们针对一个电路来进行操作。为了便于你在脑中形成一个例子，就拿我们在混淆电路示例中用过的那个电路来说（它是一个两位加法器），但去掉“每条导线两个标签”这一部分：

相反，我们将为每条导线只设置一个矩阵，再加上两个随机生成的全局公共矩阵和。

初始的是随机生成的。为了生成电路中更下游导线的矩阵，我们沿着电路向下遍历每一个门：

如果它是 ADD，那么就计算
如果它是 MUL，则计算

和 FHE 一样，我们需要通过 ADD 和 MUL 来构建 OR、XOR 和 AND，同时保持导线上的值始终处于中。

权威机构会发布与电路无关的和，以及用于该电路输入导线的。他们还会向解密者提供一把解密密钥，即一个满足的低范数矩阵，其中是对输出进行编码的那根导线对应的矩阵（即）。请注意， B 矩阵的构造并不依赖于电路输入，这也是为什么权威机构能够以一种随后对所有输入都有效的方式构造 Bf 。为了使 (A|Bf)∗Rf=D 之间的等式成立， A 需要以一种特殊方式构造，从而赋予其一个“陷门”；我们稍后会回到这一点。

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

在加密时，加密器选择一个随机向量，并计算。它们还提供输入编码，即和。请注意，加密过程并不依赖于电路本身；它只需要知道输入的和，并围绕它们进行少量乘法运算。

解密器的任务是从这些值出发，沿着电路逐层向下推进，在每个门上执行一种类似同态加密的运算，将左侧输入导线的和右侧输入导线的转换为输出导线的。

这里，ADD 的情况同样很简单：。MUL 的情况则更难。

公式为：

这里的是该计算中那根导线上的实际取值。要理解其为何成立，我们逐一来看每个组件。为便于说明，我将把写成；只需记住，由于和会相互抵消，因此：

如果我们把两者相加，就会相互抵消，我们得到：

左边的就是，这正是我们上文给出的用于乘法的的定义。而右边是误差与低范数值相乘，因此仍然保持为低范数误差。

这样一来，解密者就拥有了逐步推导到所需的一切。

如果，那么项就会从的定义中消失，于是我们只剩下：

一旦他们得到，就会在前面加上，得到，这满足。然后他们计算：

如果误差没有膨胀得太厉害（别忘了，也是低范数的），解密者现在就可以自由地恢复。

现在，让我们回到陷门机制。

我们不会随机构造。相反，我们将其构造为，其中是一个低范数的“陷门”，而是前面提到的小工具矩阵。与我们见过的 FHE 密文类似，在 LWE 假设下，如果你自己不持有这个陷门，就几乎不可能在计算上将这种构造与随机对象区分开来。

目标是满足一个简洁的数学性质：

或者用图形来表示：

我们已经构造了一个矩阵，从某种意义上说，是 A 的一种“逆”（请记住：在这类 LWE 构造中，往往扮演着“伪装成”单位矩阵的角色）。

这里的目标是构造这样的矩阵：对于任意已知向量，只有创建者才能找到一个低范数向量，使得。也就是说，这个陷门使我们能够“求解”短整数解（SIS）问题；该问题与 LWE 密切相关，也是这类密码学方案得以成立的基础。

下面是算法：

将进行二进制分解（即对其应用经典的），设输出为
输出

、和都是低范数，因此这同样也是低范数。要从代数上看出这为何能解这个方程，计算如下：

为保证这一过程是安全的（即不会泄露），现实世界中的实现会在这一步额外加入误差；关于实现这一点的最高效方法的更多细节，参见 MP12。

现在，让我们回到上面那个仍未解开的难题：计算。

我们要求解的方程是：

我们将把解释为，于是得到：

我们为采样一个随机的低范数误差，因此现在我们只需要求解：

这里，我们只是逐行使用上述方法来计算的每一行。这样就完成了。

敏锐的读者可能会注意到，这与环签名有些模糊的相似之处，至少在二选一的情形下是如此：两个项中的一个“以简单方式”计算出来，而另一个值则利用陷门被计算为与之匹配（而这本来是“你不应当能够做到”的）。

为清楚起见，需要注意的是，陷门中的从不会被交出，甚至不会提供给解密者。提供给解密者的是。

现在，让我们回顾一下我们已经得到的内容：

两个全局公共矩阵和，其中一个是随机生成的，另一个则通过陷门计算得到。
对于每根导线，一个矩阵；输出导线的矩阵为
一个满足的解密密钥 Rf
一个加密是一组个值，每个输入导线对应一个，并且有一个对应于的，以及一个对应于但混入了消息的 cout 。
解密者沿着前进，并计算以获得消息。但这只有在时才有效；如果不满足，就会混入一个项，把一切都扰乱。
其中最重要、也最惊人的性质在于：你能够生成一个密文，而它是否可解密取决于一段很长的计算过程，但你自己却完全不必运行这段计算（不过某个“权威方”——可以把它理解为可信设置——确实需要事先运行一次）。

该方案的主要限制在于电路深度：每进行一次乘法，误差都会增加一个常数量，因此电路越深，为了补偿误差，所需的数值和矩阵就必须越大。理论上你可以处理任意深度的电路，但如果真这么做，为了让密文足够大以容纳这些误差而产生的额外开销会急剧膨胀。这正是基础简洁型函数加密（succinct FE）中深度受限的根源，而我们稍后将讨论的封装器则能消除这一限制。

这就是 ABE。

顺便说一句，也不是这个 Abe。

固定深度电路的函数加密

令人惊讶的是，至少就这一部分而言，我们现在已经完成了困难的数学部分。下一节将只是把乐高积木拼接起来。

首先，给出函数加密的定义：

权威方为具有电路  的函数生成密钥；他们还会生成与电路无关的公共参数（包括公钥），以及一个依赖于  的解密密钥

加密者使用公钥对  进行加密

解密者获知  ，除此之外一无所知

我们所追求的一项特性是简洁性：正如我们在 ABE 中看到的那样，即便电路很大，加密也必须成本低廉。

下面是这一过程（沿用 GKP+13 的构造）。先看授权方的工作。授权方选择电路，并据此生成参数。

设 FHE 密文的比特长度为
生成 ABE 公共参数以及个 ABE 密钥
- ABE 电路的定义是：“取一个 FHE 公钥和 FHE 加密后的输入，计算，输出第 i 位比特”
- “第 i 位”有 w 种选择。此外，我们还构造了一组可直接输出第 i 位的参数，以及另一组在输出前先将其翻转的参数（即，解密以输出为 1 为条件）。这使得每一位额外增加两种选择。因此，总共有组参数。
公布 ABE 的公共参数，并将个 ABE 解密密钥交给解密方。

作为发出个 ABE 加密的一种替代方案，可以对 ABE 进行修改，使其同时加密两条消息：其中一条只有在满足时才能解密，另一条只有在满足时才能解密。这样会增加一些复杂性，但可节省 2 倍开销。

现在来看加密者的工作。加密者有一个值，希望将其加密。

生成一个 FHE 密钥对，加密得到
生成一个电路的混淆版本：该电路接收密文并输出（注意，这里的已被硬编码进电路）
该混淆电路包含输入标签，以及为每个中间门和输出设置的更多标签。使用作为标签，在第（index, bit）个 ABE 密钥下加密 L{index,bit} 。
输出：、，以及完整的 garbling，但其中输入标签已被加密。

解密器使用作为标签，对加密的 Lin 标签执行 ABE 解密过程，从而获得输入标签。随后，他们运行混淆电路并得到输出。

现在，让我们回顾一下我们在这里做了什么：

我们保留了 ABE 的这一属性：加密者无需运行该电路；只有授权方和解密者需要这样做。
我们改变了逻辑：不再是由电路来决定你是否能够解密某个无关的消息，而是电路本身就是你唯一能够解密的的求值结果。
其核心思路是，ABE 的属性——只有在你“应该”解密时才能解密，这一点由某个电路所定义——确保了解密者只能获得他们本应拿到的、用于混淆编码的输入标签。该混淆编码使他们只能对那个值执行 FHE 解密。如果他们试图运行某种不同的计算，那么 ABE 解密中的就会多出一个悬空的，他们将无法完成解密以获得有效的输入标签，因此也就无法运行该混淆编码。
我们继承了 ABE 的主要限制：因为在 ABE 内部完成的操作，是对该电路进行 FHE 求值，而其深度等于电路深度再乘以一个显著的膨胀因子，因此它只对深度受限的电路效果较好。

适用于无限深度电路的函数加密

这一种可以用一句话概括。与其对进行 ABE 加密，不如对这样一个函数进行 ABE 加密：它以为输入，并为生成混淆电路（例如使用作为混淆过程中的随机性）。混淆电路的生成可以并行化，因此即便电路本身深度很高，这一步的深度仍然很低。解密者运行低深度 FE，得到包含相应输入标签的混淆电路，然后以明文方式逐步执行该混淆电路，从而获得输出。

至此，我们就讲完了简洁函数加密！回顾整个过程，下面再次给出我们最初的示意图：

如何构建一个 XiO 方案？

我们先回顾一下 XiO 的定义：

生成器为一个隐藏函数选择参数，该函数的电路为，且输出为单比特。它们生成该函数的一个编码。这一步所耗费的时间可以与在所有可能输入上对进行求值一样长，甚至更长，但输出必须小于真值表（即所有可能输入对应输出的集合）。

求值器对该编码进行求值，以获知任意输入下的 C(x) 。

从技术上讲，“XiO”是“指数级（非）高效不可区分混淆”的缩写，但最好不要把它当作混淆来理解。相反，它是一种压缩数据的方法，适用于这样一种特殊情形：数据由一个程序生成，而该程序的规模远小于数据本身，并且你希望隐藏这个程序。它是为输出比特的“thunks”（零输入函数）设计的，而不是人们直觉中所认为的那种“真正的函数”。

迄今为止，大多数已知的 XiO 构造都建立在一种称为 split-FHE 的原语之上。以下是 split-FHE 的定义：

假定生成者拥有 FHE 的加密与解密密钥，以及他们心中设定的一份特定密文。我们假设一种加密方案能够高效地对向量进行加密（而不只是单个位）。给定一份对特定向量进行编码的特定密文，他们会生成一个提示，其规模远小于 v 。

解密者在拿到和后，可以利用该提示对进行解密，从而得到，但无法借此解密任何其他密文，也无法获知关于 FHE 密钥或所源自计算过程的任何其他信息。

以下是基于拆分式全同态加密（split FHE）的 XiO 的构建方式：

如果我们要对一个输出大小为的 thunk 进行编码，我们将其视为一个函数：它接收一个索引，并输出该 thunk 产生的第 i 位。

我们将输入空间划分为个桶，每个桶的大小为。对于每个桶，我们对该桶内的每个索引进行 FHE 加密（使用 GSW）（例如，第一个桶为，第二个桶为），并对每个索引运行。随后，我们使用一种特殊技术，将密文转换为一个包含所有值的打包密文。最后，我们为其发布一个固定大小的提示。XiO 即由全部个固定大小的提示组成。

这里有三个需要理解的技术部分：

GSW 的一些修改
打包机制如何运作
提示机制如何运作

实际上，这三者是相互关联的。除提示生成和基于提示的解密之外，我们不会在任何其他场景中使用打包；而对 GSW 的这些修改，也使其除了基于提示的解密之外无法以任何其他方式进行解密，因此我们不妨将其统统视为同一种算法。下面我们将按照 WW21 协议依次介绍这些内容。

对 GSW 的修改

还记得普通的 GSW：，其中每条消息新生成的对于低范数的满足 s∗A=e 。

这里，我们将 GSW 修改为：，其中是一个固定的“公钥”矩阵，而则是每次重新随机选择、但范数较低的矩阵。是新引入的误差项，用于防止被泄露，同样是每次重新随机选择，但范数较低。

重要的是，是高而窄的，是宽而矮的。两者较小的维度必须匹配。这一点很重要，因为这个维度决定了提示的大小。提示不能只是一个数值，它需要具有一定的宽度以保持 LWE 安全性，但它可以远小于这些矩阵的尺寸，因此也远小于它将协助解密的那些向量的尺寸。

同样重要的是，用于解密的乘以 s 技巧会被新的误差矩阵放大，因此不再存在可用的“解密密钥”。除继续对密文进行求值外，你唯一能对密文做的事，就是类似基于提示的解密机制。正因如此，作者明确将其称为同态承诺方案，而非同态加密。

打包与提示

假设你有若干个上述形式的密文：、 …… 。它们共享相同的，但具有不同的矩阵，以及不同的（消息）。

下面说明如何将它们全部合并为一个向量：

令为一个向量，其宽度与和相同，且除在第个位置为 1 之外，其余位置全为 0（例如，若，对于，它就是，为便于说明添加了分隔符）。注意，第个位置恰好是矩阵第 i 行取值最大的地方。
- 通俗地说，可以把看作“只保留第列、丢弃其他所有内容”的算子。
- 就其作用而言，可以把理解为：“提取出密文中最有用的信息（即以最高有效位形式存储的位置），并将其放入输出的第行。”
计算

如果不是 2 的幂，就必须采用稍微更复杂一些的方法：与其让的第 i 个区块是许多个 0 后面跟着一个 1，它必须是的按最低有效位优先的二进制编码。前者只是后者在情况下的特例。

就是这样。为了计算原始提示，我们在 FHE 中沿着加法和乘法与密文一起“追踪”这些矩阵（留给读者的练习：请自行推导 ADD 和 MUL 中“追踪 ”的代数过程；它与使用时基于和的方法非常相似，都是为了将误差保持在低范数），然后对 R 应用完全相同的过程： rf=R1∗u1+R2∗u2+…+Rk∗uk

现在，回想一下，，所以如果你从中减去，就会得到；在矩阵的每一行中，它都会在 log(q) 个相邻位置上具有 m 。不过，这里我们处理的是许多不同的 Ri ‘ 值，而我们希望通过一次操作同时揭示所有 mi 。为此，我们采用了一个技巧：在第 i 行中，我们使用 Ri 。因此，如果你减去 cf−A∗rf ，结果的第 i 行就会正确抵消掉 A∗Ri , ，并给出你所需要的值 mi∗q/2 （外加一个误差）。

现在只剩下一个问题：单独的原始提示并不是安全的提示。它泄露了过多关于本应保密的矩阵的信息。为了解决这个问题，我们对它进行掩蔽：

生成一个新的秘密（与提示大小相同）
单独发布，而不是
另外再发布一个“样本”

验证者知道，因此他们随后可以计算：

出于安全考虑，样本中的误差必须远大于其他误差，才能将有关这些误差的信息完全隐藏起来。因此，我们有两层尺度分离：样本误差足够大，可以掩盖其他误差；而消息又足够大，可以避免被样本误差破坏。

该方案的第二个版本是安全的，但它带来了一个新的大问题：样本是全宽的，而不像提示那样是短的。因此我们再做一次修改：我们不直接发布，而是发布一个用于生成它的小工具。

我们这样做：

生成器对一个新的进行加密（也就是你用来生成哈希的值），并针对种子中的每一位发布该种子的 FHE 加密：
对于每个桶，生成器和解密器都可以进行如下计算：
- 在 FHE 内部计算（其中本身是通过取另一个而生成的误差），并得到密文：，其中是的第 i 位。
- 应用我们上文描述的打包过程，但要对这列中的每一列都使用一个，而不只是对那些位于的倍数减一位置上的列。为便于说明，我们将其视为一个带有两个索引的求和：块内索引 0≤t<log(q) ，以及块索引 0≤j<k 。这里我们把所有内容都视为从零开始索引，以便让数学表达更简洁。
  - 请记住：原始打包过程给你的是。而这里，你得到的是。
  - 我们假设在电路内部，密文的第 j 个区块表示中第 j 个数字的二进制编码。
  - 因此，在第 j 个区块内，，我们是在“求值” 中第 j 个条目的二进制分解；并且由于的结构，这些值都会被发送到输出的第 j 行。
- 打包过程的输出是。注意，所在的位置，通常本应是。这正是我们以上修改打包过程的方式所直接导致的结果。的表达式可以重写为
- 生成方可以明文计算出，而求值方不行。因此，生成方将其作为的取值混入提示中。
解密方的计算与之前相同，唯一的区别是他们不会从生成方那里接收；他们会使用上述方法自行生成它。至于它为何会相互抵消，其数学原理也完全相同。

这些论文用（“伪随机函数”）来指代哈希。这只是意味着，哈希需要具备很强的随机性性质（远强于抗碰撞性，但弱于随机预言机）；如果你相信哈希满足随机预言机模型，那么你完全可以在所有地方都将其理解为。

就是这样。XiO 为：

系统的公共参数（例如加密密钥、待求值的加密电路）
每个桶的提示（其中）
对的 FHE 加密，以便能够计算出可让你抵消的样本

求值时，需要仅针对某一个特定桶重新执行一次运行，然后利用提示解密最终向量，最后从该桶中取出你所需要的值（在混淆的使用场景中，解密器会从所有桶中取出全部值）。

还有一项进一步优化，可在保证可证明安全性的同时将效率最大化。XiO 在其所编码 thunk 的大小上是，但它需要发布大小为的可信设置参数（出于一个技术性原因，这些参数是存在的：生成用于补偿提示的个样本的函数，必须有一条从未被使用的路径，用于接受并使用完全随机的值；这使得安全性证明成为可能）。这一可信设置的长度为。如果将 XiO 拆分为个独立的 XiO，那么 XiO 的大小会上升到，但可信设置（可被它们全部复用）也会降至。

XiO 与安全假设

除 XiO 之外，混淆构造流水线中的所有部分，都可以用相当“标准”的基于格的假设来加以论证。归根结底，所有密码学都只是在猜测某个数学问题“确实很难”，而不只是因为我们迄今为止还不够聪明、没能解出来，但也许明年就会想出办法。不过，有些猜测的依据比另一些更扎实。在所有抗量子原语中，作为格密码基础的 LWE 假设通常被认为不如哈希那样稳健，但又比几乎其他所有假设都更稳健（包括更复杂的格假设）。

但现有的所有 XiO 原语都存在一个问题。上述设计并不能在格假设下得到严格证明。它之所以能够被证明，是基于这样一种形式的假设：“如果你公开风格的‘样本’，并再公开少量额外信息，那么系统仍然是安全的。”但问题在于：这类假设此前就曾被攻破，而最终在这里也同样失效了。

2013 年，CLT13 提出了一种早期的多线性映射候选方案（这是一种非常强大的原语，如果我们拥有它，将使混淆变得容易得多）。然而到了 2015 年，它被攻破了。

CLT13 发布的对象是。密文的形式为。如果你将一个表示的密文与相乘，就会得到。和都是非常“小”的值（远小于模数），因此二者相乘后也会远小于模数。因此，可充当“零检测”密钥，这使得你能够在格密码密文上执行类似配对检查的操作（与配对不同的是，只要按比例扩大参数，格密码可以相乘到任意高的深度）。

问题在于：会精确暴露出该方案底层秘密在整数上的表达式，因此如果你掌握了足够多这样的值，就可以进行一些矩阵运算并恢复这些秘密。

作为 WW21 中新的核心假设，HPLS 猜想表面上似乎也提供了一种泄露“仅仅是误差”内容的方式：

对手知道，因为它是公开发布的
如果对手拥有，那么只要收集到足够多这样的值，他们就可以通过求解线性方程来恢复这些秘密（单就这一点而言并无问题：毕竟，的全部目的就是掩盖）
如果对手拥有，那么请注意，该值满足，因此如果他们将其乘以，再从中减去这一结果（这些他们也都可以计算），就能直接得到一个“误差”值

请注意，即便提取出是致命的，WW21 的安全性仍还有另一道防线：对手并不会学到两个致命秘密中的任何一个（和），他们学到的是两者之和，而也许并不存在从这个和出发的有效组合攻击。但即便提取出，很可能也没有问题。HJL21 中攻破 HPLS 假设的攻击，成功做到了一件特定的事：他们找到了如何以对抗性方式构造电路，使得误差的最低有效位（它能够在通常用于保护此类方案的“涂抹”技巧下幸存）编码一个变量，用来输出该执行是“真实”执行，还是证明过程中使用的“模拟”执行。总结如下：

该攻击要求对手来构造电路；任何合法参与者都不会以对手那样的方式设计电路
该攻击只会泄露用于证明该方案正确性的机制内部所使用的一个变量，并不会真正泄露任何秘密
该攻击要求已知，而实际上对手只知道

因此，即便这一假设在有限情况下被攻破，WW21 的安全性很可能仍然没有问题。

2025 年发表了一种新协议，它在 WW21 技术中“帮助解密器发现从偏移量到提示的样本”这一环节上增加了一些额外复杂性，使其依赖于比 HPLS 更受限、但仍比普通 LWE 更激进的格假设。具体而言，HJL25 所采用的假设属于这样一个框架：“只发布其中携带秘密的部分会经过 mod-q 包裹的对象”（这排除了提供“原始误差”以及 CLT13 的）。这不像普通 LWE 那样保守，但确实是一个有意义的改进。“普通 LWE”和“携带秘密的部分必须经过 mod-q 包裹”之间的空间，包含了诸如循环安全之类的假设，以及 HJL25 中的假设。这类假设确实存在反例，但都经过高度刻意构造，而迄今为止，基于这类假设的真实协议都已被证明是安全的。

你可能会想到一个类比：其他一些“理想化黑盒”假设：

哈希函数的随机预言机模型
椭圆曲线的通用群模型。

到目前为止，ROM 在实践中已被证明相当有效，但研究人员设计出了一些签名方案：它们在 ROM 中可被严格证明是安全的，可一旦用任何现实中的哈希算法来实例化，就很容易遭到攻击。而且，通用群模型已知在少数情况下并不成立，最著名的例子是通过 Schoof 算法进行阶求解，以及配对。椭圆曲线安全性建立在一个并不稳固的基础之上：你可以通过这两种方式违背通用群模型，但不会以更有害的方式违背它。

唯一一类完全基于“标准”假设来证明 iO 的协议是 JLS20 及其后续方案，但它们并不具备量子安全性。

总结：密码学假设是一个复杂的“动物园”，不存在绝对可靠，只有不同程度的安心感。

另一个重要的注意点是，如果我们希望能够被可证明地归约到这些安全假设，那么，对一个比特输入程序进行混淆的安全证明，就需要“遍历”所有可能的输入。对于每一个输入，都会消耗一点安全余量。因此，这一证明消耗的安全余量可能远远超过倍。正因如此，所有这些混淆协议都要求 LWE 参数具备次指数级安全性，这意味着密文会比常规 LWE 密文大数千倍之多（而且由于该协议具有层层堆叠的特性，这个“数千倍”本身还会再复合放大好几次）。

如果你愿意，也可以“yolo 一把然后忽略这一点”，就像递归 STARK 协议那样，直接忽略这样一个事实：它们要求哈希函数同时既是随机预言机，又是可以由电路实例化的具体对象。这样做很可能是可以接受的，但如果你为了效率而做了足够多这种“很可能没问题”的事情，就会碰到一个哲学问题：既然如此，为什么还要如此艰难地推动混淆在标准假设下实现可证明安全，而不是采用其他一些方案（例如 diamond iO）——这些方案虽然依赖更激进的假设才能获得可证明安全，但效率却高得多？

总而言之，对于“要构造一个可运行的混淆协议，需要作出哪些密码学假设”这个问题，答案是：

比 2010 年代稳健得多——那时的混淆是建立在矩阵分支程序之上的，而矩阵分支程序又依赖基于格的多线性映射；迄今为止，这类构造并未经受住密码学审视，而且还屡次以致命方式被攻破。
但距离完美仍相去甚远

XiO 与可信设置

最后，还有一点显而易见但非常重要，值得强调：混淆程序的安全性在许多环节都依赖于可信设置，因此我们距离实现完全无信任的混淆还相去甚远（即以这样一种方式生成带有内部秘密的程序：连混淆器本身也不知道该秘密）。我们目前所能做到的最好情况，是用一个 N 方可信设置来替代单方可信设置。

这里有一种很自然的实现方式。

我们定义一个生成器，它返回一个双输入程序，其行为如下：

如果，它会将其第二个输入解释为程序，并返回，其中。也就是说，它将一个为秘密预留槽位的程序作为输入，并输出的混淆版本，其内部秘密被硬编码其中。
如果，它会将其第二个输入解释为随机性，并输出。

按照约定，我们记作（注意：这里使用了一个类似于 Y 组合子的技巧）以及。

下面是由 N 个参与者组成的链条的样子：

Alice 运行以生成（注意，原始的未经混淆，但此步骤的输出以及之后所有步骤的输出都将被混淆）
Bob 调用，输出
Charlie 调用，输出

每位参与者还会将其输出与一起在上运行，以将（此前所有秘密的混合）作为秘密来混淆 P ，并发布这一混淆结果。实际上，只有最后一位参与者的混淆结果才会真正混入所有人的秘密；但在我们的模型中，我们假设参与者是依次加入的，而且他们都不知道自己是否会是最后一位。

这样一来，这种设置既是通用的，又可更新，堪称可信设置的黄金标准。

而为了验证每一步的正确性，每个参与者都需要生成一个递归 STARK 证明，证明：(i) 前一步已经经过递归 STARK 证明；(ii) 他们正确地加入了自己的随机性。

然而，这种方法的成本极其高昂：它需要对混淆的混淆再做一个 STARK。一个尚未解决的挑战，是找出为混淆构建通用且可更新的可信设置的理想方式。

那么，运行时间是多少？

也许，关于这些混淆协议最著名的一点是：从技术上讲，它们的运行时间是多项式级的，但在实际中却庞大到近乎天文。要明白原因，我们只需再看一遍这座完整的高塔：

要解密 FE，你需要运行对 GC 生成的 FHE 求值结果进行的 ABE 解密。这其中的每一步，都会把计算中的每一位替换成一个密码学对象——要么是哈希，要么是矩阵。FHE 还需要一个自举步骤，而这要求在 FHE 内部运行 FHE 解密。单是 ABE 就需要的开销，其中必须显著高于安全参数。而你还要把这三样东西层层叠加起来。因此，仅 FE 一项所需的开销系数就高达万亿的万亿级别。
要评估次线性 RE，你需要对底层程序的 VM 的一个简洁 FE 加密的 XiO 进行求值。XiO 基本上就是 FHE；幸运的是，你可以在所编码的不同位之间复用中间计算，因此，对于那些大部分工作都在生成单一对象、而提取各个位相对易如反掌的函数来说，XiO 开销 ~= FHE 开销，尽管遗憾的是，这是一种效率极低的 FHE。另一个幸运之处在于，XiO 针对的是生成简洁 FE 加密的过程，而这个过程并不关心底层具体是什么。但在进行求值时，你随后还必须在 FE 内部生成下一轮的 XiO。

因此，这里的理论总开销大致为：，其中主要是 FHE。所有这些都是按输入的每一比特来计算的。

此外，在此基础上，为了达到次指数级安全性，每个单独方案的参数选择都必须非常保守，这会在每一层 LWE 上额外增加超过 1000 倍的开销。

这就是为什么这些方案如今远未达到实用程度；预期运行时间比宇宙的寿命还要长。

接下来我们该何去何从？

有三条路径：

某个非常聪明的人（或某个机器人）发现了一种方法，可以在与我们今天所用假设相近的前提下，对上述高塔进行优化和／或简化。也许有办法将 ABE 和 XiO 合并成一个单一组件——比如找到一种构造，既具有与密文无关的提示信息（如同 ABE），又是真正完全同态的，因此你可以在不知道明文线路值的情况下计算乘法（就像 XiO 中使用的拆分式 FHE 那样）。
我们找到一种方法，基于更激进的密码学格假设来实现混淆，从而构建出一座不同且简单得多的高塔。
我们找到一种完全截然不同的方法来实现混淆，完全不使用格。也许这意味着要发明一类新的假设。

路径（2），尤其是路径（3），还意味着我们会更擅长在实战中检验这类假设，或许同样会借助 AI 的帮助。

本系列接下来的文章将讨论也许是试图实现（2）的领先构造——diamond iO，以及也许是试图实现（3）的领先构造——local mixing obfuscation。

如果我们在任一路径上取得成功，回报都将十分丰厚：从某种真实意义上说，我们将“解决密码学”——任何可以借助理想化受信任第三方来描述的协议，只要允许对手将时钟回拨，都将能够被安全地实现。但要走到那一步，仍是一项艰巨的挑战。