In lattice-based cryptography we create a lattice structure within a number of dimensions, and then pick a point, and define this as our vector. We then add a small error onto this vector, and the difficult problem is then to find the original vector within the lattice:
Lattice Grids |
Background
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 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 can be used to create any point 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, we get \(\vec{v1}\)=[3 2], and \(\vec{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, and we can generate:
\( \vec{v_3}=a \vec{v_1} + b \vec{v_2} \)
and where a and b are integer values. Let's start simple at take the points of (2,0) and (0,2) [here], and see how our vectors look. The vectors we have are \(\vec{v1}\)=[2 0] and \(\vec{v2}\) = [0 2], and where we have vector at \(\vec{v3} = \vec{v1} + \vec{v2}\) = [2 2], and \(\vec{v4} = 2 \vec{v1} + \vec{v2}\) = [4 2]:
The difficulty in lattice cryptography is introduced with a small noise vector (\( \vec{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 \(\vec{v1}\)=[3 2] and \(\vec{v2}\)=[5 -1]:
In this case, we are only showing the positive values for the resulting points.
Here is some sample code for generating the lattice:
import numpy as np import pandas as pd import sys import matplotlib.pyplot as plt import statsmodels.api as sm import math import numpy import plotly.graph_objs as go title="" def getPoints(x1,y1,x2,y): xval=[] yval=[] xval.append(0) yval.append(0) count=0 for a in range(-10,10): for b in range(-10,10): xnew=a*x1+b*x2 xval.append(xnew) ynew=a*y1+b*y2 yval.append(ynew) return xval,yval x1=2 y1=1 x2=3 y2=-1 title="x1="+str(x1)+",y1="+str(y1)+"x2="+str(x2)+",y2="+str(y2) print title print xval,yval=getPoints(x1,y1,x2,y2) plt.title(title) plt.xlabel('x') plt.ylabel('y') plt.axis([0,max(xval)/2,0,max(yval)/2]) plt.scatter(xval,yval) plt.show()