混淆：打造密码学的最终BOSS（第一部分）

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

密码学中最强大的原语是混淆。混淆让你可以将一个程序 $P$ 转换成一个“加密程序” $Obf(P)$，这样你可以在明文输入上运行 $Obf(P)$，得到与 $P$ 相同的明文输出，但 $P$ 的内部工作原理被隐藏了。通常使用的精确形式化方法是 **不可区分性混淆 **(iO)，它指出：如果你得到了两个功能相同但不同的程序的混淆，你无法区分它们。实际上，它隐藏的是代码，而不是数据。

混淆之所以强大，是因为它非常接近“无需信任的受信任第三方”这一理论理想：

密码学协议通常是这样描述的：首先设想一个依赖于受信任第三方的协议，该第三方能看到所有人的消息并诚实响应，然后找出无需信任就能实现同样功能的方法。

• 加密很简单：“受信任第三方”实际上就是一个邮政系统，它接受“我希望[接收者]看到[消息]”的指令，并将消息传递给接收者。
• 零知识证明取代了一个受信任第三方，该第三方接收你的数据，检查它，然后向任何询问者确认数据在某种意义上是正确的。

混淆（严格来说，是混淆加上哈希）让你可以为几乎任何协议制作一个模拟的受信任第三方，因此它可以取代上述两者以及更多。只有一个主要的例外：混淆后的程序无法阻止自己被复制，因此它无法执行像货币这样的“有状态”操作——而这正是区块链恰好能够填补的空白。

因此，如果你同时拥有混淆和区块链，你可以实现一些非常神奇的事情。例如，一个安全、隐私且抗勾结的投票系统，它几乎没有任何信任假设——不需要 $M$-of-$N$ 阈值委员会。或者基本上任何来自2014年这个列表的内容，都不需要 $M$-of-$N$ 信任假设。

那么问题在哪里呢？嗯，事实证明，创建一种安全的混淆形式极其困难。

几十年来，一直有不安全的混淆传统：人们打乱编译后程序中的逻辑，以使其更难看清发生了什么——诚然，这通常是为了防止用户修改像游戏这样的专有程序。这相当于加密中的凯撒密码——而且，像凯撒风格的密码一样，它经常被破解。

因此，几十年来，人们也一直试图创建一种可以在数学上证明安全的混淆协议。但几乎从一开始，这就遇到了问题。2001年，我们得到了一个著名的结果：创建一个理想形式的混淆——以这样一种方式混淆 $P$，使得运行 $Obf(P)$ 除了通过查询一个能为任何用户提供的 $x$ 返回 $P(x)$ 的 API 所获得的信息之外，不泄露任何信息——是不可能的。核心思想是，$P$ 的代码实例化总是会至少揭示一些超出其输出的信息：至少，你可以通过将 $P$ 应用于其自身的代码来获取一些信息。

从那时起，研究人员转向试图证明次优的目标：不可区分性混淆（iO）。这是一个长达二十年的项目，经历了许多失败的尝试，许多协议构建在尚不存在的成分之上，许多人试图构建那个成分，而那又经历了失败的尝试，等等。但在过去几年里，我们终于有了一些好消息：我们知道如何在合理的安全假设下实现 iO。

但在好消息中也有坏消息：运行时间真的是天文数字。从技术上讲，它是多项式时间，但它涉及堆叠许多层“取一个有点像全同态加密的东西，然后将评估该电路的电路放入另一个有点像全同态加密的东西中，在普通的旧式全同态加密中为每一位运行一次，生成一个中间的多兆字节值，哦对了，我有没有提到你必须将整个东西放入另一个有点像全同态加密的东西中，然后为输入的每一位运行所有这些？” 结果，这些“某种程度上可证明安全的 iO 方案”的运行时间大约在 $λ^{10}$ 以上（其中 $λ$ 是“安全参数”，即破解方案所需时间的对数；通常取 $λ = 100$ 或 $120$）。

关于这一点，你可以讲述两个充满希望的故事。一个是，这类似于 2010 年 SNARKs 所处的位置，现在我们知道这是可能的，聪明的人（和机器人）会开始针对每个瓶颈提出巧妙的变通方法，一个接一个地削减数量级的运行时间，最终我们会得到一些在重型 GPU 上“只需要”一天就能运行的东西（这听起来仍然令人望而却步，但实际上对于许多有趣的应用来说已经足够了）。另一个是，我们会看到更多针对同一目标的不同策略的工作：在开发新的密码学假设方面做得更好，并且更好地判断哪些新假设可能是真正安全的。

如果再加上启发式方法，到目前为止大约有三种（尚未消亡的）混淆协议家族，你可以将它们放在一个安全假设的“效率 vs 大胆程度”权衡前沿上：

本文将详细描述迄今为止最天文数字、但也是最严谨的一个家族：上图中蓝色的那个。

提醒一下：将会有很多数学内容。混淆之所以困难，是因为它基本上需要堆叠密码学家在过去二十年中发明的几乎所有原语，除了如果你是区块链开发者可能已经知道的原语，如 SNARKs 和 STARKs。底层数学也会不同：SNARKs 和 STARKs 往往涉及许多多项式、哈希和椭圆曲线，而混淆将有大量的格、向量和矩阵。

符号说明

• 本文中的描述基于不同论文方法的组合，并不完全遵循其中任何一篇。
• 在某些情况下，符号和词汇的选择将与任何单个底层文章不同。
• 向量是小写，矩阵是大写。
• 在图中，灰色文本和虚线非正式地表示“X 依赖于 Y，但你不必将 Y 实际传入 X，因此 X 的（大小/运行时间）可能远小于 Y 的（大小/运行时间）”。
• “iO” = “indistinguishability obfuscation”(不可区分性混淆)，区别于“IO” = “input/output”(输入/输出)，以及两者都区别于英属印度洋领地（British Indian Ocean Territory），.io TLD 就是以它命名的。

标准流程

当今构建的“在合理程度上可证明安全”的混淆协议，是建立在一个有十年历史的构造塔之上的：AJ15 / BV15 / LPST15 / LPST16 这系列工作。

AJ15 和 BV15 是两篇大致同时的论文，都发现了大致相同的方法来在一种称为功能加密的原语之上构建混淆：“权威”发布与函数 $F$ 绑定的密钥，一旦这些密钥存在，任何拥有加密密钥的人都可以加密 $x$，使得任何拥有解密密钥的人都可以恢复 $F(x)$。LPST15 提出了类似的想法。但所需的功能加密需要具有非常强的属性，而这些属性当时尚不可用。幸运的是，一年后，LPST16 发现了一种在类似原语之上构建混淆的方法，即次线性紧凑随机编码，然后将其构建在已知的“简洁但不紧凑”的功能加密方案之上，再加上一个称为 XiO 的新原语——XiO 的大小仅比发布函数在所有可能输入上的输出表略微小一点。此后的大部分工作都集中在寻找实际实现 XiO 的方法上（尽管有些协议采用了其他路线，例如 JLS20）。

我们将把这个描述分成三部分：

1. 假设你有简洁 FE 方案和 XiO 方案，如何构建混淆协议？
2. 如何构建简洁 FE 方案？
3. 如何构建 XiO 方案？

假设你有简洁 FE 方案和 XiO 方案，如何构建混淆协议？

有几种方法可以在简洁 FE 和 XiO 之上构建混淆协议，它们在高层次原理和属性上大致相当。因此，我将坚持使用 LPST15 设计的简化版本。

请注意，在本文中，我们将经常互换使用“函数”和“电路”。电路是一组 AND、OR、NOT 等门，通过导线连接，可用于评估函数。为了更好地理解电路，我推荐这篇解释混淆电路的文章（这是我们稍后无论如何都会需要的一个原语）。

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

这是简洁 FE：

权威生成与电路无关的公共参数，以及针对一个公开已知的、具有单比特输出的函数（电路 $C$）的电路特定解密密钥。

