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

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

Abstract

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

CLC Number:

TN92

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.

Figures/Tables 7

方案	密文加法	明文-密文乘法	密文旋转	密文条数	密文深度
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

算法	密文加法	明文-密文乘法	密文旋转	密文条数	密文深度
算法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

矩阵规模	加密时间/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

矩阵规模	方案	加解密时间/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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

方案	加解密时间/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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 51

Related Articles 15

Metrics

Recommended 0

[1]	Lingjin KONG, Kai MEI, Xiaoran LIU, Jun XIONG, Haitao ZHAO, Jibo WEI. Design and implementation of online learning assisted intelligent receiver [J]. Journal on Communications, 2024, 45(1): 18-30.
[2]	Zhibo QI, Lei DU, Ru HUO, Fan YANG, Tao HUANG. Multi-camera video collaborative analysis method based on edge computing [J]. Journal on Communications, 2023, 44(8): 14-26.
[3]	Xiaolin CHEN, Daoguang ZAN, Bingchao WU, Bei GUAN, Yongji WANG. Adversarial sample generation algorithm for vertical federated learning [J]. Journal on Communications, 2023, 44(8): 1-13.
[4]	Xiaoxue GONG, Jiahao PANG, Qihan ZHANG, Changle XU, Wenshuai QIN, Lei GUO. Machine learning-based detection, identification and restoration method of jamming attacks in optical networks [J]. Journal on Communications, 2023, 44(7): 159-170.
[5]	Zhuo MA, Jiayu JIN, Yilong YANG, Yang LIU, Zuobin YING, Teng LI, Junwei ZHANG. Adaptive federated learning secure aggregation scheme based on threshold homomorphic encryption [J]. Journal on Communications, 2023, 44(7): 76-85.
[6]	Xindi MA, Qinghua LI, Qi JIANG, Zhuo MA, Sheng GAO, Youliang TIAN, Jianfeng MA. Byzantine-robust federated learning over Non-IID data [J]. Journal on Communications, 2023, 44(6): 138-153.
[7]	Qianyi DAI, Bin ZHANG, Song GUO, Kaiyong XU. Blockchain network layer anomaly traffic detection method based on multiple classifier integration [J]. Journal on Communications, 2023, 44(3): 66-80.
[8]	Bowen ZHAO, Yao ZHU, Yang XIAO, Qingqi PEI, Xiaoguo LI, Ximeng LIU. Rational-security and fair two-party comparison protocol [J]. Journal on Communications, 2023, 44(12): 112-123.
[9]	Jihong YU, Ziyan LIN, Neng YE, Kai YANG, Jianping AN. Covert communication method based on tripartite generative adversarial network [J]. Journal on Communications, 2023, 44(11): 225-236.
[10]	Shengxing YU, Zhong CHEN. Efficient secure federated learning aggregation framework based on homomorphic encryption [J]. Journal on Communications, 2023, 44(1): 14-28.
[11]	Yatao YANG, Deli LIU, Peihe LIU, Ping ZENG, Song XIAO. BFV-Blockchainvoting: blockchain-based electronic voting systems with BFV full homomorphic encryption [J]. Journal on Communications, 2022, 43(9): 100-111.
[12]	Xuewang ZHANG, Zhihong LI, Jinzhao LIN. Privacy protection scheme based on fair blind signature and hierarchical encryption for consortium blockchain [J]. Journal on Communications, 2022, 43(8): 131-141.
[13]	Gaofeng HE, Qianfeng WEI, Xiancai XIAO, Haiting ZHU, Bingfeng XU. Confirmation method for the detection of malicious encrypted traffic with data privacy protection [J]. Journal on Communications, 2022, 43(2): 156-170.
[14]	Haining YU, Hongli ZHANG, Xiangzhan YU, Jiaxing QU, Mengmeng GE. Privacy-preserving trajectory similarity computation method [J]. Journal on Communications, 2022, 43(11): 1-13.
[15]	Yanhui LU, Han LIU, Hang LI, Guangxu ZHU. Time series generation model based on multi-discriminator generative adversarial network [J]. Journal on Communications, 2022, 43(10): 167-176.