An example of quantum-hard classically-implementable asymmetric crypto

http://en.wikipedia.org/wiki/NTRU

by api • 13 years ago

41 19 13 years ago

en.wikipedia.org

krickle• 13 years ago

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

tptacek2• 13 years ago

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

api2• 13 years ago

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• 13 years ago

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

uvdiv• 13 years ago

Patented, naturally.

xenophonf• 13 years ago

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.

DennisP3• 13 years ago

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.

betterunix2• 13 years ago

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

gwern• 13 years ago

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

im3w1l• 13 years ago

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

cantos2• 13 years ago

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

api2• 13 years ago

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.

jessriedel• 13 years ago

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• 13 years ago

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

tptacek2• 13 years ago

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

DennisP3• 13 years ago

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

An example of quantum-hard classically-implementable asymmetric crypto

Related Stories