ObliVM：安全计算编程框架

使用新的方法撰写密码学会议视频分享文章后，虽然点赞和阅读量并没有提升很多，但是根据知友们的反馈，这样做确实可以大幅度提高阅读体验。更开心的是，向知乎反馈后，知乎的工程师们也是大力配合，现在终于支持上传长度不超过60分钟的视频了，撒花庆祝！接下来的视频分享文章中，我会同时在知乎和B站上传翻译视频。知友们可以根据自己的习惯选择在哪个地方观看。

演讲视频简介

本次为大家带来的是2015年安全顶级会议Security and Privacy 2015的演讲视频《ObliVM：安全计算编程框架》，对应的论文是《ObliVM: A Programming Framework for Secure Computation》。

上一篇文章《SoK：安全多方计算通用框架》的视频中，作者调研了9个开源的通用安全计算框架，而ObliVM就是其中的一个。我个人对于“把Alice和Bob作为编程语言的关键词”这一点仍然记忆犹新。这一次，我们就来详细了解一下ObliVM到底是什么。

演讲视频信息

中文字幕视频

演讲视频字幕

（演讲者）大家好，我很高兴能在这里为大家介绍我们的工作：ObliVM，这是一个安全计算的编程框架。这是我和我的队友们一同完成的工作，队友有Xiao Wang，坐在那里的Kartik，还有Yan Huang，还有Elaine Shi。

很高兴自己在前面的一个演讲中为大家充分介绍了什么是安全计算，或安全函数求值。我这里只需给出一个简短的介绍。例如，Sheldon和Amy希望互相确认自己是不是对方的另一半。他们都相信基因匹配的效果。因此，他们可以执行一个分析过程，看看他们是否匹配。一个很关键的安全问题是：他们不想把敏感的基因数据泄露给对方。我在前面已经讲过了，安全计算是这一问题的绝佳解决方案。

我们可以把这个问题抽象成下述形式：给定两个参与方Alice和Bob，以及他们的秘密输入和，他们希望联合计算一个公开函数，得到函数的计算结果。同时，除了计算结果外，涉及两个秘密输入的计算过程不会向对方泄露任何其它信息。这就是安全计算的概念。

大家已经知道，安全计算的解决方案有姚氏乱码电路，还有GMW协议。我们关注什么地方呢？我们的关注点是：如何让安全计算能在实际中得到应用？例如，一个开发者希望开发一个安全计算应用。他们肯定不想把函数写成电路的形式。他们想用C语言、Java语言、或者Python语言编写代码。因此，源程序和安全计算协议之间存在很大的鸿沟。这就是我们ObliVM框架要做的事情。我们的ObliVM是一个工具，可以将源代码转换成实际的安全计算协议。这是ObliVM的框架概览。

这里面最主要的问题是什么？Kartik已经提到，主要问题是开发人员喜欢用Python等语言模型编写代码。幻灯片左侧是开发人员撰写的源程序。但实际上，大多数安全计算协议是在电路模型下实现的。因此，在高层语言程序和电路程序之间存在很大的鸿沟。我们的问题是，如何将左侧的代码转换为右侧的协议？

非常感谢Kartik的讲解，你已经提出了我们工作的出发点。这里的关键挑战是，如何能让动态内存访问过程不泄露信息。

这是一个不太容易解决的挑战。我们的解决方案是：把RAM模型下的问题转换到不经意RAM模型中。不经意的意思是内存访问和指令追踪过程不依赖于秘密输入。这样一来，不经意程序就可以被进一步转换为电路了。我们可以看到，在转换链路中，后一部分相对比较简单，前一部分非常有挑战性。本次讲座主要关注前一部分，解释如何做到这一点。

有一个非常平凡，也不能说非常平凡的解决方案。这个方案于2013年首先提出，基本思想是使用不经意RAM。不经意RAM，又称ORAM，可以把任意程序编译成不经意程序。基于这一思想，我们去年提出了SCVAM框架。此框架可以仿真通用ORAM。可以证明，我们的渐进性能比所有之前的解决方案都要好。这一解决方案是通用的，也很容易实现。但问题在于，这个方案可能不是最高效的。

在过去的几年间，我们观察到研究人员提出了很多定制化安全计算协议。这方面的工作有很多，我实在没办法在幻灯片上把所有相关工作都列出来。这些定制化安全计算协议都很高效，可以这么说，这些协议比我们去年的工作都高效。但问题在于，这些协议的设计成本很高。例如，我们与Nina Taft聊了聊，她是我们的合作方。我们私下针对CCS 2013上面发表的隐私矩阵分解算法进行了讨论。她告诉我们，她们组织了5位研究人员，花费了大约4个月的时间才完成了全部的实现。也就是说，整个过程花费了超过1.5年的研究时间。这里涉及到巨大的工作量。我们的问题是：我们能不能做得更好？我们能否构建一个通用框架，但仍然获得定制化协议的执行效率？这就是我们ObliVM的目标。

我们希望非领域专家，例如非密码学家，可以用它实现一些安全计算协议，同时获得定制化协议的执行效率。

我们如何做到这一点？关键思想是：在ObliVM内部，我们提供很多编程抽象接口。我在幻灯片上具体列举了一些，如不经意数据结构、MapReduce、循环合并等。我后面会介绍其中一个抽象接口。如果想了解更多的细节，请阅读我们的论文。我还想提及的是，Kartik刚刚讲解的GraphSC论文也是一个并行计算编程接口抽象。总之，我们提供了一些编程接口抽象。

我这里想简单介绍一下编程接口抽象到底是什么。我们来看看分布式计算社区。我估计绝大多数人都听说过MapReduce，这是谷歌于2004年在OSDI会议上发表的论文。在这篇论文发表之前，并行计算、或者说分布式计算，是一个很困难的任务。但通过MapReduce，开发者只需要将计算过程编码在Mapper和Reducer框架中。开发者不需要关注分布式计算方法，MapReduce框架会实现整个分布式计算过程。因此，与之前的工作相比，使用MapReduce涉及的开发工作量会非常小。

我们想用与之非常类似的方法解决这一问题。我们希望提供一些抽象接口，允许开发者将计算任务编码在抽象接口中，这样他们就不需要关注底层的密码学原语，但仍然获得相同的计算性能。这就是我们的目标，这就是我们的解决方案。

我们如何对外提供这些编程接口抽象？我们希望实现一个新的语言支持体系。例如，我们想为我们的开发者实现一个新的编程语言。在开发这个语言时，我们脑海中有两个目标。第一个目标是：领域专家或密码学家可以很容易地应用此语言实现不同的编程接口。另一方面，对于非专家来说，他们可能不是特别了解密码学技术，他们可以很容易地使用这些编程语言抽象构建他们自己的应用程序。

结合脑海中的这两个目标，我们的解决方案是构建新的语言特性，支持之前系统未无法支持的功能。我这里列举了一些特性，请大家阅读论文，了解相应的技术细节。后续我们会在幻灯片给出的地址上开源我们的编译器，这样大家可以更好地了解编译器的实现细节。我认为这些特性都很不错。例如，我们可以使用随机类型、虚函数等，从源代码阶段，而不是从后端原语阶段，实现不经意RAM协议。

有了这些编程接口抽象，开发人员该怎么做呢？例如，我们希望实现一个稀疏图算法。我们已经有了编程接口抽象这样一个武器库了。假设我们想要实现稀疏Dijkstra最短距离算法，我们可以选取适当的不经意数据结构，这里要选择不经意堆。随后，我们使用循环合并抽象实现相应的算法。通过使用这些工具，我们实现了3个不同的稀疏图算法。

整个流程好像都走得通，但我们得到了一个超出期望的结果：我们实现的算法从理论角度也得到了突破，所有3个算法的渐进复杂度都比当前最优算法的渐进复杂度低。这个结论令我们感到十分惊讶。如果想了解算法的更多细节，请阅读我们的论文。

开发人员具体该做些什么呢？我在几分钟之前已经向大家许诺过了，我会为大家介绍一个编程接口抽象：循环合并。这是非常细节的内容了。在安全计算中，实现秘密循环是非常有挑战性的工作，因为循环次数本身就会泄露信息。这里我们允许编程人员编写有上界循环次数限制的循环语句。例如，我们允许协议保护循环次数，但我们要求开发人员公开告知循环次数的上限。

这是一个嵌套循环代码。这里有趣的地方在于，第4行到第7行的内部循环中，循环次数上界m并不是外部循环中每次迭代的最大迭代次数上界，而是两层嵌套代码中，内部循环的总执行次数上界。这样我们可以避免重复的执行过程。例如，如果我们按照传统方法给出上界，则总迭代次数是n•m，但这样设置的总迭代次数是n+m。

我们的编译器会分析这段代码，自动将此类形式的代码转换成右下的代码形式。这段代码看起来像是一个状态机，这样就不会为算法引入额外的复杂度了。

