# Threats posed by Quantum Computing to Public Key Encryption (PKE)
source: https://developer.mastercard.com/blog/threats_posed_by_quantum_computing_to_public_key_encryption/index.md

Authors: John Beric. Overview This blog post is the second in a three-part series on Public Key Encryption (PKE), the threat posed to it by Quantum Computing and how these threats will be addressed. In this post we will cover possible threats posed by Quantum Computing to PKE and highlight how the next generation of PKE methods will secure us against this threat. Is there a problem with today's public key algorithms as a bootstrap mechanism for secure communication? There is a theoretical quantum computer algorithm called Shor's algorithm, which can only execute on massive quantum computers that as-yet do not exist. This algorithm breaks our current standardised public key algorithms (known as RSA, ECC and DSA). Although on the face of it these appear to be wildly different, their security relies on the difficulty of the same underlying mathematical problem. Shor's algorithm solves this single underlying problem. For example, in the RSA context, Shor's algorithm enables the discovery of the secret prime factors of 600-digit numbers in days (Remember from the previous blog post that this factorization is the mathematical foundation for RSA). This means RSA, and indeed the other of today's standardised public key algorithms, would no longer be fit for purpose should bad actors one day gain access to these as-yet non-existent powerful quantum computers. Communications secured by today's public key algorithms (RSA/ECC) would become vulnerable to compromise. This is an incredible leap-change showing a staggering advantage of quantum computers over classical computers. Shor's algorithm solves a problem in days/weeks that would be impossible using conventional methods. A far as I know, Shor's algorithm is only useful for breaking current public key cryptography and by extension the current security technology of the internet. How does Shor's algorithm work? Contrary to popular conception, although very understandable, quantum computer algorithms do not perform multiple independent calculations in parallel. If I have to calculate the average value of some formula over a large set of numbers, for a conventional computer, I would make the calculation for all values one by one, add the answers up and divide by the number of data points to obtain the average value. Instead with a quantum computer this average is calculated in one step, the quantum computer perceives the huge pool of numbers as a single "value", and it performs a single calculation to obtain a single output value. The quantum computer magic, in at least some algorithms, comes from this ability to calculate an average value of a formula on lots of inputs without having to evaluate the formula for each individual value. In the instance of Shor's algorithm applied to factorise a 600-digit RSA public key (remember this public key is the product of two 300-digit numbers), the algorithm requires the quantum computer to be initialized with all values from 1 to a 1200-digit number that depends on the RSA public key value under attack. All these values must be stored simultaneously in working memory (pause here, this is staggering). This is possible for a quantum computer as a result of something called superposition. A conventional computer the size of the Earth could not do this. Shor's algorithm proceeds by calculating an average on the initial pool of values and then using the calculated average to guide a cull of the pool of values and repeats this process until only one number is left. The final and solitary average value is cunningly constructed to be a number called the period which directly leads to a factorisation. Through bad luck the one number left might lead to the digit 1 which is a trivial factor of all integers or to the other trivial factor, the target number itself, this too is a factor of course. However, the most probable outcome is a genuine factor. This exposes a feature of many quantum algorithms namely that they are inherently probabilistic and might not give the answer you want every time, and the calculation will need to be run again. Wow! when we will be able to run Shor's algorithm and break our current public key algorithms? Not yet, and, according to the NSA maybe never. The timeline for this becoming a real threat is objectively unknown, the best we have is frankly informed guesses, no one really knows. In the absence of facts, hype abounds. From my knowledge and reading it appears extremely unlikely that current public key techniques will be vulnerable in the next 10 years. It is widely believed that there is a performance gap of 5 to 6 orders of magnitude between today's quantum computers and quantum computers capable of breaking public key algorithms (see https://sam-jaques.appspot.com/papers and look in the tab labelled "Other". N.B. the graph scales are logarithmic!). The judgement call is estimating the velocity of the reduction of this gap. Assuming a Moore's Law type rate of improvement then the threat may become real in the early 2040s. There is a non-zero chance that large scale performant quantum computers of a size to break RSA/ECC will be uneconomic to build ever, again no-one really knows. In summary, the performance gap is well understood, and with each passing year more data to estimate the gap closing velocity becomes available, and by 2025 we should have a better idea of threat timelines. To repeat, it is extremely unlikely the performance gap described above will be closed within the next 10 years. What are we doing about the threat Shor's algorithm brings? Given the problem is that existing public key standards are under threat, the most important initiative and task of course is to create new standards. The global cryptographic community has been mobilised under the auspices of NIST, the US government's standardisation body, to develop new public key algorithms resistant to quantum computer attack. NIST are 6 years into an 8-year first phase program. An extremely thorough candidate algorithm sieving process has completed and preparation of final standards will begin shortly. Publication of these standards should happen in the next two years. Then given almost all of us directly rely on an internet security standard known as TLS, which, itself relies on public key algorithms, TLS will be updated. The software update for consumers will be easy; browsers will update transparently. However, the supply chain that creates the foundational cryptographic material e.g. trusted directory infrastructure (called Certification Authorities) will be severely impacted and will undergo a major rip and replace exercise. Clearly, we cannot migrate to new standards until they are ready, what can we do in the meantime? Public key cryptography is an infrastructure component like a gas pipe. Most of us do not build gas pipes or equipment that pumps gas around a grid. Almost all of us use public key technology encapsulated in products we buy rather than ones we build. Indeed, many of us will not have noticed the replacement of a cryptographic standard called SHA-1 which is a good analogy for what will need to be done for public key. It is good and common IT hygiene practice to have a software bill of materials with important information alongside each piece of software e.g. last update, next update, patch level etc at some point new columns indicating for each piece of software RSA/ECC reliant or not and whether it was in-house developed/bought-in should be added. This database is an important management tool. For most of us there will be no in-house developed ECC/RSA reliant software and for us it is a case of using hardened products as they are made available. However, if you are not just an ordinary user then you will be: Tracking the standardisation process Planning an integration of final standards into products Tracking the quantum computer R\&D progress timeline Thinking about rolling hardened product out to the user base Building in crypto agility Using non-public key algorithm key management in closed user groups with trusted operators e.g. relying on direct symmetric key distribution using a pre-1970s model where the trusted operator ensures group interoperability As regards symmetric cryptography, NIST has declared that AES-128 is entry level quantum resistant, since AES-128 is also entry level classical computer resistant no action beyond continuing the current adoption of AES-128 or better is required, the community has benefitted from a lucky break! We will however need a migration at some point Migration timescales are subject to the cost, quality, timescale triangle trade-off. Public key migration will be more complicated than the phasing out of SHA-1 which took about ten to fifteen years -- there was no real urgency and the migration was conducted slowly. On the other hand, the fallout of Snowden's revelations caused major internet changes within 18 months. More recently modifications as a result of the log4j vulnerability happened in days. The overwhelming probability in dealing with the quantum threat is that we will be allowed a measured migration and we will not need a panic-driven migration. Upgrading software is always painful but it is BAU - Microsoft are currently upgrading from Windows 10 to Windows 11. As regards hardware, any consumer device equivalent to or more powerful than the cheapest mobile phone will not notice the public key algorithmic change, chip cards and other computationally constrained devices "as is" may not necessarily to able to support the new algorithms if sub second response times are required for key set-up. However, these contexts are unusual, and almost always there will be a mitigation strategy of some sort. Economics will determine whether to upgrade the constrained device in a given context of use or to fall back directly to symmetric key cryptography to manage key distribution with its increased management overhead costs.