US gov tells agencies to get serious on quantum threat to cryptography

The US government has beefed up its response to the currently-theoretical-but-getting-less-so-all-the-time threat quantum computing poses to current cryptography, through a call for government bodies to prepare for quantum-proof algorithms, and a new committee.

May 4th's Biden quantum computing memo lays out the administration’s policy on quantum computing – and crucially sets a host of requirements for government departments on documenting and reporting encryption schemes which may be vulnerable to quantum computing.

There has been a growing fear in cryptography and national security circles about the potential for a “cryptanalytically relevant quantum computer” (CRQC) to be used to break most if not all current cryptographic schemes in use.

“The United States must pursue a whole-of-government and whole‑of‑society strategy to harness the economic and scientific benefits of [quantum information science (QIS)], and the security enhancements provided by quantum-resistant cryptography,” said the Biden quantum computing memo.

“This strategy will require a coordinated, proactive approach to QIS research and development…, an expansion of education and workforce programs, and a focus on developing and strengthening partnerships with industry, academic institutions, allies, and like-minded nations.”

Lighting a fire under US agencies

The Biden quantum computingg memo orders agencies all “Federal Civilian Executive Branch” agencies to inventory “their IT systems that remain vulnerable to CRQCs, with a particular focus on High Value Assets and High Impact Systems” within a year.

And within three months, the National Institute of Standards and Technology (NIST) and the Department of Commerce must establish a “Migration to Post-Quantum Cryptography Project” at the National Cybersecurity Center of Excellence. This project will work with the private sector to develop ways to find and fix systems which remain vulnerable to CRQCs.

Along with a large number of other specific requirements, this memo aims to light a fire under the US government to get it moving towards the adoption of quantum-proof algorithms. It specifically excludes “National Security Systems” – but presumably these are being dealt with in a less public fashion.

Notably though, the memo forbids any agency from adopting quantum-proof algorithms until they have been approved by NIST – but it does require agencies to begin testing them: “These tests will help identify interoperability or performance issues that may occur in Federal environments at an early stage and will contribute to the mitigation of those issues.”

Along with the Biden quantum computing memo, the administration issued an executive order establishing a new National Quantum Initiative Advisory Committee, replacing a previous incarnation of the same body created by the Trump administration in 2019. The NQI Advisory Committee is a requirement under the 2018 National Quantum Initiative Act, which authorised spending of $1.2 billion on the US’s quantum computing efforts.

Why should we be worried?

The potential for a quantum computer to break traditional cryptography has been known since 1994, when mathematician Peter Shor published an algorithm which could be used to factor large numbers into primes orders of magnitude faster than a conventional computer. Researchers validated Shor’s algorithm on a quantum computer in 2001, but only on very small numbers.

To be classed as a CRQC, a device would have to work at a much larger scale than any current quantum computer is capable of. And getting to that stage means overcoming significant physics and engineering challenges – but the potential for a CRQC to be developed is real.

As the White House memo puts it: “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.”

The memo names no names, but it is widely understood to be referring to China, which is pouring resources into developing quantum computers. Two of the world’s most powerful quantum computers currently operating are in China, and earlier this year researchers in the country announced a breakthrough in quantum computing performance.

An article in Nature from January 2022 suggests CRQCs are not imminent: “Even the most bullish proponents of quantum computing say we’ll have to wait a while until the machines are powerful enough to crack encryption keys, and many doubt it will happen this decade – if at all.”

So why use quantum-proof algorithms now?

There are two reasons why governments are pushing the development and adoption of quantum-proof algorithms now. The first, and eminently sensible reason is it takes a long time for new cryptographic techniques to become widely used – estimates put adoption time for PQC at around a decade.

The second reason is the fear of “data hoarding” – the idea that malicious actors could be intercepting and caching encrypted data from the internet en masse, preparing for the day it can be decrypted by a quantum computer. No matter when quantum-proof algorthims are adopted, anything encrypted before then is theoretically vulnerable to attack.

While the fear of mass data hoarding may well prove to be overly neurotic – joining such classics as the Millennium Bug and Mad Cow Disease – there is certainly a real potential threat to high-value targets. So from this perspective, dealing with the problem sooner rather than later would also seem sensible.

The good news is, NIST has been in the process of evaluating PQC systems for some years, and expects to release draft standard any time from now until 2024. Hopefully the work being done by other agencies around the world will fall into line with the US government’s efforts.