隐私保护集合求交技术PSI

2020/10/10 密码学

隐私保护集合交集(Private Set Intersection, PSI)技术是多方安全计算领域的一个子问题,目的是在保护通信双方的数据隐私性前提下完成数据集的交集计算。下面主要描述PSI的定义与探讨CRYPTO 2020会议中一篇关于PSI的论文。

什么是PSI

隐私保护集合交集(Private Set Intersection, PSI)协议允许持有各自数据集合的两方执行双方集合的交集运算。PSI协议结束之后,一方或两方能够得到交集结果,但是双方都无法获知交集以外的对方集合数据的任何信息。

PSI协议定义

理想的PSI协议由一个发送方\(S\)和一个接收方\(R\)参与,其中发送方\(S\)持有集合\(X\),集合大小是\(N_X\);接收方\(R\)持有集合\(Y\),集合大小是\(N_Y\)。集合元素是长度为\(\sigma\)的二进制字符串。其中关于\(N_X\)和\(N_Y\),在大多数情况下是公开的。

PSI协议执行\(X \cap Y\)运算得到交集,并将结果发送给接收者\(R\),发送者\(S\)没有得到任何信息。PSI协议结束之后,接收者\(R\)无法获得任何关于\(X \cup Y - Y\)的任何消息,发送者\(S\)也不能获得任何关于\(X \cup Y - X\)以及\(X \cap Y\)的任何消息。

应用场景

计算广告的实际效果

线上广告是一种重要的广告形式。对于广告的有效程度的衡量的常见方法是计算转换率,也就是浏览广告的用户中有多少用户最终浏览了相应的商品页面,或是最终购买了相应的商品或是服务。一种通用的计算方法是由计算浏览广告的用户信息(由广告发送方占有)和完成相应交易的用户信息(由商家占有)的交集来计算(如计算交易总额或是总交易量等)。而与此同时双方的用户信息又是私密的,如果使用不安全的协议会导致一方的信息暴露给另一方,从而造成用户和商家或是广告主的隐私泄露。

寻找联系人

当一个用户注册使用一种新的服务(如微信、Whatsapp 等)的时候,从用户的现有联系人中寻找有哪些已经注册了同类的服务是一种在大多数情况下十分必要的操作。通过将用户的联系人发送给服务提供商可以有效地完成这项功能,但是与此同时用户的联系人信息,一种在大多数情况下被认为是隐私的信息,也被暴露给服务提供商了。因此在这种场景下,将用户的联系人信息作为一方的输入,将服务提供商的所有用户信息作为另一方的输入来进行PSI协议可以完成发现联系人的功能,而且可以防止交集以外的信息泄露给任何一方。

Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF

在国际三大密码学术会议之首的美洲密码年会CRYPTO 2020上有一篇关于PSI的论文,它由微软公司研究员Melissa Chase与Visa公司研究员Peihan Miao提出。这篇论文的重点是使用不经意传输协议OT、对称密码技术和伪随机数函数PRF实现了一个轻量级的两方PSI协议。这篇论文的难点在于如何实现使用OT扩展协议来实现不经意伪随机函数,下面的讨论中我会将OPRF看作是一个黑盒子,忽略其构造过程,从全局角度观察这篇论文的PSI协议是怎么实现的。

相关知识

不经意传输(Oblivious Transfer, OT)

不经意传输是Rabin在1981年提出的两方计算协议,协议由发送方、接收方两方参与。发送方拥有一个“消息-索引”对\((M_1,1),(M_2,2),...,(M_N,N)\)。每次传输的时候接收方选择一个满足\(i \in [1,N]\)的索引\(i\),并接收\(M_i\)。接收方不能得知关于数据库的任何其他信息,发送方也不能了解接收方选择了哪个消息。下面是n取1的不经意传输定义:

n取1的不经意传输:假设A将一个输入表\((x_1,x_2,...,x_n)\)作为输入,B将\(i \in 1,2,...,n\)作为输入。其中A不能学习到关于\(i\)的任何信息,而B只能学习到\(x_i\)。

当我们在讨论两方协议的时候,这里的\(n\)取值为2。一般情况下,给定2选1的不经意传输可以执行安全两方计算操作。

伪随机数函数(Pseudo Random Function, PRF)

伪随机数函数是使用一个确定性的算法计算出来的看似随机的数序,“伪”的意思是算法实际并不随机。一般的,如果输入到伪随机数函数的初始值是相同的,那么输出的随机数值也是相同的。我们可以朴素认为PRF是一个将输入映射到某个看似随机的输出域的过程。下面给出PRF的严格定义:

