Exploiting the symmetry of Z^n: randomization and the automorphism problem

DOI10.1007/978-981-99-8730-6_6MaRDI QIDQ6604873zbMATH OpenFDO

Authors Kaijie Jiang, Anyu Wang, Guoxiao Liu, Yang Yu, Xiaoyun Wang

Publication date 13 September 2024

zbMATH Keywords

gradient descentlattice automorphismrandomized reduction\( \mathbb{Z}\)LIPcharacteristic vectors of the unimodular lattice

Mathematics Subject Classification ID

Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Lattice packing and covering (number-theoretic aspects) (11H31)

Recommendations

• 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
• On the geometry of cyclic lattices
• scientific article; zbMATH DE number 1643917
• scientific article; zbMATH DE number 2196508

Cites work

• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1088230 (Why is no real title available?)
• scientific article; zbMATH DE number 1962147 (Why is no real title available?)
• scientific article; zbMATH DE number 2009972 (Why is no real title available?)
• scientific article; zbMATH DE number 2086714 (Why is no real title available?)
• scientific article; zbMATH DE number 1859030 (Why is no real title available?)
• scientific article; zbMATH DE number 7788447 (Why is no real title available?)
• A \(2^{n/2}\)-time algorithm for \(\sqrt{n} \)-SVP and \(\sqrt{n} \)-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP
• A canonical form for positive definite matrices
• A decade of lattice cryptography
• A quantum algorithm for computing the unit group of an arbitrary degree number field
• A reverse Minkowski theorem
• Bonsai trees, or how to delegate a lattice basis
• Classical hardness of learning with errors
• Complexity and algorithms for computing Voronoi cells of lattices
• Computing isometries of lattices
• Cryptography and Coding
• Factoring polynomials with rational coefficients
• Finding shortest lattice vectors in the presence of gaps
• Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\)
• Graph isomorphism in quasipolynomial time (extended abstract)
• How to generate random matrices from the classical compact groups
• Hull attacks on the lattice isomorphism problem
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice
• Just take the average! An embarrassingly simple \(2^n\)-time algorithm for SVP (and CVP)
• Lattices with symmetry
• Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures
• On the Lattice Isomorphism Problem
• On the lattice isomorphism problem
• On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography
• Revisiting the Gentry-Szydlo Algorithm
• Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one
• Slide reduction, revisited -- filling the gaps in SVP approximation
• Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract)
• The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators
• The Subgroup Algorithm for Generating Uniform Random Variables
• Trapdoors for hard lattices and new cryptographic constructions
• \textsc{Hawk}: module LIP makes lattice signatures fast, compact and simple

Cited in

(1)

• Provable lattice reduction of $$\mathbb {Z}^n$$ with blocksize n/2

This page was built for publication: Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem

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