For the purpose of testing algorithms for lattice basis reduction or finding short vectors, it would be useful to have examples of lattices where short vectors are hidden, that is, a nontrivial combination of vectors of the given basis. Random bases often do not appear to have a nontrivial short vector. In this posting, I will present an algorithm to find short vectors, and then go on to define a class of Matrices with hidden short vectors. This construction provides insights on the structure of certain lattices, too. Some implementations of LLL or other basis reduction algorithms can not resolve these, and thus expose bugs.

The Smith normal form

We will understand the lattice to be represented by a Matrix $B$ of column vectors of dimension $N$. Its Smith normal form is a diagonal Matrix $S$, so that:

$$ S = UBV $$

With $U$ und $V$ unitary. Algorithms to compute the Smith normal form (and the corresponding transformation matrices) exist, and are not further elaborated upon here. The central point for our purpose is that every lattice vector $\mathbf{y}=B\mathbf{x}$ satisfies the condition $S_{i,i}|(U\mathbf{x})_i$.

This implies that all lattice problems are periodic in $\mathop{det} B$. This follows from $\mathop{inv} B = {1 \over \mathop{det} B}\mathop{adj}B$. The columns of $\mathop{adj} B$ are solutions to $B\mathbf{x}=e_i\cdot\mathop{det} B$, with $e_i$ being the $i$-th unit vector.

An algorithm for the SVP

For simplicity, we assume that $\forall{i<N}: S_{i,i}=1$ (so that, implicitly, $S_{N,N}=\mathop{det}B$). This is often the case for random $B$. In this case, finding a short vector reduces to finding a short solution to $$ (U_{N,:}\mathbf{x}) = 0 \mod \mathop{det}B $$

That is, a linear combination of the entries of the last row in $U$ equal to $0$ (mod $\mathop{det}B$). The PSLQ algorithm solves exactly this problem, given the last row of $U$ and $\mathop{det} B$ as inputs. With arbitrary matrices of small dimension, this often results in a vector that LLL finds, too.

If we reverse the procedure, that is, pick $S$, $U$ and $V$ and then compute:

$$ B = U^{-1}SV^{-1} $$

we obtain a matrix in which the last row of $U$ can be influenced in several important ways, given that we can force $U$ being unimodular. We can do so, see below. Notice, however, that computing the Smith normal form of $B = U^{-1}SV^{-1}$ will not simply return U and V.

Integer Matrices with arbitrary determinant

To generate unimodular matrices (or matrices with any determinant), we use Laplace Expansion. We will replace one of the rows (a column would work, too) of a given Matrix $M$ with a (preferably small) solution $x$ to

$$ \sum_{0\leq i < N} x_iM_{0,i} = k $$

With $k$ being the determinant we want to produce (for our purpose $k=1$), and $M_{i,j}$ the determinants of the Minors of M. There are several algorithms for solving this subproblem, we stick to an algorith presented by Keith Matthews (an implementation in Python is avalable here), relying on previous work by Havas, Majewski and Matthews himself. Should there be no solution (gcd of $M_{0,i}$ does not divide $k$), we'd simply use another M.

Finding two unimodular matrices $U$ and $V$ that way, we end up with a $B$ which has a Smith form in which we can control some properties of the left transformation Matrix $U$, namely of the solutions to the last row mentioned above.

Interesting cases are:

  1. The last row is small (yielding lattices with hidden short vectors)
  2. The last row is constant, i.e. all numbers are identical. This yields a lattice in which all vectors satisfy the property $\sum_i{y_i} = 0$. I call these lattices "sum-0-lattices". In the 2-dimensional case, these are exactly the lattices containing the counterdiagonal. Allowing distinct signs results in mirroring.
  3. The last row is not constant, but allows for other trivial $0$ combinations. Interesting cases are elements being $0$, $1$, or multiplicative inverses of small numbers modulo the determinant, or any elements appearing multiple times or being multiples of each other.
  4. The lattice is cyclic, in which case the solutions are cyclic, too.

Constructing Matrices with hidden short vectors

The path to a Matrix with hidden short vectors is now beaten. Proceed like this:

  1. Pick a diagonal matrix $S$ with all diagonal elements $1$, except for the last one, which may be chosen freely.
  2. Construct unimodular matrices $U$ and $V$ with the desired properties (here: small entries and thus small solutions in the last row of $U$).
  3. Compute $B=U^{-1}SV^{-1}$

The resulting $B$ contains short vectors, of which at least one can be found with the help of PSLQ (like mentioned above). An example is provided below.

Observations

  1. The result is an apparently random lattice basis matrix $B$.
  2. In case 1 (last row of $U$ is small), there's a basis for $B$ with all vectors short but one.
  3. Some implementations of LLL can not substantially reduce $B$.

My Questions

  1. Are there any similar results known, any remarks or comments?
  2. What other (maybe useful or curious) properties could we impose upon the last row of $U$?
  3. Does PSLQ in this situation guarantee to find a shortest vector in the euclidean sense?
  4. Is there a way to do away with the restriction on $S$, that is, to also process matrices with nontrivial elementary divisors?

Example

$$ U=\left (\begin{matrix} -13 & 59 & -30 \\ -165 & 126 & -241 \\ 17 & 13 & 19 \\ \end{matrix}\right) $$

I picked some small numbers for the last row of $U$. This selection allows the short solutions $(3,-1,-2)^T$ and $(2,-7,3)^T$. Then I adjusted the first row so that $\mathop{det} U=1$ (see above.

$$ V=\left ( \begin{matrix} 38 & 85 & -119 \\ -220 & 32 & 229 \\ 17 & -238 & 189 \\ \end{matrix} \right) $$

$$ S=\left( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2308869931 \\ \end{matrix} \right) $$

The third element is a prime number of 32 bit length.

$$ B=U^{-1}SV^{-1}=\left( \begin{matrix} -1248884424688331397 & -252808953422802017 & -480021271462343831 \\ 217379346648022931 & 44003627585902284 & 83551935074919420 \\ 968695965772720018 & 196091014068821624 & 372328023281023077 \\ \end{matrix} \right) $$

The LLL reduced basis is:

$$ LLL(B)=\left( \begin{matrix} 3 & -2 & -47925262 \\ -1 & 7 & -36648728 \\ -2 & -3 & -53563527 \end{matrix}\right) $$

The python implementation of LLL provided here will, erratically, output:

$$ \left( \begin{matrix} -1248884424688331397 & 217379346648022931 & 968695965772720018 \\ -1728905696150675228 & 300931281722942351 & 1341023989053743095 \\ -2750577802799464811 & 478762320881948146 & 2133482945614261660 \\ \end{matrix}\right) $$

Thank you for reading.

  • Could this be a row-vector notation vs. column-vector notation issue ? FPLLL (the library used in python) uses row vectors. Maybe give it a shot with the transposed matrix. – LeoDucas Jul 8 at 8:59
  • I can't reproduce the problem. And, the implementation I used is not FPLLL, which I deem to be correct. I don't know what happened there, but still that's a way to check LLL implementations, respectively, to build lattice bases with nontrivial short vectors. – user222134 Jul 9 at 14:02
  • Maybe github issue is the best place to discuss this... – LeoDucas Jul 10 at 14:44

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.