Multiparty Cardinality Testing for Threshold Private Set-2021：解读

本文记录阅读该论文的笔记。

本文基于阈值加法同态加密方案提出了一个新的允许N$N$方检查其输入集的交集是否大于n−t$n-t$的IPSI方案，该协议的通信复杂度为O(Nt2)$O(N{t}^2)$。
注意：N$N$指的是多少个参与方、n$n$是输入集的大小、t$t$是预先设定的阈值，也是阈值。

该方案基于The Communication Complexity of Threshold Private Set Intersection-2019：解读进行的改进。
该协议可以用于各方知道交集很大，但不知道具体多大时，可以使用！

摘要#

（1）该协议的通信复杂度不依赖于输入集的大小，而取决于阈值t$t$的大小
（2）基于阈值的PSI协议分为两部分：

• 交集的势测试（Cardinality Testing ），即测试参与方的交集是否大于n−t$n-t$
• PSI：计算交集

介绍#

两方阈值PSI：

（1）双方先检测交集大小是否>n−t$>n-t$
（2）若满足，则求交（获取交集）；否则，什么也得不到（获取不到交集）

标准PSI和阈值PSI的对比：

• 标准的PSI更在乎交集，而不在乎交集的大小，而阈值PSI更关注交集的大小。
• 阈值PSI的通信量较少，只取决于阈值t$t$的大小；标准的PSI通信量取决于输入集合的大小。

阈值PSI现状：
只有以下方案进行了讨论：
（1）【Privatepool: Privacy-preserving ridesharing-2017】
（2）【An algebraic approach to maliciously secure private set intersection-2019】
（3）【The communication complexity of threshold private set intersection-2019】
其中只有（3）的通信复杂度不依赖于n$n$，方案是两方场景。
（4）【Multi-party threshold private set intersection with sublinear communication-2021】
这也是一个多方阈值PSI，使用FHE，通信复杂度为O(Nt)$O(Nt)$，也提出了一个TPKE加密方案实现了：只有当各方的交集足够大时，各方才能求交集。还可以秘密的计算汉克尔矩阵的行列式（矩阵大小的线性时间内）。

阈值PSI的应用：
（1）约会APP
（2）生物特征认证
（3）拼车【Privatepool: Privacy-preserving ridesharing 】
假设两个（或更多）方正在使用拼车应用程序，如果他们的路线有很大的交集，它允许他们共享车辆。然而由于隐私问题，他们不想公开他们的行程。阈值PSI可以解决该问题，各方可以联合执行一个阈值PSI协议，了解路线的交叉点，如果交叉点足够大，共享一辆车，否则，他们就不共享一辆车，也能保证用户的路线隐私。

阈值PSI#

当前的阈值PSI主要分为两步：
（1）Cardinality Testing：就是各方检测交集是否大于n−t$n-t$
（2）PSI：如果满足（1），则输出交集；否则没有输出

具体：

如果起始t=1$t=1$，则t$t$的取值范围有：1,2,4,8,...,t,2t$1,2,4,8,...,t,2t$

通信复杂只取决于t$t$的原因：

合适的阈值一定是2的次幂 ，如果交集大于n−t′$n-t^{\prime }$，则Cardinality Testing对于阈值t$t$就成功，因为t≥t′>t/2$t\ge t^{\prime }>t/2$，所以协议的通信复杂度只取决于阈值的大小。

---

解释有点牵强，或许我没理解
t′$t^{\prime }$是什么？

---

贡献#

（1）多方Cardinality Testing

• 较上面的Cardinality Testing，这里给出了满足多方的Cardinality Testing
• 通信复杂度为O(Nt2)$O(N{t}^2)$
• 并给出一些新的线性计算（linear algebra）：求密文矩阵相乘、求密文矩阵的秩、求密文矩阵的逆等

该协议在【Secure linear algebra using linearly recurrent sequences-2007】【Communication efficient secure linear algebra-2006】的（两方）基础上构建的多方阈值PSI。

（2）多方阈值PSI

这里也是将一个两方的协议改为多方。

回顾一下两方的情况：
两方Alice和Bob各有数据SA$S_A$和SB$S_B$，其大小都是n$n$，阈值t<<n$t<<n$，如果|SA∩SB|≥n−t$|S_A\cap S_B|\ge n-t$，则求出交集SA∩SB$S_A\cap S_B$。

我们方案基于【The communication complexity of threshold private set intersection-2019】论文，这是一个两方的阈值PSI协议：

（1）若交集大于n−t$n-t$
（2）计算交集
两方将数据编码到多项式中，得到PA(x)=(x−ai)...(x−an)$P_A(x)=(x-a_i)...(x-a_n)$和PB=(x−b1)...(x−bn)$P_B=(x-b_1)...(x-b_n)$在一个大的有限域上F$F$，其中ai∈SA,bi∈SB$a_i\in S_A,b_i\in S_B$，然后只要满足|SA∩SB|≥n−t$|S_A\cap S_B|\ge n-t$，则：

且deg(PA)=deg(PB)=t$deg(P_A)=deg(P_B)=t$，所以两方只需要在PA(x)/PB(x)=PA∖B(x)/PB∖A$P_A(x)/P_B(x)=P_{A\setminus B}(x)/P_{B\setminus A}$上计算O(t)$O(t)$个点。然后将这些点插值得到PA(x)/PB(x)$P_A(x)/P_B(x)$，然后求出分母PB∖A$P_{B\setminus A}$，继而求出交集多项式PA∖B(x)=PB(x)/PB∖A$P_{A\setminus B}(x)=P_B(x)/P_{B\setminus A}$

---

紧接上文问题：具体如何根据PA(x)/PB(x)$P_A(x)/P_B(x)$，然后求出分母PB∖A$P_{B\setminus A}$？

---

Bob不能恢复出分子PA∖B$P_{A\setminus B}$，否则方案就不安全了，所以这里使用Oblivious Linear Evaluation (OLE)技术用于“掩盖”分子项（随机化）。

该协议只有满足|SA∩SB|≥n−t$|S_A\cap S_B|\ge n-t$，才是安全的，否则就会泄露额外的信息，所以双方应该先执行Cardinality Testing操作，来保证协议是满足|SA∩SB|≥n−t$|S_A\cap S_B|\ge n-t$的。

扩展到多方的限制：


这里讲的是Cardinality Testing如何扩展为多方：

参与方先将数据编码到多项式中，得到QA(x)=xai+...+xan$Q_A(x)=x^{a_i}+...+x^{a_n}$和QB=xb1+...+xbn$Q_B=x^{b_1}+...+x^{b_n}$，其中ai∈SA,bi∈SB$a_i\in S_A,b_i\in S_B$，检测Q(x)=QA(x)−QB(x)$Q(x)=Q_A(x)-Q_B(x)$是否是一个稀疏多项式（sparse polynomial），若是，则判断集合(SA∪SB)∖(SA∩SB)$(S_A\cup S_B)\setminus (S_A\cap S_B)$是小集合（small），通信复杂度为O(t2)$O(t^2)$。
那问题来了：
（1）如何判断多项式是否时稀疏的？
（2）如何判断集合是小的？

如果将其扩展为多方，对于N$N$个参与者，有：Q˜(x)=(N−1)Q1(x)−Q2(x)−...−QN(x)$\tilde{Q}(x)=(N-1)Q_1(x)-Q_2(x)-...-Q_N(x)$，如果N$N$很小的话，那该多项式Q˜(x)$\tilde{Q}(x)$就是稀疏的，那我们要是能计算该多项式的稀疏性，那么Cardinality Testing协议的总通信量变为O((Nt)2)$O((Nt{)}^2)$。

主要方法#

1、安全线性代数（Secure Linear Algebra ）
来源【Secure linear algebra using linearly recurrent sequences 】
有两个参与方，一方有矩阵的加密Enc(pk,M)$Enc(pk,M)$，另一方有对应的解密私钥sk$sk$，他们想要对这个密文矩阵做运算（线性计算，linear algebra related ），比如：求逆矩阵的行列式、秩或者计算出x$x$，对于Mx=y$Mx=y$，给出加密的M,y$M,y$。

我们可以将该问题扩展到方，对于N个参与者P1,...,PN$P_1,...,P_N$，每人有一份私钥的分享值，此外P1$P_1$有一个加密的矩阵，目的是要对这个加密的矩阵做运算（线性计算，linear algebra related）。

我们发现可以将【secure linear algebra】协议扩展为多方场景，通过使用具有加法同态性的阈值PKE代替具有加法同态的PKE和GC代替来实现，所以该方案允许N方在阈值PKE下解决这个线性代数问题Mx=y$Mx=y$。

2、多方势检测（Cardinality Testing via Degree Test of a Rational Function ）
对于参与方编码的多项式PSi(x)=(x−a(i)1)...(x−a(i)n),i∈[1,N]$P_{S_i}(x)=(x-a_1^{(i)})...(x-a_n^{(i)}),i\in [1,N]$，有：

若交集∩Si$\cap S_i$大小大于n−t$n-t$，则deg(PS1∖(∩Si))=...=deg(PSN∖(∩Si))≤t$deg(P_{S_1\setminus (\cap S_i)})=...=deg(P_{S_N\setminus (\cap S_i)})\le t$。

以上是求交的方法！

所以Cardinality Testing有以下问题：
对于有理函数f(x)=P1(x)/P2(x)$f(x)=P_1(x)/P_2(x)$，能否安全的判断deg(P1(x))=deg(P2(x))≤t$deg(P_1(x))=deg(P_2(x))\le t$，进而通过插值O(t)$O(t)$个点得到f(x)$f(x)$？

我们发现，将V=(vi,f(vi))$V=(v_i,f(v_i))$和W=(wi,f(wi))$W=(w_i,f(w_i))$(2t$2t$个点值)，插值为多项式fV(x),fW(x)$f_V(x),f_W(x)$，满足：

另外，插值有理函数可以看作是求解线性方程组，所以通过前面介绍的“Secure Linear Algebra”，可以安全（不泄露额外信息）的计算“degree test”，换句话说，这能判断交集大小是否小于n−t$n-t$，同时不泄露额外信息。

3、多方计算交集

这里的方法可以看作是【The communication complexity of threshold private set intersection 】的推广。

各方将其数据进行编码为多项式PSi(x)=(x−a(i)1)...(x−a(i)n),i∈[1,N]$P_{S_i}(x)=(x-a_1^{(i)})...(x-a_n^{(i)}),i\in [1,N]$，并且知道交集大小>n−t$>n-t$，各方联合计算出有理函数(PS1+...+PSN)/PS1$(P_{S_1}+...+P_{S_N})/P_{S_1}$，然后插值O(t)$O(t)$个点值，P1$P_1$方恢复出分母，求出交集。

该方案和【The communication complexity of threshold private set intersection】的不同之处就是，将“OLE calls”换成了基于阈值的PKE（具有加法同态性），可以看成多方OLE的替换。

4、安全性
在UC框架下证明了Cardinality Testing的安全，但还存在一个问题，就是“secure linear algebra”协议不能证明是UC安全的，因为输入是在公钥加密的密文，在UC设置中，输入是来自其他地方。

使用Externalized UC框架解决该问题，在该框架下，安全的“linear algebra ideal functionalities”共享公钥，每人一个私钥的分享份，使用这种方法证明协议的安全性。

由于“secure linear algebra”协议是安全的，如果它们都共享相同的公钥，那么在“Cardinality Testing”中，我们只需要创建此公钥并共享，所以我们可以证明“Cardinality Testing”是UC安全的。

其他的证明方式：仅证明住主协议的安全性，而不单独证明每个字协议的安全性。

推荐参考：UC安全，接下来需要看Externalized UC！

基础#

S$S$是一个有限集合，x←S$x\leftarrow S$表示从S$S$中随机采样，|S|$|S|$表示S$S$的势（cardinality）；N$N$个参与者;给出两个不可区分的分布D1,D2$D_1,D_2$；安全参数λ$\lambda$

阈值的PKE#

主要介绍了密钥生成算法和判断是否为0的加密算法

UC框架和理想函数#

方案使用UC框架【A new paradigm for cryptographic protocols】分析安全性，在该协议中，只考虑半诚实敌手。

其中：

• Z$Z$是环境
• π$\pi$是协议
• A$A$是真实世界
• F$F$是理想函数
• SIM$SIM$是模拟器

理想情况下的基于阈值的多方PSI：

只有当交集够大时，各方才会求交集。

Externalized UC of Global Setup：
externalized UC emulation (EUC)来源于【Universally composable security with global setup】，这是全局设置（global setup）的UC框架（简单版）

多项式插值#

下面介绍使用一个随机多项式去“混淆/遮盖”一个级数小于t的多项式：

这种方式也可以用于多个多项式（多方），只要他们不共享一个因子（common factor）。

什么意思，不能约么？

下面介绍如何通过插值恢复出这个有理函数f(x)=P(x)/Q(x)$f(x)=P(x)/Q(x)$以及证明该函数是唯一的

其中P(x)$P(x)$的级数为m$m$，Q(x)$Q(x)$的级数为n$n$，则f(x)$f(x)$可一通过插值m+n+1$m+n+1$个点唯一的插值出f(x)$f(x)$，若P(x),Q(x)$P(x),Q(x)$是首一的（monic），则只需要m+n$m+n$个点。

给定集合V=(x,y)$V=(x,y)$，大小为m1+m2+1$m_1+m_2+1$，可以根据这V$V$个点唯一的插值出f(x)=P(x)/Q(x)$f(x)=P(x)/Q(x)$。

引理#

Oblivious Degree Test for Rational Functions#

下面给出一个多方协议下求线性计算Mx=y$Mx=y$，通信复杂度为O(t2kλN)$O(t^{2}k\lambda N)$。

多方求线性函数（Oblivious Linear Algebra）#

多方求加密矩阵乘#

功能是：

具体实现如下：
（1）初始化：各方Pi$P_i$，共享公钥pk$pk$，以及每方各有一份私钥分享份ski$s{k}_i$
（2）输入：P1$P_1$输入两个矩阵的加密Enc(pk,Ml),Enc(pk,Mr)$Enc(pk,M_l),Enc(pk,M_r)$,其中Ml,Mr∈Ft∗t$M_l,M_r\in F^{t\ast t}$
（3）输出：各方得到Enc(Ml∗Mr)$Enc(M_l\ast M_r)$

其思想就是：(a1+a2+a3)(b1+b2+b3)−a2(b1+b2+b3)−a3(b1+b2+b3)=a1b1$(a_1+a_2+a_3)(b_1+b_2+b_3)-a_2(b_1+b_2+b_3)-a_3(b_1+b_2+b_3)=a_1{b}_1$

---

但存在一个问题：（以三方为例）

最后得到的e=Enc(Ml∗Mr)+Enc(R(1)r∗R(1)r)+Enc(R(2)r∗R(2)r)+Enc(R(3)r∗R(3)r)$e=Enc(M_l\ast M_r)+Enc(R_r^{(1)}\ast R_r^{(1)})+Enc(R_r^{(2)}\ast R_r^{(2)})+Enc(R_r^{(3)}\ast R_r^{(3)})$，因为在上面框红处，没有自乘！

---

多方求加密矩阵的秩#

功能：

具体实现如下：

其中FOMM$F_{OMM}$表示的是以O(logt)批处理$O(logt)批处理$计算t$t$次乘法

---

不太懂

---

多方求线性函数#

思想是将问题约减为最小多项式。
M$M$是一个非奇异矩阵（non-singular matrix），也叫做满秩矩阵。
M,x,y$M,x,y$都是密文形式。
功能：

具体实现如下：

多方势检测（Oblivious Degree Test）#

功能：判断多方的交集数量t′$t^{\prime }$是否大于阈值t$t$，若满足，则输出1，否则输出0。

主要思想是：
在两个不同数据集上插值出有理函数，并检查两次实验的结果是否相同。
插值有理函数可以看作求解线性函数，因此可以使用“secure linear algebra”求解线性函数。
最后各方只需要安全的检查C(1)vC(2)w−C(1)wC(2)v=0$C_v^{(1)}{C}_w^{(2)}-C_w^{(1)}{C}_v^{(2)}=0$是否成立！

给定有理函数P(x)/Q(x)$P(x)/Q(x)$，其中P(x),Q(x)$P(x),Q(x)$有相同的级数，并给定两个集合V1,V2$V_1,V_2$，下面的协议secDT$secDT$是判断这个有理数函数的级数是否小于阈值t$t$：

下面具体来分析一波：
（1）初始化

• 各方共享公钥pk$pk$，且每人有一个私钥份ski$s{k}_i$；
• 假设各方可以正常执行理想函数：FORank,FOLS,FOMM,FDecZero$F_{ORank},F_{OLS},F_{OMM},F_{DecZero}$；
• 各方共享一组随机数(α1,...,α4t+2$({\alpha }_1,...,{\alpha }_{4t+2}$；

（2）参与方P1$P_1$输入
输入：((α1,Enc(pk,f1)),...,(α4t+2,Enc(pk,f4t+2)))$(({\alpha }_1,Enc(pk,f_1)),...,({\alpha }_{4t+2},Enc(pk,f_{4t+2})))$，其中fi=P1(αi)/P2(αi)$f_i=P_1({\alpha }_i)/P_2({\alpha }_i)$，P1(x),P2(x)$P_1(x),P_2(x)$是两个级数为t′$t^{\prime }$的多项式

（3）P1$P_1$设置
将P1$P_1$的输入((α1,Enc(pk,f1)),...,(α4t+2,Enc(pk,f4t+2)))$(({\alpha }_1,Enc(pk,f_1)),...,({\alpha }_{4t+2},Enc(pk,f_{4t+2})))$拆分为两部分(αj,Enc(pk,fj))j∈[2t+1]=(vj,Enc(pk,fv,j)))j∈[2t+1]$({\alpha }_j,Enc(pk,f_j){)}_{j\in [2t+1]}=(v_j,Enc(pk,f_{v,j})){)}_{j\in [2t+1]}$和(αj,Enc(pk,fj))j∈(2t+2,...,4t+2)=(wj,Enc(pk,fw,j)))j∈[2t+1]$({\alpha }_j,Enc(pk,f_j){)}_{j\in (2t+2,...,4t+2)}=(w_j,Enc(pk,f_{w,j})){)}_{j\in [2t+1]}$。

