Cryptology ePrint Archive: Report 2021/154

Generating cryptographically-strong random lattice bases and recognizing rotations of $\mathbb{Z}^n$

Tamar Lichter Blanks and Stephen D. Miller

Abstract: 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})$. How can one sample random elements from $GL(n,\mathbb{Z})$? We consider various methods, 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. Similar weaknesses for this problem are found with the random basis generation method in one of the NIST Post-Quantum Cryptography competition submissions (DRS). Other algorithms are described which appear to be much stronger.

Category / Keywords: public-key cryptography / lattice techniques, number theory, cryptanalysis

Date: received 11 Feb 2021

Contact author: miller at math rutgers edu

Available format(s): PDF | BibTeX Citation

Version: 20210212:074123 (All versions of this report)

Short URL: ia.cr/2021/154


[ Cryptology ePrint archive ]