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

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

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

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

摘要

image
(1)该协议的通信复杂度不依赖于输入集的大小,而取决于阈值\(t\)的大小
(2)基于阈值的PSI协议分为两部分:

  • 交集的势测试(Cardinality Testing ),即测试参与方的交集是否大于\(n-t\)
  • PSI:计算交集

介绍

两方阈值PSI:
image
(1)双方先检测交集大小是否\(> n-t\)
(2)若满足,则求交(获取交集);否则,什么也得不到(获取不到交集)

标准PSI和阈值PSI的对比:

  • 标准的PSI更在乎交集,而不在乎交集的大小,而阈值PSI更关注交集的大小。
  • 阈值PSI的通信量较少,只取决于阈值\(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\),方案是两方场景
(4)【Multi-party threshold private set intersection with sublinear communication-2021
这也是一个多方阈值PSI,使用FHE,通信复杂度为\(O(Nt)\),也提出了一个TPKE加密方案实现了:只有当各方的交集足够大时,各方才能求交集。还可以秘密的计算汉克尔矩阵的行列式(矩阵大小的线性时间内)。

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

阈值PSI

image

当前的阈值PSI主要分为两步:
(1)Cardinality Testing:就是各方检测交集是否大于\(n-t\)
(2)PSI:如果满足(1),则输出交集;否则没有输出

具体:
image
如果起始\(t=1\),则\(t\)的取值范围有:\(1,2,4,8,…,t,2t\)

通信复杂只取决于\(t\)的原因:
image

合适的阈值一定是2的次幂 ,如果交集大于\(n-t’\),则Cardinality Testing对于阈值\(t\)就成功,因为\(t\geq t’>t/2\),所以协议的通信复杂度只取决于阈值的大小。


解释有点牵强,或许我没理解
\(t’\)是什么?


贡献

(1)多方Cardinality Testing

  • 较上面的Cardinality Testing,这里给出了满足多方的Cardinality Testing
  • 通信复杂度为\(O(Nt^2)\)
  • 并给出一些新的线性计算(linear algebra):求密文矩阵相乘、求密文矩阵的秩、求密文矩阵的逆等

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

(2)多方阈值PSI

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

回顾一下两方的情况:
两方Alice和Bob各有数据\(S_A\)\(S_B\),其大小都是\(n\),阈值\(t<<n\),如果\(|S_A\cap S_B|\geq n-t\),则求出交集\(S_A\cap S_B\)

我们方案基于【The communication complexity of threshold private set intersection-2019】论文,这是一个两方的阈值PSI协议:
image
(1)若交集大于\(n-t\)
(2)计算交集
两方将数据编码到多项式中,得到\(P_A(x)=(x-a_i)…(x-a_n)\)\(P_B=(x-b_1)…(x-b_n)\)在一个大的有限域上\(F\),其中\(a_i\in S_A,b_i\in S_B\),然后只要满足\(|S_A\cap S_B|\geq n-t\),则:
image
\(deg(P_A)=deg(P_B)=t\),所以两方只需要在\(P_A(x)/P_B(x)=P_{A\setminus B}(x)/P_{B\setminus A}\)上计算\(O(t)\)个点。然后将这些点插值得到\(P_A(x)/P_B(x)\),然后求出分母\(P_{B\setminus A}\),继而求出交集多项式\(P_{A\setminus B}(x)=P_B(x)/P_{B\setminus A}\)


紧接上文问题:具体如何根据\(P_A(x)/P_B(x)\),然后求出分母\(P_{B\setminus A}\)


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

该协议只有满足\(|S_A\cap S_B|\geq n-t\),才是安全的,否则就会泄露额外的信息,所以双方应该先执行Cardinality Testing操作,来保证协议是满足\(|S_A\cap S_B|\geq n-t\)的。

扩展到多方的限制:
image
image
这里讲的是Cardinality Testing如何扩展为多方:

参与方先将数据编码到多项式中,得到\(Q_A(x)=x^{a_i}+…+x^{a_n}\)\(Q_B=x^{b_1}+…+x^{b_n}\),其中\(a_i\in S_A,b_i\in S_B\),检测\(Q(x)=Q_A(x)-Q_B(x)\)是否是一个稀疏多项式(sparse polynomial),若是,则判断集合\((S_A \cup S_B)\setminus (S_A \cap S_B)\)是小集合(small),通信复杂度为\(O(t^2)\)
那问题来了:
(1)如何判断多项式是否时稀疏的?
(2)如何判断集合是小的?

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

主要方法

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

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

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

2、多方势检测(Cardinality Testing via Degree Test of a Rational Function )
对于参与方编码的多项式\(P_{S_i}(x)=(x-a_1^{(i)})…(x-a_n^{(i)}),i\in [1, N]\),有:
image
若交集\(\cap S_i\)大小大于\(n-t\),则\(deg(P_{S_1\setminus (\cap S_i)})=…=deg(P_{S_N\setminus (\cap S_i)})\leq t\)

以上是求交的方法!

所以Cardinality Testing有以下问题:
对于有理函数\(f(x)=P_1(x)/P_2(x)\),能否安全的判断\(deg(P_1(x))=deg(P_2(x))\leq t\),进而通过插值\(O(t)\)个点得到\(f(x)\)

我们发现,将\(V=(v_i,f(v_i))\)\(W=(w_i,f(w_i))\)(\(2t\)个点值),插值为多项式\(f_V(x),f_W(x)\),满足:
image

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

3、多方计算交集

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

各方将其数据进行编码为多项式\(P_{S_i}(x)=(x-a_1^{(i)})…(x-a_n^{(i)}),i\in [1, N]\),并且知道交集大小\(> n-t\),各方联合计算出有理函数\((P_{S_1}+…+P_{S_N})/P_{S_1}\),然后插值\(O(t)\)个点值,\(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\)是一个有限集合,\(x\leftarrow S\)表示从\(S\)中随机采样,\(|S|\)表示\(S\)的势(cardinality);\(N\)个参与者;给出两个不可区分的分布\(D_1,D_2\);安全参数\(\lambda\)

阈值的PKE

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

UC框架和理想函数

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

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

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

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

image

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

多项式插值

下面介绍使用一个随机多项式去“混淆/遮盖”一个级数小于t的多项式:
image
这种方式也可以用于多个多项式(多方),只要他们不共享一个因子(common factor)。

什么意思,不能约么?

下面介绍如何通过插值恢复出这个有理函数\(f(x)=P(x)/Q(x)\)以及证明该函数是唯一的
image
其中\(P(x)\)的级数为\(m\)\(Q(x)\)的级数为\(n\),则\(f(x)\)可一通过插值\(m+n+1\)个点唯一的插值出\(f(x)\),若\(P(x),Q(x)\)是首一的(monic),则只需要\(m+n\)个点。

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

引理

image
image

Oblivious Degree Test for Rational Functions

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

多方求线性函数(Oblivious Linear Algebra)

多方求加密矩阵乘

功能是:
image

具体实现如下:
(1)初始化:各方\(P_i\),共享公钥\(pk\),以及每方各有一份私钥分享份\(sk_i\)
(2)输入:\(P_1\)输入两个矩阵的加密\(Enc(pk,M_l),Enc(pk,M_r)\),其中\(M_l,M_r\in F^{t*t}\)
(3)输出:各方得到\(Enc(M_l*M_r)\)
image
其思想就是:$(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_1b_1 $


但存在一个问题:(以三方为例)

最后得到的\(e=Enc(M_l*M_r)+Enc(R_r^{(1)}*R_r^{(1)})+Enc(R_r^{(2)}*R_r^{(2)})+Enc(R_r^{(3)}*R_r^{(3)})\),因为在上面框红处,没有自乘!


多方求加密矩阵的秩

功能:
image
具体实现如下:

image
其中\(F_{OMM}\)表示的是以\(O(log t)批处理\)计算\(t\)次乘法


不太懂


多方求线性函数

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

具体实现如下:
image

多方势检测(Oblivious Degree Test)

功能:判断多方的交集数量\(t’\)是否大于阈值\(t\),若满足,则输出1,否则输出0。
image

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

给定有理函数\(P(x)/Q(x)\),其中\(P(x),Q(x)\)有相同的级数,并给定两个集合\(V_1,V_2\),下面的协议\(secDT\)是判断这个有理数函数的级数是否小于阈值\(t\)
image
下面具体来分析一波:
(1)初始化

  • 各方共享公钥\(pk\),且每人有一个私钥份\(sk_i\)
  • 假设各方可以正常执行理想函数:\(F_{ORank},F_{OLS},F_{OMM},F_{DecZero}\)
  • 各方共享一组随机数\((\alpha_1,…,\alpha_{4t+2}\)

(2)参与方\(P_1\)输入
输入:\(((\alpha_1,Enc(pk,f_1)),…,(\alpha_{4t+2},Enc(pk,f_{4t+2})))\),其中\(f_i=P_1(\alpha_i)/P_2(\alpha_i)\)\(P_1(x),P_2(x)\)是两个级数为\(t’\)的多项式

(3)\(P_1\)设置
\(P_1\)的输入\(((\alpha_1,Enc(pk,f_1)),…,(\alpha_{4t+2},Enc(pk,f_{4t+2})))\)拆分为两部分\((\alpha_j,Enc(pk,f_j))_{j\in [2t+1]}=(v_j,Enc(pk,f_{v,j})))_{j\in [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\)对点值\((v_j,Enc(pk,f_{v,j})_{j\in [2t+1]}\)\((w_j,Enc(pk,f_{w,j})_{j\in [2t+1]}\)

由上面的点值构造两个密态线性系统:
image
其中\(r=(v,w)\)\(M_r\)是一个维数为\(2t+1\)的方阵,\(y_r\)是一个长度为\(2t+1\)的向量。

这样就得到了加密的\(M_v,y_v\)\(M_w,y_w\)
(4)各方联合计算
计算:\(Enc(pk,rank(M_r)-rank([M_r || y]))\),如果结果不为0,则停止协议,其中使用了两次\(F_{ORank}\)\(F_{DecZero}\)

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

这时各方能根据\(M_r[c_r^{(1)},c_r^{(2)}]=y_r,r\in(v,w)\)\((y_v,M_v)\)得到密态的\(c_v^{(1)}||c_v^{(2)}\)\((y_w,M_w)\)得到密态的\(c_w^{(1)}||c_w^{(2)}\)
(6)各方联合计算
计算出:\(C_v^{(1)}(x)=\sum_{j=0}^{t}c_{v,j}^{(1)}x^{t-j}\)\(C_v^{(2)}(x)=x^t+\sum_{j=0}^{t}c_{v,j-1}^{(2)}x^{t-j}\)\(C_w^{(1)}(x)=\sum_{j=0}^{t}c_{w,j}^{(1)}x^{t-j}\)\(C_w^{(2)}(x)=x^t+\sum_{j=0}^{t}c_{w,j-1}^{(2)}x^{t-j}\)

image
最终计算出密态的\(z\)

(7)判断
各方使用\(F_{DecZero}\)检查\(z\)是否等于0(即对\(z\)解密)。如果是,输出0;如果不是,输出1。

优化

我们考虑在对插值生成\(f(x)=P(x)/Q(x)\),当\(Q(\alpha_i)=P(\alpha_i)=0\)时,我们就不能求\(f(x)\)了。
image
解决办法就是,去掉该点
使得\(\widetilde{P}(x)=P(x)/(x-\alpha _i),\widetilde{Q}(x)=Q(x)/(x-\alpha _i),f(\alpha _i)=\widetilde{P}(\alpha _i)/\widetilde{Q}(\alpha _i)\)

具体来讲,就是计算出点值对\((\alpha _i,Enc(pk,P_1(\alpha _i)/(x-\alpha _i))\)\((\alpha _i,Enc(pk,P_2(\alpha _i)/(x-\alpha _i)))\)

这里的\(P_1(),P_2(X)\)指的是\(P(x),Q(x)\)

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

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

多方阈值PSI

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

安全的势检测(Secure Cardinality Testing)

1、理想功能
image
2、具体实现
image
总结一下:
(1)各方先各自将数据编码为多项式,然后求出\(4t+2\)个点值,加密这些点,得到\(4t+2\)个密态值\(Enc(pk,r_i*P_i(\alpha_j))\),广播出去。
(2)\(P_1\)得到\(4t+2\)\(c_i^{(j)}\),计算得到\(d^{(j)}\),形成密态点值对\((\alpha_j,d^{(j)})\),并和私钥\(sk_1\)一起发送给理想函数\(F_{SDT}\)
(3)其他参与方\(P_2,…,P_N\)也将各自的私钥\(sk_i\)发送给理想函数\(F_{SDT}\),从而判断分子\(P_1(x)\)和分母\(P_2(x)\)的级数是否最大为\(t\),然后输出结果。

完整的多方阈值PSI协议

在该协议中,通过使用TPKE扩展了之前的方案,具体协议如下:
image
总结一下:
(1)各方先将数据发送给理想函数\(F_{MPCT}\),检测交集大小和阈值的大小关系。
(2)再通过理想函数\(F_{Gen}\)生成密钥:各方共享公钥\(pk\),各自有一个私钥份\(sk_i\)
(3)各方执行:

  • 将数据\(S_i\)编码为多项式\(P_i(x)\),计算出\(3t+_1\)个点值\(P_i(\alpha_j)\)
  • 采样\(R_i(x)\),使得\(deg(R_i(x))=t\)
  • 加密:\(c_i^{(j)}=Enc(pk,R_i(\alpha_j)*P_i(\alpha_j))\),然后广播出去。

(4)\(P_1\)将收到的对应的密文相加得到\(3t+1\)个值\(d^{(j)}=\sum_{i}^{N}c_i^{(j)}\),再将其广播出去。
(5)联合解密出\(V^{(j)}=Dec(sk,d^{(j)})\)
(6)\(P_1\)计算点\(\widetilde{V}^{(j)}=V^{(j)}/P_1(\alpha_j)\),得到点值对\((\alpha_j,\widetilde{V}^{(j)})\),将其插值出函数\(\widetilde{V}^{(j)}(x)\),再恢复出分母\(P_{S_1\setminus (\cap S_i )}(x)\)
(7)\(P_1\)根据自己数据\(S_1=(a_1^{(1)},…,a_1^{(n)})\)计算出\(P_{S_1\setminus (\cap S_i )}(a_1^{(j)})\),根据\(P_{S_1\setminus (\cap S_i )}(a_1^{(j)})\neq 0\),判断\(a_1^{(j)}\)是否在交集中。
(8)广播交集。

在这里给出了详细如何根据\(P_{S_1\setminus (\cap S_i )}(x)\),计算出交集!

正确性证明:
image
image

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

总结

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


Tags: