Multi-Party Threshold Private Set Intersection with Sublinear Communication-2021:解读

记录阅读论文的笔记。

摘要#

总结：
（1）CRYPTO 2019:The Communication Complexity of Threshold Private Set Intersection-2019：解读提出任何阈值PSI得通信复杂度为Ω(T)Ω(T)；基于FHE的两方阈值PSI通信复杂度为O(T)O(T)，但计算消耗很大么；基于GC的了；两方阈值PSI得通信复杂度为O(T3)O(T3)，并给出了一个通信复杂度为O(T2)O(T2)的基于AHE的两方阈值PSI协议。

（2）本文和Multiparty Cardinality Testing for Threshold Private Set-2021：解读在同一年提出，难免相似。
（3）在本文中，研究多方阈值PSI的通信复杂度，分为两个功能：
第一，参与方检测数据集与交集的最大相差是否为TT？
即对于I=S∩I=S∩，判断|Si∖I|≤T|Si∖I|≤T，或|I|≥m−T|I|≥m−T是否成立？（mm是数据集大小）
关注的是交集（相同数据的个数）是否足够大！，记做FTPSI−intFTPSI−int。

第二，参与方检测并集与交集的最大相差是否为TT？
即判断|⋃ni=1Si∖I|≤T|⋃ni=1Si∖I|≤T是否成立？
关注的是差集（不同数据的个数）是否足够小！记做FTPSI−diffFTPSI−diff

这两个功能在两方下是等效的，在多方下不是。
因为在两方中，要求|⋃ni=1Si∖I|=2|Si∖I||⋃ni=1Si∖I|=2|Si∖I|，所以不用区分。在多方中，我们知道2|Si∖I|≤|⋃ni=1Si∖I|≤n.|Si∖I|2|Si∖I|≤|⋃ni=1Si∖I|≤n.|Si∖I|，因此和两方的不同！

（4）本文中，给出任何协议的通信复杂度为Ω(nT)Ω(nT)；在阈值FHE下的协议最大通信复杂度为O(nT)O(nT)，本文设计的协议的通信复杂度只依赖于（only数据），而不依赖集合的输入。
（5）在本文中，给出以上两个功能函数的通信复杂度的上限和下限。

其中TFHE是全同态加密方案，TAHE是加法同态性的加密方案；安全性是半诚实的。
下面是对通信复杂度的上限分析，阈值PSI一般分为两个阶段：
第一阶段：

主要就是进行cardinality testing，判断交集是否足够大，详细点说可以分为两种：
对于FTPSI−intFTPSI−int，即判断|I|≥m−T|I|≥m−T是否成立？，记做FCTest−diffFCTest−diff。

对于FTPSI−diffFTPSI−diff，即判断|⋃ni=1Si∖I|≤T|⋃ni=1Si∖I|≤T是否成立？，记做FCTest−diffFCTest−diff。

第二阶段：
如果交集足够大，即通过了cardinality testing，就会进入第二阶段，各方找到他们的差集Si∖ISi∖I。
该阶段只使用TAHE，通信复杂度为O(nT)O(nT)，再结合第一阶段（表2）就会得到最终的通信复杂度（表1）。

介绍#

1、PSI的应用：
（1）DNA测试和模式识别
（2）远程诊断
（3）僵尸网络检测
（4）在线广告
2、PSI模式：
（1）两方
（2）多方
（3）云辅助
3、PSI安全模型：
（1）半诚实
（2）恶意

设计结构#

这里也是多方参与的协议，使用的是星型拓扑结构（star network），即一个leader方（designated party）和其他方交互，该结构的优点就是，无需所有方都同时在线。用于分析通信复杂度上限时。

点对点结构（point-to-point），这是星型拓扑的扩展，在本文中用于分析通信复杂度下限时。

另外还有广播型场景：
。。。待补充

其他介绍#

两方阈值PSI#

在CRYPTO 2019中已经介绍很清晰了，使用的是AHE构造的两方阈值PSI，通信复杂度为˜O(T2)O˜(T2)。

亚线性通信PSI#

本文设计的多方阈值PSI可以用于设计多方PSI，其通信复杂度只与差值大小相关。具体说，对于多方阈值PSI，阈值T=20,...,2kT=20,...,2k，其通信复杂度是单个实例的logTlogT倍，所以实现了通信复杂度为亚线性（对于集合大小）的多方PSI。

单个实例是啥？

紧凑型MPC#

紧凑型的MPC，即通信复杂度不随函数的输入增长而增长。

当前发展#

1、CRYPTO 2019中最后给出扩展为多方的构想，但只要考虑了FTPSI−intFTPSI−int，首次使用TFHE用于cardinality testing，通信复杂度为O(nT)O(nT)，在求交阶段使用 MPC 协议来计算随机多项式，其中通信复杂度取决于 MPC 。
2、Multiparty Cardinality Testing for Threshold Private Set-2021：解读中给出了多方阈值PSI的方案，也同样没有介绍FCTest−diffFCTest−diff。

基础知识#

符号#

1、λλ是安全参数；poly(λ)poly(λ)是关于λλ的多项式函数；negl(λ)negl(λ)是不可忽略函数，即对于一个函数f(.)f(.)、任意的多项式p(.)p(.)和足够大的λλ，使得f(λ)<1/p(λ)f(λ)<1/p(λ)成立。
2、[x][x]，表示加密的xx。
3、˜O(x)=O(x.poly(x))O˜(x)=O(x.poly(x))：隐藏polylog因子。

多方计算的安全性#

UC安全参考：安全性证明

下面做简单描述：
ΠΠ是协议，nn个参与者，FF是理想函数。
1、真实世界执行
各方执行协议ΠΠ，可以调用功能函数GG，环境ZZ选择各方的输入，代替敌手，可以破坏参与方的任何集合以获得额外信息。[Z,Π,G][Z,Π,G]是真实世界中ZZ的输出

2、理想世界执行
nn个参与方将输入发送给理想函数FF，返回计算结果，其中SIMSIM作为理想世界中的敌手，可以模仿真实世界中执行中的环境ZZ，能够完全控制被腐败的参与者并模仿参与者对ZZ的view。[Z,SIM,F][Z,SIM,F]是理想世界中ZZ的输出

协议ΠΠ是安全的，需满足：对于任意的PPT的ZZ，都存在PPT的SIMSIM，满足：

TFHE#

本文中使用的是【Threshold cryptosystems from threshold fully homomorphic encryption-2018】

方案如下：

总结：
（1）这里的公钥和私钥都是多个
（2）这里的解密是部分解密，然后通过聚合全部解密结果才能完全恢复明文。

紧凑性#

如果一个同态加密方案的解密电路是独立于计算函数的，即密文的长度与计算电路的深度无关，则称该同态加密方案是紧凑的。

总结：
（1）这里的Eval和ParticalDecEval和ParticalDec都是同态计算，输出的计算密文与电路深度无关。

正确性#

正确性，就是检测计算后的密文解密和对明文计算一样。

安全性#

分为语义安全（Semantic Security）和模拟安全（Simulation Security）

1、语义安全

语义安全就是任意PPT的敌手不能区分任意两个明文的密文。

