3 ms·

So does this mean Shor's Algorithm is going to kick in for real and ruin all our securityz?

by Volpe 14y ago

jd007 14y ago
Probably not anytime soon. Right now a 4 year old kid can beat the best implemented Shor's algo (http://www.nature.com/nphoton/journal/v6/n11/full/nphoton.2012.259.html http://www.nature.com/nphoton/journal/v6/n11/full/nphoton.20...).
adrianhoward 14y 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 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.
- daeken 14y 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.
  - forTheRecord 14y ago
    Shors algorithm also breaks elliptic-curve cryptography.
    - daeken 14y ago
      Oh, wow, I've never seen the variant that breaks ECC; that's really quite awesome. Time to read some papers!
      - adrianhoward 14y ago
        Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202 is what you want ;)
- Devilboy 14y ago
  This is not correct anymore, according to D-Wave they do have a factoring algorithm now.
  - adrianhoward 14y 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.
    - Devilboy 14y ago
      https://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/#comment-22008 https://dwave.wordpress.com/2011/05/11/learning-to-program-t...
      - adrianhoward 14y 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 ;-)

So does this mean Shor's Algorithm is going to kick in for real and ruin all our securityz?

by Volpe 14y ago

So does this mean Shor's Algorithm is going to kick in for real and ruin all our securityz?

jd007 14y ago

Probably not anytime soon. Right now a 4 year old kid can beat the best implemented Shor's algo (http://www.nature.com/nphoton/journal/v6/n11/full/nphoton.2012.259.html http://www.nature.com/nphoton/journal/v6/n11/full/nphoton.20...).

adrianhoward 14y 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 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.

daeken 14y 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.
- forTheRecord 14y ago
  Shors algorithm also breaks elliptic-curve cryptography.
  - daeken 14y ago
    Oh, wow, I've never seen the variant that breaks ECC; that's really quite awesome. Time to read some papers!
    - adrianhoward 14y ago
      Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202 is what you want ;)
Devilboy 14y ago
This is not correct anymore, according to D-Wave they do have a factoring algorithm now.
- adrianhoward 14y 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.
  - Devilboy 14y ago
    https://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/#comment-22008 https://dwave.wordpress.com/2011/05/11/learning-to-program-t...
    - adrianhoward 14y 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 ;-)