基于格的抗量子认证密钥协商协议研究综述

doi:10.11896/jsjkx.200400138

摘要/Abstract

摘要： 最近在量子计算研究领域所取得的进展对当前网络安全协议中大多数的安全性依赖传统数论难题的方案构成了严重的潜在安全威胁,作为基础性网络安全协议的认证密钥协商协议首当其冲。由此,抗量子认证密钥协商协议成为了近来的一个研究热点。其中,基于格的后量子密码(Post-Quantum Cryptography)方案由于安全性强、计算效率高,于近年得到了广泛重视且现在正快速发展,有望被列入未来的抗量子密码算法标准。文中重点关注基于格的后量子认证密钥协商协议研究。首先,对抗量子认证密钥协商协议的研究背景进行介绍,并对当前基于格的后量子密码方案安全性设计所基于的主要计算性困难问题进行描述;接着,对现有典型基于格的后量子认证密钥协商协议进行概述,并以两方协议为主要研究对象,对相关方案的基本构造模式和若干当前典型相关协议的性能进行讨论、分析和比较;最后,对当前研究中存在的问题进行总结,并对相关研究的未来发展进行展望。

关键词: 后量子密码, 基于格的密码, 抗量子安全协议, 可证明安全, 认证密钥协商

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

中图分类号:

TP309

倪亮, 王念平, 谷威力, 张茜, 刘伎昭, 单芳芳. 基于格的抗量子认证密钥协商协议研究综述[J]. 计算机科学, 2020, 47(9): 293-303. https://doi.org/10.11896/jsjkx.200400138

NI Liang, WANG Nian-ping, GU Wei-li, ZHANG Qian, LIU Ji-zhao, SHAN Fang-fang. Research on Lattice-based Quantum-resistant Authenticated Key Agreement Protocols:A Survey[J]. Computer Science, 2020, 47(9): 293-303. https://doi.org/10.11896/jsjkx.200400138

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed