隐私求交| Simple, Fast Malicious Multiparty Private Set Intersection
The following article is from 隐私计算研习社 Author 云波
Introduction
Private Set Intersection即隐私集合求交集，简写为PSI，是安全多方计算中常见的一种协议，用于多个参与方共同完成求得各自隐私集合的交集。简单地说，现在有个参与方,每一方都有一个私有集合，这个参与方希望得知他们的集合里有哪些公共元素。在某些应用里也会有寻找共同好友之类的服务，但往往会直接用私有集合求交集，这并不是参与方们可接受的，他们的诉求是在不暴露自己隐私集合的前提下，求出这个集合的交集，即。
两方PSI随着多年的发展已十分成熟，许多协议能达到的速度已经比肩通过交换哈希值来求交集的朴素但不安全的办法。因此文章将重点放在多方PSI的研究上，以合谋问题为主线，给出了从原始协议到最终协议的完整构造过程。此外，文章对于其他优秀多方PSI方案的梳理也是十分详尽的。
Overview of the Techniques
文章的目标是构造一个恶意的可拓展PSI协议，使用的主要工具是oblivious programmable PRF (OPPRF) 和 oblivious key-value store (OKVS)。协议的核心组件是OKVS，故对其进行简要的介绍。
现有两方和，手头上有一个包含个键值映射的集合，(同)表示key，一般是有实际意义的；(同)则是（伪）随机值，可以带入python的字典进行理解。希望能够得到这个映射集合，但他并不想暴露自己所选用的。
key-value store(KVS)是一种数据结构，它提供了两个算法，名曰和。能够将转化为一个object （或以可忽略的概率输出）；则可以使用和一个key 来得到一个输出值，满足性质：若有，则；否则是一个随机值。如果将看成一个点集，将其进行拉格朗日插值可以得到一个阶多项式，即为多项式的系数，自然地，有。当然，实际应用时并不会使用这种方式，更多细节可以参考PaXoS[^1]，文章的实现也基于PaXoS(一种具体的OKVS实现)完成。
现在考虑这个映射集合的取值，选用随机值能够确保他人在获取后无法判断的选取情况，从上面的例子可以看出，会因为的随机性而变为一条随机的曲线。用更为形式化的语言来描述,考虑实验：
对于：均匀选取。 返回。
如果对于任意两个大小为的和任意的PPT敌手，有
则称一个KVS是不经意的(oblivious)。
使用OKVS就能完成他的目的，他可以将得到的同时发给若干个人，以达到某种程度上对于的共享。
文章的主线是关于合谋问题的讨论，具体地可以分为无合谋(即腐化方人数 )和有合谋(即腐化方人数)两种情况。我们主要介绍的是半诚实的协议，恶意的协议在半诚实协议的基础上直接添加随机预言机就行了，也就是在所有使用集合元素的地方，都用来替换。
我们先从无合谋时开始进行分析，现假设有三方，他们分别有三个集合记为，大小均为。随机生成一个PRF的密钥，并根据自己的集合（这里集合中元素的上标表示它所属的参与方，即，下标表示在集合中的位置）生成一个键值对集合，拉出来单个键值对看，就是集合中的每个元素映射到它自身的伪随机函数值，那么可以用OKVS的算法将转换为一个object 。现在，选择将交给，将交给。到目前为止，各方对于的了解程度是怎样的？只知道一个密钥，对一无所知；好像比知道的多一些，因为他得到的是由和有密切关系的生成的，但所限于OKVS这一结构，不会暴露键的取值，故而也无从得知的信息。
继续往下，会用对自己的集合进行一次转换，以得到新集合；则会用算法对集合进行一次转换，得到新集合。我们以一个在交集中的元素的视角分析，它在中会变为，在中会变为，由推知，可以看出，交集中的元素以另一种形式被保存在两个新集合中并且仍属于两个新集合的交集。那么很自然地，只要对两个新集合再求一次交集，得到的交集结果形如，再求一次逆就得到了原本的模样，而现有的两方PSI是十分成熟和高效的。
这就是整篇文章中所有协议的雏形，自然存在不少问题，之后的改进都据此展开，所谓“见微知著，识人心智”，这里看懂了，后面的也就水到渠成了，但是这个渠是怎么通的，也是文章一步步带着我们思考的一条线。
我们试着用这个简单的协议来解决有合谋的状况。假设合谋，则可以将交给。当域的范围很小时，会尝试猜测中是否有某个元素，他可以计算和，如果二者相等则有，即使不在交集中，但它的存在仍被所获知，当整个域被遍历后，便可以得到。除此之外，还有一些漏洞在后续改进时会提到。
PSI with no collusion
3.1 A Recursive Construction with 𝑂(𝑛) rounds
我们先看如何将这个原始的三方协议扩展至n方的情形。原始协议是将三方PSI转化为两方PSI，那么对于n方PSI，可以试着将其用类似的方式转化为n-1方PSI。对于，可以将OKVS的给他们，这样他们只需要和执行相同的操作就行，后续转化为再利用新集合交集，如图1所示。
图 1
上述简单的方案有一个明显的问题，假设是恶意敌手，它在生成OKVS时可以使用一个假的键值对，其中且。这样会使得在求交集时，会出现在交集集合中，但其实并不是交集中的元素。一个简单的例子如图2所示，可以看到使用了这个键值对，这导致原本和中应该出现的变为了，最后会得出是交集中元素的错误结果，这让获知了他不应该知道的两条信息：①.中有元素；②.和中有元素。
图 2
针对上述问题，文章给出了一个简单的改进方法，即在生成新集合时，映射方式由 和 改为和。这样一来，例子中的元素为，和的元素为，这样自然不会出现在最终的交集结果中。此外，这也使得求交过程更为简单，因为在得到的交集结果后(如例子中是)，直接取结果前一段就行了（无需求逆）。修改后的协议示意图如图3所示。
图 3
递归算法是有终点的，现在来看文章中所用的两方PSI协议(Kamara et al.[^2])，这里会借助不可信的服务器(在里选一个充当)来完成求交的工作，选择借助第三方来求交是因为现在的场景下假设没有合谋发生，此时这种协议的效率是最高的。先来看基础协议，由来生成密钥，并将发送给，随后和分别使用来生成新集合并交给服务器，映射方式为，最后由服务器求交并将交集分别发给和，求一下逆就能够得到原始交集结果了，基础协议示意如图4所示。
在改进协议时，有以下几个考虑点：
服务器恶意删除某个交集元素
为了防止服务器删除交集中的某个元素x， 会将中的每个元素重复次，即令。此时，为了删除元素， 服务器需要同时删除在中对应的个值，而由于这些都是伪随机值，服务器无法精准的删除它们，也就无法达到目的。
服务器将所有交集元素删除，返回空集或直接将某一方提供的集合作为最终的交集结果返回。
会事先选定三个大小均为的集合(互不相交且与的交集也为空)，并将它们交给。会将集合改为(已经做过上一点中的操作)，会将集合改为，最后得到新集合，协议示意如图5所示。在收到交集后，会做以下判断，如果满足某一条件则中止：
或。 和使得 且 。
图 5
以上就是基础递归协议的简要介绍。
3.2 Reducing to 𝑂(1) Rounds
递归协议很明显是需要轮的，要降低轮次，文章中的思路是将求交工作交给和来做。具体的方式如下(示意图见图6和图7)：首先由来生成并分别发送给，再将 作为键值对集合(包含个键值对)来生成OKVS 。键值对中key是的第个元素， value是分别用刚生成的密钥求取的伪随机函数值的异或和。随后会发送给。以上部分为第一轮。
在第二轮中，各自计算 并将发送给。
图 6
可以求出新集合。
如果中的某个元素，那么其在中对应的元素为。
可以求出新集合。
如果中的某个元素，那么其在中对应的元素为。
和之前类似，和会将和作为输入执行一次前面提到的两方PSI(文章中提到执行两方PSI需要两轮，加上前面说的两轮，总共需要四轮)，得到交集后，输出最终的交集结果 。
图 7
尽管上述协议大幅度减少了协议的轮次，但由于整个设定是在无合谋的环境中，因此以上两个协议其实都不抗合谋攻击。在递归构造中，如果与合谋， 可以将发送给，可以用任意计算 (OKVS对于的访问次数没有限制)，并与进行比较，从而判断是否属于 。在第二个构造中，如果与合谋，可以将发送给，可以用任意计算，并与进行比较，从而判断是否属于 。当集合取值的域较小时，合谋方通过暴力枚举便能获知其他诚实方的隐私集合。类似地，与合谋也能得到的信息。
PSI with arbitrary collusion
4.1 ZeroXOR
突然冒出来这样一个协议ZeroXOR，它是构造最终方案的一个小组件。先看功能：
输入：来自的键值对集合。为了方便说明，记表示键的集合。
协议要做的事情是找到同时满足以下两个条件的所有键：
在各个键值对集合中对应的value的异或和为0。
举个例子，如图8所示，键满足条件1，对应的value分别为1,1,0，异或和为0
对应的value分别为2,2,2，异或和为2，因此是满足要求的键。
图 8
4.1.1 ZeroShare
在介绍ZeroXOR的实现方式之前，需要再介绍一个协议ZeroShare，如图9。首先，由来生成密钥，对于来说，他需要为之后的每个参与方生成一个密钥，即，并发送给对应的参与方。那么在密钥生成和分发工作完成后，就会拥有一个密钥集合(大小均为)，很容易看出，装着的是与其他所有参与方之间的密钥，其中的密钥要么是为他之后的参与方生成，要么是之前的参与方为他生成的密钥。对于，会计算，前半段表示用来自之前参与方生成的密钥所求伪随机函数的异或和；后半段表示用来自为他之后参与方所生成的密钥所求伪随机函数的异或和；合起来看就是用里的每个密钥分别求的伪随机函数值，再异或起来。对于同一个，个参与方都用来求一下这样的，最后再求异或和，现在假设对于，那么中会出现一次，中也会出现一次，两两配对求异或之后就为0了，以此类推，可得。能这样做的前提是相同，如果使用计算，那么得到的是，。
图 9
4.1.2 ZeroXOR
现在我们知道ZeroShare这个协议能让同一个对应的的异或和为0。ZeroXOR从接受到的输入是键值对集合，那么对于每个键都可以生成，根据刚才的分析，若，则有。做完这一步以后，就分别与执行一次OPPRF协议，其中作为发送方，输入是点集，得到的密钥未在图10中标出。作为接收方，输入是次询问 (里的所有元素)，能够得到对应的次回答 (这里上标是表示与执行OPPRF协议的是)，如果，则 (表示在中的位置)；反之是一个伪随机值。
图 10
执行完次OPPRF协议后，输出满足的。从图11的分析可以看出，如果满足ZeroXOR的条件1，那么的计算结果为。当时，也就说明满足ZeroXOR的条件2了，这样就会被筛选出来了。
图 11
4.2 PSI with collusion
首先要做的是划分参与方，设为腐化方的数量，，将划成一部分，划成一部分，这一部分的参与方数量正好为，自成一派。分别为的每个参与方生成一个密钥并发送给对应的参与方，比如会为生成密钥并发给，也会为生成密钥并发给，以此类推，示意图见图12。经过上述操作后，除了以外的参与方都有一个密钥集合，的密钥都是自己生成的，的密钥都是从那里收来的，具体的值可以看图12。
图 12
接下来，会计算，键值对中key是中的元素，value是用拥有的密钥来对计算伪随机函数值，再求异或和的结果。随后会被发送给枢纽。计算一个键值对集合，key是中的某个元素，value是，是刚从那里收到的。若，则，这一串东西其实就是用拥有的所有密钥对求伪随机函数值，再全部异或起来的结果。
对于，也会计算一个键值对集合，key是中的某个元素，value是，用到的密钥都是从那里收到的。接下来这个参与方执行一次ZeroXOR协议，得到的结果就是我们想要的交集结果。这是为什么呢？不妨假设。首先， 说明满足ZeroXOR协议的第一个条件；而，说明的键值对集合中有键值对。中对应的value求异或和的结果为。可以看到，前半部分用的所有密钥都是生成的且仅使用过一次，而后半部分的密钥也都是来自的，只不过使用者是。如果从公式上也很容易看出互换位置前后两部分是相等的。这与之前ZeroShare的思想是类似的，每个密钥都使用了两次，使得整个异或和为0。简图见图13。
图 13
最后的问题是这个方案为什么能够抗任意数量的合谋，因为协议巧妙地利用了合谋方的数量来划分参与方。不妨命名为第一集团，为第二集团(大小为)，为枢纽。回看前面的合谋攻击，都是根据和来推断出生成者的集合信息，也就是说要被拿下，中键值对的形式是，如果想要推断的信息，他必须凑齐，这就需要第二集团都配合他，这样合谋方数量就达到了，不满足假设条件，因此上述合谋攻击无法成立。
参考文献
[1]: Pinkas B, Rosulek M, Trieu N, et al. PSI from PaXoS: fast, malicious private set intersection[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2020: 739-767.
[2]: 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.
[3]: Nevo, O., Trieu, N., & Yanai, A. (2021). Simple, Fast Malicious Multiparty Private Set Intersection. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security.
本文作者：云波
知乎链接：https://zhuanlan.zhihu.com/p/499645095
隐私计算头条周刊（3.6-3.12）
中国移动牵头定义【“1”个技术底座+“X”个厂商算法】隐私计算平台