Hacker Newsnew | comments | ask | jobs | submitlogin
An example of quantum-hard classically-implementable asymmetric crypto (wikipedia.org)
39 points by api 441 days ago | comments


tptacek 440 days ago | link

This is currently a well-studied problem in cryptography.

NTRU is one of many post-quantum (pq) candidates. Other ones include McEliece, a very old (1978) asy system that uses error-correcting codes but was beaten in the market by RSA's shorter secure keys, and Lamport-Diffie, which uses hash functions.

Here's a good talk:

http://cr.yp.to/talks/2008.10.18/slides.pdf

-----

krickle 441 days ago | link

These have facinated me for a while. I wish there was a nice open source implementation of the McEliece cryptosystem to try out.

-----

tptacek 440 days ago | link

Write one! Use any language. You'll probably learn a ton. McEliece looks like a particularly fun one to do, and its building blocks have a lot of other uses (unlike RSA).

-----

uvdiv 440 days ago | link

Patented, naturally.

-----

xenophonf 440 days ago | link

Crypto is probably one of the few types of software patents that I'd support. It's non-obvious in the extreme, and patenting a cryptosystem might be a good way to open it for public review.

-----

DennisP 440 days ago | link

Bruce Schneier has written that patents for crypto algorithms are useless. A crypto algorithm is only trustworthy if it attracts the attention of a lot of cryptographers trying to break it, and for the most part they don't bother with patented algorithms.

There's no worry about opening algorithms for public review. Nobody with a clue is willing to use a proprietary algorithm in the first place.

-----

betterunix 440 days ago | link

When last I checked, we were not supposed to have patents on math. Now, we can argue endlessly about whether or not that covers all software, but if public key crypto is not math then I am not really sure what is...

-----

DennisP 440 days ago | link

Sadly, RSA was patented. The patent expired in 2000.

-----

betterunix 440 days ago | link

I know, and it is worse than that. Over a hundred patents on ECC techniques, at least five on identity based encryption, and even patents on fully homomorphic encryption despite the fact that FHE is still years from practicality (including at least one patent on FHE that was granted before Gentry even showed that FHE is possible).

It is, simply put, a monumental failure on the part of patent examiners.

-----

im3w1l 440 days ago | link

What is the probability that someone developed/will soon develop good enough quantum computers for breaking RSA, ECC in secrecy?

-----

jessriedel 440 days ago | link

Having spoken with experts on the experimental (and theory) side at IBM Watson, the general answer for an over/under estimate to a quantum computer performing a useful calculation is 20 or 30 years. Most people put wide error bars on that, though, and I think the 2-sigma range is probably 5-100 years.

-----

archgoon 439 days ago | link

I'll interpret that as an optimistic: "Never or soon."

-----

cantos 440 days ago | link

[Edit: misread the question. This answer is about how close we might be to breaking these cryptosystems on classical, not quantum, computers]

Publicly accessible progress on factoring and discrete log have essentially employed variations on single idea and hundreds of papers have been written on the topic. It is one of the most common Phd thesis topics in math. Yet still there has been no significant new ideas since 1994. I think that Arjen Lenstra has said that he believes there will be no further progress with this approach and new ideas are needed. However, there's not even a hint of where to begin. Likewise there has never been a single promising idea for an attack on ECC.

But this lack of progress in academia may be a self fulfilling prophecy in some sense. It is not possible to get funding to just attempt to break cryptographic protocols, at least not without already having a breakthrough result. If a government decided to go all out trying to break a protocol that would create an environment more conducive to making progress.

-----

api 440 days ago | link

I thought ECC was vulnerable to Shor's algorithm. Of course we probably don't have QCs good enough to actually do it even for "toy" key sizes, let alone for the 256 bit or higher key sizes that are commonly used.

-----

cantos 440 days ago | link

Yes you're right that ECC is vulnerable to Shor. I answered a different question then the one that was asked.

-----

DennisP 440 days ago | link

This looks like it might be an interesting attack (though I'm not competent to judge, plus it's paywalled): http://link.springer.com/article/10.1007%2Fs00145-008-9031-0...

And here's a pdf intro to lattice-based crypto: http://www.cims.nyu.edu/~regev/papers/pqc.pdf

-----

gwern 440 days ago | link

http://en.wikipedia.org/wiki/Post-quantum_cryptography

-----

api 441 days ago | link

None of these look ready for prime time, but the fact that it's possible is a great sign. It means the age of asymmetric crypto and all it entails won't end with practical QC. (Which is still a ways off...)

Of course if QC does appear and these algos are still not ready, an intermedia stopgap would be to use RSA, DSA, or ECC with very, very big keys, since as far as I understand it Shor's algorithm must be run over a single block. (Correct me if I'm wrong.)

-----

adrianbg 440 days ago | link

What do you mean by "block"? A limit on the number of entangled qubits?

-----




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

Search: