NSA seeks quantum computer to crack codes

WASHINGTON — 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 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 websites 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 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, 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 a 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 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 emails. 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.

Talk to us

> Give us your news tips.

> Send us a letter to the editor.

> More Herald contact information.

More in Local News

A firefighter stands in silence before a panel bearing the names of L. John Regelbrugge and Kris Regelbrugge during the ten-year remembrance of the Oso landslide on Friday, March 22, 2024, at the Oso Landslide Memorial in Oso, Washington. (Ryan Berry / The Herald)
‘Flood of emotions’ as Oso Landslide Memorial opens on 10th anniversary

Friends, family and first responders held a moment of silence at 10:37 a.m. at the new 2-acre memorial off Highway 530.

Julie Petersen poses for a photo with images of her sister Christina Jefferds and Jefferds’ grand daughter Sanoah Violet Huestis next to a memorial for Sanoah at her home on March 20, 2024 in Arlington, Washington. Peterson wears her sister’s favorite color and one of her bangles. (Annie Barker / The Herald)
‘It just all came down’: An oral history of the Oso mudslide

Ten years later, The Daily Herald spoke with dozens of people — first responders, family, survivors — touched by the deadliest slide in U.S. history.

Victims of the Oso mudslide on March 22, 2014. (Courtesy photos)
Remembering the 43 lives lost in the Oso mudslide

The slide wiped out a neighborhood along Highway 530 in 2014. “Even though you feel like you’re alone in your grief, you’re really not.”

Director Lucia Schmit, right, and Deputy Director Dara Salmon inside the Snohomish County Department of Emergency Management on Friday, March 8, 2024, in Everett, Washington. (Ryan Berry / The Herald)
How Oso slide changed local emergency response ‘on virtually every level’

“In a decade, we have just really, really advanced,” through hard-earned lessons applied to the pandemic, floods and opioids.

Ron and Gail Thompson at their home on Monday, March 4, 2024 in Oso, Washington. (Olivia Vanni / The Herald)
In shadow of scarred Oso hillside, mudslide’s wounds still feel fresh

Locals reflected on living with grief and finding meaning in the wake of a catastrophe “nothing like you can ever imagine” in 2014.

Everett mall renderings from Brixton Capital. (Photo provided by the City of Everett)
Topgolf at the Everett Mall? Mayor’s hint still unconfirmed

After Cassie Franklin’s annual address, rumors circled about what “top” entertainment tenant could be landing at Everett Mall.

Everett
Everett man sentenced to 3 years of probation for mutilating animals

In 2022, neighbors reported Blayne Perez, 35, was shooting and torturing wildlife in north Everett.

Dorothy Crossman rides up on her bike to turn in her ballot  on Tuesday, Aug. 1, 2023 in Everett, Washington. (Olivia Vanni / The Herald)
Everett leaders plan to ask voters for property tax increase

City officials will spend weeks hammering out details of a ballot measure, as Everett faces a $12.6 million deficit.

Starbucks employee Zach Gabelein outside of the Mill Creek location where he works on Friday, Feb. 23, 2024 in Mill Creek, Washington. (Olivia Vanni / The Herald)
Mill Creek Starbucks votes 21-1 to form union

“We obviously are kind of on the high of that win,” store bargaining delegate Zach Gabelein said.

Lynnwood police respond to a collision on highway 99 at 176 street SW. (Photo provided by Lynnwood Police)
Police: Teen in stolen car flees cops, causes crash in Lynnwood

The crash blocked traffic for over an hour at 176th Street SW. The boy, 16, was arrested on felony warrants.

The view of Mountain Loop Mine out the window of a second floor classroom at Fairmount Elementary on Wednesday, Jan. 10, 2024 in Everett, Washington. (Olivia Vanni / The Herald)
County: Everett mining yard violated order to halt work next to school

At least 10 reports accused OMA Construction of violating a stop-work order next to Fairmount Elementary. A judge will hear the case.

Imagine Children's Museum's incoming CEO, Elizabeth "Elee" Wood. (Photo provided by Imagine Children's Museum)
Imagine Children’s Museum in Everett to welcome new CEO

Nancy Johnson, who has led Imagine Children’s Museum in Everett for 25 years, will retire in June.

Support local journalism

If you value local news, make a gift now to support the trusted journalism you get in The Daily Herald. Donations processed in this system are not tax deductible.