Hacker News new | ask | show | jobs
by adrianhoward 4815 days ago
So does this mean Shor's Algorithm is going to kick in for real and ruin all our securityz?

Nope.

First, as I understand it, the D-Wave stuff isn't a system that can run Shor's.

Second, Shor's only ruins security for a certain class of crypto algorithm. There are already algorithms that exist today that a proof against it (e.g the McEliece cryptosystem http://en.wikipedia.org/wiki/McEliece_cryptosystem).

Third, if you're really worried about the man cracking your s3cr3t stuff with quantum computers go pick the right cryptosystem ;-) Plenty of symmetric encryption systems that only get their key lengths reduced (effectively halved) by Grover's algorithm.
2 comments
daeken 4814 days ago
People tend to equate asymmetric crypto with the likes of RSA; systems where the efficient factoring of large numbers is a death sentence. But there's a whole slew of other asymmetric cryptosystems without such properties, e.g. elliptic-curve cryptography.
link
forTheRecord 4814 days ago
Shors algorithm also breaks elliptic-curve cryptography.
link
daeken 4814 days ago
Oh, wow, I've never seen the variant that breaks ECC; that's really quite awesome. Time to read some papers!
link
adrianhoward 4814 days ago
Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202 is what you want ;)
link
Devilboy 4814 days ago
This is not correct anymore, according to D-Wave they do have a factoring algorithm now.
link
adrianhoward 4814 days ago
Interesting. Do you have some pointers to that?

I thought both the D-Wave 1 & 2 both had specialist quantum chips that couldn't run Shor's.

link
Devilboy 4814 days ago
https://dwave.wordpress.com/2011/05/11/learning-to-program-t...
link
adrianhoward 4814 days ago
Hmmm... can't find anything else on that apart from the mention in that blog post. Is there more detail anywhere?

They also implicitly state that it's not Shor's which is (to the best of my knowledge) the most effective integer factorisation algorithm for general purpose QCs currently know.

They also say that they "have a factoring algorithm". They don't say that it's actually implemented on running hardware.

I also notice the complete lack of clarification on the followup question that poked on the explicit "executed it on real hardware" question ;-)

link