Notes for UMich EECS 598 (2015): Homework 2

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 ∣bi​∣≥2−(i−1)/2∣b1​∣=2−(i−1)/2∣b1​∣. Therefore, $$\det \mathcal{L}=\prod _{i=1}^n|{\tilde{\mathbf{b}}}_i|\ge 2^{-n(n-1)/4}|{\mathbf{b}}_1{|}^n,$$ and the desired inequality follows by moving the terms around and taking the $n$^th root of both sides.

Problem 1(b). Similar to part (a), we get $$\begin{array}{rl}\det \mathcal{L}& \ge 2^{-(n-1)(n-2)/4}|{\mathbf{b}}_1||{\tilde{\mathbf{b}}}_2{|}^{n-1}\\ ⟹|{\tilde{\mathbf{b}}}_2|& .\end{array}$$ Let ${\mu }_{12}\in \left[\frac{-1}{2},\frac{1}{2}\right]$ be s.t. b2​=b1​+μ12​b2​. Together with ∣b2​∣2≥21​∣b1​∣2, we get $$\begin{array}{rl}|{\mathbf{b}}_2|& =\sqrt{|{\tilde{\mathbf{b}}}_2{|}^2+{\mu }_{12}^2|{\tilde{\mathbf{b}}}_1{|}^2}\\ & \le \sqrt{|{\tilde{\mathbf{b}}}_2{|}^2+\frac{1}{4}|{\tilde{\mathbf{b}}}_1{|}^2}\\ & .\end{array}$$

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 $\mathbf{v}=\mathbf{B}\mathbf{z}=\tilde{\mathbf{B}}\mathbf{U}\mathbf{z}$ be any shortest vector, where $\mathbf{B}=\tilde{\mathbf{B}}\mathbf{U}$ is the Gram–Schmidt decomposition of the LLL-reduced basis $\mathbf{B}$ and z∈Zn. Writing Uz=(y1​,…,yn​)T, we have $$\begin{array}{rl}{y}_i^2|{\tilde{\mathbf{b}}}_i{|}^2& \le y_1^2|{\tilde{\mathbf{b}}}_1{|}^2+\cdots +y_n^2|{\tilde{\mathbf{b}}}_n{|}^2\\ & =|\mathbf{v}{|}^2\le |{\mathbf{b}}_1{|}^2=|{\tilde{\mathbf{b}}}_1{|}^2\le 2^{i-1}|{\tilde{\mathbf{b}}}_i{|}^2\\ ⟹|y_i|& \le 2^{(i-1)/2}.\end{array}$$ Here, the first equality is due to Pythagorean theorem, and the second inequality is because ${\mathbf{b}}_1$ is a non-zero lattice point and $\mathbf{v}$ is a shortest non-zero lattice point.

It is easy to inductively prove $|\mathbf{z}[i]|\le {\left(\frac{3}{2}\right)}^{n-i}{2}^{(n-1)/2}$ backwards (from $n$ down to 1) using $$\mathbf{z}[i]+\mathbf{U}[i,i+1]\mathbf{z}[i+1]+\cdots +\mathbf{U}[i,n]\mathbf{z}[n]=y_i$$ and the property that $|\mathbf{U}[i,j]|\le \frac{1}{2}$ for all j>i. Let c=log2​3−21​, then $|\mathbf{z}[i]|\le 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\ge 0$ such that translations of $r\mathcal{B}$ by lattice points cover Rn, and define $$s\stackrel{\text{def}}{==}\underset{\mathbf{x}\in {\mathbb{R}}^n}{\sup }\underset{\mathbf{v}\in \mathcal{L}}{\inf }|\mathbf{x}-\mathbf{v}|.$$ We want to show that s=infR. (We should prove s<+∞, but this is implied by part (c).)

By the definition of R, for all $r\in R$ and all x∈Rn, there exists some $\mathbf{v}\in \mathcal{L}$ s.t. x∈(rB+v). This means ∣x−v∣≤r, whence infv∈L​∣x−v∣≤r, which implies s≤r.

Moreover, for all s′>s, let r=2s+s′​. For all x∈Rn, since infv∈L​∣x−v∣≤s<r, there exists $\mathbf{v}\in \mathcal{L}$ s.t. ∣x−v∣<r, which implies x∈(rB+v). This gives us R∋r<s′.

We may thus conclude s=infR.

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

Problem 2(b). The lattice ${\mathbb{Z}}^n$ has covering radius $\mu \ge \sqrt{n}/2$ and minimum distance λ1​=1. The former is due to $(\frac{1}{2},\dots ,\frac{1}{2})$ having distance at least $\sqrt{n}/2$ to any lattice point.

Problem 2(c). By homework 1 problem 3(c), translations of $\tilde{\mathbf{B}}\cdot {\left[\frac{-1}{2},\frac{1}{2}\right)}^n$ by lattice points cover Rn. For any v∈B⋅[2−1​,21​)n, we have ∣v∣≤21​∑i=1n​∣bi​∣2​==defr, whence $\tilde{\mathbf{B}}\cdot {\left[\frac{-1}{2},\frac{1}{2}\right)}^n\subseteq r\mathcal{B}$ (the ball is taken to be closed). Since translations of $r\mathcal{B}$ by lattice points cover Rn, we have μ≤r.

Problem 2(d). Choose the fundamental region F=B⋅[2−1​,21​)n, and partition any covering ball $r\mathcal{B}$ into $S_{\mathbf{v}}=r\mathcal{B}\cap (\mathcal{F}+\mathbf{v})$ for lattice points v. Note that the translated partitions $S_{\mathbf{v}}-\mathbf{v}=(r\mathcal{B}-\mathbf{v})\cap \mathcal{F}$ cover $\mathcal{F}$ since $r\mathcal{B}$ is covering. Therefore, $$\begin{array}{rl}{r}^n{V}_n& =\mathrm{vol}(r\mathcal{B})=\sum _{\mathbf{v}\in \mathcal{L}}\mathrm{vol}(S_{\mathbf{v}})=\sum _{\mathbf{v}\in \mathcal{L}}\mathrm{vol}(S_{\mathbf{v}}-\mathbf{v})\\ & \ge \mathrm{vol}\left(\bigcup _{\mathbf{v}\in \mathcal{L}}(S_{\mathbf{v}}-\mathbf{v})\right)=\mathrm{vol}(\mathcal{F})=\det \mathcal{L},\end{array}$$ which implies r≥(detL/Vn​)1/n. Lastly, μ=infr≥(detL/Vn​)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 Nh,Nh−1f(x),…,Nfh−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 $$\det \mathcal{L}=N^{1+\cdots +h}{B}^{1+\cdots +2h}=N^{h(h+1)/2}{B}^{h(2h+1)}.$$ We want LLL to return a vector of length less than 2h+1ph​, and we analyse this in the next problem.

Problem 3(c). Let L=log2​p, then ${\log }_{2}N\le 2L+1$ and log2​B=21​L−5. We need to set $$Q={\log }_2\left(2^{(2h+1-1)/2}\sqrt{2h+1}(\det \mathcal{L}{)}^{1/(2h+1)}\frac{2h+1}{p^h}\right)<0.$$ We know $$\begin{array}{rl}Q& =h+\frac{1}{2}{\log }_2(2h+1)\\ & +\frac{h(h+1)}{2(2h+1)}\boxed{{\log }_{2}N}+h\boxed{{\log }_{2}B}\\ & +{\log }_2(2h+1)-h\boxed{{\log }_{2}p}\\ & \le \frac{hL}{4h+2}+\boxed{h\left(\frac{3{\log }_2(2h+1)}{2h}+\frac{h+1}{4h+2}-4\right)}\\ & \le \frac{hL}{4h+2}-h.\end{array}$$ 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.