Quantum cryptanalysis: hype and reality of the threat
(LawfareBlog) Chris Jay Hoofnagle, Professor of Law in Residence at the University of California, Berkeley, School of Law, where he teaches cybersecurity, programming for lawyers, and torts; and Simson Garfinkel, Senior Data Scientist at the US Department of Homeland Security, a part-time faculty member at George Washington University, and a member of the Association for Computing Machinery’s US Technology Policy Committee; discuss Quantum Cryptanalysis: Hype and Reality. Their premise is that “. . cryptanalysis is a boogeyman . ..occupying too much of the spotlight on quantum computing. Inside Quantum Technology News summarizes; interested readers can refer to original, lengthy discussion by clicking on the LawfareBlog source.
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.
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.
In the article, Hoofnagle and Garfinkel highlight technical, practical, and economic and strategic reasons why cryptanalysis is a boogeyman. They believe “Cryptanalysis has occupied too much of the spotlight on quantum computing. That spotlight casts shadows on different, more realistic risks and benefits”.
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.
Hoofnagle and Garfinkel explain: 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.
Hoofnagle and Garfinkel discuss the practical realities of cryptanalysis at length. Some commentators who discuss quantum computing imply that the mere existence of a large machine would undo all encryption. 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 second challenge is time. Cryptanalysis, even on a quantum computer, will take a lot of time. The third challenge would be resource management.
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.
Their 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.
