同态明文-密文矩阵运算及其应用

doi:10.11959/j.issn.1000-436x.2024024

通信学报 ›› 2024, Vol. 45 ›› Issue (2): 150-161.doi: 10.11959/j.issn.1000-436x.2024024

• 学术论文 • 上一篇

同态明文-密文矩阵运算及其应用

刘洋¹, 杨林翰¹, 陈经纬²^,³, 吴文渊²^,³, 冯勇²^,³

¹ 重庆交通大学信息科学与工程学院，重庆 400074
² 中国科学院重庆绿色智能技术研究院生物计算安全重庆市重点实验室，重庆 400714
³ 中国科学院大学重庆学院，重庆 400714

修回日期:2023-12-14 出版日期:2024-02-01 发布日期:2024-02-01
作者简介:刘洋（1984− ），女，湖北咸宁人，博士，重庆交通大学副教授、硕士生导师，主要研究方向为形式化验证、网络信息安全等
杨林翰（2000− ），男，重庆人，重庆交通大学硕士生，主要研究方向为信息安全、密文计算等
陈经纬（1984− ），男，四川巴中人，博士，中国科学院重庆绿色智能技术研究院副研究员、硕士生导师，主要研究方向为信息安全、格算法及其应用等
吴文渊（1976− ），男，四川成都人，博士，中国科学院重庆绿色智能技术研究院研究员、博士生导师，主要研究方向为符号数值计算、信息安全
冯勇（1965− ），男，四川宁南人，博士，中国科学院重庆绿色智能技术研究院研究员、博士生导师，主要研究方向为符号数值计算、信息安全
基金资助:
国家重点研发计划基金资助项目(2020YFA0712303);重庆市自然科学基金资助项目(CSTB2023NSCQ-MSX0441);重庆市自然科学基金资助项目(cstc2021jcyj-msxmX0821);重庆市自然科学基金资助项目(cstc2021yszx-jcyjX0004);重庆市自然科学基金资助项目(2022YSZX-JCX0011CSTB);重庆市自然科学基金资助项目(CSTB2023YSZX-JCX0008)

Matrix computation over homomorphic plaintext-ciphertext and its application

Yang LIU¹, Linhan YANG¹, Jingwei CHEN²^,³, Wenyuan WU²^,³, Yong FENG²^,³

¹ School of Information Science and Engineering, Chongqing Jiaotong University, Chongqing 400074, China
² Chongqing Key Laboratory of Secure Computing for Biology, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, China
³ Chongqing School, University of Chinese Academy of Sciences, Chongqing 400714, China

Revised:2023-12-14 Online:2024-02-01 Published:2024-02-01
Supported by:
The National Key Research and Development Program of China(2020YFA0712303);The Natural Science Foundation of Chongqing(CSTB2023NSCQ-MSX0441);The Natural Science Foundation of Chongqing(cstc2021jcyj-msxmX0821);The Natural Science Foundation of Chongqing(cstc2021yszx-jcyjX0004);The Natural Science Foundation of Chongqing(2022YSZX-JCX0011CSTB);The Natural Science Foundation of Chongqing(CSTB2023YSZX-JCX0008)

摘要/Abstract

摘要：

支持单指令多数据操作的同态加密方案能有效提高密文计算的均摊效率，但密文结构导致矩阵运算复杂度高。在许多应用中，采用明文-密文矩阵操作可以在确保安全的同时实现隐私计算。基于此，提出一个适用于任意维数的明文-密文矩阵乘法方案。该方案通过明文矩阵编码和密文矩阵维数变换等步骤计算得到密文结果。与已知最好的 Jiang 等所提的密文方阵乘法算法相比，所提方案支持任意维数的矩阵乘法，并支持矩阵连乘；理论分析和实验结果均表明，所提方案具有更低的密文旋转复杂度和更高的计算效率。将所提方案应用在隐私保护的贝叶斯分类器中，能以更高安全参数和更少计算时间完成分类任务。

关键词: 同态加密, 矩阵运算, 机器学习, 贝叶斯分类器

Abstract:

Those homomorphic encryption schemes supporting single instruction multiple data (SIMD) operations effectively enhance the amortized efficiency of ciphertext computations, yet the structure of ciphertexts leads to high complexity in matrix operations.In many applications, employing plaintext-ciphertext matrix operations can achieve privacy-preserving computing.Based on this, a plaintext-ciphertext matrix multiplication scheme for matrices of arbitrary dimension was proposed.The resulting ciphertext was computed through steps such as encoding the plaintext matrix, transforming the dimensions of the encrypted matrix, etc.Compared to the best-known encrypted matrix multiplication algorithm for square matrices proposed by Jiang et al., the proposed scheme supported matrix multiplication of arbitrary dimension, and consecutive matrix multiplications.Both theoretical analysis and experimental results show that the proposed scheme requires less rotations on ciphertexts and hence features higher efficiency.When applied to a privacy-preserving Bayesian classifier, the proposed scheme can complete classification tasks with higher security parameters and reduced running time.

Key words: homomorphic encryption, matrix computation, machine learning, Bayesian classifier

中图分类号:

TN92

刘洋, 杨林翰, 陈经纬, 吴文渊, 冯勇. 同态明文-密文矩阵运算及其应用[J]. 通信学报, 2024, 45(2): 150-161.

Yang LIU, Linhan YANG, Jingwei CHEN, Wenyuan WU, Yong FENG. Matrix computation over homomorphic plaintext-ciphertext and its application[J]. Journal on Communications, 2024, 45(2): 150-161.

图/表 7

表1

一次明文-密文矩阵乘法方案计算开销比较"

方案	密文加法	明文-密文乘法	密文旋转	密文条数	密文深度
Halevi等^[42]	$2 p \sqrt{n}$	pn	$2 p \sqrt{n}$	p	1CMult
Jiang等^[25]	4d	2d	$d + 2 \sqrt{d}$	1	2CMult
本文算法4	2m-1	2m-1	$3 \sqrt{m}$	1	1CMult
本文算法4+算法5	p+m+n- 1	p+m+n- 1	$2 (\sqrt{p} + \sqrt{m + n - 1})$	1	2CMult

表1

表2

计算开销比较"

算法	密文加法	明文-密文乘法	密文旋转	密文条数	密文深度
算法4	2m-1	2m-1	$3 \sqrt{m}$	1	1CMult
算法5	p	p	$2 \sqrt{p}$	1	1CMult
算法4+算法5	p+m+n- 1	p+m+n- 1	$2 (\sqrt{p} + \sqrt{m + n - 1})$	1	2CMult

表2

表3

4种规模的矩阵的运算时间"

矩阵规模	加密时间/ms	解密时间/ms	算法4的时间/ms	算法5的时间/ms	总时间/ms
$R^{16 \times 16} \times R^{16 \times 128}$	3.08	0.51	62.16	—	65.75
$R^{16 \times 16} \times R^{16 \times 256}$	2.81	0.52	48.10	—	51.43
$R^{16 \times 4} \times R^{4 \times 128}$	2.51	0.22	24.92	148.04	175.69
$R^{16 \times 4} \times R^{4 \times 256}$	3.07	0.22	21.38	257.42	282.09

表3

表4

矩阵运算效率"

矩阵规模	方案	加解密时间/ms	矩阵乘法时间/ms	密文个数/个	总时间/ms
$R^{16 \times 16} \times R^{16 \times 16}$	Halevi等^[42]	50.82	343.80	16	394.62
	Jiang等^[25]	3.20	64.24	1	67.44
	算法4	3.35	66.83	1	70.18
$R^{32 \times 32} \times R^{32 \times 32}$	Halevi等^[42]	112.40	1393.50	32	1 505.9
	Jiang等^[25]	3.48	143.85	1	147.33
	算法4	4.02	112.74	1	116.76
$R^{64 \times 64} \times R^{64 \times 64}$	Halevi等^[42]	225.85	4747.44	64	4 973.29
	Jiang等^[25]	3.48	234.70	1	238.18
	算法4	3.46	168.28	1	171.74

表4

图1

表5

表6

参考文献 51

[1]	LIN G B , LI H , ZHANG Y Y ,et al. Dynamic momentum for deep learning with differential privacy[C]// International Conference on Machine Learning for Cyber Security. Berlin:Springer, 2023: 180-190.
[2]	DWORK C , KENTHAPADI K , MCSHERRY F ,et al. Our data,ourselves:privacy via distributed noise generation[C]// Proceedings of the 24th Annual International Conference on The Theory and Applications of Cryptographic Techniques. New York:ACM Press, 2006: 486-503.
[3]	DWORK C , ROTH A . The algorithmic foundations of differential privacy[J]. Foundations and Trends? in Theoretical Computer Science, 2013,9(3/4): 211-407.
[4]	DWORK C . Differential privacy:a survey of results[C]// International Conference on Theory and Applications of Models of Computation. Berlin:Springer, 2008: 1-19.
[5]	DU W L , ATALLAH M J . Secure multi-party computation problems and their applications:a review and open problems[C]// Proceedings of the Workshop on New Security Paradigms. New York:ACM Press, 2001: 13-22.
[6]	YAO A C C . How to generate and exchange secrets[C]// Proceedings of the 27th Annual Symposium on Foundations of Computer Science (SFCS 1986). Piscataway:IEEE Press, 1986: 162-167.
[7]	MOHASSEL P , ZHANG Y P . SecureML:a system for scalable privacy-preserving machine learning[C]// Proceedings of IEEE Symposium on Security and Privacy (SP). Piscataway:IEEE Press, 2017: 19-38.
[8]	YANG Q , LIU Y , CHEN T J ,et al. Federated machine learning:concept and applications[J]. arXiv Preprint,arXiv:1902.04885, 2019.
[9]	LI L , FAN Y X , TSE M ,et al. A review of applications in federated learning[J]. Computers ＆ Industrial Engineering, 2020,149:106854.
[10]	MCMAHAN H B , MOORE E , RAMAGE D ,et al. Communication-efficient learning of deep networks from decentralized data[J]. arXiv Preprint,arXiv:1602.05629, 2016.
[11]	RIVEST R L , ADLEMAN L , DERTOUZOS M L . On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978,4(11): 169-180.
[12]	GIACOMELLI I , JHA S , JOYE M ,et al. Privacy-preserving ridge regression with only linearly-homomorphic encryption[C]// International Conference on Applied Cryptography and Network Security. Berlin:Springer, 2018: 243-261.
[13]	HALL R , FIENBERG S E , NARDI Y . Secure multiple linear regression based on homomorphic encryption[J]. Journal of Official Statistics, 2011,27(4): 669-691.
[14]	HAN K , JEONG J , SOHN J H ,et al. Efficient privacy preserving logistic regression inference and training[J]. IACR Cryptology ePrint Archive,2020, 2020:1396.
[15]	YU X P , ZHAO W , HUANG Y F ,et al. Privacy-preserving outsourced logistic regression on encrypted data from homomorphic encryption[J]. Security and Communication Networks,2022, 1396:1321198.
[16]	吕由, 吴文渊 . 两方参与的隐私保护岭回归方案与应用[J]. 密码学报, 2023,10(2): 276-288.
	LYU Y , WU W Y . Two-party privacy-preserving ridge regression scheme with applications[J]. Journal of Cryptologic Research, 2023,10(2): 276-288.
[17]	CHEN J W , FENG Y , LIU Y ,et al. Non-interactive privacy-preserving Na?ve Bayes classifier using homomorphic encryption[C]// International Conference on Security and Privacy in New Computing Environments. Berlin:Springer, 2022: 192-203.
[18]	SUN X Q , ZHANG P , LIU J K ,et al. Private machine learning classification based on fully homomorphic encryption[J]. IEEE Transactions on Emerging Topics in Computing, 2020,8(2): 352-364.
[19]	TANG W R , ZHOU Y H , LI M S ,et al. Differential privacy preserving naive Bayes classification via wavelet transform[C]// Proceedings of International Conference on Networking and Network Applications (NaNA). Piscataway:IEEE Press, 2020: 81-85.
[20]	WOOD A , SHPILRAIN V , NAJARIAN K ,et al. Private naive Bayes classification of personal biomedical data:application in cancer data analysis[J]. Computers in Biology and Medicine, 2019,105: 144-150.
[21]	YASUMURA Y , ISHIMAKI Y , YAMANA H . Secure Na?ve Bayes classification protocol over encrypted data using fully homomorphic encryption[C]// Proceedings of the 21st International Conference on Information Integration and Web-based Applications ＆ Services. New York:ACM Press, 2019: 45-54.
[22]	PANDA S . Principal component analysis using CKKS homomorphic scheme[C]// International Symposium on Cyber Security Cryptography and Machine Learning. Berlin:Springer, 2021: 52-70.
[23]	MA X R . Improved privacy-preserving PCA using optimized homomorphic matrix multiplication[J]. arXiv Preprint,arXiv:2305.17341, 2023.
[24]	RATHEE D , MISHRA P K , YASUDA M . Faster PCA and linear regression through hypercubes in HElib[C]// Proceedings of the Workshop on Privacy in the Electronic Society. New York:ACM Press, 2018: 42-53.
[25]	JIANG X Q , KIM M , LAUTER K ,et al. Secure outsourced matrix computation and application to neural networks[C]// Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. New York:ACM Press, 2018: 1209-1222.
[26]	LEE J W , KANG H , LEE Y ,et al. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network[J]. IEEE Access, 2022,10: 30039-30054.
[27]	LEE E , LEE J W , LEE J ,et al. Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions[C]// Proceedings of the International Conference on Machine Learning. New York:PMLR, 2022: 1-20.
[28]	MIHARA K , YAMAGUCHI R , MITSUISHI M ,et al. Neural network training with homomorphic encryption[J]. arXiv Preprint,arXiv:2012.13552, 2020.
[29]	LOU Q , FENG B , FOX G C ,et al. Glyph:fast and accurately training deep neural networks on encrypted data[J]. arXiv Preprint,arXiv:1911.07101, 2019.
[30]	PODSCHWADT R , TAKABI D . Non-interactive privacy preserving recurrent neural network prediction with homomorphic encryption[C]// Proceedings of IEEE 14th International Conference on Cloud Computing (CLOUD). Piscataway:IEEE Press, 2021: 65-70.
[31]	GENTRY C . A fully homomorphic encryption scheme[D]. State of California:Stanford University, 2009.
[32]	BRAKERSKI Z , GENTRY C , VAIKUNTANATHAN V . (Leveled) fully homomorphic encryption without bootstrapping[C]// Proceedings of 3rd Innovations in Theoretical Computer Science Conference. New York:ACM Press, 2012: 309-325.
[33]	FAN J F , VERCAUTEREN F . Somewhat practical fully homomorphic encryption[J]. IACR Cryptology ePrint Archive, 2012,144: 1-19.
[34]	DUCAS L , MICCIANCIO D . FHEW:bootstrapping homomorphic encryption in less than a second[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2015: 617-640.
[35]	CHILLOTTI I , GAMA N , GEORGIEVA M ,et al. TFHE:fast fully homomorphic encryption over the torus[J]. Journal of Cryptology, 2020,33(1): 34-91.
[36]	CHEON J H , KIM A , KIM M ,et al. Homomorphic encryption for arithmetic of approximate numbers[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2017: 409-437.
[37]	SMART N P , VERCAUTEREN F . Fully homomorphic SIMD operations[J]. Designs,Codes and Cryptography, 2014,71(1): 57-81.
[38]	LIU F H , WANG H . Batch bootstrapping II:bootstrapping in polynomial modulus only requires O～(1) the multiplications in amortization[C]// Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2023: 353-384.
[39]	KIM D , GUYOT C . Optimized privacy-preserving CNN inference with fully homomorphic encryption[J]. IEEE Transactions on Information Forensics and Security, 2023,18: 2175-2187.
[40]	HALEVI S , SHOUP V . Algorithms in HElib[C]// Proceedings of the Advances in Cryptology–CRYPTO 2014:34th Annual Cryptology Conference. Berlin:Springer, 2014: 554-571.
[41]	LEIGHTON F T . Introduction to parallel algorithms and architectures:arrays,trees,hypercubes[M]. San Francisco: Morgan Kaufmann Publishers Inc., 1991.
[42]	HALEVI S , SHOUP V . Bootstrapping for HElib[J]. Journal of Cryptology, 2021,34(1): 7.
[43]	HUANG H , ZONG H R . Secure matrix multiplication based on fully homomorphic encryption[J]. The Journal of Supercomputing, 2023,79(5): 5064-5085.
[44]	HUANG Z C , HONG C , WENG C K ,et al. More efficient secure matrix multiplication for unbalanced recommender systems[J]. IEEE Transactions on Dependable and Secure Computing, 2023,20(1): 551-562.
[45]	JANG J , LEE Y , KIM A ,et al. Privacy-preserving deep sequential model with matrix homomorphic encryption[C]// Proceedings of ACM on Asia Conference on Computer and Communications Security. New York:ACM Press, 2022: 377-391.
[46]	BABENKO M , GOLIMBLEVSKAIA E , TCHERNYKH A ,et al. A comparative study of secure outsourced matrix multiplication based on homomorphic encryption[J]. Big Data and Cognitive Computing, 2023,7(2): 84.
[47]	DUONG D H , MISHRA P K , YASUDA M . Efficient secure matrix multiplication over LWE-based homomorphic encryption[J]. Tatra Mountains Mathematical Publications, 2016,67(1): 69-83.
[48]	YASUDA M , SHIMOYAMA T , KOGURE J ,et al. Secure statistical analysis using RLWE-based homomorphic encryption[C]// Australasian Conference on Information Security and Privacy. Berlin:Springer, 2015: 471-487.
[49]	YASUDA M , SHIMOYAMA T , KOGURE J ,et al. New packing method in somewhat homomorphic encryption and its applications[J]. Security and Communication Networks, 2015,8(13): 2194-2213.
[50]	MISHRA P K , DUONG D H , YASUDA M . Enhancement for secure multiple matrix multiplications over ring-LWE homomorphic encryption[C]// International Conference on Information Security Practice and Experience. Berlin:Springer, 2017: 320-330.
[51]	ALBRECHT M R , PLAYER R , SCOTT S . On the concrete hardness of learning with errors[J]. Journal of Mathematical Cryptology, 2015,9(3): 169-203.

方案	加解密时间/ms	密文计算时间/ms	总时间/ms	样本平均时间/ms	密文大小/KB
算法4	3.57	60.75	64.32	2.14	385
Jiang等^[25]	3.08	177.42	180.50	6.02	385
文献[17]	580	1272	1852	61.7	40 980

方案	加解密时间/ms	密文计算时间/ms	总时间/ms	样本平均时间/ms	密文大小/KB
算法4	32.93	1 300.23	1 333.16	6.50	3856
Jiang等^[25]	25.62	1 786.45	1 812.07	8.84	3085
文献[17]	2 773	2 680	5 453	26.6	180 875

同态明文-密文矩阵运算及其应用

Matrix computation over homomorphic plaintext-ciphertext and its application

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 51

相关文章 15

Metrics

推荐阅读 0

[1]	孔凌劲, 梅锴, 刘潇然, 熊俊, 赵海涛, 魏急波. 在线学习辅助的智能接收机设计与实现[J]. 通信学报, 2024, 45(1): 18-30.
[2]	期治博, 杜磊, 霍如, 杨帆, 黄韬. 基于边缘计算的多摄像头视频协同分析方法[J]. 通信学报, 2023, 44(8): 14-26.
[3]	陈晓霖, 昝道广, 吴炳潮, 关贝, 王永吉. 面向纵向联邦学习的对抗样本生成算法[J]. 通信学报, 2023, 44(8): 1-13.
[4]	巩小雪, 庞嘉豪, 张琦涵, 徐长乐, 秦文帅, 郭磊. 基于机器学习的光网络干扰攻击检测、识别与恢复方法[J]. 通信学报, 2023, 44(7): 159-170.
[5]	马卓, 金嘉玉, 杨易龙, 刘洋, 应作斌, 李腾, 张俊伟. 基于门限同态加密的自适应联邦学习安全聚合方案[J]. 通信学报, 2023, 44(7): 76-85.
[6]	马鑫迪, 李清华, 姜奇, 马卓, 高胜, 田有亮, 马建峰. 面向Non-IID数据的拜占庭鲁棒联邦学习[J]. 通信学报, 2023, 44(6): 138-153.
[7]	戴千一, 张斌, 郭松, 徐开勇. 基于多分类器集成的区块链网络层异常流量检测方法[J]. 通信学报, 2023, 44(3): 66-80.
[8]	赵搏文, 祝遥, 肖阳, 裴庆祺, 李小国, 刘西蒙. 理性安全的公平两方比较协议[J]. 通信学报, 2023, 44(12): 112-123.
[9]	于季弘, 林子砚, 叶能, 杨凯, 安建平. 基于三方生成对抗网络的隐蔽通信方法[J]. 通信学报, 2023, 44(11): 225-236.
[10]	余晟兴, 陈钟. 基于同态加密的高效安全联邦学习聚合框架[J]. 通信学报, 2023, 44(1): 14-28.
[11]	杨亚涛, 刘德莉, 刘培鹤, 曾萍, 肖嵩. BFV-Blockchainvoting：支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9): 100-111.
[12]	张学旺, 黎志鸿, 林金朝. 基于公平盲签名和分级加密的联盟链隐私保护方案[J]. 通信学报, 2022, 43(8): 131-141.
[13]	何高峰, 魏千峰, 肖咸财, 朱海婷, 徐丙凤. 支持数据隐私保护的恶意加密流量检测确认方法[J]. 通信学报, 2022, 43(2): 156-170.
[14]	于海宁, 张宏莉, 余翔湛, 曲家兴, 葛蒙蒙. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022, 43(11): 1-13.
[15]	冯智斌, 徐煜华, 杜智勇, 刘鑫, 李文, 韩昊, 张晓博. 对抗智能干扰的主动防御技术[J]. 通信学报, 2022, 43(10): 42-54.