This article makes me wonder if the government may already possess quantum computers.

If they did, how would we know?

If they did have them, they'd most likely have to hide their existence for quite some time.

During WWII, after the Allies had broken the Enigma cipher and were reading all the German communication, they still had to allow enemy actions that would result in loss of human life, just so they wouldn't tip their hand and reveal that they had broken the code.

I'd assume it would be the same today - a plausible non-crypto way of getting data came out ("We beat him with a pipe until he told us the password", ala http://xkcd.com/538/ ) would be a better explanation than if they broke a code with some quantum ubercomputer.

GCHQ had public key cryptography in the early 1970s, a few years before Diffie-Helman and RSA did their work. While I think it'd be difficult to hide properly functional quantum computing (given the amount of interaction between public and private sector) it wouldn't surprise me if fine minds on both sides of the atlantic were doing advanced research in the field.

We won't know if they do right now for another several decades. But even if they do, there are good arguments against them being able to break AES - AES is used by the government in contexts that require the information be kept secure for decades, which they could not do if they reasonably suspected AES would be broken in the near future and certainly not if they already knew.

The Enigma case doesn't really apply here - the US was not using the known flawed encryption themselves, and tipping the public off by calling for the development of a new standard only means that AES might be broken in the next decade or two, and maybe not by quantum computers. Cryptographers already recommend switching from weak algorithms years before they're fully broken.

RSA and other key exchange techniques are another story though, as the article mentions RSA is theoretically significantly weaker to a functioning quantum computer than AES to start with, and I don't really know the extent to which the government uses RSA.

> RSA and other key exchange techniques are another story though, as the article mentions RSA is theoretically significantly weaker to a functioning quantum computer than AES to start with, and I don't really know the extent to which the government uses RSA.

NSA Suite B Cryptography recommends use of ECDSA over RSA, but the latter is acceptable for documents with "SECRET" classification level.

There is a lot of hype around quantum computing, but as far as I know there are serious hints that it might be never possible -- for example they require expotentially small precision, which is unheard of in the world of physics (a quantum computer with n qbits requiring wave function to be exact to about O(n) binary places)

If goverments can break ECDSA with quantum computers, it will make bitcoin fanatics very unhappy.

Probably not. The information that somebody is able to break "classic" crypto is probably worth much more than all the bitcoins they could steal with it.

Since the bitcoins would become worthless, that pretty much goes without saying.

From the article: They can't see the future.

Forgive my ignorance of quantum computing, but the classical computer can see the future in a finite image space by computing every image combination. It just turns out to be a lot of computing to see every variation in any space of reasonable size.

Isn't this something a quantum computer would excel at, by computing the variations concurrently?

Completely unrelated.