USENIX 2019 - 大规模数据下的移动端隐私联系人发现

演讲视频简介

连续好几个月都在整理2012年BIU密码学冬令营的内容，相信很多对格密码学兴趣不大的知友看的都有些不耐烦了。我们在中间穿插一个新的演讲视频吧！今天为知友们带来的是USENIX 2019中《Mobile Private Contact Discovery at Scale》的演讲视频。

隐私联系人发现（Private Contact Discovery）是隐私集合求交（Private Set Intersection）的重要应用场景，而移动端隐私联系人发现又是移动端应用程序经常具备的功能，具有重要的研究意义和应用需求。然而，在移动端使用隐私集合求交实现隐私联系人发现需要解决两个核心问题：计算效率问题、通信量问题，而通信量过大又是影响移动端应用的最主要瓶颈。为解决此问题，学者们专门提出了新的隐私集合求交概念：移动端隐私集合求交（Mobile Private Set Intersection）。而这篇论文的主要内容就是移动端隐私集合求交的深度优化。

在此领域有着突出贡献的作者之一就在知乎上，也就是

老师。现在刘健老师在浙江大学网络空间安全学院任教，正在招收对安全多方计算、可信计算、隐私保护机器学习等领域感兴趣的硕士生和博士生。欢迎有志向攻读博士学位、硕士学位的同学联系刘健老师。

这个视频主要是

同学听译的，我主要进行了内容的校对，并制作了时间轴。峰青同学现在在西安电子科技大学就读，对PSI等领域感兴趣的知友也欢迎和峰青同学交流。

演讲视频信息

演讲视频字幕

大家早上好，很荣幸能在这里展示我们与格拉茨技术大学联合完成的研究工作，此工作名为：移动端隐私联系人发现。

首先，为了方便大家理解，我们先简单介绍一下什么是移动端隐私联系人发现。当你在手机上安装了一个通讯应用程序，如WhatsApps时，此应用程序要做的第一件事就是检查你的通讯录，看看你的通讯录里面有哪些联系人也同样使用了他们的服务。为了实现这一功能，应用程序当然可以直接告诉服务提供商你的通讯录中有哪些用户。服务提供商随后可以告诉你，这些用户里面有哪些用户也在使用他们的服务。

这就引出了我的报告想讲解的第一个观点。我们研究了应用程序在实际中是如何实现移动端联系人发现这一功能，为什么这些实现方法存在一些严重的隐私问题。从隐私保护角度考虑，我们建议部署非平衡隐私集合求交协议，替代这些不安全的方法。由于实际应用场景对协议的效率有非常高的要求，我会为大家介绍如何优化协议的基本模块，使协议在大规模数据下也能获得优异性能。最后，我想向大家展示，为安全计算协议编写本地代码所带来的好处。本地代码不仅能大幅提高服务器端的性能，也能提高移动端的性能。

我们首先介绍移动端联系人发现中的隐私问题。必须意识到，使用我在一开始描述的简单方法，基本上意味着会泄漏你的整个社交图谱。

你可能会问，谁会在意我的社交图谱呢，我只是个无趣的博士生而已。但是，想象一下，如果你是一名记者，你正在与一个有着极高影响力的举报人进行沟通，举报人持有机密信息源。服务提供商或任何类型的监视服务很可能会对此举报人的社交信息非常感兴趣。我们对当前使用的方法进行了评估，并改进了现有的方案。

我们工作的主要贡献如下。首先，我们对安全移动通讯应用程序进行了调研。结果表明，现有安全移动通讯应用程序均未在联系人发现功能上提供适当的隐私保护。

为此，我们优化了基于不经意伪随机函数的非平衡隐私集合求交协议，应用布谷鸟过滤器压缩数据、应用新型不经意传输预计算技术和更高效的伪随机函数。我们的协议甚至可以抵御恶意客户端的攻击，这对移动端联系人发现来说非常重要，因为从原理上讲，每个客户端都能篡改并运行篡改后的通讯应用程序。

我们还用本地C/C++实现了这些协议。本地代码使用了新的ARMv8-A指令集，在硬件层面加速密码学运算和矢量运算，这使得乱码电路的求值速度提高了1000倍。我们把实现代码放入了单个安卓客户端，执行大规模数据下的性能基准测试。测试表明，即使对于包含超过2.5亿个用户信息的数据库，当客户端与服务器端应用真实的LTE建立连接，协议的在线阶段也仅花费大约5秒钟。

