Hacker Newsnew | comments | ask | jobs | submitlogin
iwwr 484 days ago | link | parent

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



jackpirate 484 days ago | link

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

-----

pjscott 484 days ago | link

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

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

-----

Lagged2Death 484 days ago | link

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

Does quantum computing somehow get around the fundamental energy requirements?

-----

iwwr 484 days ago | link

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

-----

betterunix 484 days ago | link

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

-----

jacquesm 484 days ago | link

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

-----

scott_weber 484 days ago | link

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.

-----

gsteinb88 484 days ago | link

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.

-----

Aardwolf 484 days ago | link

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? :)

-----

kluge 484 days ago | link

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

-----




Lists | RSS | Bookmarklet | Guidelines | FAQ | DMCA | News News | Feature Requests | Bugs | Y Combinator | Apply | Library

Search: