Attacking AES-128 with Grover's algorithm

Question

How many plain text / cipher text pairs are required by Grover's algorithm when it is used to try and discover a secret AES key?

I am trying to determine if having a device which limits the speed at which it produces cipher texts from plain texts will help protect against this attack.

Answer 1

Grover's algorithm is a brute-force quantum algorithm with complexity $\mathcal{O}(\sqrt{N})$ with asymptotically optimal on unstructured data. There is also "Quantum Computing and Hidden Variables" in $\mathcal{O}(\sqrt[3]{N})$ by Aaronson.

Ensuring uniqueness of the solution

Requires ECB mode;

Let $n$ denotes the block size.

Let $r$ be the number of different plaintext-ciphertext pairs.

Let $r$ denotes the number of the simultaneous plaintext-ciphertext pairs encrypted under two secret keys $k_1 \neq k_2$.

Then the expected result of having a different result if the $r$ plaintext are different;

$$ 1- \frac{1}{2^{rn}}$$

A good estimate on $r$ is given as;

$$r > \lceil 2^k/n \rceil$$

For AES-128

$n=128, k=128 \Rightarrow r=3$

For AES-192

$n=128, k=192 \Rightarrow r=4$

For AES-256

$n=128, k=256 \Rightarrow r=5$

for more details, see "Applying Grover’s algorithm to AES: quantum resource estimates" at #3.1

Answer 2

Grover's algorithm has search complexity $\sqrt{2^{128}}$ for AES 128. In plain ECB mode, one plaintext/ciphertext pair will be enough since the cipher mapping is a permutation.

Interestingly very recently a combination of Grover's algorithm and Simon's algorithm have been used to:

Convert the classical advanced slide attacks (introduced by Biryukov and Wagner) to a quantum one, that gains an exponential speed-up of the time complexity.

The authors of the quoted paper include Xiaoyun Wang who came up with the best attacks on MD5 and earlier versions of SHA.

Specifically, they extend quantum slide attacks to Feistel Ciphers.

Edit:

For an $n$ bit block cipher with $n$ bit keys the original slide attack has $O(2^{n/2})$ complexity and requires as many plaintext/ciphertext pairs.

The attakcs by Kaplan et al. cited in the above paper require $O(n)$ complexity but those need to be modified for Feistel ciphers according to the paper quoted above.