Paper 2018/504

Quantum Attacks on Some Feistel Block Ciphers

Xiaoyang Dong and Bingyou Dong and Xiaoyun Wang

Abstract

Post-quantum cryptography has attracted much attention from worldwide cryptologists. However, most research works are related to public-key cryptosystem due to Shor's attack on RSA and ECC ciphers. At CRYPTO 2016, Kaplan et al. breaks many secret-key (symmetric) systems using quantum period finding algorithm, which arises researcher's attentions to evaluate the symmetric systems against quantum attackers. In this paper, we continue to study the symmetric ciphers against quantum attackers. First, we convert the classical advanced slide attacks (introduced by Biryukov and Wagner) to a quantum one, that gains an exponential speed-up of the time complexity. Thus, we could break 2/4K-Feistel and 2/4K-DES in polynomial time. Second, we give a new quantum key-recovery attack on full-round GOST, a Russian standard, with $2^{112}$ Grover iterations, which is faster than a quantum brute force search attack by a factor $2^{16}$.