An example of quantum-hard classically-implementable asymmetric crypto | Hacker News Reader

An example of quantum-hard classically-implementable asymmetric crypto

en.wikipedia.org

41 pointsapi19 comments

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

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

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

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

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

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.

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

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.

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

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

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

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

Patented, naturally.

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.

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.

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

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

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.

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

Reply on news.ycombinator.com