Paper 2018/504

Quantum Attacks on Some Feistel Block Ciphers

Xiaoyang Dong, 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. 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}$.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Designs, Codes and Cryptography
DOI
10.1007/s10623-020-00741-y
Keywords
Quantum cryptanalysisGOSTFeistelGroverSimon
Contact author(s)
xiaoyangdong @ tsinghua edu cn
History
2020-03-01: revised
2018-05-26: received
See all versions
Short URL
https://ia.cr/2018/504
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/504,
      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},
      url = {https://eprint.iacr.org/2018/504}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.