计算机科学 ›› 2022, Vol. 49 ›› Issue (3): 338-345.doi: 10.11896/jsjkx.201200124
吕由1,2, 吴文渊1
LYU You1,2, WU Wen-yuan1
摘要： 在科学计算、统计分析以及机器学习领域,许多实际问题都可以归结到线性系统Ax=b的求解,如最小二乘估计和机器学习中的回归分析等。而实际中用于计算的数据往往由不同用户拥有且包含用户的敏感信息。当不同的数据拥有者想在合作求解一个模型的同时保护数据的隐私,同态加密可以作为解决方法之一。针对两个用户参与的场景,基于Cheon等提出的HEAAN同态加密技术,设计了一种两方参与、利用Gram-Schmidt正交化方法安全求解线性系统Ax=b的新方案;提出了一种适用于该场景的交互式安全乘法逆协议,解决了同态加密无法高效计算除法的问题,保证在高效计算的同时保护数据的隐私信息;分析了方案的安全性、通信损耗以及计算复杂度;基于HEAAN同态加密库,利用C++实现了该方案;最后通过大量的实验证明,该方案可以安全高效地求解维度不超过17的线性系统,与在明文数据上的计算结果相比,相对误差不超过0.000 1;针对该方案设计的平行编码方法,可以通过SIMD技术并行求解多个线性系统,拓宽了方案的可用性,基本满足特定场景下的实际应用需求,可进一步用于隐私保护数据挖掘算法的设计。
中图分类号:
| [1]YANG Q,LIU Y,CHEN T J,et al.Federated Machine Lear-ning:Concept and Applications[J].ACM Transaction on Intelligent Systems and Technology,2019,10(2):19. [2]GENTRY C.Fully Homomorphic Encryption Using Ideal Lat-tices[C]//Proceedings of the 2009 Acm Symposium on Theory of Computing.2009:169-178. [3]YAO A C C.How to generate and exchange secrets[C]//Proceedings of the 27th Annual Symposium on Foundations of Computer Science.IEEE Computer Society,1986:162-167. [4]DWORK C.Differential privacy[M]//Automata,Languages and Programming,Pt 2.Berlin:Springer,2006:1-12. [5]BRAKERSKI Z,VAIKUNTANATHAN V.Efficient Fully Homomorphic Encryption from (Standard) LWE[C]//2011 IEEE 52nd Annual Symposium on Foundations of Computer Science.2011:97-106. [6]BRAKERSKI Z,GENTRY C,VAIKUNTANATHAN V.(Le-veled) Fully Homomorphic Encryption without Bootstrapping[J].ACM Transactions on Computation Theory,2014,6(3):1-36. [7]FAN J,VERCAUTEREN F.Somewhat practical fully homo-morphic encryption[J].IACR Cryptology ePrint Archive,2012(144):1-19. [8]CHEON J H,KIM A,KIM M,et al.Homomorphic Encryption for Arithmetic of Approximate Numbers[M]//Advances in Cryptology-Asiacrypt 2017,Pt I.Cham:Springer.2017:409-437. [9]XU C,CHEN J,WU W,et al.Homomorphically EncryptedArithmetic Operations Over the Integer Ring[M]//Information Security Practice and Experience(ISPEC 2016).Cham:Sprin-ger,2016:167-181. [10]NIKOLAENKO V,WEINSBERG U,IOANNIDIS S,et al.Privacy-Preserving Ridge Regression on Hundreds of Millions of Records.[C]//2013 IEEE Symposium on Security and Privacy.2013:334-348. [11]HU S,WANG Q,WANG J,et al.Securing Fast Learning!Ridge Regression over Encrypted Big Data[C]//2016 IEEE Trustcom/BigDataSE/ISPA.2016:19-26. [12]CHEN Y R,REZAPOUR A,TZENG W G.Privacy-preserving ridge regression on distributed data[J].Information Sciences,2018,451:34-49. [13]GIACOMELLI I,JHA S,JOYE M,et al.Privacy-PreservingRidge Regression with only Linearly-Homomorphic Encryption[M]//Applied Cryptography and Network Security.Cham:Springer,2018:243-261. [14]QIU G,GUI X,ZHAO Y.Privacy-Preserving Linear Regression on Distributed Data by Homomorphic Encryption and Data Masking[J].IEEE Access,2020,8:107601-107613. [15]PAILLIER P.Public-key cryptosystems based on composite degree residuosity classes [C]//Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques.Springer-Verlag,1999:223-238. [16]ZHANG Y,ZHENG P,LUO W,et al.Privacy-Preserving Outsourcing Computation of QR Decomposition in the Encrypted Domain[C]//2019 18th Ieee International Conference on Trust,Security and Privacy in Computing and Communications/13th IEEE International Conference on Big Data Science and Engineering.2019:389-396. [17]STEWART G,MAHAJAN A.Matrix Algorithms,Volume II:Eigensystems[J].Applied Mechanics Reviews,2003,56(1):B2. [18]SMART N P,VERCAUTEREN F.Fully homomorphic SIMD operations[J].Designs Codes and Cryptography,2014,71(1):57-81. [19]CHEON J H,KIM A,KIM M,et al.Implementation ofHEAAN [OL].https://github.com/kimandrik/HEAAN. [20]LYNBASHEVSKY V,PEIKERT C,REGEV O.On Ideal Lattices and Learning with Errors over Rings[M]//Advances in Cryptology－Eurocrypt 2010.Berlin:Springer,2010:1-23. [21]CHEON J H,HAN K,KIM A,et al.Bootstrapping for Approximate Homomorphic Encryption[M]//Advances in Cryptology－Eurocrypt 2018,Pt I.Cham:Springer,2018:360-384. [22] CHEN H,CHILLOTTI I,SONG Y.Improved Bootstrapping for Approximate Homomorphic Encryption[M]//Advances in Cryptology-Eurocrypt 2019,Pt Ii.Cham:Springer,2019:34-54. [23]CHEON J H,HAN K,KIM A,et al.A Full RNS Variant of Approximate Homomorphic Encryption[C]//Selected Areas in Cryptography－SAC 2018.Cham:Springer International Publishing,2019:347-368. [24]KIM A,SONG Y,KIM M,et al.Logistic regression model trai-ning based on the approximate homomorphic encryption[J].BMC Medical Genomics,2018,11(4):23-31. [25]KIM M,SONG Y,WANG S,et al.Secure Logistic Regression Based on Homomorphic Encryption:Design and Evaluation[J].Jmir Medical Informatics,2018,6(2):245-255. [26]GENTRY C,HALEVI S,SMART N P.Homomorphic Evaluation of the AES Circuit[M]//Advances in Cryptology－Crypto 2012.Berlin:Springer,2012:850-867. [27]LINDNER R,PEIKERT C.Better Key Sizes (and Attacks) for LWE-Based Encryption[M]//Topics in Cryptology－CT-RSA 2011.Berlin:Springer,2011:319-339. [28]VICTOR S.NTL:A Library for doing Number Theory[OL].https://www.shoup.net/ntl. |
| [1] | 鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于分层抽样优化的面向异构客户端的联邦学习 Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients 计算机科学, 2022, 49(9): 183-193. https://doi.org/10.11896/jsjkx.220500263 |
| [2] | 汤凌韬, 王迪, 张鲁飞, 刘盛云. 基于安全多方计算和差分隐私的联邦学习方案 Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy 计算机科学, 2022, 49(9): 297-305. https://doi.org/10.11896/jsjkx.210800108 |
| [3] | 吕由, 吴文渊. 隐私保护线性回归方案与应用 Privacy-preserving Linear Regression Scheme and Its Application 计算机科学, 2022, 49(9): 318-325. https://doi.org/10.11896/jsjkx.220300190 |
| [4] | 王健. 基于隐私保护的反向传播神经网络学习算法 Back-propagation Neural Network Learning Algorithm Based on Privacy Preserving 计算机科学, 2022, 49(6A): 575-580. https://doi.org/10.11896/jsjkx.211100155 |
| [5] | 李利, 何欣, 韩志杰. 群智感知的隐私保护研究综述 Review of Privacy-preserving Mechanisms in Crowdsensing 计算机科学, 2022, 49(5): 303-310. https://doi.org/10.11896/jsjkx.210400077 |
| [6] | 秦小月, 黄汝维, 杨波. 基于素数幂次阶分圆环的NTRU型全同态加密方案 NTRU Type Fully Homomorphic Encryption Scheme over Prime Power Cyclotomic Rings 计算机科学, 2022, 49(5): 341-346. https://doi.org/10.11896/jsjkx.210300089 |
| [7] | 王美珊, 姚兰, 高福祥, 徐军灿. 面向医疗集值数据的差分隐私保护技术研究 Study on Differential Privacy Protection for Medical Set-Valued Data 计算机科学, 2022, 49(4): 362-368. https://doi.org/10.11896/jsjkx.210300032 |
| [8] | 任花, 牛少彰, 王茂森, 岳桢, 任如勇. 基于奇异值分解的同态可交换脆弱零水印研究 Homomorphic and Commutative Fragile Zero-watermarking Based on SVD 计算机科学, 2022, 49(3): 70-76. https://doi.org/10.11896/jsjkx.210800015 |
| [9] | 孔钰婷, 谭富祥, 赵鑫, 张正航, 白璐, 钱育蓉. 基于差分隐私的K-means算法优化研究综述 Review of K-means Algorithm Optimization Based on Differential Privacy 计算机科学, 2022, 49(2): 162-173. https://doi.org/10.11896/jsjkx.201200008 |
| [10] | 金华, 朱靖宇, 王昌达. 视频隐私保护技术综述 Review on Video Privacy Protection 计算机科学, 2022, 49(1): 306-313. https://doi.org/10.11896/jsjkx.201200047 |
| [11] | 张小艳, 李秦伟, 付福杰. 基于数字承诺的区块链交易金额保密验证方法 Secret Verification Method of Blockchain Transaction Amount Based on Digital Commitment 计算机科学, 2021, 48(9): 324-329. https://doi.org/10.11896/jsjkx.200800123 |
| [12] | 雷羽潇, 段玉聪. 面向跨模态隐私保护的AI治理法律技术化框架 AI Governance Oriented Legal to Technology Bridging Framework for Cross-modal Privacy Protection 计算机科学, 2021, 48(9): 9-20. https://doi.org/10.11896/jsjkx.201000011 |
| [13] | 王辉, 朱国宇, 申自浩, 刘琨, 刘沛骞. 基于用户偏好和位置分布的假位置生成方法 Dummy Location Generation Method Based on User Preference and Location Distribution 计算机科学, 2021, 48(7): 164-171. https://doi.org/10.11896/jsjkx.200800069 |
| [14] | 季琰, 戴华, 姜莹莹, 杨庚, 易训. 面向混合云的可并行多关键词Top-k密文检索技术 Parallel Multi-keyword Top-k Search Scheme over Encrypted Data in Hybrid Clouds 计算机科学, 2021, 48(5): 320-327. https://doi.org/10.11896/jsjkx.200300160 |
| [15] | 郭蕊, 芦天亮, 杜彦辉. WSN中基于目标决策的源位置隐私保护方案 Source-location Privacy Protection Scheme Based on Target Decision in WSN 计算机科学, 2021, 48(5): 334-340. https://doi.org/10.11896/jsjkx.200400099 |
|
||
首页