In my long-distance cryptography course, an assignment covers lattice-based cryptography. It is hard, and I am lost. There is no one to help me.
Thus far, I have understood that:
Lattices are a collection of regularly ordered points in Euclidean space (its terms like this which have caused me to search for answers for days).
A lattice may be defined through n vectors called a basis where n = the dimension (for now, I am working in dimension 2), and any other basis can be found by applying positive or negative multiples of each vector in the basis to another vector in the basis.
Defining a lattice L1 as a set of points allows one to multiply the whole set by some co-efficient which will essentially transform it into a new lattice L2.
The determinant of the vectors of the basis essentially tells us the volume (area in 2 dimensions) of the parallelpiped, which will be repeated to form the lattice, the lattice points being the vertices.
But now I am stuck: how do I move all of this to cryptography? I am on a question that asks me to compute the output for 3 inputs to a function:
We will see that q-ary lattices give provably collision-resistant hashing. We choose integers q; a and b. Our hash function (presented by Mikl´os Ajtai in a breakthrough paper in 1996) is a 2-variable function: h(x, y) = ax + by mod q. (a) For q = 5; a = 14; b = 13; compute h(17, 8), h(21, 16) and h((17, 8) - (21, 16))
Having found the answers…
h(17, 8) = 14*17 + 13*8 = 342 mod 5 = 2; h(21, 16) = 14*21 + 13*16 = 502 mod 5 = 2; h((17, 8)-(21, 16)) -> (h(-4, -8) = 14*-4 + 13*-8 = 160 mod 5 = 0
I believe this means that with the first two points the lattice has been moved by some multiple of 5 plus two, which has displaced it by two and thus formed a new lattice. While in the last case, the lattice has been moved by a multiple of its determinant and thus is the same lattice.
However, I cannot understand the link to hashing. In an application, would the points be the cleartext and the answer be
modulo 5 of the output of the hash function? If so, wouldn't there be too many collisions? We have already seen two examples that resulted in an answer of
2. How exactly is this linked to the shortest vector problem or short integer solution if they are not the same thing? Are q-ary lattices only an attempt to store the basic pattern needed to reproduce the lattice? And if so, wouldn't the lattice itself be the cleartext and the basic pattern (given by the basis and the determinant) the answer from the hash function? How exactly would you encrypt a message using a lattice?
I wish I could find some text explaining this in English rather than symbols… like this . Hopefully, I have not been repetitive.