In the coming years, advancements in Quantum Computing could potentially challenge the integrity of current cryptographic systems. No one knows if it’ll be in 10 years or 20, but the possibility seems more likely than not. The cryptographic solutions we use are made up of both public key (asymmetric) and symmetric algorithms. It’s widely known that Quantum Computers could compromise our current public key algorithms, requiring a shift to post-quantum solutions or algorithms… However, that addresses only the public key algorithms: what about our symmetric algorithms (the ones we use to encrypt the data we’re transmitting); what threat does a Quantum Computer pose to those?

One common symmetric algorithm we use is AES (Advanced Encryption Standard), and it comes in a few flavors: one with 128-bit long keys, one with 256-bit long keys, and one with 192-bit long keys, which no one uses. Since we rely on the security of AES, the question becomes, “How resistant are these flavors to an attacker with a Quantum Computer?”

The best attack known against AES using a Quantum Computer is Grover’s Algorithm. This treats the cipher as a black box with an unknown key, and searches for the key that converts some known (or guessed) plaintext to the known ciphertext—when modeling attacks against ciphers, we generally assume that the attacker has some knowledge of the data being protected. However, on a conventional computer, which are the ones commonly available at present, such a key search would boil down to trying each key in succession, which is commonly referred to as a brute-force attack. Even with the AES flavor with the shortest keys (AES-128), there are just too many keys to go through in any plausible timeframe. Grover’s algorithm on a Quantum Computer has a ‘key halving’ property; this means that the amount of computation it needs to perform is comparable to what a conventional computer would perform against a key that is half the size. For example, Grover’s algorithm would be able to find a 128-bit AES key with about the same effort as a conventional computer would take against a 64-bit encryption key and it is well known that a 64-bit key is not secure against a current adversary with a significant amount of resources.

Now, Does this mean that AES-128 is not quantum-safe? Well, no, it doesn’t; while the above statements are true, we skipped over some details. For one, it appears likely that Quantum Computers will be slower than the corresponding conventional ones; for example, Quantum Computers will need to perform ‘error correction’ logic periodically to eliminate accumulated errors and decoherence, something that conventional computers do not need to do.

However, that’s not the main reason. Instead, while Grover’s algorithm does meet its stated computational efficiency, it does so by performing the operations successively. Grover’s Algorithm performs a long series of evaluations on AES using a Quantum Computer, and then measures the result—if successful, what it measures is the correct AES key. What that means is that while it can find an AES-128 key with only circa 10,000,000,000,000,000,000 AES evaluations, all those operations must be done one after another. If our theoretical Quantum Computer could perform an AES computation in one microsecond, that many AES evaluations would take around 300,000 years; we generally don’t care if an attacker learns our secrets that far in the future.

If we attack a 64-bit key using a conventional computer, it would take roughly the same number of computations using a single processor. However, in realistic setups, we don’t have a single processor trying one key after another. Instead, what a realistic attack would do is have a large collection of processors—millions or possibly billions—with each one trying keys. This reduces the time from centuries to a time frame that is useful for the attacker.

So…Can we do a similar division of work for Quantum Computers? Yes, we can, but it comes at a cost. Grover’s ‘key halving’ applies only to the key space that each Quantum Computer is searching over. What this means is that to halve the key space and also the time by using Quantum Computers in parallel, we need to increase the number of computers by 4x. To reduce the 300,000-year time we mentioned earlier to, say, 10 years, we would need around 900 million Quantum Computers. If you want to get technical, here’s an optional explanation (feel free to skip).

If you want to get technical… Here’s our explanation:

In our example above trying to attack a 128-bit AES key, a single Quantum Computer would be able to obtain the key using the same number of computations as a single conventional computer attacking a 64-bit key, due to key halving. Now, let’s try to reduce the time by distributing the work across multiple Quantum Computers such that each one has to do fewer computations. We use 2 Quantum Computers and give each of them 127 bits to work on. Together, they would still be attacking a 128-bit key because 1 bit can represent 21 values. Because of the key halving property, each Quantum Computer would be able to solve with the same number of computations as a single conventional computer attacking 63.5 bits (half of 127). Suppose we use 4 Quantum Computers, giving each one 126 bits to work with (2 bits can represent 22 = 4 values, so 4 sets distributed over 4 Quantum Computers). Now, each Quantum Computer will complete its task in the same number of computations as a single conventional computer attacking 63 bits. So, to go from an effective 64-bit to 63-bit (we use the word ‘effective’ because the target key being attacked is still 128-bit) on each computer, we need to raise the number of Quantum Computers from 1 to 4. Whereas making use of parallelism with conventional computers, going from attacking 64-bits to 63-bits on each, we would only need to raise the number of conventional computers from 1 to 2. This follows if we further try to reduce the computation on each computer: to decrease the effective bits being attacked on each computer by 1 bit or, in other words, to halve the key space and also the time, we need to increase the number of Quantum Computers by 4x, whereas we only need to increase the number of computers by 2x when using conventional computers in parallel.

So, to reduce the 300,000-year time we mentioned earlier to, say, 10 years, we would need to reduce the time by a factor of 30,000. Translating this to the number of bits to reduce in effective computation on each Quantum Computer, we take the logarithm of 30,000 with base 2, which calculates to about 14.9 bits to reduce. For each bit, we need to increase the number of Quantum Computers by 4x. So, the number of Quantum Computers needed is 414.9 which calculates to about 900 million Quantum Computers.

Does that mean that we’re totally safe? Probably yes, however, we would have to point out that there are still some assumptions in our analysis. We guessed that a Quantum Computer would be able to perform an AES evaluation in one microsecond – while that might be reasonable, that’s a number we picked out of the air. More critically, we assumed that unlike conventional computers it is infeasible to have a huge number of Quantum Computers in parallel. While this is likely a good assumption (for example, if our Quantum Computers require dilution refrigeration, there’s not going to be that many of them), it is still an assumption, especially since we don’t know which of the several Qubit technologies will end up being viable.

To wrap it up…What does this mean for you? Well, if we go through the same computations for AES-256, i.e., AES with 256-bit keys, we see that it is completely safe against any sort of attack by Grover’s Algorithm. Our suggestion would be, if turning on AES-256 is easy, such as if it’s just a selection in your configuration GUI, sure, go ahead—AES-256 is only slightly slower and is certainly secure against any of the above assumptions. On the other hand, if the work is more than that, we would suggest that you don’t worry about it, and instead try to make the rest of the system secure—AES-128 is probably not the weakest point in your system.