More drills On LLL Algorithm and a little bit About CVP

Hello again everybody,

Have not posted around in a while. Things are getting a little busy as the first week of semester went by. In the meantime, I blogged about the curious properties of Domino Tilings and their Markov Chain connection which is another subject I am enrolled in this semester. Hope, that account is also accessible to most of you; I would definitely suggest you to have a look at that post - the combinatorial ramifications for Markov Chains are great. And, if you ever come to Georgia Tech, you should definitely consider sitting through that class. Prof Randall is teaching that course and she is a great teacher.

So, anyways today I am going to walk you through some more problems in Lattice Based Cryptography. The blog is certainly lagging a little behind what I had thought; I hope I would get around that within this week, and if not, the week next to this one.

So, lets tackle another problem from Homework 2 of Oded Regev's.


Q-5) Find a basis $b_1, b_2,...,b_n$ such that after we apply one reduction step of the LLL algorithm to it, the maximum length of a vector in it increases [even by as much as ­$\Omega(\sqrt n)$].

(This is Roy Kasher's solution. In retrospect, this solution seems very easy; I think it indeed is - only I could not find it [:(] )

Ans) So, what do you think?  Any matrix (rather, set of basis vectors) that springs to your mind? Notice that you are gonna apply LLL algorithm's first step.

That would impact the length of all the basis vectors. So, we would try to keep some vectors in our original basis which have got loads of zero components (not all). We hope that the steps of LLL that involve "reducing" vector $b_i$ in the sense of subtracting appropriate multiples of vector $b_j$ for $j < i$ will jitter these non-zero entries and these jitters combined would make some vector really large.

This rough intuitive idea is captured readily by some experiments in the following basis.

$\begin{pmatrix}1&3/4&0&...&0\\0&1&3/4&...&0\\...&...&...&...&...\\...&...&...&...&...\\0&0&...&1&3/4\end{pmatrix}$

Now the nice thing about this matrix is it is (nearly) in Gram Schmidt Orthogonal form already - after all the GSO matrix in this case is the identity matrix. Length of all the columns are $\Theta(1)$.

After LLL reduction step, the vector $b_n$ undergoes some intersting gyrations which we gleefully watch (because it solves the problem). The $i^{th}$ column now becomes $\begin{pmatrix} \pm1/4\\ \pm1/4\\...\\ \pm1/4 \\1\\0\\0\\...\\0\end{pmatrix}$ where $1$ is present in the $i^{th}$ location.


Q-6) Show an algorithm that solves SVP exactly in time $2O(n^2).poly(D)$ where $n$ is the rank of the lattice and $D$ is the input size.

The problem comes with a hint which I think is fair to be reproduced here.

Hint: show that if we represent the shortest vector in an LLL-reduced basis, none of the coefficients can be larger than $2^{cn}$ for some $c$.

Again, I had to look up Kasher's solution, though this time I had a few ideas of my own. I am just giving myself some solace that I was probably close to the solution myself.

Ans) Well, I am a bit tired. Please allow this post to get a little more delayed.