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

Question

We all know and love the meet-in-the-middle attack, which basically makes double encryption pointless using a time-memory trade-off. Now, the NSA recently recommended to use double encryption to adequately protect sensitive data from quantum attackers.

This made me ask myself:
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 trade-off and a quantum computer?

Answer 1

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

Answer 2

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?).