Welcome to the resource topic for 2017/1249
Title:
Quantum cryptanalysis on some Generalized Feistel Schemes
Authors: Xiaoyang Dong, Zheng Li, 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}}}.
ePrint: https://eprint.iacr.org/2017/1249
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .