几乎无解的最强加密方法，终于被证实真的存在

数学算法俱乐部

日期 ： 2021年01月04日       

正文共 ：3796字

来源 ： 环球科学

图片来源：Kiel Mutschelknaus for Quanta Magazine

构建无法破解的密码，是众多密码学科学家的目标。一种被称为不可区分混淆的加密方式因为太过完美，多年来被认为无法实现。不过最近，三名研究者首次证明不可区分混淆是可行的，这或许是通往完美密码的重要一步。

2018年，加州大学洛杉矶分校的研究生Ayush Jain前往日本，就他和同事正在开发的强大加密算法进行交流。当他讲述团队正在尝试实现不可区分混淆（indistinguishability obfuscation，简称iO）时，一位观众困惑地举起了手。

“可我一直以为iO不存在？”他说。

当时，这样的怀疑是普遍存在的。不可区分混淆如果可以被构建，不仅能隐藏数据集，还能隐藏程序本身，从而构建一种可以实现几乎所有其他加密协议的加密算法。但对很多计算机科学家来说，强大到如此地步让iO看起来难以实现。

计算机科学家从2013年开始提出iO的候选版本。但是他们很快被泼了一盆冷水，其他研究者发现了破解它安全性的方法。

现在，Jain与华盛顿大学的林惠嘉（Huijia Lin，音译），以及Jain在加州大学洛杉矶分校的导师阿米特·沙海（Amit Sahai）一起证明了这种方法的可行性。在8月18日在网上公开的论文里，这三名研究者首次展示了如何仅用“标准的”安全假设来构建不可区分混淆。

从左至右依次为Jain、沙海和林惠嘉

所有的加密协议都基于某些假设，比如著名的RSA算法，基于人们普遍认为的观点——标准计算机不能快速对大数进行质因数分解。加密协议的安全性和前提假设是绑定的，而iO的前提假设建立在未经检验并且不牢固的基础上。相比之下，新的加密协议建立在经过广泛检验的假设基础之上。

虽然协议还远未能实用，但从理论上讲，通过它可以立即构建一系列以前遥不可及的加密方式。例如，它支持创建可否认加密（deniable encryption），这种加密方式可以让你向攻击者发送和真实邮件完全不同的消息；以及函数加密（functional encryption），这种加密可以让你向用户提供不同级别的访问权限，从而用数据进行计算。

以色列理工学院的尤瓦尔·伊沙伊（Yuval Ishai）说：“现在不会有人怀疑不可区分混淆的存在了，这似乎是个不错的结局。”

皇冠上的宝石

几十年来，计算机科学家一直都想知道是否存在安全，包罗万象的方法来混淆计算机程序，让人们使用的同时无法破解。

要想知道不可区分混淆是什么，我们不妨先来看一看混淆是什么。

例如，对于程序员来说，最宝贵的自然是代码，一旦源码被别人看到了，那么基本上花的心血和知识产权都被人一览无余。为了保护代码，可以在导出程序之前采取一些手段来混淆程序，现在一般有两种程序混淆方法，即代码混淆（Code Obfuscation）和代码编译（Compilation）。

代码混淆是为了防止程序代码本身给外人提供太多信息，同时使程序的运行效率更高。在导出程序时，会将所有标注性的符号（symbols）摘除掉。比较简单的方法是直接全文替代关键词，例如将全文的ui_controller替代为a0123456，这样程序的符号就无法暴露程序运转内容了。代码编译更简单，直接输出编译后的代码，将人们可以看懂的源代码转换成电脑看得懂的机器码。这个过程，就相当于把上面提到的符号全部抹除了，他人看到我们发布的可执行文件中的机器码时，自然看不懂其中发生了什么。

但对人的混淆并不是严格意义上的混淆，这样的混淆在密码学的定义上是非常脆弱的。在电脑程序的分析下，“混淆”后的程序会变得一览无余，一下就能看出程序在干什么。

真正意义上的混淆被称作虚拟黑盒（Virtual Black Box Obfuscation，VBB）。将一个程序C嵌入一个黑盒中，我们可以在黑盒的一端输入x，另一头会输出C(x)。因为整个程序都藏在黑盒中，我们完全无法得知任何C的构造信息。唯一可以做的，就是提供输入x，观察另一头的输出C(x)。

我们称这样的黑盒为VBB混淆器O，对于经过O混淆的程序C，我们称其为O(C)。O(C)的输出C(x)并不会暴露任何关于C的任何信息。

如果实现虚拟黑盒，用户可以使用程序却无法理解程序本身，那么就能让开发的程序永远不被破解，或是用很简单地实现公钥加密。密码学中几乎所有比较高级的构造都可以非常简单地用虚拟黑盒实现。

但虚拟黑盒的概念提出不久后，人们很快就被泼了一盆冷水。2001年，七位大牛联手对混淆这一概念做了系统性的研究，并且发表了一篇文章：On the (Im)possibility of Obfuscating Programs。在文章中，他们提出了一种特殊构造的程序，并证明其无法被混淆。而这等于是在说：通用的VBB混淆是绝对不可能的。

不过，同样是在这篇论文中，一种混淆的新型定义被提出来了——如果一对程序C₁和C₂具有相同的功能性，能否通过一种新的混淆算法，使第三方无法区分两个程序的混淆结果呢？对于这样的混淆，我们称之为不可区分混淆（iO）。

虽然VBB不可能实现，但是通过iO，我们仍然可以非常完美地混淆一个程序。

假如我们有一个程序P，我们可以用五花八门的办法和技巧来混淆程序，得到一个最强混淆功能却相同的P*。同时，如果我们拥有iO，那么完全不需要很多费劲的混淆操作，可以直接得到相同的结果，因为我们无法区分混淆后的iO(P)和iO(P*)。仅仅是给P套了一层iO，得到的结果和最强混淆过后P*的iO是一样的。

图片来源：知乎用户@Steven Yue

这样一来，如果我们想充分混淆一个程序P，使其构造不被别人发现，只需要输出iO(P)就行了。

有了强大的不可区分混淆，我们就能完美加密已有的程序，使其永远不会被破解。同时，由于iO密码学完备（Crypto-Complete）的特性，我们可以轻易借其实现一系列强大的密码学构造。

更少即是更多

2013年，沙海和五位合著者提出了一个iO协议，将程序拆成几部分，类似拼图，然后他们使用多线性配对来找出这些拼图。单个碎片看上去毫无意义，但如果将碎片正确地组合到一起，程序就能正常工作。

多线性配对本质上是用多项式计算的密码学方法——由不同变量和数字之积的加和组成的数学表达式，如3xy+2yz²。Jain表示，这些配对有点类似于一个连接着多项式计算器的密码保险柜。用户输入数字，看向最后一位，看保险柜中隐藏的数值能否让整个多项式归零。

为了保证计划的安全，用户不能获知整个过程中任何参数。但是在所有可能的多线性配对候选中，打开保险柜的过程，都透露了计算过程中应该隐藏的信息。

由于多线性配对机制全都有安全性问题，林惠嘉开始探索能否通过约束多线性配对的层数来实现iO。（这样更容易实现安全性）四年前，她想出了如何用30层多线性配对构建iO。接下来几年里，她、沙海和其他研究者逐渐想出了如何只用3层多线性配对来实现iO。

表面上看，这是一个巨大的进步。但有一个问题——从安全的角度来看，3层多项式配对和其他任意层一样不稳固。

研究人员们只知道2层及以下的多线性配对是安全的。林惠嘉与Jain和沙海联手，试图找出如何用2层多线性配对应设构建iO。但是，“我们被困住了很久很久。“林惠嘉这样说。

最终，他们与加州大学圣巴巴拉分校的普拉汉汉·安纳思（Prabhanjan Ananth），区块链项目Concordium的克里斯蒂安·马特（Christian Matt）一起，想出了一个折中方案：既然iO需要三层，但计算机科学家为了安全需要二层，中间是否存在2.5层呢？

研究人员设想了一个系统，其中保险柜上有窗，用户可以看到部分密码的值。这让整个机制不需要隐藏太多信息。为了平衡多线性匹配的能力和二层的安全性，这个机制允许计算高于二阶的多项式，但有一个限制——多项式被隐藏的变量必须不能超过二阶。林惠嘉说：“我们试图不去隐藏那么多。”

图片来源：quanta magazine

但是从不太强的多项式配对到iO，团队还缺少最后一块拼图——一种新型的伪随性数生成器，它能将一串随机的数据转换成扩展成更长，更随机的一串。而这正是Jain，林惠嘉和沙海在新论文中想出来的。

结果是，iO协议最终避免了多项式配对的安全性漏洞。“他们的结果看起来几乎是完美的。”康奈尔大学的拉斐尔·帕斯（Rafael Pass）说。

该方案的安全性基于四个数学假设，这些假设已经被广泛的应用于其他加密方式中。即使是被研究最少的假设——“Learning Parity with Noise“假设——也和20世纪50年代以来一直被研究的问题有关。

很可能只有一种东西能打破新的方案——量子计算机，如果我们能造出真正的量子计算机的话。四个假设中的一个容易受到量子攻击，但过去的几个月里，帕斯和其他研究者分别独立地在论文中得到同一个结果，这一结果提供了一条不同的潜在路径，让iO在量子攻击下也能确保安全。研究人员表示，相较于Jain，林惠嘉和沙海的版本，这些新版本的iO基于不太成熟的安全假设。哈佛大学的博阿兹·巴拉克（Boaz Barak）说：“但它是有可能的。这两种尝试可能在接下来的几年融合，创造一种基于标准安全假设上，能抵御量子攻击的新版iO。

伊沙伊预测，Jain，林惠嘉和沙海的创造可能吸引新的研究者进入该领域，让该方案更加实用并作出一些新的尝试。他说：“一旦你知道某件事原则上是可能的，就会让这个领域的研究者在工作时心理上好受得多。”

在协议（或者是其变体）可用于实际应用之前，计算机科学家还有许多工作要做。但研究人员表示这是意料之中的。帕斯说：“密码学中有很多概念，当它们第一次出来的时候，人们会说：‘这只是纯理论，（它）与实践无关。’然后10年20年后，Google开始实施这些计划。”

巴拉克说，从理论突破到实际可用的协议还有很长一条路要走。“但是你可以想象。或许50年后密码学教科书上会说，‘好吧，这里有一个很简单的iO构造，我们能从中得到其他所有加密方式。’”他说。

原文链接：

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

— THE END —

☞耶鲁大学教授给研究生的一些忠告

☞数学竟然可以如此美丽

☞数学与爱情

☞微积分的发现是人类精神的最高胜利

☞父子同获诺贝尔奖什么的：细数那些从事物理学和数学的一家子

☞大雅之美：数学物理学家心中的十大方程（上）