后量子密码技术研究综述

doi:10.11896/jsjkx.240500056

摘要/Abstract

摘要： 量子计算的发展对经典密码体制造成了极大的安全威胁。后量子密码算法在理论上可以抵抗量子攻击,因此成为现阶段研究的热点。根据困难性假设分类,首先介绍基于格、编码、多变量、哈希函数等的后量子密码算法的研究现状,分析其技术特点和优劣,同时结合NIST后量子密码标准化成果,介绍不同技术路线的典型密码算法。最后,总结现阶段后量子密码迁移的技术方案,并提出未来后量子密码可能的发展方向。

关键词: 后量子密码, 基于格的密码, 基于编码的密码, 基于多变量的密码, 基于哈希的密码, 量子迁移

Abstract: The development of quantum computing poses a significant security threat to classical cryptographic systems.Post-quantum cryptographic algorithms,which are theoretically capable of resisting quantum attacks,have become a hot topic of research at present.According to the classification of hardness assumptions,this paper first introduces the current state of research on post-quantum cryptographic algorithms such as lattice-based,code-based,multivariate,and hash-based,analyzing their technical characteristics and advantages and disadvantages.At the same time,combined with the results of the NIST post-quantum cryptography standardization,typical cryptographic algorithms of different technical routes are introduced.Finally,this paper summarizes the technical solutions for the current migration to post-quantum cryptography and proposes possible future development directions for post-quantum cryptography.

Key words: Post-quantum cryptography, Lattice-based cryptography, Code-based cryptography, Multivariate-based cryptography, Hash-based cryptography, Post-quantum migration

中图分类号:

TP309

吴昆, 胡现刚. 后量子密码技术研究综述[J]. 计算机科学, 2025, 52(2): 8-19. https://doi.org/10.11896/jsjkx.240500056

WU Kun, HU Xiangang. Overview of Research on Post-quantum Cryptography Technology[J]. Computer Science, 2025, 52(2): 8-19. https://doi.org/10.11896/jsjkx.240500056

参考文献

[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.1996:212-219.
[3]CAMPBELL R,DIFFIE W,ROBINSON C.Advancements inQuantum Computing and AI May Impact PQC Migration Timelines[J/OL].https://www.researchgate.net/publication/378735569_Advancements_in_Quantum_Computing_and_AI_May_Impact_PQC_Migration_Timelines.
[4]DENG Y H,GU Y C,LIU H L,et al.Gaussian boson sampling with pseudo-photon-number-resolving detectors and quantum computational advantage[J].Physical Review Letters,2023,131(15):150601.
[5]ICV.2024 Global Quantum Computing Industry DevelopmentProspect [EB/OL].https://www.icvtank.com/filedownload/125447.
[6]DAM D T,TRAN T H,HOANG V P,et al.A survey of post-quantum cryptography:Start of a new race[J].Cryptography,2023,7(3):40.
[7]LIU Y D,CHENG Q F.A Survey of Isogeny-Based Cryptographic Schemes[J].Journal of Cryptologic Research,2023,10(4):667-684.
[8]AZARDERAKHSH R,CAMPAGNA M,COSTELLO C,et al.Supersingular isogeny key encapsulation[J].Submission to the NIST Post-Quantum Standardization Project,2017,152:154-155.
[9]CASTRYCK W,DECRU T.An efficient key recovery attack on SIDH[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Cham:Springer Nature Switzerland,2023:423-447.
[10]CHEN L,JORDAN S P,LIU Y K,et al.Report on post-quantum cryptography[R].Gaithersburg,MD,USA:US Department of Commerce,National Institute of Standards and Technology,2016.
[11]NIST.Post-Quantum Cryptography Selected Algorithms 2022[EB/OL].[2023-09-02].https://csrc.nist.gov/Projects/post-quantum-cryptography/selectedalgorithms-2022.
[12]AJTAI M.Generating hard instances of lattice problems[C]//Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing(STOC'96).ACM,1996:99-108.
[13]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(STOC '97).ACM,1997:284-293.
[14]HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:A ring-based public key cryptosystem [C]//Algorithmic Number Theory-ANTS '98.Springer Berlin Heidelberg,1998:267-288.
[15]REGEV O.On lattices,learning with errors,random linearcodes,and cryptography[C]//Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing(STOC '05),ACM,2005:84-93.
[16]LYUBASHEVSKY V,PEIKERT C,REGEV O.On ideal lattices and learning with errors over rings[C]//Advances in Cryptology-EUROCRYPT 2010.Springer Berlin Heidelberg,2010:1-23.
[17]LANGLOIS A,STEHLÉ D.Worst-case to average-case reductions for module lattices[J].Designs,Codes and Cryptography,2015,75(3):565-599.
[18]NAEHRIG M,ALKIM E,BOS J,et al.FrodoKEM[R].NationalInstitute of Standards and Technology(2017),2017.
[19]ALKIM E,AVANZI R,BOS J,et al.Supporting documen-tation:NewHope[R].National Institute of Standards and Technology,2017.
[20]D'ANVERS J P,KARMAKAR A,SINHA R S,et al.Saber:Module-LWR based key exchange,CPA-secure encryption and CCA-secure KEM[C]//Progress in Cryptology-AFRICACRYPT 2018:10th International Conference on Cryptology in Africa,Proceedings 10.Springer International Publishing,2018:282-305.
[21]AVANZIR,BOS J,DUCAS L,et al.CRYSTALS-Kyber[EB/OL].(2021-08-04)[2024-08-10].https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf.
[22]STEHLÉ D,STEINFELD R.Making NTRU as secure asworst-case problems over ideal lattices[C]//Advances in Cryptology-EUROCRYPT 2011:30th Annual International Confe-rence on the Theory and Applications of Cryptographic Techniques,Tallinn,Estonia,May 15-19,2011.Springer Berlin Heidelberg,2011:27-47.
[23]WANG Y,WANG M.Provably secure NTRUEncrypt over any cyclotomic field[C]//International Conference on Selected Areas in Cryptography.Cham:Springer International Publishing,2018:391-417.
[24]NTRUEncrypt:A lattice based encryption algorithm[R].Na-tional Institute of Standards and Technology,2017.
[25]BERNSTEIN D J,CHUENGSATIANSUP C,LANGE T,et al.NTRU Prime[J/OL].https://ntruprime.cr.yp.to/.
[26]HÜLSING A,RIJNEVELD J,SCHANCK J M,et al.NTRU-HRSS-KEM[R].NIST Submission,2017.
[27]CHEN C,DANBA O,HOFFSTEIN J,et al.Algorithm specifications and supporting documentation[R].Brown University and Onboard Security Company,Wilmington,USA:2019.
[28]HAN P,TANG C M.Design of lattice-based fully homomorphic encryption scheme[J].Journal of China West Normal University(Natural Sciences),2022,43(1):33-39.
[29]KIM A,DERYABIN M,EOM J,et al.General bootstrapping approach for RLWE-based homomorphic encryption[J].IEEE Transactions on Computers,2024,73(1):86-96.
[30]LIU Q,WANG Z B,YU C W,et al.Efficient Attribute-Based Encryption Scheme from Lattices for Cloud Security[J].Netinfo Security,2023,23(9):25-36.
[31]YAO Y F,CHEN H Y,SHEN L Z,et al.A CP-ABE Scheme Based on Lattice LWE and Its Security Analysis[J].Applied Sciences,2023,13(14):8043.
[32]QIAN X Y,WU W Y.Identity-based Encryption Scheme Based on R-SIS/R-LWE[J].Computer Science,2021,48(6):315-323.
[33]LIAN Y,HUANG R.KDM Security IBE Based on LWE Beyond Affine Functions[J].Applied Sciences,2023,13(14):8259.
[34]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trap-doors for hard lattices and new cryptographic constructions[C]//Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing.2008:197-206.
[35]WUSSLER A.Post-Quantum cryptography in OpenPGP[J/OL].https://www.wussler.it/NIST5thPQC.pdf.
[36]POETTERING B,RASTIKIAN S.Formalizing Hash-then-Sign Signatures[C]//IACR International Conference on Public-Key Cryptography.Cham:Springer Nature Switzerland,2024:289-315.
[37]PREST T,FOUQUE P A,HOFFSTEIN J,et al.Falcon[R].Technical report,National Institute of Standards and Technology,2020.
[38]FIAT A,SHAMIR A.How to prove yourself:Practical solu-tions to identification and signature problems[C]//Conference on the Theory and Application of Cryptographic Techniques.1986:186-194.
[39]ABDALLA M,AN J H,BELLARE M,et al.From identification to signatures via the Fiat-Shamir transform:Minimizing assumptions for security and forward-security[C]//Advances in Cryptology－EUROCRYPT 2002:International Conference on the Theory and Applications of Cryptographic Techniques Amsterdam.2002:418-433.
[40]DUCAS L.Accelerating Bliss:the geometry of ternary polynomials[J/OL].https://eprint.iacr.org/2014/874.pdf.
[41]BARTHE G,BELAÏD S,ESPITAU T,et al.GALACTICS:Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures,revisited[C]//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security.2019:2147-2164.
[42]DUCAS L,KILTZ E,LEPOINT T,et al.Crystals-dilithium[EB/OL].(2021-02-08)[2024-08-25].https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf.
[43]BERLEKAMP E,MCELIECE R,VAN T H.On the inherent intractability of certain coding problems(corresp.)[J].IEEE Transactions on Information Theory,1978,24(3):384-386.
[44]MCELIECE R J.A public-key cryptosystem based on algebraic[J].Coding Thv,1978,4244:114-116.
[45]NIEDERREITER H.Knapsack-type cryptosystems and alge-braic coding theory[J].Prob.Contro.Inform.Theory,1986,15(2):157-166.
[46]ARAGON N,BARRETO P,BETTAIEB S,et al.BIKE:bit flipping key encapsulation[R].Technical report,National Institute of Standards and Technology,2022.
[47]Hamming Quasi-Cyclic(HQC)(NIST Round 4 Submission)[EB/OL].https://pqc-hqc.org/index.html.
[48]BALDI M,BARENGHI A,CHIARALUCE F,et al.LEDApkc:Low-dEnsity parity-check coDe-bAsed public-key cryptosystem[R].Technical report,National Institute of Standards and Technology,2017.
[49]HOOSHMAND R,SHOOSHTARI M K,AREF M R,et al.PKC-PC:a variant of the McEliece public-key cryptosystem based on polar codes[J].IET Communications,2020,14(12):1883-1893.
[50]HOOSHMAND R,MAHDI K.Key encapsulation mechanismbased on polar codes[J].IET Communications,2022,16(20):2438-2447.
[51]LAKE Y V,TARANEH E.An efficient,secure and verifiableconjunctive keyword search scheme based on rank metric codes over encrypted outsourced cloud data[J].Computers and Electrical Engineering 2023,105:108523.
[52]MOODY D.NIST PQC Standardization Update[EB/OL].ht-tps://csrc.nist.gov/CSRC/media/Presentations/pqc-update-round-2-and-beyond/images-media/pqcrypto-sept2020-moody.pdf.
[53]BOMBAR M,ALAIN C.Decoding supercodes of Gabidulincodes and applications to cryptanalysis[C]//Post-Quantum Cryptography:12th International Workshop,PQCrypto 2021,Daejeon,South Korea,July 20－22,2021,Proceedings 12.Springer International Publishing,2021.
[54]KIM J L,KIM Y S,GALVEZ L,et al.McNie:A code-based public-key cryptosystem[J].arXiv:1812.05008,2018.
[55]BINDAL E,ABHAY K S.Secure and Compact:A New Variant of McEliece Cryptosystem[J].IEEE Access,2024,1235586-35596.
[56]Classic McEliece NIST Proposal[EB/OL].https://classic.mceliece.org/.
[57]GAREY M R,DAVID S J.Computers and intractability[EB/OL].https://bohr.wlu.ca/hfan/cp412/references/ChapterOne.pdf.
[58]PATARIN J,GOUBIN L,COURTOIS N.Improved algorithms for isomorphisms of polynomials[C]//International Conference on the Theory and Application of Cryptographic Techniques.1998.
[59]MATSUMOTO T,IMAI H.Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[C]//Advances in Cryptology—EUROCRYPT'88:Workshop on the Theory and Application of Cryptographic Techniques Davos,Switzerland,May 25－27,1988 Proceedings 7.Springer Berlin Heidelberg,1988:419-453.
[60]PATARIN J.Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88[C]//Advances in Cryptology－CRYPT0'95:15th Annual International Cryptology Conference Santa Barbara,California,USA,August 27－31,1995 Proceedings 15.Springer Berlin Heidelberg,1995:248-261.
[61]PATARIN J.Hidden fields equations(HFE) and isomorphisms of polynomials(IP):Two new families of asymmetric algorithms[C]//International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Heidelberg:Springer Berlin Heidelberg,1996:33-48.
[62]KIPNIS A,SHAMIR A.Cryptanalysis of the HFE public key cryptosystem by relinearization[C]//Annual International Cryptology Conference.Berlin,Heidelberg:Springer Berlin Heidelberg,1999:19-30.
[63]PORRAS J,BAENA J,DING J.ZHFE,a new multivariate public key encryption scheme[C]//Post-Quantum Cryptography:6th International Workshop,PQCrypto 2014,Waterloo,ON,Canada,October 1－3,2014.Proceedings 6.Springer International Publishing,2014:229-245.
[64]CARTOR R,SMITH-TONE D.EFLASH:a new multivariate encryption scheme[C]//Selected Areas in Cryptography-SAC 2018:25th International Conference,Calgary,AB,Canada,August 15－17,2018,Revised Selected Papers 25.Springer International Publishing,2019:281-299.
[65]YASUDA T,SAKURAI K.A multivariate encryption scheme with rainbow[C]//Information and Communications Security:17th International Conference,ICICS 2015.2016:236-251.
[66]IKEMATSU Y,PERLNER R,SMITH-TONE D,et al.HFERP－a new multivariate encryption scheme[C]//Post-Quantum Cryptography:9th International Conference.2018:396-416.
[67]YASUDA T,WANG Y,TAKAGI T.Multivariate encryption schemes based on polynomial equations over real numbers[C]//Post-Quantum Cryptography:11th International Conference.2020:402-421.
[68]SMITH T D.2F-A New Method for Constructing Efficient Multivariate Encryption Schemes[C]//International Conference on Post-Quantum Cryptography.Cham:Springer International Publishing,2022:185-201.
[69]PATARIN J.The oil and vinegar algorithm for signatures[C]//Dagstuhl Workshop on Cryptography.1997.
[70]KIPNIS A,SHAMIR A.Cryptanalysis of the oil and vinegar signature scheme[C]//Annual International Cryptology Confe-rence.Berlin,Heidelberg:Springer Berlin Heidelberg,1998:257-266.
[71]KIPNIS A,PATARIN J,GOUBIN L.Unbalanced oil and vinegar signature schemes[C]//International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Heidelberg:Springer Berlin Heidelberg,1999:206-222.
[72]DING J,SCHMIDT D.Rainbow,a new multivariable polynomial signature scheme[C]//International Conference on Applied Cryptography and Network Security.Berlin,Heidelberg:Sprin-ger Berlin Heidelberg,2005:164-175.
[73]MACARIORAT G,PATARIN J.UOV-pepper:New public key short signature in degree 3[J/OL].https://eprint.iacr.org/2021/1006.pdf.
[74]FURUE H,IKEMATSU Y,HOSHINO F,et al.QR-UOV[R].National Institute of Standards and Technology,2023.
[75]CARTOR R,CARTOR M,LEWIS M,et al.IPRainbow[C]//International Conference on Post-Quantum Cryptography.Cham:Springer International Publishing,2022:170-184.
[76]ZHANG W,TAN C H.MI-T-HFE,a new multivariate signature scheme[C]//Cryptography and Coding:15th IMA International Conference.2015:43-56.
[77]PETZOLDT A,CHEN M S,YANG B Y,et al.Design principles for HFEv-based multivariate signature schemes[C]//Advances in Cryptology－ASIACRYPT 2015:21st International Confe-rence on the Theory and Application of Cryptology and Information Security.2015:311-334.
[78]PETZOLDT A,CHEN M S,DING J,et al.HMFEv-an efficient multivariate signature scheme[C]//Post-Quantum Cryptography:8th International Workshop.2017:205-223.
[79]CASANOVA A,FAUGERE J C,MACARIORAT G,et al.GeMSS:A great multivariate short signature[C]//Submission to NIST.2017.
[80]LUYEN L V.An improved identity-based multivariate signature scheme based on rainbow[J].Cryptography,2019,3(1):8.
[81]DUTTA R,DEBNATH S K,BISWAS C.Storage FriendlyProvably Secure Multivariate Identity-Based Signature from Isomorphism of Polynomials Problem[C]//SECRYPT.2021:595-602.
[82]TAO Y,YANG Y T,LI Z C,et al.Multivariate group signature scheme with standing conspiracy attacks[J].Journal of University of Science and Technology of China,2011,41(7):615-618.
[83]KUNDU N,DEBNATH S K,MISHRA D.A secure and effi-cient group signature scheme based on multivariate public key cryptography[J].Journal of Information Security and Applications,2021,58:102776.
[84]YU H F,FU S F.Post-Quantum blind signature scheme based on multivariate cryptosystem[J].Ruan Jian Xue Bao Journal of Software,2021,32(9):2935-2944.
[85]PETZOLDT A,SZEPIENIEC A,MOHAMED M S E.A practical multivariate blind signature scheme[C]//Financial Cryptography and Data Security:21st International Conference.2017:437-454.
[86]GUO Q L,XIANG H,CAI B,et al.Threshold ring signature scheme based on multivariate public key cryptosystems[J].Journal of Cryptologic Research,2018,5(2):140-150.
[87]DUONG D H,TRAN H T N,SUSILO W.An efficient multivariate threshold ring signature scheme[J].Computer Standards &Interfaces,2021,74:103489.
[88]DING J,CHEN M S,PETZOLDT A,et al.Rainbow[R].Technical report,National Institute of Standards and Technology,2019.
[89]BEULLENS W.Breaking rainbow takes a weekend on a laptop[C]//Annual International Cryptology Conference.2022:464-479.
[90]LAMPORT L.Constructing digital signatures from a one wayfunction[J/OL].https://www.microsoft.com/en-us/research/uploads/prod/2016/12/Constructing-Digital-Signatures-from-a-One-Way-Function.pdf.
[91]MERKLE R C.A certified digital signature[C]//Conference on the Theory and Application of Cryptology.1987:218-238.
[92]BUCHMANN J,DAHMEN E,ERETH S,et al.On the security of the Winternitz one-time signature scheme[C]//4th International Conference on the Theory and Application of Cryptographic Techniques in Africa(Africacrypt 2011).Springer,2011:363-378.
[93]HÜLSING A.W-OTS+-shorter signatures for hash-based signature schemes[C]//Progress in Cryptology-AFRICACRYPT 2013:6th International Conference on Cryptology in Africa.2013:173-188.
[94]REYZIN L,REYZIN N.Better than BiBa:Short one-time signatures with fast signing and verifying[C]//Australasian Confe-rence on Information Security and Privacy.Berlin,2002:144-153.
[95]AUMASSON J P,ENDIGNOUX G.Improving stateless hash-based signatures[C]//Cryptographers' Track at the RSA Conference.Cham:Springer International Publishing,2018:219-242.
[96]BUCHMANN J,DAHMEN E,HÜLSING A.XMSS－a practical forward secure signature scheme based on minimal security assumptions[C]//Post-Quantum Cryptography:4th International Workshop.2011:117-129.
[97]HÜLSING A,RAUSCH L,BUCHMANN J.Optimal parameters for XMSS MT[C]//Security Engineering and Intelligence Informatics:CD-ARES 2013 Workshops:MoCrySEn and SeCIHD.2013:194-208.
[98]BERNSTEIN D J,HOPWOOD D,HÜLSING A,et al.SPHINCS:practical stateless hash-based signatures[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,2015:368-397.
[99]AUMASSON J P,ENDIGNOUX G.Improving stateless hash-based signatures[C]//Cryptographers' Track at the RSA Conference.Cham:Springer International Publishing,2018:219-242.
[100]ZHANG K Y,CUI H R,YU Y.SPHINCS-α:A Compact Stateless Hash-Based Signature Scheme[J/OL].https://eprint.iacr.org/2022/059.pdf.
[101]NIST.FIPS 205(Draft):Stateless hash-based digital signature standard[EB/OL].(2023-08-24)[2023-09-03].https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.205.ipd.pdf.
[102]BUCHMANN J,DAHMEN E,HÜLSING A.XMSS－a practical forward secure signature scheme based on minimal security assumptions[C]//Post-Quantum Cryptography:4th International Workshop.2011:117-129.
[103]HÜLSING A,KUDINOV M,RONEN E,et al.SPHINCS+ C:Compressing SPHINCS+ With(Almost) No Cost[C]//2023 IEEE Symposium on Security and Privacy(SP).IEEE,2023:1435-1453.
[104]JOSEPH D,MISOCZKI R,MANZANO M,et al.Transitioning organizations to post-quantum cryptography[J].Nature,2022,605(7909):237-243.
[105]DUBROVA E,NGO K,GÄRTNER J,et al.Breaking a fifth-order masked implementation of crystals-kyber by copy-paste[C]//Proceedings of the 10th ACM Asia Public-Key Cryptography Workshop.2023:10-20.
[106]CHEN Y L.Quantum Algorithms for Lattice Problems[EB/OL].https://eprint.iacr.org/2024/555.pdf.
[107]LIANG M,LUO Y Y,LIU F M.A survey on quantum-secure symmetric cryptography[J].Journal of Cryptologic Research,2021,8(6):925-947.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed