记录阅读论文的笔记。
摘要
总结：
（1）CRYPTO 2019:The Communication Complexity of Threshold Private Set Intersection-2019：解读提出任何阈值PSI得通信复杂度为(Omega(T))；基于FHE的两方阈值PSI通信复杂度为(O(T))，但计算消耗很大么；基于GC的了；两方阈值PSI得通信复杂度为(O(T^3))，并给出了一个通信复杂度为(O(T^2))的基于AHE的两方阈值PSI协议。
（2）本文和Multiparty Cardinality Testing for Threshold Private Set-2021：解读在同一年提出，难免相似。
（3）在本文中，研究多方阈值PSI的通信复杂度，分为两个功能：
第一，参与方检测数据集与交集的最大相差是否为(T)？
即对于(I=S_{cap})，判断(|S_i setminus I|leq T)，或(|I|geq m-T)是否成立？（(m)是数据集大小）
关注的是交集（相同数据的个数）是否足够大！，记做(F_{TPSI-int})。
第二，参与方检测并集与交集的最大相差是否为(T)？
即判断(|bigcup_{i=1}^{n}S_isetminus I|leq T)是否成立？
关注的是差集（不同数据的个数）是否足够小！记做(F_{TPSI-diff})
这两个功能在两方下是等效的，在多方下不是。
因为在两方中，要求(|bigcup_{i=1}^{n}S_isetminus I|=2|S_isetminus I|)，所以不用区分。在多方中，我们知道(2|S_isetminus I|leq |bigcup_{i=1}^{n}S_isetminus I|leq n.|S_isetminus I|)，因此和两方的不同！
（4）本文中，给出任何协议的通信复杂度为(Omega(nT))；在阈值FHE下的协议最大通信复杂度为(O(nT))，本文设计的协议的通信复杂度只依赖于（only数据），而不依赖集合的输入。
（5）在本文中，给出以上两个功能函数的通信复杂度的上限和下限。
其中TFHE是全同态加密方案，TAHE是加法同态性的加密方案；安全性是半诚实的。
下面是对通信复杂度的上限分析，阈值PSI一般分为两个阶段：
第一阶段：
主要就是进行cardinality testing，判断交集是否足够大，详细点说可以分为两种：
对于(F_{TPSI-int})，即判断(|I|geq m-T)是否成立？，记做(F_{CTest-diff})。
对于(F_{TPSI-diff})，即判断(|bigcup_{i=1}^{n}S_isetminus I|leq T)是否成立？，记做(F_{CTest-diff})。
第二阶段：
如果交集足够大，即通过了cardinality testing，就会进入第二阶段，各方找到他们的差集(S_isetminus I)。
该阶段只使用TAHE，通信复杂度为(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，通信复杂度为(widetilde{O}(T^2))。
亚线性通信PSI
本文设计的多方阈值PSI可以用于设计多方PSI，其通信复杂度只与差值大小相关。具体说，对于多方阈值PSI，阈值(T=2^0,...,2^k)，其通信复杂度是单个实例的(logT)倍，所以实现了通信复杂度为亚线性（对于集合大小）的多方PSI。
单个实例是啥？
紧凑型MPC
紧凑型的MPC，即通信复杂度不随函数的输入增长而增长。
当前发展
1、CRYPTO 2019中最后给出扩展为多方的构想，但只要考虑了(F_{TPSI-int})，首次使用TFHE用于cardinality testing，通信复杂度为(O(nT))，在求交阶段使用 MPC 协议来计算随机多项式，其中通信复杂度取决于 MPC 。
2、Multiparty Cardinality Testing for Threshold Private Set-2021：解读中给出了多方阈值PSI的方案，也同样没有介绍(F_{CTest-diff})。
基础知识
符号
1、(lambda)是安全参数；(poly(lambda))是关于(lambda)的多项式函数；(negl(lambda))是不可忽略函数，即对于一个函数(f(.))、任意的多项式(p(.))和足够大的(lambda)，使得(f(lambda)<1/p(lambda))成立。
2、([x])，表示加密的(x)。
3、(widetilde{O}(x)=O(x.poly(x)))：隐藏polylog因子。
多方计算的安全性
UC安全参考：安全性证明
下面做简单描述：
(Pi)是协议，(n)个参与者，(F)是理想函数。
1、真实世界执行
各方执行协议(Pi)，可以调用功能函数(G)，环境(Z)选择各方的输入，代替敌手，可以破坏参与方的任何集合以获得额外信息。([Z,Pi,G])是真实世界中(Z)的输出
2、理想世界执行
(n)个参与方将输入发送给理想函数(F)，返回计算结果，其中(SIM)作为理想世界中的敌手，可以模仿真实世界中执行中的环境(Z)，能够完全控制被腐败的参与者并模仿参与者对(Z)的view。([Z,SIM,F])是理想世界中(Z)的输出
协议(Pi)是安全的，需满足：对于任意的PPT的(Z)，都存在PPT的(SIM)，满足：
TFHE
本文中使用的是【Threshold cryptosystems from threshold fully homomorphic encryption-2018】
方案如下：
总结：
（1）这里的公钥和私钥都是多个
（2）这里的解密是部分解密，然后通过聚合全部解密结果才能完全恢复明文。
紧凑性
如果一个同态加密方案的解密电路是独立于计算函数的，即密文的长度与计算电路的深度无关，则称该同态加密方案是紧凑的。
总结：
（1）这里的(Eval和ParticalDec)都是同态计算，输出的计算密文与电路深度无关。
正确性
正确性，就是检测计算后的密文解密和对明文计算一样。
安全性
分为语义安全（Semantic Security）和模拟安全（Simulation Security）
1、语义安全
语义安全就是任意PPT的敌手不能区分任意两个明文的密文。
具体来讲：
（1）敌手任意模拟一个参与者(S_i)，对于两个任意明文((m_0,m_1))，发送((S_i,{pk_i,sk_i},(m_0,m_1))给挑战者
（2）挑战者任选一个(m_b)加密发给敌手
（3）敌手输出猜测值(b')，若(b=b')，则敌手获胜，输出1，否则，相反。
2、模拟安全
模拟安全，是存在一个模拟器SIM，对于任意PPT的敌手(A)，使得两个方案(Expt_{TFHE.Real}(1^{lambda }))和(Expt_{TFHE.Ideal}(1^{lambda }))在计算上是不区分的。
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说的是若((p_1(x),...,p_n(x)))是互素的，那么((p_1‘(x),...,p_n’(x)))也是互素的，其中(p_j'(x)=p(x).(x-r_i))。
（3）2.5说的是若((p_1(x),...,p_n(x)))是互素的，且(deg(p_i(x))=alpha)，则对于随机选取的((R_1(X),...,R_n(X))（其(deg(R_j(x))=betageq alpha)），那么(U(x)=sum_{i=1}^{n}(p_i(x).R_i(x))也是随机的。
主要技术
这里选用(P_1)作为leader方（designated party）
基于TFHE的(F_{CTest-int})
即使用TFHE去判断交集是否足够大！
（1）这里(p(x))的分子分母（消去后的）的degree为(m-|I|)，如果(m-|I|=|S_Asetminus I|leq T)，则(deg(p(x))leq 2T)，即可以用(2T+1)个点值对插值出(p(x))。
（2）求出(p(x))后，就可以求出其分母(p_{Asetminus I}(x))，其根就是集合(S_{A}setminus I)
下面是具体的两方协议：
（1）通过(2T+1)个数组成(2T+1)个点值对，从而插值出有理函数(p(x))
（2）这里使用的是FHE，通过同态的判断(Enc(p(z)))是否和(p_B(z)/Enc(p_A(z)))相等，决定两方数据集是否相似。为什么呢？因为若(Enc(p(z))=p_B(z)/Enc(p_A(z)))，则(deg(p(x))leq 2T)，从而(m-|I|=|S_Asetminus I|leq T)，则差集最大为(T)，两集合相似。
以上两方协议是CRYPTO 2019:The Communication Complexity of Threshold Private Set Intersection-2019：解读中给出的，下面根据这个两方协议，扩展为多方。
（1）扩展为多方后，就需要使用TFHE了
（2）决定多方数据集是否相似，还是通过判断(Enc(p(z)))是否和(Dec(p_2(z))+...+Enc(p_n(z))/p_1(z))相等。
（3）注意这里是(P_i)方加密，发给(P_1)，在两方中，是(P_1)加密，发送给其他方。
这样简单改造为多方是有问题的：分子分母中不属于交集的项也能消去！
（1）这里元素(a)不属于交集，但还是消去了。
如何解决呢？CRYPTO 2019中给出的方法是，加随机数！
这里给出的方法是加入随机数构成的随机项：
（1）在每一个多项式中加入一个随机项，这样不相同的元素就不会通过某些计算结合消去了。
基于TFHE的(F_{CTest-diff})
即使用TFHE判断差集是否足够小！
（1）(P_i)与其他参与方(P_i)交互后都会插值出一个(widetilde{p_i}(x))，从而可以得到(p_{isetminus 1}(x))和(p_{1setminus i}(x))，所以能计算出差集(D_{1,i}=S_1setminus S_i)和(D_{i,1}=S_isetminus S_1)。
（2）这里存在一个等价关系：(|bigcup S_isetminus I|leq T approx |S_isetminus I|leq T approx deg(widetilde{p_i}(x))leq 2T) 。
（3）因为(bigcup S_isetminus I)中的数据，存在两种情况，所以(P_1)不仅需要计算出差集，还要判断(|bigcup S_isetminus I|)和(T)的大小。
基于TAHE的(F_{CTest-diff})
即使用TAHE判断差集是否足够小！
本文给出的方法能将两方的通信复杂度降为(widetilde{O}(T))。
1、两方场景下：
（1）现在cardinality testing的问题是，判断(deg(p(x))leq 2T)是否成立？CRYPTO 2019给出的方法判断(p(x))是否是“稀疏”的（该思想来自【A local decision test for sparse
polynomials】），即通过判断汉克尔矩阵(H)的奇异性（判断方法来自【Secure linear algebra using linearly recurrent sequences】）
（2）该方法的通信复杂度为(widetilde{O}(T^2))。
2、该文中给出的方法：
（1）使用另外一种方法（half-GCD）去检测汉克尔矩阵奇异性（来自【Fast solution of Toeplitz
systems of equations and computation of pad´e approximants】），能将通信复杂度降低为(widetilde{O}(T))。
（2）如何使用：Alice和Bob各自计算出矩阵的分享份(H_i)，然后通过2PC或者GC联合计算出(H)，再去判断奇异性。
3、扩展为多方的思路：
（1）首先要设计一个多项式(f(x))，使其(deg(f(x))=|bigcup S_isetminus I|)。
（2）然后在各方运算是线性的，各方可以从这个多项式中获取矩阵的分享份。
（3）最后各方执行MPC，检测矩阵的奇异性。
计算交集
这部分是在cardinality testing通过后，如何计算交集。
1、两方场景
这是CRYPTO 2019中给出的方法
（1）Alice根据(2T+1)个点插值出(p(x))。
（2）再根据(f(x)=p_B(x)/p_A(x)=p_{Bsetminus A}/p_{Asetminus B})，恢复出分母(p_{Asetminus B})
（3）但是不安全：Alice不仅可以恢复出分母，也能恢复出分子，泄漏Bob的数据。正如上面介绍的，这里给出的解决办法是加入噪音多项式(V(x))：
这样(deg(p'(x))leq 3T)，这里给出(3T+1)个点插值出(p'(x))，此时Alice就不能从分子中得到额外的Bob信息了。
（4）重要的就是(V(x))是如何构造出的来的！
2、多方场景
这部分是沿着CRYPTO 2019两方扩展为多方的思想构造的。
（1）这里要求各方(P_i)选取degree为(T)的(n)个随机多项式((R_{i,1},...,R_{i,n}))
（2）然后(P_1)也根据(3T+1)个点插值出(p'(x))，进而得到分母，这样由于(V(x))足够随机，不会泄漏其他方的数据，能得到交集。
3、存在的问题
（1）上述介绍多方场景，其通信复杂度为(O(n^2T))，存在的消耗主要是，各方(P_i)选取degree为(T)的(n)个随机多项式((R_{i,1},...,R_{i,n}))。
（2）经过分析，各方只需要选取两个随机多项式就能达到效果，第一个多项式用于随机化自己插值出来的多项式，第二个用于随机化其他方插值出来的多项式。
（3）下面根据该思想，基于TFHE设计的协议通信复杂度可以降低为(O(nT))
低通信量
（1）在点对点网络模型下，多方阈值PSI的通信复杂度的下限为(Omega(nT))
（2）在广播模型下，多方阈值PSI的通信复杂度的下限为(Omega(Tlogn+n))
下面分析在点对点模型下的两种情况的通信复杂度下限。
1、求交集(F_{TPSI-int})
（1）意思是在一个能抵抗半诚实攻击的多方阈值PSI中，两两交互的通信复杂度为(Omega(T))
（1）很明显，多个一起交互的总通信复杂度为(Omega(nT))
2、求差集(F_{TPSI-diff})
这里说，(F_{TPSI-diff})和(F_{TPSI-int})不同之处是，前者是当(|(X_1setminus X_2)cup (X_2setminus X_1)|leq T)时，各方才会求交。【嗯，，为什么呢。。】
（1）意思是在一个能抵抗半诚实攻击的多方阈值PSI中，两两交互的通信复杂度为(Omega(T))
（1）很明显，多个一起交互的总通信复杂度为(Omega(nT))
基于TFHE的检测
这部分，给出关于cardinality testing的两种协议，即(F_{CTest-int})测试交集是否足够大(大于(m-T))，和(F_{CTest-diff})测试差集是否足够小（小于(T)）！
(F_{CTest-int})场景
判断交集是否足够大！
（1）各方编码得到自己的多项式后，乘以一个随机项，以随机化分子分母，解决“分子分母可以相互消去不相同的项”的问题。
（2）leader方（(P_1)）选取一个随机值(z)共享给其他方
（3）各方（不含leader）将(2T+3)个点和(z)带入到各自的多项式(p_i'(x))中，在加密得到得到([e_{i,j}])和([e'_i])发给leader
（4）leadre根据：
计算出(2T+3)个点值对：
然后leader根据这些点插值出([p^*(x)])。
（5）若(deg([p^*(x)])leq 2T+2)，则(p^*(x)=p(x))，所以这里需要判断(p^*(x)=p(x))是否成立，这里是判断
(p^*(z))和(e'_2+...+e'_n/e'_1)是否相等？
下面分析一波正确性：
1、这是符合条件的，即交集足够大，(|I|geq 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(lambda )))
总的来说，这里是想要判断交集是否足够大，即(|S_isetminus I|leq T)是否成立？规约到(deg([p^*(x)])leq 2T+2)是否成立？再规约到判断(p^*(z))和(e'_2+...+e'_n/e'_1)是否相等？
这里留一个疑问：4-(b)中如何判断密态的(p^*(z))和(e'_2+...+e'_n/e'_1)是否相等？
(F_{CTest-diff})场景
判断差集是否足够小！即判断(|bigcup S_isetminus I|<T)是否成立，实现方法是各方与leader交互，leader知道两方差集的加密，根据判断所有差集的交集大小是不是不大于(T)来实现的。
（1）首先各方先将自己数据编码为多项式(p_i(x))，然后将(2T+1)个点和(z)带入得到(e_{i,j})和(e'_i)（(z)是(P_1)随机选取的）
（2）各方（除leader外）将(e_{i,j})和(e'_i)加密，发给leader；leader就可以根据：
计算出(2T+1)个点((j,[e_{i,j}/e'_i]))，从而插值出(widetilde{p^*}(x))，从而得到分子和分母，所以就能得到两方各自的差集([D^*_{i,1}],[D^*_{1,i}])。若(deg(widetilde{p^*}(x))leq 2T)，则(widetilde{p^*}(x)=widetilde{p}(x))；反过来说，只需要判断(widetilde{p^*}(x)=widetilde{p}(x))是否成立，就能判断(deg(widetilde{p^*}(x))leq 2T)？
这时(z)就上场了，leader通过判断(widetilde{p^*}(z)=e'_i/e'_1)是否成立，进而判断(deg(widetilde{p^*}(x))leq 2T)？若相等，(b_i=1)，否则为0
（3）leader得到了各方与自己相比的所有差集，这时需要判断所有差集并在一起的数量是否不大于(T)，若是，则(b'=1)，否则为0。
（4）最后leader将密态的(b')和(b_i)相乘得到密态的(b)，然后联合解密判断差集是否足够小！
基于TAHE检测
基于TAHE只实现了(F_{CTest-diff})的功能，即检测差集是否足够小。
核心思想和CRYPTO 2019一样，即通过检测矩阵的奇异性来判断集合是否相似！不过这里更换了检测奇异性的方法，采用了一个更加高效的方法。
奇异性检测
方法来自“A local decision test for sparse polynomials”
（1）先介绍一个Half-GCD问题
意思就是给出(p_0,p_1in F(x))，其中(d=deg(p_0)=deg(p_1)leq 0)，计算出奇异矩阵(M)，同时满足：$$begin{Bmatrix}p_0 p_1end{Bmatrix}overset{M}{rightarrow} begin{pmatrix}p_2 p_3end{pmatrix} $$使得(deg(p_2)ge d/2 ge deg(p_3))。
使用原来的方法计算复杂度为(tilde{O} (T^2))，使用该新方法降低为(tilde{O} (T))
（2）利用该问题进行检测
最重要的就是：如果(deg(p_3)leq k)，则矩阵(M)就是奇异的！
把该功能看作是一个理想函数（黑盒）(F_{SingTest)，功能是：输入(n)个汉克尔矩阵，然后累加得到(H)，再通过上面的方法判断其是否奇异。
(F_{CTest-diff})情况
基于CRYPTO 2019中的思想，各方各自计算出汉克尔矩阵：
然后通过上述的理想函数(F_{SingTest)，返回结果为0，则表示集合相似，否则，不相似。
(F_{TPSI-diff})场景求交
思想是：在分子加入噪音项，混淆分子，得到带噪音的分子多项式，然后通过下面的公式插值出(q(x))，也就能得到差值分母多项式(p_{Asetminus B}(x))或者(p_{Bsetminus A}(x))，从而就能得到交集。
两方为例：
这就是CRYPTO 2019的方案，等于说求交的方法没有变，用的还是CRYPTO 2019的思想。
下面是多方：
在多方中的区别在于：
- 噪音多项式的构造不同（其实思想还是一样）
- 第3步就是在求噪音多项式的过程，其中使用部分解密-再聚合的方式形成最后的明文。
- 最后各方通过噪音多项式求出(q_i(x))，进而求出交集（这里是每个参与方都能得到交集）
总结
- 给出了两种阈值判断标准：（1）交集足够大（2）差集足够小 时才去求交
- 分别基于TFHE和TAHE构造以上两种情况
- 基于TFHE的是基于CRYPTO 2019中的思想
- 该文章有程序实现：https://www.cnblogs.com/pam-sh/p/16479540.html
- 基于同态的还是太慢，通信复杂度没有较大提升。
