IACR Cryptology ePrint Archive · 2011 · 25 citations · 18 references
ComputingComputer ScienceAlgorithmsComputer SecurityCryptographyApproximation AlgorithmsCryptographic AlgorithmsCryptographic ComplexityInformation-theoretic CryptographyLattice-based CryptographyCryptographic ReductionsGap EstimationLattice ReductionLattice VectorsShortest Vector Problem
Given a lattice L with the i-th successive minimum λi, its i-th gap λi often provides useful λ1 information for analyzing the security of cryptographic scheme related to L. This paper concerns short vectors for lattices with gaps. In the first part, a λ2-gap estimation of LWE lattices with cryptographic significance is given. For some γ ′ , a better reduction from BDDγ ′ to uSV Pγ is obtained in the presence of larger λ2-gap. The second part of the paper shows that gaps among the successive minima lead to a more efficient SVP search algorithm. As far as we know, it is the first SVP algorithm exploiting lattices with gaps.
18
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2005 · 2.2K citations
On Lovász’ lattice reduction and the nearest lattice point problem
László Babai · COMBINATORICA · 1986 · 930 citations
A sieve algorithm for the shortest lattice vector problem
Miklós Ajtai, Ravi Kumar, D. Sivakumar · 2001 · 553 citations