后量子对称密码的研究现状与发展趋势

眭晗; 吴文玲

doi:10.11999/JEIT190667

后量子对称密码的研究现状与发展趋势

doi: 10.11999/JEIT190667

眭晗^{1, 2, ,},
吴文玲¹

1.
中国科学院软件研究所计算机科学国家重点实验室可信计算与信息保障实验室北京 100190
2.
密码科学技术国家重点实验室北京 100878

基金项目: 国家自然科学基金(61672509)

详细信息

作者简介:
眭晗：女，1986年生，助理研究员，研究方向为可证明安全理论、认证加密算法的设计与分析

吴文玲：女，1966年生，研究员，博士生导师，主要研究方向为对称密码的设计与分析

通讯作者:
眭晗　suihan@tca.iscas.ac.cn

中图分类号: TN918.1
计量
- 文章访问数: 3119
- HTML全文浏览量: 1444
- PDF下载量: 332
- 被引次数: 0
出版历程
- 收稿日期: 2019-09-02
- 修回日期: 2019-10-18
- 网络出版日期: 2019-11-18
- 刊出日期: 2020-02-19

Research Status and Development Trend of Post-quantum Symmetric Cryptography

Han SUI^{1, 2
, ,},
Wenling WU¹

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)

摘要

摘要: 经典对称密码算法的安全性在量子环境下面临严峻的挑战，促使研究者们开始探寻在经典和量子环境下均具有安全性的密码算法，后量子对称密码研究应运而生。该领域的研究目前仍处于初级阶段，尚未形成完整的体系。该文对现有的研究成果进行归类，从量子算法、密码分析方法、安全性分析、可证明安全4个方面对后量子对称密码领域的研究现状进行介绍。在分析研究现状的基础上，对后量子对称密码的发展趋势进行预测，为对称密码在量子环境下的分析和设计提供参考。
- 对称密码 /
- 量子算法 /
- 后量子 /
- 密码分析 /
- 可证明安全
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.
- Symmetric cryptography /
- Quantum algorithm /
- Post-quantum /
- Cryptanalysis /
- Provable security

HTML全文

参考文献(49)

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.

施引文献

资源附件(0)

访问统计