logo

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

Abstract

Post-quantum cryptography has attracted much attention from worldwide cryptologists.In ISIT 2010, Kuwakado and Morii gave a quantum distinguisher with polynomial time against 3-round Feistel networks. However, generalized Feistel schemes (GFS) have not been systematically investigated against quantum attacks.In this paper, we study the quantum distinguishers about some generalized Feistel schemes. For $d$-branch Type-1 GFS (CAST256-like Feistel structure), we introduce ($2d-1$)-round quantum distinguishers with polynomial time. For $2d$-branch Type-2 GFS (RC6/CLEFIA-like Feistel structure), we give ($2d+1$)-round quantum distinguishers with polynomial time. Classically, Moriai and Vaudenay proved that a 7-round $4$-branch Type-1 GFS and 5-round $4$-branch Type-2 GFS are secure pseudo-random permutations. Obviously, they are no longer secure in quantum setting.Using the above quantum distinguishers, we introduce generic quantum key-recovery attacks by applying the combination of Simon's and Grover's algorithms recently proposed by Leander and May. We denote $n$ as the bit length of a branch. For $(d^2-d+2)$-round Type-1 GFS with $d$ branches, the time complexity is $2^{(\frac{1}{2}d^2-\frac{3}{2}d+2)\cdot~\frac{n}{2}}$, which is better than the quantum brute force search (Grover search) by a factor $2^{(\frac{1}{4}d^2+\frac{1}{4}d)n}$. For $4d$-round Type-2 GFS with $2d$ branches, the time complexity is $2^{{\frac{d^2~n}{2}}}$, which is better than the quantum brute force search by a factor łinebreak $2^{{\frac{3d^2~n}{2}}}$.


Acknowledgment

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).


References

[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

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号