Executive Summary

Recent advances in quantum computing present serious threats to most public key cryptography in use today.

This necessitates rapid innovation to develop, review, and implement quantum-resistant encryption standards.

The following discusses the well-known Learning with Errors Problem and uses a basic Python app to demonstrate one possible model for quantum-resistant encryption using this problem as the backbone.

Background

Quantum computing is an emergent branch of computing that uses the components of quantum mechanics to process information and has been found to pose a risk to the majority of public key cryptography in use today.

Public key cryptography is the mechanism by which we can send encrypted messages to one another without first sharing a secret key.

This enables us to connect securely to web servers via TLS/SSL, to transfer files to and from file servers securely, and to establish secure tunnels between two networks via the use of VPNs.

After learning about the current state of post-quantum encryption, I set out to develop my own basic post-quantum resistant encryption app, built on the foundations laid by Oded Regev in developing the Learning with Errors problem and explained brilliantly by Kelsey Houston-Edwards and Veritasium, among others.

I chose this problem for the backbone of the app, as it’s been identified as resistant to many of the post-quantum attacks that both RSA and Diffie-Hellman are not, largely due to its close alignment with lattice-based mathematics.

To demonstrate, let’s start by looking at an example of a very simple yet insecure encryption algorithm.

Imagine Ivan wants to send a message to Dana.

Dana has a private list of vectors, which will be her Private Key:

Formatted Private Key

2, 4, 1

She publishes a set of equations, each with as many variables, which will be her Public Key:

Formatted Public Key

1. 2x + 3y + 7z = 23
2. 1x + 2y + 6z = 16
3. 3x + 1y + 2z = 12

The message Ivan wants to send Dana is the number 6 in binary; “110”.

To do this, he can send Dana an equation from her Public Key for each bit, embedding the value in the constant on the right side of each equation by adding one to represent one, and leaving it unaltered to represent zero.

In this example, the message “110” might look like this:

Formatted Message (Encapsulation Equations)

1. 2x + 3y + 7z = 24 (1)
2. 1x + 2y + 6z = 17 (1)
3. 3x + 1y + 2z = 10 (0)

When Dana receives the message, all she needs to do is substitute her private vectors into each equation and solve.

The remainder, after solving, can then be extracted to reveal the message content:

Formatted Message (Encapsulation Equations)

1. ... = 1
2. ... = 1
3. ... = 0

This is clearly extremely weak encryption, as an attacker that intercepts the message could simply solve for the variables using linear algebra.

For an algorithm to be considered cryptographically strong, it needs a few more conditions to be satisfied.

1. The time taken to for a computer to attempt every possible Private Key value must increase exponentially with each increase in the number of variables.
2. The task of decrypting a message without access to the Private Key and without attempting all possible Private Key values must be Hard to solve, meaning there must be no efficient algorithm to solve the problem the encryption is based upon.
3. It must not rely upon security by obscurity, i.e. publishing the full workings of the algorithm must not reduce its strength.

Our example above may adhere to the first and third points, but certainly not the second, as there are numerous efficient algorithms available to solve for the variable values.

Let’s modify our example to transform it into something cryptographically stronger.

The first thing we’ll do is take our Public Key and add some errors.

To do this, we simply take a random number within a known range (in this example, +/-2) and add or subtract it from the known constant on the right-hand side of the equation.

Formatted Public Key

1. 2x + 3y + 7z = 23 + 1 = 24
2. 1x + 2y + 6z = 16 - 2 = 14
3. 3x + 1y + 2z = 12 - 1 = 11

Then hide the errors to show the new, erroneous constants.

Formatted Public Key

1. 2x + 3y + 7z = 24
2. 1x + 2y + 6z = 14
3. 3x + 1y + 2z = 11

This is our new Public Key.

The Private Key remains unchanged.

Now we can see that the task