基于OT协议的外包隐私集合交集计算协议

廖鹏程，陈小军，申立艳,3, 时金桥

(1. 吉林大学，长春130000；2. 中国科学院信息工程研究所，北京100093；3.中国科学院大学 网络空间安全学院，北京 100049)

0 引言

随着物联网技术、云计算技术的快速发展，信息系统中每时每刻都会产生大量的数据。据统计，在2013年时社交网站Twitter每天活跃用户达到2亿人次，每天发送信息超过4 亿条，在2017年，Facebook自己披露每日活跃用户达到13 亿。

这是一个数据爆发的时代，每天都有大量数据产生，那么大数据下的隐私保护问题已经成为学术界和工业界的关注焦点。

隐私集合交集(Private Set Intersection，PSI)是安全多方计算的一个重要协议，它允许参与计算的各方只能获得交集元素的信息。现在大部分PSI为参与方为两方的协议，以实现的方法不同来分类。基于公钥密码体制的PSI，根据协议的设计思想不同可以分为：基于不经意多项式计算PSI[1]，本方案将元素表示为方程的根，然后通过同态加密方案来保证数据的安全性；基于不经意伪随机函数PSI[2]，本方案客户端和服务端通过不经意伪随机函数将客户端隐私集合加密，然后在密文上做交集，保证隐私数据的安全性。基于盲签名的PSI[3]，本方案客户端将数据进行盲化操作，然后服务器在盲化操作的数据上签名和本地数据签名之后发送给客户端，客户端执行去盲化操作，就可以在元素的签名上做交集运算。基于混乱电路的PSI[4]，本方案通过设计混乱电路来实现所需要的交集功能，基于OT协议的PSI[5]，本方案通过执行随机OT协议将元素变为一个随机值，在随机值的基础上做交集计算。

产生大量数据的终端大多数为低性能设备，如手机、传感器等。需要大量计算力的两方的隐私集合交集计算协议不适用于这类设备。由此产生了基于云环境的隐私集合交集计算协议。在该协议中低性能设备将部分计算外包给高性能的服务器，从而降低计算开销。

现有的基于云环境的PSI大体上分为基于对称密码体制的PSI[6]和基于非对称密码体制的PSI[7]两种。其中基于对称密码体制的PSI，两个客户端将自己的元素用对面密码体制的加密算法将元素加密，发送给服务器，服务器在密文上做交集计算，将结果返回给客户端；基于非对称密码体制的PSI，将本地元素用非对称密码体制的加密算法加密，发送给服务器，服务器利用加密之后的数学性质做交集计算。但是以上两种协议都各有缺点，不能很好地满足人们的需求。

本文提出一种新的基于云环境的PSI，本协议是在两方的基于OT协议PSI上进行扩展而衍生的新协议。本协议的效率远远高于基于非对称密码体制的PSI，安全性高于基于对称密码体制的PSI。

1 预备知识

1.1 安全模型

目前，在安全多方计算领域，GOLDREICH O所提出的安全性定义[8]是被广泛接受的，所以以下采用该定义，将参与方分为三类：

(1)诚实参与者：完全遵守协议的执行过程，在协议执行过程中不会监听，伪造各参与方的信息。

(2)半诚实参与者：完全遵守协议的执行过程，但是可能会在执行过程中监听其他参与方的输入输出信息，从而推测其他参与者的隐私信息。

(3)恶意参与者：可能不会完全遵守协议的执行过程，可能会拒绝参与协议，终止协议，或者在协议执行过程中发送虚假的数据。

其中半诚实模型是在安全多方计算中广泛使用的模型，也是更接近于真实场景的模型，以下就以半诚实模型为安全模型对协议进行分析。

1.2 不经意传输(Oblivious Transfer，OT)

OT协议[9-10]是一种基于公钥密码体制的协议，也是一种多方安全计算的基础协议。在协议中有两个参与方分别为发送方P1和接收方P2，P1有N条数据d1,d2,…,dn，P2拥有选择向量σ。在协议执行前P1的输入为N条数据d1,d2,…,dn，P2的输入为选择向量σ。在执行完协议之后P2会获得数据dσ，并且不能获取P1的其他数据的信息。P1没有输出且不能获取P2的选择向量σ。

OT协议在近些年发展也很迅速，由最初的二选一OT协议、N选一OT协议，为减少计算开销而发展为二选一扩展OT协议、N选一扩展OT协议，同时为了减少通信开销发展为它们对应的随机OT协议。本文所采用的是随机N选一OT协议。

1.3 布谷鸟哈希

布谷鸟哈希是在简单哈希函数的基础上解决了哈希函数的冲突问题。可以通过添加哈希函数或者通过哈希表来实现。

本文通过添加哈希函数来解决冲突，算法的实现步骤为，首先将元素用不同的哈希函数映射到哈希桶中对应的位置。在所有映射到的位置中，如果有空的哈希桶，则选择任意一个插入，如果映射到的位置全都有元素，则任意选择一个桶插入，将桶中的元素踢出，被踢出的元素继续执行以上操作，直到找到合适的位置插入。

经过多次循环之后，有的元素仍然不能找到合适的位置插入，则可以将插入失败的元素插入到一个数据结构Stash中。

2 基于OT协议的外包隐私集合交集协议

本节对基于OT协议的外包隐私集合交集协议的主体部分进行描述，然后对协议的效率、正确性和安全性进行分析。在协议中所用到的符号，参与方分别为Alice、Bob，Alice的集合为Da={x1,x2,…,xn1}，Bod的集合为Db={y1,y2,…,yn2}。Alice和Bob执行OT协议之后所产生的随机序列mask。服务器为C。

2.1 协议过程

协议主体分为三个阶段：

第一阶段：Hash(本地执行)

(1)Alice将集合中的元素通过设置中的k次不同哈希函数的简单哈希映射到哈希表中。

(2)Bob将集合中的元素映射用设置中的k个不同哈希函数的布谷鸟哈希，将元素映射到哈希表中。

第二阶段:OT协议(两个客户端通信)

(1)对于每个哈希桶，Alice、Bob执行随机OT协议，Bob作为OT协议的发送方以哈希桶中的元素为选择向量，Alice作为OT协议的接收方。

(2)Alice将收到的mask添加到集合中，作为对隐私集合的加密，Bob选择哈希桶中对应元素的mask，作为对隐私集合的加密。

第三阶段：计算交集(客户端和云服务器通信)

758 Permanent pacemaker implantation after cardiac surgery: an analysis of 103 cases

(1)Alice、Bob在自己的mask集合发送给服务器，服务器在mask上做交集计算，并将结果返回给Alice、Bob。

(2)Alice，Bob收到返回的集合后，就可以根据mask找到对应的元素，得到最后的隐私集合交集。

基于OT协议的隐私集合交集计算过程如图1所示。

图1 基于OT协议的隐私集合交集计算

2.2 协议分析

(1)正确性

在这里考虑元素成功映射到哈希桶中的情况，如果插入失败，而放到Stash时，原理和在哈希桶中的正确性证明无差异。假设Da中有一个元素xi，Db中有一个元素yj。下面分两种情况讨论。

当xi=yj时，因为两个元素相同，所以肯定会通过k个哈希函数中的一个映射同一个桶中，对这个桶中的元素执行OT协议之后，这两个元素的mask也是相同的，之后计算交集时能正确判断两个元素相等。

当xi≠yj时，如果要错误地判断它们为相等，它们的mask必须相同，mask相等的概率为2，Alice的mask和Bob对应的桶中的所有mask都要进行比较，Alice和Bob桶中任意元素相等的概率为kn1n22，所以要让它们都不相同的概率为1-kn1n22。

(2)安全性

在半诚实模型下考虑协议的安全性。只有在协议的第二阶段和第三阶段才有可能泄露隐私信息。

首先考虑第二阶段，两个客户端执行OT协议，对于Bob来说肯定是安全的，因为在协议执行期间并没有输入隐私信息。对于Alice来说输入了选择向量，即对应的元素哈希之后的值，但是OT协议保证了Bob不能获取该选择向量。所以对于Alice来说也是安全的。

再来考虑第三阶段，在本阶段所发送的都是mask，该值是双方通过随机OT协议所产生的和原来的元素是独立的随机序列，所以不能通过mask推断出原有隐私集合的信息。

(3)效率

下面分析该协议的效率，将协议的效率分为计算效率和通信效率。假设交集大小为I。

首先分析协议的计算效率，对于客户端来说，在协议的第一阶段对隐私集合中的元素用哈希函数映射到对应的哈希桶中，所执行的哈希操作为|Da|×k(元素个数乘哈希函数的数量)。第二阶段，计算双方执行OT协议，一共执行了(s+b)次OT协议，可以通过增加哈希函数来减少Stash的大小，从而减少执行OT协议的次数来降低计算开销，第三阶段，根据服务器返回的结果查询对应的元素，在时间复杂度为O(I)。对于服务器来说，只有在密文上计算交集，时间复杂度为O(|Da|+|Db|)。

然后分析协议的通信开销，对客户端来说通信开销为两个客户端执行OT协议时和发送给服务器mask所产生的流量，这两部分通信开销都和元素的大小呈正相关。对于服务器来说，只是最后将交集结果返回给客户端所以通信开销和交集的大小呈正相关。

3 实验

在实验部分，实现了基于对称密码体制的PSI、基于非对称密码体制的PSI和基于OT协议的PSI，并将三种协议进行对比分析。

实验设置：隐私集合分为25，210，216,220,224等数量级不同的集合，分析三种协议在集合大小不同时的计算和通信开销。

假设计算隐私集合交集的两个客户端分别为Alice和Bob，Alice和Bob分别选用以上的数量级大小不同的集合作为自己的隐私集合，和对方做隐私集合交集计算。

首先对表1分析，首先看Alice集合小于等于Bob集合时，固定Alice的集合大小不变增大Bob集合的大小，所需的计算时间增大；再看Alice集合大于Bob集合时，固定Alice集合大小不变增大Bob集合大小，所需的计算时间基本不变。这里是因为采用采用布谷鸟哈希插入元素时，所需的时间大于采用简单哈希插入元素的时间，而且需要等待哈希操作结束之后才能执行之后的OT协议。

现在对表2分析，第一，Alice和Bob发送的数据量相互独立，且只与本地数据集大小有关；第二，当Alice和Bob本地数据集大小相同时，Alice所需要发送的数据量大致为Bob的两倍，这是因为Alice作为OT协议的发送方，需要发送更多的数据；第三，本协议所需发送的数据量较大，比如在集合大小为224时，Bob所要发送的数据为480 MB。

从图2中可以看出，基于对称密码体制的隐私集合交集计算协议所需的计算量和发送的数据量都是最少的，基于非对称密码体制的隐私集合交集计算协议所需的计算量和发送的数据量是最多的，而本协议基于OT协议的隐私集合交集计算协议所需的计算量和发送的数据量居中。

表1 协议的计算时间 (ms)

注：1)表中第一行为Bob即接收方的隐私集合大小，第一列为Alice即发送方的隐私集合大小。

表2 协议的通信开销 (MB)

注：1)表中第一行为Bob即接收方的隐私集合大小，第一列为Alice即发送方的隐私集合大小。

2)表中A表示客户端Alice，B表示客户端Bob。

图2 在数据量为时三种方法所需的计算时间和发送数据量对比

下面对三种协议的安全性进行对比，三种协议安全性最主要的区别就是是否可以抵抗服务器与任意一端客户端的合谋攻击。基于对称加密体制的隐私集合交集协议不能抗合谋攻击，因为客户端双方所用密钥相同，只要有一方客户端和服务器合谋，就会泄露另一客户端的信息，基于非对称加密的隐私集合交集协议和基于OT协议的隐私集合交集协议可以抗合谋攻击。

总的来说，本协议证明半诚实模型下是安全的，可以抵抗合谋攻击，并且有较高的计算效率。

4 结论

本文提出了一种新的在云环境下的基于OT协议的隐私集合交集计算协议，该协议提供了比基于对称密码体制的隐私集合交集计算协议更高的安全性，而计算开销和通信开销远小于基于非对称密码体制的隐私集合交集算法。

在未来工作中会继续对隐私集合交集协议的计算效率和通信效率进行优化。目前为止大多是两个客户端计算交集，未来的一个研究方向是将隐私集合交集计算协议扩展为多个客户端同时计算交集。

[1] FREEDMAN M J, NISSIM K, PINKAS B. Efficient private matching and set intersection[C]//International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2004: 1-19.

[2] FREEDMAN M J, ISHAI Y, PINKAS B, et al. Keyword search and oblivious pseudorandom functions[C]//Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2005: 303-324.

[3] DE CRISTOFARO E, TSUDIK G. Experimenting with fast private set intersection[C]//International Conference on Trust and Trustworthy Computing. Springer, Berlin, Heidelberg, 2012: 55-73.

[4] YAO A C C. How to generate and exchange secrets[C]//27th Annual Symposium on Foundations of Computer Science. IEEE, 1986: 162-167.

[5] PINKAS B, SCHNEIDER T, ZOHNER M. Scalable private set intersection based on OT extension[J]. IACR Cryptology ePrint Archive, 2016, 2016: 930.

[6] KAMARA S, MOHASSEL P, RAYKOVA M, et al. Scaling private set intersection to billion-element sets[C]//International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2014: 195-215.

[7] KERSCHBAUM F. Collusion-resistant outsourcing of private set intersection[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing. ACM, 2012: 1451-1456.

[8] GOLDREICH O. Secure multi-party computation[J]. Manuscript. Preliminary version, 1998: 86-97.

[9] NAOR M, PINKAS B. Efficient oblivious transfer protocols[C]//Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2001: 448-457.

[10] ASHAROV G, LINDELL Y, SCHNEIDER T, et al. More efficient oblivious transfer and extensions for faster secure computation[C]//Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. ACM, 2013: 535-548.