所以得到了4t+2$4t+2$对点值(vj,Enc(pk,fv,j)j∈[2t+1]$(v_j,Enc(pk,f_{v,j}{)}_{j\in [2t+1]}$和(wj,Enc(pk,fw,j)j∈[2t+1]$(w_j,Enc(pk,f_{w,j}{)}_{j\in [2t+1]}$。

由上面的点值构造两个密态线性系统：

其中r=(v,w)$r=(v,w)$，Mr$M_r$是一个维数为2t+1$2t+1$的方阵，yr$y_r$是一个长度为2t+1$2t+1$的向量。

这样就得到了加密的Mv,yv$M_v,y_v$和Mw,yw$M_w,y_w$。
（4）各方联合计算
计算：Enc(pk,rank(Mr)−rank([Mr||y]))$Enc(pk,rank(M_r)-rank([M_r||y]))$，如果结果不为0，则停止协议，其中使用了两次FORank$F_{ORank}$和FDecZero$F_{DecZero}$。

即参与方联合测试Enc(pk,rank(Mv)−rank([Mv||yv]))$Enc(pk,rank(M_v)-rank([M_v||y_v]))$和Enc(pk,rank(Mw)−rank([Mw||yw]))$Enc(pk,rank(M_w)-rank([M_w||y_w]))$解密后是否为0，若为0，则继续。
（5）各方联合计算
利用FOLS$F_{OLS}$计算上面的两个线性函数，每方得到Enc(pk,(c(1)v||c(2)v))$Enc(pk,(c_v^{(1)}||c_v^{(2)}))$和Enc(pk,(c(1)w||c(2)w))$Enc(pk,(c_w^{(1)}||c_w^{(2)}))$，其中Mr[c(1)r,c(2)r]=yr,r∈(v,w)$M_r[c_r^{(1)},c_r^{(2)}]=y_r,r\in (v,w)$；c(1)r$c_r^{(1)}$和c(2)r$c_r^{(2)}$各是长度为t+1$t+1$和t$t$的向量。

这时各方能根据Mr[c(1)r,c(2)r]=yr,r∈(v,w)$M_r[c_r^{(1)},c_r^{(2)}]=y_r,r\in (v,w)$由(yv,Mv)$(y_v,M_v)$得到密态的c(1)v||c(2)v$c_v^{(1)}||c_v^{(2)}$，(yw,Mw)$(y_w,M_w)$得到密态的c(1)w||c(2)w$c_w^{(1)}||c_w^{(2)}$。
（6）各方联合计算
计算出：C(1)v(x)=∑tj=0c(1)v,jxt−j$C_v^{(1)}(x)=\sum _{j=0}^t{c}_{v,j}^{(1)}{x}^{t-j}$，C(2)v(x)=xt+∑tj=0c(2)v,j−1xt−j$C_v^{(2)}(x)=x^t+\sum _{j=0}^t{c}_{v,j-1}^{(2)}{x}^{t-j}$和C(1)w(x)=∑tj=0c(1)w,jxt−j$C_w^{(1)}(x)=\sum _{j=0}^t{c}_{w,j}^{(1)}{x}^{t-j}$，C(2)w(x)=xt+∑tj=0c(2)w,j−1xt−j$C_w^{(2)}(x)=x^t+\sum _{j=0}^t{c}_{w,j-1}^{(2)}{x}^{t-j}$

最终计算出密态的z$z$。

（7）判断
各方使用FDecZero$F_{DecZero}$检查z$z$是否等于0（即对z$z$解密）。如果是，输出0；如果不是，输出1。

优化#

我们考虑在对插值生成f(x)=P(x)/Q(x)$f(x)=P(x)/Q(x)$，当Q(αi)=P(αi)=0$Q({\alpha }_i)=P({\alpha }_i)=0$时，我们就不能求f(x)$f(x)$了。

解决办法就是，去掉该点：
使得P˜(x)=P(x)/(x−αi),Q˜(x)=Q(x)/(x−αi),f(αi)=P˜(αi)/Q˜(αi)$\tilde{P}(x)=P(x)/(x-{\alpha }_i),\tilde{Q}(x)=Q(x)/(x-{\alpha }_i),f({\alpha }_i)=\tilde{P}({\alpha }_i)/\tilde{Q}({\alpha }_i)$

具体来讲，就是计算出点值对(αi,Enc(pk,P1(αi)/(x−αi))$({\alpha }_i,Enc(pk,P_1({\alpha }_i)/(x-{\alpha }_i))$，(αi,Enc(pk,P2(αi)/(x−αi)))$({\alpha }_i,Enc(pk,P_2({\alpha }_i)/(x-{\alpha }_i)))$。

这里的P1(),P2(X)$P_1(),P_2(X)$指的是P(x),Q(x)$P(x),Q(x)$

然后再分别构造出Enc(pk,Mr),Enc(pk,yr)$Enc(pk,M_r),Enc(pk,y_r)$，后面的不变。

另外协议也能推广到deg(P(x))≠deg(Q(x))$deg(P(x))\ne deg(Q(x))$的情况。

多方阈值PSI#

该协议的重点就是cardinality test protocol，能够安全的判断N方数据的交集和阈值的大小关系。

安全的势检测（Secure Cardinality Testing）#

1、理想功能

2、具体实现

总结一下：
（1）各方先各自将数据编码为多项式，然后求出4t+2$4t+2$个点值，加密这些点，得到4t+2$4t+2$个密态值Enc(pk,ri∗Pi(αj))$Enc(pk,r_i\ast P_i({\alpha }_j))$，广播出去。
（2）P1$P_1$得到4t+2$4t+2$个c(j)i$c_i^{(j)}$，计算得到d(j)$d^{(j)}$，形成密态点值对(αj,d(j))$({\alpha }_j,d^{(j)})$，并和私钥sk1$s{k}_1$一起发送给理想函数FSDT$F_{SDT}$。
（3）其他参与方P2,...,PN$P_2,...,P_N$也将各自的私钥ski$s{k}_i$发送给理想函数FSDT$F_{SDT}$，从而判断分子P1(x)$P_1(x)$和分母P2(x)$P_2(x)$的级数是否最大为t$t$，然后输出结果。

完整的多方阈值PSI协议#

在该协议中，通过使用TPKE扩展了之前的方案，具体协议如下：

总结一下：
（1）各方先将数据发送给理想函数FMPCT$F_{MPCT}$，检测交集大小和阈值的大小关系。
（2）再通过理想函数FGen$F_{Gen}$生成密钥：各方共享公钥pk$pk$，各自有一个私钥份ski$s{k}_i$。
（3）各方执行：

• 将数据Si$S_i$编码为多项式Pi(x)$P_i(x)$，计算出3t+1$3t{+}_1$个点值Pi(αj)$P_i({\alpha }_j)$。
• 采样Ri(x)$R_i(x)$，使得deg(Ri(x))=t$deg(R_i(x))=t$。
• 加密：c(j)i=Enc(pk,Ri(αj)∗Pi(αj))$c_i^{(j)}=Enc(pk,R_i({\alpha }_j)\ast P_i({\alpha }_j))$，然后广播出去。

（4）P1$P_1$将收到的对应的密文相加得到3t+1$3t+1$个值d(j)=∑Nic(j)i$d^{(j)}=\sum _i^N{c}_i^{(j)}$，再将其广播出去。
（5）联合解密出V(j)=Dec(sk,d(j))$V^{(j)}=Dec(sk,d^{(j)})$。
（6）P1$P_1$计算点V˜(j)=V(j)/P1(αj)${\tilde{V}}^{(j)}=V^{(j)}/P_1({\alpha }_j)$，得到点值对(αj,V˜(j))$({\alpha }_j,{\tilde{V}}^{(j)})$，将其插值出函数V˜(j)(x)${\tilde{V}}^{(j)}(x)$，再恢复出分母PS1∖(∩Si)(x)$P_{S_1\setminus (\cap S_i)}(x)$。
（7）P1$P_1$根据自己数据S1=(a(1)1,...,a(n)1)$S_1=(a_1^{(1)},...,a_1^{(n)})$计算出PS1∖(∩Si)(a(j)1)$P_{S_1\setminus (\cap S_i)}(a_1^{(j)})$，根据PS1∖(∩Si)(a(j)1)≠0$P_{S_1\setminus (\cap S_i)}(a_1^{(j)})\ne 0$，判断a(j)1$a_1^{(j)}$是否在交集中。
（8）广播交集。

在这里给出了详细如何根据PS1∖(∩Si)(x)$P_{S_1\setminus (\cap S_i)}(x)$，计算出交集！

正确性证明：

这样就能根据3t+1$3t+1$个点插值出V˜(j)(x)${\tilde{V}}^{(j)}(x)$，再“恢复”出分母PS1∖(∩Si)(x)$P_{S_1\setminus (\cap S_i)}(x)$，进而带入数据元素判断是否为交集元素。

总结#

1、关键点“cardinality test protocol”，也是最难理解的
2、如何根据f(x)$f(x)$恢复出分母？

---