Lattices with symmetry

DOI10.1007/S00145-016-9235-7MaRDI QIDQ2408587zbMATH OpenOpenAlexFDO

Authors Alice Silverberg, H. W. jun. Lenstra

Publication date 12 October 2017

Published in Journal of Cryptology (Search for Journal in Brave)

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

zbMATH Keywords

latticeslattice-based cryptographyideal latticesGentry-Szydlo algorithm

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Abstract: For large ranks, there is no good algorithm that decides whether a given lattice has an orthonormal basis. But when the lattice is given with enough symmetry, we can construct a provably deterministic polynomial-time algorithm to accomplish this, based on the work of Gentry and Szydlo. The techniques involve algorithmic algebraic number theory, analytic number theory, commutative algebra, and lattice basis reduction.

Recommendations

• Revisiting the Gentry-Szydlo Algorithm
• Deciding orthogonality in construction-A lattices
• A hierarchy of polynomial time lattice basis reduction algorithms
• scientific article; zbMATH DE number 3922766
• An LLL algorithm for module lattices

Cites work

• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 5532102 (Why is no real title available?)
• scientific article; zbMATH DE number 3439001 (Why is no real title available?)
• scientific article; zbMATH DE number 2086714 (Why is no real title available?)
• scientific article; zbMATH DE number 3279238 (Why is no real title available?)
• Determining cyclicity of finite modules
• Factoring polynomials with rational coefficients
• Intégration
• Revisiting the Gentry-Szydlo Algorithm
• Roots of unity in orders
• Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression

Cited in

(13)

• scientific article; zbMATH DE number 14713 (Why is no real title available?)
• scientific article; zbMATH DE number 3297122 (Why is no real title available?)
• Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\)
• Universal gradings of orders
• Testing isomorphism of lattices over CM-orders
• Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
• Deciding whether a lattice has an orthonormal basis is in co-NP
• Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice
• \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple
• On the lattice isomorphism problem
• Extreme lattices: symmetries and decorrelation
• Deciding orthogonality in construction-A lattices
• Deciding orthogonality in construction-A lattices

This page was built for publication: Lattices with symmetry

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