Paper 2021/1203

The irreducible vectors of a lattice: Some theory and applications

Emmanouil Doulgerakis, Thijs Laarhoven, and Benne de Weger

Abstract

The main idea behind lattice sieving algorithms is to reduce a sufficiently large number of lattice vectors with each other so that a set of short enough vectors is obtained, including a basis of the lattice. It is therefore natural to study vectors which cannot be reduced. In this work we give a concrete definition of an irreducible vector and study the properties of the set of all such vectors. We show that the set of irreducible vectors is a subset of the set of relevant vectors and study its properties. For extremal lattices this set may contain as many as $2^n$ vectors, which leads us to define the notion of a complete system of irreducible vectors, whose size can be upper-bounded by the kissing number. We study properties of this set and observe a close relation to heuristic sieving algorithms. Finally we briefly examine the use of this set in the study of lattice problems such as SVP, SIVP and CVPP. The introduced notions, as well as various results derived along the way, may provide further insights into lattice algorithms and motivate new research into understanding these algorithms better.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
latticesrelevant vectorsirreducible vectorssieving algorithms
Contact author(s)
e doulgerakis @ tue nl
History
2021-10-18: revised
2021-09-17: received
See all versions
Short URL
https://ia.cr/2021/1203
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1203,
      author = {Emmanouil Doulgerakis and Thijs Laarhoven and Benne de Weger},
      title = {The irreducible vectors of a lattice: Some theory and applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1203},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1203}},
      url = {https://eprint.iacr.org/2021/1203}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.