Paper 2024/458
Classical and Quantum Generic Attacks on 6-round Feistel Schemes
Abstract
In this paper, we describe new quantum generic attacks on 6 rounds balanced Feistel networks with internal functions or internal permutations. In order to obtain our new quantum attacks, we revisit a result of Childs and Eisenberg that extends Ambainis' collision finding algorithm to the subset finding problem. In more details, we continue their work by carefully analyzing the time complexity of their algorithm. We also use four points structures attacks instead of two points structures attacks that leads to a complexity of $\mathcal{O}(2^{8n/5})$ instead of $\mathcal{O}(2^{2n})$. Moreover, we have also found a classical (i.e. non quantum) improved attack on $6$ rounds with internal permutations. The complexity here will be in $\mathcal{O}(2^{2n})$ instead of $\mathcal{O}(2^{3n})$ previously known.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Feistel ciphersPseudo-random permutationQuantum cryptanalysisLuby–Rackoff block cipherSubset finding problem
- Contact author(s)
-
maya saab-chartouni @ thalesgroup com
benoit-michel cogliati @ thalesgroup com
jacques patarin @ thalesgroup com - History
- 2024-03-22: approved
- 2024-03-18: received
- See all versions
- Short URL
- https://ia.cr/2024/458
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/458,
author = {Maya Chartouny and Benoit Cogliati and Jacques Patarin},
title = {Classical and Quantum Generic Attacks on 6-round Feistel Schemes},
howpublished = {Cryptology ePrint Archive, Paper 2024/458},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/458}},
url = {https://eprint.iacr.org/2024/458}
}
