Paper 2017/1229

Quantum Demiric-Selçuk Meet-in-the-Middle Attacks: Applications to 6-Round Generic Feistel Constructions

Akinori Hosoyamada and Yu Sasaki

Abstract

This paper shows that quantum computers can significantly speed-up a type of meet-in-the-middle attacks initiated by Demiric and Selçuk (DS-MITM attacks), which is currently one of the most powerful cryptanalytic approaches in the classical setting against symmetric-key schemes. The quantum DS-MITM attacks are demonstrated against 6 rounds of the generic Feistel construction supporting an $n$-bit key and an $n$-bit block, which was attacked by Guo et al. in the classical setting with data, time, and memory complexities of $O(2^{3n/4})$. The complexities of our quantum attacks depend on the adversary's model and the number of qubits available. When the adversary has an access to quantum computers for offline computations but online queries are made in a classical manner (so called Q1 model), the attack complexities are $O(2^{n/2})$ classical queries, $O(2^n/q)$ quantum computations by using about $q$ qubits. Those are balanced at $\tilde{O}(2^{n/2})$, which significantly improves the classical attack. Technically, we convert the quantum claw finding algorithm to be suitable in the Q1 model. The attack is then extended to the case that the adversary can make superposition queries (so called Q2 model). The attack approach is drastically changed from the one in the Q1 model; the attack is based on 3-round distinguishers with Simon's algorithm and then appends 3 rounds for key recovery. This can be solved by applying the combination of Simon's and Grover's algorithms recently proposed by Leander and May.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. SCN 2018
Keywords
post-quantum cryptographyDemiric-Selçuk meet-in-the-middle attackFeistel networkGrover's algorithmclaw finding algorithmclassical query model
Contact author(s)
hosoyamada akinori @ lab ntt co jp
History
2018-06-21: last of 3 revisions
2017-12-22: received
See all versions
Short URL
https://ia.cr/2017/1229
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1229,
      author = {Akinori Hosoyamada and Yu Sasaki},
      title = {Quantum Demiric-Selçuk Meet-in-the-Middle Attacks: Applications to 6-Round Generic Feistel Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1229},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1229}},
      url = {https://eprint.iacr.org/2017/1229}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.