四个假设论证“不可区分混淆”存在性，华人科学家触摸“皇冠上的明珠”

  • 2020 年 11 月 25 日
  • AI

作者 | 蒋宝尚
编辑 | 青暮 
在密码学中,一直存在一种黑科技般的概念：Indistinguishability Obfuscation。中文翻译为不可区分混淆，简称为iO。 
iO是否存在一直是个迷，学者们为了论证它也打了非常多的“架”。这个概念（iO）又称为Crypto-complete（密码学完备）的，如果它真的存在，那么就可以基于IO构建出几乎所有的密码学构造，包括但不限于公钥加密、函数加密、数字水印…….
此概念自美国加州大学洛杉矶分校的Sahai教授及其合作者们提出之后，有人狂热，有人鄙夷。有学者称：“随着时间的推移，相信它存在的狂热分子越来越少了。”
iO的出现最初是为了保护软件不被破解。其基本思想是：将程序转换为一种称为多线性拼图的游戏（multilinear jigsaw puzzle），从而将混淆技术的安全性转化为一类与格（lattice）有关的数学难题。
换句话说，其利用的原理是：如果你使用两个同等的程序 A 和 B（如把相同值输入到 A 或 B 里去产生相同的输入）计算得到 O(A)=P 和 O(B)=P，则在无法进入程序 A 或 B 的情况下，则在计算上分辨 P 来自于 A 还是 B 是不可行的。
可以看出，这个问题在理论上很容易定义，但是符合人们期望的混淆技术在理论上是否存在还是一个很困难的问题。
8月18日，来自华盛顿大学和加利福尼亚大学的三位研究者发表了一篇名为“Indistinguishability Obfuscation from Well-Founded Assumptions”的文章，在文章中作者用“标准”的安全假设构建了IO。这三位作者中，Huijia Lin本业毕业于浙江大学，2011年在康奈尔大学获得博士学位，目前是华盛顿大学的副教授。
具体而言，他们证明了四个假设：
1.关于素数阶为p=O(2^λ)的非对称双线性群的SXDH假设，
2.在Zp上的LWE假设，次指数模数噪声（subexponential modulus-to-noise ratio）比为2^(ke)。
3.在Zp上的LPN假设，且具有多项式的LPN样本和错误率1/L^δ。
4.Boolean PRG在NC^0中的存在性。
有了上述四个假设，那么IO对于所有的多项式逻辑线路（polynomialsize circuits）都是存在的。
此篇论文的作者之一在接受采访中表示，新的研究结果应该会让IO怀疑论者安静下来。“现在，人们将不再怀疑IO的存在。”

1

IO：皇冠上的明珠

几十年来。计算机科学家一直在思考，是否存在一种方法，能够安全的、全方位的混淆计算机程序呢？为了不让使用计算机程序的用户弄清楚程序原理（反编译），科学家们做了很多努力。
康奈尔大学Rafael Pass 称这个问题为“密码学皇冠上的明珠”，“一旦找到通用的方法，你就会得到一切”。
而当前程序混淆有两种方式，第一种是全文替换关键词，把整段代码中所有的“命名”全部替换成数字（例如b4452)；第二种是直接输出编译过后的代码（可执行文件），这样别人就没法直接打开这个文件看到原本的代码了。
这两种方式的目的都是在导出程序的时候，把标注性的符号（symbols）摘除掉。从而达到不暴露原本源码信息的效果。
但比较可惜的是，当今常用的这两种方法，其实并不能作为真正意义上的混淆。
文章链接：//zhuanlan.zhihu.com/p/270364254?utm_source=qq
知乎网友@Steven Yue一篇介绍介绍IO的时候，指出：”在密码学的定义上是非常脆弱的。这就像是上世纪二战的时候，我们通过各种各样的暗号以及暗码来加密通讯的电报，然后在另一头通过某一本小说或者报纸来解读出原文一样。整个系统的目的就在我们使用各种乱码一样的名字，错综复杂的逻辑结构（比如循环展开），以及不同的表述方式（把C变成汇编），尽可能使得看到我们最终混淆输出的人无法从输出中有效的提取和源代码有关的信息来。”

          
比如说上述的C混淆代码，虽然说看似一团乱码，我们作为人类难以去理解这串代码到底在做什么。但是如果我们一旦把这样的代码放入编译器中，去分析整个编程语言的语法结构，把每一行的指令做的事情都归纳出来的话，那么就能看出些端倪来了。
一开始，科学家们采用虚拟黑盒混淆（Virtual Black Box Obfuscation），这个机制可以简单理解为输入和输出之间有一个摸不透的黑盒，此黑盒保护输出无法反推输入。但随后在2001年的时候被证明通用的黑盒混淆是绝对不可能的。
此后，这一方向就分为了两派，一派是继续研究黑盒混淆，另一派则是研究则研究Indistinguishability Obfuscation。