具体来讲：
（1）敌手任意模拟一个参与者SiSi，对于两个任意明文(m0,m1)(m0,m1)，发送(Si,pki,ski,(m0,m1)(Si,pki,ski,(m0,m1)给挑战者
（2）挑战者任选一个mbmb加密发给敌手
（3）敌手输出猜测值b′b′，若b=b′b=b′，则敌手获胜，输出1，否则，相反。

2、模拟安全

模拟安全，是存在一个模拟器SIM，对于任意PPT的敌手A，使得两个方案ExptTFHE.Real(1λ)和ExptTFHE.Ideal(1λ)在计算上是不区分的。

TAHE#

1、和TFHE不同之处：
（1）Eval中的计算电路C是线性的，即只能进行ax+b之类的计算
（2）只有加法同态性
2、给出常用的TAHE方案：

来源于：Scalable multi-party private set-intersection

（1）Paillier变体：https://github.com/niclabs/tcpaillier
（2）ElGamal变体：https://github.com/aistcrypt/Lifted-ElGamal

3、密文具有随机性，不可区分

引理#

总结：
（1）2.3说的是在计算V(x)时，所选的R(x)和编码后的多项式p(x)时互素的。
（2）2.4说的是若(p1(x),...,pn(x))是互素的，那么(p1‘(x),...,p′n(x))也是互素的，其中p′j(x)=p(x).(x−ri)。
（3）2.5说的是若(p1(x),...,pn(x))是互素的，且deg(pi(x))=α，则对于随机选取的(R1(X),...,Rn(X)（其deg(Rj(x))=β≥α），那么U(x)=∑ni=1(pi(x).Ri(x)也是随机的。

主要技术#

这里选用P1作为leader方（designated party）

基于TFHE的FCTest−int#

即使用TFHE去判断交集是否足够大！

（1）这里p(x)的分子分母（消去后的）的degree为m−|I|，如果m−|I|=|SA∖I|≤T，则deg(p(x))≤2T，即可以用2T+1个点值对插值出p(x)。
（2）求出p(x)后，就可以求出其分母pA∖I(x)，其根就是集合SA∖I

下面是具体的两方协议：

（1）通过2T+1个数组成2T+1个点值对，从而插值出有理函数p(x)
（2）这里使用的是FHE，通过同态的判断Enc(p(z))是否和pB(z)/Enc(pA(z))相等，决定两方数据集是否相似。为什么呢？因为若Enc(p(z))=pB(z)/Enc(pA(z))，则deg(p(x))≤2T，从而m−|I|=|SA∖I|≤T，则差集最大为T，两集合相似。

以上两方协议是CRYPTO 2019:The Communication Complexity of Threshold Private Set Intersection-2019：解读中给出的，下面根据这个两方协议，扩展为多方。

（1）扩展为多方后，就需要使用TFHE了
（2）决定多方数据集是否相似，还是通过判断Enc(p(z))是否和Dec(p2(z))+...+Enc(pn(z))/p1(z)相等。
（3）注意这里是Pi方加密，发给P1，在两方中，是P1加密，发送给其他方。

这样简单改造为多方是有问题的：分子分母中不属于交集的项也能消去！

（1）这里元素a不属于交集，但还是消去了。

如何解决呢？CRYPTO 2019中给出的方法是，加随机数！

这里给出的方法是加入随机数构成的随机项：

（1）在每一个多项式中加入一个随机项，这样不相同的元素就不会通过某些计算结合消去了。

基于TFHE的FCTest−diff#

即使用TFHE判断差集是否足够小！

（1）Pi与其他参与方Pi交互后都会插值出一个~pi(x)，从而可以得到pi∖1(x)和p1∖i(x)，所以能计算出差集D1,i=S1∖Si和Di,1=Si∖S1。
（2）这里存在一个等价关系：|⋃Si∖I|≤T≈|Si∖I|≤T≈deg(~pi(x))≤2T 。
（3）因为⋃Si∖I中的数据，存在两种情况，所以P1不仅需要计算出差集，还要判断|⋃Si∖I|和T的大小。

基于TAHE的FCTest−diff#

即使用TAHE判断差集是否足够小！
本文给出的方法能将两方的通信复杂度降为˜O(T)。

1、两方场景下：


（1）现在cardinality testing的问题是，判断deg(p(x))≤2T是否成立？CRYPTO 2019给出的方法判断p(x)是否是“稀疏”的（该思想来自【A local decision test for sparse
polynomials】），即通过判断汉克尔矩阵H的奇异性（判断方法来自【Secure linear algebra using linearly recurrent sequences】）
（2）该方法的通信复杂度为˜O(T2)。

2、该文中给出的方法：

（1）使用另外一种方法（half-GCD）去检测汉克尔矩阵奇异性（来自【Fast solution of Toeplitz
systems of equations and computation of pad´e approximants】），能将通信复杂度降低为˜O(T)。
（2）如何使用：Alice和Bob各自计算出矩阵的分享份Hi，然后通过2PC或者GC联合计算出H，再去判断奇异性。

3、扩展为多方的思路：

（1）首先要设计一个多项式f(x)，使其deg(f(x))=|⋃Si∖I|。
（2）然后在各方运算是线性的，各方可以从这个多项式中获取矩阵的分享份。
（3）最后各方执行MPC，检测矩阵的奇异性。

计算交集#

这部分是在cardinality testing通过后，如何计算交集。

1、两方场景

这是CRYPTO 2019中给出的方法

（1）Alice根据2T+1个点插值出p(x)。
（2）再根据f(x)=pB(x)/pA(x)=pB∖A/pA∖B，恢复出分母pA∖B
（3）但是不安全：Alice不仅可以恢复出分母，也能恢复出分子，泄漏Bob的数据。正如上面介绍的，这里给出的解决办法是加入噪音多项式V(x)：

这样deg(p′(x))≤3T，这里给出3T+1个点插值出p′(x)，此时Alice就不能从分子中得到额外的Bob信息了。
（4）重要的就是V(x)是如何构造出的来的！

2、多方场景

这部分是沿着CRYPTO 2019两方扩展为多方的思想构造的。

（1）这里要求各方Pi选取degree为T的n个随机多项式(Ri,1,...,Ri,n)
（2）然后P1也根据3T+1个点插值出p′(x)，进而得到分母，这样由于V(x)足够随机，不会泄漏其他方的数据，能得到交集。

3、存在的问题

（1）上述介绍多方场景，其通信复杂度为O(n2T)，存在的消耗主要是，各方Pi选取degree为T的n个随机多项式(Ri,1,...,Ri,n)。
（2）经过分析，各方只需要选取两个随机多项式就能达到效果，第一个多项式用于随机化自己插值出来的多项式，第二个用于随机化其他方插值出来的多项式。
（3）下面根据该思想，基于TFHE设计的协议通信复杂度可以降低为O(nT)

低通信量#

（1）在点对点网络模型下，多方阈值PSI的通信复杂度的下限为Ω(nT)
（2）在广播模型下，多方阈值PSI的通信复杂度的下限为Ω(Tlogn+n)

下面分析在点对点模型下的两种情况的通信复杂度下限。

1、求交集FTPSI−int

（1）意思是在一个能抵抗半诚实攻击的多方阈值PSI中，两两交互的通信复杂度为Ω(T)

（1）很明显，多个一起交互的总通信复杂度为Ω(nT)
2、求差集FTPSI−diff

这里说，FTPSI−diff和FTPSI−int不同之处是，前者是当|(X1∖X2)∪(X2∖X1)|≤T时，各方才会求交。【嗯，，为什么呢。。】

（1）意思是在一个能抵抗半诚实攻击的多方阈值PSI中，两两交互的通信复杂度为Ω(T)

（1）很明显，多个一起交互的总通信复杂度为Ω(nT)

基于TFHE的测试#

这部分，给出关于cardinality testing的两种协议，即FCTest−int测试交集是否足够大(大于m−T)，和FCTest−diff测试差集是否足够小（小于T）！

FCTest−int#

判断交集是否足够大！

（1）各方编码得到自己的多项式后，乘以一个随机项，以随机化分子分母，解决“分子分母可以相互消去不相同的项”的问题。
（2）leader方（P1）选取一个随机值z共享给其他方
（3）各方（不含leader）将2T+3个点和z带入到各自的多项式p′i(x)中，在加密得到得到[ei,j]和[e′i]发给leader
（4）leadre根据：

计算出2T+3个点值对：

然后leader根据这些点插值出[p∗(x)]。
（5）若deg([p∗(x)])≤2T+2，则p∗(x)=p(x)，所以这里需要判断p∗(x)=p(x)是否成立，这里是判断
p∗(z)和e′2+...+e′n/e′1是否相等？

下面分析一波正确性：

1、这是符合条件的，即交集足够大，|I|≥m−T

（1）经过相同项消去后，分子和分母的最大级数（degree）为T+1，所以p′(x)最大级数为2(T+1)，即需要2T+3个点才能插值出来。

2、这是不符合条件的，即交集不足够大，|I|<m−T


（1）对于分子和分母的级数，有(m−|I|+1)>(T+1)，（因为，|I|<m−T，说明差集大于T，即(m−|I|)>T），则p′(x)最大级数大于2(T+1)，即最小为2T+3，至少需要2T+4个点才能插值出来，这里只有2T+3点。

下面是通信量

（1）O(1)轮，通信量为O(nTpoly(λ))

总的来说，这里是想要判断交集是否足够大，即|Si∖I|≤T是否成立？规约到deg([p∗(x)])≤2T+2是否成立？再规约到判断p∗(z)和e′2+...+e′n/e′1是否相等？

这里留一个疑问：4-(b)中如何判断密态的p∗(z)和e′2+...+e′n/e′1是否相等？

FCTest−diff#

判断差集是否足够小！即判断|⋃Si∖I|<T是否成立，实现方法是各方与leader交互，leader知道两方差集的加密，根据判断所有差集的交集大小是不是不大于T来实现的。

（1）首先各方先将自己数据编码为多项式pi(x)，然后将2T+1个点和z带入得到ei,j和e′i（z是P1随机选取的）
（2）各方（除leader外）将ei,j和e′i加密，发给leader；leader就可以根据：

计算出2T+1个点(j,[ei,j/e′i])，从而插值出~p∗(x)，从而得到分子和分母，所以就能得到两方各自的差集[D∗i,1],[D∗1,i]。若deg(~p∗(x))≤2T，则~p∗(x)=˜p(x)；反过来说，只需要判断~p∗(x)=˜p(x)是否成立，就能判断deg(~p∗(x))≤2T？

这时z就上场了，leader通过判断~p∗(z)=e′i/e′1是否成立，进而判断deg(~p∗(x))≤2T？若相等，bi=1，否则为0
（3）leader得到了各方与自己相比的所有差集，这时需要判断所有差集并在一起的数量是否不大于T，若是，则b′=1，否则为0。
（4）最后leader将密态的b′和bi相乘得到密态的b，然后联合解密判断差集是否足够小！

总结#

• 给出了两种阈值判断标准：（1）交集足够大（2）差集足够小 时才去求交
• 分别基于TFHE和TAHE构造以上两种情况
• 基于TFHE的是基于CRYPTO 2019中的思想
• 该文章有程序实现：https://www.cnblogs.com/pam-sh/p/16479540.html
• 基于同态的还是太慢，通信复杂度没有较大提升。