混淆技术：打造密码学的终极难题（上）

背景

混淆（Obfuscation）被许多密码学家视为该领域构想出的最强大原语。它的目标是将一个程序 (P) 转化为一个“加密程序” (Obf(P))，使得 (Obf(P)) 可以在明文输入上运行并产生与 (P) 完全相同的明文输出，但程序内部的逻辑和细节却被彻底隐藏。目前最常用的形式化定义是“不可区分混淆”（indistinguishability obfuscation, iO）：如果你拿到两个功能相同但实现不同的程序的混淆结果，你将无法分辨哪个混淆对应哪个程序。本质上，它隐藏的是代码本身，而非数据。

混淆之所以强大，是因为它几乎实现了密码学协议中那个理论上的终极理想——一个通用的“无需信任的受信第三方”。许多密码学协议的设计思路，都是先设想一个能看到所有人消息并诚实回应的受信第三方，然后再想办法在没有信任的情况下实现同样的功能。加密、零知识证明等都可以看作对这种受信第三方的模拟。而混淆（加上哈希）能够为几乎任意协议模拟出一个受信第三方，从而替代上述所有方案，甚至做得更多。唯一的重大例外是：混淆后的程序无法阻止自身被复制，因此无法实现像货币那样需要“状态”的功能——而这恰好是区块链可以填补的空白。因此，混淆与区块链结合，可以构建出几乎无需任何信任假设的安全、私密且抗共谋的投票系统等神奇应用。

然而，构建安全的混淆极其困难。历史上长期存在不安全的混淆实践（如对编译后程序做逻辑混淆以保护商业软件），它们就像凯撒密码一样经常被攻破。与此同时，数学上可证明安全的混淆研究也历经坎坷。2001年，一个著名结果表明，理想的“黑盒混淆”是不可能的——任何代码实现总会泄露超出输入输出关系的信息。此后，研究者转向证明次优目标 iO。这是一个长达二十年的项目，充满了失败尝试、基于尚未存在组件的协议构造，以及反复的试错。直到近几年，终于传来好消息：我们知道了如何在合理的安全假设下实现 iO。

但好消息中也藏着坏消息：这些方案的运行时间堪称“银河级”。虽然理论上是多项式时间，但其构造涉及层层叠叠的“类全同态加密”电路，每比特输入都要生成兆字节级的中间值，并再次嵌套进另一层“类全同态加密”中。最终，这些“勉强可证明安全的 iO 方案”的运行时间超过 (\lambda^{10})（其中 (\lambda) 是安全参数，通常取 100 或 120）。

尽管如此，仍有两个充满希望的叙事。其一，这类似于 2010 年左右的 SNARKs 处境——一旦知道可行，聪明人（和机器人）就会开始逐一攻克瓶颈，不断砍掉数量级的运行时间，最终可能达到“只需在重型 GPU 上跑一天”的水平（听起来仍很昂贵，但对许多有趣应用已足够）。其二，我们可能会看到更多针对同一目标的不同策略：即更擅长提出新的密码学假设，并更擅长判断哪些新假设真正安全。

若将更启发式的方法也算上，目前大致有三个尚未“死亡”的混淆协议家族，它们分布在效率与安全假设“大胆程度”构成的权衡前沿上。本文将详细描述其中最为“银河级”但也最为严谨的那个家族。

核心内容

混淆的愿景与iO的定义

混淆的核心承诺是：给定程序 (P)，生成 (Obf(P))，使得：

• 对任意输入 (x)，(Obf(P)(x) = P(x))；
• 从 (Obf(P)) 中无法获得关于 (P) 内部逻辑的任何额外信息。

iO 的具体形式化是：若两个程序 (P_1) 和 (P_2) 功能完全相同（即对所有输入输出一致），则它们的混淆 (Obf(P_1)) 与 (Obf(P_2)) 在计算上不可区分。这意味着混淆器隐藏了程序的具体实现，只暴露其输入输出行为。

混淆作为“无需信任的受信第三方”

文章将混淆置于密码学协议的“受信第三方”框架下。传统上，协议设计先假设一个能看到所有消息并诚实执行的中心方，再通过密码学工具消除该中心。混淆的独特之处在于，它可以为几乎任意协议模拟出一个受信第三方：你只需将协议逻辑编写成一个程序，然后混淆它。混淆后的程序就扮演了那个“黑盒”角色——任何人都可以与之交互（提供输入、获得输出），但无人能窥探其内部状态或逻辑。这比加密（隐藏消息内容）和零知识证明（证明数据正确性）都更通用。

唯一的鸿沟在于“状态”。混淆程序无法阻止被无限复制，因此无法原生地实现像数字货币那样需要唯一性和状态持续性的功能。区块链恰好能提供这种状态层，因此混淆+区块链的组合可以构建出几乎无需信任的复杂系统，例如安全、私密、抗共谋且无需门限委员会的投票系统。

从不可能到iO：二十年征程

2001年，Barak 等人证明了“黑盒混淆”的不可能性：任何代码实现总会泄露超出输入输出映射的信息（例如，将程序应用于自身代码就能学到东西）。这一结果迫使研究者退而求其次，转向 iO 这一较弱但可能实现的目标。

此后二十年，iO 的构造经历了无数失败。直到近几年，才终于出现基于合理安全假设的 iO 候选方案。这些方案建立在一条始于 AJ15 / BV15 / LPST15 / LPST16 谱系的十年塔式构造之上：

• AJ15 和 BV15（两篇几乎同时发表的论文）发现了一种基于“函数加密”（functional encryption）构建混淆的方法。函数加密中，权威机构发布与函数 (F) 绑定的密钥，拥有加密密钥的人可以加密 (x)，而拥有解密密钥的人只能恢复 (F(x))。但所需的函数加密性质极强，当时并不存在。
• LPST15 提出了类似思路，同样需要当时不可得的强性质函数加密。
• LPST16 取得突破：发现可以基于一种称为“亚线性紧凑随机编码”（sublinear compact randomized encoding）的类似物构建混淆，进而将其建立在一种已知的“简洁但非紧凑”的函数加密方案之上，并引入一种名为 XiO（obfuscation）的新原语。

“银河级”运行时间与希望

尽管 iO 在理论上已被攻克，其实用性却受限于天文数字般的运行时间。这些方案的构造方式大致是：将一个“类全同态加密”的评估电路，嵌套进另一个“类全同态加密”中，对每个比特运行一次普通全同态加密，生成多兆字节的中间值，然后再将整个结构嵌入又一层的“类全同态加密”中。最终运行时间超过 (\lambda^{10})，其中 (\lambda) 通常取 100 或 120，这意味着实际运行完全不可行。

但文章给出了两个乐观视角：

1. 类比 SNARKs 的发展史：2010 年的 SNARKs 同样低效，但一旦可行性被证明，研究者便不断削减瓶颈，最终达到可实用水平。iO 可能重蹈覆辙，最终只需在重型 GPU 上运行一天即可。
2. 新密码学假设的进步：我们可能会看到更多工作致力于提出新的密码学假设，并发展出判断这些假设安全性的更好方法，从而可能绕过当前构造中的巨大开销。

混淆协议家族与权衡前沿

目前存在三个尚未消亡的混淆协议家族，它们分布在效率与安全假设“大胆程度”构成的权衡前沿上。本文聚焦于其中最为