The Final Nail in the Coffin for Privacy?

[Renegade]

Can quantum computing reduce prime numbers and factorization to polynomial time? If so, does that spell the end of privacy and security on the interwebs?

http://www.naturalne...ernment_secrets.html

NaturalNews exclusive: US government developing ultimate cyber weapon; Prime-factoring quantum computing makes encryption obsolete

...

All this is very much a layman's description of the phenomenon of quantum computing, by the way. Physicists will get into far more detail about how qubits might actually work... although technically, nobody really understands quantum computing. The key thing to understand about quantum computing is that a qubit can store its states of zero and one simultaneously. A collection of eight qubits can store 256 variations or "values" simultaneously, unlike a traditional silicon "bit" which can only store one of 256 values at a time.

The upshot of all this, mathematically speaking, is that instead of decryption algorithms being exponentially more complex as the number of encryption digits increases, qubits allow decryption algorithms to process the problem in so-called polynomial time, meaning the problem becomes exponentially easier to solve. (Or, technically, it doesn't become exponentially harder to solve as the number of encryption digits increases.)

If I weren't so lazy, I'd look into it more. Instead, I'm posting here at DC for other people to do the heavy lifting.

[SeraphimLabs]

Of course they still botched the explanation.

A bit is either 1 or 0, on or off, with only two possible states.

They're thinking about bytes, which uses 8 bits to store 1 of 256 possible values at a time.

But security is ultimately no better than the weakest link, with nearly every data security scheme in the world having some vital and carefully safeguarded flaw that only a few deep inside people even know about.

Besides, even if they do invent a radically new computing technology with calculation power greater than anything we've ever considered, someone will almost instantly develop a whole new encryption scheme that takes advantage of that power to generate it and in the process makes it again time consuming to crack. Even if it means going back to the centuries old technique of actually scrambling the documents, or using a template to decode it.

[f0dder]

Besides, even if they do invent a radically new computing technology with calculation power greater than anything we've ever considered, someone will almost instantly develop a whole new encryption scheme that takes advantage of that power to generate it and in the process makes it again time consuming to crack.

-SeraphimLabs (August 22, 2012, 11:56 AM)

Will they? And will they be able to design something that can run, securely, on a regular non-quantum computing device? I expect there's going to be a nice long gap where government agencies and (decreasingly) sophisticated/wealthy nasty attackers will have access to quantum computing devices, whereas it'll take far longer before everybody and their dog has. Just how many of our current public/private-key encryption schemes don't depend on factoring numbers? What do we currently have, or know of mathematically, that is resistant to the currently known quantum-computing attacks?

Even if it means going back to the centuries old technique of actually scrambling the documents, or using a template to decode it.

-SeraphimLabs (August 22, 2012, 11:56 AM)

Document encryption (using symmetric ciphers) isn't the biggest worry here, it's the prospect of (all?) our existing asymmetric public/private key schemes going bunk... without those, no SSH, no SSL, no lots-of-other-stuff.

[Carol Haynes]

I thought quantum cryptography was supposed to be the ultimate in security?

http://www.csa.com/d...s/crypt/overview.php

Of course we all need fibre optics but that is coming!

[vlastimil]

Yes, if factoring numbers becomes easy, we will be in big trouble for some time. Too many things depend on that.

Though, the question whether there ever will be a feasible quantum computer is not decided. It may be just too difficult to manufacture enough qubits and maintain coherency long enough. It may prove to be as difficult as making a room-temperature superconductor. Finding a way to create and control 5 qubits may be totally unrelated to finding a way to manufacture 10 of them. This is just a wild speculation, but maybe the problem with manufacturing enough qubits is exponential - building N+1 is twice as difficult than building N. Maybe we will build a quantum computer that will be able to turn exponential problems into polynomial ones, but only up to size of (a very small) N.

[ewemoa]

Does this seem relevant?

  http://pqcrypto.org/

[barney]

Does this seem relevant?

  http://pqcrypto.org/

-ewemoa (August 24, 2012, 07:47 PM)

Very interesting link.  Thanks  .  You just ate up all my free time for the next three (3) months  .