先来讲讲调研结果。我们调研的移动通讯应用程序是安全的，不过安全原因是它们使用了端到端加密技术。我们使用了不同的分析技术来检查这些应用程序是如何实现联系人发现的，以下是结果。

大家可以看到，很多应用程序实际上使用了我在一开始描述的简单解决方案。

例如，WhatsApp在其合规信息中是这样描述的：在符合应用程序法律约束的条件下，您将定期向WhatsApp提供您通讯录中WhatsApp客户和其他用户的手机号码。

最棒的是，有些应用程序使用的技术是朴素哈希协议，客户端只向服务提供商发送电话号码的哈希结果。不幸的是，几乎可以认为这种技术也是不安全的。由于电话号码的熵值很低，朴素哈希方法很容易遭受字典攻击。

由于这些方法是不安全的，我们建议部署隐私集合求交协议，简称PSI。一般来说，PSI协议是可证明安全的密码协议。它允许双方计算输入集合的交集，协议不会泄露除交集以外的其他任何信息。

然而，在移动端联系人发现场景中，大多数PSI协议的问题是：协议的在线阶段，即计算交集阶段，其通信复杂度与两个输入集合的大小成线性关系。在移动联系人发现场景中，服务器端数据库可能有数百万甚至数十亿个数据条目，而一般假设客户端只有大约1000个联系人。这使得协议的通信复杂度极高而无法应用。

幸运的是，非平衡PSI协议适用于一个输入集合比另一个输入集合大得多的场景。非平衡PSI协议在线阶段的通信复杂度仅与客户端的输入集合大小成线性关系。非平衡PSI协议将大部分通信复杂度转移到协议建立阶段，而协议建立阶段可以在实际计算之前的任意时间点上运行，通常只引入一次性的开销。

我们接下来介绍非平衡PSI的相关工作，非平衡PSI协议可以分为三个协议族。

第一个协议族是基于全同态加密的非平衡PSI。此类协议引入的通信量是最低的。然而，本文考虑的是服务器端数据规模极大的场景。如果在此场景下使用，服务提供商每天需要大约3000万核心小时的开销，略显昂贵。

第二个协议族是将隐私信息检索与PSI相结合的协议。但是，使用这种协议需要假设存在多个不共谋的服务器。在两服务器版本中，外部服务器需存储用户数据库的完整副本。我们希望避免这种情况。

最后一个协议族来自于Kiss等人的工作。他们指出，多数已有的安全两方PSI协议都可以改为预计算协议。这使得这些协议可以变为非平衡PSI协议。这些协议中，有些是纯粹基于公钥密码学的，有些是基于不经意伪随机函数求值的。

我们仔细研究了这些协议中的其中两个协议，通过简单地使用恶意安全的不经意传输协议，就可以使协议抵抗恶意客户端的攻击。其中一个协议对Naor-Reingold的伪随机函数进行了不经意求值，另一个协议对乱码AES电路求值。之所以很容易将这些协议修改为能够抵御恶意客户端攻击的原因是，这些协议中，客户端唯一发送的消息是通过不经意传输发送的。

为了让大家了解这两个协议是如何工作的，我们分阶段快速介绍一下这两个协议。协议的第一个阶段是基础阶段，此阶段的复杂度与输入完全无关。此阶段主要由不经意传输预计算构成。服务器在该阶段也生成一个密钥。在需要计算乱码电路的协议中，服务器还会在该阶段构建和传输待求值的乱码电路。

接下来是协议建立阶段。服务器对其数据库中的所有联系人信息进行加密，并将加密结果放入概率性数据结构中，方便高效完成存在性检测。我们在本文中使用的概率性数据结构为布谷鸟过滤器，服务器端向客户端发送布谷鸟过滤器，客户端存储此布谷鸟过滤器。

最后是在线阶段。客户端和服务器对不经意伪随机函数求值。客户端不经意地获得用服务器密钥加密的客户端地址簿条目。随后，客户端验证加密结果是否存在于布谷鸟过滤器中。

我们使用了前面介绍的基于不经意伪随机函数的PSI协议，详细研究了每一个基础模块，尽可能对协议性能进行优化。我现在快速为大家介绍我们在协议级别上所完成的两个重要优化点。这些优化点也可能为其他应用领域的性能优化带来帮助。

