PKI header for site page

The Future of Classical Algorithms in PKI Hierarchies

(Compiled and researched by Steve Monti

The days of building new PKI hierarchies and re-keying with RSA and ECDSA keys using lifetimes of 15 years or more are a thing of the past.

We cannot accurately say when a quantum computer will be available that will make practical use of Shor’s algorithm to negate RSA, ECDH, and ECDSA algorithms.

I have been following the Quantum community over the last few years. I am a regular attendant atInside Quantum Computing(IQT) conferences.

I attended the IQT New York conference where the foremost gathering of business leaders and investors focused on the Quantum Internet and related Quantum computing security issues. Approximately 1,000 people attended.

I asked people the popular question relating to the date of a Quantum breakthrough (the question that everybody asks). The consensus ranges from a worst-case scenario of three or five years to possibly ten years.

There is a lot of disagreement on the date, but one thing all people in the industry agree about, is that all companies that rely on RSA, ECDH and ECDSA (which covers just about everybody) should have, at least, an audit of their estate. They should also have some form of cryptographic agility in place in readiness for the deprecation of classical algorithms.

On the optimistic side, at least for buying time, there may be intractable reasons that prevent the scalability of quantum computers into the sort of size required to use Shor’s algorithm.

The well-known problem of decoherence and noise inherent in Qubit scalability may be intractable. However, given the amount of investment pouring into quantum research, these problems are likely to be solved sooner than we think.xMy biggest concern is that the current timeline for a Quantum breakthrough is primarily based on research flowing out of the academic community.

There seems to be an unstated premise that progress (or lack of it) will be gently fed into the PKI community so that we may act accordantly, almost in a leisurely fashion. This is a dangerous illusion.

There is very little mention of the covert ability of a State backed military or well-funded adversary developing a Quantum breakthrough much sooner than five years. Such States or adversaries will not be in a hurry to tell the community.

From my discussions with the large financials and several global institutions there seems to be a feeling that a Quantum breakthrough will be handled by the appropriate cryptographic vendors that supply and support their cryptographic libraries and peripherals. To a certain extent this is partly true.

Cryptographic vendors will be responsible for updating their libraries with quantum-safe algorithms. However, the task of transitioning your classical algorithms will be largely the responsibility of your company.

I am still encountering companies that still have not finished migrating their SHA1 estate. NIST deprecated SHA1 over ten years ago.The migration to Quantum resistant algorithms will beinfinitely more complexand time consuming than migrating from SHA1 to SHA2.


It’s very unlikely that new Quantum-safe algorithms will be able to be swapped out into existing designs. This is especially pertinent in relation to the key establishment process, key size, and signature schemes. In reality the new Quantum-safe algorithms will have much larger public keys and signatures. A great deal of testing will be required to understand the implications of this.

The added complexity of extending compliant PKI estates into your Microservice environments creates a further challenge. You cannot expect or rely on your cloud provider to upgrade your microservice environment from classical to quantum-safe algorithms.

Finally, I have been building PKI hierarchies for over twenty years, the days of building new PKI hierarchies and re-keying with RSA and ECDSA keys using lifetimes of 15 years or more are a thing of the past.

Shor’s Polynomial algorithm is not going to be deterred by increasing your RSA key size or using ECDSA keys.

You need a very good crypto agile plan for when NIST deprecates your RSA and ECDSA keys.

Written and compiled by Steve Monti using insights and associations gathered at Inside Quantum Technology conferences.