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.
Explore the documents
Explore
an annotated version of the NSA's description of its effort to build "a
cryptologically useful quantum computer." Read it.
The
agency describes classification levels for information related to quantum
computing. Read
it.
Barton
Gellman DEC 24
His
leaks have fundamentally altered the U.S. government’s relationship with its
citizens, the rest of the world.
Read
all of the stories in The Washington Post’s ongoing coverage of the National
Security Agency’s surveillance programs.
"If
you think you understand quantum mechanics, you don't understand quantum
mechanics," said the late Nobel laureate Richard Feynman, widely regarded
as the pioneer in quantum computing. The science video blog Vertiasium tries to
help make sense of it.
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 primeswithin
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.
