Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors

DOI10.1515/JMC-2016-0008MaRDI QIDQ515394zbMATH OpenOpenAlexFDO

Authors Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, Takeshi Koshiba

Publication date 16 March 2017

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

Full work available at URL https://doi.org/10.1515/jmc-2016-0008

zbMATH Keywords

random samplingLLL algorithmSVP

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Cryptography (94A60) General topics of discrete mathematics in relation to computer science (68R01)

Recommendations

• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Analysis of DeepBKZ reduction for finding short lattice vectors
• scientific article; zbMATH DE number 1962809
• scientific article; zbMATH DE number 3972987
• Random sampling revisited: lattice enumeration with discrete pruning

Cites work

• scientific article; zbMATH DE number 1186948 (Why is no real title available?)
• scientific article; zbMATH DE number 1088230 (Why is no real title available?)
• scientific article; zbMATH DE number 1962809 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• A sieve algorithm for the shortest lattice vector problem
• Algorithmic Number Theory
• Factoring polynomials with rational coefficients
• Fast lattice point enumeration with minimal overhead
• Lattice basis reduction. An introduction to the LLL algorithm and its applications
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice enumeration using extreme pruning
• Mathematics of public key cryptography.
• Predicting Lattice Reduction
• The LLL algorithm. Survey and applications
• The shortest vector in a lattice is hard to approximate to within some constant

Cited in

(3)

• Analysis of DeepBKZ reduction for finding short lattice vectors
• A survey of solving SVP algorithms and recent strategies for solving the SVP challenge
• A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths

Describes a project that uses

Uses Software

• NTRU

This page was built for publication: Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors

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