基于Csanky算法的同态加密矩阵求逆方法、系统、设备及介质
本技术涉及隐私保护计算和同态加密,特别是涉及一种基于csanky算法的同态加密矩阵求逆方法、系统、设备及介质。
背景技术:
1、矩阵求逆是线性代数中的基础运算,广泛应用于机器学习、数据分析、科学计算、工程计算、统计分析和优化求解等场景。在医疗健康、金融服务、基因数据分析以及用户行为分析等应用中,参与计算的矩阵通常包含个人隐私、商业数据或者其他敏感信息。若将明文矩阵直接发送至云端服务器进行计算,可能导致输入数据、中间计算过程和计算结果泄露。因此,如何在数据处于加密状态的情况下完成矩阵求逆,是隐私保护计算领域需要解决的问题。
2、全同态加密技术允许计算方在无法获得明文数据和私钥的情况下,对密文执行预定的计算操作,并将加密计算结果返回数据持有方解密。部分同态加密方案支持打包编码,能够将多个数据元素编码至同一密文的不同槽位中,从而利用单指令多数据方式并行执行密文运算。以ckks方案为代表的近似同态加密方案还支持对近似实数进行加密计算,为加密数值计算和加密线性代数运算提供了实现基础。
3、然而,同态加密环境下的密文运算代价明显高于明文运算。密文乘法、密文旋转、重线性化、重缩放以及密钥切换等操作均会消耗计算资源,并且同态加密方案通常受到可用乘法深度的限制。对于包含多轮密文乘法和多阶段中间运算的矩阵求逆过程,如果计算流程组织不合理,将产生较高的密文计算开销,并可能受到乘法深度和近似计算误差的制约。
4、传统矩阵求逆方法通常包括高斯消元、lu分解以及基于选主元的数值计算方法。此类方法在执行过程中通常需要进行数值比较、主元选择或者根据中间计算结果确定后续执行路径,涉及数据相关分支和条件控制。同态加密环境中的计算方无法直接获得密文对应的明文数值,也难以基于密文数值高效执行比较、选主元和数据相关控制流,导致传统矩阵求逆方法难以直接适用于同态加密环境。
5、现有的同态加密线性代数计算多集中于密文矩阵乘法、逐元素加密矩阵运算或者特定应用场景下的安全计算协议。逐元素加密方式在矩阵元素数量较大时会产生大量密文,增加通信开销和密文管理开销;单独的密文矩阵乘法运算也无法直接构成完整的密文矩阵求逆过程。在矩阵求逆涉及多类中间运算和中间结果复用的情况下,若各中间结果重复计算,还会进一步增加密文乘法次数和计算资源消耗。
6、因此,在同态加密环境下,如何在不获取明文矩阵和私钥的情况下,避免依赖数值比较、选主元和数据相关分支完成矩阵求逆,并减少密文矩阵求逆过程中的重复计算开销,是需要解决的技术问题。
技术实现思路
1、本技术的目的是提供一种基于csanky算法的同态加密矩阵求逆方法、系统、设备及介质,能够实现密文矩阵求逆,保护矩阵数据隐私,并减少重复密文矩阵乘法。
2、为实现上述目的,本技术提供了如下方案:
3、第一方面,本技术提供了一种基于csanky算法的同态加密矩阵求逆方法,包括:
4、数据拥有端对待求逆的非奇异矩阵进行打包编码和同态加密,得到打包密文矩阵,并将所述打包密文矩阵以及同态计算所需的计算密钥发送至计算服务端;
5、所述计算服务端在未获得所述非奇异矩阵的明文矩阵以及所述数据拥有端持有的私钥的情况下,基于所述打包密文矩阵执行打包密文矩阵乘法,顺序计算并缓存多个矩阵幂密文;
6、所述计算服务端从各所述矩阵幂密文中分别提取迹,得到多个加密迹标量;
7、所述计算服务端基于多个所述加密迹标量,按照牛顿恒等式递推计算特征多项式系数密文;
8、所述计算服务端在密文域对所述特征多项式系数密文中的常数项系数密文进行倒数近似,得到常数项倒数近似密文;
9、所述计算服务端基于缓存的多个所述矩阵幂密文、所述特征多项式系数密文和所述常数项倒数近似密文,按照凯莱-哈密顿关系重构加密逆矩阵;
10、所述计算服务端将所述加密逆矩阵返回所述数据拥有端,由所述数据拥有端解密得到所述非奇异矩阵的逆矩阵近似结果。
11、可选地,所述同态加密为支持打包编码和近似数值计算的ckks同态加密;
12、所述打包编码将所述非奇异矩阵中的多个矩阵元素编码到同一密文的不同打包槽中;
13、所述计算密钥包括用于密文旋转、重线性化以及密钥切换的辅助密钥;
14、所述计算服务端为云端服务器。
15、可选地,所述计算服务端基于多个所述加密迹标量,按照牛顿恒等式递推计算各特征多项式系数;
16、在递推计算中,除以整数的运算通过乘以对应的明文标量实现;
17、所述计算服务端将各所述特征多项式系数复制到对应密文的多个所述打包槽中,得到所述特征多项式系数密文。
18、可选地,所述非奇异矩阵为d阶矩阵,记为矩阵a,多个所述矩阵幂密文包括一阶至d阶矩阵幂密文;
19、所述计算服务端将所述打包密文矩阵作为一阶矩阵幂密文,并针对二阶至d阶中的每一阶,对上一阶矩阵幂密文与所述打包密文矩阵执行打包密文矩阵乘法,得到当前阶矩阵幂密文;
20、所述计算服务端缓存所述一阶至d阶矩阵幂密文,以供迹提取和加密逆矩阵重构调用
21、可选地,所述计算服务端采用固定迭代次数的牛顿-拉夫森迭代对所述常数项系数密文进行倒数近似,其中,迭代的初始近似值根据常数项系数的预期数值范围预先设定,迭代次数根据目标精度和可用乘法深度预先设定;
22、所述计算服务端按照下式所表示的凯莱-哈密顿组合关系构造中间矩阵密文,并利用所述常数项倒数近似密文对所述中间矩阵密文进行密文标量乘法,得到所述加密逆矩阵:
23、
24、其中,至分别为所述矩阵a的特征多项式系数,i为d阶单位矩阵。
25、可选地,从各所述矩阵幂密文中提取迹,包括:
26、所述计算服务端利用明文对角线掩码对各所述矩阵幂密文进行掩码处理,以保留各所述矩阵幂密文对应的主对角线元素,并对掩码处理得到的密文中的槽位执行槽求和,得到对应的加密迹标量。
27、可选地,在进行打包编码之前,所述数据拥有端采用明文缩放因子对所述非奇异矩阵进行数值归一化,得到缩放矩阵,并对所述缩放矩阵进行打包编码和同态加密;
28、所述数据拥有端解密得到所述缩放矩阵的逆矩阵近似结果后,将所述缩放矩阵的逆矩阵近似结果乘以所述明文缩放因子,得到所述非奇异矩阵的逆矩阵近似结果。
29、第二方面,本技术提供了一种基于csanky算法的同态加密矩阵求逆系统,包括数据拥有端和计算服务端;
30、所述数据拥有端用于对待求逆的非奇异矩阵进行打包编码和同态加密,得到打包密文矩阵,将所述打包密文矩阵以及同态计算所需的计算密钥发送至所述计算服务端,接收所述计算服务端返回的加密逆矩阵,并对所述加密逆矩阵进行解密,得到所述非奇异矩阵的逆矩阵近似结果;
31、所述计算服务端用于在未获得所述非奇异矩阵的明文矩阵以及所述数据拥有端持有的私钥的情况下,基于所述打包密文矩阵执行打包密文矩阵乘法,顺序计算并缓存多个矩阵幂密文;从各所述矩阵幂密文中分别提取迹,得到多个加密迹标量;基于多个所述加密迹标量,按照牛顿恒等式递推计算特征多项式系数密文;在密文域对所述特征多项式系数密文中的常数项系数密文进行倒数近似,得到常数项倒数近似密文;基于缓存的多个所述矩阵幂密文、所述特征多项式系数密文和所述常数项倒数近似密文,按照凯莱-哈密顿关系重构所述加密逆矩阵,并将所述加密逆矩阵返回所述数据拥有端。
32、第三方面,本技术提供了一种电子设备,其特征在于,包括处理器和存储器,所述存储器中存储有计算机程序,所述计算机程序被所述处理器执行时实现上述的基于csanky算法的同态加密矩阵求逆方法。
33、第四方面,本技术提供了一种计算机可读存储介质,其特征在于,所述计算机可读存储介质上存储有计算机程序,所述计算机程序被处理器执行时实现上述的基于csanky算法的同态加密矩阵求逆方法。
34、根据本技术提供的具体实施例,本技术公开了以下技术效果:
35、数据拥有端对待求逆的非奇异矩阵进行打包编码和同态加密,计算服务端在未获得明文矩阵和私钥的情况下完成矩阵求逆,并将加密逆矩阵返回数据拥有端解密。由此,输入矩阵、中间计算结果和输出逆矩阵在计算服务端均处于加密状态,能够降低矩阵数据在安全外包计算过程中的泄露风险;
36、通过基于矩阵幂密文、加密迹标量、特征多项式系数密文和凯莱-哈密顿关系重构加密逆矩阵,无需在密文域执行高斯消元中的选主元、明文数值比较以及数据相关分支操作,使矩阵求逆流程能够适配同态加密计算环境。
37、通过顺序计算并缓存多个矩阵幂密文,缓存后的矩阵幂密文能够同时用于迹提取和逆矩阵重构,避免各矩阵幂从初始密文矩阵开始独立重复计算,从而减少密文矩阵求逆过程中的重复密文矩阵乘法,降低密文计算开销。
38、通过在密文域对特征多项式的常数项系数密文进行倒数近似,无需直接执行密文除法,即可完成逆矩阵重构所需的常数项倒数计算,提高了矩阵求逆流程在同态加密环境下的可实施性。
39、通过将打包编码、密文矩阵乘法、矩阵幂缓存、迹提取、特征多项式系数递推、常数项系数倒数近似和凯莱-哈密顿逆矩阵重构组合为完整的密文矩阵求逆流程,而非仅提供单独的密文矩阵乘法运算,能够实现从加密矩阵输入到加密逆矩阵输出的端到端安全外包计算。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com