基于MLWE的低膨胀率加密算法

doi:10.11896/j.issn.1002-137X.2019.04.023

计算机科学 ›› 2019, Vol. 46 ›› Issue (4): 144-150.doi: 10.11896/j.issn.1002-137X.2019.04.023

基于MLWE的低膨胀率加密算法

柯程松^1,2, 吴文渊², 冯勇²

重庆邮电大学计算机科学与技术学院重庆400065¹
中国科学院重庆绿色智能技术研究院自动推理与认知重庆市重点实验室重庆400714²

收稿日期:2018-03-09 出版日期:2019-04-15 发布日期:2019-04-23
通讯作者: 吴文渊(1976-),男,博士,研究员,主要研究方向为自动推理、混合计算、格密码,E-mail:wuwenyuan@cigit.ac.cn(通信作者)
作者简介:柯程松(1994-),男,硕士生,主要研究方向为信息安全、同态加密;冯勇(1965-),男,博士,研究员,主要研究方向为自动推理、符号计算、格理论。
基金资助:
本文受重庆市科委项目(cstc2017zdcy-yszxX0011),国家自然科学基金资助项目(11471307,11671377),中科院前沿重点项目(QYZDB-SSW-SYS026)资助。

Low Expansion Rate Encryption Algorithm Based on MLWE

KE Cheng-song^1,2, WU Wen-yuan², FENG Yong²

College of Computer Science & Technology,Chongqing University of Posts & Telecommunications,Chongqing 400065,China¹
Chongqing Key Laboratory of Automated Reasoning & Cognition,Chongqing Institute of Green & Intelligent Technology,Chinese Academy of Sciences,Chongqing 400714,China²

Received:2018-03-09 Online:2019-04-15 Published:2019-04-23

摘要/Abstract

摘要： 基于模容错学习问题(MLWE)的格密码算法Kyber具有抗量子攻击、加密效率高的优势,但密文膨胀率较大约为1∶25,仅适用于密钥封装等少数场景。为了构建一种能够应用于一般的公钥加密场景的加密算法,提出了一种改进的基于MLWE的低膨胀率公钥加密算法。文中在Kyber加密算法中引入新的加密参数dp,扩大了明文空间,通过严格的理论推导与实验分析了dp对加密算法正确性的影响,并优化了加密参数,降低了密文膨胀率。改进后的算法会扩大有限域(即计算空间),导致直接使用原算法中的有限域上的多项式乘法运算,需调用额外的大整数计算库,从而降低了加密效率。通过使用基于浮点运算的复数域上的快速傅里叶变换进行多项式乘法,避免了在增大后的有限域上进行大整数多项式乘法。最后,对浮点运算产生的误差进行了分析,同时使用C++实现了改进算法,并将其与Kyber的实验数据进行对比。实验表明,所提算法在保证了计算效率的同时使密文膨胀率由1∶25左右降低到了1∶4.25左右。

关键词: 浮点运算, 复数域, 公钥加密, 密文膨胀率, 模容错学习问题

Abstract: The lattice encryption algorithm Kyber based on MLWE has the advantage of anti-quantum attack and high encryption efficiency.However,the expansion rate of ciphertext is as high as about 1∶25,which is just suitable for a few scenes such as key encapsulation.In order to give an encryption algorithm that can be applied to common public key encryption scenes,an improved MLWE based low expansion rate public key encryption algorithm was proposedin this paper.A new encryption parameter dp was introduced into this algorithm to expand the plaintext space.By strict theoretical deduction and experiment,the influence of dp on the correctness of the encryption algorithm was analyzed,and the encryption parameter was optimized to reduce the expansion rate of ciphertext.The improved algorithm will work in a large finite field,which leads to low encryption efficiency.To avoid this situation,this paper proposed a polynomial mul-tiplication method based on FFT in complex field by using floating point arithmetic.And the improved algorithm was implemented in C++.Experimental results show that the new method is more efficient and the floating error is controllable.Compared with Kyber,the ciphertext expansion rate is reduced from 1∶25 to about 1∶4.25.

Key words: Ciphertext expansion rate, Complex field, Floating point arithmetic, Module learning with errors(MLWE), Public key encryption

中图分类号:

TP309

柯程松, 吴文渊, 冯勇. 基于MLWE的低膨胀率加密算法[J]. 计算机科学, 2019, 46(4): 144-150. https://doi.org/10.11896/j.issn.1002-137X.2019.04.023

KE Cheng-song, WU Wen-yuan, FENG Yong. Low Expansion Rate Encryption Algorithm Based on MLWE[J]. Computer Science, 2019, 46(4): 144-150. https://doi.org/10.11896/j.issn.1002-137X.2019.04.023

参考文献

