How would you apply quantum computing to break a symmetric key system?

Question

How would you apply quantum computing to break a symmetric key system? Do you attack the plaintext password by bruteforcing? Or the mathematical process of the encryption algorithm?

Answer 1

There are lots of different ways.

Generally, symmetric key cryptography has much less structure than asymmetric-key cryptography, so there usually isn't much benefit to looking for mathematical structure that you can use. If no helpful structure can be found (such as with AES), you treat the encryption as a black box, and try to break it from there. The usual model for this is a known plaintext attack: you know a plaintext message $m$, and you know the encrypted value $c$, but you don't know the key that encrypted it. In this case, you would use Grover's algorithm to search the keyspace. In theory this offers a square-root speed-up over a classical brute-force search, although this only holds for a single processor doing the search. In practice you would use many parallel machines for a big search like this, and the more parallel machines you use, the smaller the advantage of Grover's algorithm.

A more sophisticated attack would try to attack the underlying structure of the encryption. Classically, the main methods are linear and differential cryptanalysis, of which there are quantum versions.

Some specific constructions (like Feistel or XEX) can be attacked quite easily if we are allowed quantum plaintext queries. This means we are allowed to construct arbitrary quantum states and send them to a server that has the secret key, and the server will apply an encryption circuit to that quantum state. Effectively, this means we are allowed to ask for a superposition of messages to all be encrypted in superposition under the same key.

This is a slightly outlandish assumption (it's really hard to maintain a quantum state, so if the server just lets any input decohere, the attack fails), but there are offline versions where you ask for a lot of plaintext-ciphertext pairs, then run an exponential-time algorithm that is a bit better than a basic Grover search.

Beyond any of this, we can ask about the actual kinds of attacks we might face. An attacker might not try to attack just a single person's key with a single plaintext-ciphertext pair. They might have many such pairs, from many different people, and they are satisfied if they can find any key. As you might expect, this is an easier problem for the attacker, and it is also easier for a quantum attacker, though quantum computers still give, at best, a square-root speed-up.