  Lattice-based cryptography relies on generating random bases which are
difficult to fully reduce. Given a lattice basis (such as the private basis for
a cryptosystem), all other bases are related by multiplication by matrices in
$GL(n,\mathbb{Z})$. We compare the strengths of various methods to sample
random elements of $GL(n,\mathbb{Z})$, finding some are stronger than others
with respect to the problem of recognizing rotations of the $\mathbb{Z}^n$
lattice. In particular, the standard algorithm of multiplying unipotent
generators together (as implemented in Magma's RandomSLnZ command) generates
instances of this last problem which can be efficiently broken, even in
dimensions nearing 1,500. Likewise, we find that the random basis generation
method in one of the NIST Post-Quantum Cryptography competition submissions
(DRS) generates instances which can be efficiently broken, even at its 256-bit
security settings. Other random basis generation algorithms (some older, some
newer) are described which appear to be much stronger.