对于一个伪随机数函数\(F\),我们有:

  1. \(F(x)\)与\(F(y)\)的分布是没有关联的。(\(x \neq y\))
  2. 通过\(F(x)\)求出\(x\)是计算困难的。

协议执行过程

初始化阶段

发送方\(P_1\)与接收方\(P_2\)共同协商两个哈希函数\(H_1,H_2\)以及一个伪随机数函数\(F_k\),并且双方都持有\(F\)对应的相同密钥\(k\),同时双方也共同协商了协议参数\(m,w\)。

这里的伪随机数函数\(F_k\)的输出是长度为\(w \times \log m\)-bit的字符串。

也就是说协议开始之前双方拥有相同的\(H_1(),H_2(),F_k(),m,w,k\)。

预计算阶段

发送方\(P_1\):

  1. 随机选择一个长度是\(w\)-bit的字符串\(S\)。

接收方\(P_2\):

  1. 生成\(w \times m\)的二进制的单位矩阵\(D\)(也就是矩阵的元素是0或1),这个矩阵有\(w\)行,\(m\)列。
  2. 生成随机的密钥\(k\),这个密钥将用于伪随机数函数\(F\)的输入。
  3. 对于数据集合\(Y\)的每一个元素\(y\),计算\(v=F_k(H_1(y))\)。\(v\)是一个长度为\(w \times \log m\)-bit的随机字符串。
  4. 将\(v\)分成\(w\)个长度为\(\log m\)-bit的部分,也就是可以得到\(w\)个范围在\([0,m-1]\)的随机数,我们用符号\(v[i]\)表示这个随机数。
  5. 将\(D[i][v[i]]\)设置为0。注意符号\(D[x][y]\)表示矩阵的第\(x\)行、第\(y\)列对应的值。

OT阶段

发送方\(P_1\):

  1. 我们忽略OT阶段的细节,OT执行完毕之后得到一个矩阵\(C\),这个矩阵有\(w\)行,\(m\)列。

接收方\(P_2\):

  1. 随机选择一个\(w \times m\)的矩阵\(A\),并计算出矩阵\(B\),其满足\(B = A \oplus D\)。

  2. 我们忽略OT阶段的细节。矩阵\(C\)的每一行与随机数\(S\)有关,如果\(S[i]=0\),那么就选择矩阵\(A\)的第\(i\)行作为矩阵\(C\)的第\(i\)行;如果\(S[i]=1\),那么就选择矩阵\(B\)的第\(i\)行作为矩阵\(C\)的第\(i\)行;这里\(i\)的范围是\(0,1,...,w-1\)。

下面这张图可以清晰的描述这几个矩阵的关系:假设\(w=5,m=6\),首先\(P_2\)生成一个单位矩阵,将伪随机数函数的值映射到这个矩阵中得到新的矩阵\(D\)。然后随机选择一个矩阵\(A\),并与矩阵\(D\)求异或得到矩阵\(B\)。忽略OT的细节,最终\(P_1\)会得到矩阵\(C\),并与随机数\(S\)满足一定的关系。

PSI阶段

接收方\(P_2\):

  1. 将密钥\(k\)发送给\(P_1\)。
  2. 对于数据集合\(Y\)的每个元素\(y\),计算出\(v=F_k(H_1(y))\)。
  3. 收到\(P_1\)发来的一些哈希值的集合\(CX\)。
  4. 我们用\(a_i\)来代表\(A[i][v[i]]\)的值,\(a_i\)是矩阵A的元素,要么是0要么是1,符号”\(\|\)“表示位的拼接。
  5. 计算出\(H_2(a_0 \| a_1 \| ... \| a_{w-1})\)的值,注意这里的\(H_2()\)的输入是长度为\(w\)-bit的随机字符串。所有这些值得到哈希值的集合\(AY\)。
  6. 求交集\(AY \cap CX\)。
  7. 根据第6步得出的结果反推出\(X \cap Y\)。

发送方\(P_1\):

  1. 对于数据集合\(X\)的每个元素\(x\),计算出\(v=F_k(H_1(x))\)。
  2. 我们用\(c_i\)来代表\(C[i][v[i]]\)的值。
  3. 计算出\(H_2(c_0 \| c_1 \| ... \| c_{w-1})\)的值,并将这些值发送给\(P2\)。

下面这张图举出了一个简单的例子:

首先双方已经成功拿到了矩阵A和矩阵C,随后各自分别输入一个值。如果这两个值相同(\(x=y\)),那么最后得到的\(w\)-bit长度的随机数一定会相等,否则不相等。

奥妙

这个协议为什么可以实现PSI?我们重新来审视整个协议过程,并简化掉部分操作,使得可以更加直观地观察出其中的原理。首先我们需要明确在协议过程中,双方都达成了一个共识算法(我们将PRF、Hash看作一个映射关系,将OT过程忽略):

双方的数据看作是\(x1\),按照上面的流程经过多次映射后得到最后的输出\(x_4\)。在通信中传输的数据是\(x_4\),求交集执行算法过程中处理的数据也是\(x_4\),因为这个映射关系是一一对应的,所以接收者可以通过交集的结果反推出\(x_1\)(因为接收者在预计算过程中学习了输入与输出的映射关系)。

上面这个过程是两方都在同步执行的,关键就在于中间的矩阵是不同的,我们知道他们分别使用的是矩阵A和矩阵C。因此这个精妙之处就在于矩阵A与矩阵C的关系是什么?我们先来看看矩阵D的形状:

首先我们使用上面的算法的一部分,求出输入在矩阵中投影的位置,生成一个特殊的图案。每一个不同的输入都会对应一个不同的图案,将这些图案合并在一起得到一个新的图案。强调:黑点与白点只是代表位置,并不代表矩阵的0和1。随后将黑点的位置设置为0,将白点的位置设置为1,得到了矩阵D。

随后我们随机选择一个同等大小的矩阵A,并与矩阵D进行异或操作得到了矩阵B。注意这里的红点和绿点均表示位置,并且对应位置的红色和绿色是互斥的关系,即如果红色位置是0,那么对应的绿色位置是1,反之红色位置是1,那么绿色位置是0。因为我们知道矩阵D中黑点都是0,白点都是1,那么异或之后得到的矩阵B满足这种红绿的互斥关系。

矩阵C是矩阵A与矩阵B经过OT协议得到的,也就是说矩阵C的每一行要么是来自矩阵A,要么是来自矩阵B,但是我们不知道这个映射关系是什么,它是由随机数S的位来决定的。但是你会发现不管怎么选,其中某些位置是一定不会发生变化的,除此之外别的地方到底是什么,对于接收者来说它没有办法学习,因此我用了红绿两色来表达这些位置。

换言之,矩阵A与矩阵C的关系是在某些特定位置(矩阵D中黑点的位置),他们的值是一样的,而除此以外的别的位置的值,是无法被对方知道的,这个特性是由OT协议来确保的。

从上面的关系中可以看出,矩阵D【凝聚】了所有\(y\)值的特征位置,并且【隐含】了在矩阵A和矩阵C中。当某个x值如果是满足\(x \in Y\),那么这个\(x\)所生成的图案将会【命中】矩阵D的黑色位置,并产生了相同的哈希值。如果某个x值是不满足\(x \in Y\),那么这个\(x\)所生成的图案将会含有少量矩阵D中白色的位置,最终产生了部分红绿位置的值,因为这个值是双方非共识的,所以最终产生的哈希值是不同的。

思考

这个协议设计非常微妙,下面是一些进一步思考的方向。

  1. 协议的通信量是这个矩阵C的大小,也就是\(w \cdot m\),与通信双方的数据集合的大小无关,并且假设了通信双方的数据集合大小是对等的。在现实意义下有的时候通信双方的数据集合大小是不对等的,例如联系人功能的应用场景,用户手机里面的联系人数量非常小,而app公司拥有的联系人数量非常庞大,应该如何解决数据集合不对等的问题呢?

  2. 在论文中关于\(w\)和\(m\)的选择有着严谨的数学证明,其中\(m\)一般是取数据集合大小\(n\),而\(w\)则在几百的范围。如何选择\(w\)是一个需要仔细思考的问题,论文中有展开描述,这里就不多讲。当这个\(w\)很小的时候,虽然通信量减少(矩阵的行减少),但是会使得上面的映射关系出现碰撞,即两个不同的输入得到了相同的输出。上面提到的共识算法中,输入源x1的长度是\(a\)-bit,输出x3的长度是\(w\)-bit,那么如果\(w<a\),就会出现映射碰撞的问题。在论文的实验中,这个\(a\)的取值是128,\(w\)的取值在600-700范围,我尝试着去运行了论文的代码,发现\(w\)的值降低到300、400、500也没有出现碰撞,那么我们是否可以往某个方向去假设,存在某个合理的\(w\)边界使得这个碰撞不会发生?

  3. 上面提到了OT协议的作用是使得矩阵A和矩阵C互不相同,但是却隐含着矩阵D的特征位置。那么假设不执行OT协议,双方直接得到完全相同的矩阵A,这样是否达到了PSI的隐私保护要求?在这种情况下,这个协议就会退化到朴素的哈希PSI协议,我们可以将这个相同的矩阵A看作是相同的、预共享的Hash函数(映射关系),由于hash函数的单向性,如果这个hash的映射域非常非常巨大,那么在安全性上我觉得也能达到隐私保护的要求。

    在这种情况下会存在一个什么问题呢?那就是接收者可以得到一个布尔服务。用户B收到了用户A发来的所有x映射的值,然后B想知道A是否含有某个m?B可以在本地执行相同的算法得到了映射的值,并将这个值在A发来的集合中匹配,如果存在,则输出“含有”;如果不存在,则输出“没有”。

    这意味着用户B能够以高效的算法快速知道用户A是否含有某个元素,尽管用户B不能算出所有的x。上述的协议使用了OT,使得用户B不能回答这个问题,它对于用户A是否含有某个元素的概率是50%-50%的。

