环LWE上高效的多密钥全同态加密方案

doi:10.19665/j.issn1001-2400.2021.01.010

Abstract

Abstract:

The ring-LWE-based BGV-type multi-key fully homomorphic encryption (MKFHE) scheme has a large size of ciphertexts and keys,and the generation process of evaluation key is complicated,which results in a low homomorphic evaluating efficiency.To improve these problems,a BGV-type MKFHE scheme with a small-size key and a high efficiency of evaluation of key generation is proposed.First,by modifying the expansion of the ciphertext,the algorithm for generation of the evaluation key is optimized and the efficiency of the algorithm is improved.Second,the low bit discarding technique is used in the generation algorithm,which reduces the calculated redundancy and decreases the calculated complexity.Finally,by applying modulus-switching and key-switching techniques to the optimized algorithm,an efficient leveled BGV-type MKFHE scheme with IND-CPA security is proposed.Compared with the previous leveled BGV-type MKFHE schemes,the proposed scheme can simplify the process of generation of the evaluation key and decrease memory (bit-size) and calculation costs.Moreover,the proposed scheme has a higher efficiency and a less noise magnitude.

Key words: multi-key fully homomorphic encryption, ciphertext expansion algorithm, evaluation key, key-switching, hybrid homomorphic multiplication

CLC Number:

TP309

CHE Xiaoliang,ZHOU Haonan,YANG Xiaoyuan,ZHOU Tanping,LIU Longfei,LI Ningbo. Efficient multi-key fully homomorphic encryption scheme from RLWE[J].Journal of Xidian University, 2021, 48(1): 87-95.

Figures/Tables 2

算法类型	公钥尺寸	计算密钥的密文尺寸	扩展密文尺寸
LZY⁺19的计算密钥生成算法	k(β_l×2)nβ_l	k(β_l×4)nβ_l	n $β l 2$ k(k+1)²
CDKS19的计算密钥生成算法	k(β_l×2)nβ_l	k(β_l×3)nβ_l
文中构造的计算密钥生成算法	k(v_l+2)nβ_l	k(v_l×2+2)nβ_l	nβ_lk(k+1)²

方案类型	扩展密文尺寸	公钥尺寸	生成计算密钥的密文尺寸	完成一次同态乘法解密产生的噪声值
LZY⁺19方案	(k+1)nβ_l	k(β_l×2)nβ_l	(8β_l+4)β_ln	O(k² $β l 3$ n⁴B²)
文中方案	(k+1)nβ_l	k(v_l+2)nβ_l	(3v_l+4)β_ln	O(k² $β l 3$ n³B²)

References 20

[1]	LOPEZ-ALT A, TROMER E, VAIKUNTANATHAN V. On-the-fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption [C]//Proceedings of the 2012 Annual ACM Symposium on Theory of Computing.New York:ACM, 2012: 1219-1234.
[2]	QAOSAR M, ZAMANA, SIDDIQUE M.A,et al.Privacy-preserving Secure Computation of Skyline Query in Distributed Multi-party Databases[J]. Information, 2019,10(3):119-135.
[3]	KIRAN A, PURI M, SURESH S. Privacy Preserving Model Using Homomorphic Encryption[J]. International Journal of Computer Applications, 2019,182(38):12-18.
[4]	韩鹍, 张海林, 辛丹, 等. 利用身份的全同态加密函数库设计方法[J]. 西安电子科技大学学报, 2017,44(4):56-61.
	HAN Kun, ZHANG Hailin, XIN Dan, et al. Design Method of An Identity-based Fully Homomorphic Encryption Library[J]. Journal of Xidian University, 2017,44(4):56-61.
[5]	DORÖZ Y, HU Y, SUNAR B. Homomorphic AES Evaluation Using the Modified LTV Scheme[J]. Designs,Codes,and Cryptography, 2016,80(2):333-358.
[6]	CHONGCHITMATE W, OSTROVSHY R. Circuit-private Multi-key FHE [C]//Lecture Notes in Computer Science:10175.Heidelberg:Springer Verlag, 2017: 241-270.
[7]	CHE X L, ZHOU T P, LI N B, et al. Modified Multi-key Fully Homomorphic Encryption Based on NTRU Cryptosystem without Key-switching[J]. Tsinghua Science and Technology, 2020,25(5):564-578.
[8]	GENTRY C, SAHAI A, WATERS B. Homomorphic Encryption from Learning with Errors:Conceptually-simpler,Asymptotically-faster,Attribute-based [C]//Lecture Notes in Computer Science:8042.Heidelberg:Springer Verlag, 2013: 75-92.
[9]	CLEAR M, MCGOLDRICK C. Multi-identity and Multi-key Leveled FHE from Learning with Errors [C]//Lecture Notes in Computer Science:9216.Heidelberg:Springer Verlag, 2015: 630-656.
[10]	MUKHEJEE P, WICHS D. Two Round Multiparty Computation via Multi-key FHE [C]//Lecture Notes in Computer Science:9666.Heidelberg:Springer Verlag, 2016: 735-763.
[11]	PEIKERT C, SHIEHIAN S. Multi-key FHE from LWE,Revisited [C]//Lecture Notes in Computer Science:9986.Heidelberg:Springer Verlag, 2016: 217-238.
[12]	BRAKERSHI Z, PERLMAN R. Lattice-based Fully Dynamic Multi-key FHE with Short Ciphertexts [C]//Lecture Notes in Computer Science:9814.Heidelberg:Springer Verlag, 2016: 190-213.
[13]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster Fully Homomorphic Encryption:Bootstrapping in Less Than 0.1 Seconds [C]//Lecture Notes in Computer Science:10031.Heidelberg:Springer Verlag, 2016: 3-33.
[14]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE [C]//Lecture Notes in Computer Science:10624.Heidelberg:Springer Verlag, 2017: 377-408.
[15]	CHEN H, CHILLOTTI I, SONG Y. Multi-key Homomorphic Encryption from TFHE [C]//Advances in Cryptology-ASIACRYPT.2019,Proceedings of 25th International Conference on the Theory and Application of Cryptology and Information Security,Berlin:Springer, 2019: 446-472.
[16]	CHEN L, ZHANG Z F, WANG X Q. Batched Multi-hop Multi-key FHE from Ring-LWE with Compact Ciphertext Extension [C]//Lecture Notes in Computer Science:10678.Heidelberg:Springer Verlag, 2017: 597-627.
[17]	LI N B, ZHOU T P, YANG X Y, et al. Efficient Multi-key FHE with Short Extended Ciphertexts and Directed Decryption Protocol[J].IEEE Access, 2019(7):56724-56732.
[18]	CHEN H, KIM M, DAI W, et al. Efficient Multi-key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network Inference [C]//Proceedings of the 2019 ACM Conference on Computer and Communications Security.New York:ACM, 2019: 395-412.
[19]	CHEON J H, KIM A, KIM M, et al. Homomorphic Encryption for Arithmetic of Approximate Numbers [C]//Lecture Notes in Computer Science:10624.Heidelberg:Springer Verlag, 2017: 409-437.
[20]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V.(Leveled) Fully Homomorphic Encryption without Bootstrapping [C]//Innovations in Theoretical Computer Science Conference.New York:ACM, 2012: 309-325.

Efficient multi-key fully homomorphic encryption scheme from RLWE

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 20

Related Articles 15

Metrics

Comments

Recommended 10

[1]	YANG Xiaoyuan,TANG Hongqiong,NIU Ke,ZHANG Yingnan. Video steganography based on macroblock complexity [J]. Journal of Xidian University, 2022, 49(2): 164-172.
[2]	XIE Lixia,NI Huiyu. Key business node identification model for the business process [J]. Journal of Xidian University, 2022, 49(2): 190-197.
[3]	YAN Xixi,ZHAO Qiang,TANG Yongli,LI Yingying,LI Jingran. Multi-keyword search encryption scheme supporting flexible access control [J]. Journal of Xidian University, 2022, 49(1): 55-66.
[4]	LI Xuelian,ZHANG Xiachuan,GAO Juntao,XIANG Dengmei. Blockchain data sharing scheme supporting attribute and proxy re-encryption [J]. Journal of Xidian University, 2022, 49(1): 1-16.
[5]	HUANG Mengmeng,WU Gaofei. New class of complete permutation monomials over finite fields [J]. Journal of Xidian University, 2022, 49(1): 102-110.
[6]	XU Hua,TIAN Youliang. Protection of privacy of the weighted social network under differential privacy [J]. Journal of Xidian University, 2022, 49(1): 17-25.
[7]	YANG Haibin,LI Ruifeng,YI Zhengge,NIU Ke,YANG Xiaoyuan. Efficient cloud storage data auditing scheme without bilinear pairing [J]. Journal of Xidian University, 2022, 49(1): 47-54.
[8]	ZUO Kaizhong,LIU Rui,ZHAO Jun,CHEN Zhangyi,CHEN Fulong. Method for the protection of spatiotemporal correlation location privacy with semantic information [J]. Journal of Xidian University, 2022, 49(1): 67-77.
[9]	MIAO Meixia,WU Panru,WANG Yunling. Research progress and applications of cryptographic accumulators [J]. Journal of Xidian University, 2022, 49(1): 78-91.
[10]	HUANG Hai,NA Ning,LIU Zhiwei,YU Bin,ZHAO Shilei. Low computation-complexity multi-scalar multiplication algorithm for the ECDSA [J]. Journal of Xidian University, 2022, 49(1): 92-101.
[11]	GE Bin,CHEN Xu,CHEN Gang. Fast hyper-chaotic image encryption algorithm using vector operation [J]. Journal of Xidian University, 2021, 48(6): 187-196.
[12]	DAI Mingjun,LI Xiaofeng,DENG Haiyan,CHEN Bin. Private information retrieval with low encoding/decoding complexity [J]. Journal of Xidian University, 2021, 48(6): 212-220.
[13]	XIE Lixia,BAI Yu. Information system business affecting impact evaluation method [J]. Journal of Xidian University, 2021, 48(4): 184-191.
[14]	WANG Xingxin,HU Wei,TAN Jing,ZHU Jiacheng,TANG Shibo. Correlation fault attack on AES [J]. Journal of Xidian University, 2021, 48(4): 192-199.
[15]	SONG Cheng,JIN Tong,NI Shuiping,HE Junyi,DU Shouheng. K-anonymous location privacy protection scheme for the mobile terminal [J]. Journal of Xidian University, 2021, 48(3): 138-145.