Post Quantum Cryptography

9 min readOct 21, 2022

It’s an exciting time to work on quantum technologies; quantum computers are nearly upon us. It is a common belief that commercially viable quantum computers will be available within the next twenty years. While we are yet to grasp the implications of quantum effects being fully exploited, we will undoubtedly see significant developments in fields like AI and Data Science, where quantum computing will help us truly understand and make the most of existing data.

Unfortunately, not everyone gets to view the arrival of quantum computers with nothing but excitement. Cryptographers, the practitioners responsible for protecting people’s data and privacy on the internet and beyond, are preparing to see decades of well-tuned techniques for hiding data invalidated by the first wave of sophisticated quantum machines.

Before we get to precisely what Post-Quantum Cryptography (PQC) is, let us first go over the basics of the prerequisites required to understand it.

Cryptography (Classical):

“Cryptography is the practice and study of techniques for secure communication in the presence of adversarial behaviour. Cryptography is generally about constructing and analyzing protocols that prevent third parties or the public from reading private messages.”

That was the Wikipedia definition of cryptography. Basically, what cryptographers do is solve and analyze variants of the following problem:

“Alice wants to send a secret message to Bob, but she has no private channel through which to send this message. Furthermore, she worries that Eve may try to intercept her secret message and obtain the information in the message. So, what can Alice do?”

This is where encryption comes in. Assume that there is a key only known to Alice and Bob. Alice can use this key to encrypt a message (imagine putting it in a locked box), and once Bob receives this message, he can decrypt it (unlocking the box) with the key. Even if Eve intercepts the communication, she won’t be able to make sense of the message (she has the locked box but not the key).

This type of cryptography is known as Symmetric Key Cryptography, as the same key is used in both the encryption and decryption processes.

Figure 1: Overview of Symmetric Cryptography (Source: CryptoQuantique)

However, there is an obvious shortcoming associated with this method. What if Alice and Bob can’t or haven’t agreed on their secret key? In the real world as well, parties are unlikely to have been able to agree on a key in advance. Just think about it, when you enter your bank details to complete a transaction on a website you’ve never been on before, you haven’t agreed on any secret key in advance, yet you don’t encounter any security lapses. This is where we come across the techniques of Public Key Cryptography.

Coming back to Alice, Bob and Eve, in Public Key Cryptography, Bob makes a pair of keys: a public key and a private key. He sends the public key out in the world. When Alice wants to send a message to Bob, she uses the public key to encrypt the message. Once Bob receives the message, he uses the private key to decrypt the message. If Eve intercepts the communication, she only has the message and the public key but not the private key, so she can’t make sense of the message.

Figure 2: Overview of Public Key Cryptography (Source: Tutorialspoint)

So, the question is, how secure is Public Key Cryptography? If Bob can decrypt a message encrypted with a public key using a private key, there must be some relationship between these keys. Thus, all Eve has to do to read the message is extract the private key from her knowledge of the public key and the encryption scheme. Therefore, the scheme’s security is directly proportional to the computational complexity of finding the private key from the public key.

Consider the famous RSA cryptosystem; here, Bob’s public key is a large integer (say n), and the private key is the pair of primes (say p and q) where n = p*q. So, Eve’s task here is finding p and q from n. As simple as it may sound, there is no efficient algorithm (classical) that can find p and q from n. Here, an efficient algorithm refers to one that has polynomial time complexity. This problem is referred to as the famous ‘integer factorization’ problem.

Another famous mathematical problem used to enhance the security of cryptosystems is the ‘discrete logarithm’ problem. In this problem, one has to find n such that aⁿ ≡ b (mod p) where we know a, b and p. The ‘≡’ denotes the modular congruence operator. (Notice how the equation looks analogous to n = logₐb, hence the discrete logarithm name). There isn’t any efficient algorithm (classical) that can find n in this problem as well. This fact is used in the Diffie-Hellman protocol.

This was an overview of classical cryptography and some techniques used to ensure communications security.

The Quantum Angle:

While Classical Cryptography uses the ‘hardness’ of certain mathematical problems to ensure security, Quantum Cryptography (not to be associated with PQC, they are pretty different) uses certain favourable principles of quantum mechanics to do the same. The no-cloning theorem states that it is impossible to create an independent and identical copy of an unknown quantum state, guaranteeing that a message can’t be copied without the sender’s knowledge. Quantum mechanics also provides the ability to detect the presence of an eavesdropper attempting to learn something about the message. This is because when Eve wants to observe something, she must make a measurement. As soon as she makes this measurement, she disturbs the state of the message qubits, which is immediately known to the sender. Via these properties, the security of communication is ensured in Quantum Cryptography. To learn more about Quantum Cryptography and Quantum Key Distribution protocols, follow this link.

PQC:

While quantum mechanics’ properties can help secure communications, quantum attacks can also be powerful enough to render classical cryptosystems obsolete. Shor’s algorithm, developed by American mathematician Peter Shor in 1994, is an algorithm that can factorize an integer on a ‘feasible’ quantum computer in polynomial time. Shor’s algorithm breaks the RSA cryptosystem.

Even worse, the main building block of Shor’s algorithm, the Quantum Fourier Transform, can be adapted to break most other commonly implemented cryptography, such as Diffie-Helman key exchange and Elliptic Curve Digital Signatures. The only reason practices like the RSA and Diffie-Hellman are still in practice is that we don’t have a feasible quantum computer.

To prepare for this eventuality, cryptographers have developed the subject of Post-Quantum Cryptography: the study of cryptography which can be run on classical computers while being resistant to quantum attacks.

We have seen how quantum computers are effective against existing public-key cryptography protocols. However, they won’t be able to provide much improvement on symmetric key cryptosystems. This is because typical symmetric schemes, like the AES, rely on the “fast and efficient” mixing of objects. To decrypt the ciphertext, you must manually perform the unmixing steps. Due to Grover’s algorithm, any symmetric key cryptosystem would incur a significant security loss, but this can be mitigated simply by doubling the key length. Thus, the main focus of PQC is updating public key cryptography.

To update public key cryptography, we need to find problems that are ‘hard’ for a quantum computer as well. Let us look at some of the leading computational problems in PQC. The bulk of proposed PQC schemes lies in one of four main categories: lattice, code-based, multivariate, and isogeny-based cryptography. Let us look over some of the aspects of the first three.

Starting with the most popular category: lattice cryptography. A lattice can be understood as a regular grid of points in space. The points on the lattice are chosen systematically from an object called its basis, which describes the lattice by explaining how you move between lattice points.

There have been computationally complex problems on lattices long before the RSA and Diffie-Hellman schemes even existed. This provides some confidence in the belief that these problems will also withstand quantum attacks.

Figure 3: A Lattice with Two Different Bases

The backbone of lattice cryptography comes from an interesting observation about these bases. Using the green basis, it is straightforward to understand the shape of the lattice and how to get from one point to another using the shortest path. On the other hand, the red basis overly complicates finding paths from one point to another, and it is also tough to verify that there isn’t a shorter path. So, one can consider the green basis as a ‘good’ basis and the red as a ‘bad’ one. This is the idea used in Lattice-based cryptosystems: a bad basis is used as a public key, and a good basis as the private key. The bad basis’s description of the lattice will be complicated enough to hide the message, and only the receiver can solve the problem quickly, as this requires knowledge of the good basis. Lattice cryptography tends to be the most flexible category of PQC since there is a lot of design space to work with regarding how one chooses lattices and hides points.

Code-based cryptography includes cryptosystems whose security relies, partially or totally, on the hardness of decoding a linear error-correcting code. A well-chosen error-correcting code serves as the private key for a cryptosystem based on this, and the accompanying public key is the method of encoding the message. Encryption is straightforward: the sender encodes the message as usual and then simulates an unreliable channel by manually inserting some errors. An adversary without access to the description of the error-correcting code cannot recover the message as long as there are enough errors, whereas the intended recipient can decode it using their error-correcting code. These schemes have huge public keys and compare poorly with existing schemes like the RSA. However, we may see a shift back to Code-based cryptography as they seem secure against quantum attacks.

Multivariate cryptography is based on the problem of solving systems of multivariate polynomial equations. A typical multivariate quadratic equation looks something like this:

This problem is an NP-Complete problem. It is not expected that quantum computers will be able to solve NP-Complete problems. Current schemes in Multivariate cryptography perform poorly as compared to lattice-based schemes. However, it demonstrates potential, and there is hope that we will see tremendous advances in the future.

Standardization:

Standardization is developing a protocol that is fit for practical use based on specific guidelines. In 2016, the National Institute of Standards and Technology (NIST) initiated this process via an open call asking for proposals for post-quantum algorithms and key-encapsulation methods.

The two main features NIST are looking for are security and efficiency: if a protocol isn’t secure, then there’s no point in using it to protect data, and if it isn’t efficient, it will slow down internet communications. PQC tends to perform slower than its pre-quantum counterpart, so an algorithm can be considered efficient if there is little to no drop in performance when using it in place of an existing pre-quantum scheme.

After a proposal is submitted, it is subjected to months of cryptanalysis and is thoroughly examined. Initially, there were 69 proposals submitted. As of now, there are only four schemes selected for further examination. Although these schemes have all been thoroughly vetted, they each come with different strengths and weaknesses that are useful to understand.

Conclusion:

It is not long before we see the first sophisticated quantum computer. To ensure data security, one must start preparing for this eventuality. Keeping up to date with happenings around the NIST process will satiate the curious observer. For people tasked with keeping data safe, they need to consider the pros and cons of each algorithm, factoring in what they need. For your sake and mine, we need to hope that PQC advances fast enough to protect us when the first wave of capable quantum computers arrives.