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