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

doi:10.19665/j.issn1001-2400.2021.01.010

西安电子科技大学学报 ›› 2021, Vol. 48 ›› Issue (1): 87-95.doi: 10.19665/j.issn1001-2400.2021.01.010

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

车小亮^1,²(),周昊楠²(),杨晓元^1,²(),周潭平^1,²(),刘龙飞¹(),李宁波²()

1.武警工程大学密码工程学院,陕西西安 710086
2.网络和信息安全武警部队重点实验室,陕西西安710086

收稿日期:2020-08-14 出版日期:2021-02-20 发布日期:2021-02-03
通讯作者: 杨晓元,周潭平
作者简介:车小亮(1987—),男,博士,E-mail: smo_mrche@yeah.net|周昊楠(1992—),男,硕士,E-mail: 1957028@qq.com|刘龙飞(1990—),男,讲师,硕士,E-mail: ya_zhou_521@163.com|李宁波(1992—),男,讲师,博士,E-mail: 372726936@qq.com
基金资助:
国家重点研发计划(2017YFB0802000);国家自然科学基金(U1636114);国家密码发展基金(MMJJ20170112);陕西省自然科学基金(2020JQ-492)

Efficient multi-key fully homomorphic encryption scheme from RLWE

CHE Xiaoliang^1,²(),ZHOU Haonan²(),YANG Xiaoyuan^1,²(),ZHOU Tanping^1,²(),LIU Longfei¹(),LI Ningbo²()

1. College of Cryptographic Engineering,Engineering University of PAP,Xi’an 710086,China
2. Key Laboratory of Network and Information Security of the PAP,Xi’an 710086,China

Received:2020-08-14 Online:2021-02-20 Published:2021-02-03
Contact: Xiaoyuan YANG,Tanping ZHOU

摘要/Abstract

摘要：

基于RLWE问题的BGV型多密钥全同态加密方案具有较大的密文量和密钥量,且生成计算密钥的过程复杂,致使同态运算效率较低。针对该问题,提出了一种密钥量小、计算密钥生成效率高的BGV型多密钥全同态加密方案。首先,通过改进密文的扩展形式,优化了计算密钥的生成算法,提高了计算密钥的生成效率;其次,利用低位比特丢弃技术,减小了计算密钥生成算法中的计算冗余,降低了计算开销;最后,根据优化的算法,结合模交换技术和密钥交换技术,构造了一种高效的层级BGV型多密钥全同态加密方案。相比于现有的层级BGV型多密钥全同态加密方案,新方案在满足IND-CPA安全的条件下,简化了计算密钥生成过程,降低了存储和计算开销,且同态运算过程中产生的噪声值较小,运算效率较高。

关键词: 多密钥全同态加密, 密文扩展算法, 计算密钥, 密钥交换, 混合同态乘法

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

中图分类号:

TP309

车小亮,周昊楠,杨晓元,周潭平,刘龙飞,李宁波. 环LWE上高效的多密钥全同态加密方案[J]. 西安电子科技大学学报, 2021, 48(1): 87-95.

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.

图/表 2

表1

文中构造的计算密钥生成算法与LZY+19和CDKS19的算法存储开销对比"

算法类型	公钥尺寸	计算密钥的密文尺寸	扩展密文尺寸
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)²

表1

表2

文中方案与LZY+19方案的参数对比"

方案类型	扩展密文尺寸	公钥尺寸	生成计算密钥的密文尺寸	完成一次同态乘法解密产生的噪声值
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²)

表2

参考文献 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.

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

Efficient multi-key fully homomorphic encryption scheme from RLWE

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 20

相关文章 4

Metrics

本文评价

推荐阅读 10

[1]	张紫楠;郭渊博;杨奎武;黄惠新;杨占海. 通用可组合认证密钥交换协议[J]. J4, 2014, 41(5): 185-191.
[2]	彭清泉;裴庆祺;杨超;马建峰. 通用可组合安全的Internet密钥交换协议[J]. J4, 2009, 36(4): 714-720.
[3]	丁勇. 一种用椭圆曲线密码构建的传感网络密钥管理方案[J]. J4, 2008, 35(4): 739-742.
[4]	白国强;蔡勉;肖国镇. 一种关于GH-PKD的密码分析方法[J]. J4, 2000, 27(6): 740-745.