UK agency warns post-quantum cryptography migration will be ‘very complicated’

New guidance published Friday by the United Kingdom’s National Cyber Security Centre (NCSC) has cautioned that the migration to post-quantum cryptography will be “a very complicated undertaking.”

As explained in the NCSC’s blog post, more than just mathematics will be necessary to meet the threat that quantum computers pose to traditional public-key cryptography, as some systems — such as those controlling critical national infrastructure — would simply not be capable of running the resource-heavy software used in post-quantum cryptography.

Ultimately, the security of public key cryptographic systems relies on the mathematical difficulty of factoring very large prime numbers — something that traditional computers find exhaustingly difficult.

However, research by American mathematician Peter Shor published in 1994 proposed an algorithm for finding these prime factors with far more ease, undermining some of the key assumptions about what makes public-key cryptography secure.

The good news, according to NCSC, is that while advances in quantum computing are continuing to be made, the machines that exist today “are still limited, and suffer from relatively high error rates in each operation they perform,” writes the agency’s head of crypt research, John H. (Surnames are not published for most of its staff.)

But the agency warns that “in the future, it is possible that error rates can be lowered such that a large, general-purpose quantum computer could exist,” but it is “impossible to predict when this may happen.”

That does not mean that the risk doesn’t exist today, as contemporary attackers could be collecting and storing data today for decryption “at some point in the future.”

“Given the cost of storing vast amounts of old data for decades, such an attack is only likely to be worthwhile for very high-value information,” states the NCSC blog.

As such, at least for the subset of organizations that have access to this kind of very high-value data, the possibility of a cryptographically-relevant quantum computer (CRQC) existing at some point in the future is a relevant threat right now.

To that end, numerous organizations and researchers have been attempting to develop a new kind of cryptography that would not be broken by a quantum computer — including the Dilithium standard proposed by Google.

Known as post-quantum cryptography (PQC), the work to develop a standard has continued at pace since 2016 when the U.S. National Institute of Standards and Technology (NIST) started soliciting comments on what such a cryptographic system could look like, resulting in draft standards being published in August of this year.

But even if a standard achieved universal acceptance as something that would be unbreakable by a quantum computer, that wouldn’t be enough to completely solve the issue. As NCSC writes: “Migration to PQC requires more than just new algorithms.”

Whole “protocols and services need to be re-engineered, because PQC typically places greater demands on devices and networks than traditional [public-key cryptography].”

Upgrading major internet services is likely to be one of the easier aspects of the transition, but legacy and sector-specific protocols such as those used in critical national infrastructure (CNI) is likely to be a significant challenge, because PQC requires more resources than public-key cryptography and much CNI is dependent on “devices with constrained resources, and on legacy systems that are hard to upgrade.”

The owners of these systems will need to plan for the PQC transition “as a part of scheduled technology refresh cycles,” but the good news is that for the majority of individuals and organizations relying on major service providers, the transition is largely expected to happen behind the scenes “because of the years of work already done by cryptographers, software engineers, hardware designers, security architects, and many other cyber security specialists worldwide.”