2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ If you want to foil Grover's, just use 256 bit AES keys $\endgroup$ – poncho Oct 12 '18 at 22:21
  • $\begingroup$ @poncho due to $\sqrt{}$ ? $\endgroup$ – kelalaka Oct 13 '18 at 11:27
  • 1
    $\begingroup$ @kelalaka Correct. $\endgroup$ – bkjvbx Oct 13 '18 at 17:52
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "one plaintext/ciphertext pair will be enough since the cipher mapping is a permutation" There will be many permutations that have the same mapping, right? This part is the only part of the post that is actually answering the question, or am I mistaken? $\endgroup$ – Maarten Bodewes Oct 14 '18 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.