1
$\begingroup$

(This question is related to homework) 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))'

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 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 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 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.

$\endgroup$
0
$\begingroup$

You have several confusions regarding cryptography. First, the nature of hash functions. The non-cryptographic use of hash functions is to hash long messages into shorter ones in a "uniform" fashion. So we expect there to be many collisions, by design. Cryptographic hash functions have the additional properties that collisions are hard to find (there are several, inequivalent ways of stating this). Therefore, while it is possible to find collisions even for cryptographic hash functions (simply because the range is smaller than the domain), this should be difficult. Such hash functions can be used in various ways in cryptography, for example in digital signatures: you sign on the (small) hash rather than the (large) message.

Second, encryption is a different primitive from hash functions. Encryption itself comes in two main kinds, symmetric and public key, which are rather different, and there are many other cryptographic constructions out there. There are reductions between some of the cryptographic "primitives" (hash functions, one-way functions and the like), for example you can use them to construct HMACs (message authentication codes) and PRNGs (pseudorandom number generators), but perhaps not encryption schemes.

Regarding the matter at hand: the idea of Ajtai's hash function is to use a random lattice $A$, the hash function being $x \mapsto Ax \pmod{q}$, for some prime $q$. Here $x$ is a binary vector in $\{0,1\}^m$, embedded into $\mathbb{Z}_q^m$. The parameters here are important — the size of $A$ and $q$ — but I'll ignore them here. In order to show that this is cryptographically secure, under one definition we need to show that it is difficult to find a collision, that is two messages $x,y$ with the same hash. Such messages would satisfy $A(x-y) \equiv 0 \pmod{q}$, and so $x-y$ would be in the dual lattice $A^{\perp}$. Now $x-y \in \{-1,0,1\}^m$, so (for the correct choice of parameters) it is "short", and finding it is conjectured to be difficult. This shows the (conditional) security of the scheme.

Lattice-based encryption can also be used for public-key encryption (Regev's scheme) and for homomorphic encryption. These schemes rely on a different problem, LWE (learning with errors), which is similar to CVP (closest vector problem). The details are more complicated &mdash you can have a look at Regev's scheme in Section 5.4 of his survey with Micciancio, though it could be hard to glean from there why exactly the scheme works. Perhaps this is explained later in your course, and if you need more explanations, you can ask another question here.

$\endgroup$
  • $\begingroup$ firstly, thanks a million for replying. You're right in that I have more than one confusions so thanks for the explanations. Regarding your third paragraph, the fact that you, and many other sources said that 'x is a binary vector in {0,1}m was a little confusing for me, because arent the points (17, 8) and (21, 16) playing the role of x? Additionally, the concept of a dual lattice.. i really am very new to this, could you please break that third paragraph down just slight bit. Also just to clarify, are you saying that the situation showed by the exercise is unlikely - h(x) = 0 $\endgroup$ – user2012620 Feb 6 '14 at 14:51
  • $\begingroup$ The question you were assigned just doesn't reflect the actual usage of the function. The trick is that even though everything is being done modulo $q$, the messages themselves are $\{0,1\}$. Regarding the concept of dual lattice, the dual lattice $A^\perp$ is defined as the set of vectors satisfying $Ax \equiv 0 \pmod{q}$. Finally, since the image of the hash function is roughly uniformly distributed, for any given $A$ the probability that $Ax \equiv 0 \pmod{q}$ is roughly $1/q^n$, where $n$ is the output length. $\endgroup$ – Yuval Filmus Feb 6 '14 at 15:14
  • $\begingroup$ Ok, i've been reading and re-reading the post so let me try, the collisions are expected. But as long as the proper parameters are chosen thenthey should not occur. The statement ''x is a binary vector in {0,1}m' stated earlier implies that the vectors used in the example were only for practice. collisions are detected by an answer 'zero' to the function. Might I ask why q has to be a prime, also what would be a 'correct choice of parameters' and in practice would q be smaller that 5? I had thought that (5<) (or rather (det<) is what was meant by short (sorry posted this before seeing a reply) $\endgroup$ – user2012620 Feb 6 '14 at 15:18
  • $\begingroup$ Ahhhhh! that last comment helped alot. :D $\endgroup$ – user2012620 Feb 6 '14 at 15:24
  • $\begingroup$ In practice $q$ would be much much larger than $5$, though I don't think lattice-based schemes are used in practice. You want $q$ to be prime (or a prime power) since you want to work over a field, which makes everything simpler. The correct choice of parameters depends on your beliefs on the complexity of SVP - you can consult the Regev-Micciancio lecture notes I linked to. $\endgroup$ – Yuval Filmus Feb 6 '14 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.