# Can Grover's Algorithm be combined with a meet-in-the-middle attack?

We all know and love the meet-in-the-middle attack which basically makes double encryption pointless using a time-memory-tradeoff. Now there was recently the recommendation by the NSA to use double encryption to protect sensitive data adequately from quantum attackers.

Can one combine Grover's algorithm with the mitm attack to make double encryption "pointless" in the quantum setting?

Example:
The classical strength of double AES-256 encryption is 257-bits and $2^{256}$ storage. Using Grover's algorithm to attack the full cipher would take $2^{256}$ time. Can this time be reduced using a mitm tradeoff and a quantum computer?

• – CodesInChaos Oct 25 '15 at 20:30

The combination of Grover algorithm and man in the middle attack is the main subject of a paper (arXiv:1410.1434) published last year by Marc Kaplan (Full disclosure: Marc is a friend of mine.)

In this paper beyond applying Grover to MITM to reduce the time needed to analyse double-encryption, he also looks at the time-space gain, which is different, and quadruple encryption.

From the conclusion:

Equipped with a quantum computer, an attacker can run a quantum algorithm for collision finding. We have proven that this approach leads to optimal time complexity for extracting keys, making crucial use of the generalized adversary method, a tool from quantum complexity theory. Extracting a pair of keys $(k_1, k_2)$ takes time $N^{2/3}$, where $N$ is the size of the key space of a single encryption

You could be able to reduce the space required for a meet-in-the-middle attack, if you follow a similar idea as the application of Grover's algorithm on collisions. Suppose you have two layers of $n$-bit encryption:

1. Partition the inner keyspace into $2^{n/4}$ parts of size $2^{3n/4}$.
2. For each partition generate the inner encryption table.
3. Run Grover's on the outer keyspace in $O(2^{n/2})$ time.
4. If you find the preimage in the table, you found both keys, otherwise return to 2.

You would get $O(2^{n})$ time and $O(2^{3n/4})$ storage, which is better than classical meet-in-the-middle and requires less quantum computations, $O(2^{3n/4})$, than just using Grover's on the whole combined keyspace in $O(2^{n})$ time.

The problem of the size of the quantum computer would probably apply (maybe $O(2^{3n/4})$ qubits here?).