Computer Science ›› 2019, Vol. 46 ›› Issue (4): 144-150.doi: 10.11896/j.issn.1002-137X.2019.04.023

• Information Security • Previous Articles     Next Articles

Low Expansion Rate Encryption Algorithm Based on MLWE

KE Cheng-song1,2, WU Wen-yuan2, FENG Yong2   

  1. College of Computer Science & Technology,Chongqing University of Posts & Telecommunications,Chongqing 400065,China1
    Chongqing Key Laboratory of Automated Reasoning & Cognition,Chongqing Institute of Green & Intelligent Technology,Chinese Academy of Sciences,Chongqing 400714,China2
  • Received:2018-03-09 Online:2019-04-15 Published:2019-04-23

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

CLC Number: 

  • TP309
[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.
[1] ZHU Jun, YUAN Xiao-feng, GOU Zhi-nan and YANG Yi. Certificateless Threshold Decryption Scheme for Data Security of Recommendation System [J]. Computer Science, 2017, 44(11): 253-263.
[2] XIA Gui-yang, LIU Yan-tao, XU Jing and Yasser Morgan. Double-layer Satellite Communication System Based on Complex Field Network Coding [J]. Computer Science, 2016, 43(10): 114-119.
[3] FANG Li-ming, HUANG Zhi-qiu and WANG Jian-dong. Secure Channel Free Searchable Encryption in Standard Model [J]. Computer Science, 2015, 42(11): 197-202.
[4] ZHANG Lin-Hua CHEN Yong (College of Math&Computer, Chongqing Normal University, Chongqing 400047). [J]. Computer Science, 2007, 34(12): 91-93.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!