Paper 2017/1249
Quantum cryptanalysis on some Generalized Feistel Schemes
Xiaoyang Dong, Zheng Li, and Xiaoyun Wang
Abstract
Postquantum cryptography has attracted much attention from worldwide cryptologists. In ISIT 2010, Kuwakado and Morii gave a quantum distinguisher with polynomial time against 3round 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 Type1 GFS (CAST256like Feistel structure), we introduce ($2d1$)round quantum distinguishers with polynomial time. For $2d$branch Type2 GFS (RC6/CLEFIAlike Feistel structure), we give ($2d+1$)round quantum distinguishers with polynomial time. Classically, Moriai and Vaudenay proved that a 7round $4$branch Type1 GFS and 5round $4$branch Type2 GFS are secure pseudorandom permutations. Obviously, they are no longer secure in quantum setting. Using the above quantum distinguishers, we introduce generic quantum keyrecovery 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^2d+2)$round Type1 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 Type2 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)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Minor revision. SCIENCE CHINA Information Sciences
 Keywords
 Quantum cryptanalysis
 Contact author(s)
 xiaoyangdong @ tsinghua edu cn
 History
 20180507: last of 4 revisions
 20171230: received
 See all versions
 Short URL
 https://ia.cr/2017/1249
 License

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} }