Paper 2017/1249

Quantum cryptanalysis on some Generalized Feistel Schemes

Xiaoyang Dong, Zheng Li, and Xiaoyun Wang

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 $2^{{\frac{3d^2 n}{2}}}$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. SCIENCE CHINA Information Sciences
Keywords
Quantum cryptanalysis
Contact author(s)
xiaoyangdong @ tsinghua edu cn
History
2018-05-07: last of 4 revisions
2017-12-30: received
See all versions
Short URL
https://ia.cr/2017/1249
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1249,
      author = {Xiaoyang Dong and Zheng Li and Xiaoyun Wang},
      title = {Quantum cryptanalysis on some Generalized Feistel Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1249},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1249}},
      url = {https://eprint.iacr.org/2017/1249}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.