2

研究历程

2013年Sahai联合其他五位学者发布文章“Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits”，提出IO协议，其基本思想正如前面提到的“把一个程序转换为一种称为多线性拼图的游戏（multilinear jigsaw puzzle），从而将混淆技术的安全性转化为一类与格（lattice）有关的数学难题。”
这一混淆技术从概念上来看，具备了黑箱混淆器的大多数特性。当时也被称为一种突破，并引发了数十篇后续论文。但在提出的几年内，已遭受了领域内一大批专家（包括提出者）的第一轮攻击。
后来有研究者证明：在混淆过程，使用多线性映射是不安全的。这时候IO是否存在的质疑声又甚嚣尘上。
2016年，在本科毕业于浙江大学，现在是华盛顿大学副教授的Huijia Lin，开始研究有可能减少对多线性配对（Multilinear maps）的需求，从而绕过IO机制的弱点。
确实，多线性配对存在致命的缺点。多线性配对本质上只是用多项式计算的一种方式。它由数字和变量之间的和与乘积组成，如3xy+2yz^2。这些映射需要一个类似多项式计算器的东西，连接到一个包含变量值的“秘密储物柜系统”。用户在机器上输入一个机器接受的多项式时，可以查看最后一个储物柜。从而找出隐藏的值是否使多项式的值为0。因此，打开最后一个“储物柜”的过程中，透露了本应隐藏的计算信息。
接下来几年中，她发现，减少使用多线性配对确是可行！紧接着，她把多线性配对的维度（层数）降到了5层。同在2017年的时候，她与Tessaro在中成功的把这一要求降到了3层。这也就是说，只要我们拥有一个三线性配对（Trilinear Map）的构造，就可以IO。
但是，这时候又有学者质疑：从论文上看，这似乎是一个巨大的进步，但是从安全的角度来看，3次好像还是差点意思。
于是，Huijia Lin 与 Jain以及Sahai联手探索2次多线匹配的方法。但是研究过程似乎陷入了沉默之中，久久找不到方向。
后来另一位研究区块链的学者Christian Matt提出了一种折中的方法，由于IO似乎需要3次，但计算机科学家只有2次，是否有一种介于两者之间的东西？2.5次？
后来Huijia Lin也考虑到，这些只用2.5次的“混合储物柜”系统可以安全地建造。.基于这种并不需要强大的多线性配对思想，Huijia Lin和她的团队发明了一种新型的伪随机性生成器。此随机生成器可以将一串随机比特扩展成更长的字符串，其随机性足以愚弄计算机。
以上就是Jain、Lin和Sahai在他们的新论文中想出的方法。另外，论文中的方案依赖于四个数学假设，这些假设在其他密码学环境中已经有了广泛应用。即使是研究最少的假设—LWE假设（learning parity with noise），在20世纪50年代就有了相关研究。
但是，虽然证明了iO存在性，但仍然有一样东西能够破坏所有的美好：量子计算机。如果量子计算机建成了，那么四个假设就很容易受到量子攻击，IO的理论就会受到威胁。
另外，有三篇独立的论文也提供了一条不同的通往IO的潜在途径，即使面对量子攻击也可能是安全的。研究人员称：“此版本的IO依赖于不那么确定的安全假设”。

参考资料：
//www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/

点击阅读原文，直达ICLR小组！

VirMach 便宜 VPS

QNews

QNews