A lot has been made about a post-quantum computer future in which traditional encryption methods have suddenly been rendered obsolete. With this terrifying idea in mind, it’s reassuring to see some recent pushback to the idea with some factual evidence. In a recent blog post by [Filippo Valsorda] – a cryptography engineer – the point is raised that 128-bit symmetric keys like AES-128 and SHA-256 are at risk of being obliterated in a post-quantum future.
Rather than just taking [Filippo]’s word for it, he takes us through a detailed explanation of the flawed understanding of Grover’s algorithm that underlies much of the panic. While it’s very true that this quantum search algorithm can decrease the amount of time required to find a solution, the speed-up with a single thread is quadratic, not exponential. While asymmetric cryptography systems like ECDH, RSA, and kin are very much at risk courtesy of Shor’s algorithm, the same is not true for symmetric systems.
An interesting detail with Grover’s is also that you cannot simply run a search in parallel to get a corresponding speed-up, as it’s not a parallel problem. Barring a breakthrough that replaces Grover’s with something that lends itself better to such a parallel search, it would seem that we won’t have to abandon classical encryption any time soon.
Incidentally, even for Shor’s algorithm, there are still some hold-ups. Current quantum computers are not even able to factor 21 yet. Meanwhile, supposed quantum computing breakthroughs are being trolled with a Commodore 64.









