Lower bounds of shortest vector lengths in random NTRU lattices

DOI10.1016/j.tcs.2014.10.011zbMath1304.46004OpenAlexW2236597804MaRDI QIDQ477183

Qi Cheng, Jingguo Bi

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

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

Uses Software

• NTRU

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved low-density subset sum algorithms
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
• Lattice points in high-dimensional spheres
• A mean value theorem in geometry of numbers
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• Lower Bounds of Shortest Vector Lengths in Random NTRU Lattices
• The Rank of Circulant Matrices
• Solving low-density subset sum problems
• Topics in Cryptology – CT-RSA 2005
• New Chosen-Ciphertext Attacks on NTRU

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