加密者可以使用加密密钥来加密 $x$。此步骤的运行时间不会（或只是略有增加）随着 $C$ 的电路大小而增加，尽管它与输入长度成线性关系。

解密者可以使用解密密钥来学习 $C(x)$，并且除了 $x$ 之外什么也获知不到。此步骤的运行时间确实会随着 $C$ 的电路大小而增加。

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

功能加密本身不足以用于混淆，因为 (i) 它不隐藏函数，并且 (ii) 每个发布的加密绑定到一个输入，并且只能解密在该输入上评估的函数。但它让你走完了很长一段路。

请注意，简洁 FE 更常见的定义要求 FE 能够容忍高的电路大小，而不是高的电路深度。然而，在我们的使用中，我们确实需要容忍高深度。幸运的是，深度无关的简洁 FE 是深度有界简洁 FE 的一个相当简单的封装（我们稍后会讨论），因此本文将假设我们使用的简洁 FE 也是深度无关的。

现在，这是 XiO：

生成者为一个具有单比特输出的隐藏函数（电路 $C$）选择参数。他们生成该函数的编码。此步骤允许花费与在所有可能输入上评估 $C$ 一样长甚至更长的时间，但输出必须小于真值表（所有可能输入的输出集合）。

评估者评估编码，以学习任何输入 $x$ 的 $C(x)$。

XiO 所设计的那类函数，最好被理解为零输入函数（或称“thunks”），它们产生一个庞大但大小可控的输出。给定一个 thunk $()\rightarrow X$，我们可以将其视为一个函数 $i\rightarrow X[i]$，即一个以索引 $i$ 作为输入，并返回 thunk 的第 $i$ 个输出的函数。这是同一对象的两种不同视图；在本文中，我们将经常在这两种视图之间来回切换。

例如，你可以想象将一个生成 STARK（大约 128-512 kB 大小的密码学证明）的函数，转变为一个以索引 $0 \leq i < 2^{22}$ 为输入，在内部生成 STARK，然后输出 STARK 的第 $i$ 位的函数。XiO 的目标是成为一个比 STARK 更小的工具（尽管注意：即使是一个 STARK 也可能太小，以至于已知的 XiO 协议实际上无法缩小它），让你能够生成那个 STARK，而无法了解关于生成它的底层过程的任何其他信息。

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

让我们仔细地过一遍。目标是创建一个 $P()$ 的“随机编码”——即一个能够执行 $P()$ 的工具——它在渐近意义上比 $P$ 的运行时间更小，也比它的输出更小，并且隐藏 $P$。

这与通常的随机编码展示方式略有不同，后者操作于 $P(x)$ 并隐藏 $x$ 而不是 $P$（例如，混淆电路就是这样工作的），但这就是我们的用例所需要的——混淆完全是为了隐藏函数。

我们将要使用的原语本身并不隐藏函数。为了解决这个问题，我们让这些原语所操作的“外部”函数只是一个虚拟机（或“图灵机”）——基本上，一个以电路为输入的函数 $VM$，因此 $VM(P,X)=P(x)$。评估 $VM$ 的电路通常被称为通用电路。这样，$P$ 就变成了另一个输入，它可以被保密。

关于渐近复杂度的一个细微差别：$VM$ 需要被实例化为一个电路，而电路的大小必须与其运行时间成正比（因为电路不允许循环）。因此，$VM$ 电路的大小必须与 $P$ 的运行时间成正比。幸运的是，简洁 FE 允许即使电路很大且很深，生成过程也很快。然而，输出可能具有随 $P$ 大小而扩展的大小和加密成本。这就是为什么 $P$ 必须用电路以外的语言（例如图灵机）来表达：即使计算变得很大，其大小也必须是固定的。

我们对简洁功能加密进行可信设置，其中创建者发布 $VM$ 的公共参数和解密密钥。这允许任何人加密 $(P,x)$，使得其他任何人都可以解密 $VM(P,x)=P(x)$，但不会了解 $P$ 或 $x$。

为了生成这个随机编码，创建者将上述两个原语相互包裹：他们对 $VM(P,x)$ 的简洁 FE 加密进行 XiO。简洁 FE 加密隐藏了 $(P,x)$，并且即使 $P$ 需要很长时间运行，生成过程也很快。但简洁 FE 不是输出压缩的：如果输出很大，简洁 FE 加密甚至更大（并且这是该类构造不可避免的限制）。XiO 将大小削减回来。创建者制作一个电路 $C_{sfe}(i)$，它输出简洁 FE 加密的第 $i$ 位，并在其上应用 XiO。现在，其大小在渐近意义上比程序 $P$ 本身更小，并且生成速度也更快（注意“渐近”：在较小规模下，方案的开销占主导地位，我们想要的关键属性是，对于足够大的电路，$xIO(sFE(VM(P,x)))))$ 在字节大小和生成时间上都变得比 $(P,x)$ 本身更小）。

注意，这里我们已经首次瞥见了混淆：创建者自己既可以进行可信设置，也可以发布 $xIO$，其他人可以在不了解正在运行的程序的情况下执行它。但我们有一个大问题：这只适用于一个预先配置的输入。

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

本质上，我们采用了次线性紧凑 RE 原语，并递归地应用它，递归次数取决于你试图混淆的函数的输入位数。在基本情况下（零输入），我们就像上面那样直接使用次线性紧凑 RE。为了增加一位，我们对生成两个低一级混淆的过程进行次线性紧凑 RE：混淆函数 $P_0(x)$，它执行 $P$ 但将第一个输入位固定为 $0$；以及 $P_1(x)$，它执行 $P$ 但将第一个输入位固定为 $1$。

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

• XiO 确保这个混淆可以小于它正在生成的两个子混淆。
• 简洁 FE 确保它可以在生成速度上快于它正在生成的两个子混淆。

这两个属性都是确保递归避免爆炸所需要的。

为了评估一个混淆后的程序，你评估顶层的 RE 以得到两个新的混淆（两者都少需要一个输入位），然后根据第一个输入位选择左边或右边，然后继续向下递归，直到你碰到一个 thunk，它为 $x$（即你走过的完整路径）生成 $P(x)$。

这是看待正在发生的事情的另一种等效方式：

对于具有 $n$ 位输入的程序，存在一个深度为 $n$、大小为 $2^n$ 的所有可能评估树。然而，这个树的大部分从未被评估。整个东西是一个“thunks”的树，因此创建树的指数级成本永远不会被支付，因为所有不在你关心的特定输入路径上的 thunks 实际上从未被实例化。唯一确实被实例化的是从根到输入路径上的每一步的混淆。在高层次上，就是这样，这就是核心设计。

请注意，最初的 LPST15 和 LPST16 论文描述的内容略有不同（但等效）：他们不直接递归混淆，而是递归一个“节点程序”。这种方法的一个很好的特性是，节点程序捕获了“到目前为止的输入位”，因此你不必操作或包装 $P$ 本身；在他们的版本中，$P$ 在整个过程中保持不变。

上述描述忽略的另一件事是，为了安全，混淆需要是随机化的。所以实际上，它不是 $iO(P)$，而是 $iO(P,seed)$，其中 $seed$ 是一个被哈希以生成混淆电路等原语所需（伪）随机性的值。随机编码、XiO 和简洁功能加密也都采用 $seed$ 作为参数。当这些函数中的任何一个作为子例程调用其他函数时，它应该通过从其自身的 $seed$ 进行哈希来为子例程生成 $seed$，并注意为每一个提供唯一的不同的 $seed$。为了使安全证明清晰，哈希在技术上必须是一个可穿刺 PRF，尽管有趣的是，哈希的可穿刺版本需要能够构造，但实际上从未运行。

如何构建简洁 FE 方案？

坏消息是：简洁 FE 方案是一个复杂的构造塔，一个堆叠在另一个之上。

好消息是：这些构造相对容易理解，使用非常标准的密码学假设（“仅仅是”格），并且构建简洁 FE 的流程自 2014 年左右以来就已为人所知。

这是首先的图：

让我们逐一过一遍。两个最基本的构建块是混淆电路和全同态加密。

