不可区分混淆被实现，计算机科学家摘得这颗密码学皇冠上的明珠
机器之心报道
编辑：魔王、小舟
iO（IndistinguishabilityObfuscation ， 不可区分混淆）是密码学中黑科技一样的存在 ， 但很多人认为它并不存在 。 最近 ， 一些研究人员提出了新的iO协议 。
2018年 ， 加州大学洛杉矶分校博士生AayushJain前往日本演讲 ， 介绍他和同事正在开发的一款强大的加密工具 。 在他陈述团队在iO方面的努力时 ， 有观众提问：「我认为iO不存在 。 」
当时 ， 这种看法较为普遍 。 如果iO确实存在 ， 它不仅可以隐藏数据集合 ， 还可以隐藏计算机程序的内部工作机制 ， 创造出强大的加密工具 。 哈佛大学计算机科学教授BoazBarak表示 ， 这是「掌控一切的密码学原语」 ， 而这种力量的强大让人们怀疑iO是否真的存在 。
2013年 ， 计算机科学家SanjamGarg、AmitSahai等人首次提出iO的候选版本 ， 后来其他研究者找出了对其安全性进行攻击的方法 。 「谁将赢得胜利 ， themakersorthebreakers？」
加州大学伯克利分校西蒙斯计算理论研究所负责人ShafiGoldwasser表示：「当时很多人对此很狂热 ， 他们相信iO的存在 ， 并坚持研究 。 但后来这些人越来越少了 。 」
而近期 ， AayushJain与华盛顿大学副教授HuijiaLin、Jain的导师AmitSahai合作的一项研究为maker站台 。 这篇于8月18日线上发布的论文首次展示了 ， 如何仅使用「标准」安全假设来构建iO 。
论文链接：https://eprint.iacr.org/2020/1003.pdf
文章图片
加州大学伯克利分校博士生、论文一作AayushJain
所有的加密协议都依赖于一些假设 ， 譬如著名的RSA算法基于一条被普遍认同的观点：标准计算机无法对两个大素数的乘积进行因式分解 。 加密协议的安全性和其假设有关 ， 之前的iO基于未经测试、最终被证明不可靠的假设 。 而最新的协议依赖于经过广泛使用和研究的安全假设 。
尽管这一协议距离现实部署还很遥远 ， 但它从理论角度提供了一种即时构建多个加密工具的方式 ， 而这在之前是不可能的 。 例如 ， 它允许创建「可否认」加密和「函数」加密 。
以色列理工学院教授YuvalIshai表示：「现在应该不会有人怀疑iO的存在了 。 」
【不可区分混淆被实现，计算机科学家摘得这颗密码学皇冠上的明珠】iO：密码学「皇冠上的明珠」
数十年来 ， 计算机科学家一直在思考是否存在安全、全面的方式来实现计算机程序混淆 ， 使人们能够在不了解其内部秘密的情况下使用它们 。 程序混淆可以支持大量实际应用 ， 如使用混淆程序在银行或电子邮件账户中向他人委派任务 ， 而无需担心别人滥用该程序或读取你的账户密码 。
但截至目前 ， 所有构建现实混淆器的尝试都失败了 。 2001年 ， 理论层面也出现了坏消息：最强大的混淆形式「黑盒混淆」是难以实现的 。 （黑盒混淆即攻击者无法了解程序内部 ， 只能看到程序的使用及其输出 。 ）BoazBarak、AmitSahai以及其他五位研究者证明 ， 一些程序自己揭示了内部秘密 ， 它们无法实现完全混淆 。
不过 ， 这些程序是专门创建来抵抗混淆的 ， 与现实程序没有太多相似之处 。 因此 ， 计算机科学家希望存在另外一些混淆 ， 它足够弱因此是可行的 ， 又足够强能够隐藏人们真正关心的秘密 。 证明黑盒混淆不可能实现的研究者在论文中提出了一个可能的替代方案：iO 。
乍一看 ， iO并不是特别有用的概念 。 它不要求隐藏程序的秘密 ， 只要求程序足够混淆 ， 比如你有两个可执行相同任务的不同程序 ， 你无法区分哪个是混淆版本 ， 哪个是原版 。
文章图片
AayushJain导师、UCLA教授AmitSahai ， 也是iO候选版本的提出者之一 。
但是 ， iO实际上要强大得多 。 例如 ， 假设你有一个程序 ， 可以执行一些与银行账户相关的任务 ， 但是它包含未加密密码 ， 因此易受攻击 。 但是 ， 只要有一个执行同样任务但能够隐藏密码的程序 ， 不可区分混淆器就可以成功地mask密码 。
近年来 ， 计算机科学家证明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年代 。
只可能有一种情况会打破该研究提出的新iO协议 ， 那就是全功率量子计算机 。 四个假设之一易受量子攻击 ， 但最近的一些研究已经提供了通往iO的另一种潜在途径 ， 保证它即使受到量子攻击也是安全的 ， 不过它所依赖的假设没有那么坚固 。 有研究者表示 ， 在未来的研究中可以将两种方法结合起来 ， 创造出既基于标准安全假设又能抵挡量子攻击的iO版本 。
这可能会吸引新的研究人员加入 。 当理论上存在可行性时 ， 那么就会有更多人愿意加入研究团队 。 毫无疑问 ， 在该协议（或其变体）用于实际应用之前 ， 计算机科学领域仍然有很多事要做 。
https://www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/
推荐阅读
- 量化|量化大师麦教授：美好的不确定性
- 结核|再见吧，“结核君”
- 减肥也能吃的小零食，营养美味，低脂低热量，多吃也不怕！
- 这款抹茶麻薯软欧，简单好做，满满坚果馅，好吃还不腻
- 1碗面粉，不加水，锅里蒸一蒸，做香甜可口的发糕，比蛋糕还香
- 扇贝最好吃的做法，适合冬日里吃，做法简单好吃不腻，家人超爱吃
- 从小就馋此口，比肉香多了，几块钱做一大盘，咋吃都不腻
- 盐酥烧饼这做法，皮酥里软吃着香，不醒面照样层层酥脆，省时间
- 番茄炒鸡蛋先炒番茄还是先炒鸡蛋？其实都不对，正确方法送给你
- 一碗糯米，半个南瓜，香甜软糯，好吃不上火，比南瓜饼香，太好吃