Welcome to the resource topic for 2021/154
Title:
Generating cryptographically-strong random lattice bases and recognizing rotations of \mathbb{Z}^n
Authors: Tamar Lichter Blanks, 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.
ePrint: https://eprint.iacr.org/2021/154
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .