基于NTRU的多密钥同态代理重加密方案及其应用

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

Abstract

Abstract:

To improve the practicability of homomorphic encryption in the application of multi-user cloud computing, a NTRU-based multi-key homomorphic proxy re-encryption (MKH-PRE) scheme was constructed.Firstly, a new form of NTRU-based multi-key ciphertext was proposed based on the idea of ciphertext extension, and the corresponding homomorphic operations and relinearization procedure were designed on the basis of this new ciphertext form, so that a NTRU-based multi-key homomorphic encryption (MKHE) scheme which supported distributed decryption was constructed.Then, resorting to the idea of key switching, the re-encryption key and re-encryption procedure were put forward such that the functionality of proxy re-encryption (PRE) was integrated to this new NTRU-based MKHE scheme.The MKH-PRE scheme preserved the properties of MKHE and PRE, and had a better performance on the client side.The scheme was applied to the privacy-preserving problems in federated learning and an experiment of the application was carried out.The results demonstrate that the accuracy of learning is scarcely affected by the encryption procedure and the computational overhead of this MKH-PRE scheme is acceptable.

Key words: homomorphic encryption, proxy re-encryption, multi-key, cloud computing, federated learning

CLC Number:

TP309.7

Ruiqi LI, Chunfu JIA, Yafei WANG. Multi-key homomorphic proxy re-encryption scheme based on NTRU and its application[J]. Journal on Communications, 2021, 42(3): 11-22.

Figures/Tables 8

方案	公钥尺寸	计算密钥尺寸（用户）	密文尺寸	分布式解密	代理重加密
本文方案	$O (d n \log q)$	$O (d n \log q)$	$O (k n \log q)$	支持	支持
LTV12方案	$O (n \log q)$	$O (n \log^{3} q)$	$O (n \log q)$	不支持	不支持

方案	密码学假设	明文空间	公钥尺寸	计算密钥尺寸（用户端）	重加密密钥尺寸	密文扩张	同态密文/明文尺寸比例（用户端）	同态密文/明文尺寸比例（计算过程中）	重加密后密文/明文尺寸比例	批处理
本文方案	RLWE、DPSR	多项式环	$\tilde{O} (λ^{2} L^{4})$	$\tilde{O} (λ^{2} L^{4})$	$\tilde{O} (λ^{2} L^{4})$	$\tilde{O} (1)$	$\tilde{O} (λ L^{2})$	$\tilde{O} (λ k L^{2})$	$\tilde{O} (λ L^{2})$	支持
YKHK18方案	LWE	{0,1}	$\tilde{O} (λ (N + L)^{2})$	—	$\tilde{O} (λ^{2} (N + L)^{2})$	$t \tilde{O} (k^{2} λ^{4} (N + L)^{4})$	$\tilde{O} (λ^{3} (N + L)^{4})$	$\tilde{O} (k^{2} λ^{3} (N + L)^{4})$	$\tilde{O} (λ (N + L))$	不支持

References 36

[1]	RIVEST R , ADLEMAN L , DERTOUZOS M . On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978,4(11): 169-177.
[2]	GENTRY C . A fully homomorphic encryption scheme[D]. Palo Alto:Stanford University, 2009.
[3]	GENTRY C , . Fully homomorphic encryption using ideal lattices[C]// Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC). New York:ACM Press, 2009: 169-178.
[4]	BRAKERSKI Z , VAIKUUNTANATHAN V . Efficient fully homomorphic encryption from (standard) LWE[C]// Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 2011: 97-106.
[5]	BRAKERSKI Z , GENTRY C , VAIKNTANATHAN V . (Leveled) Fully homomorphic encryption without bootstrapping[C]// Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York:ACM Press, 2012: 309-325.
[6]	DIJK V M , GENTRY C , HALEVI S ,et al. Fully homomorphic encryption over the integers[C]// 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2010: 24-43.
[7]	GENTRY C , SAHAI A , WATERS B . Homomorphic encryption from learning with errors:conceptually-simpler,asymptotically-faster,attribute-based[C]// 33rd Annual Cryptology Conference. Berlin:Springer, 2013: 75-92.
[8]	LóPEZ-ALT A , TROMER E , VAIKUNTANATHAN V . On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C]// Proceedings of the 44th Annual ACM Symposium on Theory of Computing. New York:ACM Press, 2012: 1219-1234.
[9]	CHILLOTTI I , GAMA N , GEORGIEVA M ,et al. Faster fully homomorphic encryption:bootstrapping in less than 0.1 seconds[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2016: 3-33.
[10]	CHEON J H , KIM A , KIM M ,et al. Homomorphic encryption for arithmetic of approximate numbers[C]// 23rd International Conference on the Theory and Applications of Cryptology and Information Security. Berlin:Springer, 2017: 409-437.
[11]	CLEAR M , MCGOLDRICK C . Multi-identity and multi-key leveled FHE from learning with errors[C]// 35th Annual International Cryptology Conference. Berlin:Springer, 2016: 630-656.
[12]	MUKHERJEE P , WICHS D . Two round multiparty computation via multi-key FHE[C]// 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2016: 735-763.
[13]	PEIKERT C , SHIEHIAN S . Multi-key FHE from LWE,revisited[C]// 14th Theory of Cryptography Conference. Berlin:Springer, 2016: 217-238.
[14]	BRAKERSKI Z , PERLMAN R . Lattice-based fully dynamic multi-key FHE with short ciphertexts[C]// 36th Annual International Cryptology Conference. Berlin:Springer, 2016: 190-213.
[15]	CHEN L , ZHANG Z F , WANG X Q . Batched multi-hop multi-key FHE from ring-LWE with compact ciphertext extension[C]// 15th Theory of Cryptography Conference. Berlin:Springer, 2017: 597-627.
[16]	LI N , ZHOU T , YANG X ,et al. Efficient multi-key FHE with short extended ciphertexts and directed decryption protocol[J]. IEEE Access, 2019,7: 56724-56732.
[17]	CHEN H , CHILLOTTI I , SONG Y . Multi-key homomorphic encryption from TFHE[C]// 25th International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2019: 446-472.
[18]	CHEN H , DAI W , KIM M ,et al. Efficient multi-key homomorphic encryption with packed ciphertexts with application to oblivious neural network inference[C]// 2019 Conference on Computer and Communications Security. New York:ACM Press, 2019: 395-412.
[19]	YASUDA S , KOSEKI Y , HIROMASA R ,et al. Multi-key homomorphic proxy re-encryption[C]// 2018 International Conference on Information Security. Berlin:Springer, 2018: 328-346.
[20]	HOFFSTEIN J , PIPHER J , SILVERMAN J H . NTRU:a ring-based public key cryptosystem[C]// 1998 International Algorithmic Number Theory Symposium. Berlin:Springer, 1998: 267-288.
[21]	STEHLé D , STEINFELD R . Making NTRU as secure as worst-case problems over ideal lattices[C]// 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2011: 27-47.
[22]	YU Y , XU G W , WANG X Y . Provably secure NTRU instances over prime cyclotomic rings[C]// 20th IACR International Conference on Practice and Theory in Public-Key Cryptography. Berlin:Springer, 2017: 409-434.
[23]	WANG Y , WANG M Q . Provably secure NTRUEncrypt over any cyclotomic field[C]// 25th Selected Areas in Cryptography. Berlin:Springer, 2018: 391-417.
[24]	李瑞琪, 贾春福 . 一个基于NTRU的多密钥同态加密方案[J]. 密码学报, 2020,7(5): 683-697.
	LI R Q , JIA C F . A multi-key homomorphic encryption scheme based on NTRU[J]. Journal of Cryptologic Research, 2020,7(5): 683-697.
[25]	车小亮, 周潭平, 李宁波 ,等. NTRU 型多密钥全同态加密方案的优化[J]. 工程科学与技术, 2020,52(5): 186-193.
	CHE X L , ZHOU T P , LI N B ,et al. Optimization of NTRU-type multi-key fully homomorphic encryption scheme[J]. Advanced Engineering Sciences, 2020,52(5): 186-193.
[26]	NUNEZ D , AGUDO I , LOPEZ J . NTRUReEncrypt:an efficient proxy re-encryption scheme based on NTRU[C]// Proceedings of the 10th ACM Symposium on Information,Computer and Communications Security. New York:ACM Press, 2015: 179-189.
[27]	张明武, 杜林 . 基于NTRU的单向抗合谋代理重加密方案[J]. 密码学报, 2020,7(2): 187-196.
	ZHANG M W , DU L . A collusion-resistant and uni-directional proxy re-encryption scheme based on NTRU[J]. Journal of Cryptologic Research, 2020,7(2): 187-196.
[28]	LYUBASHEVSKY V , PEIKERT C , REGEV O . On ideal lattices and learning with errors over rings[C]// 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2010: 1-23.
[29]	MICCIANCIO D , PEIKERT C . Trapdoors for lattices:simpler,tighter,faster,smaller[C]// 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2012: 700-718.
[30]	BOS J W , LAUTER K , LOFTUS J ,et al. Improved security for a ring-based fully homomorphic encryption scheme[C]// 2013 IMA International Conference on Cryptography and Coding. Berlin:Springer, 2013: 45-64.
[31]	BRAKERSKI Z , . Fully homomorphic encryption without modulus switching from classical GapSVP[C]// 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2012: 868-886.
[32]	MUKHERJEE P , WICHS D . Two round multiparty computation via multi-key FHE[C]// 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2016: 735-763.
[33]	ASHAROV G , JAIN A,LóPEZ-ALT A ,et al. Multiparty computation with low communication,computation and interaction via threshold FHE[C]// 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin,Springer, 2012: 483-501.
[34]	LóPEZ-ALT A , TROMER E , VAIKUNTANATHAN V . Multikey fully homomorphic encryption and applications[J]. SIAM Journal on Computing, 2017,46(6): 1827-1892.
[35]	ALBRECHT M , BAI S , DUCAS L . A subfield lattice attack on overstretched NTRU assumptions[C]// 36th Annual International Cryptology Conference. Berlin:Springer, 2016: 153-178.
[36]	KIRCHNER P , FOUQUE P A . Revisiting lattice attacks on overstretched NTRU parameters[C]// 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2017: 3-26.

Metrics

Recommended 0

No Suggested Reading articles found!

数据集	准确率
明文参数模型测试集	71.08%
密文参数模型测试集	71.19%

算法	运行时间/ms
Setup	1 450
KeyGen	0.549
Enc	8.972
Eval	0.158
PartDec	10.920
PartDec+FinDec	33.747

算法	运行时间/ms
RKGen	3.015
ReEnc	276.613
PRDec	280.800

Multi-key homomorphic proxy re-encryption scheme based on NTRU and its application

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 36

Related Articles 15

Metrics

Recommended 0

[1]	Ling MA, Qiliang FAN, Ting XU, Guanchen GUO, Shenglin ZHANG, Yongqian SUN, Yuzhi ZHANG. Scheduling framework based on reinforcement learning in online-offline colocated cloud environment [J]. Journal on Communications, 2023, 44(6): 90-102.
[2]	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.
[3]	Kaiju LI, Qiang XU, Hao WANG. Communication-efficient federated learning method via redundant data elimination [J]. Journal on Communications, 2023, 44(5): 79-93.
[4]	Shengxing YU, Zekai CHEN, Zhong CHEN, Ximeng LIU. DAGUARD: distributed backdoor attack defense scheme under federated learning [J]. Journal on Communications, 2023, 44(5): 110-122.
[5]	Hui JIANG, Tianliu HE, Min LIU, Sheng SUN, Yuwei WANG. High-performance federated continual learning algorithm for heterogeneous streaming data [J]. Journal on Communications, 2023, 44(5): 123-136.
[6]	Youliang TIAN, Shihong WU, Ta LI, Lindong WANG, Hua ZHOU. Federated learning optimization algorithm based on incentive mechanism [J]. Journal on Communications, 2023, 44(5): 169-180.
[7]	Jiale ZHANG, Chengcheng ZHU, Xiaobing SUN, Bing CHEN. Membership inference attack and defense method in federated learning based on GAN [J]. Journal on Communications, 2023, 44(5): 193-205.
[8]	Shengxing YU, Zhong CHEN. Efficient secure federated learning aggregation framework based on homomorphic encryption [J]. Journal on Communications, 2023, 44(1): 14-28.
[9]	Lingtao TANG, Di WANG, Shengyun LIU. Data augmentation scheme for federated learning with non-IID data [J]. Journal on Communications, 2023, 44(1): 164-176.
[10]	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.
[11]	Shaoshuai FAN, Jianbo WU, Hui TIAN. Federated learning resource management for energy-constrained industrial IoT devices [J]. Journal on Communications, 2022, 43(8): 65-77.
[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]	Xiaodong YANG, Tian TIAN, Jiaqi WANG, Meijuan LI, Caifen WANG. Certificateless ciphertext retrieval scheme with multi-user and multi-keyword based on cloud-edge collaboration [J]. Journal on Communications, 2022, 43(5): 144-154.
[14]	Zijia MO, Zhipeng GAO, Yang YANG, Yijing LIN, Shan SUN, Chen ZHAO. Efficient distributed model sharing strategy for data privacy protection in Internet of vehicles [J]. Journal on Communications, 2022, 43(4): 83-94.
[15]	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.