Short Bases of Lattices over Number Fields

Claus Fieker, Damien Stehle

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

22 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationAlgorithmic Number Theory; Proceedings of the 9th International Symposium on Algorithmic Number Theory (ANTS-IX); Lecture Notes in Computer Science 6197
EditorsGuillaume Hanrot, Francois Morain, Emmanuel Thome
Place of PublicationGermany
PublisherSpringer, Springer Nature
Pages157-173
Number of pages17
ISBN (Print)9783642145179
DOIs
Publication statusPublished - 2010
EventThe 9th International Symposium on Algorithmic Number Theory (ANTS-IX) - Nancy, France
Duration: 19 Jul 201023 Jul 2010

Conference

ConferenceThe 9th International Symposium on Algorithmic Number Theory (ANTS-IX)
CityNancy, France
Period19/07/1023/07/10

Fingerprint

Dive into the research topics of 'Short Bases of Lattices over Number Fields'. Together they form a unique fingerprint.

Cite this