GoKawiilThe advancing threat of cryptographically-relevant quantum computers has made it urgent to replace currently-deployed asymmetric cryptography primitives—key exchange (ECDH) and digital signatures (RSA, ECDSA, EdDSA)—which are vulnerable to Shor’s quantum algorithm. It does not, however, impact existing symmetric cryptography algorithms (AES, SHA-2, SHA-3) or their key sizes.
There’s a common misconception that quantum computers will “halve” the security of symmetric keys, requiring 256-bit keys for 128 bits of security. That is not an accurate interpretation of the speedup offered by quantum algorithms, it’s not reflected in any compliance mandate, and risks diverting energy and attention from actually necessary post-quantum transition work. The misconception is usually based on a misunderstanding of the applicability of a different quantum algorithm, Grover’s.
AES-128 is safe against quantum computers. SHA-256 is safe against quantum computers. No symmetric key sizes have to change as part of the post-quantum transition. This is a near-consensus opinion amongst experts and standardization bodies and it needs to propagate to the rest of the IT community. The rest of this article backs up this claim both technically and with references to relevant authorities.
The Grover speedup
Grover’s is a quantum algorithm that allows searching an input space of size N of an unstructured function f for the “right answer” in π / 4 × N \pi / 4 \times \sqrt{N} invocations of f.
This is commonly interpreted to mean that Grover’s algorithm can find an AES-128 key in 2 64 2^{64} “time.” That is not the case in practice, because running such an attack as a single sequential thread would take hundreds of thousands of years, and parallelizing it makes its total cost grow.
A few important things to understand about Grover’s algorithm:
the function oracle f must be implemented as part of the quantum circuit;
the oracle invocations have to happen one after the other in series;
importantly, there is no better way to parallelize the attack than to partition the search space (Zalka, 1997).
... continue reading