14
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ Does this answer your question? Is AES-256 a post-quantum secure cipher or not? and Could quantum computers "break" symmetric crypto-systems (e.g. AES)? – and Is AES-128 quantum safe? $\endgroup$
    – kelalaka
    Commented Oct 17, 2023 at 6:04
  • 1
    $\begingroup$ Note that for RSA, ECC-like scheme the Shor's period doesn't need any (plaintext,ciphertext) pair. $\endgroup$
    – kelalaka
    Commented Oct 17, 2023 at 7:58
  • 3
    $\begingroup$ Grover's Algorithm has a very simple explanation: If you could do some brute-force search with N queries to some oracle, now you can instead do it with sqrt(N) queries. This breaks (quantitatively, not totally) a lot of things, and it should be straightforward to analyze what it breaks or not. E.g. it would not break a true one-time pad, which is information-theoretically (not merely computationally) secure. $\endgroup$ Commented Oct 18, 2023 at 16:23

5 Answers 5

13
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ @VictorEspinoza If you want to understand the quantum query by something like classical parallel query, the important thing is that a single quantum query (potentially) evaluates every possible input simultaneously, which makes the situation complex and the classical bound useless. Also, I need to say that this quantum=parallel understanding is a usual mistake. $\endgroup$
    – Hhan
    Commented Oct 17, 2023 at 3:52
  • 5
    $\begingroup$ For the second comment, this is indeed a very important point, which I didn't include in my answer because it seems a little bit off from your question. But, yes, making quantum query to (say) AES without knowning secret key is somewhat strange assumption, because someone who holds the AES key is probably classical and may not answer quantumly. However, when we are applying Grover search on key with the quantum implementation of AES, with the knowledge of some plaintext-ciphertext pairs, the key space is indeed reduced by half-bit. $\endgroup$
    – Hhan
    Commented Oct 17, 2023 at 3:56
  • 1
    $\begingroup$ Still, the quantum cryptanalysis with assuming quantum encryption oracle is of theoretic interest. In some simple cases like Even-Mansour or FX, this kind of hypothetical quantum oracle attacks are discovered first, then the attacks using the classical encryption oracle + quantum implementation of them (without knowing key) better than classical bound follow, inspired by the quantum oracle attacks. $\endgroup$
    – Hhan
    Commented Oct 17, 2023 at 4:00
  • 7
    $\begingroup$ Note - Grover's algorithm is easily re-defeated by doubling the key length, cancelling out sqrt(N). So it's not a serious threat to symmetric cryptography. $\endgroup$ Commented Oct 17, 2023 at 13:56
  • 1
    $\begingroup$ @VictorEspinoza While a complete explanation of why quantum is not just parallel classical doesn't fit in a comment, you can get a decent intuition by noting that parallel algorithms generally (especially in practice) have limits on how efficiently information can be shared between threads; information transfer also tends to end up forcing bits of sequential code into your parallel algorithm. Quantum computers don't have this problem, at the cost of not being able to query an individual "thread". $\endgroup$ Commented Oct 19, 2023 at 6:18
15
$\begingroup$

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).
$\endgroup$
11
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "It is and it will be always secure." This seems a bit strong of a claim at this point, no? Or did you just mean from Grover's? $\endgroup$ Commented Oct 18, 2023 at 17:53
  • 4
    $\begingroup$ @TrixieWolf It is clear that It will be secure against Grover's. For classical, well, it resisted attacks more than 20 years. The AES authors really know what they are doing, even the rounds are thigh. AES is not perfect ( not hermetic cipher i.e has related key attacks - this is important if you want to build hash function with AES). NSA is working to attack with Tau statistics, however, whatever the attack is it will be hard to consider that the attack can reduce the key size less than 200. Even for DES, the practical attack is the bruteforce $\endgroup$
    – kelalaka
    Commented Oct 18, 2023 at 19:00
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ok, thank you for your answer. I recently new in this about provable security and make noise to me all this quantum stuff. By the way, I would like to continue talk about tweakable blockciphers so no problem with good times. $\endgroup$ Commented Oct 18, 2023 at 23:00
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.