NSA seeks to build quantum computer that could crack most types of encryption
NSA seeks to build quantum computer that could crack most
types of encryption
By Steven Rich and Barton Gellman, Thursday, January 2,
1:24 PM
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, Md.
The development of a quantum computer has long been a
goal of many in the scientific community, with revolutionary implications for
fields such as 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
about 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 the
Massachusetts Institute of Technology.
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, an MIT professor of quantum mechanical
engineering, 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 article.
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 avoid having to make calculations that are unnecessary to solving
a problem. That allows it to home in on the correct answer much more quickly
and efficiently.
Quantum computing is 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 soon a quantum computer would be
feasible. 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 Washington Post in
a recent interview.
Some companies, however, claim to already be producing
small quantum computers. A Canadian firm, 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 University Information Security
Institute, referring to the algorithm that could be used to break encryption
like RSA.
Experts think 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 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 “Owning the Net,” is using
quantum research to support the creation of 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
Comments
Post a Comment