13

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

 4 years ago
source link: https://www.jiqizhixin.com/articles/2020-11-12-6
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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。

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

Jzua2qe.jpg!mobile

加州大学伯克利分校博士生、论文一作 Aayush Jain

所有的加密协议都依赖于一些假设，譬如著名的 RSA 算法基于一条被普遍认同的观点：标准计算机无法对两个大素数的乘积进行因式分解。加密协议的安全性和其假设有关，之前的 iO 基于未经测试、最终被证明不可靠的假设。而最新的协议依赖于经过广泛使用和研究的安全假设。

尽管这一协议距离现实部署还很遥远，但它从理论角度提供了一种即时构建多个加密工具的方式，而这在之前是不可能的。例如，它允许创建「可否认」加密和「函数」加密。

以色列理工学院教授 Yuval Ishai 表示：「现在应该不会有人怀疑 iO 的存在了。」

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

数十年来，计算机科学家一直在思考是否存在安全、全面的方式来实现计算机程序混淆，使人们能够在不了解其内部秘密的情况下使用它们。程序混淆可以支持大量实际应用，如使用混淆程序在银行或电子邮件账户中向他人委派任务，而无需担心别人滥用该程序或读取你的账户密码。

但截至目前，所有构建现实混淆器的尝试都失败了。2001 年，理论层面也出现了坏消息：最强大的混淆形式「黑盒混淆」是难以实现的。（黑盒混淆即攻击者无法了解程序内部，只能看到程序的使用及其输出。）Boaz Barak、Amit Sahai 以及其他五位研究者证明，一些程序自己揭示了内部秘密，它们无法实现完全混淆。

不过，这些程序是专门创建来抵抗混淆的，与现实程序没有太多相似之处。因此，计算机科学家希望存在另外一些混淆，它足够弱因此是可行的，又足够强能够隐藏人们真正关心的秘密。证明黑盒混淆不可能实现的研究者在论文中提出了一个可能的替代方案：iO。

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

Bb2eAnq.jpg!mobile

Aayush Jain 导师、UCLA 教授 Amit Sahai，也是 iO 候选版本的提出者之一。

但是，iO 实际上要强大得多。例如，假设你有一个程序，可以执行一些与银行账户相关的任务，但是它包含未加密密码，因此易受攻击。但是，只要有一个执行同样任务但能够隐藏密码的程序，不可区分混淆器就可以成功地 mask 密码。

近年来，计算机科学家证明 iO 可以作为几乎所有加密协议的基础（除了黑盒混淆），包括经典的加密任务（如公钥加密）和新兴任务（如全同态加密）。它还涵盖无人知道如何构建的加密协议，如可否认加密和函数加密。

康奈尔大学教授 Rafael Pass 表示：「这是皇冠上的明珠。一旦实现，我们可以获得一切。」

2013 年，Sanjam Garg、Amit Sahai 等人提出 iO 候选版本，将一个程序分割成多个「拼图块」，然后使用多重线性映射混淆单个「拼图块」。把所有拼图块拼在一起后，所有混淆互相抵消，程序运转如常，但是每个单独的「拼图块」看起来是无意义的。当时，这一研究结果被视为一大突破，并引发了后续大量相关论文。然而几年后，其他研究者发现多重线性映射并不安全。之后又出现了其他 iO 候选版本，但也都被攻破。

YfENRfa.png!mobile

当时，很多人担心 iO 可能只是个无法实现的奇迹。

少即是多

2016 年，Huijia Lin 开始研究能否通过简单地减少多项式计算，来解决多重线性映射的缺陷。多重线性映射本质上是多项式计算的加密方式。Jain 表示：「这些映射类似于多项式计算器，并与包含变量值的 secret locker 相连接。」机器接受用户输入的多项式，用户可以查看最终 locker，以了解隐藏值能否使多项式的值为 0。

为了确保该方案的安全性，用户不应了解有关其他 locker 的信息或者过程中生成的任何数字。Sahai 表示：「我们希望这是真的，」但是，在研究人员提出的所有候选多重线性映射中，打开最终 locker 的过程中总是泄露出本该隐藏的计算信息。

qeqANr6.jpg!mobile

华盛顿大学副教授、该研究第二作者 Huijia Lin。

研究人员提出的的多重线性映射均存在安全漏洞，Lin 想知道是否有一种方法，不必计算那么多不同种类的多项式也能构建 iO（因此更容易被安全地构建）。

四年前，Lin 发现了仅使用某些类型的多重线性映射构建 iO 的方法，这些映射计算「阶数（degree）」为 30 或者更小的多项式（这意味着每个项是最多 30 个变量的乘积）。接下来的几年中，Lin、Sahai 和其他研究者致力于如何将阶数降得更低。直到能够使用三阶多重线性映射构建 iO。

理论上，这似乎是一个巨大的进步。但它仍存在一个问题：从安全的角度讲，三阶实际上与任意阶多项式处理机器一样差。

研究者了解如何安全构建的唯一多重线性映射是二阶或者更低阶的多项式处理机器。Lin 与 Jain、Sahai 一道，试图找出用二阶多重线性映射构建 iO 的方法，他们在这个问题上挣扎了很久。

尽管探究过程充满艰辛，但最终他们提出了一种新的想法：由于 iO 需要三阶映射，而计算机科学家只能安全构建二阶映射，那么二者是否存在折中方案？比如 2.5 阶映射？

研究者设想了一个系统，其中某些 locker 具备清晰的窗口，因此用户能够查看其中包含的值。这使得机器不需要保护太多的隐藏信息。为了在高阶多重线性映射的能力与二阶映射的安全性之间取得平衡，机器可以使用高于二阶的多项式进行计算，但是有一个限制：隐藏变量的多项式必须为二阶。研究者称他们试图不隐藏太多信息，并证明能够安全构建这类混合 locker 系统。

EjqQjiy.png!mobile

要将这些功效较弱的多重线性映射转换为 iO，还需要最后一个要素：一种新型的伪随机数生成器。它可以将一串随机位扩展为更长的字符串，并且仍具有随机性。

该研究的最终成果是能够避免多重线性映射安全弱点的 iO 协议。

该方案的安全性基于在在其他加密环境中被广泛使用的四个数学假设，这些假设历史悠久，研究时间最短的假设相关问题都可以追溯到 20 世纪 50 年代。

只可能有一种情况会打破该研究提出的新 iO 协议，那就是全功率量子计算机。四个假设之一易受量子攻击，但最近的一些研究已经提供了通往 iO 的另一种潜在途径，保证它即使受到量子攻击也是安全的，不过它所依赖的假设没有那么坚固。有研究者表示，在未来的研究中可以将两种方法结合起来，创造出既基于标准安全假设又能抵挡量子攻击的 iO 版本。

这可能会吸引新的研究人员加入。当理论上存在可行性时，那么就会有更多人愿意加入研究团队。毫无疑问，在该协议（或其变体）用于实际应用之前，计算机科学领域仍然有很多事要做。

原文链接：

https://www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK