Does Grover's algorithm really threaten symmetric security proofs?

Question

By Shannon's theorem of perfect security, if I give you a ciphertext 'LOUPL', you can do a brute-force attack and then you would find plaintexts like 'HELLO', 'APPLE', 'SPOON', but you can't distinguish the true plaintext from the fake one, unless with a probability in 1 of 23⁵. That's a theoretical information security warranty.

For example, the Rogaway's XEX construction has a pure TI query complexity bound of $O \left( \frac{4.5q²}{2^n} \right)$ for any CCA-adversaries with infinite computational power. I truly don't understand why a weak assumption, like having a finite amount of quantum computers, compromises this security.

I know that in asymmetric cryptography you can recover plaintext with a single query and applying brute force to it, because the security is due to its computational complexity, not to information leakage.

How does the algorithm reduce the security bounds in Information Theoretic Analysis?

Answer 1

Despite the classical security proof, Grover's algorithm threatens symmetric key cryptography. The main reason is that classical security proof assumes that the adversary makes classical queries to the primitives, while Grover's algorithm or other quantum algorithms make quantum queries to the primitives. This makes the model of quantum adversaries different from the classical adversaries.

Let me give a concrete example explaining this difference more vividly. Sample $z \in [N]$ uniformly at random, and define $$ F(x)=\begin{cases} 0 &\text{ if }x\neq z\\ 1 &\text{ if }x=z \end{cases} $$ as usual in Grover's algorithm. The goal is to find $z$ by accessing the oracle that computes $F$.

For any algorithm that makes classical queries to the oracle, meaning that whenever it accesses $F$ it gives a classical string $x$ and receives $F(x)$, it is not that hard to prove that after $q$ oracle queries, it can find $z$ with probability at most $O\left(\frac{q}{N}\right)$. This bound holds even for the computationally unbounded algorithms, as long as it makes $q$ queries.

On the other hand, Grover's algorithm finds $z$ only using $\sqrt{N}$ queries! This is not a contradiction; Grover's algorithm makes the quantum query $$ \sum_{x\in[N],b\in\{0,1\}} \alpha_{x,b} |x,b\rangle \mapsto\sum_{x\in[N],b\in\{0,1\}} \alpha_{x,b} |x,b \oplus F(x)\rangle, $$ which is not captured by the classical queries I described above.

Answer 2

Yes, but also no. Grover's algorithm is actually quadratically faster than classical algorithms. However there are a few catches.

1. Quantum computers are slow and expensive. This means that in the near term at least, they are likely only useful in cases where they provide exponential improvement.
2. Grover's algorithm doesn't parallelize like a normal algorithm. Regular search algorithms parallelize trivially. Divide your search space into 10000 and you can easily use 10000 computers to search 1000x as fast. With Grover you can't divide your search space so 10000 computers only gives you a 100x speedup.
3. Quadratic speedup isn't very much. Even with Grover's algorithm, it's still exponentially easier to decrypt than to crack. By doubling the keysize once, you've negated the quantum advantage (this typically means going from 128 bit encryption to 256 bit encryption which lots of software already uses).

Answer 3

Does Grover's algorithm really threaten symmetric cryptography?

Lov K. Grover's algorithm reduces the key search into $\mathcal{O}(\sqrt{2^n})$ instead of the $\mathcal{O}(2^n)$. What is generally not mentioned is the number of successive evaluations; it is $\mathcal{O}(\sqrt{2^n})$, too. What do we know about the successive calls? Almost nothing since nothing was built yet. We can only estimate it even with some good numbers like assuming that one can prepare-and-run the Gover machine in one nanosecond. Then for AES-128 (or any block cipher with 128-bit key), it will take $\approx 585$ years.

	AES-128	AES-192	AES-256
complexity	$2^{64}$	$2^{96}$	$2^{128}$
evaluations (circa)	$2^{64}$	$2^{96}$	$2^{128}$
approx-time	$\approx 583$ years	$\approx 583\cdot 2^{32}$ years	$\approx 583\cdot 2^{64}$ years

Grover's algorithm also can be parallelized, the gain, however, is not quadratic speed up as one expected. For running $k$ machine one gets $\sqrt{k}$ speed ups. Therefore if one runs $10^6$ Grover's machine in parallel they can break AES-128 for less than one year. We cannot do more on the Grover's algorithm since, it is also proven that Grover's algorithm is asymptotically optimal, $\Omega(\sqrt{2^n})$

