基于同态加密的线性系统求解方案

作     者：吕由 吴文渊 LYU You;WU Wen-yuan

作者机构：中国科学院重庆绿色智能技术研究院重庆400714 中国科学院大学北京100049 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2022年第49卷第3期

页      面：338-345页

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：重庆市科委项目(cstc2018jcyj-yszxX0002) 贵州省科技计划项目(4Y056) 国家重点研发计划(2020YFA0712300)。 

主　　题：线性系统 Gram-Schmidt正交化 隐私保护 同态加密 HEAAN 

摘      要：在科学计算、统计分析以及机器学习领域,许多实际问题都可以归结到线性系统Ax=b的求解,如最小二乘估计和机器学习中的回归分析等。而实际中用于计算的数据往往由不同用户拥有且包含用户的敏感信息。当不同的数据拥有者想在合作求解一个模型的同时保护数据的隐私,同态加密可以作为解决方法之一。针对两个用户参与的场景,基于Cheon等提出的HEAAN同态加密技术,设计了一种两方参与、利用Gram-Schmidt正交化方法安全求解线性系统Ax=b的新方案;提出了一种适用于该场景的交互式安全乘法逆协议,解决了同态加密无法高效计算除法的问题,保证在高效计算的同时保护数据的隐私信息;分析了方案的安全性、通信损耗以及计算复杂度;基于HEAAN同态加密库,利用C++实现了该方案;最后通过大量的实验证明,该方案可以安全高效地求解维度不超过17的线性系统,与在明文数据上的计算结果相比,相对误差不超过0.0001;针对该方案设计的平行编码方法,可以通过SIMD技术并行求解多个线性系统,拓宽了方案的可用性,基本满足特定场景下的实际应用需求,可进一步用于隐私保护数据挖掘算法的设计。