计算机科学 ›› 2020, Vol. 47 ›› Issue (9): 293-303.doi: 10.11896/jsjkx.200400138
所属专题: 密码学 虚拟专题
倪亮1, 王念平2, 谷威力1, 张茜1, 刘伎昭1, 单芳芳1
NI Liang1, WANG Nian-ping2, GU Wei-li1, ZHANG Qian1, LIU Ji-zhao1, SHAN Fang-fang1
摘要: 最近在量子计算研究领域所取得的进展对当前网络安全协议中大多数的安全性依赖传统数论难题的方案构成了严重的潜在安全威胁,作为基础性网络安全协议的认证密钥协商协议首当其冲。由此,抗量子认证密钥协商协议成为了近来的一个研究热点。其中,基于格的后量子密码(Post-Quantum Cryptography)方案由于安全性强、计算效率高,于近年得到了广泛重视且现在正快速发展,有望被列入未来的抗量子密码算法标准。文中重点关注基于格的后量子认证密钥协商协议研究。首先,对抗量子认证密钥协商协议的研究背景进行介绍,并对当前基于格的后量子密码方案安全性设计所基于的主要计算性困难问题进行描述;接着,对现有典型基于格的后量子认证密钥协商协议进行概述,并以两方协议为主要研究对象,对相关方案的基本构造模式和若干当前典型相关协议的性能进行讨论、分析和比较;最后,对当前研究中存在的问题进行总结,并对相关研究的未来发展进行展望。
中图分类号:
[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,SCHGE 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,GNTHER 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] | 张振超, 刘亚丽, 殷新春. 适用于物联网环境的无证书广义签密方案 New Certificateless Generalized Signcryption Scheme for Internet of Things Environment 计算机科学, 2022, 49(3): 329-337. https://doi.org/10.11896/jsjkx.201200256 |
[2] | 莫天庆, 何咏梅. 一种基于无证书的SIP认证密钥协商协议 SIP Authentication Key Agreement of Protocol Based on Certificateless 计算机科学, 2020, 47(6A): 413-419. https://doi.org/10.11896/JsJkx.191100216 |
[3] | 秦艳琳, 吴晓平, 胡卫. 多重PKG环境中高效的身份基认证密钥协商协议 Efficient Identity-based Authenticated Key Agreement Protocol with Multiple Private Key Generators 计算机科学, 2020, 47(11): 68-72. https://doi.org/10.11896/jsjkx.191000008 |
[4] | 叶君耀,郑东,任方. 改进的具有轻量级结构的Veron身份认证及数字签名方案 Improved Veron’s Identification with Lightweight Structure and Digital Signature Scheme 计算机科学, 2017, 44(3): 168-174. https://doi.org/10.11896/j.issn.1002-137X.2017.03.037 |
[5] | 姜頔,韩益亮. 适用于移动网络的属性基在线/离线签密方案 Attribute-based Online/Offline Signcryption for Mobile Network 计算机科学, 2016, 43(11): 221-225. https://doi.org/10.11896/j.issn.1002-137X.2016.11.043 |
[6] | 张恩,孙权党,刘亚鹏. 抗合谋理性多秘密共享方案 Collusion-free Rational Multi-secret Sharing Scheme 计算机科学, 2015, 42(10): 164-169. |
[7] | 张襄松,刘振华. 具有消息恢复功能的无陷门格签名方案 Non-trapdoors Lattice Signature Scheme with Message Recovery 计算机科学, 2014, 41(9): 165-168. https://doi.org/10.11896/j.issn.1002-137X.2014.09.031 |
[8] | 柳秀梅,高克宁,薛丽芳,常桂然,周福才. eCK模型下的密钥协商 Authenticated Key Exchange in eCK Model 计算机科学, 2014, 41(8): 172-177. https://doi.org/10.11896/j.issn.1002-137X.2014.08.038 |
[9] | 孙 瑾,胡予濮. 基于身份的新型广播签密方案 Novel Identity Based Broadcast Signcryption Scheme 计算机科学, 2013, 40(2): 124-128. |
[10] | 孙华,郑雪峰. 一种可证明安全的有效无证书签密方案 Provably Secure and Efficient Certificateless Signcryption Scheme 计算机科学, 2013, 40(11): 112-116. |
[11] | 陶文君,胡斌. 一个可抵抗临时指数泄露的密钥协商协议形式化安全模型 Formal Security Model Resist ing Session Exponential Reveal for Key Agreement Protocol 计算机科学, 2013, 40(11): 98-102. |
[12] | 王刚,郭渊博,刘伟. 一种无线Mesh网络中可证明安全的HMIPv6路由优化方案 Provable Secure Route Optimization Scheme for HMIPv6 in Wireless Mesh Network 计算机科学, 2012, 39(3): 62-66. |
[13] | 侯惠芳,王云侠. 基于CPK和改进ECDH算法的可证安全的认证协议 Provable Secure Authentication Protocol Based on CPK and Improved ECDH Algorithm 计算机科学, 2011, 38(9): 55-58. |
[14] | 文毅玲,马建峰,王超. 一个新的基于身份的聚合签名方案 New ID-based Aggregate Signature Scheme 计算机科学, 2011, 38(6): 54-57. |
[15] | 赵秀凤,徐秋亮,韦大伟. 群组密钥协商协议的安全性分析方法研究 Security Analysis Approaches for Group Key Agreement Protocols 计算机科学, 2011, 38(6): 145-148. |
|