格密码学之iO入门（一）：什么是iO（Indistinguishability Obfuscation）

本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。

写在前面

千呼万唤始出来，我们终于要讲到格密码学最令人激动的话题——了！

要想知道Indistinguishability Obfuscation是什么，我们不妨先来看一看Obfuscation是什么。

我们都知道，作为程序员，最宝贵的自然是我们写的代码了。一旦我们写的源码被人看到了，那么基本上花的心血和知识产权都被人一览无余。假如我们写了个画面非常精美，性能也很好的一款游戏，并且卖出去也买的很好，但是一卖出去就被人给反编译拿到源码了的话，那么第二年也许就会有无数第三方的游戏开发者直接copy我们的技术，并且做出跟我们差不多的游戏。

那么为了让我们写的程序卖出去之后不被人能够发现到底背后藏了些什么秘密（比如说非常强大的算法，或者是很聪明的数据结构等等），我们在导出程序准备卖出去之前可以采取一些手段来混淆（obfuscate）我们写的程序，在维持原本相同的功能性的同时，即使我们写的程序被人拿到了，别人也没有办法非常有效的把它还原成源代码，把我们辛辛苦苦积累的秘密全部拿走。

一般来说，我们现在会使用的程序混淆方法有两种。

在我们写程序的时候，往往都会根据实际的使用场景给变量或者函数命名。比如说一个计算下一秒展示的图像的函数，我们可以起名为calculate_next_frame()。一个代表UI控制器的变量，我们可以起名为ui_controller，等等。如果被别人看到了一段这样的代码，那么别人一下子就可以看明白这段程序到底在做什么。

于是，为了防止让我们的程序本身给外人提供太多的信息（以及使得程序的运转效率变得更高），我们会在导出程序的时候，把这些标注性的符号（symbols）统统的摘除掉。比较简单的实现方法是直接全文替换关键词，比如说把整段代码中所有的ui_controller全部替换成a0123456，这样一来，程序的symbols本身就无法暴露关于程序运转的内容了。

这一类的代码混淆器（Obfuscator）当今市面上很多，比如webpack就会在导出JavaScript至production的时候，自动的使用minify的功能来简化（并且混淆）JS代码。在我们编译Java与Kotlin程序（如安卓开发）的时候，同样我们可以使用ProGuard来进行代码的缩减和混淆化操作。

第二种方法更加简单：我们直接输出编译过后的代码（可执行文件），这样别人就没法直接打开这个文件看到原本的代码了。

为什么编译之后的代码不会暴露出原本的源码信息呢？这是因为编译器在把人可以看的懂的源代码转换成电脑可以看得懂的机器码的这个过程中，就等于是把我们上面描述过的symbols全部去除了。同时，由于现代的Compiler都可以通过大量的代码优化（Optimization），比如Loop Unrolling（循环展开）等等的方法来改变代码的结构，使得最后生成的机器码和我们原本写的代码大相径庭。虽然说编译器的主要任务并不是用于混淆我们的代码，但是它通过把我们熟悉的代码转换成我们比较陌生的机器码的形式，变相的让我们对于同样的程序变得”不认识“了。

所以当别人看到我们发布的可执行文件中的机器码的时候，只会是一脸懵逼的啦。

比较可惜的是，我们刚刚提到的当今常用的这两种方法，其实并不能作为真正意义上的混淆。

这是为什么呢？这是因为我们在做的事情，在密码学的定义上是非常脆弱的。这就像是上世纪二战的时候，我们通过各种各样的暗号以及暗码来加密通讯的电报，然后在另一头通过某一本小说或者报纸来解读出原文一样。整个系统的目的就在我们使用各种乱码一样的名字，错综复杂的逻辑结构（比如循环展开），以及不同的表述方式（把C变成汇编），尽可能使得看到我们最终混淆输出的人无法从输出中有效的提取和源代码有关的信息来。

char*M,A,Z,E=40,J[40],T[40];
main(C)
{
  for(*J=A=scanf(M="%d",&C);
  --
  E;
  J[E]=T
  [E]=E)   
  printf("._");  
  for(;(A-=Z=!Z) || (printf("\n|") , A =39 ,C--) ;
  Z
  ||printf(M))M[Z]=Z[A-(E=A[J-Z])
  &&!C
  & A ==T[A]
  |6<<27<rand()
  ||!C&!Z?J[T[E]=T[A]]=E,
  J[T[A]=A-Z]=A,"_.":" |"];
}

了解完我们通常听说的程序混淆之后，接下来我们就来看真正的密码学中对于Obfuscation的定义：Virtual Black Box Obfuscation，简称VBB。

早在上个世纪的时候，大家就开始畅想，如果我们真的可以实现VBB Obfuscation的话，那么我们可以用这个技术来实现什么应用呢？

最简单的应用就是我们之前描述的程序混淆。我们在开发新的应用程序的时候，只需要在输出代码之前通过VBB来混淆一下整个程序，那么我们就可以确保购买软件的人永远都无法反向破解出任何和我们应用中有关的信息了！这对于一些拥有专利算法的公司（比如图像处理、机器学习等等）是一个非常大的帮助，因为保护了他们的代码就等于守住了他们所有的知识产权。

其次，基于VBB还有一个比较有趣的应用，这是上个世纪的一个偶然的想法，变相的打开了Obfuscation领域研究的大门：使用VBB来实现公钥加密。

我们都知道， 在Diffie-Hellman出现之前（包括之后），我们只拥有一系列可靠的对称加密系统，比如上世纪的DES，以及现在的AES。对称加密系统的问题在于，如果我们想要与另一方进行加密通讯，那么通讯的双方需要实现约定好使用的密钥（encryption key）。然而，Diffie-Hellman一类的密钥交换又基于不让人那么放心的DLog（离散对数）问题。这让不少人都在探讨，还有没有别的方法可以让通讯的另一方变相的“知道”我们选择的密钥。

当然，我们畅想了那么久VBB的概念，肯定会想到：为什么到现在我们还没有如此简单的实现高级的密码学应用呢？这其实是因为，在VBB的概念提出不久后，很快就被泼了一盆冷水。

在2001年的时候，Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang七位大牛真正意义上的对于Obfuscation这一概念做了系统性的研究，并且发表了一篇文章（简称【BGI+01】）：On the (Im)possibility of Obfuscating Programs。

【BGI+01】一篇文章系统性的分析了VBB Obfuscation，提出了一些重要的问题。

首先，我们需要知道到底什么样的程序/电路才适合Obfuscation。如果一个程序的功能性本身就是print出自己的源代码，或者做一些非常有规律的事情，那么我们完全都不需要看这个程序本身，光是看这个程序的输出，就可以知道这到底是一个什么样的程序。对于这一类的程序/电路，我们称作为Learnable Program，因为我们可以从程序的输出本身了解到程序本身的逻辑结构。想必我们也明白了，Learnable Program其实并没有什么Obfuscation的必要，因为就算不是VBB，而是真的把这个程序装在一个黑盒中，我们也可以很简单的通过它的输出来判断出程序的结构。真正需要Obfuscation的程序，应该需要符合unlearnable的要求，也就代表我们无法从一个程序的输出中得到任何与这个程序有关的信息。

一看到这个定义，就有点密码学的味道了。没错，密码学中常见的加密算法，PRF等等，都是非常适合Obfuscate的例子。比如说我们上文提到的PKE算法，我们等于是Obfuscate了一个嵌入了私钥的加密算法。因为输出的加密密文符合加密算法本身的语义安全属性，所以我们无法从密文中得之任何和程序有关的信息。

1. 首先，我们需要满足Functionality Preserving（保持功能性），即被混淆的程序需要和混淆之前一样，保持完全一样的功能性。

2. 其次就是Indistinguishability，即不可区分性啦。对于两个功能性完全一样的程序，即，就算这两个程序的实现方法完全不同，我们也无法有效的分辨他们的混淆结果。换句话来说的话，如果有两个相同功能的程序，而我们看到了只看到了一个未知的结果的话，我们无法分辨到底是哪个程序被混淆了。

3. 最后一点是Efficiency，即高效率。这一条属性指出了，的输出一定不能太大，最多是原本程序大小的多项式倍数，即。为什么需要这一条约束呢？这是因为如果没有这一条效率的约束，整个混淆操作就失去了实际使用的意义。我们甚至可以构造出非常简单的结构：假如一个程序的输入是位而输出是位，那我们只需要输出一个大小的表格，把所有输入值和输出值一一对应。这样一个巨大的表格也是不可区分混淆了，因为只要功能性不变，那么输入和输出的一一对应也不会改变！为了排除这一类无意义的构造，我们需要规定一个理想的算法输出的程序大小相比起输入的程序大小来说不会变得过大。

虽然我们知道VBB已经是不可能实现了，不过通过iO，我们仍然可以非常完美的混淆一个程序。

在我们进行软件开发的时候，还有一件非常头疼的事情，那就是软件试用版的开发。假如我们在写一个游戏，我们已经把整个游戏写好了，但是想开放一部分的游戏免费给玩家试用，这个时候我们面临两种选择：

1. 第一种方案，就是我们把整个游戏复制一份，然后把收费版的功能和逻辑全部都一一删除掉，最后就留下免费试用的部分并且发布出去。这种方案虽然是最好的，但是整个过程会花费大量的精力，最后生成的“阉割”版本的游戏甚至可能还会有未知的bug需要我们来修补。

2. 第二种方案则非常简单，我们直接在软件内部设置一组feature flags（功能开关），可以选择性的打开或者关闭一部分的功能。我们可以在试用版的软件中把收费的功能对应的flag都关闭，这样整个程序就不会运行任何付费的功能了。这种方案相对来说比较常见，但是问题在于，一旦黑客破解了我们的程序，然后把收费功能打开的话，那么这些功能就一览无余了。

显然相比起来，第二种方案是实现起来最简单的，但是有没有办法可以让我们获得和第一种方案一样的安全性呢？

1. 第一条线是基于Lin的一系列发现而延续下去的一条线。直到现在，最新的研究成果为Jain-Lin-Sahai的【JLS20】，可以成功的使用双线性配对，LWE，LPN，与OWF这四条假设成功的构造出来。这也就是说，我们已经可以基于已知的构造来实现了！
2. 第二条线也很有意思，是Brakerski-Dottling-Garg-Malavolta在去年的【BDGM19】与【BDGM20】相继提出的新的框架：split-FHE。通过结合全同态加密FHE（如GSW）以及线性同态加密LHE（如Damgård-Jurik），通过巧妙的circular-security假设，可以使得密文在两个加密体系中来回周旋，最终得出来！大概的思路非常的巧妙：我们把需要混淆的程序使用FHE加密，然后同态的计算这个程序，最后通过一个特殊的解密方法得到计算的结果。这样一来，我们等于是在用FHE的安全性来实现的不可区分性。

写在最后

这一期，我们详细的了解了Obfuscation是什么，以及VBB的假设是什么样的。在了解了VBB Impossibility Result之后，我们学习了的定义，以及拥有之后，我们可以做些什么。在最后，我们快速的过了一遍为了实现近些年在学术圈的发展。