CCS 2017 - 基于同态加密的高效隐私集合求交协议

演讲视频简介

格密码视频被花式催更，无奈最近实在是太忙了，没有时间静下心来整理字幕，但我保证格密码学视频一定会整理完毕的，后面也会为知友和B站的朋友们带来2015年和2017年的冬令营视频讲座翻译。

今天为知友们带来的是CCS 2017《Fast Private Set Intersection from Homomorphic Encryption》的报告视频，主讲人是Hao Chen，目前在微软研究院工作。用同态加密构造隐私集合求交协议似乎是一个疯狂的想法，但在特定的应用场景（非平衡隐私集合求交）、结合特定的优化（布谷鸟哈希、分窗、划分、模转换），可以让同态加密隐私集合求交协议的性能优于OT隐私集合求交协议的性能。这篇论文也为读者介绍了非常多有关多项式求值方法的介绍，这也侧面影响了后面隐私集合求交协议的构造，如Pinkas等人在CRYPTO 2019上给出的SpOT-light。下一个视频我将会带来SpOT-light的翻译。

这次的视频仍然是

感谢主持人的介绍。我今天要介绍的是基于全同态加密（FHE）的隐私集合求交（PSI）方案。此工作是我与微软研究院的Kim Laine和Peter共同完成的，Peter也是上一个讲座的演讲者。

我们将回到半诚实模型，考虑非对称场景下的隐私集合求交协议。在非对称场景中，我们假设接收方拥有的集合大小比发送方拥有的集合大小要小得多。接收方是获得交集的那一方，他可以是某种移动应用程序。发送方可以是高性能服务器。

非对称PSI有哪些应用场景呢？非对称PSI的一个应用场景是隐私保护联系人发现，我将在下一张幻灯片介绍此场景。另一个应用场景是恶意软件检测。在该场景中，客户端在电脑上安装了一些软件，服务器端有一个恶意软件哈希结果列表，他们希望安全计算客户端安装了哪些恶意软件，但不泄露客户端安装的所有软件。Peter在之前的讲座中提到，广告转换率计算中也会用非平衡PSI，我就不详细介绍了。

在隐私保护联系人发现场景中，你是运行了某些移动端应用程序的用户，这里指的应用程序一般是WhatsApp或Signal这样的消息通讯应用。你的手机上还存有你的通讯录，里面包含所有你认识的人的手机号。服务器端拥有一份完整的手机号列表，列表中包含了所有注册了该服务的用户手机号。你想知道你的哪个朋友也已经注册了该服务，但不希望向服务器透露你认识的其他人。因此在这种情况下，你可以和服务器运行非对称PSI协议，因为你的通讯录比服务器的数据库小得多。

之前的PSI方案已经实现了非常好的性能表现，但是他们实际上并不专门针对这种不平衡的情况。通常在之前的工作中，会假设双方的集合数量大致相同。在2016年，由Pinkas等人和Kolesnikov等人分别提出了两个PSI协议。这两个协议是半诚实安全的，协议的性能非常优异。但是请注意，他们的通信开销是与发送端集合大小成线性关系的。而在我们的场景中，我们认为发送端的集合大小要比接收方的集合大小大得多。在这种情况下，协议的通信开销看起来不是最优的，我们希望改进通信开销。

下面我介绍我们的解决方案。这是一个基于全同态加密的高效非对称PSI协议。此协议的通信开销只与小集合的大小成线性关系，与大集合的大小成对数关系。因此，在特定的场景下，此协议的通信开销可以比之前的方案小40倍。我们结合使用了PSI和FHE领域的优化技术，使协议获得最佳的性能。我们使用了SEAL同态加密库来实现我们的方案，SEAL库由是微软开发的。

趁这个机会，我也给SEAL库打个广告。大家可以通过幻灯片的链接访问SEAL的官方网站，这是一个开源库。SEAL将在不久之后更新到新的版本，此版本会有很大的性能提升。请大家随时了解并使用SEAL库。

