Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Elliptic curve cryptography isn't vulnerable to quantum computing. EDIT: This is mistaken. I was thinking of lattice-based cryptography, which isn't currently vulnerable to quantum computing.

In the video game Final Fantasy, there's a spell called "Doom" which places a countdown over your head. When it reaches 0, you die.

RSA is Doomed in exactly that sense: it's just a matter of time before RSA offers zero security, whereas elliptic curve cryptography remains (for now) unbroken.



It is [1]. Quantum computers, using Shor's algorithm, polynomially break any specialization of the abelian hidden subgroup problem; see [2] for a fairly complete list.

Whatever reason to prefer elliptic curves over integer factorization or discrete log-based schemes must be classical.

[1] http://arxiv.org/abs/quantph/0301141

[2] http://pqcrypto.org/quantum.html


Oh.

Then which (if any) algorithm is currently believed to be safe from quantum computing?

I think I was thinking of lattice-based cryptography.


There's a bunch of them. There's no known quantum algorithm for quickly decoding binary linear codes, so McEliece is one. The Clostest Vector Problem in linear algebra is another trapdoor that may be QC-resistent.

You didn't ask, but it's worth saying: block ciphers, stream ciphers and hash functions aren't thought to be fundamentally threatened by QC the way IFP and DLP number theoretic cryptosystems are.


It's easy-ish to move from RSA to ECC schemes, because they have significantly smaller key sizes and gain efficiency. The same isn't true of lattice schemes, which have significantly larger keys.

A switch to lattice or code-based crypto seems unlikely in the near future.


"it's just a matter of time before RSA offers zero security"

This is not the only possible outcome. Scalable quantum computing could turn out to be impractical due to cost. Or new physics could be found that rules out scalable quantum computing. Personally, I find both of these outcomes unlikely, the second more than the first, but they do exist.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: