PERSPECTIVE: RETROSPECTIVE DECRYPTIONA Retrospective Post-Quantum Policy Problem

Published 15 September 2022

In May 2022, a White House memorandum warned that a quantum computer of sufficient size and sophistication will be capable of breaking much of the public-key cryptography used on digital systems across the United States and around the world. The various steps taken by the administration, and proposed by lawmakers, to deal with the problem are all forward-looking. “However, despite these efforts, policymakers have given little or no attention to what could be called a retrospectivepost-quantum problem,” Herb Lin writes. “Policymakers would be wise to consider the very real possibility that in a PQC[post-quantum computing] world, messages they once believed would be kept secret could in fact be made public.”

In May 2022, the White House issued a National Security Memorandumthat stated:

a quantum computer of sufficient size and sophistication—also known as a cryptanalytically relevant quantum computer (CRQC)—will be capable of breaking much of the public-key cryptography used on digital systems across the United States and around the world. When it becomes available, a CRQC could jeopardize civilian and military communications, undermine supervisory and control systems for critical infrastructure, and defeat security protocols for most Internet-based financial transactions.

Herb Lin writes in Lawfare that this concern is not new. The theoretical possibility that quantum mechanics could be used as the basis for computation was first posed in the physics literature around 1980. In 1994, Peter Shor developedan algorithm that could rapidly factor large numbers into their constituent primes if run on a quantum computer.

Lin adds:

Since 1994, the cryptography community has speculated about the forthcoming availability of quantum computing hardware that could run Shor’s algorithm. In the early days of such speculation, the range of estimates for that time frame ranged from “pretty soon” to “probably never.” However, in recent years, the emerging consensus seems to be that quantum computing, as it applies to cryptanalysis, cannot be dismissed as mere puffery.

The efforts by lawmakers and government agencies to deal with the emerging problems posed by quantum computing have generally focused on the future by developing the technology base to support what the United States should do to ensure the security of its sensitive communications.

However, despite these efforts, policymakers have given little or no attention to what could be called a retrospectivepost-quantum problem.To wit—pre-quantum public-key encryption algorithms such as RSA have almost certainly been used to protect nearly all classified U.S. government messages since the 1970s, when the mathematics for public-key encryption were first discovered. A properly encrypted message is useless to anyone without the decryption key or the technology to discover that key, but even encrypted messages can be recorded for future analysis. Indeed, intelligence agencies have a habit of collecting information just in case it might be useful in the future, and there is no reason to suppose that these encrypted messages have not been recorded somewhere by some adversary government. 

 In a PQC world, those recorded encrypted messages will be vulnerable to decryption. In their decrypted form, they potentially hold a treasure trove of secrets. Though these are secrets from the past, decrypted messages may reveal embarrassments and dangers with potentially detrimental policy implications for today and tomorrow. The possibilities for these secrets are endless: Salacious information about a world leader currently believed to be a right and upstanding patriot to his country? Operational instructions regarding an assassination attempt or a coup supported or encouraged by U.S. authorities despite public denials? A communique about alien technology discovered by accident on the ocean floor? 

Lin concludes:

Policymakers would be wise to consider the very real possibility that in a PQC[post-quantum computing] world, messages they once believed would be kept secret could in fact be made public. The adversary cannot be confident that it will be able to retrieve a large volume of interesting information from its trove of encrypted recorded messages, at least not in the immediate aftermath of a true quantum computing breakthrough. Still, the United States cannot be fully confident that any of its secrets encrypted with pre-quantum algorithms will never be revealed. Thus, the danger that such secrets will be revealed will only grow, as the adversary is able to devote more quantum computing resources to the process of retrospective decryption.