# Is it true that AES-128 and AES-256 are Quantum resistant?

Is it true that with the rise of quantum computers, which is pretty close these days, AES 128 and 256 are resistant? while PGP and RSA are not?

• Can you link sources for that? Oct 23, 2015 at 20:20
• i read it on a book called "understanding bitcoin", page 63, Oct 23, 2015 at 20:49
• Find the answers yourself. en.wikipedia.org/wiki/Grover%27s_algorithm and en.wikipedia.org/wiki/Shor%27s_algorithm The short answer is that yes, AES is more quantum computer resistant than RSA is. The long answer is that we're a long way away from quantum computers able to tackle these problems. Oct 23, 2015 at 21:39

Not entirely. Symmetric cryptosystems, including those using AES, are not completely broken by quantum computing, as far as we know. However, Grover's algorithm does pose a significant threat:

Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just O(N^(1/2)) evaluations of the function, where N is the size of the function's domain.

This means that, given a known plaintext-ciphertext pair, we could determine an AES-128 key using about (2^128)^(1/2) = 2^64 steps. In other words, AES-128 would be unusable.

There's a straightforward mitigation though: double the key size. In a post-quantum world, AES-256 is still comfortably secure.

PGP and GPG are programs that use a variety of cryptographic algorithms. All of their asymmetric operations use algorithms (such as RSA and ECDSA) that are vulnerable to quantum computing. It's likely that they will be updated, at some point, to use quantum resistant asymmetric algorithms, but that has not yet occurred.

• "In other words, AES-128 would be unusable." Thomas Pornin makes a really good point in this answer (security.stackexchange.com/a/48027): "however, note that these are 2^64 quantum-computing operations; you cannot apply figures from studies with FPGA and GPU and blindly assume that if a quantum computer can be built at all, it can be built and operated cheaply." Feb 11, 2016 at 21:18