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
-
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}
}
