Lattice: The Easy and Hard Problem

With lattice cryptography, we create a lattice of points and then introduce a small error in the point, and it then becomes a hard problem to find the nearest point to the point with the error.

Lattice cryptography is seen as a replacement for our existing public-key methods. What is so good about them, is that we have a provably hard problem. So, I’m going to show that this is a hard problem, and is based on this YouTube video [here]. In the presentation, we look at the CVP (Closest Vector Problem), and where we have we find the closest point. For simplicity we take two vectors (v_1 and v_2), and which connect from the origin to two points. We then find a solution for:

w = a(v_1) + b(v_2)

If v_1 and v_2 are orthogonal (they are almost at right angles to each other), Baini’s algorithm allows us to find the closest points, if not, we will get an incorrect answer. If we define one vector (v_1) with (5,1) and another vector (v_2) with (-2,8), we get the following lattice [here]:

Now we want to find the nearest point to (27,8). First we determine if the angle between the points is around 90 degrees, and if it is, we should be able to solve for…