Short Bases of Lattices over Number Fields

Claus Fieker and Damien Stehlé

Abstract: Lattices over number fields arise from a variety of sources in algorithmic algebra and more recently cryptography. Similar to the classical case of Z-lattices, the choice of a nice, ``short'' (pseudo)-basis is important in many applications. In this article, we provide the first algorithm that computes such a ``short'' (pseudo)-basis. We utilize the LLL algorithm for Z-lattices together with the Bosma-Pohst-Cohen Hermite Normal Form and some size reduction technique to find a pseudo-basis where each basis vector belongs to the lattice and the product of the norms of the basis vectors is bounded by the lattice determinant, up to a multiplicative factor that is a field invariant. As it runs in polynomial time, this provides an effective variant of Minkowski's second theorem for lattices over number fields.

Download: pdf.
Homepage