TY - GEN
T1 - Generating Cryptographically-Strong Random Lattice Bases and Recognizing Rotations of Zn
AU - Blanks, Tamar Lichter
AU - Miller, Stephen D.
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - DRS signature scheme
KW - Integral lattices
KW - Lattices
KW - Random basis
KW - Unimodular integral matrices
UR - http://www.scopus.com/inward/record.url?scp=85112729472&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85112729472&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-81293-5_17
DO - 10.1007/978-3-030-81293-5_17
M3 - Conference contribution
AN - SCOPUS:85112729472
SN - 9783030812928
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 319
EP - 338
BT - Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, Proceedings
A2 - Cheon, Jung Hee
A2 - Tillich, Jean-Pierre
PB - Springer Science and Business Media Deutschland GmbH
T2 - 12th International Conference on post-quantum cryptography, PQCrypto 2021
Y2 - 20 July 2021 through 22 July 2021
ER -