澎湃新闻|不可区分混淆被实现计算机科学家摘得这颗密码学“皇冠上的明珠”( 二 ) 机器之心报道

乍一看， iO 并不是特别有用的概念。它不要求隐藏程序的秘密，只要求程序足够混淆，比如你有两个可执行相同任务的不同程序，你无法区分哪个是混淆版本，哪个是原版。

文章图片
Aayush Jain 导师、UCLA 教授 Amit Sahai ，也是 iO 候选版本的提出者之一。
但是， iO 实际上要强大得多。例如，假设你有一个程序，可以执行一些与银行账户相关的任务，但是它包含未加密密码，因此易受攻击。但是，只要有一个执行同样任务但能够隐藏密码的程序，不可区分混淆器就可以成功地 mask 密码。
近年来，计算机科学家证明 iO 可以作为几乎所有加密协议的基础（除了黑盒混淆），包括经典的加密任务（如公钥加密）和新兴任务（如全同态加密）。它还涵盖无人知道如何构建的加密协议，如可否认加密和函数加密。
康奈尔大学教授 Rafael Pass 表示：「这是皇冠上的明珠。一旦实现，我们可以获得一切。」
2013 年， Sanjam Garg、Amit Sahai 等人提出 iO 候选版本，将一个程序分割成多个「拼图块」，然后使用多重线性映射混淆单个「拼图块」。把所有拼图块拼在一起后，所有混淆互相抵消，程序运转如常，但是每个单独的「拼图块」看起来是无意义的。当时，这一研究结果被视为一大突破，并引发了后续大量相关论文。然而几年后，其他研究者发现多重线性映射并不安全。之后又出现了其他 iO 候选版本，但也都被攻破。

文章图片
当时，很多人担心 iO 可能只是个无法实现的奇迹。
少即是多
2016 年， Huijia Lin 开始研究能否通过简单地减少多项式计算，来解决多重线性映射的缺陷。多重线性映射本质上是多项式计算的加密方式。Jain 表示：「这些映射类似于多项式计算器，并与包含变量值的 secret locker 相连接。」机器接受用户输入的多项式，用户可以查看最终 locker ，以了解隐藏值能否使多项式的值为 0 。
为了确保该方案的安全性，用户不应了解有关其他 locker 的信息或者过程中生成的任何数字。Sahai 表示：「我们希望这是真的，」但是，在研究人员提出的所有候选多重线性映射中，打开最终 locker 的过程中总是泄露出本该隐藏的计算信息。

文章图片
华盛顿大学副教授、该研究第二作者 Huijia Lin 。
研究人员提出的的多重线性映射均存在安全漏洞， Lin 想知道是否有一种方法，不必计算那么多不同种类的多项式也能构建 iO（因此更容易被安全地构建）。
四年前， Lin 发现了仅使用某些类型的多重线性映射构建 iO 的方法，这些映射计算「阶数（degree）」为 30 或者更小的多项式（这意味着每个项是最多 30 个变量的乘积）。接下来的几年中， Lin、Sahai 和其他研究者致力于如何将阶数降得更低。直到能够使用三阶多重线性映射构建 iO 。
理论上，这似乎是一个巨大的进步。但它仍存在一个问题：从安全的角度讲，三阶实际上与任意阶多项式处理机器一样差。

澎湃新闻|不可区分混淆被实现 计算机科学家摘得这颗密码学“皇冠上的明珠”( 二 )

澎湃新闻|不可区分混淆被实现计算机科学家摘得这颗密码学“皇冠上的明珠”( 二 )