Lower bounds of shortest vector lengths in random NTRU lattices

DOI10.1016/J.TCS.2014.10.011MaRDI QIDQ477183zbMATH OpenOpenAlexFDO

Authors Jingguo Bi, Qi Cheng

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.10.011

zbMATH Keywords

Kolmogorov complexityshortest vector problemGaussian heuristicNTRU latticesrandom lattices

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Ordered topological linear spaces, vector lattices (46A40)

Recommendations

• Lower bounds of shortest vector lengths in random NTRU lattices
• On the distribution of lengths of short vectors in a random lattice
• Estimates of lengths of shortest nonzero vectors in some lattices. I
• Estimates of lengths of shortest nonzero vectors in some lattices. II
• Long shortest vectors in low dimensional lattices
• On polynomial approximations to the shortest lattice vector length
• Minimal condition for shortest vectors in lattices of low dimension
• scientific article; zbMATH DE number 3870586
• Random Lattice Vectors in a Set of Size O(n)
• On the distribution of angles between the \(N\) shortest vectors in a random lattice

Cites work

• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 5485482 (Why is no real title available?)
• scientific article; zbMATH DE number 1186948 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• A mean value theorem in geometry of numbers
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
• Improved low-density subset sum algorithms
• Lattice points in high-dimensional spheres
• Lower bounds of shortest vector lengths in random NTRU lattices
• New Chosen-Ciphertext Attacks on NTRU
• Solving low-density subset sum problems
• The Rank of Circulant Matrices
• The shortest vector in a lattice is hard to approximate to within some constant
• Topics in Cryptology – CT-RSA 2005

Cited in

(4)

• On the non-existence of short vectors in random module lattices
• Lower bounds of shortest vector lengths in random NTRU lattices
• On the smoothing parameter and last minimum of random orthogonal lattices
• Long shortest vectors in low dimensional lattices

Describes a project that uses

Uses Software

• NTRU

This page was built for publication: Lower bounds of shortest vector lengths in random NTRU lattices

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