Paper 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. 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. PQCrypto 2021
Keywords
lattice techniquesnumber theorycryptanalysis
Contact author(s)
miller @ math rutgers edu
History
2021-05-19: last of 2 revisions
2021-02-12: received
See all versions
Short URL
https://ia.cr/2021/154
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/154,
      author = {Tamar Lichter Blanks and Stephen D.  Miller},
      title = {Generating cryptographically-strong random lattice bases and recognizing rotations of $\mathbb{Z}^n$},
      howpublished = {Cryptology ePrint Archive, Paper 2021/154},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/154}},
      url = {https://eprint.iacr.org/2021/154}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.