# Help in understanding exactly how lattices used as one way functions for hashing

I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers and videos in an attempt to build my understanding of the subject, but due to the intensely technical manner in which information on the subject is presented, I have not been able to answer many questions in my mind. Due to the structure of my long distance course I have no access to professors or extensive libraries so my question is one which merely seeks to increase my understanding, please bear with 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 be searching 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.

Having said this, I am now stuck in understanding how I move all of this to cryptography. I am on a question which asks me to compute the output for 3 inputs to a function:

We will see that q-ary lattices give provably collision-resistent 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))

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 just cannot understand the link to hashing. In an application would the points be the cleartext and the answer modulo 5 the output of the hash function? If so would'nt there be too many collisions as we have already seen two examples of which give the answer 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 aonly 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 just wish I could find some text which explained this in English rather than symbols… like this http://www.wisdom.weizmann.ac.il/~odedg/COL/cfh.pdf . I really hope I have not repeated any questions through my lack of understanding. Thanks in advance.

-
There are six questions and the final one is on encryption. Can you divide them? –  xagawa Feb 6 '14 at 14:18
@xagawa Sorry about that I was sort of pulling the areas on which I was confused out of my head. Probably an answer to the link to hashing would clear most of it up. So how exactly are q-ary lattices used for hashing in terms of the example given? –  user2012620 Feb 6 '14 at 14:22
The note you refer starts from the definition of the Ajtai hash functions. What does confuse you? –  xagawa Feb 6 '14 at 14:25
@xagawa I understand that Ajtai developed a new method for hashing, and it is clear to me that using this function (Ax mod q) all answers will me mapped to a range 0 to q. However, a hash function, in my understanding is supposed to sort of 'shrink information' My confusion stems from the fact that I dont see the relevance of the points. They were not bases for the lattice.. Take a message m, encrypted to e and then hashed h(e). I know that m is whats of importance. Im just trying to wrap my mind around what exactly would be encrypted. Additionally, the example shows a collision... –  user2012620 Feb 6 '14 at 14:31
you wrote "I just wish I could find some text which explained this in English rather than symbols". I'm afraid you're not likely to be able to understand this without mathematics (i.e., symbols). I don't mean to be rude, but you might want to consider the possibility that you do not have the necessary mathematical background to understand the answers to the questions you posed. Perhaps you are better off either focusing on strengthening your math skills, or moving to a different topic where you do have the preparation. –  D.W. Feb 7 '14 at 3:27

I'm also afraid you couldn't understand this as D.W., but let us start. I sometimes cannot understand your questions. Please restate them, if possible.

# The definition of the Ajtai hash functions

Let $n$, $m$, and $q$ be positive integers. Let $R = \mathbb{Z}_q$ be the quotient ring of integers modulo $q$. Let us define a function, which maps a vector in $D^m \subset R^m$ to $R^n$ and is indexed by a matrix $\boldsymbol{A} \in R^{n \times m}$ as follows:

$f_\boldsymbol{A}(\vec{x}) = \boldsymbol{A} \vec{x} \bmod{q} = \sum_{i=1}^{m} x_i \vec{a}_i \bmod{q}$.

The Ajtai hash functions is defined as a family of the above hash functions;

$\mathcal{F}_{n,m,q,D} = \{f_{\boldsymbol{A}}:D^m \to R^n \mid \boldsymbol{A} \in R^{n \times m}\}$.

You can obtain your function by setting $n=1$, $m=2$, $q=5$, and $D = R$; then set $\vec{a}_1 = 14 \ (= 4)$ and $\vec{a}_2 = 13 \ (= 3)$.

For example, you can set $n = 256$, $q = 4097$, $m = 4096$, and $D = \{0,1\}$. The input of the function is a bit string of length $4096$ and the output of the function on such parameters is $256$-dimensional vectors whose coefficients are in $\mathbb{Z}_q$.

# Is it shrinking?

Good parameters makes the above functions shrinking. Correctly speaking, if the size of domain is larger than the size of range, that is, $|D|^m > |R|^n$, the function is (obviously) shrinking.

A possible choice of parameters is $D = \{0,1\}$ and $m > n \log_2(q)$, which often appears in the context. Another possible choice is $D = \{-1,1\}$ or $D = \{-1,0,1\}$.

# Is it hard to find a collision? What is the relation between a collision and a short vector?

How exactly is this linked to the shortest vector problem or short integer solution if they are not the same thing?

If $D = R$, it is too easy to find the collision is function by the power of the linear algebra. You can use Gauss's elimination if $R$ is a field. But, if $D \subset R$ and the size of $D$ is small, it becomes hard. Roughly speaking, the number of collisions depends on the ration $|D|^m/|R|^n$.

In 1996, Ajtai shows that, for good parameters, if there exists an inverter of his hash functions, then there exists an algorithm finding a short vector from any $n$-dimensional lattice. Goldreich, Goldwasser, and Halevi pointed out in the note you refer that, if there exists an algorithm finding a collision of the Ajtai hash functions, then there exists an algorithm finding a short vector from any $n$-dimensional lattice. The reductions are based on the fact that the sum of short vectors is (relatively) short.

# How should we interpret the above in lattice words?

You would skip this part.

We define a lattice related to a matrix $\boldsymbol{A}\in R^{n \times m}$ as

$\Lambda = \Lambda_q^{\perp}(\boldsymbol{A}) = \{\vec{e} \in \mathbb{Z}^m \mid \boldsymbol{A} \vec{e} \equiv \vec{0} \bmod{q}\}$.

This $\Lambda$ is an $m$-dimensional lattice. (You can check this is a lattice by verifying that for any two vectors $\vec{e}, \vec{e}' \in \Lambda$, the sum of them lies in $\Lambda$ again. You can check this is $m$-dimensional by verifying that any $q \vec{u}_i$ is in $\Lambda$, where $\vec{u}_i$ is a unit vector).

This lattice defines a map from $\mathbb{Z}^m$ to a quotient group $\mathbb{Z}^m/\Lambda$, which is isomorphic to $R^n$. The map is a hash function.

Conversely, a collision $\vec{e} \neq \vec{e}'$ for $f_{\boldsymbol{A}}$ implies a short non-zero vector $\vec{e}-\vec{e}'$ in $\Lambda_q^{\perp}(\boldsymbol{A})$.

-