混淆电路

这里有一篇文章，我详细解释了混淆电路。基本总结如下：

• 对于电路中的每条导线，你生成两个标签，一个代表 $0$，一个代表 $1$。
• 对于每个门，你发布一个表格，说明哪对输入标签对应哪个输出标签，按标签排序存储，这样就不清楚哪个输入标签对应 0，哪个对应 1。
• 输出标签不是“明文”给出的；相反，它们通常与两个输入的哈希进行异或。这使得它们在需要时可以计算，但防止你了解除了你拥有两个输入标签的那个“分支”之外的任何信息。
• 要执行，你需要获得对应于你的输入的标签，然后你“沿着电路走下去”，最终确定末端导线的值（这些值实际上是值，而不仅仅是标签）。

混淆电路只能安全地执行一次。如果你给某人两个输入的标签，他们能够计算出远不止两个输出的内容。混淆电路最初是作为 2-of-2 多方计算原语开发的：我有一个电路 $C$，你知道 $x$，我发给你一个 $C$ 的混淆，对于每个输入导线，我使用一种叫做不经意传输的技术帮助你学习两个输入导线中的一个，而我不知道是哪一个，然后你沿着电路走，计算出输出 $C(x)$。

关于不经意传输如何工作的一个基本粗略描述：你发给我两个公钥 $A$ 和 $B$，它们必须加起来等于某个随机哈希，这样其中一个只能有一个有效的私钥，但我不知道是哪一个，我用 $A$ 加密一个标签，用 $B$ 加密另一个，你解密你有私钥的那个标签，但我无法分辨是哪一个。

然而，这里我们不是在做 2-of-2 计算。相反，我们使用混淆电路作为成分来获得简洁 FE 所需的属性。混淆电路有许多有价值的属性。特别是：

• 你可以给某人输入标签而不透露输入。
• 由于每个门的工作是并行的，为 $C$ 生成一个混淆电路是低深度的，即使 $C$ 本身非常深。

这两个属性都很重要。

混淆隐藏了一些关于电路的信息，但不足以对任何需要函数隐藏的用途有意义地有用。当需要函数隐藏时（例如 2-of-2 MPC 用例），一个典型的解决方案是混淆一个通用电路（又名虚拟机），并让电路提供者也提供他们想要运行的实际电路 $C$ 作为成为输入一部分的标签。对于我们的用例，我们不关心混淆泄露函数的细节，实际上正是因为我们采用了这种“将其包装在虚拟机中”的技巧。

全同态加密 (FHE)

这里有一篇文章，我详细讨论了 FHE。因为细节对于本文后面的其他构造很重要，我将提供一个基本总结。

FHE 基于一个称为带误差学习 (LWE) 的密码学假设。基本上，如果你有一个模某个数的线性方程组的近似解（即矩阵 $A$，向量 $s$ 和 $b$，模数 $q$，使得 $b=(As+e)$ 模 $q$，其中 $e$ 是一个“小的”（又名“低范数”）误差向量，因此 $e$ 中的每个值都远小于 $q$），那么给定 $b$ 和 $A$，你无法提取 $s$。如果你有一个精确方程 $sA=b$，那么这是一个线性方程组（模 $q$），可以通过高斯消元法相当廉价地求解。但是加上误差后，进行这种求逆在计算上是不可行的。

有许多基于此假设的 FHE 算法，它们具有不同的属性。最简单的想法涉及随机选择一个私钥 $s$，生成一个随机矩阵 $A$，并计算 $b=As+e+m\frac{q}{2}$ 模 $q$ 作为单个比特 $m$ 的加密（这里，给一个向量加一个比特，是将该值添加到向量的每个元素）。

创建者随后可以发布用这种方式计算的 $0$ 和 $1$ 的加密。要解密，你可以计算 $b-As$，它等于 $e+m\frac{q}{2}$；高阶位编码了消息，低阶位编码了可以被丢弃的误差。如果你有两个密文 $b_1$ 和 $b_2$，它们是 $x_1$ 和 $x_2$ 的有效加密，那么 $b_1+b_2$（同样，所有模 $q$）是 $x_1+x_2$ 的有效加密。

还要注意，上述设计可以支持在消息槽中加密向量的比特，而不仅仅是单个比特。但实际上，上述设计不支持一个关键操作：乘法。

乘法比加法更棘手，原因有几个。首先，你不能将两个向量彼此相乘得到向量；你只能对矩阵或多项式等其他结构进行乘法。其次，将两个三项值 $As+e+m\frac{q}{2}$ 相加会得到另一个三项值，而将两个三项值相乘会得到一个九项值，因此你仍然得到了一个不同的“形状”。第三，你最终会将“小的”误差乘以“大的”其他东西，这使得误差在一次乘法后就爆炸式增长。

没有一个简单的解决方案。有几种解决方案家族，它们都有不同的缺点。使用多项式的方案基于一个更强的假设，称为环 LWE；一个常用的方案是 BFV。对 FHE 使用最方便的方案是基于矩阵的，称为 GSW。为了展示它是如何工作的，我将首先展示一个简化版本，它使基本算术工作，但不处理误差问题，因此如果有非零误差，它就会失效。

首先，生成一个秘密 $s$。为了加密一个值 $m$，首先生成一个在其他方面是随机的矩阵 $A$，使得 $s*A$ 等于某个“小的”或“低范数的”误差 $e$。一种方法是将两者分成两部分生成：

• 生成一个随机的 $s_{prefix}$，然后设置 $s=(-s_{prefix} | 1)$（$ | $ 是拼接）
• 生成一个随机的 $A_{prefix}$ 和一个随机的低范数误差 $e$，然后设置 $A=\begin{pmatrix}A_{prefix}\ s_{prefix}*A_{prefix}+e\end{pmatrix}$（这是垂直拼接）

然后，计算 $c=A+mI$（其中 $I$ 是单位矩阵）。为了解密密文，读出 $(sC)[-1]$（即 $s*C$ 的最后一个值）。

如果你是数学家，你可能会注意到，我们是在将 $m$ 隐藏到 $C$ 的一个特征值中：$s$ 是特征向量，因此它满足 $sC \approx sm$。它们并不完全是精确的特征向量和特征值；它们是带误差的特征向量和特征值。但首先，我们可以将误差放在一边，并注意一些使特征值特殊的属性。

密文加法再次是平凡的：如果

$C_1$ 满足 $(s*C_1)[-1] \approx m_1$

$C_2$ 满足 $(s*C_2)[-1] \approx m_2$

那么

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

但与之前不同，我们也可以乘密文：如果

$sC_1 \approx sm_1$

$sC_2 \approx sm_2$

那么

$s*(C_1*C_2)$

$=(s*C_1)*C_2$

$\approx m_1sC_2$

$\approx m_1m_2s$

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

现在，让我们重新引入容错性。上述机制，正如所写的，有一个致命缺陷：如果你写出包含误差的完整方程，你会将误差乘以 $C$ 和 $s$ 的元素，这些元素可以在整个范围 $[0,q-1]$ 内。因此，这会立即将误差放大到最大值。此外，即使是解密也无法容忍误差。

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

这是小工具矩阵的样子：

这单独看起来不错，但没有太大意义。然而，它旨在与一个它抵消的操作（不是一个矩阵）配对：矩阵位分解操作：

此操作输出中每四个相邻的值（我们称之为“$G^{-1}$”）是输入中相应位置值的（最低有效位优先）二进制编码（又名位分解）。

关于 $G$ 和 $G^{-1}$ 最重要的事实是：

• $G^{-1}$ 的输出是“低范数的”（所有小值）
• 对于任何 $x$，$G*G^{-1}(x)=x$

你可以直观地看到后者。在上面的例子中，追踪高亮显示的 $2$ 的位分解（0 1 0 0）通过计算，然后它被乘以小工具中的 1 2 4 8，结果是 $(01)+(12)+(04)+(08)=2$。也就是说，如果你将小工具矩阵应用于一个位分解，它会“求值”位分解以恢复原始值。

