不可区分混淆被实现，计算机科学家摘得这颗密码学皇冠上的明珠机器之心报道编辑：魔王、小

机器之心报道
编辑：魔王、小舟
iO（Indistinguishability Obfuscation ，不可区分混淆）是密码学中黑科技一样的存在，但很多人认为它并不存在。最近，一些研究人员提出了新的 iO 协议。
2018 年，加州大学洛杉矶分校博士生 Aayush Jain 前往日本演讲，介绍他和同事正在开发的一款强大的加密工具。在他陈述团队在 iO 方面的努力时，有观众提问：「我认为 iO 不存在。」
当时，这种看法较为普遍。如果 iO 确实存在，它不仅可以隐藏数据集合，还可以隐藏计算机程序的内部工作机制，创造出强大的加密工具。哈佛大学计算机科学教授 Boaz Barak 表示，这是「掌控一切的密码学原语」，而这种力量的强大让人们怀疑 iO 是否真的存在。
2013 年，计算机科学家 Sanjam Garg、Amit Sahai 等人首次提出 iO 的候选版本，后来其他研究者找出了对其安全性进行攻击的方法。「谁将赢得胜利，the makers or the breakers？」
加州大学伯克利分校西蒙斯计算理论研究所负责人 Shafi Goldwasser 表示：「当时很多人对此很狂热，他们相信 iO 的存在，并坚持研究。但后来这些人越来越少了。」
而近期， Aayush Jain 与华盛顿大学副教授 Huijia Lin、Jain 的导师 Amit Sahai 合作的一项研究为 maker 站台。这篇于 8 月 18 日线上发布的论文首次展示了，如何仅使用「标准」安全假设来构建 iO 。
论文链接：
文章插图
加州大学伯克利分校博士生、论文一作 Aayush Jain
所有的加密协议都依赖于一些假设，譬如著名的 RSA 算法基于一条被普遍认同的观点：标准计算机无法对两个大素数的乘积进行因式分解。加密协议的安全性和其假设有关，之前的 iO 基于未经测试、最终被证明不可靠的假设。而最新的协议依赖于经过广泛使用和研究的安全假设。
尽管这一协议距离现实部署还很遥远，但它从理论角度提供了一种即时构建多个加密工具的方式，而这在之前是不可能的。例如，它允许创建「可否认」加密和「函数」加密。
以色列理工学院教授 Yuval Ishai 表示：「现在应该不会有人怀疑 iO 的存在了。」
iO：密码学「皇冠上的明珠」
数十年来，计算机科学家一直在思考是否存在安全、全面的方式来实现计算机程序混淆，使人们能够在不了解其内部秘密的情况下使用它们。程序混淆可以支持大量实际应用，如使用混淆程序在银行或电子邮件账户中向他人委派任务，而无需担心别人滥用该程序或读取你的账户密码。
但截至目前，所有构建现实混淆器的尝试都失败了。 2001 年，理论层面也出现了坏消息：最强大的混淆形式「黑盒混淆」是难以实现的。（黑盒混淆即攻击者无法了解程序内部，只能看到程序的使用及其输出。）Boaz Barak、Amit Sahai 以及其他五位研究者证明，一些程序自己揭示了内部秘密，它们无法实现完全混淆。
不过，这些程序是专门创建来抵抗混淆的，与现实程序没有太多相似之处。因此，计算机科学家希望存在另外一些混淆，它足够弱因此是可行的，又足够强能够隐藏人们真正关心的秘密。证明黑盒混淆不可能实现的研究者在论文中提出了一个可能的替代方案：iO 。
【不可区分混淆被实现，计算机科学家摘得这颗密码学皇冠上的明珠】乍一看， iO 并不是特别有用的概念。它不要求隐藏程序的秘密，只要求程序足够混淆，比如你有两个可执行相同任务的不同程序，你无法区分哪个是混淆版本，哪个是原版。
文章插图
Aayush Jain 导师、UCLA 教授 Amit Sahai ，也是 iO 候选版本的提出者之一。
但是， iO 实际上要强大得多。例如，假设你有一个程序，可以执行一些与银行账户相关的任务，但是它包含未加密密码，因此易受攻击。但是，只要有一个执行同样任务但能够隐藏密码的程序，不可区分混淆器就可以成功地 mask 密码。
近年来，计算机科学家证明 iO 可以作为几乎所有加密协议的基础（除了黑盒混淆），包括经典的加密任务（如公钥加密）和新兴任务（如全同态加密）。它还涵盖无人知道如何构建的加密协议，如可否认加密和函数加密。
康奈尔大学教授 Rafael Pass 表示：「这是皇冠上的明珠。一旦实现，我们可以获得一切。」
2013 年， Sanjam Garg、Amit Sahai 等人提出 iO 候选版本，将一个程序分割成多个「拼图块」，然后使用多重线性映射混淆单个「拼图块」。把所有拼图块拼在一起后，所有混淆互相抵消，程序运转如常，但是每个单独的「拼图块」看起来是无意义的。当时，这一研究结果被视为一大突破，并引发了后续大量相关论文。然而几年后，其他研究者发现多重线性映射并不安全。之后又出现了其他 iO 候选版本，但也都被攻破。