Computer Science ›› 2020, Vol. 47 ›› Issue (9): 293-303.doi: 10.11896/jsjkx.200400138

;

• Information Security • Previous Articles     Next Articles

Research on Lattice-based Quantum-resistant Authenticated Key Agreement Protocols:A Survey

NI Liang1, WANG Nian-ping2, GU Wei-li1, ZHANG Qian1, LIU Ji-zhao1, SHAN Fang-fang1   

  1. 1 School of Computer Science,Zhongyuan University of Technology,Zhengzhou 450007,China
    2 The PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China
  • Received:2020-04-29 Published:2020-09-10
  • About author:NI Liang,born in 1975,Ph.D,lecturer,is a member of China Computer Federation.His main research interests include network security and cryptography.
  • Supported by:
    Science and Technology Research Program of Henan Province of China (182102210130,192102210286),State Scholarship Fund of China (201908410281),University Key Research Program of Henan Province of China (18A520052) and National Natural Science Foundation of China (61672031).

Abstract: Recent advances in quantum computing have posed a serious potential security threat to the majority of current network security protocols,whose security relies on classical number-theoretic hard problems.As the basic network security protocols,authenticated key agreement protocols bear the brunt.Therefore,quantum-resistant authenticated key agreement protocols have become a recent hot research topic.Thereinto,lattice-based post-quantum cryptographic schemes,with strong security and high computational efficiency,have gained extensive attention in recent years,and are developing rapidly,which are expected to be included in the future standards of quantum-resistant cryptographic algorithms.In this paper,research on lattice-based post-quantum authenticated key agreement protocols is focused on.Firstly,the research background of quantum-resistant authenticated key agreement protocols is introduced,and the main computational hard problems that the security designs of current lattice-based post-quantum cryptographic schemes depend on are also described.Then,an overview of the existing typical lattice-based post-quantum authenticated key agreement protocols is given,and by taking the two-party protocols as the main research object,the basic construction modes of related schemes and performance of several current typical related protocols are discussed,analyzed and compared.Lastly,the existing problems in the current research are summarized,and the future development of related research is also forecasted.

Key words: Authenticated key agreement, Lattice-based cryptography, Post-quantum cryptography, Provable security, Quantum-resistant security protocol

CLC Number: 

  • TP309
[1] DIFFIE W,HELLMAN M.New Directions in Cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654.
[2] SHOR P.Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J].SIAM J.Comput.,1997,26(5):1484-1509.
[3] DEVORET M H,SCHOELKOPF R J.Superconducting Circuits for Quantum Information:an Outlook[J].Science,2013,339(6124):1169-1174.
[4] KELLY J,BARENDS R,FOWLER A G,et al.State Preservation by Repetitive Error Detection in a Superconducting Quantum Circuit[J].Nature,2015,519:66-69.
[5] WAN Y.Summary of Hot Research Topics in InformationTechnology in 2017[J].Science & Technology Review,2018,36(1):91-97.
[6] CESARE C.Online Security Braces for Quantum Revolution[J].Nature,2015,525(7568):167-168.
[7] CHEN L,JORDAN S,LIU Y K,et al.Report on Post-Quantum Cryptography[M].US Department of Commerce,National Institute of Standards and Technology,2016.
[8] GALBRAITH S D,PETIT C,SHANI B,et al.On the Security of Supersingular Isogeny Cryptosystems[C]//Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016).Berlin,Heidelberg:Springer,2016:63-91.
[9] LIU Y M,LI X X,LIU H L.Post-Quantum Key Exchange from Lattice[J].Journal of Cryptologic Research,2017,4(5):485-497.
[10] HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:A Ring-Based Public Key Cryptosystem[C]//Proceedings of the Third International Symposium on Algorithmic Number Theory (ANTS 1998).Berlin,Heidelberg:Springer,1998:267-288.
[11] REGEV O.On Lattices,Learning with Errors,Random Linear Codes,and Cryptography[J].J.ACM,2009,56(6):1-40.
[12] 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 (EUROCRYPT 2010).Berlin,Heidelberg:Springer,2010:1-23.
[13] LYUBASHEVSKY V,PEIKERT C,REGEV O.A Toolkit for Ring-LWE Cryptography[C]//Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2013).Berlin,Heidelberg:Springer,2013:35-54.
[14] PEIKERT C.A Decade of Lattice Cryptography[J].Foundations and Trends in Theoretical Computer Science,2016,10(4):283-424.
[15] AJTAI M.Generating Hard Instances of Lattice Problems[J].Quaderni di Matematica,2004,13:1-32.
[16] AJTAI M,DWORK C.A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence[C]//Proceedings of the 29th annual ACM symposium on Theory of computing (STOC 1997).New York:Association for Computing Machinery,1997:284-293.
[17] BANERJEE A,PEIKERT C,ROSEN A.Pseudorandom Functions and Lattices[C]//Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2012).Berlin,Heidelberg:Springer,2012:719-737.
[18] LANGLOIS A,STEHLÉ D.Worst-Case to Average-Case Re-ductions for Module Lattices[J].Designs,Codes and Cryptography,2015,75(3):565-599.
[19] D’ANVERSJ P,KARMAKAR A,SINHA ROY S,et al.Saber:Module-LWR Based Key Exchange,CPA-Secure Encryption and CCA-Secure KEM[C]//Proceedings of the 10th International Conference on Cryptology in Africa (AFRICACRYPT 2018).Cham:Springer,2018:282-305.
[20] MICCIANCIO D,MOL P.Pseudorandom Knapsacks and theSample Complexity of LWE Search-to-Decision Reductions[C]//Proceedings of the 31st Annual Cryptology Conference.Berlin,Heidelberg:Springer,2011:465-484.
[21] APPLEBAUM B,CASH D,PEIKERT C,et al.Fast Crypto-graphic Primitives and Circular-Secure Encryption Based on Hard Learning Problems[C]//Proceedings of the 29th Annual International Cryptology Conference (CRYPTO 2009).Berlin,Heidelberg:Springer,2009:595-618.
[22] BOGDANOV A,GUO S,MASNY D,et al.On the Hardness of Learning with Rounding over Small Modulus[C]//Proceedings of the 13th International Conference on Theory of Cryptography (TCC 2016).Berlin,Heidelberg:Springer,2016:209-224.
[23] PEIKERT C.How (Not) to Instantiate Ring-LWE[C]//Proceedings of the 10th International Conference on Security and Cryptography.Cham:Springer,2016:411-430.
[24] GONG B,ZHAO Y.Cryptanalysis of RLWE-Based One-PassAuthenticated Key Exchange[C]//Proceedings of the 8th International Workshop on Post-Quantum Cryptography.Cham:Springer,2017:163-183.
[25] DING J,FLUHRER S,RV S.Complete Attack on RLWE Key Exchange with Reused Keys,Without Signal Leakage[C]//Proceedings of the the 23rd Australasian Conference on Information Security and Privacy.Cham:Springer,2018:467-486.
[26] BAUER A,GILBERT H,RENAULT G,et al.Assessment ofthe Key-Reuse Resilience of NewHope[C]//Proceedings of the Cryptographers’ Track at the RSA Conference 2019.Cham:Springer,2019:272-292.
[27] DODIS Y,REYZIN L,SMITH A.Fuzzy Extractors:How toGenerate Strong Keys from Biometrics and Other Noisy Data[C]//Proceedings of the the 23rd Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Heidelberg:Springer,2004:523-540.
[28] DENT A W.A Designer’s Guide to KEMs[C]//Proceedings of the 9th IMA International Conference on Cryptography and Coding.Berlin,Heidelberg:Springer,2003:133-151.
[29] DING J,XIE X,LIN X.A Simple Provably Secure Key Ex-change Scheme Based on the Learning with Errors Problem[EB/OL].IACR Cryptology ePrint Archive.https://eprint.iacr.org/2012/688.pdf.
[30] PEIKERT C.Lattice Cryptography for the Internet[C]//Proceedings of the 6th International Workshop on Post-Quantum Cryptography.Cham:Springer,2014:197-219.
[31] KRAWCZYK H.SIGMA:The ‘SIGn-and-MAc’ Approach toAuthenticated Diffie-Hellman and Its Use in the IKE Protocols[C]//Proceedings of the 23rd Annual International Cryptology Conference.Berlin,Heidelberg:Springer,2003:400-425.
[32] BOS J W,COSTELLO C,NAEHRIG M,et al.Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem[C]//Proceedings of the 2015 IEEE Symposium on Security and Privacy (SP 2015).USA:IEEE Computer Society,2015:553-570.
[33] ZHANG J,ZHANG Z,DING J,et al.Authenticated Key Ex-change from Ideal Lattices[C]//Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Heidelberg:Springer,2015:719-751.
[34] KRAWCZYK H.HMQV:A High-Performance Secure Diffie-Hellman Protocol[C]//Proceedings of the 25th Annual International Cryptology Conference.Berlin,Heidelberg:Springer,2005:546-566.
[35] BELLARE M,ROGAWAY P.Random Oracles Are Practical:A Paradigm for Designing Efficient Protocols[C]// Proceedings of the 1st ACM Conference on Computer and Communications Security (CCS 1993).New York:Association for Computing Machinery,1993:62-73.
[36] ALKIM E,DUCAS L,ELMANN T,et al.Post-Quantum Key Exchange - A New Hope[C]//Proceedings of the 25th USENIX Security Symposium.USA:USENIX Association,2016:327-343.
[37] ALKIM E,DUCAS L,ELMANN T,et al.NewHope without Reconciliation[EB/OL].IACR Cryptology ePrint Archive.https://eprint.iacr.org/2016/1157.pdf.
[38] BOS J,COSTELLO C,DUCAS L,et al.Frodo:Take off theRing! Practical,Quantum-Secure Key Exchange from LWE[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS 2016).New York,NY,USA:Association for Computing Machinery,2016:1006-1018.
[39] JIN Z,ZHAO Y.Optimal Key Consensus in Presence of Noise[EB/OL].IACR Cryptology ePrint Archive.https://eprint.iacr.org/2017/1058.pdf.
[40] JIN Z,ZHAO Y.Generic and Practical Key Establishment from Lattice[C]//Proceedings of the 17th International Conference on Applied Cryptography and Network Security.Cham:Sprin-ger,2019:302-322.
[41] BOS J,DUCAS L,KILTZ E,et al.CRYSTALS- Kyber:ACCA-Secure Module-Lattice-Based KEM[C]//Proceedings of the 2018 IEEE European Symposium on Security and Privacy.London,UK:IEEE,2018:353-367.
[42] DEL PINO R,LYUBASHEVSKY V,POINTCHEVAL D.The Whole is Less Than the Sum of Its Parts:Constructing More Efficient Lattice-Based AKEs[C]//Proceedings of the 10th International Conference on Security and Cryptography.Cham:Springer,2016:273-291.
[43] DE SAINT GUILHEM C,SMART N P,WARINSCHI B.Generic Forward-Secure Key Agreement Without Signatures[C]//Proceedings of the 20th International Conference on Information Security.Cham:Springer,2017:114-133.
[44] FUJIOKA A,SUZUKI K,XAGAWA K,et al.Strongly Secure Authenticated Key Exchange from Factoring,Codes,and Lattices[C]//Proceedings of the 15th International Conference on Practice and Theory in Public Key Cryptography.Berlin,Heidelberg:Springer,2012:467-484.
[45] FUJIOKA A,SUZUKI K,XAGAWA K,et al.Practical andPost-Quantum Authenticated Key Exchange from One-Way Secure Key Encapsulation Mechanism[C]//Proceedings of the 8th ACM SIGSAC Symposium on Information,Computer and Communications Security.New York,NY,USA:Association for Computing Machinery,2013:83-94.
[46] FUJISAKI E,OKAMOTO T.How to Enhance the Security of Public-Key Encryption at Minimum Cost[C]//Proceedings of the Second International Workshop on Practice and Theory in Public Key Cryptography.Berlin,Heidelberg:Springer,1999:53-68.
[47] HOFHEINZ D,HVELMANNS K,KILTZ E.A Modular Analysis of the Fujisaki-Okamoto Transformation[C]//Proceedings ofthe 15th International Conference on Theory of Cryptography.Cham:Springer,2017:341-371.
[48] HVELMANNS K,KILTZ E,SCHGE S,et al.Generic Au-thenticated Key Exchange in the Quantum Random OracleModel[C]//Proceedings of the 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography.Cham:Springer,2020:389-422.
[49] NEJATOLLAHI H,DUTT N,RAY S,et al.Post-QuantumLattice-Based Cryptography Implementations:A Survey[J].ACM Computing Surveys,2019,51(6):129-169.
[50] BINDEL N,BUCHMANN J,RIE S.Comparing Apples withApples:Performance Analysis of Lattice-Based Authenticated Key Exchange Protocols[J].International Journal of Information Security,2018,17(6):701-718.
[51] BONEH D,DAGDELEN ,FISCHLIN M,et al.Random Ora-cles in a Quantum World[C]//Proceedings of the 17th Interna-.
tional Conference on the Theory and Application of Cryptology and Information Security.Berlin,Heidelberg:Springer,2011:41-69.
[52] SAITO T,XAGAWA K,YAMAKAWA T.Tightly-Secure Key-Encapsulation Mechanism in the Quantum Random OracleModel[C]//Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Cham:Springer,2018:520-551.
[53] JIANG H,ZHANG Z,CHEN L,et al.IND-CCA-Secure KeyEncapsulation Mechanism in the Quantum Random Oracle Model,Revisited[C]//Proceedings of the 38th Annual International Cryptology Conference.Cham:Springer,2018:96-125.
[54] KATSUMATA S,YAMADA S,YAMAKAWA T.Tighter Security Proofs for GPV-IBE in the Quantum Random Oracle Model[C]//Proceedings of the 24th International Conference on the Theory and Applications of Cryptology and Information Security.Cham:Springer,2018:253-282.
[55] BRENDEL J,FISCHLIN M,GNTHER F,et al.Challenges in Proving Post-Quantum Key Exchanges Based on Key Encapsulation Mechanisms[EB/OL].IACR Cryptology ePrint Archive.https://eprint.iacr.org/2019/1356.pdf.
[56] QIN Y,CHENG C,DING J.A Complete and Optimized Key Mismatch Attack on NIST Candidate NewHope[C]//Procee-dings of the 24th European Symposium on Research in Computer Security.Cham:Springer,2019:504-520.
[57] DING J,CHENG C,QIN Y.A Simple Key Reuse Attack on LWE and Ring LWE Encryption Schemes as Key Encapsulation Mechanisms (KEMs) [EB/OL].IACR Cryptology ePrint Archive.https://eprint.iacr.org/2019/271.pdf.
[58] WU H S.Analysis of Post-Quantum Cryptographic Develop-ment[EB/OL].(2017-01-13).The Website of Knowfar Institute for Strategic and Defence Studies.http://www.knowfar.org.cn/html/zhanlue/201701/13/657.htm.
[1] ZHANG Zhen-chao, LIU Ya-li, YIN Xin-chun. New Certificateless Generalized Signcryption Scheme for Internet of Things Environment [J]. Computer Science, 2022, 49(3): 329-337.
[2] LI Shu-quan,LIU Lei,ZHU Da-yong,XIONG Chao,LI Rui. Protocol of Dynamic Provable Data Integrity for Cloud Storage [J]. Computer Science, 2020, 47(2): 256-261.
[3] QIN Yan-lin, WU Xiao-ping, HU Wei. Efficient Identity-based Authenticated Key Agreement Protocol with Multiple Private Key Generators [J]. Computer Science, 2020, 47(11): 68-72.
[4] YE Jun-yao, ZHENG Dong and REN Fang. Improved Veron’s Identification with Lightweight Structure and Digital Signature Scheme [J]. Computer Science, 2017, 44(3): 168-174.
[5] JIANG Di and HAN Yi-liang. Attribute-based Online/Offline Signcryption for Mobile Network [J]. Computer Science, 2016, 43(11): 221-225.
[6] ZHANG Xiang-song and LIU Zhen-hua. Non-trapdoors Lattice Signature Scheme with Message Recovery [J]. Computer Science, 2014, 41(9): 165-168.
[7] TAO Wen-jun and HU Bin. Formal Security Model Resist ing Session Exponential Reveal for Key Agreement Protocol [J]. Computer Science, 2013, 40(11): 98-102.
[8] SUN Hua and ZHENG Xue-feng. Provably Secure and Efficient Certificateless Signcryption Scheme [J]. Computer Science, 2013, 40(11): 112-116.
[9] . Provable Secure Route Optimization Scheme for HMIPv6 in Wireless Mesh Network [J]. Computer Science, 2012, 39(3): 62-66.
[10] HOU Hui-fang, WANG Yun-xia. Provable Secure Authentication Protocol Based on CPK and Improved ECDH Algorithm [J]. Computer Science, 2011, 38(9): 55-58.
[11] WEN Yi-ling,MA Jian-feng,WANG Chao. New ID-based Aggregate Signature Scheme [J]. Computer Science, 2011, 38(6): 54-57.
[12] WANG Qing-long,ZHANG Shao-bo. Public Traceable Traitor Tracing Scheme Secure against CCA2 [J]. Computer Science, 2011, 38(2): 106-109.
[13] . Certificate-based Aggregate Signature Scheme [J]. Computer Science, 2011, 38(12): 57-60.
[14] . [J]. Computer Science, 2008, 35(9): 9-12.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!