Paper 2018/504

Quantum Attacks on Some Feistel Block Ciphers

Xiaoyang Dong, Bingyou Dong, and Xiaoyun Wang


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. showed that many secret-key (symmetric) systems could be broken using a quantum period finding algorithm, which encouraged researchers to evaluate symmetric systems against quantum attackers. In this paper, we continue to study 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 in 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, which is a Russian standard, with $2^{114.8}$ quantum queries of the encryption process, faster than a quantum brute-force search attack by a factor of $2^{13.2}$.

Available format(s)
Publication info
Published elsewhere. Designs, Codes and Cryptography
Quantum cryptanalysisGOSTFeistelGroverSimon
Contact author(s)
xiaoyangdong @ tsinghua edu cn
2020-03-01: revised
2018-05-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaoyang Dong and Bingyou Dong and Xiaoyun Wang},
      title = {Quantum Attacks on Some Feistel Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2018/504},
      year = {2018},
      doi = {10.1007/s10623-020-00741-y},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.