## Monday, December 28, 2009

### Lattice Based Cryptography - Getting Inside 2

Hello Again,

So did you try out the problems listed at the end of the previous post?

That was fun, right?

Anyway, in case you did not get the solution (or did not try the problem at all) here is the solution.

(Please note that the following material draws heavily from Oded Regev lecture notes)

We will solve the more general problem of determining Base Equivalence first. That is given $2$ bases $B_{1}$ and $B_{2}$ we will determine whether they lead to the same lattice. This will help with the the problem of determining whether the given lattice hits all points in $Z^n$ as well because we know that $I$ hits all points in $Z^n$ and we know the condition when a base $B$ is equivalent to $I$. Actually we know more. We not only know "how to determine whether given $B$" is equivalent to $I$; we also know "how to create such a $B$".

First of all we notice that a given Base $B_{1}$ and another base $B_{2}$ obtained by permutation of its columns are equivalent (why? hint - its too easy).

Any other base $B_{2}$ equivalent to $B_{1}$ will have the same number of "effectively independent vectors". Further, we would expect that the set of vectors is effectively the same - both are clearly integer combinations of each other,

Something tells us that column operations on $B_{2}$ can convert it to the equivalent matrix $B_{1}$.

Further, if $B_{1}$ is full rank so that $det$($B_{1}$$) is defined, we hope that det(B_{2}$$)$ would be same in magnitude as $det$($B_{1}$$). So, that looks like the rule; perhaps both the matrices should have the same determinant in magnitude. Hmm..So we can say that if B_{1} = B_{2}$$U$ (and $B_{2}$ = $B_{1}$$V) for some unimodular matrix U (and Unimodular V), B_{1} and B_{2} are equivalent. By the way Unimodular matrices are those which have determinant +1 or (-1) and have all B_{ij}'s integral. But wait. We talked about lattices with full rank bases. What if rank is not full? Well, you can prove that these rules hold in general. This helps you see that if you want your Basis to hit Z^n, your matrix needs to be a unimodular matrix times I; in short your matrix needs to be unimodular itself. Now lets actually prove the following proposition Two bases B_{1}, B_{2} \epsilon \RR^{m*n} are equivalent if and only if B_{2} = B_{1}$$U$ for some unimodular matrix $U$.

1. Great post. Keep it coming :).
Lets try to prove the statement above.
$(\Leftarrow)$
Let $x$ be an integral vector. Take $y=Ux$. This $y$ also an integral vector (since $U$ is unimodular). It follows that $B_2x=B_1y$. NOw for $z=U^{-1}x$ ($z$ is clearly integral) we also have $B_1x=B_2z$. Hence $B_1$ and $B_2$ are equivalent.

$(\Rightarrow)$
Suppose $B_1,B_2$ are equivalent. Then there are integer vectors $x_i$ such that
$B_2e_i=B_1x_i$
But $B_2e_i$ is exactly the $i$th column of $b_2$. Hence
$B_2=B_1X$
where $X$ is the matrix such that its ith column is $x_i$.
By similar argument there is an integer matrix $Y$ such that $B_1=B_2Y$. It follows that
$B_1=B_1XY$
Hence $\det(XY)=1$ which implies that $\det(X)=\pm 1$. So $X$ is unimodular.