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

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

通信学报 ›› 2021, Vol. 42 ›› Issue (3): 11-22.doi: 10.11959/j.issn.1000-436x.2021023

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

李瑞琪¹^,², 贾春福¹^,², 王雅飞¹^,²

¹ 南开大学网络空间安全学院，天津 300350
² 天津市网络与数据安全技术重点实验室，天津 300350

修回日期:2020-12-16 出版日期:2021-03-25 发布日期:2021-03-01
作者简介:李瑞琪（1993- ），男，黑龙江尚志人，南开大学博士生，主要研究方向为同态加密、格密码学等。
贾春福（1967- ），男，河北文安人，博士，南开大学教授、博士生导师，主要研究方向为网络与信息安全、可信计算、恶意代码分析、密码技术应用等。
王雅飞（1995- ），女，天津人，南开大学硕士生，主要研究方向为同态加密应用、隐私保护等。
基金资助:
国家重点研发计划基金资助项目(2018YFA0704703);国家自然科学基金资助项目(61972215);国家自然科学基金资助项目(61702399);国家自然科学基金资助项目(61972073);天津市自然科学基金资助项目(20JCZDJC00640)

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

Ruiqi LI¹^,², Chunfu JIA¹^,², Yafei WANG¹^,²

¹ College of Cyber Science, Nankai University, Tianjin 300350, China
² Tianjin Key Laboratory of Network and Data Security Technology, Tianjin 300350, China

Revised:2020-12-16 Online:2021-03-25 Published:2021-03-01
Supported by:
The National Key Research and Development Program of China(2018YFA0704703);The National Natural Science Foundation of China(61972215);The National Natural Science Foundation of China(61702399);The National Natural Science Foundation of China(61972073);The Natural Science Foundation of Tianjin(20JCZDJC00640)

摘要/Abstract

摘要：

为了提高同态加密算法在多用户云计算场景下的实用性，构造了一个基于NTRU的多密钥同态代理重加密方案。首先利用密文扩张思想提出了一种新的NTRU型多密钥同态密文形式，并基于此设计了相应的同态运算和重线性化过程，从而形成一个支持分布式解密的NTRU型多密钥同态加密方案；然后借助于密钥交换思想设计了重加密密钥和重加密过程，将代理重加密功能集成到该NTRU型多密钥同态加密方案中。所提方案保留了多密钥同态加密和代理重加密的特性，而且在用户端的计算开销较低。将所提方案应用于联邦学习中的隐私保护问题并进行了实验，结果表明，所提方案基本不影响联邦训练的准确率，加解密、同态运算和重加密等过程的计算开销也可接受。

关键词: 同态加密, 代理重加密, 多密钥, 云计算, 联邦学习

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

中图分类号:

TP309.7

李瑞琪, 贾春福, 王雅飞. 基于NTRU的多密钥同态代理重加密方案及其应用[J]. 通信学报, 2021, 42(3): 11-22.

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.

图/表 8

表1

本文方案与LTV12方案的对比"

方案	公钥尺寸	计算密钥尺寸（用户）	密文尺寸	分布式解密	代理重加密
本文方案	$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)$	不支持	不支持

表1

表2

本文方案与YKHK18方案的对比"

方案	密码学假设	明文空间	公钥尺寸	计算密钥尺寸（用户端）	重加密密钥尺寸	密文扩张	同态密文/明文尺寸比例（用户端）	同态密文/明文尺寸比例（计算过程中）	重加密后密文/明文尺寸比例	批处理
本文方案	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))$	不支持

表2

图1

图2

图3

表3

表4

表5

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

数据集	准确率
明文参数模型测试集	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

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 36

相关文章 15

Metrics

推荐阅读 0

[1]	马玲, 樊漆亮, 许婷, 郭冠琛, 张圣林, 孙永谦, 张玉志. 基于强化学习的在线离线混部云环境下的调度框架[J]. 通信学报, 2023, 44(6): 90-102.
[2]	马鑫迪, 李清华, 姜奇, 马卓, 高胜, 田有亮, 马建峰. 面向Non-IID数据的拜占庭鲁棒联邦学习[J]. 通信学报, 2023, 44(6): 138-153.
[3]	金彪, 李逸康, 姚志强, 陈瑜霖, 熊金波. GenFedRL：面向深度强化学习智能体的通用联邦强化学习框架[J]. 通信学报, 2023, 44(6): 183-197.
[4]	田有亮, 吴柿红, 李沓, 王林冬, 周骅. 基于激励机制的联邦学习优化算法[J]. 通信学报, 2023, 44(5): 169-180.
[5]	张佳乐, 朱诚诚, 孙小兵, 陈兵. 基于GAN的联邦学习成员推理攻击与防御方法[J]. 通信学报, 2023, 44(5): 193-205.
[6]	李开菊, 许强, 王豪. 冗余数据去除的联邦学习高效通信方法[J]. 通信学报, 2023, 44(5): 79-93.
[7]	余晟兴, 陈泽凯, 陈钟, 刘西蒙. DAGUARD：联邦学习下的分布式后门攻击防御方案[J]. 通信学报, 2023, 44(5): 110-122.
[8]	姜慧, 何天流, 刘敏, 孙胜, 王煜炜. 面向异构流式数据的高性能联邦持续学习算法[J]. 通信学报, 2023, 44(5): 123-136.
[9]	余晟兴, 陈钟. 基于同态加密的高效安全联邦学习聚合框架[J]. 通信学报, 2023, 44(1): 14-28.
[10]	汤凌韬, 王迪, 刘盛云. 面向非独立同分布数据的联邦学习数据增强方案[J]. 通信学报, 2023, 44(1): 164-176.
[11]	杨亚涛, 刘德莉, 刘培鹤, 曾萍, 肖嵩. BFV-Blockchainvoting：支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9): 100-111.
[12]	范绍帅, 吴剑波, 田辉. 面向能量受限工业物联网设备的联邦学习资源管理[J]. 通信学报, 2022, 43(8): 65-77.
[13]	张学旺, 黎志鸿, 林金朝. 基于公平盲签名和分级加密的联盟链隐私保护方案[J]. 通信学报, 2022, 43(8): 131-141.
[14]	莫梓嘉, 高志鹏, 杨杨, 林怡静, 孙山, 赵晨. 面向车联网数据隐私保护的高效分布式模型共享策略[J]. 通信学报, 2022, 43(4): 83-94.
[15]	于海宁, 张宏莉, 余翔湛, 曲家兴, 葛蒙蒙. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022, 43(11): 1-13.