Race to save our secrets from the computers of the future

They call it Q-Day: the day when a quantum computer, more powerful than any yet built, could shatter the world of privacy and security as we know it.

This happens through a strange mathematical operation: separating some very large numbers, hundreds of digits long, into their prime factors.

This may sound like a trivial divisive problem, but it fundamentally undermines the encryption protocols that governments and companies have relied on for decades. Sensitive information such as military intelligence, weapons designs, industry secrets, and banking information are often transmitted or stored under digital locks that large number factoring can unlock.

Among the various threats to America’s national security, the discovery of encryption is rarely discussed in the same terms as nuclear proliferation, the global climate crisis, or artificial general intelligence. But for many of those working on the problem behind the scenes, the risk is existential.

Glenn S. “This is potentially a completely different kind of problem than we’ve ever faced,” said Gerstel, a former NSA general counsel and co-author of the Expert Consensus Report on Cryptography. It may only have a 1% chance of happening, but a 1% chance of a disaster is something to worry about.

The White House and the Department of Homeland Security have made clear that in the wrong hands, a powerful quantum computer could disrupt everything from secure communications to the foundations of our financial system. In short, credit card transactions and stock exchanges can be hijacked by fraudsters. Air traffic systems and GPS signals can be manipulated. And the security of critical infrastructure, such as nuclear power plants and the power grid, may be compromised.

The risk extends not only to future breaches, but to past ones as well: troves of encrypted data collected now and for years to come could be unlocked after Q-Day. Current and former intelligence officials say China and other potential rivals are likely trying to find and store such troves of data in hopes of deciphering them in the future. European policy researchers echoed these concerns in a report this summer.

No one knows when quantum computing will advance to that degree. Today, the most powerful quantum device uses 433 qubits, which are called the quantum equivalent of transistors. That number would probably have to reach tens of thousands, maybe even millions, before today’s encryption systems collapse.

But in the US cybersecurity community, the threat is considered real and urgent. China, Russia, and the United States are all racing to develop the technology ahead of their geopolitical rivals, though it’s hard to know who is leading the way because some achievements are shrouded in secrecy.

On the American side, the possibility that an adversary could win that race has sparked a multi-year effort to develop a new generation of encryption systems, systems that even a powerful quantum computer cannot crack.

The effort, which began in 2016, will culminate early next year when the National Institute of Standards and Technology is expected to finalize its guidelines for migrating to the new systems. Ahead of this migration, President Biden late last year signed the Quantum Computing Cybersecurity Preparedness Act, which directed agencies to review their systems for encryption that needs to be replaced.

But even with this new urgency, the migration to stronger encryption is likely to take a decade or more, a pace that, some experts worry, may not be fast enough to avert disaster.

Stay ahead of the clock

Researchers have known since the 1990s that quantum computing, which uses the properties of subatomic particles to perform multiple calculations simultaneously, might one day threaten the encryption systems used today.

In 1994, American mathematician Peter Shore showed how this could be done, publishing an algorithm that a then-hypothetical quantum computer could use to rapidly factor extremely large numbers. A task at which conventional computers are woefully inefficient. This weakness of conventional computers is the foundation upon which much of today’s cryptography is built. Even today, factoring one of the large numbers used by RSA, one of the most common forms of factor-based encryption, takes trillions of years for the most powerful conventional computers.

The Shors Algorithm initially landed as little more than a worrisome curiosity. Much of the world is moving to use encryption methods that Shor has proven to be vulnerable. The first quantum computer, too weak to run the algorithm efficiently, would not be built for another four years.

But quantum computing has advanced rapidly. In recent years, IBM, Google and others have shown steady progress in building larger and more capable models, leading experts to conclude that scaling up is not only theoretically possible, but achievable with a few major technical advances.

If quantum physics works as we expect, it’s an engineering problem, says Scott Aronson, director of the Center for Quantum Information at the University of Texas at Austin.

