ACM通信
研究突出了
技术视角:软件混淆的突破
查看所附文件，请访问doi.acm.org/10.1145/2902313
数千年来，密码学一直是“秘密书写”的同义词，双方使用一些共享的密钥或方法来交流机密信息。但从20世纪70年代开始，新的密码概念和应用出现了爆炸式增长。这些包括公钥加密技术双方通过公开渠道进行机密沟通，安全功能评价联合计算私人输入的函数(如选举或拍卖的结果)，但不透露它们，零知识证明在不透露任何其他信息的情况下证明一个命题是正确的，完全同态加密对加密数据的计算，以及更多。
这些概念看起来如此矛盾，甚至让这些密码学先驱感到惊讶想象它们是可以实现的!一个根据他们的写作，似乎这些发明家的思维过程中至少有一部分涉及以下心理实验:说服自己这些美妙的物体实际上可以实现并不太难，如果我们有一个黑盒计算一些函数，而每个人都可以使用盒子从输入中计算输出，但不能理解它的内部工作。用詹姆斯·埃利斯的话说，b“我们可以把我们的(加密函数)看作一个查找表，其中包含每个可能输入值的一个输出值。”他们希望能够通过使用迪菲和赫尔曼所称的“单向编译器”来模拟这样一个程序，这种编译器将一个容易理解的高级语言程序转换成一个无法理解的机器语言程序。c
这样的编译器被称为软件模糊处理，尽管它为我们希望实现的加密工具提供了指路明灯，但在许多年之后，关于这个概念的大多数实践和理论结果都已经得到了负的。混淆过去和现在仍然用于保护源代码中的知识产权和其他秘密，但是还没有发现能够抵抗真正坚定的攻击者的实用方案。在理论方面，在2001年，我和我的合著者证明了模糊化最自然的概念，被称为“虚拟黑盒”模糊化，是不可能的才能实现。d我们留下了一个“小”漏洞，指出它不排除一个更弱的概念，即“难以区分模糊化”(ininguishability confusion)或IO。然而，至少对我来说，IO这个概念似乎也是不可能实现的，即使它是可以实现的，它似乎也不是很有用。下面Garg等人的论文证明了我的第一项估计可能是错误的，第二项肯定是错误的。
在这项了不起的工作中，作者构建了一个Diffie和Hellman所设想的类型的“单向编译器”。这是一种改造程序的方法P成一个项目问这在功能上是等价的，在这个意义上它会产生相同的输出P但它是“不可理解的”，因为它满足这个IO条件。编译器本身与所有以前的混淆器都非常不同。它基于这些作者中的一部分人的另一篇突破性论文，e他构建了一个被称为"加密多线性映射"的对象他们把这个和巴林顿的结果结合起来f它最初出现在电路下界的环境中。产生的编译器可以被认为有点类似于转换程序P变成了一个拼成的魔方如果你解释输入x作为应用于立方体的一系列旋转，最终的图案将传递输出P（x)．但是你不能从中学到任何其他信息。
本文的第二个贡献是展示了IO的这个看似薄弱的概念实际上足够强大，可以获得一些最令人兴奋的混淆应用程序。这在许多后续工作中得到了极大的扩展，这些工作将IO确立为一种“加密主工具”，可以产生许多其他应用程序。
本文开启了比关闭更多的研究方向。首先，虽然作者为其结构的安全性提供了一些证据，但这并不真正令人满意，而将IO建立在更坚实的基础上是一个关键的研究目标。而且，目前这种结构非常不实用，即使是最简单的程序也会遭到巨大的破坏。这两种以及更多的东西现在都是深入研究的对象。对于密码学来说，这确实是一个激动人心的时代。
脚注
a.事实上，当拉尔夫·梅克尔(Ralph Merkle)与惠特·迪菲(Whit Diffie)、马丁·赫尔曼(Martin Hellman)以及英国机构CESG的詹姆斯·埃力斯(James Ellis)一起，是最早构想出公钥加密想法的人之一时，他将自己的工作提交给了ACM通信，他指出，他能找到的关于这个问题的唯一参考文献是在科幻小说中。
b。j·埃利斯。安全的非秘密数字加密的可能性。CESG报告1970年1月,
c. W.迪菲和M.E.赫尔曼。密码学的新方向。IEEE反式。信息理论22， 6(1976)， 644654。
d. B.巴拉克等人。混淆程序的(不)可能性。密码学的发展。施普林格柏林海德堡，2001,118。同时,JACM2012.
e. S. Garg, C. Gentry和S. Halevi。理想格中的候选多线性映射。欧洲地穴7881(2013)，117。
f。d .巴林顿。有界宽度多项式大小的分支程序能够准确地识别NC1中的这些语言。j .第一版。系统。Sci 38。， 1(1989)， 150164。
数字图书馆是由计算机协会出版的。版权所有©2016 ACM股份有限公司
没有发现记录