Quantum Cryptanalysis: Hype and Reality

Drawn from Law and Policy for the Quantum Age (Cambridge University Press, 2022), by Chris Jay Hoofnagle and Simson L. Garfinkel. 

In 1994, Peter Shor fired the starting gun of the quantum computing race. Shor found that a quantum computer—in those days, a device only imagined by physicists and theoretical computer scientists—could solve a math problem that in turn would make it possible to efficiently factor large numbers. Because much of modern encryption depends on the assumption that such factoring is too time-consuming for even all the world’s computers working together to crack a single key, Shor’s insight led to massive public and private investment in quantum computing. Inadvertently, it also caused many observers to view quantum computing mainly as a threat to encryption.

Today, nation-states and even private companies compete for “quantum computing superiority,” a quantum computer that is so fast that it can solve problems that cannot be realistically solved by classical computers (the kinds of computers that we use every day). The United States, China, the European Union, and individual European nations (France, Germany, the United Kingdom) are pumping billions into the field. And make no mistake: Quantum computers are here today. They just aren’t very powerful for solving real-world problems like factoring or revealing the secrets of photosynthesis.

Nevertheless, the public can now purchase shares in IonQ Inc., a pure-play quantum computing company that is listed on the New York Stock Exchange through the controversial but increasingly common practice of using a SPAC (special purpose acquisition company). And even relatively small startups have working, yet equally small, quantum computers. Chinese scientists can credibly claim to lead the quantum computing race, with peer-reviewed publications in top journals detailing their technical might. One of the Chinese machines even claims “quantum supremacy,” although it is supremely capable of solving a problem that is of no practical interest to anyone but quantum computing researchers and their investment bankers.

Does this mean that society is on the verge of losing all of its secrets to quantum cryptanalysis—possibly to a single geopolitical actor, like China? We confidently assess that this is improbable. Quantum cryptanalysis may indeed be a threat in the distant future, but we believe that the cryptanalytic usefulness of quantum computers will be limited, if they are possible at all. Here we highlight technical, practical, and economic and strategic reasons why cryptanalysis is a boogeyman. Cryptanalysis has occupied too much of the spotlight on quantum computing. That spotlight casts shadows on different, more realistic risks and benefits.

The State of the Science

Quantum computers are here today, both in research labs and in production. But even today’s most performant devices—the laboratory trophies that are at the very bleeding edge of what is possible with today’s technology—are far from leveling attacks on public key encryption systems like RSA. Scientists have made steady progress, but not enough to be a realistic threat.

Whereas modern computers are measured in bits and bytes—your new cell phone probably has a 64-bit processor and perhaps 256 gigabytes of storage—quantum computers are measured in qubits. Although many popular accounts of quantum computers say that qubits simultaneously have the value of 0 and 1, that’s not strictly true. Instead, qubits can have a value of either 0 or 1, but the value isn’t determined until the end of quantum computation. Whereas conventional computers consist of circuits that process data, quantum computers are more properly thought of as a collection of indeterminate data—qubits—that experience a program: at the end of the program’s execution, each qubit is measured. Typically a program must be played multiple times with many separate measurements before the outcome of a computation can be known with high accuracy.

In 2001, a 7-qubit bespoke quantum computer constructed by Isaac Chuang’s group at IBM Almaden Research Center successfully factored the number 15 into its factors 3 and 5. The number 15 is represented in binary by four bits: 1111. The number 15 is also, not coincidentally, the smallest number that is not prime, not even, and not a perfect square. So realistically, it’s the smallest number that the IBM team could have meaningfully factored. The “quantum computer” was based on a chemical that had been specially synthesized to have 7 qubits.

Since IBM’s demonstration, other researchers have factored larger numbers on quantum computers. None of these approaches has managed to factor a number out of reach of a conventional computer. Most of the numbers factored can be factored with pen and paper. For example, in 2012 a team led by Nanyang Xu at the University of Science and Technology of China, Hefei, successfully factored the number 143. 

More recent examples that have captured public attention include a January 2019 factoring of the 7-digit (20-bit) number 1,005,973 using a special kind of quantum device known as an annealing machine. This was an exciting development because it was previously thought that annealing quantum computers could not factor. This seemed to expand the cryptanalysis threat. The scientists reasoned that because the manufacturer of the device scaled it dramatically in just seven years, perhaps a machine capable of factoring the kinds of numbers used to secure today’s commercial internet might be constructed in years, and not in decades. 

The current record described in the peer-reviewed literature factors a 13-digit number, 1,099,551,473,989. 

For comparison, credible estimates predict that quantum cryptanalysis will require a large machine, one far bigger than anything built today, and one with far fewer errors. Instead of factoring 7- or 13-digit numbers, an attacker will need to factor 1,300-digit ones. A National Academies group assessed in 2019 that cryptanalysis against a weak RSA-encrypted message “requires building a machine that is more than five orders of magnitude larger and has error rates that are about two orders of magnitude better than current machines[.]” Google scientists estimated that factoring a conventional RSA public key in use on the commercial internet today “would take 100 million qubits, even if individual quantum operations failed just once in every 10 000 operations.” That article was titled “Commercialize Quantum Technologies in Five Years” and was published in 2017. In 2022, the largest quantum computer has just 127 qubits.

Quantum Computing Is Only a Threat to Modern Public Key Cryptography

When commentators predict a collapse in encryption, they are describing attacks against systems based on public key cryptography, such as RSA using the Shor algorithm (a method for using quantum computing to find a number’s factors). The statistics we relate above focus on RSA attacks. 

Public key cryptography is rarely used by itself in modern computing systems. Instead, a public key is used to encrypt Advanced Encryption Standard (AES) encryption keys: It is the AES keys that are used to encrypt the actual email messages, web pages, banking transactions, and bulk data on a hard drive. If you have an iPhone, its data is encrypted with AES.

In 1996, Lov Grover came up with a way to use a performant quantum computer to significantly cut the time that it takes to search for an AES encryption key. With Grover’s algorithm and exclusive use of a quantum computer, it might be possible to crack a 128-bit AES key in somewhere between 5 hours and a year, depending on many details. That’s why many governments and manufacturers have been upgrading their systems from AES-128 to AES-256. The upgrade, which is essentially cost-free, puts AES cracking out of range for even the most imaginably advanced quantum computer using today’s cryptanalytic methods.

Of course, there might be a breakthrough in the underlying cryptanalytic methods themselves—or in the understanding of complexity theory on which they are fundamentally based. If computer scientists ever discover that P=NP, then attacking encryption algorithms like RSA-2048 and AES-256 could become the stuff of high school science fairs soon thereafter. If P=NP, then computer scientists would be able to find fast and easy solutions to nearly all of today’s difficult problems. Today, most computer scientists do not think that we live in a world where P=NP. 

The Practical Realities of Cryptanalysis

Some commentators who discuss quantum computing imply that the mere existence of a large machine would undo all encryption. Like in the 1992 movie Sneakers, they suggest that successful quantum computing would unravel the world’s secrets in an automatic way, perhaps by finding some fundamental weakness in all encryption systems. But this is not the case. Instead, the attacker will have to use the quantum computer for cryptanalysis on a key-by-key basis. And even then, attackers would be able to decrypt only those messages that they had successfully intercepted and stored. This leads to three practical challenges that set bounds on the quantum cryptanalysis threat.

First, the attacker must acquire the encrypted data to analyze—meaning the attacker needs some kind of surveillance capacity against the target. The quantum cryptanalysis threat actor, therefore, comes from nation-states with large surveillance and storage capabilities, and from private actors with particular dominance on the internet. The biggest risk comes from institutions with the resources and incentives to keep messages for decades.

The second challenge is time. Cryptanalysis, even on a quantum computer, will take a lot of time. The National Academies estimated that a strong RSA key would take 28 hours to crack, while a 2019 Google paper proposed a method that would require 8 hours. Even a standard 2,048-bit key is projected to take 3.5 hours to crack.

The third challenge would be resource management. Military doctrine envisions a process involving targeting, tasking orders, and deconfliction for making such rationing decisions. Targeting is the process of selecting and making a priority of messages and pairing an appropriate response. Once targets are chosen, a military command would issue a tasking order to choose a method to attack the message.

To illustrate why this process is important, consider an organization that can intercept wireless messages between a target’s phone and a publication service such as Twitter. Each wireless message might contain a tweet destined for immediate publication, a tweet scheduled to be published at some point in the future, a direct message to another user, or perhaps a status check, polling the service for other messages posted by other users. Some of these messages are clearly more valuable than others, but they all require the same level of effort to decrypt. 

And here is the problem: With a well-designed encryption system, there is no obvious way to differentiate among messages before one is decrypted. Encrypted messages are easy to create, so a smart adversary can generate many worthless ones to flood or overwhelm another state’s capacity to decrypt. Lengthening keys imposes more time requirements on the attacker as well. The National Academies estimates that those using an 8,000-bit RSA key would impose 229 hours (about 1 and a half weeks) of work on the attacker. 

Twitter is a relatively public service, yet it still presents challenges for analysis. The situation is more challenging in other contexts because of advances in cryptographic features. Strong encryption has been available since the 1990s but has only recently become ubiquitous and usable. Today, however, strong encryption is everywhere, and modern systems implement forward secrecy, so that the compromise of one key will not endanger the secrecy of other messages.

The term “deconfliction” describes systematic management procedures to coordinate the use of resources by various stakeholders. Quantum cryptanalysis will require multiple layers of deconfliction. At the most basic level, there will need to be an equities process to decide who gets to make the decisions. 

Targeting and resource prioritization will become significantly more complex if the very existence of the quantum cryptanalysis system is itself a state secret. Policymakers will need to decide whether the results from cryptanalysis can be exploited directly, or if the results will need to be closely held to prevent adversaries from learning the extent of the organization’s cryptanalytic capabilities. 

