SCIENCE CHINA Information Sciences, Volume 62 , Issue 2 : 022501(2019) https://doi.org/10.1007/s11432-017-9436-7

Quantum cryptanalysis on some generalized Feistel schemes

More info
  • ReceivedDec 26, 2017
  • AcceptedApr 9, 2018
  • PublishedJan 2, 2019



This work was supported by National Key Research and Development Program of China (Grant No. 2017YFA0303903), Project Funded by China Postdoctoral Science Foundation (Grant No. 2017M620807), National Cryptography Development Fund (Grant No. MMJJ20170121), Zhejiang Province Key RD Project (Grant No. 2017C01062), National Natural Science Foundation of China (Grant No. 61672019), and Fundamental Research Funds of Shandong University (Grant No. 2016JC029).


[1] Shor P W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J Comput, 1997, 26: 1484-1509 CrossRef Google Scholar

[2] Kuwakado H, Morii M. Security on the quantum-type even-mansour cipher. In: Proceedings of International Symposium on Information Theory and Its Applications, 2012. 312--316. Google Scholar

[3] Kuwakado H, Morii M. Quantum distinguisher between the 3-round feistel cipher and the random permutation. In: Proceedings of International Symposium on Information Theory, 2010. 2682--2685. Google Scholar

[4] Kaplan M, Leurent G, Leverrier A, et al. Breaking symmetric cryptosystems using quantum period finding. In: Advances in Cryptology - CRYPTO 2016. Berlin: Springer-Verlag, 2016. 207--237. Google Scholar

[5] Leander G, May A. Grover meets simon - quantumly attacking the FX-construction. In: Advances in Cryptology - ASIACRYPT 2017, Part II Berlin: Springer, 2017. 10625: 161--178. Google Scholar

[6] Takagi T, Peyrin T. In: Advances in Cryptology - ASIACRYPT 2017, Part I. Berlin: Springer, 2017. 10624: 1--813. Google Scholar

[7] Boneh D, Zhandry M. Secure signatures and chosen ciphertext security in a quantum computing world. In: Advances in Cryptology - CRYPTO 2013. Berlin: Springer, 2013. 8043: 361--379. Google Scholar

[8] Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of STOC 1996. 1996. 212--219. Google Scholar

[9] Simon D R. On the Power of Quantum Computation. SIAM J Comput, 1997, 26: 1474-1483 CrossRef Google Scholar

[10] Feistel H, Notz W A, Smith J L. Some cryptographic techniques for machine-to-machine data communications. In: Proceedings of the IEEE 1975. 63: 1545--1554. Google Scholar

[11] International Organization for Standardization(ISO) International Standard- ISO/IEC 18033-3, Information technology-Security techniques-Encryption algorithms -Part 3: Block ciphers 2010. Google Scholar

[12] Zheng Y L, Matsumoto T, Imai H. On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses In: Advances in Cryptology - CRYPTO 1989. New York: Springer-Verlag, 1989. 435: 461--480. Google Scholar

[13] Moriai S, Vaudenay S. On the pseudorandomness of top-level schemes of block ciphers In: Advances in Cryptology - ASIACRYPT 2000. Berlin: Springer, 2000. 1976: 289--302. Google Scholar

[14] Luby M, Rackoff C. How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM J Comput, 1988, 17: 373-386 CrossRef Google Scholar

[15] Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation,. arXiv Google Scholar

[16] Borghoff J, Canteaut A, Güneysu T, Kavun E B, et al. PRINCE - a low-latency block cipher for pervasive computing applications - extended abstract. In: Advances in Cryptology - ASIACRYPT 2012. Berlin: Springer-Verlag, 2009. 7658: 208--225. Google Scholar

[17] Albrecht M R, Driessen B, Kavun E B, et al. Block ciphers - focus on the linear layer (feat. PRIDE). In: Advances in Cryptology - CRYPTO 2014. Berlin: Springer, 2014. 8616: 57--76. Google Scholar

[18] Kilian J, Rogaway P. How to protect DES against exhaustive key search. In: Advances in Cryptology - CRYPTO 1996. Berlin: Springer-Verlag, 1996. 1109: 252--267. Google Scholar

[19] Dong X, Wang X. Quantum key-recovery attack on Feistel structures. Sci China Inf Sci, 2018, 61: 102501 CrossRef Google Scholar

[20] Hosoyamada A, Sasaki Y. Quantum meet-in-the-middle attacks: Applications to generic feistel constructions. In: Proceedings of International Conference on Security and Cryptography for Networks, 2018. 386--403. Google Scholar

[21] Zhang L T, Wu W L. Pseudorandomness and super pseudorandomness on the unbalanced feistel networks with contracting functions. Chin J Comput, 2009, 32: 1320-1330 CrossRef Google Scholar