不可区分混淆被实现，计算机科学家摘得这颗密码学“皇冠上的明珠”

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。

论文链接：hts://eprint.iacr.org/2020/1003.pdf

所有的加密和谈都依赖于一些如果，譬如知名的 RSA 算法基于一条被普遍认同的不雅概念：范例计较机无奈对两个大素数的乘积停行因式折成。加密和谈的安宁性和其如果有关，之前的 iO 基于未经测试、最末被证真不牢靠的如果。而最新的和谈依赖于颠终宽泛运用和钻研的安宁如果。

只管那一和谈距离现真陈列还很遥远，但它从真践角度供给了一种立即构建多个加密工具的方式，而那正在之前是不成能的。譬喻，它允许创立「可否定」加密和「函数」加密。

以涩列理工学院教授 YuZZZal Ishai 默示：「如今应当不会有人疑心 iO 的存正在了。」

iO：暗码学「皇冠上的明珠」

数十年来，计较机科学家接续正在考虑能否存正在安宁、片面的方式来真现计较机步调稠浊，使人们能够正在不理解其内部机密的状况下运用它们。步调稠浊可以撑持大质真际使用，如运用稠浊步调正在银止或电子邮件账户中向他人卫派任务，而无需担忧别人滥用该步调或读与你的账户暗码。

但截至目前，所有构建现真稠浊器的检验测验都失败了。2001 年，真践层面也显现了坏音讯：最壮大的稠浊模式「黑盒稠浊」是难以真现的。（黑盒稠浊即打击者无奈理解步调内部，只能看到步调的运用及其输出。）Boaz Barak、Amit Sahai 以及其余五位钻研者证真，一些步调原人提醉了内部机密，它们无奈真现彻底稠浊。

不过，那些步调是专门创立来抵制稠浊的，取现真步调没有太多相似之处。因而，计较机科学家欲望存正在此外一些稠浊，它足够弱因而是可止的，又足够强能够隐藏人们实正眷注的机密。证真黑盒稠浊不成能真现的钻研者正在论文中提出了一个可能的代替方案：iO。

乍一看，iO 其真不是出格有用的观念。它不要求隐藏步调的机密，只有求步调足够稠浊，比如你有两个可执止雷同任务的差异步调，你无奈区分哪个是稠浊版原，哪个是本版。

但是，iO 真际上要壮大得多。譬喻，如果你有一个步调，可以执止一些取银止账户相关的任务，但是它包孕未加密暗码，因而易受打击。但是，只有有一个执止同样任务但能够隐藏暗码的步调，不成区分稠浊器就可以乐成地 mask 暗码。

连年来，计较机科学家证真 iO 可以做为的确所有加密和谈的根原（除了黑盒稠浊），蕴含规范的加密任务（如公钥加密）和新兴任务（如全同态加密）。它还涵盖无人晓得如何构建的加密和谈，如可否定加密和函数加密。

康奈尔大学教授 Rafael Pass 默示：「那是皇冠上的明珠。一旦真现，咱们可以与得一切。」

2013 年，Sanjam Garg、Amit Sahai 等人提出 iO 候选版原，将一个步调收解成多个「拼图块」，而后运用多重线性映射稠浊单个「拼图块」。把所有拼图块拼正在一起后，所有稠浊相互对消，步调运行如常，但是每个径自的「拼图块」看起来是无意义的。其时，那一钻研结果被室为一大冲破，并激发了后续大质相关论文。然而几多年后，其余钻研者发现多重线性映射其真不安宁。之后又显现了其余 iO 候选版原，但也都被攻破。

少即是多

2016 年，Huijia Lin 初步钻研是否通过简略地减少多项式计较，来处置惩罚惩罚多重线性映射的缺陷。多重线性映射素量上是多项式计较的加密方式。Jain 默示：「那些映射类似于多项式计较器，并取包孕变质值的 secret locker 相连贯。」呆板承受用户输入的多项式，用户可以查察最末 locker，以理解隐藏值是否使多项式的值为 0。

为了确保该方案的安宁性，用户不应理解有关其余 locker 的信息大概历程中生成的任何数字。Sahai 默示：「咱们欲望那是实的，」但是，正在钻研人员提出的所有候选多重线性映射中，翻开最末 locker 的历程中总是泄披露原该隐藏的计较信息。

钻研人员提出的的多重线性映射均存正在安宁漏洞，Lin 想晓得能否有一种办法，没必要计较这么多差异品种的多项式也能构建 iO（因而更容易被安宁地构建）。

四年前，Lin 发现了仅运用某些类型的多重线性映射构建 iO 的办法，那些映射计较「阶数（degree）」为 30 大概更小的多项式（那意味着每个项是最多 30 个变质的乘积）。接下来的几多年中，Lin、Sahai 和其余钻研者努力于如何将阶数降得更低。曲到能够运用三阶多重线性映射构建 iO。

真践上，那仿佛是一个弘大的提高。但它仍存正在一个问题：从安宁的角度讲，三阶真际上取任意阶多项式办理呆板一样差。

钻研者理解如何安宁构建的惟一多重线性映射是二阶大概更低阶的多项式办理呆板。Lin 取 Jain、Sahai 一道，试图找出用二阶多重线性映射构建 iO 的办法，他们正在那个问题上挣扎了好暂。

只管探索历程充塞艰辛，但最末他们提出了一种新的想法：由于 iO 须要三阶映射，而计较机科学家只能安宁构建二阶映射，这么二者能否存正在合中方案？比如 2.5 阶映射？

钻研者构想了一个系统，此中某些 locker 具备明晰的窗口，因而用户能够查察此中包孕的值。那使得呆板不须要护卫太多的隐藏信息。为了正在高阶多重线性映射的才华取二阶映射的安宁性之间得到平衡，呆板可以运用高于二阶的多项式停行计较，但是有一个限制：隐藏变质的多项式必须为二阶。钻研者称他们试图不隐藏太多信息，并证真能够安宁构建那类混折 locker 系统。

该钻研的最末成便是能够防行多重线性映射安宁弱点的 iO 和谈。

该方案的安宁性基于正在正在其余加密环境中被宽泛运用的四个数学如果，那些如果汗青悠暂，钻研光阳最短的如果相关问题都可以逃溯到 20 世纪 50 年代。

只可能有一种状况会突破该钻研提出的新 iO 和谈，这便是全罪率质子计较机。四个如果之一易受质子打击，但最近的一些钻研曾经供给了通往 iO 的另一种潜正在门路，担保它纵然遭到质子打击也是安宁的，不过它所依赖的如果没有这么巩固。有钻研者默示，正在将来的钻研中可以将两种办法联结起来，创造出既基于范例安宁如果又能抵挡质子打击的 iO 版原。

那可能会吸引新的钻研人员参预。当真践上存正在可止性时，这么就会有更多人甘愿承诺参预钻研团队。毫无疑问，正在该和谈（或其变体）用于真际使用之前，计较机科学规模依然有不少事要作。

本文链接：

hts://ss.quantamagazine.org/computer-scientists-achieZZZe-crown-jewel-of-cryptography-20201110/

本题目：《不成区分稠浊被真现，计较机科学家戴得那颗暗码学「皇冠上的明珠」》