CN119496603A 基于全同态加密的密态数据并行排序方法及系统 （中国科学院信息工程研究所）

心基于全同态加密的密态数据并行排序方法本发明提供一种基于全同态加密的密态数公共参数与公钥，根据比较矩阵对明文数组排实现了同态排序算法的并行加速，提高了吞吐2基于所述公共参数与所述公钥，根据所述比较矩阵以垂直方式进行打包加密，计算出cj=Enc(laay,ayy…,an-y,0,…,0l),j=0,1…n-1，利用掩码技术和明文槽旋转技术，将i/w个密文c(+1),…,c+/N)打包到单个密文中，并把c广播复制次；获得的密文，并将比较结果以对角线方式组成比较计算初始信号的密文以及;3;计算c*=pn-1-o+Gn-1-o，输出得到密文c*，对应明文为c1和cz的比较结果。输入加密数组的密文(N,c:=(cjl-o…n-1)，利用所述比较矩阵;;将密文c:={cj-o….n-1和密文R相乘，具体为：;输出密文数组，对应的明文槽加密了多项式的二进制分计算密文pj在不同Frobenius映射下的结果o(p())；按照各个投影函数的系数o(a)，线性组合出投影结果L,(p(x),)=by的密文;4利用明文槽旋转技术，将所述的密文Bij打包为B;=Enc(Ibo,b1,…,bw-1,0,…,01)；7.根据权利要求1至6任一项所述的基于全采用BGV层次型全同态加密方式，定义m次分圆整数环R=Z[X]/(pm(X))，所述BGV层次型全同态加密方式中的明文空间为商环R,=R/PR，其中，pm(x)ez[x]为m次分圆多项式，基于Ring_LWE假设，对称版本的BGV密文为ct=Enc,(m)=lco:=as+petm,cr:=-aleR⃞,[c,+cys(modq)(modp)，噪声范数的上界为。所述公钥；结果输出模块，用于基于所述私钥，将所述有序数组9.一种电子设备，包括存储器、处理器及存储在机程序被处理器执行时实现如权利要求1至7任一项所述基于全同态加密的密态数据并行5处理框架等领域，它们通过最小化时间复杂度和空间复杂度来满足不同场景下的性能需6基于所述公共参数与所述公钥，根据所述比较矩阵对所述明文数组进行同态排对所述明文数组中每个整数进行二进制分解：a1=ay·2)；输入加密数组[ao,an-1l的密文(N,c:=(cjJ-o…n-1)，利用掩码技术和明文槽旋利用掩码技术和明文槽旋转技术，将i/w个密文c(+1),…,c+/N)打包到单个密文获得[ao<a],[a<arr1]…,[an-1<arrn-1]的密文，并将比较结果以对角线方式组成比较矩的打包密文。;7;计算c*=pn-1-o+Gn-1-o，输出得到密文c*，对应明文为c1和cz的比较结果。输入加密数组loor-av-1l的密文(N,c:=(cjl-o…n-1)，利用所述比较矩阵构造方;将密文c:={cj-o….n-1和密文R相乘，具体为：;计算密文pj在不同Frobenius映射下的结果o(p(x),)；按照各个投影函数ui的系数，线性组合出投影结果L,(p(x),)=by的密文;输出得到密文B=t8),，对应明文[bo,b1,…,by-1l为有序数组。8采用BGV层次型全同态加密方式，定义m次分圆整数环R=Z[X]/(pm(X))，所述BGV层次型全同态加密方式中的明文空间为商环R,=R/PR，其中，pm(x)ez[x]为m次分圆多ct=Enc,;(m)=[eo:=as+pe+m,c:=-aleR⃞,其中，q是密文模数，s,eER,分别是秘密和机程序被处理器执行时实现如上述任一种基于全同态加密的密态数据并[0021]本发明提供的基于全同态加密的密态数据并行排序方法及系统，充分利用了BGV兼容性和可扩展性更好的并行同态排序算法。通过使用SIMD编码技术和多线程加速技术，9[0026]图1为本发明提供的基于全同态加密的密态数据并行排序方法的流程示意图，如公钥；然后随机采样短的环元素s-R作为私钥，均匀采样a-RO，采样噪声et-R，计算[0030]在服务器对密文做同态排序阶段中，图4为本发明提供的并行同态排序算法流程接着利用掩码技术和明文槽旋转技术，将i/w个密文c(+1),…,c+/N)打包到单个并利用所提出的并行前缀同态比较方法，计算出上述打包的c和ct0的比较结果将密文c:={cj-o….n-1和密文R相乘，具体为：计算密文pj不同Frobenius映射下的结果o(p(x),)；按照各个投影函数ui的系数，线性组合出投影结果L,(p(x),)=by的密文;最后输出密文(ws-l))，其明文是输入数组lan-as-1l的[0036]具体的，用户解密阶段包括输入密文(s-t))。[0037]分别从密文Bj中解密出[bo分别模拟XOR逻辑和AND逻辑，使用扩域cr(pd)上的多项式乘法模拟多比特整数的算术加杂度比常用的线性比较器降低了一个对数因子。本发明充分利用BGV方案的SIMD并行计算较矩阵行/列的汉明重量为排列次序ri，计算出多项式p(x)=iar-x"i，在标准基下的系数假设p(modm)的乘法阶是d，那么在素域上可以分解为l=p(m)/d个不可约因子，形如，并且它们的次数都满足degFi=d。给定整环Z[x]的理想p=(p,中m(x))，定义不可约因子生成的理想p;=(p,FI(x))，那么有p=NZP:，根。输入加密数组loor-av-1l的密文(N,c:=(cjl-o…n-1)，利用掩码技术和明文槽旋利用掩码技术和明文槽旋转技术，将i/w个密文c(+1),…,c+/N)打包到单个密文,获得[ao<a],[a<arr1]…,[an-1<arrn-1]的密文，并将比较结果以利用明文槽旋转技术，复制出剩余一半元素的密文，输出比较矩阵[0050]在本发明中，执行上述的打包加密后，N个n比特整数组成的数组被加密为[0051]本发明利用并行前缀比较器来构造明文数组的比较矩阵。定义信号为二元组p;=(at⃞1)·b,0≤i≤n-1，g;=a;$b;$1,1≤i≤n-1，以及。,以及G0=0；;计算c*=pn-1-o+Gn-1-o，输出得到密文c*，对应明文为c1和cz的比较结果。输入加密了数组[ao,…,a-1]的密文。继续利用掩码技术和明文槽旋转技术，将i/w个密文c(+1),…,c+/N)打包到单个利用所提出的并行前缀同态比较算法，计算出上述打包的和的比较结果,获得[ao<a],[a<arr1]…,[an-1<arrn-1]输入加密数组loor-av-1l的密文(N,c:=(cjl-o…n-1)，利用所述比较矩阵构造方;将密文c:={cj-o….n-1和密文R相乘，具体为：;;;比ai更大的元素的数量；而矩阵M的第i列的汉明重量，也恰好等于输入数组中比aj更小的[0064]本发明采用了指数编码方法，利用多项式乘法快速计算多比特整数的算术加在所设置参数下，BGV方案的明文槽是S=GF(24)=Z2[X]/(F:(X))，其中于整数a,be[0,d]，它们被分别编码为。那么整数上的算术加法a+b被转化为了有限域s上的多项式乘法x"·xb=x"tb，因此只需要一次同态乘法就完成了整数上的算术加[0066]步骤1，利用所述的比较矩阵构造方法，计算出比较矩阵各个对角线的密文;;计算密文pj在不同Frobenius映射下的结果o(p(x),)；按照各个投影函数ui的系数，线性组合出投影结果L,(p(x),)=by的密文;输出得到密文B=t8),，对应明文[bo,b1,…,by-1l为有序数组。[0069]本发明提出的多项式系数同态提取算法是为了从多项式p(x)中提取出有序密文，数环元素。迹函数定义为，其中cae(cr(24)/z2)中i=0,1,",d-1;为常数，那么L,(p(x))就是o(p(x))的线性组合，并且o(p(x))是与Li无关的自同构运算结计算密文pj不同Frobenius映射下的结果o(p(x),)；按照各个投影函数ui的系数，线性组合出投影结果L,(p(x),)=by的密文;采用BGV层次型全同态加密方式，定义m次分圆整数环R=Z[X]/(pm(X))，所述BGV层次型全同态加密方式中的明文空间为商环R,=R/PR，其中，pm(x)ez[x]为m次分圆多I-llo为无穷述的基于全同态加密的密态数据并行排序系统与上文描述的基于全同态加密的密态数据[0076]图7为本发明提供的基于全同态加密的密态数据并行排序系统的结构示意图，如[0077]本发明提供的基于全同态加密的密态数据并行排序系统，充分利用了BGV方案的[0078]本发明实施例提供的基于全同态加密的密态数据并行排序系统是用于执行上述[0080]此外，上述的存储器803中的逻辑指令可以通过软件功能单元的形式实现并作为发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以