So as of current, it is not easy to call AES-128 is not quantum-safe. The practical problems that scientists and engineers are working on must be solved to break AES-128 in a meaningful time. In the end, we expect that it will be broken, actually, any block cipher with a 128-bit key is broken, and there is nothing specific to AES.

On the other hand, AES-128 has other major problems than Grover's algorithm; multi-target, or small block size for proper random IV guarantees for GCM.

Is AES-256 (or any block cipher with 256-bit key) a post-quantum secure cipher or not?

It is and it will be always secure. Therefore AES-256 is the golden standard in the industry with only 40% performance penalty when compared to AES-128. Always use AES-256 with a good mode of operation for your target security.

This is also the reason that we don't have a Post-Quantum call for new symmetric encryption algorithms from NITS PQC like for Cryptographic Hash functions.

That explains why we are using 256-bit keys to encrypt top secrets. But latest practical attack on AES shows brute-forcing AES-256 take $2^{100}$ operations.

This attack is a related-key attack and not practical in the sense of what is done to RC4 with related-key attack.

This is also misleading since the attack requires $2^{99.5}$-time and $2^{99.5}$-data complexity. Though the collective Bitcoin Miners can reach $\approx 2^{93}$ SHA-256d in a year, they don't store the data. This is the major problem of the attack. Since we cannot store this amount in memory, we have to consider the bottleneck of the data access, too.

As a practice matter, one selects the AES key either

• uniform randomly
• as a result of a key exchange like DHKE, then a cryptographic hash function is applied, or
• form a password with a password-based key derivation function like PBKDF2, Scrypt, and Argon2.

The attacker has no means to control the selected key. And, it will be very surprising that any of these can aid the related-key attacker. We can say this is not a key recovery attack.

---

As a conclusion: use AES-256 or ChaCha20 with a proper mode of operation to be safe from The Grover machine.

Answer 4

I'm going to answer the question in your headline and then go forward.

No. Grover's algorithm is a canard and you ought to stop worrying about it.

The major reason for this is that Grover reduces the space to the square root of the space. In plain terms, it means that it halves the number of bits in the key space. So Grover can solve AES-128 in 2^64 operations as opposed to a search of 2^128. Thus, the obvious mitigation is to use AES-256, which Grover can solve in 2^128 operations and that's just not feasible. Poof, you're done, upgrade to 256-bit symmetric crypto. Bob's your uncle and Alice is your auntie.

But wait -- there's more. One of the things that is more is that while Grover can reduce the search space to 2^64, you still have to search it and it's not clear that 2^64 quantum operations are any more practical than 2^128 classical ones, for real things like it not being clear that there's enough stuff in the universe (matter, space, and time) to be able to do it.

If I may digress, there's an O(1) way to solve AES that is much faster than Grover. You just precompute all possible AES operations into a big table and just look it up. Poof, you're done. Alice is your auntie. And yeah -- you can't fit that in the universe so while it's O(1), you can't actually do it. There's a lot of evidence that Grover is similarly just not going to work for real-world constraints on search spaces as large as 2^64.

And of course, as we started with, if we just use a 256-bit cipher, Grover isn't going to work at all. (By the way, I'm one of the creators of Threefish, which has 512-bit and 1024-bit options. Don't threaten me with a good time by making me advocate for my own ciphers.)

Lastly, you started talking about information-theoretic security. You're absolutely right that with small cipher texts, they are too close to information-theoretic bounds to be able to be decrypted at all. This is why one-time pads work. It's also why a lot of short messages encrypted by something long ago have not been deciphered, because there's just not enough information in the cipher to be able to pull it back out. This is really fascinating but not at all related to Grover, except to mention that Grover cannot decrypt something that is information-theoretically secure.

Answer 5

The question as currently written asks whether Grover's algorithm threatens symmetric security proofs.

The vacuous answer to this is "no".

A proof will operate under an assumption of a particular adversary, frequently a classical adversary with some kind of oracle and some goal, and will operate under some assumptions about the cryptographic primitives in use (such as the ideal cipher model or the random oracle model). A proof will commonly be a reduction, showing that if the adversary can achieve their goal, then they must also have the capacity to defeat some assumed property of the underlying cryptographic primitives.

The proof remains valid, even if a more powerful adversary exists in the real world (such as a quantum adversary), or if no real cryptographic primitives meet the assumptions (the random oracle model is already controversial for precisely this reason).

So the proofs themselves aren't threatened at all, but the extent to which they're applicable to the real world may be diminished by things that aren't considered in their model.