NSA seeks to build quantum computer that could crack most types of encryption

[Logical]

In room-size metal boxes, secure against electromagnetic leaks, the National Security Agency is racing to build a computer that could break nearly every kind of encryption used to protect banking, medical, business and government records around the world.

According to documents provided by former NSA contractor Edward Snowden, the effort to build “a cryptologically useful quantum computer” — a machine exponentially faster than classical computers — is part of a $79.7 million research program titled, “Penetrating Hard Targets.” Much of the work is hosted under classified contracts at a laboratory in College Park.

The development of a quantum computer has long been a goal of many in the scientific community, with revolutionary implications for fields like medicine as well as for the NSA’s code-breaking mission. With such technology, all current forms of public key encryption would be broken, including those used on many secure Web sites as well as the type used to protect state secrets.

Physicists and computer scientists have long speculated whether the NSA’s efforts are more advanced than those of the best civilian labs. Although the full extent of the agency’s research remains unknown, the documents provided by Snowden suggest that the NSA is no closer to success than others in the scientific community.

More at : http://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html

[longship]

1. I wouldn't be too worried about that.

The theoretical basis is not yet nailed down as even possible, let alone practical. Yes, there is enough plausibility for there to be research, but not enough that we are going to see quantum computers soon. Plus, it is more likely to be done first at a place like MIT than NSA, and then first only on a small scale, very few qubits. Not very practical.

Then there's the big problem of how the hell do you even interface to the damned thing without screwing up the coherence. No coherence; no quantum computing.

[JVS]

2. I'm inexperienced on the computer side of this, but from number theory...

I remember that encryption generally relies on the lack of an "efficient" factoring algorithm, with "efficient" meaning a process that means IIRC at best a linear expansion of processes required as the number to be factored increases. So, my question is: how are they planning on getting around the lack of an efficient algorithm?

[Locut0s]

3. Encryption relies on there being no "classical" efficient algorithm...

In the world of quantum computers where a qbits can take on any of a range of values simultaneously, there are quantum algorithms that are efficient.

[longship]

4. Theoretically, a quantum computer can do massively parallel computing.

Cryptography depends on trap door algorithms, which can be solved one way, but where there is no analytic inverse function, forcing one to perform exhaustive search. Finding prime factors of very large integers is one of those trap doors. When a large number is the product of two very long prime numbers it is extremely difficult, if not impossible in practice, to discover the factors in a reasonable length of time.

Theoretically a quantum computer could short circuit this process by using its capabilities for massively parallel calculations, which is why NSA has a high interest.

But as I wrote above, I am not concerned that practical quantum computers will be seen any time soon. They may not ever happen. It's a very difficult problem if it is possible at all.