An Introduction to Post-Quantum Public Key Cryptography

Quantum computers are not yet commercially ready and not easy to build, but they promise to outperform today's existing supercomputers¹. History has proved that technology that seems complex today will reach commercial use in the future, and building quantum computers and using them is surely not feasible now, but that might not always be the case in the future. In fact, many organizations like Google, IBM, Microsoft are doing a lot of research to bring quantum computers into being for practical use.

If quantum computers become ready for commercial application, what will be their use, and what impact will they have? Foreseeably, their use is going to be enormous, and this may benefit many industries and even change our lives. Some of the areas that could benefit are artificial intelligence and machine learning, computational chemistry, drug design, weather predictions, and the list goes on⁶.

Though there are a lot of benefits to be expected from quantum computers, they pose a huge risk for public key cryptography, which is the backbone of all secure connections on the internet today. 

In this article, we will discuss the impact quantum computers are predicted to have on public key cryptography based on the topics listed below:

• Quantum computers
• Public key cryptography
• Quantum threat to PKI
• Shor’s and Grover’s Algorithm
• Post-quantum Cryptography
• Post-quantum Migration

Quantum computers

Though quantum computers are in their initial stage, the research and the speed at which the inventions are taking place can make them operational in a decade or two³. Quantum computers can replace supercomputers, which are classical computers with thousands of classical CPU and GPU cores. In 2017 IBM started working with clients on a new generation of electric vehicles with quantum battery technology aimed to reduce atmospheric carbon emissions using quantum computing-aided material discovery⁵.

Quantum computers are systems that use the properties of quantum states to perform computations. In today's computers and PDA devices, the data is represented in bits as 0 or 1, but in quantum computers, 0 and 1 exist simultaneously in different combinations at the same time. The ability to exist simultaneously at the same time is called superposition². 

Quantum bits are constituted of a physical system made from the spin of an electron or the orientation of a proton. Electrons, when they spin, behave like tiny magnets, and this orientation always results in 0 pointing up and 1 pointing down. Similarly, a photon behaves like an electromagnetic field with 0 as horizontal polarization and 1 as vertical polarization. These properties of spin and orientation can be found in many different arrangements, forming the basis for quantum computing and linked together with a property known as quantum entanglement².

In the rest of the article, we will see how quantum computers are going to impact public key cryptography which is the backbone of all secure connections.

Public key cryptography

Public key cryptography (PKC) is the basis for today's secure interactions over the Internet. Public key cryptography is asymmetrical, meaning it uses two keys: one is public, which is shared with everyone, and the other is a private key used by the system to prove its identity. The client sends a message to the receiver by generating the hash of the message and encrypting it with the public key. The server uses its key, the private key, to decrypt the message, which can be decrypted only by the corresponding private key and not with any other key, even in case of a middle man attack⁴.

The server proves to the client that it is the intended server and no one else by showing a certificate obtained from the Certificate Authority (CA). The CA follows all required PKI standards and guidelines to issue a certificate to the server and signs it with its private key. The client validates the digitally signed certificate with its trust store, which contains the public keys shared by the CA. Once the certificate has been validated, the client and server establish a symmetric key for the rest of the session because the asymmetric key is slower than the symmetric key.

The keys provided by the CA are used by the algorithm to encrypt and decrypt the plain text. The RSA algorithm, named after its inventors Rivest, Shamir, and Adelman⁴, is the most used among such algorithms.

The keys, both public and private, are prime numbers. In the asymmetric key setup, two prime numbers are taken, p and q, which constitute the private key. Their product p · q constitutes the public key. It would be easy for small numbers p and q to find its prime factors. For example, if the number 15 was given as the public key, then factoring 15 into prime numbers yields 3 and 5. If the same number has 200 or 400 digits,  though, factoring it into its prime numbers is difficult for any current, classical computer, and it would take millions or trillions of years.

Quantum threat to Public Key Cryptography

The difficulty of factoring prime numbers has allowed public key cryptography to work for many decades without any issues. But with the creation of quantum computers, public key cryptography is at risk because factoring large numbers into primes could take only hours. The National Institute of Standards and Technology (NIST) predicts³ that quantum computers will be fully operational in a decade, and they will be able to break asymmetric key cryptography. Once factoring becomes possible, encrypted data that is considered safe today will be easily decrypted. In other words, data that are encrypted and stored now can be decrypted once quantum computers are available.

The algorithm used in quantum computers to factor numbers was proposed by mathematician Peter Shor. We will discuss its impact on PKC in the next section, along with Grover’s algorithm.

Shor’s and Grover’s Algorithms

