scientific article; zbMATH DE number 1313325
Unter einem Gitter vestehen wir eine (durch eine Gitterbasis erzeugte) diskrete, additive Untergruppe des \(\mathbb{R}^n\). Wir entwickeln Aufzählungsverfahren zur Bestimmung eines (bezüglich einer beliebig vorgegebenen Norm) nachweislich kürzesten, von Null verschiedenen Gittervektors, die in möglichst hohen Dimensionen vertretbare Rechenzeiten besitzen. Wir lösen Rucksackprobleme durch Reduktion auf die Suche nach einem Gittervektor mit \(\ell_\infty\)-Norm 1. Mit unserem Aufzählungsverfahren bezüglich der \(\ell_\infty\)-Norm gelingt es, alle Rucksackprobleme bis Dimension 66 effizient zu lösen. Wir brechen mit diesem Verfahren Kryptosysteme, die auf dem Rucksackproblem basieren. Der Aufwand zur Bestimmung eines kürzesten, von Null verschiedenen Gittervektors hängt entscheidend von der Wahl der Basis des jeweiligen Gitters ab. Er wird umso geringer, je besser die Basisvektoren die kürzesten Gittervektoren approximieren. Wir untersuchen daher verschiedene Reduktionsbegriffe. Wir zeigen Schranken für die Güte der Approximation und entwickeln Algorithmen zur Bestimmung von reduzierten Gitterbasen. Für große Dimensionen reichen selbst ``gut vorreduzierte Gitterbasen nicht mehr aus, um einen kürzesten Gittervektor effizient zu bestimmen. Wir entwickeln ein probabilistisches Aufzählungsverfahren, das für zufällige Eingaben eine fest vorgegebene Erfolgswahrscheinlichkeit beweisbar nicht unterschreitet.
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- A sieve algorithm for the shortest lattice vector problem
- scientific article; zbMATH DE number 2196508
- scientific article; zbMATH DE number 3972987
- Sampling methods for shortest vectors, closest vectors and successive minima
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4254898)