后量子對(duì)稱密碼的研究現(xiàn)狀與發(fā)展趨勢(shì)
doi: 10.11999/JEIT190667
-
1.
中國(guó)科學(xué)院軟件研究所計(jì)算機(jī)科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室可信計(jì)算與信息保障實(shí)驗(yàn)室 北京 100190
-
2.
密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100878
基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61672509)
Research Status and Development Trend of Post-quantum Symmetric Cryptography
-
1.
TCA Laboratory, SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China
-
2.
State Key Laboratory of Cryptology, Beijing 100878, China
Funds: The National Natural Science Foundation of China(61672509)
-
摘要: 經(jīng)典對(duì)稱密碼算法的安全性在量子環(huán)境下面臨嚴(yán)峻的挑戰(zhàn),促使研究者們開(kāi)始探尋在經(jīng)典和量子環(huán)境下均具有安全性的密碼算法,后量子對(duì)稱密碼研究應(yīng)運(yùn)而生。該領(lǐng)域的研究目前仍處于初級(jí)階段,尚未形成完整的體系。該文對(duì)現(xiàn)有的研究成果進(jìn)行歸類,從量子算法、密碼分析方法、安全性分析、可證明安全4個(gè)方面對(duì)后量子對(duì)稱密碼領(lǐng)域的研究現(xiàn)狀進(jìn)行介紹。在分析研究現(xiàn)狀的基礎(chǔ)上,對(duì)后量子對(duì)稱密碼的發(fā)展趨勢(shì)進(jìn)行預(yù)測(cè),為對(duì)稱密碼在量子環(huán)境下的分析和設(shè)計(jì)提供參考。Abstract: The security of classical symmetric cryptography is facing severe challenges in quantum environment, which has prompted researchers to explore cryptography algorithms that are secure in both classical and quantum environments. Post-quantum symmetric cryptography research emerges. Research in this field is still at its primary stage and has not formed a complete system. This paper categorizes the existing research results, and introduces the research status from four aspects, including quantum algorithm, cryptographic analysis method, security analysis, provable security. Based on the analysis of the research status, the development trend of post-quantum symmetric cryptography is predicted, which provides reference for the analysis and design of symmetric cryptography in quantum environment.
-
Key words:
- Symmetric cryptography /
- Quantum algorithm /
- Post-quantum /
- Cryptanalysis /
- Provable security
-
FEYNMAN R P. Simulating physics with computers[J]. International Journal of Theoretical Physics, 1982, 21(6/7): 467–488. DEUTSCH D. Quantum theory, the Church-Turing principle and the universal quantum computer[J]. Proceedings of the Royal Society A Mathematical, Physical and Engineering Sciences, 1985, 400(1818): 97–117. doi: 10.1098/rspa.1985.0070 SHOR P W. Algorithms for quantum computation: Discrete logarithms and factoring[C]. The 35th Annual Symposium on Foundations of Computer Science, Santa Fe, USA, 1994: 124–134. SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484–1509. doi: 10.1137/S0097539795293172 GROVER L K. A fast quantum mechanical algorithm for database search[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 212–219. KUWAKADO H and MORII M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation[C]. 2010 IEEE International Symposium on Information Theory, Austin, USA, 2010: 2682–2685. KUWAKADO H and MORII M. Security on the quantum-type Even-Mansour cipher[C]. 2012 International Symposium on Information Theory and Its Applications, Honolulu, USA, 2012: 312–316. KAPLAN M, LEURENT G, LEVERRIER A, et al. Breaking symmetric cryptosystems using quantum period finding[J]. arXiv: 1602.05973, 2016. SIMON D R. On the power of quantum computation[C]. The 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994: 116–123. BRASSARD G and HOYER P. An exact quantum polynomial-time algorithm for Simon's problem[C]. The Fifth Israeli Symposium on Theory of Computing and Systems, Ramat-Gan, Israel, 1997: 12–23. LONG Guilu. Grover algorithm with zero theoretical failure rate[J]. Physical Review A, 2001, 64(2): 022307. doi: 10.1103/PhysRevA.64.022307 TOYAMA F M, VAN DIJK W, and NOGAMI Y. Quantum search with certainty based on modified Grover algorithms: Optimum choice of parameters[J]. Quantum Information Processing, 2013, 12(5): 1897–1914. doi: 10.1007/s11128-012-0498-0 LEANDER G and MAY A. Grover meets Simon - Quantumly attacking the FX-construction[C]. Proceedings of the 23rd International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, 2017: 161–178. BRASSARD G, H?YER P, and TAPP A. Quantum cryptanalysis of hash and claw-free functions[C]. Theoretical Informatics: Third Latin American Symposium, Campinas, Brazil, 1998: 163–169. AMBAINIS A. Quantum walk algorithm for element distinctness[J]. SIAM Journal on Computing, 2007, 37(1): 210–239. doi: 10.1137/S0097539705447311 AARONSON S and SHI Yaoyun. Quantum lower bounds for the collision and the element distinctness problems[J]. Journal of the ACM, 2004, 51(4): 595–605. doi: 10.1145/1008731.1008735 AMBAINIS A. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range[J]. Theory of Computing-An Open Access Electronic Journal in Theoretical Computer Science, 2005, 1(1): 37–46. KUTIN S. Quantum lower bound for the collision problem with small range[J]. Theory of Computing-An Open Access Electronic Journal in Theoretical Computer Science, 2005, 1(1): 29–36. YUEN H. A quantum lower bound for distinguishing random functions from random permutations[J]. Quantum Information & Computation, 2014, 14(13/14): 1089–1097. ZHANDRY M. A note on the quantum collision and set equality problems[J]. Quantum Information & Computation, 2015, 15(7/8): 557–567. HOSOYAMADA A, SASAKI Y, and XAGAWA K. Quantum multicollision-finding algorithm[C]. The 23rd International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, 2017: 179–210. LIU Qipeng and ZHANDRY M. On finding quantum multi-collisions[C]. The 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, 2019: 189–218. GRASSL M, LANGENBERG B, ROETTELER M, et al. Applying Grover's algorithm to AES: Quantum resource estimates[J]. arXiv: 1512.04965, 2015. FOWLER A G, DEVITT S J, and JONES C. Surface code implementation of block code state distillation[J]. Scientific Reports, 2013, 3(1): 1939. doi: 10.1038/srep01939 FOWLER A G and DEVITT S J. A bridge to lower overhead quantum computation[J]. arXiv: 1209.0510, 2012. DEVITT S J, STEPHENS A M, MUNRO W J, et al. Requirements for fault-tolerant factoring on an atom-optics quantum computer[J]. Nature Communications, 2013, 4(1): 2524. doi: 10.1038/ncomms3524 CHAILLOUX A, NAYA-PLASENCIA M, SCHROTTENLOHER A, et al. An efficient quantum collision search algorithm and implications on symmetric cryptography[C]. The 23rd International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, 2017: 211–240. BERNSTEIN E and VAZIRANI U. Quantum complexity theory[C]. The 28th Annual ACM Symposium on Theory of Computing, San Diego, USA, 1993: 11–20. LI Hongwei and YANG Li. Quantum differential cryptanalysis to the block ciphers[C]. The 6th International Conference on Applications and Techniques in Information Security, Beijing, China, 2015: 44–51. XIE Huiqin and YANG Li. Quantum impossible differential and truncated differential cryptanalysis[J]. arXiv: 1712.06997, 2017. XIE Huiqin and YANG Li. Using Bernstein-Vazirani algorithm to attack block ciphers[J]. Designs, Codes and Cryptography, 2019, 87(5): 1161–1182. doi: 10.1007/s10623-018-0510-5 ZHOU Qing, LU Songfeng, ZHANG Zhigang, et al. Quantum differential cryptanalysis[J]. Quantum Information Processing, 2015, 14(6): 2101–2109. doi: 10.1007/s11128-015-0983-3 KAPLAN M, LEURENT G, LEVERRIER A, et al. Quantum differential and linear cryptanalysis[J]. arXiv: 1510.05836, 2015. CHEN Yuao and GAO Xiaoshan. Quantum algorithms for Boolean equation solving and quantum algebraic attack on cryptosystems[J]. arXiv: 1712.06239, 2017. BONNETAIN X, NAYA-PLASENCIA M, SCHROTTENLOHER A, et al. On quantum slide attacks[R]. 2018/1067, 2018. DONG Xiaoyang, DONG Bingyou, WANG Xiaoyun, et al. Quantum attacks on some Feistel block ciphers[R]. 2018/504, 2018. MONTANARO A. Quantum search with advice[C]. The 5th Conference on Theory of Quantum Computation, Communication, and Cryptography, Leeds, UK, 2010: 77–93. MARTIN D, MONTANARO A, and OSWALD E. Quantum key search with side channel advice[C]. The 24th International Conference on Selected Areas in Cryptography, Ottawa, Canada, 2017: 407–422. DONG Xiaoyang and WANG Xiaoyun. Quantum key-recovery attack on Feistel structures[J]. Science China Information Sciences, 2018, 61(10): 102501. doi: 10.1007/s11432-017-9468-y ITO G, HOSOYAMADA A, MATSUMOTO R, et al. Quantum chosen-ciphertext attacks against feistel ciphers[C]. The Cryptographers’ Track at the RSA Conference, San Francisco, USA, 2019: 391–411. HOSOYAMADA A and SASAKI Y. Quantum Demiric-Sel?uk meet-in-the-middle attacks: Applications to 6-round generic feistel constructions[C]. The 11th International Conference on Security and Cryptography, Amalfi, Italy, 2018: 386–403. DONG Xiaoyang, LI Zheng, WANG Xiaoyun, et al. Quantum cryptanalysis on some generalized Feistel schemes[J]. Science China Information Sciences, 2019, 62(2): 22501. doi: 10.1007/s11432-017-9436-7 HOSOYAMADA A and AOKI K. On quantum related-key attacks on iterated Even-Mansour ciphers[C]. The 12th International Workshop on Security, Hiroshima, Japan, 2017: 3–18. BONNETAIN X. Quantum key-recovery on full AEZ[C]. The 24th International Conference on Selected Areas in Cryptography, Ottawa, Canada, 2018: 394–406. BONEH D, DAGDELEN ?, FISCHLIN M, et al. Random oracles in a quantum world[C]. The 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 2011: 41–69. ZHANDRY M. How to construct quantum random functions[C]. The 53rd Annual Symposium on Foundations of Computer Science, New Brunswick, USA, 2012: 679–687. SONG Fang and YUN A. Quantum security of NMAC and related constructions[C]. The 37th International Cryptology Conference, Santa Barbara, USA, 2017: 283–309. HOSOYAMADA A and YASUDA K. Building quantum-one-way functions from block ciphers: Davies-Meyer and Merkle-Damg?rd constructions[C]. The 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia, 2018: 275–304. ZHANDRY M. How to record quantum queries, and applications to quantum indifferentiability[C]. The 39th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2019: 239–268. -
計(jì)量
- 文章訪問(wèn)數(shù): 3454
- HTML全文瀏覽量: 1594
- PDF下載量: 350
- 被引次數(shù): 0