What does a square-root speedup do to a key?
Before the part that breaks, the part that does not. A secret needs a key and an open design, a fingerprint needs a one-way function, and both of those, the symmetric cipher and the hash, meet nothing worse than a square root.
Breaking a symmetric cipher with an unknown key is a search problem: try keys until one decrypts the message into something sensible. A quantum computer running Grover's algorithm searches N possibilities in about the square root of N steps. So a key space of 2128 becomes about 264 steps. That is a real speedup, and it is a quadratic one, nothing like the leap Shor's algorithm gives for factoring. It is also the best possible: Bennett, Bernstein, Brassard and Vazirani proved in 1997 that no quantum algorithm can search an unstructured space faster than the square root.
The practical answer is therefore dull and reassuring: use a 256-bit key. A 256-bit AES key under Grover costs as much as a 128-bit key does today, which nobody can brute-force. The US National Security Agency's CNSA 2.0 suite for national-security systems asks for AES-256, together with SHA-384 or SHA-512.
There is a second reason the threat is smaller than the number suggests. Grover's steps cannot be shared out the way a classical brute-force search can. A classical attacker with a million machines is a million times faster. A Grover attacker with a million machines is only a thousand times faster, because the speedup is the square root of the number of machines.
Grover iterations. To find the one marked item among N, the algorithm needs about
(π/4) · √N iterations, N = 2k for a k-bit key
For k = 128 that is (π/4) × 264 = 1.449 × 1019 iterations. Each iteration runs a full AES encryption reversibly inside the quantum computer, and the iterations must follow one another: iteration j needs the result of iteration j − 1.
What that means in time. Even granting each iteration a nanosecond, a deliberately generous figure for a reversible AES circuit, 1.449 × 1019 of them in a row is about 459 years. Splitting the search over p machines divides the time by √p, not by p, so 10,000 machines give a hundred-fold speedup. For k = 256 the iteration count is (π/4) × 2128 = 2.67 × 1038.
The rule NIST uses. NIST defines its post-quantum security categories by comparison with AES: category 1 means at least as hard as a key search against AES-128, category 3 AES-192, category 5 AES-256. Symmetric key search is the yardstick the new algorithms are measured against, which is a quiet statement of how well AES holds up.
Almost every encrypted connection AES-128-GCM, AES-256-GCM and ChaCha20-Poly1305 protect the bulk of the data in TLS, SSH, disk encryption and messaging. Moving to AES-256 costs a little speed and nothing else, which is why it is the conservative default for anything that must stay secret for decades.
The honest caveat The 459-year figure rests on an assumed iteration speed and on counting only serial steps. The engineering of a machine that runs 1019 reversible AES evaluations in sequence is far from the machines that exist, which is why the assessment for AES-128 is “probably fine in practice, 256 is the safe choice” and not “broken”. The key point for the rest of the course is the contrast: this is the mild case. The public-key case, from topic 04, is not.
Check yourself
What does Grover's algorithm do to the cost of searching for a 128-bit symmetric key?
Grover searches N possibilities in about the square root of N steps, so a 128-bit key costs about 2^64 serial iterations. It is quadratic, proven optimal for unstructured search, and a 256-bit key restores the margin.