应用所有这些技术以后，我们能得到什么呢？我之前已经提到，实现矩阵分解算法涉及的人力开销大约为1年1.5个研究者。如果使用ObliVM呢？结果非常令人惊讶，只需要一天就够了。一个博士研究生只需要一天就可以实现全部功能。

你可能会想，实现结果是否高效？可能自动化的实现结果并不高效。事实上，我们的实现的算法效率要高10到20倍，因此实现结果甚至更高效了。这就是我们现在得到的优化结果。我相信ObliVM对于所有安全计算开发者来说都是一个福音。

我们深入解析一下各个优化点所带来的性能提升情况。我们这里给出的是Dijkstra算法的实现结果。论文中给出了更多的实现结果。虽然我们这里只关注ObliVM的编程语言部分，但实际上ObliVM拥有一个经过深度优化的后端ObliVM-SC。此后端代码也开源了，大家可以访问我们的网站，获取源代码链接。

我们实现了一个当前最优的电路ORAM，此ORAM专门为安全计算进行优化。我们将我们的系统和之前在CCS 2012上公开的最佳结果进行了对比，电路ORAM本身可以为我们带来50倍的性能提升。编程语言和编译器可以为我们带来2500倍的性能提升。我们进一步对后后端的其它部分进行了深度优化，可以在我们的论文中找到相应的技术细节描述。这些深度优化可以为我们带来7倍的性能提升。

总体来说，我们获得了大约100,000倍的性能提升，这是很大的性能提升倍数。

这里给大家一个更直观的方案效率描述。2012年在同一篇论文中，他们在1GB数据集上执行了二分搜索算法。一次单独问询的计算时间大约为12小时。现在情况又怎么样呢？使用我们的ObliVM框架，每次问询的执行时间仅为7.3秒。

我们还将我们的SCVM框架与不安全的解决方案进行了效率对比。也就是说，我们直接在计算机上执行明文程序，从而对比效率。我们计算了效率损失量，效率损失量相对还是可以接受的。对于分布式GWAS，效率损失仅为130倍。我们可以期待，未来这一数字可能会进一步降低。

有很多合作方都与我们合作，ObliVM已经在多个场景下得到了应用。我们刚刚赢得了3月份举办的基因分析竞赛，这是大约2个月前举办的竞赛。未来，我们希望在ObliVM框架的基础上实现更多的密码学计算任务，如同态加密等。

非常感谢大家，这就是我讲座的全部内容了，接下来我可以回答一些问题。

提问者：在演讲开始阶段你给出了一个二分搜索的例子，开发人员应该怎么实现二分搜索？开发人员需要写什么代码？

主讲人：你指的是哪个例子？

提问者：在最开始的地方，你给出了一个二分搜索的例子，那时候你提到…

主讲人：这张图中左侧是开发人员实现循环合并时要编写的代码。你提到了二分搜索的例子，对吧？

提问者：是的。

主讲人：我觉得用二分搜索举例子会比较好。开发人员要做的事情是…我们回到那页幻灯片上。在这里。

提问者：就是这里。

主讲人：这就是开发人员需要编写的代码…我看看这个代码能不能编译通过…是的，可以用我们的ObliVM编译器编译这个程序。编译器会自主处理内存访问过程。

提问者：是的。

主讲人：是的，编译器会识别相应的模块，判断哪些部分要替换为ORAM，哪些部分不需要替换。

提问者：ObliVM是不是有一种潜在使用方法，就是让ObliVM输出C代码，而不是电路，这样我们就可以把任意一个程序输入给ObliVM，使得程序无法被旁路攻击？

主讲人：这是一个非常好的问题。一个非常有趣的事实是，我们的ObliVM编译器输出的是Java代码。

提问者：明白。

主讲人：随后，执行Java代码，会生成一个电路。所以我觉得你提的问题非常好。我认为未来一个很有趣的研究方向是，如何阻止ObliVM编译器遭到旁路攻击。

提问者：好的，谢谢。

主讲人：谢谢你。

主讲人：什么？你可以使用麦克风的。

合作者：我们的编译器没办法被旁路攻击。如果你直接编写类似这样的代码，编译的输出结果是通用ORAM程序。但你也可以调用我们提供的不经意数据结构。我们在不经意数据结构中实现了二分搜索树，如果直接调用不经意数据结构抽象接口，编译时间会减少log(n)倍。

提问者：明白。

合作者：很容易让编译器输出C代码，修改后端编译器即可。比较困难的点在于前端，如何编译得到一个高效的电路。

主持人：感谢Elaine的解释。

主讲人：是的，感谢Elaine。

主持人：再次感谢我们的演讲者。