第一种优化是一种简单而有效的压缩技术。使用布谷鸟过滤器可以更有效地表示服务器端的数据库。大家可能不知道布谷鸟过滤器，它的效率很高，可以代替著名的布隆过滤器。与此同时，你可以很容易地从布谷鸟过滤器中删除一个元素。从数据结构的角度来看，它与布隆过滤器的主要区别是，每个桶内可以存储多个条目，桶中存储的元素也不是单比特值，而是短哈希值，也称这些短哈希值为指纹或标签。

由于某种原因，在以前的所有工作中，服务器都需要完整传输所有的哈希桶。哪怕哈希桶中未填充元素，也需要传输。我们在本文的协议中建议，将布谷鸟过滤器拆分为一个位图，指示哪个位置的哈希桶填充了元素，并单独给出一个填充内容的标签列表。这一方法可以进一步压缩布谷鸟过滤器，压缩率约等于布谷鸟过滤器的负载因子。

注：负载因子指布谷鸟过滤器已填充元素数量占总共可填充元素数量的占比。

在实际中，服务器端永远不会传输一个填满元素的过滤器，这是因为会有很多新用户在服务端注册，后续需进一步向布谷鸟过滤器填充元素。因此，这一方法会压缩布鲁鸟过滤器，降低通信开销。论文中还描述了如何根据桶大小和标签长度合理设置布谷鸟过滤器的参数，使整个协议的失效概率是可忽略的。我们还描述了如何高效地更新布谷鸟过滤器，与以前的工作相比，通信量节省了4.3倍。

这里我们快速推荐一篇文献。在得到这些结果后，我们看到去年有其他团队提出了一个新的过滤器：莫顿过滤器，基本思想是把我们的压缩技术与进一步的优化方法结合起来。如果你要设计新的协议，可能会用到莫顿过滤器。

在用乱码电路实现OPRF的协议中，我们替换了AES的伪随机函数，进一步提高性能。之所以能提高性能，原因是乱码电路可以通过FreeXOR技术进行优化，这使得电路设计的成本指标发生了变化。我们现在希望尽可能少地使用AND门，而不太关心XOR门的数量，这就是LowMC技术发挥作用的地方。LowMC是一种高度参数化的分组密码，是专门为安全多方计算和全同态加密的应用程序设计的分组密码。LowMC允许我们根据新的电路设计成本指标调整各种参数。在128位安全性的联系人发现的场景中，可以根据不同的成本指标选择不同的参数。结果表明，使用LowMC的通信开销要比使用AES少8.2倍。

下一步，我们实现了所有的协议。我们不仅希望在协议层面上优化，还希望在实现层面上优化PSI。为此，我们是用本地C/C++实现的协议。代码现在是开源的，大家可以随意使用。

在本地实现方面，我们在两个地方使用了新的ARMv8-A指令集。

一方面，为实现恶意安全的不经意传输拓展协议，我们使用了Peter Rindal的libOTe库。然而，libOTe库的大量性能优化针对的都是x86体系结构，我们用ARM等效指令替换了特定的x86硬件指令。同时，客户端指令的计算结果仍然与服务器端指令的计算结果相兼容。

另一方面，在实现乱码电路协议时，我们知道，由于AES有本地指令集加速，固定密钥AES乱码方案可以有极大的性能提升，而近期Intel CPU大多都提供AES本地指令集。由于ARMv8体系结构现在也包含了加密扩展指令集，因此我们现在也可以在移动设备中使用此类指令集。与标准的软件实现相比，使用此类指令集的性能可以提高约35倍。

我们还可以利用ARM-NEON指令集高效操作128位寄存器，这使得在乱码电路协议中，我们可以很方便地操作128位长的导线标签。

总的来说，与之前工作中使用Java的实现相比，我们的乱码电路求值速度快了1000倍。

为了证明我们的协议的实用性，我们进行了一些大规模数据下的PSI协议性能测试。实验设置如下所示。

客户端是谷歌Pixel 2智能手机，PSI服务器是一台商用笔记本电脑。在网络方面，我们使用真实的Wi-Fi连接，配置如幻灯片所示。

我们还使用了真实的LTE连接。要是在德国用LTE进行大规模数据下的实验，没准做几个实验后我们就得宣布破产了。但在奥地利实验的话，我们还不至于破产。随便吐个槽，别当真。

