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

DOI10.1007/978-3-030-81293-5_17MaRDI QIDQ2118552zbMATH OpenOpenAlexFDO

Authors Tamar Lichter Blanks, Stephen D. Miller

Publication date 22 March 2022

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• scientific article; zbMATH DE number 2086714 (Why is no real title available?)
• scientific article; zbMATH DE number 1405637 (Why is no real title available?)
• scientific article; zbMATH DE number 5266153 (Why is no real title available?)
• A characterization of the Z^ n lattice
• A hierarchy of polynomial time lattice basis reduction algorithms
• An LLL algorithm with quadratic complexity
• Bonsai trees, or how to delegate a lattice basis
• Cryptography and Coding
• Density of integer points on affine homogeneous varieties
• Factoring polynomials with rational coefficients
• Generating shorter bases for hard random lattices
• How to pick a random integer matrix? (and other questions)
• Lattices with symmetry
• Non-abelian analogs of lattice rounding
• Revisiting the Gentry-Szydlo Algorithm
• Testing isomorphism of lattices over CM-orders
• The Behavior of Random Reduced Bases
• The Ergodic Theory of Lattice Subgroups (AM-172)
• Trapdoors for lattices: simpler, tighter, faster, smaller

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)