​iO(1) 为什么我们要研究不可区分混淆？

程序混淆

一个程序的代码中有代码的框架结构、组件间的调用关系、算法思想等信息，有时也还包含一些硬编码的字符，这些硬编码的字符或算法等都可以被看作程序中隐藏的一些秘密信息。显然，软件行业往往并不希望软件中的算法随着软件的售卖而被泄露，也不希望软件被任意修改(例如运用反编译等手段对付费软件进行破解)。程序混淆便可用于解决这一问题(也许有人声称一份写得极为糟糕的代码也能达到类似的效果，但这种做法的有效性无法被严格证明，同时也会增加软件产生 bug 的风险)。

程序混淆(Program Obfuscation)保证了程序中确实能够隐藏某些秘密信息，即使是拥有这个程序并且能够任意运行这个程序的人也无法得知这些秘密信息。

为了实现程序混淆，我们需要有程序混淆器(Program Obfuscator)。一个程序混淆器(我们将其记为 )可以被视为一个特殊的编译器，这个编译器的输入(例如一段代码)对应于某个程序，我们将输入对应的这个程序记为 ，编译器将  编译后会输出一个混淆后的程序，我们将其记为 。我们要求：

1.  、 这两个程序的功能完全一致，记为 。
2. 从实用性的角度出发，、 都应当是高效的。
3.  要尽可能地隐藏  中包含的秘密信息(“尽可能”这个说法十分模糊，接要来我们就开始讨论怎样刻画“尽可能”这个概念)。

程序混淆的安全性定义

密码学常见的安全性的刻画方式有两类：基于模拟的(SIM-based)和基于不可区分的(IND-based)。我们分别对这两种安全性定义进行讨论，前者我们称之为虚拟黑盒混淆(Virtual Black Box Obfuscation, VBBO)，后者我们称之为不可区分混淆(Indistinguishability Obfuscation, iO)。

虚拟黑盒混淆

虚拟黑盒混淆是指，对于一个得到了  的学习者和一个只能对  进行黑盒访问的模拟器，二者的能力是完全一致的。换言之，得到  并没有给学习者带来任何通过黑盒调用无法得到的信息(即使学习者可以研究 的运算步骤，查看计算过程中某些变量的值的变化，设置断点，甚至在运算进行过程中直接修改某些寄存器的值并观察产生的影响……)。虽然这个安全性定义非常强，但是事实上它是无法达成的。比如至少有一项能力是学习者有而模拟器没有的，那就是学习者可以输出一个和  功能一致的程序(这个程序就是 )，而模拟器仅靠对  进行的多项式次黑盒访问根本不可能写出一份和  功能一致的代码。在 2001 年，Barak 等人 最早注意到了这一点并证明了不存在通用的虚拟黑盒混淆(VBBO 和 iO 的定义也是由他们在同一篇文章中提出的)。

不可区分混淆

不可区分混淆是指，对于两个功能完全一致的程序 ，则任何区分器都无法区分  和 。这个安全性的定义直觉上并没有特别强(事实上即使 ，iO 仍然能够存在，但这种情形下 iO 几乎隐藏不了什么信息)，但是在 2007 年，Goldwasser 等人证明了，iO 是有可能被实现的最好的混淆器。为了简述其思想，我们假设 VBBO 是可能存在的，并证明此时 iO 至少和 VBBO 一样安全。对于程序  和 ，显然有 ，于是，根据 iO 的定义，有 。因为混淆不可能凭空产生新的信息，因此  蕴含的信息不会超过 ，即  安全性不低于 ，综上  的安全性也至少和  相当。

不可区分混淆的密码学应用

由于通用 VBBO 的不可实现以及 iO 具有很强的安全性，目前已有大量根据 iO 来构造密码学组件的研究成果，其中最早的是 Sahai 等人  在 2014 年通过 iO 和一些基础的密码学假设(例如单向函数(One-way Function))构造了公钥加密(Public-key Encryption)、数字签名(Digital Signature)、可否认加密(Deniable Encryption)等。综合这些研究成果可以看到，iO 不仅能用于构造我们已经熟知的经典密码学组件，更可以作为桥梁构造大量功能十分强大的"新"密码学组件(其中一部分组件目前只能基于 iO 构造)。

参考文献

 Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (Im)possibility of obfuscating programs. In Advances in Cryptology. CRYPTO 2001, number Im, 2001.

 Shafi Goldwasser and Guy N. Rothblum. On best-possible obfuscation. In TCC, pages 194–213, 2007.

 Amit Sahai and Brent Waters. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. Proc. of STOC 2014. ,2014