在简化描述中使用单位矩阵 ($I$) 的地方，在实际协议中我们使用 $G$。也就是说，密文的形式是 $A+m*G$。我们通过计算 $C_1 * G^{-1}(C_2)$ 来乘两个密文。消息被隐藏在一个不再完全是带误差的特征值的东西中，但我们仍然保留了所需的属性。数学最终以相同的方式工作，但由于误差永远不会被大数相乘，乘法实际上可行。具体来说：

• 加密：$C = A + m*G$
• 解密：$\frac{(s*C)[-1]}{q/2}$
• 加法：$C_1 + C_2$（显然）
• 乘法：$C_1 * G^{-1}(C_2)$

注意解密中的一个微妙之处。$G$ 的最后一列包含 $\frac{q}{2}$ 作为其唯一的非零条目，因此乘以 $G$ 实际上给了我们一个包含 $m*\frac{q}{2}+e$（而不是 $m+e$）的对象。这给了我们解密时的容错性。这也是为什么我们现在在加密时要除以 $\frac{q}{2}$ 的原因。请注意，此方法需要 $q$ 是 2 的幂。如果你愿意，你可以让 $q$ 为其他值，但这需要稍微调整解密过程。

我们可以检查乘法的正确性。让我们从代数开始。首先是加法：

$C_1 = A_1 + m_1*G$

$C_2 = A_2 + m_2*G$

然后是乘法：

$C_1 * G^{-1}(C_2)$

$= (A_1 + m_1*G) * G^{-1}(C_2)$

$= A_1 * G^{-1}(C_2) + m_1 * G * G^{-1}(C_2)$

$= A_1 * G^{-1}(C_2) + m_1 * C_2$

$= A_1 * G^{-1}(C_2) + m_1 * A_2 + m_1 * m_2 * G$

现在，我们必须证明前两项都是有效的“填充”，就像原始的 $A_1$ 和 $A_2$ 是有效的填充一样。我们需要的核心属性是，乘以 $s*A$ 只留下一个小的低范数误差。

第二项很简单：$A_2$ 是一个有效的填充（$sA_2$ 是低范数的），我们将其乘以 $m_1$，它是小的，因此 $m_1A_2$ 也是低范数的，因此是一个有效的填充。

对于第一项，让我们展开 $sA_1G^{-1}(C_2)$。$sA_1$ 返回一个“小的”误差。$G^{-1}(C_2)$ 返回一个由 0 和 1 组成的矩阵。因此，$sA_1*G^{-1}(C_2)$ 是一个小误差乘以一个由 0 和 1 组成的矩阵，这仍然是一个小误差。

第二个填充中的误差会大致按消息空间的大小（因此，$0$ 或 $1$）放大。第一个填充中的误差会大致按矩阵的大小放大。因此，每次乘法都会将误差放大一个常数因子，因此我们可以预测 FHE 在误差变得过高之前能够承受多少次乘法。此时，你需要通过自举来重置误差：在 FHE 内部评估 FHE 解密电路。

最后，还有一个细微差别：为了保持误差放大有界，我们需要消息保持较小；具体来说，它们必须是 $0$ 或 $1$（我们可以也接受例如 $-1$ 或 $2$）。加法和乘法不尊重大小限制，与 BGV 不同，这里我们没有原生的模 $2$ 环绕。因此，为了使上述算法安全，你需要使用像这样实现的“逻辑门”的电路：

• $AND(a,b)=ab$
• $OR(a,b)=a+b-ab$
• $XOR(a,b)=a+b-2ab$
• $NOT(a)=E_1-a$ 其中 $E_1$ 是对 $1$ 的加密。

这只是一个方法；它不是最优的；有更高效的方法，这是 FHE 优化艺术的一部分。

这里有一些遵循这种 GSW 风格的 Python 代码，尽管注意它使用了一种略有不同的技术，其中 $A*R$ 是“填充”而不是 $A$（它具有上述所有属性，外加一个我们稍后需要的额外属性）。<https://gist.github.com/vbuterin/f0f8a9eb09633226ada20c21a98d537e>

动手玩玩这种 FHE 是值得的，因为它有助于建立对我们将要在下面使用的一些其他原语的直觉。

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

属性基加密 (ABE)

不是这个 Abe。

也不是这个 Abe。

也不是这个 Abe。

下面是属性基加密的定义：

权威为具有电路 $C$ 的函数生成密钥，他们生成一个“主公钥” $mpk$（公开），以及一个依赖于 $C$ 的秘密密钥 $sk_C$（给解密者）

加密者知道 $m$（要加密的消息），他们知道该消息的标签，他们不一定知道 $C$，但知道 $mpk$。他们生成一个密文 $T$

给定这样的 $T$ 和 $sk_C$ 的解密者可以在 $C(tag)=0$ 时解密恢复 $m$，否则不能。

通常，属性基加密是通过这样的例子来证明其合理性的：$m$ 可能是某家医院 $H$ 的医疗记录，$tag$ 可能是一个代表“你在 $H$ 工作并且你有医学学位”的对象，因此很容易以这样一种方式加密医疗记录，使得只有预期的医生可以看到它们。然而，据我所知，能很好地映射到这种范式且不能通过更简单的公钥加密轻松解决的用例数量非常少。因此，ABE 在实践中并未得到太多使用。

但这里，我们有一个非常好的消息：ABE 具有一些有价值的属性，使其在构建功能加密方面非常有用！（因此，也用于构建混淆）特别是，即使对于大型电路，加密也是廉价的。这是允许混淆中的“thunks”在创建时比执行时更快，从而使得指数级大小的树成为可能的非对称性的最终种子。

以下是 ABE 的工作原理。这里我们将遵循 BGG+14 构造，其属性对于简洁 FE 和混淆用例是理想的。

我们在一个电路上工作。为了在你的脑海中有一个例子，采用我们在混淆电路示例中使用的电路（它是一个两比特加法器），但移除“每条导线两个标签”的部分：

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

初始的 $B_i$ 是随机生成的。为了生成更下游导线的 $B$ 矩阵，我们沿着电路走下去，经过每个门：

• 如果是 ADD，则计算 $B_{out}=B_L+B_R$
• 如果是 MUL，则计算 $B_{out}=B_R*G^{-1}(-B_L)$

如同在 FHE 中，我们需要以保持导线值在 ${0,1}$ 中的方式，从 ADD 和 MUL 构建 OR、XOR 和 AND。

权威发布与电路无关的 $A$ 和 $D$，以及电路输入导线的 $B_i$。他们还为解密者提供解密密钥，一个低范数矩阵 $R_f$，满足 $(A|B_f)*R_f=D$，其中 $B_f$ 是编码输出（即 $C(tag)$）的导线的 $B$ 矩阵。注意，$B$ 矩阵的构造不依赖于电路的输入，这就是为什么权威能够以一种对所有输入都有效的方式构造 $B_f$。为了使 $(A|B_f)*R_f=D$ 方程正确，$A$ 需要以特殊方式构造，使其具有一个“陷门”；我们稍后会回到这一点。

首先，让我们过一遍加密者和解密者的逻辑。

要加密，加密者选择一个随机向量 $s$，并计算 $c_{out}=sD+e_{out}+\frac{q}{2}m$。他们还提供输入编码：$c_i=s(B_i+Gtag[i])+e_i$，以及 $c_A=s*A+e_A$。注意加密如何不依赖于电路本身；它只需要知道并对输入 $B_i$ 和 $D$ 进行一些乘法。

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

这里，ADD 情况再次是平凡的：$c_{out}=c_L+c_R$。MUL 情况更难一些。

公式是：$c_{out}=x_Rc_L+c_RG^{-1}(-B_L)$

这里的 $x_R$ 是计算中该导线的实际值。要理解为什么这样可行，让我们依次查看每个组成部分。为了便于说明，我将 $G^{-1}(-B_L)$ 写为 $R_{-L}$；只需记住，因为 $G$ 和 $G^{-1}$ 会抵消，$G*R_{-L}=-B_L$：

