Improved methods for calculating vectors of short length in a lattice, including a complexity analysis
1985; American Mathematical Society; Volume: 44; Issue: 170 Linguagem: Inglês
10.1090/s0025-5718-1985-0777278-8
ISSN1088-6842
Autores Tópico(s)Cryptography and Data Security
ResumoThe standard methods for calculating vectors of short length in a lattice use a reduction procedure followed by enumerating all vectors of Z m {{\mathbf {Z}}^m} in a suitable box. However, it suffices to consider those x ∈ Z m {\mathbf {x}} \in {{\mathbf {Z}}^m} which lie in a suitable ellipsoid having a much smaller volume than the box. We show in this paper that searching through that ellipsoid is in many cases much more efficient. If combined with an appropriate reduction procedure our method allows to do computations in lattices of much higher dimensions. Several randomly constructed numerical examples illustrate the superiority of our new method over the known ones.
Referência(s)