CN115529118B 一种基于全同态加密的隐私集合运算方法及系统 （山东大学）

号一种基于全同态加密的隐私集合运算方法2若隐私集合运算指令为隐私集合求并集PSU的指令，发送方S和接议进行交互计算，得到集合的并集；PSU协议采用基于所述层级同态加密技术构造的基础发送方为拥有小集合X＝{x1，…,xm}的客户端，用S表示；接收方为拥有大集合Y=密每一个元素：c,=FHE.Enc(pk,x),ie[ml，并将公钥和密文发送给R2）R选择随机值 若隐私集合运算指令为隐私集合求交集的势PSI_card的指令，同态加密技术构造的基础PSI_card协议，对基础PSI_card协议进行优化后的PSI_card协R将公钥pk和所有的密文cyie[m]发送给S2）S对大集合x编码为多项式f，并使用乘法随c'=FHE.Enc(pk,rf(y,)),ie[m]，随后S选择[m]上的随机置换对m个密文ct'进行置换获3数，即为交集的势xnyl。所述服务器和客户端响应于隐私集合运算指令，通过协议进行交互若隐私集合运算指令为隐私集合求并集PSU的指令，发送方S和接议进行交互计算，得到集合的并集；PSU协议采用基于所述层级同态加密技术构造的基础PSU协议,对基础PSU协议进行优化后，并结合置换矩阵隐私相等测试和不经意传输的得到发送方为拥有小集合X＝{x1，…,xm}的客户端，用S表示；接收方为拥有大集合Y=每一个元素：c,=FHE.Enc(pk,x),ie[ml，并将公钥和密文发送给R2）R选择随机值 若隐私集合运算指令为隐私集合求交集的势PSI_card的指令，同态加密技术构造的基础PSI_card协议，对基础PSI_card协议进行优化后的PSI_card协R将公钥pk和所有的密文cyie[m]发送给S2）S对大集合x编码为多项式f，并使用乘法随c'=FHE.Enc(pk,rf(y,)),ie[m]，随后S选择[m]上的随机置换对m个密文ct'进行置换获4数，即为交集的势xnyl。5[0005]隐私集合求交集的势(PrivateSetIntersectionCardinality，PSI_card)是[0006]隐私集合求交集的和以及势(PrivateSetIntersectionSumwith私集合求交集的和以及势(LabeledPrivateSetIntersectionSumwithCardinality，6[0014]PSU协议采用基于所述层级同态加密技术构造的基础PSU协议，或用布谷鸟哈希、PSI_card协议进行优化后的PSI_sum_card协议进行优化后得到的PSI_su[0021]进一步地，若服务器和客户端各自拥有一组带有标签的隐私数据，则所述PSI_7[0027]本发明的一种基于全同态加密的隐私集合运算方法，其通信量与小集合线性相[0029]本发明的一种基于全同态加密的隐私集合运算方法，其[0030]本发明的一种基于全同态加密的隐私集合运算方法，其在本发明构造PSI_card和PSI_sum_card协议中，发送方的预处理过程可以完全离线完成，[0036]图5为实施例三所述的基础[0037]图6为实施例三所述的基础[0040]图9为实施例三所述的La[0041]图10为实施例三所述的LabeledPSI_sum_cardwithlargeset优化协议示意8ij＝0。[0057]多点不经意伪随机函数(Multi_pointobliviouspseudorandomfunction，mp_[0060]2.随机选择一个伪随机函数的密钥k给发送方；给接收方发送伪随机函数值{FkFk;[0064]2.选择一组置换分享{sπ(0)，…,sπ(n)}给发送方；给接收方发送一组置换分享s/9PSI_sum_card协议均基于层级同[0069]若隐私集合运算指令为隐私集合求并集的指令，服务器和客户端之间通过PSU协规的优化技术，批量技术来源于2017年发表于Proceedingsofthe2017ACMSIGSACsetintersectionfromhomomorphicencryption，分窗技术来源于2018发表于Proceedingsofthe2018ACMSIGSACConferenceonComputerandCommunicationsSecurity，CCS2018的论文LabeledPSIfromfullyhomomorphicencryptionwithmalicioussecurity，模转换技术来源于2021发表于CCS’21：2021ACMSIGSACConferenceonComputerandCommunicationsSecurity的论文LabeledPSIfromhomomorphicencryptionwithreducedcomputa[0071]若隐私集合运算指令为隐私集合求交集的势的指令，服务器和客户端之间通过块、Paterson_Stockmeyer算法和模转换技术对基础PSI_card协议进行优化后的PSI_card[0073]响应于隐私集合求交集的和以及势的指令，服务器和客户端之间通过PSI_sum_用基础PSI_sum_card协议，或用布谷鸟哈希、朴素哈希、批量、分窗、分块、Paterson_Stockmeyer算法和模转换技术对基础PSI_sum_card协议进行优化后得到的PSI_sum_cardStockmeyer算法和模转换技术对基础LabeledPSI_sum_card协议进行优化后的Labeled布谷鸟哈希以及LFHE的优化技术对基础PSU协议进行优[0087]随后，使用布谷鸟哈希(Cuckoohash)、朴素哈希(simplehash)、批量行优化，最后使用置换矩阵隐私相等测试(pm_PEQT)技术判断置换位置后的元素是否属于区别；[0093](303)R使用全同态加密的批量优化技术，即单指令多数据(SingleInstruction每个元素属于群zt;R将每个向量编码为β=mc/n个明文多项式，其中第i子矩阵Ai的每一行;[0097](403)S基于全同态加密方案使用自己生成的公钥加密每一个幂数，获得β组密文A′[0102](7)[pm_PEQT阶段]R和S运行pm_PEQT协议：R输入矩阵RaxmcrS输入矩阵Rrm:和非交集元素，然后R使用OT选择该列对应的元素)；然后R和S运行OT协议：对于每一列j∈Ccccπ(ij)和均表示输入值。表示异或操作，对于比特串r1=[0109](3)R获得置换矩阵分享sr=sn,,S计算置换矩阵分享其中)b)对v′和v″的第i行第j列元素；[0118]PSU协议的实现和对比：本实施例使用FHE开源库——SEAL库中的实现的BFV全同[0122]本实施例首先测试PSUDDH和PSUPS的通信效率和计算效率，其中具体测试数据(PSU1、PSU*1和PSU*2，PSU1和PSU*1来源于2022年发表于UsenixSecurity2022上的论文于ASIACRYPT2019上的论文Scalableprivatesetunionfromsymmetric_key[0131]本实施例基于层级同态加密方案(leveledfullyhomomorphicencryption，对于0的加密且交集元素加密不变，然后结合LFHE技术，设计安全高效的PSI_sum_card协再对bi加密)，即c;=FHE.Enc([0145]基础PSI_sum_card协议计算的是集合元素的和，但是对即双方对于交集元素的标签(数据)进行求和的运算，无法直接使用PSI_sum_card协议获的集合是大集合，元素个数小于设定值的集合是小集[0146]基础LabeledPSI_sum_card协议包括关于小集合标签的隐私集合求交集和与势[0147]本实施例首先考虑关于小集合标签的隐私集合求交集和与势协议(LabeledPSI_[0148]基础LabeledPSI_sum_cardwithsmallset协议的前3步与基础PSI_card协议bi＝0，即c;=FHE.Enc(pk,b),ieIm]。此外，R使用LFHE的公钥pk，对每个元素对应的标i对应于标签数据di；然后R将ei和随后，对密文ei8e使用加法同态计算交集元素对应标签数据和的密文：csum=[0152]基础LabeledPSI_sum_cardwithsmallset协议与基础PSI_sum_card协议相[0153]基础LabeledPSI_sum_cardwithsmallset协议只能对小集合元素对应的标签g(x)=其中依旧使用乘法随机化方法，计算多项式hj[0155]根据上述思路，本实施例构造关于大集合标签的隐私集合求交集和与势协议(LabeledPSI_sum_cardwithlargeset)，该协议计算的是交集元素对应大集合标签的[0156]具体协议前三步类似基础PSI_card协议，只是在第(2)步中服务器S基于X=sum_card协bi＝0，即cf=FHE.Enc(pk,b),iE[m]。R将密文ei发送给服务器S；RPHEEncnk,i=Imbihs();并将csum发送给R；[0162](6)R接收到密文csum后，使用私钥sk解密密文，可获得交集元素的和sum=集元素对应的标签数据的和。基础LabeledPSI_sum_cardwithlargeset协议如图6所分窗(windowing)、分块(partitioning)、Paterson_Stockmeyer算法、模转换(modulusc]；[0168](4)S使用LFHE方案的单指令多数据(SingleInstructionMultipleData)优化wnyl="bh,[0173]根据PSI_card协议的高效优化，本实施例对PSI_sum_card协议，LabeledPSI_[0174]LabeledPSI_sum_card优化协议包括LabeledPSI_sum_cardwithsmallset优[0175]PSI_sum_card优化协议的前三步完全使用PSI_card优化协议，后续步骤和基础[0176]关于小集合标签的隐私集合求交集和与势的优化协议(LabeledPSI_sum_card[0177]关于大集合标签的隐私集合求交集和与势的优化协议(LabeledPSI_sum_card[0179](2)服务器S对大集合X和对应标签集合E进行预处理，首先使用朴素哈希将集合X的所有元素哈希到xxmc,该表包含mc列，每一列可以包含B个元素，标签集合E对应填充到[0180](3)S选择随机矩阵Rrm:=Irl.然后，S将xorm:Brm:的分别按照行划分为α对Xiij…+[0181](4)S使用LFHE方案的单指令多数据优化技术对系数矩阵Af和Ah进行批量处理，Afo:发送给服务器S；[0186](9)S接收到密文ei后，结合步骤(4)中的置换密文矩阵CO基于LFHE全同态运算性质，在密文状态下计算对应位置密文的乘积，[0187](10)R接收到密文csum后，使用私钥sk解密密文，可获得交集元素的和sum=[0188]LabeledPSI_sum_cardwithlargeset优化协议采用与PSI_card优化协议相同的布谷鸟哈希填充方法，多项式f和h计算类