Hacker News Reader

Comment by Lagged2Death | Hacker News Reader

But remember that before we build our Dyson sphere, we may get quantum computers...

Does quantum computing somehow get around the fundamental energy requirements?

Yes. The fundamental energy requirements come out of the destruction of information from a bit flip (or from a 2 bit -> 1 bit gate). Qubits don't undergo that transition - until the final measurement, they're in a superposition of both states, so the transformations are really just rotations and reflections of a state, which in principle are not subject to the same requirements. Also, the real power of quantum computing comes from the ability to 'test multiple answers' at once, at least in principle. In reality, we've only figured out how to do this for a small subclass of problems.

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).

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