Hacker News Reader

For symmetric cryptosystems search difficulty is halved (a 256 bit AES key under a quantum bruteforce becomes as 'hard' as a 128 bit key under conventional bruteforce).

For asymmetric systems, search is reduced to polynomial (if using the discrete log, EC discrete log or prime factorization).

View on HN

Doesn't halving the search difficulty mean dropping 1 bit from the key length? So 256->255 rather than 256->128?

The numbers are correct, but it was written in an odd way. Grovers algorithm gives a speedup of sqrt(n), so the exponent gets halved.

For some public key systems, the search becomes polynomial. Luckily, we know of ones for which that is not the case (as far as we know), and so if a practical quantum computer could be built we would just deploy new cryptosystems (pricey, but not end-of-the-world pricey).

Reply on news.ycombinator.com