2021/02/11 by Tamar Lichter Blanks, Stephen D. Miller, Blanks, Tamar Lichter +1
Computer Science · Mathematics · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Number Theory (math.NT) #cs.CR #math.GR #math.NT
paper · pdf · doi:10.48550/arxiv.2102.06344
20 pages, 2 figures, to appear in PQCrypto 2021
openalex publication_date 2021/02/11 · arxiv created 2021/05/19 · arxiv updated 2021/05/20 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
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,ℤ). We compare the strengths of various methods to sample random elements of GL(n,ℤ), finding some are stronger than others with respect to the problem of recognizing rotations of the ℤ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.