# Notes for UMich EECS 598 (2015): Homework 1

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

Update on 5 January 2020. I managed to give an ugly solution to the extra credit problem.

Problem 1. Given a generating set output the (positive) greatest common divisor of those elements. Euclidean algorithm for computing the GCD of two numbers runs in polynomial time, and the output is shorter than the input. Therefore, the total running time is polynomial.

Problem 2. Note that the two inequalities are equalities when For consider the basis where is a positive integer. The determinant bound is and the shortest Gram–Schmidt vector has length 1. We now consider any non-zero lattice point

• When the smallest possible length is attained when
• When its length is at least
• When its length is at least

The above covers all possible cases. Therefore, we have

Problem 3(a). By definition, for any there exists unique s.t. which means for some This further translates into Therefore, is non-empty. Suppose then for some This means By the uniqueness of it follows that hence This completes the proof that the intersection is a singleton set.

Problem 3(b). Given find (using Gaussian elimination) real coefficients s.t. We then have

Problem 3(c). We use QDU decomposition. Suppose and where is orthogonal, is positive diagonal, and is upper-unitriangular. Let

First, we show only if for Let be a vector in this intersection, then for some s.t. Moving terms around and cancelling we get Suppose for the sake of contradiction that and that its last non-zero entry were the one. Using the upper-unitriangularity, we would get This is a contradiction because the left-hand side would be a non-zero integer. Therefore,

Next, we show that its translations using lattice points cover algorithmically. This amounts to solving from where is any vector in and the other symbols inherit their meanings from the first part. We solve from the last entry to the first. Suppose we have computed we then set This can be done efficiently and, by inspection, gives a correct solution.

Problem 4. The volume of an dimensional ball of radius is (This formula is due to Xianfu Wang.) Setting this to be at least we get (using Stirling’s formula)

Problem 5. We first show that its translations by lattice points do not overlap. Suppose for the sake of contradiction that for but We would have but by swapping the roles of in the above argument. Therefore, the translations of by lattice points do not overlap.

Next, for all points whose closest lattice point is unique, it is easy to verify that it lies in the translate of by the closest lattice point to it. If a point is closest to two distinct lattice points, it cannot be in a translate of by any lattice point.

(Assume the lattice is full-rank by convention.) The points whose closest lattice points are not unique form a null set (set of measure 0, i.e., rare). To see this, consider enumerating non-singleton closest lattice point set The set of points that have the same lengths to all points in has measure zero, so the union of countably many of them still has measure zero.