林蕙佳：不可区分混淆 (iO)
播客： https://zeroknowledge.fm/podcast/375/
译校：Kurt Pan
Anna Rose：本周，我和 Tarun 采访了华盛顿大学保罗·G·艾伦计算机科学与工程学院的教授 Rachel Lin。我们讨论了不可区分混淆（简称 iO）。
iO 常被誉为密码学的圣杯，它是一种强大的原语，如果得到充分实现，将对整个隐私技术产生深远的影响。Rachel 为那些可能已经熟悉零知识证明 (ZK)、全同态加密 (FHE) 和可信执行环境 (TEE) 的听众解析了这一概念，阐明了 iO 与这些构造的区别，以及它们所基于的假设的一些相似之处。我们的对话涵盖了 iO 研究的历史，从 2013 年的早期工作，到 2021 年 Rachel 与 Jain 和 Sahai 合作撰写的论文中描述的关键突破。
这篇论文介绍了一种基于广泛研究过的假设的新型 iO 构造。我们讨论了本文的细微之处，以及自 2021 年以来 iO 领域的发展，以及基于格的 iO 构造的重新兴起。
现在切换回 iO，这是我们与 Rachel Lin 的节目。
今天，Tarun 和我与华盛顿大学保罗·艾伦计算机科学与工程学院的教授 Rachel Lin 一起来到这里。
欢迎来到节目，Rachel。
Rachel Lin：谢谢。很高兴认识你们，Anna 和 Tarun。
Anna Rose：嘿。很高兴认识你。感谢 Muthu 的介绍。
我觉得这已经是 Muthu 在过去几个月里第四次或第五次为嘉宾做精彩的引介了。所以，我想说声谢谢，Muthu，谢谢你把这些优秀的人带到我们这里。
Rachel Lin：我也要感谢 Muthu。
Anna Rose：嘿，Tarun。
Tarun Chitra：嘿，很高兴回来。
Anna Rose：是的。Tarun，我觉得当我们提出关于 iO 做一集节目，专门和Rachel对话的时候，你一定很兴奋。所以，我很高兴你能来参加节目。
就我个人而言，iO、不可区分性、混淆，也就是本期的主题，我们从未深入探讨过。我不知道自己是否完全了解它。所以在我们两个人中，我绝对是这个话题的新手。
但我确实觉得我们之前暗示过，或者在节目里顺便提过几次。我很好奇它是否和 ZK 以及我们目前在做的事情，比如 FHE，以及我们在节目里已经讨论过很多的事情有关联，或者，是的，我不知道，还是目前只是个空想，未来会有的。
所以我想我们先来简单介绍一下。什么是不可区分混淆？我们以后会称之为“iO”。那么，什么是“iO”呢？
Rachel Lin：这个问题问得非常好。恐怕我得先讲个故事才能解释清楚什么是 iO。
Anna Rose：好的，完美。
Rachel Lin：我想我们可以从某个时间点开始，也从这个概念的发展角度来探讨。我的意思是，首先要问的是，什么是混淆，对吧？不可区分混淆既包含不可区分的部分，也包含混淆的部分。
混淆部分的概念是，我能否有一个编译器，将明文程序（一个非常复杂的软件）转换成一个新版本？可以把它想象成一个非常混乱的版本。它混乱到即使你把它发布给公众，也没人能真正理解它在做什么。
但它仍然有效，你给它一个输入，它就会产生一个输出，并且输入输出行为与原始版本相同。这就是混淆或程序混淆的基本概念。
Anna Rose：这种混淆是通过什么方式实现的？因为我们听说过类似的东西，比如散列，或者添加随机性，你做了什么来创建这种混淆或类似混乱的输出？
Rachel Lin：这是一个非常宏大的问题。
Anna Rose：听起来简单，但回答起来可能很复杂。
Rachel Lin：我的意思是，这是一个非常自然的概念，对吧？事实上，在软件行业，软件一出现，人们就开始思考是否有办法对其进行加密，这样就能像你说的那样，扰乱软件的内部运作，让任何人都无法理解你的秘密来源。人们可以凭直觉知道如何解决这个问题。
然后他们可能想做的第一件事就是，我可以给变量起一些难以理解的名字。也许我可以插入一些类似空操作的操作，这些操作会自行抵消。也许我会做点别的，对吧？
最初，仅凭编程技巧就能玩出很多花招。人们也一直在研究和探索这些技巧。但问题是，所有这些直观的方法最终都会被去混淆。
它们最终很容易被逆向工程。
Anna Rose：太容易消除混淆了。
Rachel Lin：是的。所以密码学就派上用场了，因为在密码学中，我们想要构建真正坚不可摧的工具。我们知道，只要某些数学难题仍然难以解决，就没有人能够违反我们基于其难度所做出的保证。
因此，最大的挑战问题是，我们能否以坚实的基础、基于我们已经广泛研究过的密码难题以及我们知道它们能够抵御攻击的方式构建程序混淆？
Anna Rose：太棒了。在我们直接讨论“iO”之前，我想再问一个关于名称的问题。你说的“不可区分混淆”是不是有点重复，就像是重复说了两遍一样？
因为混淆，我想我们已经说得很清楚了，但这里指的是难以区分吗？它的意思非常具体吗？
Rachel Lin：这当然是以一种非常具体的方式表达的。事实上，不可区分混淆，这个概念本身就是一项伟大的贡献。混淆的概念实际上从公钥密码学的最一开始就存在了。
这个概念最早出现在 1976 年的一篇论文中，由 Diffie 和 Hellman 撰写，他们也在同一篇论文中提出了公钥密码学。有趣的是，当他们提出这个概念时，他们将其命名为“单向编译器”。正如我之前所说，你可以将其想象成混淆，将程序编译成难以理解的内容。所以他们称之为单向编译器，以表明这个过程是单向的，并且很难逆转。
有趣的是，当时我们根本不相信他们，就像社区里争论的那样，公钥加密真的存在吗？听起来很神奇，拥有公钥还能保证加密安全。所以 Diffie 和 Hellman 证明了这一点，他们认为这个概念应该是可行的，因为如果你有一个单向编译器，那么你需要做的就是采用一个私钥加密方案，比如说你最喜欢的方案，也就是我们今天使用的 AES。
现在选择一个随机密钥。接下来，我们将用这个随机密钥对 AES 加密算法进行混淆。混淆之后，这个混淆后的程序将作为公钥。
为什么？因为你给它输入任何你想加密的消息，并赋予它一定的随机性，它就会生成密文。而且由于这个随机密钥被锁在这个混淆程序里，所以没人能知道它是什么。
有趣的是，我们后来知道，公钥密码学可以直接从各种难题中构建出来。但混淆的挑战持续了40多年，直到最近我们才取得了一些进展。
Anna Rose：那么这种不可区分性就是新的突破吗？
Rachel Lin：这是一项突破，也是一项里程碑，因为第一个里程碑就是要知道哪些安全保障是我能实现的，哪些是我不能实现的。我刚才向你们描述的是一个非常简单的思维模型，可以用来思考混淆可能造成的影响，它有点像一个数学黑盒。
你把一个程序放进去，就可以随时调用这个黑盒，而且它不会泄露任何关于里面软件的信息。不幸的是，这是一种理想的混淆方法。事实证明，这种想法在一般意义上是不可能的。
这与2000年左右发现的复杂性理论中的“不可学习性”有关。那么问题来了，什么概念是可能的呢？我们真的要完全放弃混淆吗？
随后，研究人员提出了一种名为“不可区分混淆”的新概念。它声称混淆不会像数学黑盒那样运作，但其正式保证是，如果我一开始就使用同一功能的两个不同实现，那么你无法从混淆后的版本中分辨出哪个版本是最初的版本。
Anna Rose：我明白了。这就是不可区分。这两个看起来一模一样。
Rachel Lin：没错。
Anna Rose：有意思。是的。
Rachel Lin：因此，如果您从两个原始程序开始，它们是同一功能的不同实现，那么您最终会得到一些难以区分的东西。
Anna Rose：酷。
Rachel Lin：所以对于熟悉零知识语言的观众来说，我想说不可区分混淆有点像证据不可区分证明的类似物，而最初的理想混淆则是零知识证明的类似物。
Anna Rose：有意思，太酷了。
Tarun Chitra：我觉得有一点很有趣，那就是 iO 蕴含了很多东西，比如单向函数的困难性。它就像是从平均情况的 NP 问题归约到最坏情况的 NP 问题。
就好像如果你能实现它，你就能随之实现所有其他目标。所以它有点像万物理论中的圣杯，因为你可以从中衍生出很多东西。所以，或许我们不妨谈谈一些可以从 iO 衍生出来的原语，以及为什么它作为黑盒比其他一些东西更强大一些。关于你用电路表示来定义不可区分性的观点，我想，能够比较一下为什么需要在电路表示层面而不是图灵带或函数层面，你知道，我觉得电路方面很重要，就像 MPC 和 ZK 中的情况一样，而不是像其他状态机的表示形式那样。抱歉，这里有很多问题……
Rachel Lin：问题太多了，我们可以一个一个地处理。
Tarun Chitra：是的，抱歉，抱歉。
Rachel Lin：是的，我认为就 iO 的威力而言，这无疑解释了为什么这种混淆技术一般意义上如此引人入胜。首先，混淆技术本身就如此强大。要理解 iO 的威力，我们首先要了解理想混淆技术的力量。人们为什么需要它？我们为什么如此努力地追求它？它有什么用处？
我刚才举过例子，如何利用数学黑盒将一个私钥加密方案转化为公钥加密方案，对吧？其实就是用一个随机密钥来混淆私钥加密方案的加密算法。因为现在密钥被放进了这个数学黑盒里，所以私钥就被隐藏了，泄露这个黑盒是安全的。
本质上它几乎为您提供了可信硬件的软件版本。
Anna Rose：哦，是的，是的。
Rachel Lin：对。所以，任何你希望使用可信硬件解决的问题，比如你有一些想要保护的秘密，但又想通过一个受限的接口使用这些秘密，或者你有一个程序，你想确保其内部逻辑保持隐藏。直观的解决方案是将其放入可信硬件之中。
现在，密码学的核心是用数学来取代管理或硬件。所以现在我们可以用理想的混淆技术来包装它，这样就安全了。你可以想象一下，我只给出输入输出行为。
所以它非常容易使用。就像我想说的，在密码工程师或密码研究人员遇到可行性问题时，比如，我能实现这个密码学目标吗？他们可以先考虑，我能用安全硬件来实现它吗？
如果他们能用安全硬件实现这一点，那么用理想的混淆技术也很可能实现。并非总是如此，但已经接近了。是的。
现在我们要问的是，不可区分混淆的威力到底有多大？它并不理想，对吧？理想状态根本不存在。
因此，事实证明，得益于大量研究成果，一种名为“穿刺编程(punctured programme)”的技术（最早由 Amit Sahai 和 Brent Waters 在一篇论文中提出）在许多理想的混淆应用中，我们实际上可以用 iO 来替代这种理想混淆。这需要我们了解一些密码技术。回答这个问题还有另一个层面，那就是如果我们习惯于使用启发式方法，那么事实证明，这种数学黑箱模拟，即使一般上不可能实现，仍然是可能的。
这种可能性并没有完全排除。所以有一种稍微弱一点的变体，叫做虚拟黑盒，它接近这种理想的混淆效果。至于它的可实现性，也已被证明普遍上不可能。
但这种不可能性是用某些复杂且病态的例子来证明的，表明这种概念是不可能的。所以你可能会想，哦，那么，对于一个并非设计为对抗数学黑箱概念的自然程序来说，这种黑箱安全保障仍然可能实现吗？所以，从启发式层面来看，我们现在有一些证据表明这可能是真的。
我们有证据表明，这种自然程序的启发式方法，我们可以用数学黑箱的方式进行混淆，它与我们在密码学中钟爱的随机预言启发式方法相通。事实上，如果你考虑一下随机预言启发式方法，它说的是，你知道，给我一个现实世界哈希函数的代码，比如 SHA。即使攻击者能够查看代码，获得这段代码，他的能力也不过是把这个哈希函数的输入输出当作一个随机函数而已。
所以，仔细想想，哈希函数的代码实际上是伪随机函数的数学黑盒，因为即使能够访问代码，甚至看到代码，你也只能查询输入输出，而输入输出的行为就像随机的一样。所以从启发式的角度看，这个概念是可行的。从这个启发式的角度看，我们实际上可以证明，对于自然程序来说，数学黑盒安全性仍然是可能的。
Tarun Chitra：一个简单的问题。您说的“自然程序”是指相对化意义上的程序吗？那种类型的程序，我猜您指的是什么？
Rachel Lin：哇哦。很高兴你提到了这一点，因为有很多术语重叠。不，我所说的“自然程序”实际上是指类似于随机预言启发式算法。我们知道随机预言启发式算法在数学上并不成立，在实际应用中也存在反例，在访问黑盒随机预言时它是安全的，但无论你使用哪个哈希函数来实例化这个随机预言，它都不安全。
然而，这些例子通常是病态的，通常是数学构造的，以便我们能够区分预言访问和代码访问。因此，随机预言启发式算法是关于随机预言启发式算法的自然应用的，自然的含义不是对抗性地构建来构造分隔，这种使用真实世界哈希函数的随机函数或随机预言的实例将是安全的。所以，从同样的意义上讲，“自然”是指它不是为了防止数学黑箱混淆存在而创建的程序。
Tarun Chitra：或许可以稍微拉远一点，你知道，如果我比较 iO、FHE 和功能加密，我会忽略你的一个构造是用 FHE 来构造 iO 的，但这就像细节中的魔鬼。我想或许可以描述一下它们的不同之处，比如，我可以混淆输入，我可以混淆输出，我可以混淆电路或函数，我可以混淆计算程序，以及这些在 iO 和 FHE 中有何不同。
Rachel Lin：哦，所以从某种意义上说，FHE 是加密的高级版本。它的意思是，如果你给我输入的加密结果，而不需要解密，我就能导出输出的加密结果。所以我们对密文进行计算。
但它在某种意义上遵循了密码学中传统的“全有或全无”的安全保证。我说的“全有或全无”是什么意思呢？安全保证是指，要么你知道密钥，你知道所有信息，你知道所有输入，你知道所有中间计算结果，你知道所有输出。
或者说“什么也没有”意味着如果你没有密钥，你就什么也得不到。密码学的一大进步，甚至从80年代开始，以及之后我们构建的许多不同项目，都是为了超越这种“全有或全无”的保证。我们真正想要的是实现非常精确、可控的信息发布。
我掌握了一些敏感信息，敏感数据 X。我想了解一些基于它进行求值的函数。而且，我实际上希望以明文形式了解它。
我想了解 F(X) 。而这是唯一能揭示的信息。所以，事实证明，如果你想不透露任何信息，其实更容易实现。
如果你想透露确切的信息，那就比较难了。
Anna Rose：在 FHE 中，您说。
Rachel Lin：是的，在 FHE 里没有。我们在 FHE 里没有办法做到这一点。
Anna Rose：那么在 iO 中，有机会做到这一点吗？
Rachel Lin：仔细想想，iO 就是这样一种原语，因为我有一个秘密的程序。我允许公开的是，对于任何输入，你都能知道该输入的输出是什么。
所以它揭示了我们的真值表。我所说的真值表指的是整个函数表。我可以轻松地对其进行编程，以实现我刚才所说的功能。
你提到了功能加密的概念，对吧？功能加密是一种加密……听起来有点像 FHE，但它可以精确地泄露信息。
所以你可以像在 FHE 中一样加密数据。如果你有一个密钥，这个密钥可以用于创建与特定函数绑定的密钥。这被称为函数 $F$ 的密钥。
如果你有这样一个密钥，当你解密输入 X 的密文时，你得到的并不是 X 本身。你得到的只是 F(X) 。你只能得到输出。
因此输出被揭示，而有关 X 的其他信息均未被揭示。
Anna Rose：但在 FHE 中，什么也没有，在两端都是加密的，对吧？所以你得不到任何信息，只能得到全部或什么都没有。
Rachel Lin：是的，要么全有，要么全无。功能加密是为了精确地披露信息。
Anna Rose：我也一样，当你谈到黑盒之类的东西时，我也想到了 FHE，因为我一直听说你有一个可信执行环境（TEE），如果你想要它的软件版本或密码学版本的话，你可以用 FHE。但你说的是，这就像 iO 提供的，首先，你可以获得一些启发。你可以揭示某些东西。
TEE 通常也具有该功能吗？
Rachel Lin：是的，我认为 iO 是 TEE 的直接类似物。人们常说，一旦有了 FHE，就可以移除 TEE。他们指的是，它只适用于知道密钥的单个用户。
对于知道 FHE 密钥的单个用户，现在他们可以将其输入的任何计算委托给可信环境。现在，它不需要可信环境，因为所有内容都已加密，然后他们将获得加密的输出。如果他们知道密钥，他们就能解密并获取输出。
但关键是，如果我想公开信息，这就行不通了。除非我把我的密钥公开，否则每个人都会知道所有信息，所有信息。
Anna Rose：是的。
Rachel Lin：在功能加密中，我可以透露函数 $F$ 的密钥，这样每个人都可以知道 F(X)。
Anna Rose：但不是那些你不想让他们学到的东西。
Rachel Lin：没错。不是那些你不想让他们知道的关于 X 的事情。
Tarun Chitra：我认为值得补充的是，功能加密和 iO 非常密切相关，就像一个蕴含着另一个一样。所以，或许可以谈谈这一点，因为我认为功能加密在某些方面实际上更容易理解，感觉更容易。但它们等价的事实，在某种程度上，是一种在某些额外假设下的等价概念。
就像回顾一下人们在这个领域的探索历史一样，因为感觉从2010年代到2020年代，很多关于iO和功能加密的概念都发展了很多，对吧？人们发现了这些特殊情况，然后他们证明了它们。当然，到了2021年，你把所有这些整合在一起，找到了如何运用一系列被充分理解的假设来构建整个体系的方法。
但感觉就像看着别人用乐高积木搭建东西一样，对吧？他们就像是一块砖一块砖地搭建起来，然后有人得想办法把它们拼起来。所以这些东西的历史也挺有意思的，比如人们是如何发现它们的。
Rachel Lin：是的，功能加密与 iO 非常相关。首先，我们来看看，用 iO 我可以轻松构建一个功能加密。这也很巧妙。首先，我想加密私有信息。
让我们以一个普通的公钥加密为例，这样我就可以加密我的输入 X。现在这个公钥加密有一个密钥。这个密钥是一个“全有或全无”的密钥。
一旦你泄露了它，一切都会暴露。所以，对于一个功能加密，我想创建部分解密密钥，对吗？这个解密密钥与一个特定的函数 F 相关，就像一个解密令牌。
我允许你计算 F。所以我可以做的是，现在我可以创建一个数学黑盒，里面又会硬编码这个密钥。创建它时，我也会硬编码函数 F 的逻辑，因为我试图为函数 F 创建一个部分解密密钥。
那么这个黑盒会做什么呢？如果你输入一个密文，即 X 的加密，它会在内部对其进行解密并显示 X，但它不会输出 X。它会在 X 求值 F，并且只输出 F(X)。对吗？
所以一旦我有了这个盒子，我就可以让它输出部分信息，也就是 F(X)，而不输出其他信息。如果这是一种理想混淆，那么它就非常安全。因此，你得到了 F(X)。
事实证明，有了 iO，利用我之前提到的这种穿刺编程技术以及其他一些技术，我们也能使这个范式发挥作用。这就是 iO 是如何蕴含功能加密的。
希望您也能看到，这个数学版本的可信环境非常非常强大，因为它使得一个非常困难、具有挑战性的问题变得非常容易解决。
Anna Rose：有意思。我只是想问个问题，因为我们没有了解你的背景以及你的研究方向。不过，Tarun，你刚才提到了这篇2021年的论文。
你是在那篇论文里把这些内容整合起来的吗？能简单描述一下你论文里讲了什么吗？
Rachel Lin：这篇 2021 年的论文是与 Amit Sahai 和 Aayush Jain 合作完成的。我们三人首次基于一些众所周知、经过长期研究且已知能够抵御攻击的密码学困难假设，提出了 iO 的构造。这可以说是许多人、整个社区为实现 iO 而付出的漫长努力的结晶。这篇 2021 年的论文与之前研究的不同之处在于，之前我们需要依赖一些神奇的、未经审查的假设，这些假设被发明出来，以便我们能够对 iO 进行启发式和候选式的构造。
Anna Rose：我明白了……
那么在这篇论文中，你对它进行了强化吗？你使用了一些已证实的部分来证明这实际上是可能的。
Rachel Lin：是的。在这篇论文中，我们成功地证明了它可以建立在更坚实的基础之上，基于社区一直在研究的假设，并且这些假设与数学的其他方面以及计算理论有着深厚的联系。所以，我认为这第一次让我们确信，iO 的概念并非只是一种奇幻的想象，而是真正值得信赖的东西。
Anna Rose：酷。
因为我们现在还没讲你的背景故事，所以我有点好奇，你当时是在为此努力吗？你之前研究这个 iO 问题很久了吗？还是你来自密码学的另一个领域？
Rachel Lin：哦，是的，完全正确。我是说，我大约在 2015 年就开始研究 iO 问题了。那时，就我个人而言，直到 2021 年发表那篇论文，我经历了一段漫长的五六年。
我还没有对一个话题如此兴奋过。
Anna Rose：除此之外。
Rachel Lin：那个时间段。是的。
Anna Rose：哦，哇哦。
Rachel Lin：当我在 2015 年进入这个领域时，iO 正处于一个非常有趣的发展节点。这个概念可以追溯到 20 世纪 70 年代。实际上，当我们开始设想公钥密码学时，人们就已经在想象它了。
但在很长一段时间里，没有人真正理解它。直到 2013 年，我才取得了突破，这是第一项尝试基于多线性映射的数学对象构建 iO 的工作，只不过我们当时没有，它有点像配对群的泛化，实际上有点像给配对群注射了类固醇。想象一下，它不仅可以进行一次配对，还可以进行很多次配对。
这就是我们所说的多线性映射。如果我们有了这个目标，我们就可以构建 iO。这项工作确实在社区引起了轩然大波，只是我们并没有找到多线性映射的良好候选方案，因为想象配对，过去几十年来人们并不能推广配对。我们不知道如何推广配对。
因此，他们针对这些多线性映射给出了一个基于格的启发式候选方案。结果发现，该方案随后遭到了攻击。
Anna Rose：好吧。我想，成了一个错误的候选方案？
Rachel Lin：可以说，这是一个不完美的候选方案。是的，它留下了很多空白，但我认为这项工作至今仍具有很大的影响力。它对于重启对 iO 的研究热潮至关重要。大约在同一时间，我认为 Amit Sahai 和 Brent Waters 在 2014 年发表的论文也是一个里程碑，他们在论文中引入了穿孔编程技术，因为它真正开启了使用 iO 的应用。因为当我们思考如何使用程序混淆时，我们的本能是使用理想混淆，即数学黑箱。他们表明，当我们使用 iO 时，这种思维方式并没有错，只是我们需要一些技巧。他们引入了这些技巧，从而真正打开了基于 iO 的应用之门。由于这两件事，我们开始再次研究 iO，但随之而来的巨大挑战和最大的问题是，我们能否真正将其建立在坚实的基础之上，还是我们只是基于一些从一开始就有缺陷的假设来证明一切皆有可能？
Anna Rose：是的……
那么，从2015年你加入这个问题领域到2021年，你是否立刻就知道自己想要专注于这个问题？你是否在寻找方法来证明这个问题的有效性，是否真的可以基于具体的、已证实的东西？还是后来逐渐演变成这样？
Rachel Lin：我觉得我被带走了。我被 iO 带走了。
那感觉就像一种痴迷，同时也是一见钟情。
2015 年，当我看到 iO 的所有这些应用时，我深信它真的像圣杯一样，或者你称之为，或者我称之为密码学的终极工具，这令人信服。有充分的证据证明它是如此强大的工具。而且，我认为它的长期目标愿景也非常令人信服，因为我们现在有这些类似于数学黑箱启发式算法的东西。即使有一天这个东西真的实用了，我也坚信工程师们能够轻松地使用它来创建自己的密码工具，而不必依赖研究社区，毕竟研究社区的进展很慢。所以当我看到它时，我被深深地吸引了。
在2015年那个时候，那些最初的启发式候选方案遭到了猛烈的攻击。我当时的感觉是，我们需要多样化我们的方法。我们不应该只关注那些启发式候选点，也就是直接的构造，而应该采取一些不同的策略。
因此，当我在 2016 年提交第一篇论文时，我采取的策略是基于当时两组研究人员的一项非常重要的工作，他们证明了功能加密实际上蕴含 iO。这是我最初的灵感，那就是，我们能否真正使用可证明安全性，你知道，安全归约，这些现代技术首先尝试理解 iO 这个对象，通过归约到越来越弱的对象，这也许会告诉我们，首先，iO 到底是什么。其次，我们需要完成的核心任务是什么？
所以这更像是一种复杂性理论的方法。我认为，如果我们能把范围缩小到核心，事情就会变得更容易，无论我们是想从启发式方法中实例化，还是幸运地基于可靠的假设。这就是我的观点。
然后在 2016 年，我的第一篇关于 iO 构造的论文中，我证明了它们可以基于常数次数多线性映射，这仍然是配对的推广，只不过它不需要那么多的配对，只需要常数个配对。
Tarun Chitra：抱歉，那是像AC0还是NC0电路？
Rachel Lin：NC0 电路。没错。没错，就是 NC0 电路。
所以从那时起，我就痴迷于这个对象，并不断尝试将其归约到越来越弱的东西。另一方面，我不断尝试实例化这些最小的硬核对象。这实际上是一种从两端进行的斗争，既从复杂性理论的角度，也从代数和假设的角度。
并最终幸运地在2021年中途相遇。
Tarun Chitra：所以实际上，我认为或许有必要讨论一下不可区分性的正式定义，比如对于任何一对电路，任何 PPT，在概率多项式时间内敌手都无法区分，这有点像核心内容。我想，我们先来谈谈定义，比如我们想要的东西，比如可靠性、完备性等等。然后，我们再讨论一下你第一篇论文中的假设，以及这些假设是如何变化的。
因为我确实认为理解这些假设才是关键，因为显然人们花了很长时间去探索各种假设。对。所以，理解哪些假设有效以及为什么我认为有效就很好了。
但也许让我们先从不可区分性的定义开始，以及如何将其与人们习惯的零知识保证…简洁性保证进行比较。
Rachel Lin：好的，我们来试试。正式来说，不可区分混淆实际上有一个非常简单的定义。该定义表示，对于任何两个电路，假设 C0 和 C1，它们具有相同的输入输出行为。
所以，对于每个输入 X，它们都会计算出相同的输出。此外，它们的大小也相同。也就是说，它们的门个数也相同。
那么，iO 保证的是，如果我将 C0 输入 iO 的编译器，它会生成 C0’；如果我将 C1 输入 iO 的编译器，它会生成 C1’，那么任何 PPT 攻击者或概率多项式时间攻击者，即使知道 C0 和 C1，也无法区分 C0’ 和 C1’。换句话说，对于任何 PPT 攻击者来说，即使他们知道明文形式的 C0 和 C1，C0’ 和 C1’ 在计算上也是无法区分的。
Anna Rose：这可以定义为一种可靠性吗？有没有专门的术语来描述这种保证？
Rachel Lin：我认为你可以把它看作一个关于可靠性的术语。在这个定义中，它实际上非常引人注目，也与我们之前关于密码学从“全有或全无”走向“部分信息披露”的讨论相呼应。那么，这需要什么呢？
为了确保隐藏来自 C0 或 C1 的混淆程序，需要具备哪些属性？所以它包含两个要素。显然，它有一定的隐私性，对吧？
因为它至少需要隐藏哪个电路，如果它把电路暴露出来，那显然就没有隐私了。你很容易就能分辨出来。
Anna Rose：是的。
Rachel Lin：但我还要说一下完整性。完整性的意思是，给定一个经过混淆的程序，我能够对任意输入进行求值，并且它应该产生输出。
现在，攻击者能做的，就是它真的掌握了这个程序。它实际上可以看到，你知道，这个程序也会把自己变成一个电路，对吧？否则，你怎么执行它呢？
因此，攻击者只要掌握了这个程序，就能观察到程序计算的所有中间值。希望这些中间值都被打乱，不会泄露内部电路的信息。而且，它实际上可能会翻转，对吧？
在电路执行过程中，它甚至可以篡改执行结果。它会说，哦，我看到这条线现在的值为1。让我把它翻转为0。然后看看它们接下来会执行什么。
所以它可以做很多事，因为这是对代码的直接访问，攻击者可以做很多事。那么完整性是什么意思呢？
完整性意味着，无论攻击者做什么，这个程序都需要确保，给定 X，要么生成垃圾（如果篡改过多），要么生成正确的 Y。它不应该生成 Y’，也就是在某个相关电路上对 X 求值，对吧？这就是我所说的完整性。
有一种嵌入的可靠性。你需要确保它内部确实执行着正确的程序。
Tarun Chitra：所以实际上，我想这有点相关，也许在我们讨论假设之前，但既然我们继续与 ZK 建立联系，我不妨提一下。比如，我有一个函数，我把它表示成一个多线性多项式，比如它的布尔展开。然后我对它进行算术运算，就像你在 ZK 中做的那样，在 iO 中也这样做，在这两种情况下，你都会构造出这些多项式。
但是 iO 的区别在于，然后，我想我得认真读你的论文好几遍才能理解这一点。基本上，对于给定的布尔函数，存在一组电路，理论上，它们具有相同的真值表。理论上，如果我有一个可以采样这些电路的 PRG，并且我可以针对给定函数随机采样一个电路，我应该能够做到这一点。这似乎是一个获取 iO 的简单而明显的方法，对吧？但是，这种明显的方法只有在你深入细节时才有效。
那么，我们为什么不应该期待这样的事情呢？如果我能够枚举出代表一个真值表的所有电路，为什么随机选择一个就不行呢？或者说，为什么这很难？
因为这种想法一开始总是有点幼稚，对吧？就像，哦，想象一下，我可以写出一组电路。但由于一些复杂性的原因，你无法做到这一点。
Rachel Lin：是的，我的意思是，这是一个很棒的问题。事实上，这就是为什么 iO 如此令人着迷，因为你知道，在大多数密码学中，如果 P 等于 NP，那么密码学就不存在。比如，如果 P 等于 NP，我们就没有单向函数，也没有公钥加密，什么都没有，对吧？
所以我们最好生活在一个 P 不等于 NP 的世界。但实际上，如果 P 等于 NP，那么 iO 就存在。
正是因为你提到的原因。因为现在我该怎么办？我的编译器给了我一个程序。
它要做的就是，要么像你说的，尝试找到一个随机电路，一个实现相同程序的随机电路，要么找到一个按字典顺序第一个实现该程序的电路。因为 P 等于 NP，所以这个过程会很高效。这实际上是统计 iO，是统计上的，它会给我完美不可区分性，而不仅仅是计算不可区分性。
唯一的问题是，这种方法在 P 不等于 NP 的世界中效率不高，对吧？给定两个电路，很难判断它们是否实现相同的函数，更不用说给我一个电路，我想找到所有可能的电路，或者第一个实现相同函数的电路。
Tarun Chitra：顺便说一句，我之所以提起这件事，是因为我觉得在 ZK 中，人们总是会想，我做了一个电路。我不在乎所有能给我相同输入和输出的电路，对吧？我只想问，我的编译器给了我哪一个？
或者说，我构造了哪个多线性多项式，对吧？而在 iO 中，你实际上关心的是组合函数，比如，有多少个这样的电路？我怎么才能随机地给你一个，而你又无法推断出我选择了哪一个？
对我来说，这似乎一直就是差距所在，也就是为什么它更强大。就好像，你必须以某种方式处理所有可能做同样事情的电路集合，而不是处理单个做某事的电路。你同意这就是差距的来源吗？
Rachel Lin：确实如此。这正是差距所在。这在某种程度上体现在理想混淆和不可区分混淆之间的差异上。
理想混淆就像零知识一样。你不必关心同一个电路有多少种不同的实现，你只需对其进行混淆，它就是一个黑盒，对吧？至于不可区分混淆，当你想使用它的安全保证时，在一个诚实的环境中，我总是可以直接进行混淆。
它自带编译器，我随时可以把我的电路输入进去。它会自动生成结果。到那时，我就不用再关心有多少种不同的实现方式了。
但如果我想推断这个混淆程序给了我什么保证，我就必须开始思考，哦，还有另一种实现。然后，基于现有的其他实现，我才能推断它的安全性。这就是为什么 iO 并不显然的原因。
iO 强大的原因并不明显。这要归功于我们目前所做的大量工作，它们为我们提供了绕过这一难题的额外技巧。
Anna Rose：我本来想继续你 2016 年论文里讲的内容，比如那个年代的功能加密，功能加密可以实现 iO。你刚才提到了这些技巧。或许你可以再分享一下这些技巧是什么。
听起来这就是你在 2021 年之前所积累的东西。
Rachel Lin：对。所以我想我可以告诉你一个非常强大的技巧，那就是功能加密蕴含iO。还有一个概念叫做指数效率（exponential efficiency） iO，它与功能加密非常相关。
它在某种程度上捕捉到了功能加密的作用。为什么它与 iO 语言中的 iO 相关？那么它到底是什么呢？
比如，如果你考虑一下 IO，它的核心是能够将一个非常大的真值表或输入输出行为压缩到这个规范电路中。无论你从哪个真值表的实现开始，你最终都会得到这种规范的表示，只不过它不是单一的表示。它是一种计算上不可区分的表示。
所以它就像一个伪规范表示。它从指数级的真值表压缩到了多项式级的伪规范表示，就像一个巨大的压缩。那么指数效率 iO 的概念是什么呢？
意思是，好吧，也许我只需要一点点压缩。如果我只有一个非常小的真值表呢？不是那么小，但也不是指数级的。
指数级很难处理，但我有一个多项式大小的真值表。如果我有多项式大小的真值表，从技术上讲，我可以计算出这个真值表，然后直接发布。这本身就是一种完美不可区分混淆。
因为任何两个计算这个多项式大小真值表的电路最终都会得到相同的表。所以显然，你丢失了关于你来自哪个电路的任何信息。现在，我们指数效率 iO，或者我们称之为 XiO，指的是我只想稍微压缩一下这个多项式大小的真值表。
你知道，如果它的初始大小是 M，我希望混淆电路的大小是 M 的 0.99 倍。所以任何亚线性压缩都足够了。这就是 XiO 的意义所在。
事实证明，XiO 蕴含着完整的 iO。只要我能以亚线性的方式压缩真值表，就能将指数大的真值表压缩回多项式大小。XiO 本质上是一种功能加密。
它比功能加密更弱，却接近功能加密。原因在于，正如我之前提到的，功能加密允许你揭示 X 的 F，但每次揭示，某种意义上都需要一个令牌。换句话说，这就好比，一旦我混淆了输入 X，我就能揭示多项式数量的输出，不同的 F 对应不同的 X 的 F，只要我能给出多项式数量的令牌。
但他们无法揭示指数级的输出，因为那样的话，我必须揭示指数级的令牌。这不可行。因此，X 的密文可以展开为任意多项式数量的输出。
这就是功能加密和 XiO 之间的联系。现在，关键在于功能加密到 iO 的转换。用 XiO 到 iO 转换的语言来说，它们之间有一种联系，也就是在密码学中，你们有些人可能知道伪随机生成器到伪随机函数的转换。
伪随机生成器是指我能从一个短种子生成一个多项式长度的伪随机字符串；而伪随机函数是指我能从一个短种子开始，生成一个指数级长度的伪随机输出。与伪随机生成器到伪随机函数的转换类似，几乎相同的范式，我可以从 XiO 到 iO。其关键思想是使用递归，也就是说，只要我能压缩一个亚线性量，一个很小的量，我就一直压缩，一直压缩，直到最终得到一个很小的量。
Anna Rose：你当时是借用了这个想法吗？比如你看到伪随机生成器变成伪随机函数，然后意识到可以借用这种技术？
Rachel Lin：我认为这是一种事后看来的观点。
Anna Rose：好的。
Rachel Lin：所以，当两组研究人员的前两篇论文展示了功能加密到 iO 的变换时，我们后来提出了 XiO 的概念，并展示了类似的变换。事后看来，我们发现了它们的相似之处。
Anna Rose：看起来很相似。
Rachel Lin：是的。
Anna Rose：所以你在平行的轨道上发现了一种类似的技术。
Rachel Lin：我想是的。是的。我想人们都有这种感觉，你知道，作为研究人员，我们会被各种不同的想法所滋养，有时你不知道这些灵感从何而来。
所以我认为这是 iO 发展中非常重要的一步，我们能够将其精简到只需查看多项式大小的真值表，这使得它更容易管理。另一个非常重要的一步是，我们意识到，如果我们有一个假设，即伪随机生成器可以在 NC0 电路中计算，这意味着每个伪随机输出仅取决于输入 C 中常数个元素。如果我有这种简单的伪随机生成器，那么我不仅需要关心这个多项式大小的真值表，我只需要关心这个使用 NC0 电路计算的真值表。
所以，我不仅不需要关心输出的指数数量，而且只需要关心非常非常简单的电路。这是另一个重要的步骤。
Tarun Chitra：实际上，就这一点而言，我认为那篇具有重大突破的论文有四个主要假设。PRG 和 NC0 可以算作一个假设。我知道，我猜我知道那篇论文有点像某种混合假设。
就像我们知道 NC0 中存在 PRG 一样，但它们与 NC1 相比非常烦人，就像对数深度的 PRG 一样。但是……
Rachel Lin：是的，我明白……
Tarun Chitra：……因为最后我们会讨论，实际中的 iO 是什么样子的？我知道这类东西，以及所有黑盒归约、XiO 之类的东西，都会增加很多复杂性。
但是，所以，NC0 中的 PRG，当我扩展它时，你可以生成具有常数元的伪随机数生成器。带错误学习（LWE）。所以，你知道，这在 FHE 中很常见。
带噪声奇偶学习（LPN）。所以它在某种程度上有点像稀疏域版本的 LWE，只不过你有一些额外的条件，然后像双线性 DLIN 之类的东西。所以，我们来讨论一下这些假设。
为什么它们是必要的？它们各自对你的构造有什么作用？我知道你后来写了一些论文，删除了其中一些，但只是为了……
Anna Rose：我们将结束 2021 年。
Rachel Lin：我认为最终我们会证明 LWE 并非必需，但我认为真正需要的两个假设是：一是带噪声奇偶学习假设。正如您所说，对于熟悉 LWE 的人来说，它几乎类似于 LWE，只是它不是使用小噪声来扰动线性系统。它使用稀疏但较大的噪声来扰动线性系统。它更接近于编码理论，因为在编码理论中，我们通常认为一个码字会因稀疏损坏而损坏，但每当发生损坏时，码字所在的位置就会完全消失。
这就是假设。另一个假设是双线性配对，它属于 DLIN 类型的假设。所以真正需要的双线性配对实际上源自 iO 的起源，其中第一个启发式构造是，如果我有强化版的双线性配对，也就是说，我不只有一个配对，而是有足够多的配对，可以继续下去。
每一对都对应着对秘密值进行一次乘法运算。对吧？我们知道，群通常允许对秘密值进行加法运算。
这只是一个一般性的，就像离散对数困难群一样。配对会给你多一次计算，也就是一次乘法。但问题是，一旦你完成了一次乘法，你就最终会进入一个目标群，你就不能再继续乘法了。
Tarun Chitra：嗯，我想其实有个小问题，因为在 FHE 中，你会进行一些重加密的操作，比如乘法、加噪声、降噪。但你构建这些操作的方式似乎不需要这样做，还是我理解错了？
Rachel Lin：是的。所以最大的区别在于，在 FHE 中，一切都是隐藏的。比如，你可以在 FHE 中做更多的乘法运算，但你就像永远不会透露任何信息一样。
但配对的有趣之处在于，即使你只考虑群，而不是配对，一个椭圆曲线群，它既具有隐私性，也允许一些信息泄露。也就是说，如果我有一个随机值，把它放在指数 g 的 r 次方中，我们现在知道它是隐藏的，我们可以利用这种隐私性来构建加密。同时，这种数学结构也允许我测试 g 的 x 次方是否是 x 为零的情况，因为我可以用恒等式比较 g 的 x 次方。所以，这是一个微小的漏洞，可以泄露一些信息。
FHE 没有这个。而在这个信息泄露的小孔上构建是一门艺术。通过配对，我们可以构建所谓的二次函数功能加密，因为它允许一次乘法。
因此，拟可以对秘密输入 x 求值二次函数，并了解输出是否为零。
Tarun Chitra：所以实际上，这引出了一个很好的观点，我认为这是这篇论文中的一个关键构造。也许这不是第一次这样做，但肯定是我第一次看到这种对公开值进行任意高阶分解，而对秘密值进行二阶分解的情况，就像你能够以某种方式将秘密值与公开数据进行分解，从而实现这种操作。你是怎么想出这个构造的？因为我觉得这篇论文中有两点似乎非常、非常不明显。
嗯，首先，你可以把这个东西分成低次和高次，然后是极低次，比如2。其次，你可以做类似Johnson–Lindenstrauss压缩感知的事情，制作这些矩阵，然后进行扩展和压缩。对。
我只是有点好奇，灵感是什么？因为我觉得这个工作的创作过程中涉及了太多不同的东西，所以把所有这些东西整合在一起肯定花了很长时间。
Rachel Lin：这确实花了很长时间，确实花了很长时间。
Tarun Chitra：嗯，只是因为它们看起来很不一样。我觉得你从密码学的许多不同领域汲取了很多东西。
Rachel Lin： 我的意思是，研究的魅力就在于，有时候我甚至不知道下一篇论文会朝什么方向发展。我认为你所描述的，是我们说我们可以对二次函数进行功能加密。这实际上展示了一项更早的研究。
事实上，我之前说过，如果有 k 个可用的配对，那么就可以为 k 次多项式构建功能加密。如果 k 等于 2，那么只能是二次函数。这是早期的工作，更像是对基于多线性映射构建 iO 的初始尝试的直接跟进。但我们对其进行了形式化，然后证明了这个原语是可行的。后来，我们最初尝试将所需的次数从我第一项工作中的常数 k 降低到 5 次，然后降低到 3 次。然后我们甚至提出了新的伪随机生成器假设，结果证明是正确的。
在某些时候，我们有一些候选的伪随机生成器，它们的次数恰好是2。之所以是2次，是因为我们想在配对内部求值这些伪随机生成器。当我们意识到如果我们可以在配对内部求值伪随机生成器时，那就太好了。
只是我们没有找到合适的候选方案。直到今天，我们仍然没有找到合适的候选方案。所以我们只能尝试寻找其他方法。
如果我的伪随机生成器不是2次的，而是常数阶的，该怎么办？而且我只有一个只计算2次秘密求值和秘密计算的配对。所以一个想法是寻求全同态加密的帮助。
你知道，如果我有同态加密，也许我可以在全同态加密中求值伪随机生成器。或者它不需要是全同态的。如果我有一个足够简单的伪随机生成器，我只需要一个常数次的同态加密，对吗？
然后，也许2次不会直接用于计算伪随机生成器本身，而只是用于解密。因为同态加密的缺点是它虽然计算能力强大，但却不会泄露任何信息。所以我必须以某种方式解密它。
我只能在配对内部解密，因为这样我可以控制哪些信息会被泄露。但是可靠性很重要，因为同态加密没有任何可靠性。一旦我得到了输入的加密，你就可以计算任何你想要的函数，对吧？
这里我只想求值伪随机生成器对我的种子加密的效果。这就是为什么我提出增强配对群构造的想法，不仅要实现秘密二次函数，还要包含一个计算的公开部分，这个部分虽然次数更高，但好处是公开部分不需要隐藏，因为它受到了功能加密的保护。这就是部分隐藏功能加密的由来。
因此，这至少是一个框架，我们可以将同态加密与这种部分隐藏功能加密结合起来，以求值更高次数的伪随机生成器。
Anna Rose： 我稍微回顾一下。你们用了一个我不太懂的缩写词，那就是 DLIN。你们确实定义了 LWE 是“带错误学习”。
LPN 是…
Tarun Chitra：带噪声奇偶学习。
Anna Rose： 没错。所以你定义了这些，但 DLIN 你没有。所以我有点，我对这个缩写有点困惑。
您能分享一下这代表什么吗？
Rachel Lin：判定性线性。
Anna Rose：好的。
Rachel Lin：这是配对群上标准假设。
是的。我认为具体的假设并不那么重要，因为我们也可以使用不同的配对群假设来构建这种部分隐藏功能加密。
判定性线性就是其中之一。另一个叫做 SXDH。我自己也想不起这个假设的全名了。
Tarun Chitra： 对称的什么 Diffie-Hellman 算法。是的。我不知道它到底是什么。
但是Anna，这在很多 ZK 和 BLS 类的东西中都有使用。
Anna Rose： 我怎么从来没看到过？我也不知道。
Tarun Chitra：这就像您在正式保证中做出的假设一样。
Anna Rose：是的。
Tarun Chitra： 所以这实际上更像是标准的。其他的更像 FHE。比如 LWE 就是 FHE。
LPN 就像我们讨论水印和纠错码时所做的假设一样。我的意思就是这样。它的证明依赖于许多不同的子领域，这些子领域必须结合在一起，我认为这对我来说确实很有趣。
我们已经讨论了很多关于构造、候选构造以及所使用的许多细节，对吧？比如有很多组合学定理，比如从 XiO 到完整 iO，对吧，其中你必须递归，这可能会常数级膨胀，使实际计算变得昂贵。或者，你知道，很多假设，比如 PRG 和 NC0，电路非常宽，计算成本很高，对吧？我只是想说，如果我们想要开发 iO，似乎还有很长的路要走，但我只是好奇，你认为世界是如何实现这一目标的，以及人们是如何找到可能更直接的新构造的，有点像 FHE 从环 LWE 开始，然后转向整数，然后所有实际的构造都是整数，或者说，它必须是一个全新的东西？因为我从我们这边知道，我们肯定听说过以太坊基金会试图资助人们建立实现方案。
我的意思是，他们使用的假设有些非典型，所以我不确定效果如何。但我只是好奇，你认为这件事会在世界上传播开来吗？
Rachel Lin： 这个问题问得非常好。我想说，这就是下一个挑战，也是下一座需要攀登的高山。如果一定要打个比方，我想说，iO 目前还处于起步阶段。
Anna Rose：好的，甚至没有走向山，只是成长和发展。
Rachel Lin： 是的，就像在发展一样。所以我认为这项研究还处于起步阶段，我们还有很多工作要做，对吧？如果能有其他的替代构造就太好了。
这是第一点。基于原则性的新假设来构建启发式结构将非常棒。而且，我认为目前的构造距离实践还很远，因为存在几个不同的效率瓶颈。
您提到的这种引导（有时我们称之为 FE-to-iO 或 XiO-to-iO 的转换）本身就过于昂贵。但在所有这些方面，我们都需要全新的想法。在这个方面，我们可以考虑将直接代数构造，但这可能底层还是会被视为使用递归。
然而，由于直接代数构造，它可能效率更高。所以我想做的类比是，当我们第一次将 Goldreich-Micali 伪随机生成器转换为伪随机函数时，它并不是黑盒式的。它也不可用。
然而，后来我们有了直接代数构造，例如Naor–Reingold，从群中构造一个 PRF。从某种意义上说，这些构造内部可以看到原始 GGM 变换的结构，但它是代数的。代数性使它更加直接，也更加高效。
事实上，有人尝试创建这种变换的代数版本，这可能会更高效。就 XiO 本身而言，我认为也有人尝试直接基于格的候选。我们正在再次尝试基于格。
他们从格开始，我们也在尝试格。尝试直接使用全同态加密来构建 XiO 候选方案。这条路线大约在 2021 年或 2020 年启动，关键的技术障碍是克服全同态 FHE 不会泄露任何信息这一事实。
我们想要创建一种新的可控解密方法。我想给你一个电路加密，允许你对1到100的输入进行运算，并只显示1到100的输入的输出。正如我提到的，这个揭示很重要，这允许我显示这些输出（这100个输出）的令牌本身要比100短。
这就是关键的技术挑战。最近有一些研究，包括我自己的研究，正在尝试解决这个问题。然而，目前我们还处于基于格做出新假设的阶段。
所以我想说，我们还需要一段时间才能在假设方面达到稳定，并尝试去攻击它。要么我们会达到某种程度，希望我们能够达到某种程度的稳定状态，这样我们就有了一个愿意继续推进的新假设。或者，如果我们真的很幸运的话，我们或许已经设法从标准格假设出发构建了它。
Tarun Chitra：实际上，出于好奇，比如什么是非标准，比如你在这里假设的东西是什么，我猜？
Rachel Lin： 是的。所以，如果你仔细想想，全同态加密可以让我从一个加密电路（因为我想隐藏这个电路）计算任意数量的输出。所以，从输入 1 到 100，我们就用这个作为例子。
所以我会得到输出，我会得到输入从1到100的加密输出。现在的问题是，我如何揭示这些输出？所以这似乎需要我给你一个解密令牌，它可以破解输出密文。
但是，我想确保它不会破坏输入的密文，因为输入的密文隐藏了我的电路。所以我需要一些足够强大的解密令牌，能够解开我想要的某些密文，但又不会破坏其他密文的安全性。那么，这个解密令牌是什么呢？
我的意思是，更糟糕的是，这个解密令牌必须短于 100，否则还有什么意义呢？最强大的解密令牌是密钥本身。它当然短于 100，但你知道，它会泄露一切。
所以，这肯定是某种关于这个密钥的泄露信息，以及与输入（1到100）相关的泄露信息。这真的很难想出来。某种足以破解部分密文（而非全部）的泄露信息。
这就是新假设的由来。它大致如此。我们正在探索的这种假设被称为“带提示的 LWE”。
Anna Rose：带提示
Tarun Chitra：您描述的方式实际上让我想起了一些老派的复杂性理论，比如切换引理类型的东西，你随机限制一个电路，然后突然它的深度就小了很多。
Rachel Lin：哦，有趣。
Tarun Chitra： 听起来好像有点什么，好像我得读一下这篇论文，不过总之，听起来挺有意思的。我之前没意识到这一点。
Rachel Lin： 是的。我还想强调一下，直接构建 iO 有完全不同的方法，使用完全不同的数学。例如，最近有研究利用局部混合可逆电路（local mixing of reversible circuits）。
然后，还有关于启发式iO候选构造的研究，使用仿射行列式规划（affine determinant programmes）。所以在这些研究中，我们不是在研究电路。我们考虑的是不同的计算模型，比如仿射行列式规划，它更接近于分支规划。
可逆电路有点像一种计算模型，更接近于量子计算中使用的模型。因此，对于不同的计算模型，或许存在更简单的方法来扰乱它们，并有一些类似启发式的候选方案，但这些方法目前还处于起步阶段。
Tarun Chitra：嗯，听起来像是新生儿。
Rachel Lin： 他们是新生儿。是的，确实如此。
所以我想说，目前我们欢迎任何想法，任何进入这个领域的想法。我们保持乐观，因为一旦我们有了代数构造（其安全性相对可靠），以及对代数和直接构造的优化，我们的领域就拥有了如此丰富的专业知识，希望事情能够进入指数级增长的领域。
对吧？所以，我们现在的情况就是这样。
Tarun Chitra：我的意思是，它确实感觉有点像 00年代的 ZK，在你获得所有 R1CS 和人们最终认为我可以实现的东西之前。
Anna Rose：你的意思是像 2013 年之前那样？
Tarun Chitra：甚至像，就像，我的意思是，更像是 2000s 年代之前。
Anna Rose： 哦，哇。好的。
Tarun Chitra：当时，ZK 就像是一个非常小的程序。
Rachel Lin： 是的。我们需要新想法。是的。但研究的魅力在于，你永远不知道会发生什么。
我们永远不知道自己是彻底陷入困境，还是只差几个想法。一旦我们有了正确的想法，事情就可能豁然开朗。
Anna Rose：太棒了。
Rachel Lin：这也是我喜欢理论研究的原因，因为有时它可以创造这些飞跃。
Anna Rose：太酷了。
我们之前聊过你2021年的工作，以及你如何从不同领域收集这些已被证实的假设，并将它们整合在一起，从而证明这件事是可能的。从那时起，我的意思是，你只是分享了一些想法，但你自己的研究，比如你自己的工作，你一直专注于什么？你有没有谈及这些方面？
你开始探索格的东西了吗？我只是好奇你的工作是什么。
Rachel Lin： 是的。我一直在和我的合著者 Aayush Jain（也是 2021 年论文的作者）一起探索格结构。Aayush Jain 是我的长期合作伙伴，也是 2021 年论文的作者之一，还有 Amit Sahai。所以 Aayush 和我一直在探索基于格的构造。
我之前提到过，2020年和2021年提出了一种新方法，这种方法开辟了一些新的途径。最初我们主要关注密码分析，因为总有新的假设。不幸的是，我们通过密码分析证明了这些假设都有反例，对吧？
我们可以创造反例来反驳他们假设的某个版本。所以它并没有完全失效，但我想说，这段旅程很大程度上在于找到一种启发式方法。我们可以明确困难性在哪里，我们可以指出困难性的来源，即使这种困难性最终不会成为一个标准的、经过充分研究的假设，我们也希望能够说，我们能够以人性化的方式理解这个困难问题，并拥有一定的信心。
所以我认为，将这一点形式化、具体化是这一旅程中至关重要的一部分。最近，我们也提出了一个基于格的候选假设。我们将继续推进。
我们的攻击和对困难假设的具体化。所以这很有趣。这是一个方面。
除了 iO 之外，我还研究其他类型的密码对象。事实上，我研究的是混淆。我最近对混淆电路有了个有趣的想法。
Anna Rose： 其实在采访开始之前我就问过你一个问题，现在再问一下。我一直听说 iO 和混淆电路是一起用的，但你告诉我，它们其实并没有那么接近。我之前一直以为 iO 是混淆电路的技术。所以，请告诉我什么是混淆电路。
有什么不同？怎么样？有什么关联？
Rachel Lin： 是的，混淆电路是密码学中必不可少的工具之一。既然我们一直在讨论iO，你可以把它想象成一次性的求值。所以它能让我隐藏电路。
但是，为了对特定输入进行求值，我需要先获取该输入的令牌。获取到该输入的令牌后，我就可以用这个加密电路进行求值，并获得明文输出。与全同态加密不同，它会以明文形式给出输出。
但只有一次。一旦我拿到了令牌，你知道，那个混淆电路只能被求值一次。
Anna Rose：我猜 iO 是永久的吧？
Rachel Lin： iO 是永久的。是的。而且任何输入都不需要令牌。
Anna Rose： 你只需求值。太棒了。我看到了区别。
Rachel Lin： 混淆电路是早期的概念之一，它与构建双方计算相关，也用于多方计算。这是我们实现部分信息披露的传统方式，每个输出都需要你做一些事情。而在iO中，一旦我给你一些东西，你就可以继续做，这是永久的。
你说得太好了，它是永久的。所以这是一个很大的区别。因此，混淆电路是最早实现的密码学工具之一，它可以仅基于单向函数，例如，你可以使用随机预言来构建它。
而 iO 则必须依赖更多的困难问题。
Tarun Chitra：但是在混淆电路中存在简洁与不简洁的概念，对吗？
Rachel Lin： 是的，你说得对。这两个看似处于光谱两端的对象，它们的共同点在于，它们都可以泄露部分信息。而为了泄露部分信息，与全同态加密不同，完整性至关重要。你需要确保，一旦这些编码信息泄露出去，无论攻击者如何操作，都能确保在允许的输入下对正确的电路进行运算。
所以这就是完整性和可靠性的部分，对吧？现在可靠性部分实际上涵盖了整个范围。我们使用了一些技术，密码学中也有很多中间对象，例如属性基加密。
Anna Rose：是基于属性的加密吗？
Rachel Lin： 是的，基于属性的加密，这是一种介于两者之间的加密方法。人们认为它比混淆电路更强大。
虽然没有直接的可比性，但它比混淆电路强大得多，但比 iO 弱得多。它也包含完整性部分。所以有趣的是，完整性技术实际上可以随意使用。
所以，如果我使用更强大的工具，比如基于属性的加密或 iO，我就能构建更高级的混淆电路。比如，我可以构建一些本身规模很小的混淆电路。它非常简洁。
它比电路本身小得多。这被称为简洁的混淆电路。我甚至可以创建可重复使用的混淆电路，也就是说，同一个混淆电路可以用于不同的输入令牌。
您仍然需要获取输入令牌才能进行求值，但它可以在多个输入令牌之间重复使用。因此，这个概念本身实际上越来越接近功能加密，而且确实与之相关。从这个意义上讲，整个光谱都是相互关联的。
作为一名研究人员，你可以在这些不同的概念之间游走，有时逆流而上，有时顺流而下，这很有趣。
Anna Rose： 我经历过这样的对话，因为它涉及到很多假设和技术的拼凑。但是，你会发展其中的一些吗？或者说，你会去证明这些假设吗？
比如，是谁在做这件事？你说，你想建立一个证明来证明这些事情已经被证实了，那么是谁在建立这些证明呢？还有，是否会有新的证据出现，或者新的假设被证实，然后你可以把它们结合起来，这能帮助你解释某些东西实际上是安全的吗？
Rachel Lin： 每当我谈到假设时，我脑海中浮现的画面就是火山。而假设则是熔岩。一方面，它们极其危险，因为它们未经证实。
如果我推测一个问题，一个数学问题，对于多项式时间计算机来说很难解决，那么我就是在做一个假设。我可能在假设猪能飞。至终，我并不知道，因为这还没有得到证实。
Anna Rose：是的。
Rachel Lin：所以感觉火山非常非常危险。但与此同时，火山也创造了新的陆地，可供生命生长。
密码学的起源就在于假设。它，你知道，它具有二元性。它很美。
是的，这就是我们需要的。它能带我们去往我们之前不知道该如何去的地方。每当我们有了一个好的、可靠的新假设，很多东西就会从中衍生出来。你懂吗？
想想格的故事吧。我想，直到 2005 年 Regev 的论文发表，它才出现。看看因为这个假设，密码学取得了多大的进步。
但另一方面，如果我们每天的密码学业务都是我想要实现一个目标，然后我做出一个新的假设，我想要实现一个目标，然后我做出一个新的假设，那么我们就不知道我们是否只是基于错误的假设来证明每一个可能的陈述。
Tarun Chitra： 好吧，那我们知道我们不能那样做，对吧？嗯，不，是的。按照你的比喻，密码分析就好比那些喜欢在火山爆发时爬上去观看火山爆发的人……？
Rachel Lin： 是的，是的，他们确实是勇士。他们绝对是勇士，而且需要很多技能。
这就是密码学的一个重要方面。所以你说得完全正确，新的假设确实会时不时地出现。人们通常使用的那些假设通常是冰山一角，因为它们实际上很优雅，而且很容易表述。
他们拥有人们深入研究过的结构。我们对它们的安全性充满信心。因此，这些是我们优先使用的，并且有充分的理由鼓励我们使用这些结构。
但这些假设最终从何而来？嗯，人们必须尝试，对吧，从不同的数学领域汲取养分，审视我们想要构建的密码学目标，但最终却失败了，于是尝试弥合差距，并对现有假设进行修改，以提升实用性或功能性。很多人都在这样做。
而这本身有时就会给我们带来新的假设。
Anna Rose： 酷。
Tarun Chitra： 是的，我的意思是，我认为 iO 对我来说最有趣的一点，或许对 80 年代的 ZK 也算得上，就是它与复杂性理论有多接近，就像它的假设真的在复杂性理论的边缘上跳舞一样。感觉就像如果你能做 iO，你就把所有平均情况的问题都变成了可逆性的最坏情况。
这看起来就像一件非常强大的事情。所以它看起来比那些我只需要偶尔遇到最坏情况的事情要难得多。明白了吗？
就像我总是必须将最坏的情况视为一种非常高的标准一样。
Rachel Lin：是的，这确实是一个非常强大的概念。是的。
Anna Rose： 太棒了。好吧。话说回来，我真的很喜欢这次对话。
非常感谢你来参加，Rachel。之前和 Tarun 以及我聊天的时候，我对这件事一无所知。所以感觉很棒。
Rachel Lin： 非常感谢你邀请我，Anna。也非常感谢你，Tarun，问了这么多问题。你真是博学多识。
Tarun Chitra： 我不知道。我是说，我在读你们的论文。你是知识源泉。我只是个学习者。
Anna Rose： 太棒了。非常感谢你，Rachel。谢谢你。
Rachel Lin：谢谢，谢谢！
Anna Rose：我要衷心感谢播客团队，Rachel、Henrik、Tanya、Kai，以及我们的听众。感谢收听。