What do these challenges mean in full? “Key value” emerges as an important factor. Attackers will need to focus on high-value keys—such as developer certificates—that give the attacker access to entire devices or services. Conversely, smart defenders will consider the time-value of their secrets and invest in defending the most important keys. 

Meanwhile, the window of vulnerability is closing rapidly, as work is underway to choose and deploy post-quantum cryptography systems that will likely be resistant to attack from even a large, reliable quantum computer. Deployment of such systems will take years and coordination, similar to the upgrade from AES-128 to AES-256. But in the meantime, there are relatively simple and inexpensive countermeasures: lengthening keys, choosing forward-secrecy-enabled services and using AES where possible.

The Economic and Strategic Reality of Cryptanalysis

The economics and strategy of quantum technologies reveal cryptanalysis to be a minor concern; this is unfortunate because the spotlight on cryptanalysis leaves other uses of quantum computing in the shadows.

The quantum computing race differs from prior big-science projects because of the role of the private sector. It is plausible that a technology powerhouse like IBM or even a startup in the field may develop the first strategically significant quantum computer. But no matter who develops that device, they will almost certainly be smart enough to not waste its capabilities on cryptanalysis.

Relatively speaking, there is not much money to be made in cryptanalysis. Realistically, governments are the only real buyers of the service. While governments have deep pockets, other uses of quantum computers are more strategic and remunerative.

The smart strategy will be to use one’s quantum computer to build ever-bigger quantum computers. Indeed, companies in quantum computing identify chemistry and materials science as their research focus. This is because with a mid-scale quantum computer, one might discover fundamental insights in materials design and in chemistry that elucidate strategies to build a larger quantum computer. 

Thus, like classical computers before it, quantum computer strategy is to trigger a virtuous cycle of growth. This insight also foreshadows an innovation policy issue: Groups that can make those fundamental observations are likely to pull ahead of the pack, building ever-larger computers with teams that were trained over decades, using discoveries that competitors cannot obtain. In this large-scale scenario, quantum computing could be a winner-take-all technology, suggesting that the first innovator might well become the most successful one.

In addition to the potential winner-take-all prize, the focus on quantum chemistry and materials science could lead to fantastically remunerative scientific discovery. Priorities include better understanding photosynthesis, nitrogen fixation, and the development of new pharmaceuticals. Innovations in those fields will mint untold billions and create entire new economic realities. Viewed in this light, using a quantum computer for cryptanalysis will be like developing satellites for surveillance and never allowing them to be used for weather or civilian communications. 

What the Public Should Be Worried About

Dramatic claims about the capabilities of quantum computers may be driven by marketing, wishful thinking and even strategic considerations. Marketing and wishful thinking are easy to understand: Companies want to position themselves as unparalleled leaders in the quantum computing field. The strategic considerations are more important and serve a political end: to quell concerns that might lead to regulation.

Inevitability is one moat against regulation. By making dramatic claims, such as, “in a 5 to 10 year timeframe, quantum computing will break encryption as we know it today…,” companies suggest that social regulation is impossible because the realities of the technology will make them futile. Such claims are the acceptable, modern equivalent of “you have zero privacy anyway. Get over it.” 

The second strategy is to elide military applications of quantum technology. Just as with artificial intelligence, some will hand-wave with far-off promises instead of focusing on who is funding quantum technologies and why.

Obscured in the shadows of cryptanalysis are far more anti-social uses of quantum computers. Optimizing the fixation of nitrogen may also lend insights into more destructive nitrogen bombs. Chemical discovery could lead to new kinds of chemical, biological and even genetic weapons. 

A huge portion of government expenditure in quantum technologies envisions new sensing systems for intelligence and war fighting. Indeed, quantum sensing will provide exquisitely sensitive devices, ones that could create entirely new surveillance capabilities with few countermeasures. 

The privacy threat from quantum technologies—at least in the near term—comes from quantum sensing that will give some actors the ability to sense gravity and electromagnetic fields remotely and through natural barriers such as walls and roofs. Quantum devices that increase the precision of measuring time will provide more resolution to other kinds of sensing as well. The real privacy threat we face is that quantum-capable governments and companies will be able to sense more and, thus, know more about us.

The strategic threat comes from reducing the stealthiness of submarines and low-observable aircraft. Imagine a world where a single, quantum-superior government can see all other nations’ weapons systems and critical infrastructure from space.

Conclusion

In sum, quantum cryptanalysis is a threat, but one that we consider to be overhyped. Simply put, quantum computers will not magically break all encryption quickly, as sometimes implied by the news media and even by some policy analysts. Instead, attackers will carefully choose and focus their cryptanalysis resources on high-value keys, presumably ones that cannot be attacked using other intelligence tradecraft.

The collapse of encryption has captured the attention of the media and led to many privacy doomsday predictions about quantum computers. This narrative is unfortunate, because we believe that quantum computing has both more strategic opportunities and more positive potential for society through the application of quantum simulation. 

The views expressed in this book excerpt are those of the authors and do not represent the policy of the U.S. Department of Homeland Security or the U.S. government.