Hacker News Reader

Comment by iwwr | Hacker News Reader

Using elliptic-curve cryptosystems you may be able to reduce PK key sizes to near symmetric crypto lengths (within a factor of 2-4).

http://www.nsa.gov/business/programs/elliptic_curve.shtml

But remember that before we build our Dyson sphere, we may get quantum computers, which makes our bruteforcing polynomial rather than exponential. Cryptsystems based on discrete log, EC discrete log or prime factorization (pretty much all existing crypto-infrastructure) are vulnerable.

More on this http://en.wikipedia.org/wiki/Post-quantum_cryptography

View on HN

which makes our bruteforcing polynomial rather than exponential

I think that's wrong. Grover's algorithm let's us speed up any algorithm, but not exponentially. You just take the sqrt of the run time.

https://en.wikipedia.org/wiki/Grovers_algorithm

Shor's algorithm lets us factor numbers in polynomial time. This would break RSA, but not every algorithm in general. I think, but I'm not 100% sure, that elliptic curve methods have no known polynomial time quantum algorithms, for example.

https://en.wikipedia.org/wiki/Shors_algorithm

A version of Shor's algorithm applies to elliptic curve crypto:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.38...

The person quoting Schneier said: "... will be infeasible until computers are built from something other than matter and occupy something other than space"

So are quantum computers not from matter and not in space? :)

They (and Schneier) were talking about symmetric encryption, which does not rely on the things quantum computing is going to affect.

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

Does quantum computing somehow get around the fundamental energy requirements?

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

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

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.

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.

Reply on news.ycombinator.com