现在，让我来介绍一下基于同态加密的PSI协议基本构造思路。我们先考虑最简单的情况。假设接收方的集合中只有一个元素，发送方的集合X中包含 到 这B个元素，假定这些都是有限域中的元素。我们可以对如图所示的多项式求值，此多项式的根就是到 到 这B个元素。如果元素y在集合X中，那么多项式的求值结果为0，否则求值结果不为0。

然而，对多项式求值实际上会泄露一些关于集合X的信息。为了随机化求值结果，发送方需要在多项式上再乘以一个随机值。这样一来，如果y在X中，则多项式求值结果为0。如果y不在X中，则求值结果为随机数。因此，为了在同态加密下对多项式求值，我们只需让接收方发送同态加密后的元素y。发送方将使用FHE对多项式求值，并将密文求值结果返回给接收方。接收方将解密密文，得到明文多项式求值结果。如果明文为0，则接收方认为元素在交集中。

此协议的构造思路非常简单，我已经描述了我们的原型协议。只需要进行一轮通信，双方就能完成PSI的计算。如果存在高性能的FHE，这个协议的构造思路是非常简单的。但实际上，如果真的去实现这个原型协议，会发现协议的效率非常差。主要原因如下。首先，如果直接实现这个协议，则接收方需要为每个元素都生成一个密文。因此，如果接收方有数千个元素，则接收方需要发送数千个密文。从渐近复杂性的角度看，此协议的性能仍然很优异。但实际上，这么做的性能很差，因为每个FHE密文的密文长度都不算太小。所以，如果需要发送两倍于小集合的密文，则通信量仍然是一个很大的负担。而另一个可能更为严重的问题是，发送方需要在此协议中执行高幂次同态计算，这使得电路的深度与大集合元素数量成对数关系，这会导致协议性能较差，不满足预期。

为了提高协议的实际性能，我们使用了一些优化方法。我们使用了PSI领域的布谷鸟哈希、切分技术。我们还使用了FHE领域的批处理、分窗、模数转换技术。需要注意的是，每个技术都涉及到相应参数的配置方法。我们需要进行仔细考量各个参数的设置方法，寻找最优的参数组合，以达到最佳性能。

下面，我将依次介绍这些优化技术。首先是布谷鸟哈希。其他主讲人在之前的讲座中也提到过这项技术。布谷鸟哈希的基本思想是，发送方和接收方先协商出一些哈希函数。我们的协议要使用包含三个哈希函数的布谷鸟哈希。接收方将使用布谷鸟哈希，将接收方的集合哈希到一个哈希表中。发送方将使用全部三个哈希函数，将发送方的集合哈希到一个多列哈希表中。为简化描述，在幻灯片的实例中，我们假设两个集合包含相同的元素。假设我们有x、y和z三个元素。接收方将三个元素哈希为三种颜色对应的三个位置。在发送方的多列哈希表中，x、y、z将总共占据9个位置。

现在，假设我们要插入一个新的元素w，但如幻灯片所示，w的所有三个位置都已被占据。

在这种情况下，布谷鸟哈希会将w放在第一个位置，即x所在的位置。布谷鸟哈希将弹出x，并尝试重新插入x。请注意，发送方的操作非常简单，只需将w添加进三个哈希值对应位置的哈希桶中即可。

很幸运，在幻灯片的例子中，x的第三个位置是空的。布谷鸟哈希只需要把x重新插入到第三个位置即可。这就是布谷鸟哈希的原理，后面我们将讲解布谷鸟哈希在实际使用时的性能表现。

下面我来介绍另一个优化技术：批处理。这是FHE中的常用技术，可以将一组密文向量编码为一个密文，这样就可以实现SIMD，即逐个系数批处理加法和乘法运算操作。本协议将接收方哈希表批处理为|Y|(1+ε)/n个明文，其中ε是一个小的扩展因子。n相对比较大，大约为8,000或16,000。拓展因子ε的取值比较小。当使用三个哈希函数时，只需令1+ε=1.48，即可把接收方的所有元素放入哈希表中。在实验中，我们发现大多数情况下的密文数量会被压缩到只有一个。在这种参数设置下，布谷鸟哈希的失败概率为 。在发送方这边，元素数量为|X|，每个元素都被哈希了三次。哈希表有n行，n为批处理参数。由于|X|通常为百万量级，远远大于参数n，因此明文数量大约为3|X|/n。总的来说，该技术使得协议的通信开销从Θ(|Y|)降低到Θ(|Y|/n)，多项式求值电路的深度从Θ(log|X|)降低到Θ(log|X|/n)，不过需要乘以一个常数3。由于n是常数，因此渐近复杂度结果看起来差不多，但协议的实际性能有很大差异。

