The Beauty of Cybersecurity and a Post-Quantum World: A World of Lattices, Rings and Errors

The Beauty of Cybersecurity and a Post-Quantum World: A World of Lattices, Rings and Errors

Our existing public key methods are at threat, and RSA and ECC will have to be deprecated in the face of the rise of quantum computers. The methods that RSA and ECC are based on, will that not be a hard problem in the era of quantum computers. So what is the alternative? Well, we turn to the beauty of lattices in search of a hard problem in a post-quantum era.

Lattices involve creating vectors and which are generated from points on a grid. If we have a 2-dimensional lattice, we have an x-axis and a y-axis. Then we could chose two points on the grid, such as p1=(3,2) and p2=(5,-1). Now if we represent these as a vector, to get v1=[3 2], and v2=[5 -1], and where the vector starts from the origin (0,0) point. So how many vectors are now possible for integer values? Well, there will be an infinite number, of which we get:

v=a v1 + b v2

and where a and b are integer values. Let’s start simple with the points of (2,0) and (0,2) [here], and see how our grid and vectors look. The vectors we have are v1=[2 0] and v2 = [0 2], and where we have vector at v3 = v1 + v2 = [2 2], and another at v4 = 2 v1 + v2 = [4 2] (Figure 1):

The difficulty in lattice cryptography is introduced with a small noise vector (e) onto our original vector, and where it is then difficult to find what the actual vector is for our defined lattice (Figure 2). With this we have the Short Vector Problem and Closest Vector Problem. For Close Vector Problem we must find a grid point in our lattice (L) and which is the closest to our original point. With the Short Vector problem, we must find a short vector (one that is close to the orgin) and not a long vector (and one which is far away from the origin).

And so while finding a short vector and the closest point looks easy on our grid, in real-life we will have 10s of thousands of co-ordinates, and not two in our example. We must then generate 10s of thousands of co-ordinates, and search for the nearest point to the original point. At the present time, no computer on the planet can do this, and even quantum computers will struggle greatly. We thus have a quantum robust cryptography method.

So let’s plot the grid for these vectors for v1=[3 2] and v2=[5 -1] [here]:

In this case, we are only showing the positive values for the resulting points. Here is some sample code for generating the lattice:

We use lattice cryptography with a method such as RLWE (Ring Learning With Errors):

With this we use matrices to perform our public key operations, and over lattices.

Conclusions

And so, we need to move away from our existing public key methods, and lattice cryptography should give us a foundation for the future of digital signing.