Generating cryptographically-strong random lattice bases and recognizing rotations of Z^n

DOI10.1007/978-3-030-81293-5_17zbMATH Open1485.94059arXiv2102.06344OpenAlexW3141419395MaRDI QIDQ2118552FDOQ2118552

Tamar Lichter Blanks, Stephen D. Miller

Publication date: 22 March 2022

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,mathbbZ)$. We compare the strengths of various methods to sample random elements of $GL(n,mathbbZ)$, 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.

Full work available at URL: https://arxiv.org/abs/2102.06344

Recommendations

• Generating shorter bases for hard random lattices
• Generating shorter bases for hard random lattices
• Publication:4938616
• A lattice-based public-key cryptosystem
• scientific article; zbMATH DE number 2196508

zbMATH Keywords

random basislatticesintegral latticesDRS signature schemeunimodular integral matrices

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Quantum cryptography (quantum-theoretic aspects) (81P94) Authentication, digital signatures and secret sharing (94A62)

Cites Work

• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Density of integer points on affine homogeneous varieties
• A characterization of the \(\mathbb Z^ n\) lattice
• Bonsai Trees, or How to Delegate a Lattice Basis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Title not available (Why is that?)
• An LLL Algorithm with Quadratic Complexity
• Revisiting the Gentry-Szydlo Algorithm
• Generating shorter bases for hard random lattices
• The Ergodic Theory of Lattice Subgroups (AM-172)
• How to pick a random integer matrix? (and other questions)
• Non-abelian analogs of lattice rounding
• Title not available (Why is that?)
• Lattices with symmetry
• Testing Isomorphism of Lattices over CM-Orders
• The Behavior of Random Reduced Bases
• Cryptography and Coding

Cited In (5)

• Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
• Deciding whether a lattice has an orthonormal basis is in co-NP
• On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography
• Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice
• Provable lattice reduction of $$\mathbb {Z}^n$$ with blocksize n/2

This page was built for publication: Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118552)