我们使用的另一个优化方法叫做分窗。回想一下，在我们的协议中，发送方需要在同态加密下对多项式求值，多项式的阶为B。有多种多项式求值方法。第一种方法是，接收方只发送y的密文，发送方应用二叉树求值法对多项式求值。你可以理解为，发送方将多项式分为左半部分和右半部分，对多项式递归求值。第二种方法是，接收方将y的所有幂，即从y^0到y^B都计算出来并发送给发送方，发送方可以展开多项式并线性求值。第三种方法是，接收方不发送y的所有幂，只发送2的幂次方所对应的幂。也就是说，接收方发送的是 、 、 ，以此类推。随后，发送方可以用这些密文计算出y的所有幂，并应用第二种方法对多项式求值。

幻灯片下方列出了这三种方法的性能比较结果。第一种方法的通信量很小，但是电路深度很大，这不能满足我们期望的效率要求。第二种方法的电路深度为常数1，但是接收方需要发送B个密文，通信量很大。第二种方法的渐近通信复杂度为|Y||X|，即两个集合大小的乘积，仍然不满足期望。可以证明第三种方法的通信量与小集合|Y|成线性关系，与大集合|X|成对数关系。在实际中，这基本上已经达到最优渐近通信复杂度了。第三种方法的电路深度与大集合|X|成双对数关系，实际电路深度几乎总是一个小常数。因此，我们选择第三种方法，协议效率可以达到最佳的平衡状态。

我们使用的另一个优化技术是切分。在上一张幻灯片中，我们已将同态加密下求值多项式的电路深度减小到双对数关系。但即使这样，协议的实际性能有时仍无法满足要求，我们希望进一步减小电路深度。有一种方法可以让发送方把B列数据切分成α块，每块的大小为B/α。这样一来，接收方需要对α个多项式求值，每个多项式的次数为B/α，一共求值α次。这样做有以下几个好处。第一个好处是，发送方可以重复使用加密后的y的幂，因为在每个多项式中，y都是相同的，只要有了y所有幂的加密结果，拆分多项式的方法就不需要引入额外的计算。第二个优点是，电路深度会进一步减小，从B的双对数关系下降到B/α的双对数关系，这将为我们提供更多选择参数的自由度，通过不同的参数平衡协议的性能。使用拆分技术会带来一些副作用。如果我们使用拆分技术，则返回的密文的数量为变为原来的α倍。记得之前我们通过批处理技术使返回的密文只有一个，而现在我们需要大约α个密文，拆分技术增加了通信量。