[1]SHOR P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Review,1999,41(2):303-332.
[2]GROVER L K.A fast quantum mechanical algorithm for database search[C]∥Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing.ACM,1996:212-219.
[3]NSA Suite B cryptography:Cryptography today[OL].https://www.nsa.gov/ia/programs/suiteb_cryptography/.2015.
[4]CHEN L,CHEN L,JORDAN S,et al.Report on post-quantum cryptography[M].US Department of Commerce,National Institute of Standards and Technology,2016.
[5]AJTAI M.Generating hard instances of lattice problems[C]∥Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing.ACM,1996:99-108.
[6]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.How to Use a Short Basis:Trapdoors for Hard Lattices and New Cryptographic Constructions[OL].http://www.cs.toronto.edu/～vinodv/GentryPeikertVSTOC2008.pdf.2008.
[7]AJTAI M,DWORK C.A public-key cryptosystem with worst-case/average-case equivalence[C]∥Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing.ACM,1997:284-293.
[8]REGEV O.On lattices,learning with errors,random linear codes,and cryptography[J].Journal of the ACM,2009,56(6):34.
[9]LYUBASHEVSKY V,PEIKERT C,REGEV O.On ideal lattices and learning with errors over rings[C]∥Annual International Conference on the Theory and Applications of Cryptographic Techniques.Springer,Berlin,Heidelberg,2010:1-23.
[10]WANG X Y,LIU M J.Survey of lattice-based cryptography[J].Journal of Cryptologic Research,2014,1(1):13-27.(in Chinese) 王小云,刘明洁.格密码学研究[J].密码学报,2014,1(1):13-27.
[11]LI Z P,MA C G,ZHOU H S.Overview on Fully Homomorphic Encryption[J].Journal of Cryptologic Research,2017,4(6):561-578.(in Chinese) 李增鹏,马春光,周红生.全同态加密研究[J].密码学报,2017,4(6):561-578.
[12]LANGLOIS A,STEHLÉ D.Worst-case to average-case reductions for module lattices[J].Designs,Codes and Cryptography,2015,75(3):565-599.
[13]BOS J,DUCAS L,KILTZ E,et al.CRYSTALS-Kyber:a CCA-secure module-lattice-based KEM[C]∥2018 IEEE European Symposium on Security and Privacy.2018.
[14]LIU YM,LI XX,LIU H L.Post-quantum key exchange from lattice[J].Journal of Cryptologic Research,2017,4(5):485-497.(in Chinese) 刘亚敏,李祥学,刘晗林.基于格的后量子密钥交换研究[J].密码学报,2017,4(5):485-497.
[15]BAI S,LANGLOIS A,LEPOINT T,et al.Improved security proofs in lattice-based cryptography:using the Rényi divergence rather than the statistical distance[C]∥International Confe-rence on the Theory and Application of Cryptology and Information Security.Springer,Berlin,Heidelberg,2015:3-24.
[16]GOLUB G H,VAN LOAN C F.Matrix computations[M].JHU Press,2012:219-222.
[17]HIGHAM N J.Accuracy and stability of numerical algorithms[M].Society for Industrial and Applied Mathematics,2002:451-458.
[18]BOS J,COSTELLO C,DUCAS L,et al.Frodo:Take off the ring! practical,quantum-secure key exchange from LWE[C]∥Proceedings of the 2016 ACM SIGSAC Conference on Compu-ter and Communications Security.ACM,2016:1006-1018.
[19]ERDEM A,LÉO D,THOMAS P,et al.Post-quantum Key Exchange-A New Hope[C]∥USENIX Security Symposium.2016.

相关文章 12

[1]	朱俊,袁晓峰,勾智楠,杨亿. 面向推荐系统数据安全的无证书门限解密方案 Certificateless Threshold Decryption Scheme for Data Security of Recommendation System 计算机科学, 2017, 44(11): 253-263. https://doi.org/10.11896/j.issn.1002-137X.2017.11.038
[2]	夏桂阳,刘宴涛,徐静,Yasser Morgan. 一种基于复数域网络编码的双层卫星通信系统 Double-layer Satellite Communication System Based on Complex Field Network Coding 计算机科学, 2016, 43(10): 114-119. https://doi.org/10.11896/j.issn.1002-137X.2016.10.021
[3]	方黎明,黄志球,王建东. 标准模型下增强的无需安全信道的带关键词搜索的公钥加密 Secure Channel Free Searchable Encryption in Standard Model 计算机科学, 2015, 42(11): 197-202. https://doi.org/10.11896/j.issn.1002-137X.2015.11.041
[4]	郭松辉,牛小鹏,王玉龙. 一种基于椭圆曲线的轻量级身份认证及密钥协商方案 Elliptic Curve Based Light-weight Authentication and Key Agreement Scheme 计算机科学, 2015, 42(1): 137-141. https://doi.org/10.11896/j.issn.1002-137X.2015.01.032
[5]	陈宇,韦鹏程. 基于实数域扩散离散Chebyshev多项式的公钥加密算法 Public-key Encryption Based on Extending Discrete Chebyshev Polynomials' Definition Domain to Real Number 计算机科学, 2011, 38(10): 121-122.
[6]	. 一种改进的PETKS原型方案及其扩展计算机科学, 2009, 36(3): 58-60.
[7]	张林华陈勇. 基于环面自同构的公钥加密方案的密码分析计算机科学, 2007, 34(12): 91-93.
[8]	杨军周贤伟覃伯平. 对一种基于公钥加密算法的组密钥管理方案的密码分析计算机科学, 2006, 33(7): 134-137.
[9]	邓锐周玉洁. Montgomery逆算法的改进和应用计算机科学, 2006, 33(5): 124-127.
[10]	王晓英都志辉. 基于HPL测试的集群系统性能分析与优化计算机科学, 2005, 32(11): 231-234.
[11]	李强颜浩陈克非. 安全多方计算协议的研究与应用计算机科学, 2003, 30(8): 52-55.
[12]	刘鹏何川李三立都志辉黄震春时培植. 跨地域高性能科学计算及其可视化的设计和实现计算机科学, 2002, 29(2): 1-4.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于MLWE的低膨胀率加密算法

Low Expansion Rate Encryption Algorithm Based on MLWE

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

Metrics

本文评价

推荐阅读 0