$x_R*c_L$

$=x_R*(s*(x_L*G+B_L)+e_L)$

$=x_Rs(x_LG+B_L)+x_Re_L$

$=s*(x_Lx_RG+x_RB_L)+x_Re_L$

$c_R*R_{-L}$

$=(s*(x_R*G+B_R)+e_R)*R_{-L}$

$=s*(x_RGR_{-L}+B_RR_{-L})+e_RR_{-L}$

$=s*(-x_RB_L+B_RR_{-L})+e_R*R_{-L}$

如果我们将两者相加，$x_R*B_L$ 项会抵消，我们得到：

$s*(x_Lx_RG+B_RR_{-L})+x_Re_L+e_R*R_{-L}$

左边的 $B_RR_{-L}$ 就是 $B_RG^{-1}(-B_L)$，这是我们上面给出的乘法的 $B_{out}$ 定义。右侧是误差乘以低范数值，因此它保持为低范数误差。

因此，解密者拥有他们所需的一切来一路走到 $c_f$。

如果 $C(tag)=0$，那么 $sx_fG$ 项从 $c_f$ 的定义中消失，我们只剩下：$c_f=s*B_f+e_f$

一旦他们到达 $c_f$，他们会在前面拼接上 $c_A$ 得到 $c_f'=(c_A | c_f)$，它满足 $c_f'=s*(A | B_f)+e_f'$。然后他们计算：

$c_{out}-c_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 - sD - e_f'*R_f$

$=e_{out}+\frac{q}{2}*m - e_f'*R_f$

如果误差没有爆炸得太厉害（记住，$R_f$ 也是低范数的），解密者现在可以自由地恢复 $m$。

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

我们不随机构造 $A$。相反，我们将其构造为 $A=(A_{prefix} | G - A_{prefix}*R)$，其中 $R$ 是一个低范数的“陷门”，而 $G$ 是之前的小工具矩阵。类似于我们见过的 FHE 密文，根据 LWE 假设，如果你自己没有陷门，这种构造在计算上无法与随机区分。

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

$A*R_I$

$=(A_{prefix} | G - A_{prefix}*R)*R_I$

$=A_{prefix}*R + (G - A_{prefix}*R)*I$

$=A_{prefix}*R + G - A_{prefix}*R$

$=G$

或者用图形表示：

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

这里的目的是，我们想要创建这样的矩阵，对于任何已知向量 $u$，只有创建者可以找到一个低范数向量 $r$，使得 $A*r=u$。也就是说，陷门让我们能够“求解”短整数解 (SIS) 问题，该问题与 LWE 密切相关，并且是这种密码学工作的基础。

算法如下：

• 对 $u$ 进行二进制分解（即对其应用老派的 $G^{-1}$），让输出为 $z$
• 输出 $r=R_I*z$

$R$、$I$ 和 $z$ 都是低范数的，因此这也是低范数的。为了从代数上理解为什么这能解出方程，计算：

$Ar = AR_Iz = Gz = u$

为了保证这是安全的（在不泄露 $R$ 的意义上），实际实现在这一步会添加额外的误差；参见 MP12 以了解最高效地实现此目的的方法的更多细节。

现在，让我们回到上面仍未解决的谜题：计算 $R_f$。

我们要解的方程是：

$(A | B_f)*R_f = D$

我们将 $R_f$ 解释为 $\begin{pmatrix}R_{top}\ R_{bottom}\end{pmatrix}$，因此我们得到：

$AR_{top} + B_fR_{bottom} = D$

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

$AR_{top} = D - B_fR_{bottom}$

在这里，我们只是逐行使用上述方法来计算 $R_{top}$ 的每一行。我们就完成了。

敏锐的读者可能会注意到与环签名的模糊相似之处，至少在 1-of-2 情况下是这样：你“以简单的方式”计算两项中的一项，而使用陷门计算另一项以匹配（这是你“本不应能够做到的”）。

为清晰起见，请注意陷门中的 $R$ 永远不会被给出，甚至不会给解密者。给解密者的是 $R_f = \begin{pmatrix}R_{top}\ R_{bottom}\end{pmatrix}$。

现在，让我们总结一下我们拥有的：

• 两个全局公共矩阵 $A$ 和 $D$，一个是随机的，另一个是通过陷门计算的。
• 每条导线一个矩阵 $B_w$；输出导线的矩阵是 $B_f$
• 一个解密密钥 $R_f$，满足 $(A | B_f)*R_f = D$
• 加密是 $c_i$ 值，每个输入导线一个，以及一个对应于 $A$ 的 $c_A$ 和一个对应于 $B_f$ 但混入了消息的 $c_{out}$。
• 解密者走到 $c_f$，并计算 $c_{out} - (c_A | c_f)$ 以获得消息。但这仅在 $C(tag)=0$ 时有效；如果不是，则会混入一个 $sx_fG$ 项，破坏一切。
• 其中最令人惊奇的属性是，你能够生成一个密文，其可解密性依赖于一个长时间的计算，而你自己从未运行那个计算（尽管一个“权威”——想想可信设置——确实也需要运行一次）

这个方案的主要限制在于电路深度：每次乘法会使误差增加一个常数，因此电路越深，需要的值和矩阵就越大以进行补偿。理论上你可以做任意深度的电路，但如果尝试，为了使密文足够大以处理误差而带来的开销会爆炸。这就是基本简洁 FE 中深度限制的来源，我们稍后将讨论的封装可以消除这个限制。

这就是 ABE。

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

针对固定深度电路的功能加密

令人惊讶的是，至少对于这一部分，我们已经完成了困难的数学。下一部分将只是拼接乐高积木。

首先，功能加密的定义：

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

加密者使用公钥加密 $x$

解密者学习 $C(x)$ 并且别无其他

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

以下是流程（遵循 GKP+13 构造）。首先，权威的工作。权威选择他们正在为其生成参数的电路 $C$。

• 让 FHE 密文的长度比特为 $w$
• 生成 ABE 公共参数和 $2*w$ 个 ABE 密钥
  • ABE 电路是：“取一个 FHE 公钥 $FHE.pk$ 和 FHE 加密的输入 $Ex$，计算 $FHE.eval(C,Ex)$，输出第 $i$ 位”
  • “第 $i$ 位”有 $w$ 种选择。此外，我们制作一组直接输出第 $i$ 位的参数，以及另一组在输出前翻转它（即解密条件为输出是 $1$）的参数。这样每位贡献两个选项。因此，总共 $2*w$ 组参数。
• 发布 ABE 的公共参数，并将 $2*w$ 个 ABE 解密密钥交给解密者。

一种替代方案是修改 ABE，使其同时加密两条消息，一条只能在 $C(tag)=0$ 时解密，另一条只能在 $C(tag)=1$ 时解密。这会增加一些复杂性，但节省了 $2x$ 开销。

现在，加密者的工作。加密者有一个他们想要加密的值 $x$。

• 生成一个 FHE 密钥对 $(FHE.sk, FHE.pk)$，加密 $x$ 得到 $Ex$
• 生成一个电路的混淆，该电路接收密文 $Ey$ 并输出 $FHE.dec(Ey, FHE.sk)$（注意，这里 $FHE.sk$ 被硬编码在电路中）
• 这个混淆电路有输入标签 $L_{index,bit}$，然后还有每个中间门和输出的更多标签。使用第 $(index, bit)$ 个 ABE 密钥加密 $L_{index,bit}$，以 $Ex$ 作为标签。
• 输出：$FHE.pk$，$Ex = FHE.enc(x, FHE.pk)$，以及完整的混淆，但输入标签是加密的。

解密者使用 $Ex$ 作为标签，对加密的 $L_in$ 标签执行 ABE 解密过程，从而学习输入标签。他们运行混淆并得到输出。

现在，让我们总结一下我们在这里做了什么：