Peter Shor showed⁴ how to factor a number using quantum computers with the effect of reducing the time required from years down to hours. Shor's algorithm can be used to target asymmetric keys, which are the basis for the PKI. If Shor's algorithm ever becomes practical, then any existing keys and data that are stored anywhere need to be re-encrypted.

Shor's algorithm would impact the key exchange to generate the session keys used to encrypt the data. An eavesdropper can record the encrypted session, and later when quantum computers become available, easily decrypt it. An eavesdropper can also forge the digital signatures a client uses to authenticate the server certificate, resulting in data integrity and authentication loss.

Shor’s algorithm consists of the following steps:

Choose a random positive integer m. Compute the greatest common divisor GCD using the euclidean method (m, N) where N is the set of natural numbers N={1, 2, 3, 4, 5…….}. If the greatest common divisor GCD(m, N) != 1, then the value obtained is a non-trivial factor of N. But if GCD(m, N) = 1, then we need to determine the period.

This step involves finding the period r of the function f(x) = a^x mod N., That is, we need to find the smallest value of r such that f(x)= f(x+r). This step can be brought into use only with a quantum computer.

If r is an odd number, then we need to start over from the beginning, else we’ll proceed to the next step.

If m^r/2 + 1 = 0 mod N, then we again need to go to step 1, or else we need to compute the greatest common divisor of (m^r/2- 1, N) using the Euclidean algorithm. Finally, we obtain all non-trivial factors of N.

Let’s summarize the above steps with an example.

Step 1 - Let the number to be factorized be N, in our case N is 15.

Step 2 - Choose a random number between 1 and N let’s call this m, i.e between 1 and 15 let's take m=4.

Step 3 - Find the GCD(N,m). We can use Euclid’s Division Algorithm to find it. If GCD is not equal to 1 then it is a factor of N. In our example GCD(15,4) = 1, so we move to the next step.

Step 4 - In this step, we need to find the smallest positive integer r such that, if  f(x) = kˣ mod N, then f(a) = f(a+r). This can be achieved in our example as follows.

Step 4.1 - Let’s define a variable q=1. Then we will calculate q*m mod N. If the remainder is 1, let's move on to the next step else we repeat the step until we get the reminder 1 by setting the value of q to the reminder we got from the previous step as in:

1 * 4 mod 15 = 4

4 * 4 mod 15 = 1

Since we did two transformations to get the reminder 1, the value of r is 2. If r is odd we go back to Step 2 and choose a different value for m, else we move on to the next step.

Step 5 - To find the factors f1 and f2, we use  f₁ = GCD (p+1, N) and f₂ = GCD (p-1, N). To find the value p, we define p equals the remainder in the (r/2)th transformation. In our case, it is 4, i.e the (2/2)th transformation. 

Step 6 - The factors of N i.e 15 are 

• f₁ = GCD (p+1, N), i.e. f₁ = GCD(5,15) = 5.
• f₂ = GCD (p-1, N) is f₁ = GCD(3,15) = 3.

Grover's unstructured key search algorithm⁴, on the other hand, could impact symmetric key encryption. Grover's algorithm uses amplitude amplification to search an item in a list. While it would take a classical computer N/2 or N steps, Grover's amplification trick only requires the square root of N steps. A quadratic speedup is a time saver to search items from a long list, but the algorithm has to be executed sequentially to achieve its full quadratic speedup.

Since much parallel processing happens in quantum computers, Grover's algorithm cannot be applied as it requires serial processing. If serial processing is taken into consideration, then the impact of Grover's algorithm on symmetric key encryption is less relevant, and using AES 128 will remain secure. In fact, the symmetric key used in AES can be brute-forced using Grover’s algorithm, in roughly 2⁶⁴ iterations for a 128-bit symmetric cryptographic key, or in roughly 2¹²⁸ iterations for a 256-bit key. Hence having a symmetric key of double-length will protect from future quantum attacks.

Post Quantum Cryptography

In order to address the challenges posed by quantum algorithms, post-quantum cryptography⁴ will aim to make it difficult for quantum computers to break digital signatures.

Several post-quantum cryptography (PQC) solutions have been proposed, like Lattice-based, code-based, multivariate polynomial cryptography, and hash-based signatures⁴. Most PQC algorithms will use a larger key size, for example, AES with keys greater than today’s 128-bit keys. If a large key size is required, changes have to be made to various Internet protocols like Transfer Layer Security (TLS) protocol or the Internet Key Exchange. But none of the above proposals have shown to be the perfect solution for quantum threats, as NIST's Report on Post-Quantum Cryptography (NISTIR 81051) concluded.

It is likely we will have different algorithms for different types of applications because of a number of implementation constraints. One such example is the key size: a large key could be suitable for some applications, but not for others. PQC will develop different standards for new applications to be able to defy both traditional and quantum challenges.

While active research is ongoing to find a solution for existing cryptography, another totally different solution has been proposed: Quantum Key Distribution (QKD)⁴. In a network, when two parties communicate through a secure channel, it is still possible for an evil person to look at the ciphertext.  With QKD, an eavesdropper can be detected before sending any secure information and the communication between two parties can be stopped in the first place. When an eavesdropper interferes, it affects the quantum state and thereby two parties will come to know about the alteration.

Quantum Key Distribution is the process of transferring symmetric keys securely during the execution of PQC algorithms.  For classical systems, sharing the secret symmetric keys through an untrusted medium is going to be a challenge in quantum times. QKD attempts to solve it. In fact, different key distribution algorithms exist using public key schemes that are not RSA or ECC, but QKD offers security guarantees rooted in the laws of physics. Furthermore, it will be resilient to quantum attacks. The reason for this is QKD is achieved by encoding the data using quantum states of light, which is impossible to break for an attacker⁵.

In the PQC era, applications should be able to handle more than one cryptographic algorithm to process both quantum and classical ciphers. Using hybrid key mechanisms would enable new applications to safeguard themselves from quantum threats while maintaining the traditional standards. Eventually, organizations need to prepare for new encryption standards.

Post Quantum Migration

The migration from classical cryptography to quantum-safe cryptography has to be done in a staged manner. This includes compiling a list of inventories of applications that will be in use 10 or 20 years from now, as well as preparing migration and execution plans for the implementation of post-quantum cryptography. The organization should consider any new projects in its long-term roadmap with the quantum threat in mind. Migration has to be done with complete knowledge of the assets and evaluating them in view of the quantum threat. In some cases, the organization might depend on 3rd party software which needs to be assessed, and it should be listed as part of the migration plan. In the case of the PKI strategy, for example, the CA does not change, but the implementation will vary.

While preparing the migration plan, a complete assessment has to be done, including deciding whether the application needs to be migrated at all. In fact, some of the systems can be retired or made obsolete during the redesign. Most organizations follow the PKI strategy for their applications, and certificates issued by the CA will need to be re-issued with quantum-safe certificates. The application may need to consider backward compatibility to support hybrid certificates in some cases.

If a PKI is ready to support the new quantum-safe cryptography, the trust certificates and the certificate chain validation must be updated. When the organizations using the PKI are prepared to move to the quantum-safe PKI, the intermediate and root certificates have to be updated in the store. So, the migration plan should consider the CA's migration plan before migrating to quantum-safe PKI. The stored data which are being used in secure communication need to be migrated because they are vulnerable to future quantum attacks. Risk analysis can be performed, and if any in-tangible assets are found, they can be moved to an identified quarantine zone.

The standards are not in place, yet, but the pace of research is growing. The standard will eventually be ready and everyone should be prepared to migrate to it. Once the new standards are put in place, and organizations adhere to the new PKI standards, the users of the certificates and the organizations producing the self-signed certificates should be aware of this change and get ready for the migration. The migration to the new standard involves understanding the existing PKI standards and the quantum-safe standards to come in. 

Conclusions

In this article, we provided a short introduction to current PKC architecture and described the impact quantum computers could have on public-key cryptography.

Though quantum computers are in their infancy, their further development could make them commercially available at a reasonable cost, with multifold impact. When that day comes, all public and private keys will be exposed to quantum threats, a massive risk for every organization. Though public key users do not know the internals of how their data is transferred in a secure way, understanding quantum computing growth and the impact it may have on cryptography is key for everyone, irrespective of their role.  

Understanding what and how to migrate to the new, yet to come, quantum-safe cryptography standard is vital for everyone, from the CEO to the engineer implementing it. The migration involves budgeting, planning, migrating, developing, implementing, executing, and ensuring a hybrid implementation is in place.

References

1. ai.googleblog (2019, October 23) Quantum Supremacy Using a Programmable Superconducting Processor

2. Azure.Microsoft Superposition, and entanglement

3. NIST computer security resource center 

4. Wikipedia Man in the middle attack, RSA cryptosystem, Shor's algorithm, Grover's algorithm, Post-quantum cryptography, Quantum key distribution

5. IBM Quantum Computing, QKD quantum key distribution

6. Top Applications Of Quantum Computing Everyone Should Know About, 20, Mar 2020