在客户端包含1000个联系人的情况下，我们测试了基本阶段和在线阶段的性能开销。可以看到，我们的协议在计算时间和通信量方面有着出色的性能改进。请注意，幻灯片中图的纵坐标是对数轴。这张幻灯片给出了我们协议与Kiss等人协议在我们的基准测试环境中的性能比较结果。我们之所以直接选择与他们的协议进行比较，是因为他们的工作到目前为止是唯一一个在智能手机上实现非平衡PSI协议的工作。

我们考察当服务器数据库包含超过2.5亿个用户时，协议建立阶段的开销。可以看到，布谷鸟过滤器较好地压缩了数据，这里布谷鸟过滤器的负载因子约为70%。

然而，即使是通过Wi-Fi连接，实际应用中在某个时间点传输大约1GB的数据也有些大。因此，在本文中，我们建议使用多个扩展机制来进一步减少通信量。

我想在这里快速介绍与多服务器隐私信息检索技术相结合的扩展方案，工作原理如下。首先，主服务器将布谷鸟过滤器发送给第二个非合谋服务器。这里我要强调的是，此协议的信任假设并不如在其他协议那么强，但因为布谷鸟过滤器只包含加密元素，即使发生合谋，协议的安全级别仍然比目前最好的落地方案要好。在第二步中，客户端和主服务器执行不经意伪随机函数求值协议，随后使用多服务器隐私信息检索技术来检查服务器数据库中是否存在联系人。最重要的是，此方法将客户端与服务器的通信量减少到服务器数据库大小的对数级别。这样一来，即使服务器端用户数量超过10亿，协议也会非常高效。

我们总结一下报告内容。

今天我们介绍了目前最实用的移动端隐私联系人发现协议，以及协议的具体实现方法。所提出的协议不仅适用于联系人发现，而且适用于通用的非平衡PSI协议。我们提出的非平衡PSI协议还可以用于移动恶意软件检测和密码泄露检测等场景。我们还认为，我们在ARMv8-A架构上本地实现的乱码电路协议，对于未来移动设备上的许多安全计算应用程序都有借鉴意义。

不过，有一件事我不想隐瞒。我们联系了调查列表中的一个服务提供商，询问他们如何看待在现实世界中部署我们协议的可能性。不幸的是，他们给了我们一个非常苛刻的需求列表。其中，最大的问题是他们限定了协议的最大通信量。既然我们还不能满足这些要求，我只能鼓励在座的每一个人继续研究这个有趣而重要的领域。

以上就是我的报告内容，我很乐意回答一些问题，谢谢大家。

主持人：有什么问题吗？我有个问题。可能我刚刚错过了一部分讲解内容，你提到你的协议中用到了两个伪随机函数，那么Naor-Reingold伪随机函数和乱码电路伪随机函数的性能比较结果是怎样的？

主讲人：在我们的实验中，他们的性能表现大致相当。当然，AES在基本阶段会带来一些开销，因为我们需要传输这些乱码电路。你可能想问的问题是，实际中应该选择哪一个伪随机函数。我想说的是，这没有明确答案，选择哪个伪随机函数取决于应用场景。AES版本协议的好处在于，它不仅支持隐私集合求交这一特定的计算过程，AES版本协议可以实现通用PSI计算，允许你在交集结果之上对任意对称函数求值。在这种场景下，我建议使用基于AES或LowMC的协议。如果只考虑隐私集合求交，它们的效率是相似的。

主持人：很抱歉，我其实一共有两个问题。我知道时间有限所以我快点提问。在未来的5年内我们有可能在实际中应用这个协议吗？2年内呢？我把时间跨度减小点。有可能在实际中使用吗？

主讲人：我认为如果不弱化一些假设，像服务提供商也说，他们不想有任何非共谋服务器，如果你不弱化这些假设，我认为实际中不太容易很快应用此类协议。我的意思是，人们还在探索一些其他的方法，如使用Intel SGX技术，Intel SGX技术已经有实际应用的趋势了。当然了，这类技术也有其他的缺点。因此，在极其严格的要求和所有这些强假设下，我认为实际落地不会来得那么快。

主持人：尽管如此，这仍然是很大的进步。

主讲人：是的。

主持人：好的，再次用掌声感谢主讲人的精彩报告。