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 $B$ we have
$∣b_{i}∣≥2_{−(i−1)/2}∣b_{1}∣=2_{−(i−1)/2}∣b_{1}∣$
Therefore,
$detL=i=1∏n ∣b_{i}∣≥2_{−n(n−1)/4}∣b_{1}∣_{n},$
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
$detL⟹∣b_{2}∣ ≥2_{−(n−1)(n−2)/4}∣b_{1}∣∣b_{2}∣_{n−1}≤2_{(n−2)/4}(∣b_{1}∣detL )_{1/(n−1)}. $
Let $μ_{12}∈[2−1 ,21 ]$
be s.t.
$b_{2}=b_{1}+μ_{12}b_{2}$
Together with
$∣b_{2}∣_{2}≥21 ∣b_{1}∣_{2}$
we get
$∣b_{2}∣ =∣b_{2}∣_{2}+μ_{12}∣b_{1}∣_{2} ≤∣b_{2}∣_{2}+41 ∣b_{1}∣_{2} <2∣b_{2}∣_{2} ≤2_{n/4}(∣b_{1}∣detL )_{1/(n−1)}. $

**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 $v=Bz=BUz$ be any shortest vector,
where $B=BU$ is the Gram–Schmidt decomposition of the LLL-reduced basis $B$ and $z∈Z_{n}$
Writing $Uz=(y_{1},…,y_{n})_{T}$
we have
$y_{i}∣b_{i}∣_{2}⟹∣y_{i}∣ ≤y_{1}∣b_{1}∣_{2}+⋯+y_{n}∣b_{n}∣_{2}=∣v∣_{2}≤∣b_{1}∣_{2}=∣b_{1}∣_{2}≤2_{i−1}∣b_{i}∣_{2}≤2_{(i−1)/2}. $
Here, the first equality is due to Pythagorean theorem, and the second inequality is because $b_{1}$ is a non-zero lattice point and $v$ is a *shortest* non-zero lattice point.

It is easy to inductively prove $∣z[i]∣≤(23 )_{n−i}2_{(n−1)/2}$ backwards (from $n$ down to 1) using $z[i]+U[i,i+1]z[i+1]+⋯+U[i,n]z[n]=y_{i}$ and the property that $∣U[i,j]∣≤21 $ for all $j>i$ Let $c=g_{2}3−21 $ then $∣z[i]∣≤2_{cn}$ for all $i=1,…,n$

**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 $R$ be the set of radius $r≥0$ such that translations of $rB$ by lattice points cover $R_{n}$ and define $s==defx∈R_{n}sup v∈Lf ∣x−v∣.$ We want to show that $s=fR$ (We should prove $s<+∞$ but this is implied by part (c).)

By the definition of $R$ for all $r∈R$ and all $x∈R_{n}$ there exists some $v∈L$ s.t. $x∈(rB+v)$ This means $∣x−v∣≤r$ whence $f_{v∈L}∣x−v∣≤r$ which implies $s≤r$

Moreover, for all $s_{′}>s$ let $r=2s+s_{′} $ For all $x∈R_{n}$ since $f_{v∈L}∣x−v∣≤s<r$ there exists $v∈L$ s.t. $∣x−v∣<r$ which implies $x∈(rB+v)$ This gives us $R∋r<s_{′}$

We may thus conclude $s=fR$

**Problem 2(a).**
Let $v$ be a shortest non-zero lattice point and suppose $2v ∈u+μB$ where $u$ is a lattice point.
We now have $2v =u+r$ for some $r$ s.t. $∣r∣≤μ$
This means $2r=v−2u$ is a lattice point.
It cannot be zero, otherwise $v=2u$ would be longer than lattice point $u$
Therefore,
$2μ≥∣2r∣≥λ_{1}$

**Problem 2(b).**
The lattice $Z_{n}$ has covering radius $μ≥n /2$ and minimum distance $λ_{1}=1$
The former is due to $(21 ,…,21 )$
having distance at least $n /2$ to any lattice point.

**Problem 2(c).**
By homework 1 problem 3(c),
translations of
$B⋅[2−1 ,21 )_{n}$
by lattice points cover $R_{n}$
For any
$v∈B⋅[2−1 ,21 )_{n}$
we have
$∣v∣≤21 ∑_{i=1}∣b_{i}∣_{2} ==defr$
whence
$B⋅[2−1 ,21 )_{n}⊆rB$
(the ball is taken to be closed).
Since translations of $rB$ by lattice points cover $R_{n}$ we have $μ≤r$

**Problem 2(d).**
Choose the fundamental region
$F=B⋅[2−1 ,21 )_{n}$
and partition any covering ball
$rB$
into
$S_{v}=rB∩(F+v)$
for lattice points $v$
Note that the translated partitions $S_{v}−v=(rB−v)∩F$ cover $F$ since $rB$ is covering.
Therefore,
$r_{n}V_{n} =vol(rB)=v∈L∑ vol(S_{v})=v∈L∑ vol(S_{v}−v)≥vol(v∈L⋃ (S_{v}−v))=vol(F)=detL, $
which implies
$r≥(detL/V_{n})_{1/n}$
Lastly,
$μ=fr≥(detL/V_{n})_{1/n}$

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

**Problem 3.**
It suffices to consider
$ε=0,B=p /32$

**Problem 3(a).**
We need
$N_{h},N_{h−1}f(x),…,Nf_{h−1}(x)$

**Problem 3(b).**
Consider the lattice generated by $g(Bx)$ where $g(x)$ is one of the $2h+1$ polynomials.
The determinant is
$detL=N_{1+⋯+h}B_{1+⋯+2h}=N_{h(h+1)/2}B_{h(2h+1)}.$
We want LLL to return a vector of length less than
$2h+1p_{h} $
and we analyse this in the next problem.

**Problem 3(c).**
Let $L=g_{2}p$ then
$g_{2}N≤2L+1$
and
$g_{2}B=21 L−5$
We need to set
$Q=g_{2}(2_{(2h+1−1)/2}2h+1 (detL)_{1/(2h+1)}p_{h}2h+1 )<0.$
We know
$Q =h+21 g_{2}(2h+1)+2(2h+1)h(h+1) g_{2}N +hg_{2}B +g_{2}(2h+1)−hg_{2}p ≤4h+2hL +h(2h3g_{2}(2h+1) +4h+2h+1 −4) ≤4h+2hL −h. $
It suffices to set $h$ to be a positive integer s.t. $4h+2≥L$
which can be made polynomial in the input length.
The rest is obvious.

Please enable JavaScript to view the comments powered by Disqus.