scientific article; zbMATH DE number 1313325

From MaRDI portal
Publication:4254898





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.











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)