但我们可以使用其他方法来进一步减小通信量，这项技术叫做模数转换。在FHE领域，经常会使用模数转换方法来降低返回密文数据所引入的通信量。在同态加密中，通常不受信任的参与方会在加密的数据上完成一些计算任务。完成计算后，此参与方将密文结果发送回持有解密密钥的参与方进行解密。但是，密文一般都比较大，这是因为要进行密文同态运算，需要为噪声增长留出足够的空间。因此，密文一般都比较大。但是，有一种方法可以减小结果密文的长度，且解密方仍然可以正确解密密文。这里涉及到一些技术细节。简单来说，如果使用的同态加密方案是Fan-Vercauteren或BGV方案，就可以执行带舍入除法操作来减小结果密文的长度，但密文所关联的明文保持不变。此技术的基本思路是，舍入除法可以使密文长度从log(q)减小到log(q')，但是噪声的比例大致保持不变。为仍能正确解密密文，只需要让噪声比例低于某个阈值即可。我们在实际中对该方法进行了测试，结果表明，在我们选择的参数设置下，通信量会减少约5到10倍。

组合使用所有这些优化方法，我们就得到了我们的完整协议。与原型协议相比，完整协议中包含了许多的新增内容。首先，接收方用布谷鸟哈希把集合映射到哈希表中。随后，接收方使用同态批处理操作将哈希表拆分成多个明文。另一方面，服务器使用多个哈希函数将集合映射到多列哈希表中。随后，服务器使用批处理技术将哈希表拆分成B个明文。第二个绿色框可以离线完成，我们可以将此步骤的处理时间算作预处理时间。接下来，服务器将明文拆分为α个子集。在线阶段中，对于每个明文向量y，接收方向发送方发送加密后的y的2的幂所对应的幂。对于发送方的每个明文子集，发送方采样一些随机量，在同态加密下对多项式求值，从而计算出差值连乘和采样随机量的乘积结果。发送方计算得到最终结果的密文后，对密文执行模数转换，减小结果密文的长度。最后，发送方将密文返回给接收方。接收方解密密文，得到最终的交集结果。以上就是协议的完整描述。

幻灯片上的表格给出了协议的性能对比结果。在实验中，我们将接收方数据集大小设置为5,500或11,000，发送方数据集大小为100万或1600万。我们对比了本方案与之前两个方案的性能。红色的数字表示我们的协议在通信量或总运行时间方面的性能更优。我们也考虑了不同网络带宽配置下的性能比较结果。在如10Mbps或1Mbps等低带宽网络条件中，我们的协议比之前的协议要快很多。在Mbps级别的网络带宽条件下，我们的协议比之前的协议要快40倍。

我们目前正在进行后续的研究工作。我们进一步优化了协议的性能。我们结合了一些SEAL库的优化技术，并对PSI协议的部分细节点进行了进一步的优化。幻灯片的这张图指出，如果接收方集合大小为5,000，发送方集合大小为1600万，我们新协议的在线阶段运行时间小于4秒。因此在计算和通信量方面，我们的新协议比其他两个协议都要好得多。我刚刚咨询过Peter，他说这个结果在高带宽网络配置下应该也成立。

综上所述，我们的协议基于全同态加密构造。针对接收方集合比发送方集合小得多的场景下，我们对协议进行了一系列的优化。在这一场景下，我们协议的通信开销非常低，通信量与小集合的大小成线性关系，与大集合的大小成对数关系。其他两种PSI协议的通信开销都与大集合的大小成线性关系。这是我们协议与这两个协议的主要区别之一。

总的来说，在非对称PSI场景下，FHE是一种很好的解决方案，协议的通信开销很小。

我想简单介绍一下我们的未来研究方向。首先，我们论文中的方案只能处理长度最长为32比特的集合元素。在后续的工作中，我们将集合元素的支持长度扩展为任意长。审稿人还询问我们，协议是否可以支持其他场景，如发送方集合较小，接收方集合较大。这也是我们正在进行的工作。审稿人还提出多方PSI、披露交集大小的PSI。Peter也提到，带数据查询功能的PSI就是带负载数据的PSI。我想说的一点是，已经有工作应用FHE构造隐私集合交集求和协议。此类协议可以应用于这样的场景：谷歌和特斯拉要运行此PSI计算广告转化率，特斯拉可能想知道谷歌投放广告的总收益，即汽车销量乘以每辆汽车的收益，这里可以使用隐私集合交集求和协议。此协议有着不错的应用场景，但只有谷歌发表了一篇论文，且协议使用了耗时的公钥密码操作。我们正在探索一些其他方法，期望改进此类协议的效率。最后，我们还可以考虑是否可以使用FHE在恶意模型下构建PSI协议，这都是一些值得研究的问题。

我的报告就到这里，非常感谢大家的聆听。

提问者：你好，这是个非常出色的工作，我没想到可以用全同态加密如此高效地解决特定场景下的PSI问题。我想将你提出的方案与另一个方案比较，那个方案也是针对非对称PSI场景所提出的。在该方案中，发送方对集合中的每个元素都计算了一次PRF，得到每个元素的PRF结果。接收方得到了接收方集合元素的OPRF结果。随后，发送方将发送方所有元素的PRF结果发送给接收方。此协议的通信量与大集合元素数量成线性关系，这比你们方案的通信量要大很多，但那个PSI方案只需为每个元素发送少量数据，每个元素大约需发送40或80比特数据。如果我对你的性能对比表格理解正确的话，当大集合包含上百万个元素时，你们方案的通信开销会更好。也就是说，当大集合元素数量为 量级时，你们方案的性能更优。但是我描述的这种解决方案，其运行效率要高得多，只需要几秒钟即可完成计算。因此，应该需要进一步比较你们的方案与其他非平衡PSI方案的性能。

主讲人：非常正确。我不是非常了解你说的这个方案，我觉得你提到的方案和CCS 2016上Kolesnikov的工作很像，我前面提到过这个方案。简单来说，他们的方案使用了OPRF。接收方得到每个元素的OPRF结果，发送方向接收方发送自己所有元素的PRF结果。这个协议的通信复杂度更大。我认为我们的协议有个很好的特性，即协议的复杂度不与元素数量成线性关系，协议的复杂度近似为一个常数。因此，本工作是改进了之前工作的性能。你可能还知道一些其他的优化协议，我们可以线下交流，谢谢。

提问者：很棒的工作。你在你的未来工作这部分提到了一个方向，即还有另一种有趣的场景：发送方的集合较小，接收方的集合较大。为什么不能仅仅转换下协议中的角色来满足此场景的需求呢？

主讲人：是的，我们的想法是先交换协议角色，协议执行到最后阶段时，再执行一些操作。如果你只是直接交换协议的角色，那么发送方就会得到交集。我们希望接收方能够得到交集，但接收方的集合比较大。因此，我们还需要执行一些操作，保证接收方得到交集。但这个问题不是非常的困难…

提问者：但你总可以让一方对自己的大集合元素进行加密，再让获得结果的这一方发送交集的加密结果，因为协议半诚实安全的。不过如果用朴素的方法实现此功能，通信量就与集合大小成线性关系了。

主讲人：没错，我认为是的。

提问者：好的，谢谢。

提问者：我有一些关于同态加密优化方法的问题。不知你是否尝试过下述优化方法，如果没有，你可能需要进一步修改协议的参数了。第一个优化方法是，你可以尝试Paterson-Stockmeyer多项式求值方法，用该方法对单个多项式求值的效率会比朴素方法快很多。另一个优化方法是，如果要计算元素的所有幂次，那么本质上只需要使用一个线性转换。可以用通用工具在压缩密文上做一次一般线性转换，这比手动做线性转换要快很多。以上这些优化可能只会带来常数级的性能提升，但是会影响优化方案的参数选择。

主讲人：好的，谢谢。当我们在写这篇论文的时候，我们还不知道有Paterson-Stockmeyer技术。我们应该可以直接使用Paterson-Stockmeyer技术来进一步提高效率。我不太清楚的一点是，由于我们使用了很多优化技术来减小电路深度，最后的多项式幂次会很低，Paterson-Stockmeyer技术可能不会带来太大性能提升。我们可以之后尝试下这个技术，这是个很宝贵的建议。我不是很了解线性转换技术，我之后会研究一下，非常感谢你的建议。

提问者：使用FHE解决PSI问题是个很棒的想法。我想问一个更基础的问题，此协议真的需要使用FHE吗？

主讲人：不好意思，我没理解你的问题。

提问者：为什么一定要用FHE？这里只是做的简单的计算吧？

主讲人：为什么要使用FHE…

提问者：可以先约定多项式大小，用另一种形式发送多项式，从而降低通信量，当然了，用FHE是个很不错的想法。

主讲人：你的意思是对比一下FHE和加法HE？

提问者：是的，或者乘法HE。

主讲人：如果使用幻灯片中的第二种方法，我认为只用加法HE就能实现协议。问题在于，我不知道是否存在某个加法HE，可以使协议获得更优的通信开销，这是我存疑的一个点。如果使用基于格的加法HE，通信开销应该是差不多的。但如果使用其他的加法HE，我就不是很确定实际的通信复杂度了。

提问者：好的你们是因为自己有个库所以使用了FHE吧？

主讲人：是的，我们使用FHE的一个原因就是我们有自己的FHE库。

主讲人：谢谢大家！