Generating Cryptographically-Strong Random Lattice Bases and Recognizing Rotations of Zn

Tamar Lichter Blanks, Stephen D. Miller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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

Original languageEnglish (US)
Title of host publicationPost-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, Proceedings
EditorsJung Hee Cheon, Jean-Pierre Tillich
PublisherSpringer Science and Business Media Deutschland GmbH
Pages319-338
Number of pages20
ISBN (Print)9783030812928
DOIs
StatePublished - 2021
Event12th International Conference on post-quantum cryptography, PQCrypto 2021 - Daejeon, Korea, Republic of
Duration: Jul 20 2021Jul 22 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12841 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on post-quantum cryptography, PQCrypto 2021
Country/TerritoryKorea, Republic of
CityDaejeon
Period7/20/217/22/21

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • DRS signature scheme
  • Integral lattices
  • Lattices
  • Random basis
  • Unimodular integral matrices

Fingerprint

Dive into the research topics of 'Generating Cryptographically-Strong Random Lattice Bases and Recognizing Rotations of Zn'. Together they form a unique fingerprint.

Cite this