Notes for UMich EECS 598 (2015): Homework 2

Hero image
Hero image

Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for homework 2.

Problem 1(a). In an LLL-reduced basis we have Therefore, and the desired inequality follows by moving the terms around and taking the root of both sides.

Problem 1(b). Similar to part (a), we get Let be s.t. Together with we get

Question. The inequality for part (b) is so similar to that of part (a). Is it possible to defined a ‘quotient lattice’ so that part (b) is part (a) applied to this quotient?

Problem 1(c). Let be any shortest vector, where is the Gram–Schmidt decomposition of the LLL-reduced basis and Writing we have Here, the first equality is due to Pythagorean theorem, and the second inequality is because is a non-zero lattice point and is a shortest non-zero lattice point.

It is easy to inductively prove backwards (from down to 1) using and the property that for all Let then for all

Problem 2. I prove the meta proposition that the two definitions are equivalent. This would be a good exercise to reactive the muscle of elementary calculus.

Let be the set of radius such that translations of by lattice points cover and define We want to show that (We should prove but this is implied by part (c).)

By the definition of for all and all there exists some s.t. This means whence which implies

Moreover, for all let For all since there exists s.t. which implies This gives us

We may thus conclude

Problem 2(a). Let be a shortest non-zero lattice point and suppose where is a lattice point. We now have for some s.t. This means is a lattice point. It cannot be zero, otherwise would be longer than lattice point Therefore,

Problem 2(b). The lattice has covering radius and minimum distance The former is due to having distance at least to any lattice point.

Problem 2(c). By homework 1 problem 3(c), translations of by lattice points cover For any we have whence (the ball is taken to be closed). Since translations of by lattice points cover we have

Problem 2(d). Choose the fundamental region and partition any covering ball into for lattice points Note that the translated partitions cover since is covering. Therefore, which implies Lastly,

Interleave. The video below is by 3Blue1Brown and about high-dimensional balls. (Video is removed from printing.)

Problem 3. It suffices to consider

Problem 3(a). We need

Problem 3(b). Consider the lattice generated by where is one of the polynomials. The determinant is We want LLL to return a vector of length less than and we analyse this in the next problem.

Problem 3(c). Let then and We need to set We know It suffices to set to be a positive integer s.t. which can be made polynomial in the input length. The rest is obvious.

Please enable JavaScript to view the comments powered by Disqus.