实验

这篇论文对应的代码已经开源在github上,下面是验证方法:

$ git clone --recursive https://github.com/peihanmiao/OPRF-PSI.git
$ cd OPRF-PSI
$ bash compile

# Examples

$ ./bin/PSI_test -r 0 -ss 16 -rs 16 -w 609 -h 16 -hash 9 -ip 127.0.0.1
  & ./bin/PSI_test -r 1 -ss 16 -rs 16 -w 609 -h 16 -hash 9 -ip 127.0.0.1

$ ./bin/PSI_test -r 0 -ss 20 -rs 20 -w 621 -h 20 -hash 10 -ip 127.0.0.1
  & ./bin/PSI_test -r 1 -ss 20 -rs 20 -w 621 -h 20 -hash 10 -ip 127.0.0.1

运行的样本结果如下:

通过查看其源代码,我发现了其中一些工程上实现的细节。

  1. OT协议是使用libOTe库提供的方法。

  2. 矩阵A、B的传输过程并不是一次性发送出去的,因为这个矩阵的大小已经超过了TCP协议单次承载的最大载荷,因此在其实现中是将这个矩阵进行分组,多次发送的。正因为进行了分片操作,所以程序最后输出的空间开销实际上比理论上的开销要多了那么一点点,这部分内容我理解是多次传送所需要耗费的头部、首尾指针等。

  3. 理论上我们使用的矩阵是0、1作为元素的,但是C++中最小表示单位是字节(8 bit),因此代码中的矩阵实际上存储的基本单位是无符号字符类型,因此实际的列数是除以8的。也因为这样,在代码中作者使用了很多位运算技巧来找到矩阵D对应的黑点位置。

     for (auto i = 0; i < widthBucket1; ++i) {
         memset(matrixDelta[i], 255, heightInBytes);
     }
        
     for (auto i = 0; i < w; ++i) {
         for (auto j = 0; j < receiverSize; ++j) {
             auto location = (*(u32*)(transLocations[i] + j * locationInBytes)) & shift;
             matrixDelta[i][location >> 3] &= ~(1 << (location & 7));
         }
     }
    
  4. 作者使用伪随机函数生成了X数据集以及Y数据集,每个元素的长度是128-bit,其中这两个数据集的前100个元素是完全相同的,后面的所有元素是不同的。这个伪随机函数生成的随机数流是完全不同的,确保了集合中不存在重复元素。

     vector<block> senderSet(senderSize); 
     PRNG prng(oc::toBlock(123));
     for (auto i = 0; i < senderSize; ++i) {
         senderSet[i] = prng.get<block>();
     }
    
     vector<block> receiverSet(receiverSize); 
     PRNG prng(oc::toBlock(123));
     for (auto i = 0; i < 100; ++i) {
         receiverSet[i] = prng.get<block>();
     }
    	
     PRNG prng2(oc::toBlock(456));
     for (auto i = 100; i < receiverSize; ++i) {
         receiverSet[i] = prng2.get<block>();
     }
    

参考

  1. Melissa Chase, Peihan Miao: Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF. CRYPTO (3) 2020: 34-63

  2. 崔泓睿,刘天怡,郁昱,程越强,张煜龙,韦韬:多方安全计算热点-隐私保护集合求交技术(PSI)分析研究报告 (https://anquan.baidu.com/upload/ue/file/20190814/1565763561975581.pdf)

  3. 《联邦学习》电子工业出版社

  4. 《Introduction to Modern Cryptography》 Jonathan Katz and Yehuda Lindell

Search

    Table of Contents