Paper 2019/318

Improved quantum attack on Type-1 Generalized Feistel Schemes and Its application to CAST-256

Boyu Ni and Xiaoyang Dong

Abstract

Generalized Feistel Schemes (GFS) are important components of symmetric ciphers, which have been extensively researched in classical setting. However, the security evaluations of GFS in quantum setting are rather scanty. In this paper, we give more improved polynomial-time quantum distinguishers on Type-1 GFS in quantum chosen-plaintext attack (qCPA) setting and quantum chosen-ciphertext attack (qCCA) setting. In qCPA setting, we give new quantum polynomial-time distinguishers on $(3d-3)$-round Type-1 GFS with branches $d\geq3$, which gain $d-2$ more rounds than the previous distinguishers. Hence, we could get better key-recovery attacks, whose time complexities gain a factor of $2^{\frac{(d-2)n}{2}}$. In qCCA setting, we get $(3d-3)$-round quantum distinguishers on Type-1 GFS, which gain $d-1$ more rounds than the previous distinguishers. In addition, we give some quantum attacks on CAST-256 block cipher. We find 12-round and 13-round polynomial-time quantum distinguishers in qCPA and qCCA settings, respectively, while the best previous one is only 7 rounds. Hence, we could derive quantum key-recovery attack on 19-round CAST-256. While the best previous quantum key-recovery attack is on 16 rounds. When comparing our quantum attacks with classical attacks, our result also reaches 16 rounds on CAST-256 with 128-bit key under a competitive complexity.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Generalized Feistel SchemeQuantum attackSimon's algorithmCAST-256
Contact author(s)
xiaoyangdong @ tsinghua edu cn
375828077 @ qq com
History
2019-03-29: received
Short URL
https://ia.cr/2019/318
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/318,
      author = {Boyu Ni and Xiaoyang Dong},
      title = {Improved quantum attack on Type-1 Generalized Feistel Schemes and Its application to {CAST}-256},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/318},
      year = {2019},
      url = {https://eprint.iacr.org/2019/318}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.