• 我们保持了 ABE 的属性，即加密者不必运行电路；只有权威和解密者需要运行。
• 我们改变了逻辑：不是电路 $C$ 决定你是否可以解密某个无关的消息 $m$，而是电路本身就是你唯一可以解密的 $x$ 的求值。
• 核心思想是，ABE 的属性（只有当你被“期望”解密时，如某个电路 $C$ 所定义的那样）确保解密者只得到他们应该得到的混淆输入标签。混淆允许他们仅解密那个值。如果他们试图运行不同的计算，那么 ABE 解密中的 $c_f$ 将有一个额外的悬空的 $s*G$，他们将无法完成解密以获得有效的输入标签，因此他们将无法运行混淆。
• 我们继承了 ABE 的主要限制：因为在 ABE 内部进行的是电路的同态加密评估，其深度等于电路深度乘以一个显著的放大因子，所以它只适用于有限深度的电路。

针对无限深度电路的功能加密

这个是一行搞定。你不是对 $C$ 进行 ABE 加密，而是对这样一个函数进行 ABE 加密：它接收 $x$ 作为输入，并生成 $C(x)$ 的混淆电路（例如，使用 $hash(x)$ 作为混淆的随机性）。混淆电路的生成是可并行的，因此即使是高深度的电路，它也是低深度的。解密者运行低深度 FE 以获得包含适当输入标签的混淆电路，然后以明文方式沿着混淆电路走，以获得输出。

就这样，我们完成了简洁功能加密！为了回顾整个内容，这里是我们原来的图：

如何构建 XiO 方案？

让我们先记住 XiO 的定义：

生成者为一个具有单比特输出的隐藏函数（电路 $C$）选择参数。他们生成该函数的编码。此步骤允许花费与在所有可能输入上评估 $C$ 一样长甚至更长的时间，但输出必须小于真值表（所有可能输入的输出集合）。

评估者评估编码，以学习任何输入 $x$ 的 $C(x)$。

从技术上讲，“XiO”代表“指数（低）效不可区分性混淆”，但最好不要把它当作混淆。相反，它是一种压缩数据的方式，适用于数据是由一个比数据本身小得多的程序生成的特殊情况，并且你想要隐藏该程序。它是为输出 $n$ 位的“thunks”（零输入函数）设计的，而不是你可能直觉上认为的“实际函数”。

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

假定生成者拥有 FHE 加密和解密密钥，以及一个他们心目中的特定密文。我们假设一种加密方案，它能够高效地加密向量（而不仅仅是单个比特）。给定一个编码特定向量 $v$ 的特定密文 $C$，他们生成一个提示 $h$，它比 $v$ 小得多。

解密者，给定 $C$ 和 $h$，可以使用提示解密 $C$ 得到 $v$，但不能用它解密任何其他密文或学习任何关于 FHE 密钥或 $C$ 派生的计算的信息。

以下是建立在拆分 FHE 之上的 XiO 的工作原理：

如果我们正在编码一个输出大小为 $n$ 的 thunk，我们将其视为一个函数 $Q$，它接受一个索引 $i \in {1...n}$，并输出 thunk 产生的第 $i$ 位。

我们将输入空间分成 $n$ 个桶，每个桶的大小为 $n$。对于每个桶，我们（使用 GSW）FHE 加密该桶内的每个索引（例如，第一个桶是 $1...n$，第二个是 $n+1...2*n$），并在每个索引上运行 $Q$。然后，我们使用一种特殊技术将 $n$ 个密文转换为一个持有所有值的打包密文。最后，我们为其发布一个恒定大小的提示。XiO 是所有 $n$ 个恒定大小提示的集合。

这里有三个技术要点需要理解：

• 对 GSW 的一些修改
• 打包如何工作
• 提示机制如何工作

实际上，这三者是相互关联的。我们从未在除了提示生成和基于提示的解密之外的任何上下文中使用打包，而对 GSW 的修改使其无法通过除了基于提示的解密之外的任何方式进行解密，因此我们完全可以将其视为一个算法。让我们逐一过一遍，遵循 WW21 协议。

对 GSW 的修改

记住普通的 GSW：$C = A + \frac{q}{2}mG$，其中每次新鲜生成的 $A$ 满足对于低范数 $e$ 有 $s*A = e$。

这里，我们将 GSW 修改为：$C = A*R + \frac{q}{2}mG + E$，其中 $A$ 是一个固定的“公钥”矩阵，$R$ 是每次随机新选的但低范数的。$E$ 是为了保护 $R$ 不被泄露而引入的新误差，也是每次随机新选的但低范数的。

重要的是，$A$ 是高而窄的，$R$ 是宽而短的。两者的较小维度需要匹配。这很重要，因为这个维度决定了提示的大小。提示不能只是一个值，它需要有一定的宽度以保持 LWE 安全性，但它可以比矩阵的大小小得多，因此也比它将帮助解密的向量小得多。

同样重要的是，用于解密的乘以 s 的技巧会被新的误差矩阵放大，因此不再存在有效的‘解密密钥’。除了进一步求值之外，你唯一能对密文做的事情就是像基于提示的解密机制这样的东西。因此，作者明确地称其为同态承诺方案，而不是同态加密。

打包和提示

假设你有几个上述形式的密文：$C_1, C_2 ... C_k$。它们都共享相同的 $A$，但有不同的 $R_i$ 矩阵，以及不同的 $m_i$（消息）。

以下是我们如何将它们全部组合成一个向量：

• 令 $u_i$ 为一个与 $R$ 和 $G$ 具有相同宽度、全为零的向量，除了在 $\log(q)*i$ 位置处为 $1$（例如，如果 $q=16$，对于 $i=1$，它是 $[ 0 0 0 1 | 0 0 0 0 | 0 0 ... ]$（添加分隔符以便清晰）。注意，$\log(q)*i$ 位置正好是 $G$ 矩阵第 $i$ 行具有最大值的地方。
  • 通俗地说，将 $u_i$ 视为“仅保留 $\log(q)*i$ 列，丢弃其他所有内容”的操作符。
  • 就其角色而言，将 $u_i$ 视为“提取关于密文最有用的东西（消息以最高有效位形式存储的地方），并将其放入输出的第 $i$ 行”。
• 计算 $c_f = C_1u_1 + C_2u_2 + ... + C_k*u_k$

如果 $q$ 不是 $2$ 的幂，你必须做一些稍微复杂的事情：不在 $\log(q)$ 的第 $i$ 块是许多零后跟一个一，它必须是 $\frac{q}{2}$ 的最低有效位优先的二进制编码。前者是后者的 $q=2^k$ 特例。

就是这样。要计算原始提示，我们沿着 FHE 中的加法和乘法，与密文一起“跟踪” $R$ 矩阵（留给读者作为练习：自己过一遍 ADD 和 MUL 的“跟踪 $R$”代数；它紧密遵循与 $C$ 相同的基于 $G$ 和 $G^{-1}$ 的方法以保持误差低范数），然后对 $R$ 应用完全相同的过程：$r_f = R_1u_1 + R_2u_2 + ... + R_k*u_k$

现在，记住 $C_i = AR_i + mG + E_i$，因此如果你从 $C_i$ 减去 $AR_i$，你会得到 $mG + E_i$，它在矩阵的每一行上相邻 $\log(q)$ 个位置包含 $m$。然而，在这里，我们处理的是许多不同的 $R_i'$ 值，并且我们希望有一个单一操作能同时揭示所有 $m_i$。为此，我们采用了一个技巧：在第 $i$ 行，我们使用 $R_i$。因此，如果你计算 $c_f - Ar_f$，结果的第 $i$ 行将正确抵消 $AR_i$，并给出你需要的值 $m_i * q/2$（加上一个误差）。

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

• 生成一个新鲜的秘密 $s$（与提示大小相同）
• 发布 $d_f = r_f + s$，而不是单独的 $r_f$
• 同时发布一个“样本”，$b = A*s + e$

验证者知道 $c_f$，因此他们可以计算：

$c_f + b - A*d_f$

$= (Ar_f + mG + e_1) + (As + e_2) - (Ar_f + A*s)$

$= m*G + e_1 - e_2$

为了安全，样本中的误差必须远大于其他误差，以便完全隐藏关于它们的信息。因此，我们有两层尺度分离：样本误差足够大以抹去其他误差，而消息足够大以避免被样本误差破坏。

这个方案的第二个版本是安全的，但它有一个新的重大问题：样本 $b$ 是全宽的，不像提示那样短。因此，我们再做一个修改：不是直接发布 $b$，而是发布一个生成它的工具。

做法如下：

• 生成者生成一个种子的新鲜加密（即，一个你从中生成哈希的值），并发布种子的 FHE 加密：对于种子中的每个比特，$A*R_i + seed[i]*G + E_i$

• 对于每个桶 $\beta$，生成者和解密者都可以进行以下计算：

  • 在 FHE 内部计算 $Ahash(seed,\beta)+e_\beta$（其中 $e$ 本身是通过取另一个 $hash2(seed,\beta)$ 生成的误差），并得到密文：$C_i = AR_i + m_i*\frac{q}{2} + E_i$，其中 $m_i$ 是 $A*hash(seed,\beta)+e_\beta$ 的第 $i$ 位。
  • 应用我们上面描述的打包过程，但是是对所有 $k*\log(q)$ 列使用 $u_i$，而不仅仅是 $\log(q)$ 倍数列中除了最后一列之外的 $k$ 列。为清晰起见，我们将此视为一个带有两个索引的和：块内索引 $0 \le t < \log(q)$，和块索引 $0 \le j < k$。我们在这里将所有内容视为从零开始索引，以使数学更干净。
    • 记住：原始打包过程给你 $c_f = \sum_i (Ar_i + \frac{q}{2} * m_i)$。在这里，你得到 $c_g = \sum_{j,t} (Ar_{t+\log(q)*j} + 2^t * m_{t+\log(q)*j})$。
    • 我们假设在电路内部，$\log(q)$ 个密文的第 $j$ 块表示 $A*hash(seed,\beta)+e_\beta$ 中第 $j$ 个数的二进制编码。
    • 因此，在第 $j$ 块内，$\sum_t 2^t * m_{t+\log(q)j}$，我们“求值”了 $Ahash(seed,\beta)+e_\beta$ 第 $j$ 个条目的二进制分解，并且由于 $G$ 的结构，所有这些值都被发送到输出的第 $j$ 行。
  • 打包过程的输出是 $c_g = Ar_g + Ahash(seed,\beta)+e_\beta + e_g$。注意，$Ahash(seed,\beta)+e_\beta$ 位于通常 $m\frac{q}{2}$ 所在的位置。这是我们在上面修改打包过程的直接结果。$c_g$ 的表达式可以重写为 $c_g = A*(r_g + hash(seed,\beta)) + e$
  • 生成者可以以明文方式计算 $r_g + hash(seed,\beta)$，而评估者不能。因此，生成者使用这个作为他们混合到提示中的 $s$ 值。

• 解密者的计算与之前相同，只是他们没有从生成者那里接收 $c_f$；他们自己使用上述方法生成它。关于为什么它会抵消的数学也完全相同。

论文使用 $prf$（“伪随机函数”）来指代哈希。这只是意味着哈希需要具有很强的随机性属性（比抗碰撞性强得多，但比随机预言机弱）；如果你信任哈希满足随机预言机模型，那么你可以在任何地方安全地认为 $prf = hash$。

就是这样。XiO 是：

• 系统的公共参数（例如，加密密钥，要评估的加密电路）
• 每个桶的提示 $r_f + s$（其中 $s = r_g + hash(seed,\beta)$）
• 种子的 FHE 加密，以便能够计算让你抵消 $s$ 的样本

评估需要仅为一个特定的桶重做执行，然后使用提示解密最终的向量，最后从该桶中取出你需要的值（在混淆用例中，解密者从所有桶中取出所有值）。

还有一项进一步的优化，可以在保证可证明安全性的同时最大化效率。XiO 的大小是它所编码的 thunk 大小 $n$ 的 $O(n)$，但它需要发布大小为 $n$ 的可信设置参数（这些存在有技术原因：生成抵消提示所需的 $A*s+e$ 样本的函数需要有一个从未被使用的路径，该路径接受并使用完全随机的值，这允许进行安全证明）。这个可信设置的长度为 $n$。如果你将 XiO 拆分成 $\approx n^{\frac{1}{3}}$ 个独立的 XiO，那么 XiO 的大小会上升到 $\approx n^{\frac{2}{3}}$，但可信设置（可以被所有 XiO 重用）也下降到 $\approx n^{\frac{2}{3}}$。

XiO 和安全假设

混淆流水线中除了 XiO 之外的所有部分都可以用相当“标准”的基于格的假设来证明。归根结底，所有密码学都只是猜测某个数学问题“实际上很难”，而不仅仅是我们至今太笨解不出来，但可能明年就能解决。但有些猜测比其他猜测更有依据。在所有的抗量子原语中，支撑格的 LWE 基本假设通常被认为不如哈希可靠，但比几乎所有其他假设（包括更复杂的格假设）更可靠。

但所有现有的 XiO 原语都存在一个问题。上述设计并不能严格地在格假设下被证明。它确实可以在以下形式的假设下被证明：“如果你发布 $A*s+e$ 风格的‘样本’，并且还发布一点额外的信息，那么我们仍然是安全的”。但有一个问题：这类假设以前被攻破过，最终在这里也被攻破了。

2013 年，一个早期的多线性映射候选方案（一个非常强的原语，如果我们拥有它，混淆将容易得多）在 CLT13 中发布。然而，在 2015 年，它被攻破了。

CLT13 发布的对象是 $pzt \approx z * \frac{h}{g}$。密文的形式是 $c = a + \frac{g}{r}z$。如果你将一个 $a=0$ 的密文乘以 $pzt$，你得到 $cpzt = \frac{g}{r}z * z * \frac{h}{g} = rh$。$r$ 和 $h$ 都是非常“小的”值（远小于模数），因此它们相乘的结果也远小于模数。因此，$pzt$ 起到一个“零检查”密钥的作用，它允许你在格密文上执行配对检查风格的操作（与配对不同，如果你缩放参数，它可以乘法到任意深度）。

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

HPLS 猜想，WW21 的核心新假设，表面上也有一种泄露“仅仅是误差”的方式：

• 对手知道 $d_f = r_f + s$，因为它被发布了
• 如果对手拥有 $r_f$，那么有了足够多的这些值，他们可以解线性方程组来恢复秘密（这本身就还可以：毕竟，$s$ 的全部意义就是掩码 $r_f$）
• 如果对手拥有 $s = r_g + hash(seed,\beta)$，那么注意该值满足 $c_g = A*(r_g + hash(seed,\beta)) + e$，因此如果他们将它乘以 $A$，然后从 $c_g$（他们也能计算）中减去它，那么他们就能以明文方式得到一个“误差”值 $e$

注意，即使提取 $e$ 是致命的，WW21 的安全性仍有另一道防线：对手不会学到两个致命秘密（$r_f$ 和 $s$）中的任何一个，他们学到的是两者的和，也许没有有用的组合攻击可以从这个和开始。但即使是提取 $e$ 可能也没问题。HJL21 中的攻击，它打破了 HPLS 假设，设法做了一件特定的事情：他们想出了如何以对手方式构建电路，使得误差的最低有效位（它能经受住通常保护此类方案的“涂抹”技巧）编码了一个变量，该变量输出执行是“真实”的还是用于证明过程的“模拟”执行。总结如下：

• 攻击要求对手精心制作电路；没有任何合法行为者会以对手那样的方式设计电路。
• 攻击只泄露了用于证明方案正确性的机制内部的一个变量，实际上并不泄露任何秘密。
• 攻击需要知道 $s$，而实际上对手只知道 $d = s + r_f$

因此，即使假设在有限情况下被打破，WW21 的安全性很可能没问题。

2025 年发布了一个新协议，它为 WW21 技术中的“帮助解密者发现提示偏移的样本”部分增加了一些额外的复杂性，使其依赖于比 HPLS 更有限、但仍然比普通 LWE 更激进的格假设。特别是，HJL25 使用的假设属于“只发布秘密部分经过模 q 环绕的对象”的框架（这排除了提供“原始误差”和 CLT13 的 $r*h$）。这不如普通 LWE 保守，但这是一个有意义的改进。“普通 LWE”和“秘密部分必须经过模 q 环绕”之间的空间包含像循环安全性这样的假设，以及 HJL25 中的假设。这类假设确实存在反例，但它们是非常牵强的，而基于这些类型假设的实际协议到目前为止已被证明是安全的。

你可能有一个类比是其他“理想化黑盒”假设：

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

到目前为止，ROM 在实践中被证明是好的，但研究人员已经设计出在 ROM 中可证明安全但如果用任何真实哈希算法实例化则容易攻击的签名方案。并且通用群模型已知在少数情况下是错误的，最著名的是通过 Schoof 算法进行阶数查找，以及配对。椭圆曲线安全性建立在一个摇摇欲坠的基础上：你可以以这两种方式违反通用群模型，但不会以更有害的方式。

完全从“标准”假设证明 iO 的唯一协议家族是 JLS20 及其后代，但这些不是抗量子的。

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

另一个重要的注意事项是，如果我们要可证明地归约到这些安全假设，那么对一个 $k$ 位输入程序的混淆的安全证明需要“遍历”所有可能的 $2^k$ 个输入。对于每个输入，你消耗一点点安全裕度。因此，证明消耗的安全裕度可能远远超过 $2^{128}$ 次。出于这个原因，所有这些混淆协议都要求 LWE 参数是亚指数安全的，这意味着密文比普通 LWE 密文大数千倍（并且由于协议的分层性质，这个“数千”自身会叠加多次）。

如果你愿意，你可以“yolo 并忽略这一点”，就像递归 STARK 协议 yolo 并忽略它们要求哈希函数同时是一个随机预言机和一个可以由电路实例化的具体事物一样。这样做可能是可以的，但如果你为了效率做了足够多的可能可以的事情，你就会遇到一个哲学问题：为什么要费那么大力气让混淆在标准假设下可证明安全，而不是采用其他方法（例如 diamond iO），这些方法在激进假设下是可证明安全的，但效率要好得多？

总之，对于“你需要什么样的密码学假设才能构建一个可工作的混淆协议”这个问题的答案是：

• 比 2010 年代强得多，当时混淆建立在矩阵分支程序之上，而这些程序又依赖于基于格的多线性映射——到目前为止，这些多线性映射未能经受住密码学审查，并且经常以致命方式被攻破。
• 但仍然远非完美

XiO 和可信设置

最后，另一个显而易见但重要的事情需要强调：混淆后的程序的安全性在许多地方依赖于可信设置，因此我们距离能够进行完全无需信任的混淆（即，以一种连混淆者自己都不知道秘密的方式生成带有内部秘密的程序）还很远。我们能做到的最好情况是用 $N$ 方可信设置取代单方可信设置。

以下是一种自然的方式。

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

• 如果 $\beta=0$，它将第二个输入解释为一个程序 $P$，并返回 $Obf(Q)$，其中 $Q(input)=P(input,hash(s,P,0))$。也就是说，它接收一个带秘密槽的程序 $P$ 作为输入，并输出 $P$ 的混淆版本，其内部秘密被硬编码在内。
• 如果 $\beta=1$，它将第二个输入解释为随机性，并输出 $Obf(H(H,hash(s,x,1)))$。

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

以下是 $N$ 个参与者的链的样子：

• Alice 运行 $G(G,s_1)$ 来生成 $G_{s_1}$（注意，原始的 $G$ 是未混淆的，但此步骤及以后所有步骤的输出将是混淆的）
• Bob 调用 $G_{s_1}(1,r_2)$，它输出 $G(G,hash(s_1,r_2,1))=G_{s_2}$
• Charlie 调用 $G_{s_2}(1,r_3)$，它输出 $G(G,hash(s_2,r_3,1))=G_{s_3}$

每个参与者还会对其输出 $G_{s_k}$ 使用 $\beta=0$ 在 $P$ 上运行，以混淆 $P$，使用 $s_k$（之前所有秘密的混合）作为秘密，并发布这个混淆。只有最后一个参与者的混淆实际上会混合每个人的秘密，但在我们的模型中，我们假设参与者一个接一个地出现，并且他们都不知道自己是否是最后一个。

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

为了验证每一步的正确性，每个参与者需要制作一个递归 STARK 来证明 (i) 前一步已经过递归 STARK 证明，以及 (ii) 他们正确地添加了他们的随机性。

然而，这种方法极其昂贵：它需要一个混淆的混淆的 STARK。一个开放挑战是找出为混淆实现通用且可更新的可信设置的理想方法。

那么运行时间是多少？

也许关于这些混淆协议最著名的事实是，它们的运行时间在技术上是多项式，但实际上却是天文数字。要了解原因，我们只需要再次看看完整的塔：

• 要解密 FE，你需要运行 ABE 解密，它涉及 FHE 评估，而 FHE 评估又涉及混淆电路的生成。每一个操作都会将计算中的每个比特替换为一个密码学对象——要么是哈希，要么是矩阵。FHE 还需要一个自举步骤，这需要在 FHE 内部运行 FHE 解密。仅仅是 ABE 就有一个 $(\log q)^5$ 的开销，其中 $\log q$ 必须显著高于安全参数 $\lambda \approx 120$。而你将这三者堆叠在一起。因此，仅 FE 就需要千万亿级别的开销因子。
• 要评估次线性 RE，你需要评估 XiO，它是对底层程序的 VM 的简洁 FE 加密。XiO 主要是 FHE；幸运的是，你可以在正在编码的不同比特之间重用中间计算，因此对于大部分工作在于生成单个事物、提取单个比特相对简单的函数，XiO 的开销 $\sim$ FHE 的开销，尽管不幸的是，它是一种非常低效的 FHE。同样幸运的是，XiO 是针对生成简洁 FE 加密的过程，该过程不关心底层的具体内容。但当你评估时，你还必须在 FE 内部生成下一轮的 XiO。

因此，这里的总理论开销大致是：$ABE * FHE * GC * XiO * sFE_{enc}$，其中 XiO 主要是 FHE。所有这些都是针对输入中的每比特。

现在，在所有这些之上，每个单独方案的参数选择必须非常保守以实现亚指数安全性，在每个 LWE 层上增加超过 $1000$ 倍的额外开销。

这就是为什么这些方案今天远非实用；预计的运行时间比宇宙的寿命还要长。

我们接下来要往哪里走？

有三条路线：

1. 某个非常聪明的人（或某个机器人）发现了一种方法来优化和/或简化上述塔，使用与我们今天相似的假设。也许有办法将 ABE 和 XiO 合并成一个单一的工具——也许找到一个构造，它既具有独立于密文的提示（如 ABE），又是真正的全同态，因此你可以计算乘法而不需要明文导线值（如 XiO 中使用的拆分 FHE）。
2. 我们找到一种方法，使用更大胆的密码学格假设来实现混淆，从而创建另一个更简单的塔。
3. 我们找到一种完全不同的方法来实现混淆，根本不使用格。也许这意味着发明一类全新的假设。

路线 (2) 以及特别是 (3) 也意味着我们在实战测试此类假设方面做得更好，也许再次借助 AI 的帮助。

本系列接下来的文章将讨论也许是为实现 (2) 而进行的主要构造：diamond iO，以及也许是为实现 (3) 而进行的主要构造：局部混合混淆。

如果我们在任一路径上取得成功，回报都是巨大的：在某种意义上，我们将“解决密码学问题”：任何可以使用理想化的受信任第三方描述的协议，只要允许对手倒回时钟，都可以安全地实现。但要达到那里仍然是一个艰巨的挑战。

• 原文链接： vitalik.eth.limo/general...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～