[Infowarrior] - NSA seeks to build quantum computer that could crack most types of encryption

[Richard Forno]

NSA seeks to build quantum computer that could crack most types of
encryption
By Steven Rich and Barton Gellman

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_print.html

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 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.

“It seems improbable that the NSA could be that far ahead of the open
world without anybody knowing it,” said Scott Aaronson, an associate
professor of electrical engineering and computer science at MIT.

The NSA appears to regard itself as running neck and neck with quantum
computing labs sponsored by the European Union and the Swiss government,
with steady progress but little prospect of an immediate breakthrough.

“The geographic scope has narrowed from a global effort to a discrete
focus on the European Union and Switzerland,” one NSA document states.

Seth Lloyd, professor of quantum mechanical engineering at MIT, said the
NSA’s focus is not misplaced. “The E.U. and Switzerland have made
significant advances over the last decade and have caught up to the U.S.
in quantum computing technology,” he said.

The NSA declined to comment for this story.

The documents, however, indicate that the agency carries out some of its
research in large, shielded rooms known as Faraday cages, which are
designed to prevent electromagnetic energy from coming in or out. Those,
according to one brief description, are required “to keep delicate
quantum computing experiments running.”

The basic principle underlying quantum computing is known as “quantum
superposition,” the idea that an object simultaneously exists in all
states. A classical computer uses binary bits, which are either zeroes
or ones. A quantum computer uses quantum bits, or qubits, which are
simultaneously zero and one.

This seeming impossibility is part of the mystery that lies at the heart
of quantum theory, which even theoretical physicists say no one
completely understands.

“If you think you understand quantum mechanics, you don’t understand
quantum mechanics,” said the late Nobel laureate Richard Feynman, who is
widely regarded as the pioneer in quantum computing.

Here’s how it works, in theory: While a classical computer, however
fast, must do one calculation at a time, a quantum computer can
sometimes home in on the correct answer much more efficiently, without
running those calculations.

Quantum computing is so difficult to attain because of the fragile
nature of such computers. In theory, the building blocks of such a
computer might include individual atoms, photons or electrons. To
maintain the quantum nature of the computer, these particles would need
to be carefully isolated from their external environments.

“Quantum computers are extremely delicate, so if you don’t protect them
from their environment, then the computation will be useless,” said
Daniel Lidar, a professor of electrical engineering and the director of
the Center for Quantum Information Science and Technology at the
University of Southern California.

A working quantum computer would open the door to easily breaking the
strongest encryption tools in use today, including a standard known as
RSA, named for the initials of its creators. RSA scrambles
communications, making them unreadable to anyone but the intended
recipient, without requiring the use of a shared password. It is
commonly used in Web browsers to secure financial transactions and in
encrypted e-mails. RSA is used because of the difficulty of factoring
the product of two large prime numbers. Breaking the encryption involves
finding those two numbers. This cannot be done in a reasonable amount of
time on a classical computer.

In 2009, computer scientists using classical methods were able to
discover the primes within a 768-bit number, but it took almost two
years and hundreds of computers to factor it. The scientists estimated
that it would take 1,000 times longer to break a 1,024-bit encryption
key, which is commonly used for online transactions.

A large-scale quantum computer, however, could theoretically break a
1,024-bit encryption much faster. Some leading Internet companies are
moving to 2,048-bit keys, but even those are thought to be vulnerable to
rapid decryption with a quantum computer.

Quantum computers have many applications for today’s scientific
community, including the creation of artificial intelligence. But the
NSA fears the implications for national security.

“The application of quantum technologies to encryption algorithms
threatens to dramatically impact the US government’s ability to both
protect its communications and eavesdrop on the communications of
foreign governments,” according to an internal document provided by Snowden.

Experts are not sure how feasible a quantum computer is in the near
future. A decade ago, some experts said that developing a large quantum
computer was likely 10 to 100 years in the future. Five years ago, Lloyd
said the goal was at least 10 years away.

Last year, Jeff Forshaw, a professor at the University of Manchester,
told Britain’s Guardian newspaper, “It is probably too soon to speculate
on when the first full-scale quantum computer will be built but recent
progress indicates that there is every reason to be optimistic.”

“I don’t think we’re likely to have the type of quantum computer the NSA
wants within at least five years, in the absence of a significant
breakthrough maybe much longer,” Lloyd told the Post in a recent interview.

However, some companies claim to already be producing small quantum
computers. A Canadian company, D-Wave Systems , says it has been making
quantum computers since 2009. In 2012, it sold a $10 million version to
Google, NASA and the Universities Space Research Association, according
to news reports.

That quantum computer, however, would never be useful for breaking
public key encryption like RSA.

“Even if everything they’re claiming is correct, that computer, by its
design, cannot run Shor’s algorithm,” said Matthew Green, a research
professor at the Johns Hopkins Information Security Institute, referring
to the algorithm that could be used to break encryption like RSA.

Experts believe that one of the largest hurdles to breaking encryption
with a quantum computer is building a computer with enough qubits, which
is difficult given the very fragile state of quantum computers. By the
end of September, the NSA expected to be able to have some basic
building blocks, which it described in a document as “dynamical
decoupling and complete quantum control on two semiconductor qubits.”

“That’s a great step, but it’s a pretty small step on the road to
building a large-scale quantum computer,” Lloyd said.

A quantum computer capable of breaking cryptography would need hundreds
or thousands more qubits than that.

The budget for the National Intelligence Program, commonly referred to
as the “black budget,” details the “Penetrating Hard Targets” project
and noted that this step “will enable initial scaling towards large
systems in related and follow-on efforts.”

Another project, called the “Owning the Net,” is using quantum research
to support the creation of new quantum-based attacks on encryptions like
RSA, documents show.

“The irony of quantum computing is that if you can imagine someone
building a quantum computer that can break encryption a few decades into
the future, then you need to be worried right now,” Lidar said.

© The Washington Post Company

-- 
Just because i'm near the punchbowl doesn't mean I'm also drinking from it.