Types of post-quantum cryptographic algorithms

As technology continues to evolve, cryptographic solutions face new challenges. As quantum computers become more and more commonplace, their large computing capacity is threatening the cryptographic methods currently in use.

To help companies prepare for these challenges in time, the National Institute of Standards and Technology (NIST) has launched the Post-Quantum Cryptography Standardization competition. This process is used to develop, evaluate, and standardise cryptographic algorithms that show promise for potential attacks with quantum computers. Such algorithms are called quantum resistant algorithms or Post-Quantum Cryptography (PQC) and can be classified into different families of algorithms.

Now, let’s look at these families in broad terms.

Lattice-based cryptography

The lattice is a mathematical structure containing points in a repeating pattern. At first glance, they appear simple, but they hide serious mathematical problems. These problems serve as the basis for Lattice-based cryptography, which are expected to be difficult for a quantum computer to solve.

A two-dimensional lattice is defined by two basis vectors, i.e., each point on the lattice can be traversed by combining the two basis vectors. Of course, the same two-dimensional lattice can be defined by two other basis vectors.

Let’s look at a mathematical problem. Find the lattice point that is closest to, but not equal to, the origin of the lattice. In two dimensions, you can find the solution by combining the two basis vectors, but the higher the dimension of the lattice (i.e. the more basis vectors you have), the harder it is. We call this Shortest Vector Problem (SVP). Another similar problem is to find the lattice point closest to an arbitrary point in space. This is called Closest Vector Problem (CVP).

But how can this be used in cryptography?

Fact: With some basis vectors, it is easy to solve the problems mentioned earlier (good basis), but not with some basis vectors (bad basis).

A simple way to use this is to use a good basis as a private key and a bad basis as a public key. When Bob wants to send a message to Alice, he uses Alice’s public key to select a point on the lattice that represents the information to be encrypted. It then specifies a point in space close to this lattice point.

The attacker can only know the public key, but since it is the wrong base, it is difficult to solve the problem with it. Alice, on the other hand, knows the private key, which is a good base, so she can easily solve the problem and decrypt Bob’s message.

This scheme is called Goldreich-Goldwasser-Halevi (GGH) encryption scheme, but it is not secure. However, using the Learning With Errors (LWE) mathematical problem, we get a sufficiently secure lattice-based cryptography. Examples of lattice-based algorithms include Kyber or Dilithium.

Code-based cryptography

It is based on the idea that a matrix is used to encrypt and decrypt the message. A simple example is to imagine a codebook that tells you what code to substitute for each character in the message. This turns the message into a seemingly random sequence of codes. To recover the original message, the process must be reversed.

It is easy to see that the security of the process depends on the secrecy and complexity of the codebook.

But how?

This is where error-correcting codes come in. These are mathematical constructs that detect and correct errors in the data. They hide errors during encryption, and then correct them during decryption.

An example is the McEliece cryptosystem. It is resistant to Shor’s algorithm, which can break RSA.

Hash-based cryptography

Imagine a machine in which any length of data is entered, and the result is a unique fingerprint of a fixed length. If we change the input data even slightly, we get a different result. This machine is called a hash function.

Hash-based cryptography is a method of protecting data using hash functions. The beauty of hash functions lies in their one-way nature – it is easy to compute the hash value from the input, but extremely difficult to reverse the process and get the original input from the hash value.

Useful in many applications, such as password storage, data integrity or digital signatures.

And the best part: hash functions are said to be resistant to attacks from quantum computers.

Non-commutative cryptography

It is based on non-commutative operations interpreted on algebraic structures. But what is a non-commutative operation? In short, it is the order of values in the operation that counts. For example, on a set of real numbers, division is non-commutative, since 1/2 ≠ 2/1. Conversely, addition is commutative, since 1+2 = 2+1.

A simple example is that a lock can only be opened by combining several keys and the order of the keys is important. To unlock it, you not only need to have the right keys, but you need to use them in the right order.

The procedures depend on the difficulty of solving problems interpreted on such algebraic structures. An example of such a problem is the Hidden Subgroup Problem (HSP), where the task is to find a hidden subgroup within a group.

A practical example in broad terms: a private key contains elements within a non-commutative group combined in a specific way, which allows efficient decryption. A public key contains elements from the same non-commutative group, but hides the information contained in the private key. The structure of the public key exploits the difficulty of solving HSP. An attacker would essentially have to solve the HSP with the elements in the public key, which is difficult even for a quantum computer.

Multivariate cryptography

Here, security is not provided by one big hard mathematical problem, but by a bunch of smaller, but interrelated problems.

In the case of Multivariate Public Key Cryptosystem (MPKC), a set of multivariate equations is given. The equations are contained in the public key and their solutions in the private key. So, when Bob sends a message to Alice, he encrypts the data using these equations. And Alice can decrypt it using the solution to the equation.

The attackers only know the encrypted data and the equations. Without a private key, they run into the Multivariate Quadratic Problem (MQ Problem), which is hard to solve even for a quantum computer.

As an example, the Hidden Field Equations (HFE) cryptosystem is based on this principle.

Isogeny-based cryptography

These procedures use elliptic curves and functions called isogenies. These functions allow us to move points from one curve to another while preserving certain mathematical relationships. Together, these represent cryptographic challenges even for quantum computers.

The private key contains the secret information that allows us to efficiently navigate the complex mathematical structure represented by the public key.

Supersingular Isogeny Diffie-Hellman (SIDH) is inspired by Elliptic-curve Diffie-Hellman (ECDH), with the difference that it replaces scalar multiplications by isogenies. Its implementation is the Supersingular Isogeny Key Encapsulation (SIKE). For a while it was a promising candidate for post quantum algorithms, but in 2022 it was proven to be insecure.