Research Status and Development Trend of Post-quantum Symmetric Cryptography

Han SUI; Wenling WU

doi:10.11999/JEIT190667

Volume 42 Issue 2

Feb. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2020 > 42(2): 287-294

Han SUI, Wenling WU. Research Status and Development Trend of Post-quantum Symmetric Cryptography[J]. Journal of Electronics & Information Technology, 2020, 42(2): 287-294. doi: 10.11999/JEIT190667

Citation:

Han SUI, Wenling WU. Research Status and Development Trend of Post-quantum Symmetric Cryptography[J]. Journal of Electronics & Information Technology, 2020, 42(2): 287-294. doi: 10.11999/JEIT190667

Han SUI, Wenling WU. Research Status and Development Trend of Post-quantum Symmetric Cryptography[J]. Journal of Electronics & Information Technology, 2020, 42(2): 287-294. doi: 10.11999/JEIT190667

Citation:

Han SUI, Wenling WU. Research Status and Development Trend of Post-quantum Symmetric Cryptography[J]. Journal of Electronics & Information Technology, 2020, 42(2): 287-294. doi: 10.11999/JEIT190667

PDF( 327 KB)

Research Status and Development Trend of Post-quantum Symmetric Cryptography

doi: 10.11999/JEIT190667

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)

Received Date: 2019-09-02
Rev Recd Date: 2019-10-18

Available Online: 2019-11-18

Publish Date: 2020-02-19

Abstract

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

FullText(HTML)

References(49)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views