Quantum Miss-in-the-Middle Attack

Abstract

We apply Simon's algorithm to the miss-in-the-middle technique and propose a quantum algorithm for finding impossible differentials of a general block cipher. We prove that, under certain assumption on the block cipher, the differentials output by the quantum algorithm are key-independent impossible differentials of the block cipher with a overwhelming probability. Moreover, we demonstrate that if the traditional miss-in-the-middle attack works for the block cipher, the proposed quantum algorithm will always work as well. By contrast, the quantum version of miss-in-the-middle technique proposed in this paper to some extent compensates for the disadvantages of traditional miss-in-the-middle technique that the successful probability decreases greatly with the increase of the number of rounds.