SCIENCE CHINA Information Sciences, Volume 61 , Issue 10 : 102501(2018) https://doi.org/10.1007/s11432-017-9468-y

Quantum key-recovery attack on Feistel structures

More info
  • ReceivedDec 12, 2017
  • AcceptedMay 8, 2018
  • PublishedAug 31, 2018



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


[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] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21: 120-126 CrossRef Google Scholar

[3] Even S, Mansour Y. A construction of a cipher from a single pseudorandom permutation. J Cryptology, 1997, 10: 151-161 CrossRef Google Scholar

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

[5] 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

[6] Moody D. The ship has sailed: the NIST post-quantum cryptography “competition” (invited talk). In: Advances in Cryptology-ASIACRYPT 2017. Berlin: Springer, 2017. 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. 361--379. Google Scholar

[8] Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, 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. Proc IEEE, 1975, 63: 1545-1554 CrossRef Google Scholar

[11] International Organization for Standardization (ISO). Information Technology-Security Techniques-Encryption Algorithms-Part 3: Block Ciphers. International Standard-ISO/IEC 18033-3. 2010. https://www.iso.org/standard/54531.html. Google Scholar

[12] Luby M, Rackoff C. How to construct pseudorandom permutations from pseudorandom functions. SIAM J Comput, 1988, 17: 373-386 CrossRef Google Scholar

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

[14] Dinur I, Dunkelman O, Keller N, et al. New attacks on Feistel structures with improved memory complexities. In: Advances in Cryptology - CRYPTO 2015, Part I Berlin: Springer, 2015. 433--454. Google Scholar

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

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

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

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

[19] 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. 57--76. Google Scholar

  • Figure 1

    The $i$th round of the Feistel structure.

  • Figure 2

    FX constructions.

  • Figure 3

    Quantum key-recovery attack on 5-round Feistel structures.

  • Table 1   Summary of the key-recovery attacks on Feistel schemes in classical and qCPA settings
    Classical setting qCPA setting
    Dinur et al. [14] Trivial bound Ours
    Rounds Time Memory Time Time
    5 $2^{n}$ $2^{0.5n}$ $2^{1.25n}$ $2^{0.5n}$
    7 $2^{1.5n}$ $2^{n}$ $2^{1.75n}$ $2^{n}$
    8 $2^{1.75n}$ $2^{1.25n}$ $2^{2n}$ $2^{1.25n}$
    15 $2^{3.5n}$ $2^{2n}$ $2^{3.75n}$ $2^{3n}$
    31 $2^{7.5n}$ $2^{4n}$ $2^{7.75n}$ $2^{7n}$
    32 $2^{7.75n}$ $2^{7.25n}$ $2^{8n}$ $2^{7.25n}$