基于NTRU的多密钥同态加密方案解密结构

doi:10.11772/j.issn.1001-9081.2020010051

计算机应用 ›› 2020, Vol. 40 ›› Issue (7): 1959-1964.DOI: 10.11772/j.issn.1001-9081.2020010051

基于NTRU的多密钥同态加密方案解密结构

车小亮^1,2, 周昊楠¹, 周潭平^1,2, 李宁波², 杨晓元^1,2

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

收稿日期:2020-01-17 修回日期:2020-03-12 发布日期:2020-07-24 出版日期:2020-07-10
通讯作者: 车小亮
作者简介:车小亮(1987-),男,安徽亳州人,博士研究生,主要研究方向:同态密码、信息安全;周昊楠(1992-),男,黑龙江牡丹江人,硕士研究生,主要研究方向:同态密码、信息安全;周潭平(1989-),男,江西鹰潭人,讲师,博士,主要研究方向:同态密码、信息安全;李宁波(1992-),男,河南三门峡人,博士研究生,主要研究方向:同态密码、信息安全;杨晓元(1959-),男,湖南湘潭人,教授,博士生导师,硕士,主要研究方向:密码学、信息安全。
基金资助:
国家重点研发计划项目（2017YFB0802000）；国家自然科学基金资助项目（U1636114）；国家密码发展基金资助项目（MMJJ20170112）。

Decryption structure of multi-key homomorphic encryption scheme based on NTRU

CHE Xiaoliang^1,2, ZHOU Haonan¹, ZHOU Tanping^1,2, LI Ningbo², YANG Xiaoyuan^1,2

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

Received:2020-01-17 Revised:2020-03-12 Online:2020-07-24 Published:2020-07-10
Supported by:
This work is partially supported by the National Key Research and Development Program of China (2017YFB0802000), the National Natural Science Foundation of China (U1636114), the National Cryptography Development Fund of China (MMJJ20170112).

摘要/Abstract

摘要： 为了进一步提升NTRU型多密钥全同态加密（MKFHE）方案的安全性和效率，基于素数幂次分圆多项式环，研究了NTRU型多密钥同态加密的原始解密结构特点，并提出了两种多密钥同态解密结构改进优化方法。首先通过降低多项式系数，设计了“Regev-Style”多密钥解密结构；其次通过扩展密文维度，设计了“Ciphertext-Expansion”多密钥解密结构。通过与NTRU型多密钥同态加密方案的原始解密结构进行对比分析，结果表明“Regev-Style”多密钥解密结构降低了产生噪声的量级，用于NTRU型多密钥全同态加密方案设计时能减少密钥交换次数和模交换次数；“Ciphertext-Expansion”多密钥解密结构消除了密钥交换过程，降低了产生噪声的量级，且能更有效地处理重复用户的密文乘积。改进优化的多密钥解密结构的安全性均基于素数幂次分圆多项式环上的误差学习（LWE）问题和判定小多项式比（DSPR）假设，这些结构能较好地抵御子域攻击。通过选取合适的参数，它们可用于设计更加安全高效的NTRU型多密钥全同态加密方案。

关键词: NTRU型多密钥同态加密, 素数幂次分圆多项式环, 同态乘法解密结构, 小系数多项式, 密文扩展

Abstract: In order to further improve the security and efficiency of Number Theory Research Unit (NTRU)-type Multi-Key Fully Homomorphic Encryption (MKFHE) schemes, based on the prime power cyclotomic rings, the properties of the original decryption structure of NTRU-type multi-key fully homomorphic encryption were studied, and two optimization methods of multi-key homomorphic decryption structures were proposed. Firstly, by reducing the polynomial's coefficients, the "Regev-Style" multi-key decryption structure was designed. Secondly, the "Ciphertext-Expansion" multi-key decryption structure was designed by expanding the dimension of ciphertexts. Compared with the original decryption structure of NTRU-type multi-key homomorphic encryption scheme, the "Regev-Style" multi-key decryption structure reduced the magnitude of error, which was able to reduce the number of key-switching and modulo-switching when it was used in the design of NTRU-type multi-key homomorphic encryption scheme; the "Ciphertext-Expansion" multi-key decryption structure eliminated the key-switching operation, reduced the magnitude of error, and was able to process the ciphertext product of repeated users more effectively. The security of the optimized multi-key decryption structures was based on the Learning With Errors (LWE) problem and Decisional Small Polynomial Ratio (DSPR) assumption on the prime power cyclotomic rings, so these structures were able to resist subfield attacks well. Therefore, they can be used to design a more secure and efficient NTRU-type multi-key fully homomorphic encryption scheme by selecting appropriate parameters.

Key words: NTRU (Number Theory Research Unit)-type Multi-key Homomorphic Encryption (MKFHE), prime power cyclotomic ring, homomorphic multiplication decryption structure, small coefficient polynomial, ciphertext expansion

中图分类号:

TP309

车小亮, 周昊楠, 周潭平, 李宁波, 杨晓元. 基于NTRU的多密钥同态加密方案解密结构[J]. 计算机应用, 2020, 40(7): 1959-1964.

CHE Xiaoliang, ZHOU Haonan, ZHOU Tanping, LI Ningbo, YANG Xiaoyuan. Decryption structure of multi-key homomorphic encryption scheme based on NTRU[J]. Journal of Computer Applications, 2020, 40(7): 1959-1964.

参考文献

[1] GOLDREICH O,MICALI S,WIGDERSON A. How to play any mental game or a completeness theorem for protocols with honest majority[C]//Proceedings of the 19th Annual ACM Symposium on Theory of Computing. New York:ACM,1987:218-229.
[2] BEN-OR M,GOLDWASSER S,WIGDERSON A. Completeness theorems for non-cryptographic fault-tolerant distributed computation[C]//Proceedings of the 20th Annual ACM Symposium on Theory of Computing. New York:ACM,1988:1-10.
[3] LÓPEZ-ALT A,TROMER E,VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multi-key fully homomorphic encryption[C]//Proceedings of the 44th Annual ACM Symposium on Theory of Computing. New York:ACM,2012:1219-1234.
[4] LYUBASHEVSKY V,PEIKERT C,REGEV O. On ideal lattices and learning with errors over rings[C]//Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques,LNCS 6110. Berlin:Springer,2010:1-23.
[5] STEHLÉ D,STEINFELD R. Making NTRU as secure as worst-case problems over ideal lattices[C]//Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques,LNCS 6632. Berlin:Springer,2011:27-47.
[6] ALBRECHT M,BAI S,DUCAS L. A subfield lattice attack on overstretched NTRU assumptions[C]//Proceedings of the 36th Annual Cryptology Conference,LNCS 9814. Berlin:Springer,2016:153-178.
[7] CHEON J H,JEONG J,LEE C. An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero[J]. LMS Journal of Computation and Mathematics,2016, 19(A):255-266.
[8] YU Y,XU G,WANG X. Provably secure NTRU instances over prime cyclotomic rings[C]//Proceedings of the 20th IACR International Workshop on Public Key Cryptography,LNCS 10174. Berlin:Springer,2017:409-434.
[9] YU Y,XU G,WANG X. Provably secure NTRUEncrypt over more general cyclotomic rings[EB/OL]. (2017-04-05)[2019-04-05]. https://eprint.iacr.org/2017/304.pdf.
[10] BRAKERSKI Z,GENTRY C,VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York:ACM,2012:309-325.
[11] 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.
[12] BOS J W,LAUTER K,LOFTUS J,et al. Improved security for a ring-based fully homomorphic encryption scheme[C]//Proceedings of the 14th IMA International Conference on Cryptography and Coding,LNCS 8308. Cham:Springer,2013:45-64.
[13] 陈智罡. 基于格的全同态加密研究与设计[D]. 南京:南京航空航天大学,2015:47-59.(CHEN Z G. Research and design of fully homomorphic encryption based on lattice[D]. Nanjing:Nanjing University of Aeronautics and Astronautics,2015:47-59.)
[14] 李子臣, 张卷美, 杨亚涛, 等. 基于NTRU的全同态加密方案[J]. 电子学报,2018,46(4):938-944.(LI Z C,ZHANG J M, YANG Y T,et al. A fully homomorphic encryption scheme based on NTRU[J]. Acta Electronica Sinica,2018,46(4):938-944.)
[15] MICCIANCIO D,REGEV O. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing,2004,37(1):267-302.
[16] GENTRY C,SAHAI A,WATERS B. Homomorphic encryption from learning with errors:conceptually-simpler,asymptoticallyfaster,attribute-based[C]//Proceedings of the 33rd Annual Cryptology Conference,LNCS 8042. Berlin:Springer,2013:75-92.
[17] BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]//Proceedings of the 32nd Annual Cryptology Conference, LNCS 7417. Berlin:Springer, 2012:868-886.
[18] FAN J,VERCAUTEREN F. Somewhat practical fully homomorphic encryption[EB/OL]. (2012-04-05)[2019-04-05]. http://eprint.iacr.org/2012/144.pdf.

基于NTRU的多密钥同态加密方案解密结构

Decryption structure of multi-key homomorphic encryption scheme based on NTRU

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	高瑞, 陈学斌, 张祖篡. 面向部分图更新的动态社交网络隐私发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3831-3838.
[2]	项勇, 李艳俊, 黄丁韫, 陈愚, 谢惠琴. 全轮Shadow算法的差分和线性特征分析[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3839-3843.
[3]	赵振皓, 张仕斌, 万武南, 张金全, 秦智. 基于信誉值和强盲签名算法的委托权益证明共识算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3717-3722.
[4]	王伊婷, 万武南, 张仕斌, 张金全, 秦智. 基于SM9算法的可链接环签名方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3709-3716.
[5]	梁静, 万武南, 张仕斌, 张金全, 秦智. 面向主从链的慈善系统溯源存储模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3751-3758.
[6]	刘德渊, 张金全, 张鑫, 万武南, 张仕斌, 秦智. 基于无证书签密的跨链身份认证方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3731-3740.
[7]	张鑫, 张金全, 刘德渊, 万武南, 张仕斌, 秦智. 基于身份代理重加密的跨链身份管理方案[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3723-3730.
[8]	邓伊琳余发江. 基于LSTM和可分离自注意力机制的伪随机数生成器[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	张润莲王蒿唐瑞锋武小年. 基于均匀流型逼近与投影的高级加密标准算法相关功耗分析方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	刘运东汪学明. 基于穿刺伪随机函数的动态可搜索加密方案[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	张宏扬张淑芬谷铮. 面向个性化与公平性的联邦学习算法fedPF[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	姚梓豪马自强李扬魏良根. 基于冲突的缓存侧信道攻击与驱逐集研究综述[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	晏燕李飞飞吕雅琴冯涛. 安全高效的混洗差分隐私频率估计方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[14]	彭海洋计卫星刘法旺. 基于区块链的自动驾驶仿真测试数据存证模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	闫润雨郭瑞闫永勃刘光军. 云中指定测试者的细粒度结果可验证搜索加密方案[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.