Search for: All records

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,Z). We compare the strengths of various methods to sample random elements of GL(n,Z), finding some are stronger than others with respect to the problem of recognizing rotations of the Zn 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. 

It is well-known that there are automorphic eigenfunctions on SL(2,Z)∖SL(2,R)/SO(2,R)—such as the classical j-function—that have exponential growth and have exponentially growing Fourier coefficients (e.g., negative powers of q=e2πiz, or an I-Bessel function). We show that this phenomenon does not occur on the quotient SL(3,Z)∖SL(3,R)/SO(3,R) and eigenvalues in general position (a removable technical assumption). More precisely, if such an automorphic eigenfunction has at most exponential growth, it cannot have non-decaying Whittaker functions in its Fourier expansion. This confirms part of a conjecture of Miatello and Wallach, who assert all automorphic eigenfunctions on this quotient (among other rank ≥2 examples) always have moderate growth. We additionally confirm their conjecture under certain natural hypotheses, such as the absolute convergence of the eigenfunction’s Fourier expansion.