Lattices with symmetry

DOI10.1007/S00145-016-9235-7zbMATH Open1377.94060arXiv1501.00178OpenAlexW2570157913MaRDI QIDQ2408587FDOQ2408587

Authors: Alice Silverberg, H. W. jun. Lenstra 

Publication date: 12 October 2017

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Factoring polynomials with rational coefficients
• Title not available (Why is that?)
• Title not available (Why is that?)
• Roots of unity in orders
• Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression
• Revisiting the Gentry-Szydlo Algorithm
• Determining cyclicity of finite modules
• Title not available (Why is that?)
• Intégration

Cited In (13)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Deciding orthogonality in construction-A lattices
• Deciding orthogonality in construction-A lattices
• Extreme lattices: symmetries and decorrelation

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)