Last year, quantum tech startups attracted $2.35 billion in private investment, according to an analysis by consulting firm McKinsey, which also predicted the technology would generate $1.3 trillion in value in these fields by 2035.

Cybersecurity experts have warned for some time that arch-rivals such as China and Russia are among the few adversaries with both the scientific talent and the billions of dollars needed to build a formidable quantum computer, and are likely to go somewhat stealthily with quantum science.

Despite a number of achievements by American scientists, analysts insist the country is still in danger of falling behind, a fear echoed this month in a report from the Center for Data Innovation, a think tank focused on technology policy.

Too close for comfort

Scientists at the National Institute of Standards and Technology have worn the mantle of maintaining encryption standards since the 1970s, when the agency studied and published the first public cipher to protect information used by civilian agencies and contractors, the Data Encryption Standard. As encryption needs have evolved, NIST has regularly collaborated with military agencies to develop new standards that guide technology companies and IT departments around the world.

During the 2010s, officials at NIST and other agencies became convinced that the likelihood of a significant leap in quantum computing within a decade and the threat to national encryption standards had grown too high to be prudently ignored.

Richard H. “Our guys were doing the basic thing of saying, hey, this is too close for comfort,” Leggett Jr., a former deputy director of the National Security Agency, said.

The sense of urgency was heightened by the knowledge of how difficult and time-consuming it would be to roll out new standards. Judging some of the past migrations, officials estimated that even after settling on a new generation of algorithms, it could take another 10 to 15 years for widespread implementation.

It’s not just because all the players, from tech giants to small software vendors, have to integrate new standards over time. Some cryptography also exists in hardware, where it may be difficult or impossible to change, for example in cars and ATMs, NIST mathematician Dustin Moody notes that even satellites in space can be affected. .

“You launch that satellite, that hardware is there, you can’t replace it,” Dr. Moody noted.

Open source defense

According to NIST, the federal government has set an overall goal of migrating as many of these new quantum-resistant algorithms as possible by 2035, which many officials acknowledge is ambitious.

These algorithms are not the product of a Manhattan Project initiative or a commercial effort led by one or more technology companies. Instead, they came about through years of collaboration in a diverse and international community of cryptographers.

After its global call in 2016, NIST received 82 submissions, most of which were prepared by small teams of academics and engineers. As in the past, NIST relied on a playbook in which it solicits new solutions and then makes them available to government and private-sector researchers to challenge for weaknesses.

“It’s done in an open way so that academic cryptographers, the people who develop methods to break encryption, have a chance to assess what’s strong and what’s not,” said Steven B. Lippner, executive director of SAFECode. do A non-profit organization focused on software security.

Many of the most promising submissions are built on grids, a mathematical concept involving grids of points in various repeating shapes, such as squares or hexagons, but displayed to dimensions far beyond what humans can imagine. As the number of dimensions increases, problems such as finding the shortest distance between two given points become exponentially harder, even overcoming the computational strengths of quantum computers.

NIST eventually selected four algorithms for wider use.

Despite the serious challenges of transitioning to these new algorithms, the US has benefited from the experience of previous migrations, such as the one used to address the Y2K bug and the previous move to new encryption standards. The size of US companies such as Apple, Google and Amazon, with their control over large parts of internet traffic, also means that a small number of players can handle large parts of the transfer relatively quickly.

Chris Pickert, a professor of computer science and engineering at the University of Michigan, said, “You really get a very large fraction of the total traffic that updates directly to the new crypto, so you can get these very large chunks all at once.” , said.

But strategists warn that an adversary’s behavior after achieving a major breakthrough makes the threat different from any society’s defenses. Using advances in artificial intelligence and machine learning, a rival country might hide its advances rather than display them in order to silently infiltrate vast amounts of data.

Cybersecurity experts say that, especially as storage has become much cheaper, the main challenge now for US adversaries is not storing massive amounts of data, but making educated guesses about what they are harvesting.

Couple that with advances in cyber attack and artificial intelligence, Mr. Gerstel said, and you have a potential existential weapon against which we have no specific deterrent.