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

近年来，计算机科学家证明iO可以作为几乎所有加密协议的基础（除了黑盒混淆），包括经典的加密任务（如公钥加密）和新兴任务（如全同态加密）。它还涵盖无人知道如何构建的加密协议，如可否认加密和函数加密。
康奈尔大学教授RafaelPass表示：「这是皇冠上的明珠。一旦实现，我们可以获得一切。」
2013年， SanjamGarg、AmitSahai等人提出iO候选版本，将一个程序分割成多个「拼图块」，然后使用多重线性映射混淆单个「拼图块」。把所有拼图块拼在一起后，所有混淆互相抵消，程序运转如常，但是每个单独的「拼图块」看起来是无意义的。当时，这一研究结果被视为一大突破，并引发了后续大量相关论文。然而几年后，其他研究者发现多重线性映射并不安全。之后又出现了其他iO候选版本，但也都被攻破。

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

文章图片
华盛顿大学副教授、该研究第二作者HuijiaLin 。
研究人员提出的的多重线性映射均存在安全漏洞， Lin想知道是否有一种方法，不必计算那么多不同种类的多项式也能构建iO（因此更容易被安全地构建）。
四年前， Lin发现了仅使用某些类型的多重线性映射构建iO的方法，这些映射计算「阶数（degree）」为30或者更小的多项式（这意味着每个项是最多30个变量的乘积）。接下来的几年中， Lin、Sahai和其他研究者致力于如何将阶数降得更低。直到能够使用三阶多重线性映射构建iO 。
理论上，这似乎是一个巨大的进步。但它仍存在一个问题：从安全的角度讲，三阶实际上与任意阶多项式处理机器一样差。
研究者了解如何安全构建的唯一多重线性映射是二阶或者更低阶的多项式处理机器。 Lin与Jain、Sahai一道，试图找出用二阶多重线性映射构建iO的方法，他们在这个问题上挣扎了很久。
尽管探究过程充满艰辛，但最终他们提出了一种新的想法：由于iO需要三阶映射，而计算机科学家只能安全构建二阶映射，那么二者是否存在折中方案？比如2.5阶映射？
研究者设想了一个系统，其中某些locker具备清晰的窗口，因此用户能够查看其中包含的值。这使得机器不需要保护太多的隐藏信息。为了在高阶多重线性映射的能力与二阶映射的安全性之间取得平衡，机器可以使用高于二阶的多项式进行计算，但是有一个限制：隐藏变量的多项式必须为二阶。研究者称他们试图不隐藏太多信息，并证明能够安全构建这类混合locker系统。

文章图片
要将这些功效较弱的多重线性映射转换为iO ，还需要最后一个要素：一种新型的伪随机数生成器。它可以将一串随机位扩展为更长的字符串，并且仍具有随机性。
该研究的最终成果是能够避免多重线性映射安全弱点的iO协议。
该方案的安全性基于在在其他加密环境中被广泛使用的四个数学假设，这些假设历史悠久，研究时间最短的假设相关问题都可以追溯到20世纪50年代。

科技小辛辛 计算机科学家摘得这颗密码学皇冠上的明珠，不可区分混淆被实现( 二 )

科技小辛辛计算机科学家摘得这颗密码学皇冠上的明珠，不可区分混淆被实现( 二 )