Open Access

Gerold Jäger

• Gitter sind diskrete, additive Untergruppen des IRm, ein linear unabhängiges Erzeugendensystem eines Gitters heißt Gitterbasis. Die Anzahl der Basisvektoren eines Gitters ist eindeutig bestimmt und heißt Rang des Gitters. Zu jedem Gitter vom Rang n gibt es mehrere Gitterbasen, die man alle erhält, indem man eine Basismatrix B = [b1, · · · , bn] von rechts mit allen Matrizen aus der Gruppe GLn(ZZ) multipliziert. Eine wichtige Fragestellung der Gittertheorie ist es, zu einem gegebenen Gitter einen kürzesten, vom Nullvektor verschiedenen Gittervektor zu finden. Dieses Problem heißt das kürzeste Gittervektorproblem . Ein dazu verwandtes Problem ist das "nächste Gittervektorproblem", das zu einem beliebigen Vektor x aus IRm einen Gittervektor sucht, dessen Abstand zu x minimal ist. Aus dem "kürzesten Gittervektorproblem" entwickelte sich die Gitterbasenreduktion, deren Ziel es ist, eine gegebene Gitterbasis in eine Gitterbasis zu transformieren, deren Vektoren bzgl. der Euklidischen Norm kurz und möglichst orthogonal zueinander sind. Wichtig für die Güte einer Reduktion ist der Begriff der sukzessiven Minima ¸1(L), · · · , ¸n(L) eines Gitters L. Dabei ist ¸i(L) die kleinste reelle Zahl r > 0, für die es i linear unabhängige Vektoren cj 2 L gibt mit kcjk · r für j = 1, · · · , i. Man versucht, für ein Gitter L eine Gitterbasis b1, · · · , bn zu finden, bei der die Größe kbik / ¸i(L) für i = 1, · · · , n möglichst klein ist. Für Gitter vom Rang 2 liefert das Gauß'sche Reduktionsverfahren eine Gitterbasis mit kbik = ¸i(L) für i = 1, 2. Eine Verallgemeinerung der Gauß-Reduktion auf Gitter mit beliebigem Rang ist die im Jahre 1982 von Lenstra, Lenstra, Lovasz vorgeschlagene L3-Reduktion einer Gitterbasis, deren Laufzeit polynomiell in der Bitlänge der Eingabe ist. L3-reduzierte Gitterbasen approximieren die sukzessiven Minima bis auf einen (im Rang des Gitters) exponentiellen Faktor. Die vorliegende Arbeit besteht aus zwei Teilen. Im ersten Teil (Kapitel 1-6) wird ein neues Reduktionskonzept von M. Seysen aus der Arbeit "A Measure for the Non-Orthogonality of a Lattice Basis" behandelt und im zweiten Teil (Kapitel 7) ein aktuelles Ergebnis von M. Ajtai über die Faktorisierung ganzer Zahlen aus "The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions"[2]. Seysen führte in [13] zu einer gegebenen Gitterbasis b1, · · · , bn die Größe ¾(A) ein, die nur von den Einträgen der zugehörigen Gram-Matrix A = [b1, · · · , bn]T · [b1, · · · , bn] und der Inversen A 1 abhängt. Sie hat die Eigenschaft, daß für jede Gitterbasis b1, · · · , bn mit Gram-Matrix A gilt, daß ¾(A) ¸ 1, wobei die Gleichheit genau dann gilt, wenn b1, · · · , bn orthogonal ist. Aus dieser Defintion ergibt sich folgender Reduktionsbegriff: Eine Gitterbasis b1, · · · , bn mit Gram-Matrix A heißt genau dann ¿ -reduziert, wenn ¾(A) minimal für alle Basen des Gitters ist. Der wesentliche Unterschied der ¿-Reduktion zur L3-Reduktion ist, daß die Größe ¾(A) unabhängig von der Reihenfolge der Basisvektoren ist, so daß eine ¿ -reduzierte Gitterbasis bei beliebiger Permutation der Basisvektoren ¿ -reduziert bleibt. Die ¿-Reduktion reduziert also im Gegensatz zur L3-Reduktion die Basisvektoren gleichmäßig. Seysen zeigte, daß man zu jedem Gitter vom Rang n eine Gitterbasis mit Gram-Matrix A findet, so daß ¾(A) durch eO((ln n)2) beschränkt ist. Daraus läßt sich ableiten, daß ¿ -reduzierte Gitterbasen eines Gitters vom Rang n die sukzessiven Minima bis auf den Faktor eO((ln n)2) approximieren. Da es sich bei der ¿-Reduktion um einen sehr starken Reduktionsbegriff handelt, für den es schwer ist, einen effizienten Algorithmus zu finden, definiert man folgenden schwächeren Reduktionsbegriff: b1, · · · , bn heißt genau dann ¿2-reduziert, wenn keine Basistransformation der Form bj := bj +k · bi mit 1 · i 6= j · n und k 2 ZZ die Gr¨oße ¾(A) erniedrigt. Für n = 2 entspricht die ¿-Reduktion sowohl der ¿2- Reduktion als auch der Gauß-Reduktion. Für die ¿2-Reduktion findet man einen effizienten Algorithmus. Wendet man diesen Algorithmus auf Rucksackprobleme an, so ergibt sich, daß durch einen Algorithmus, bestehend aus ¿2-Reduktion und anschließender L3-Reduktion, bei großer Dichte und bei kleiner Dimension wesentlich mehr Rucksackprobleme gelöst werden als durch den L3-Algorithmus. Die Faktorisierung großer ganzer Zahlen ist ein fundamentales Problem mit großer kryptographischer Bedeutung. Schnorr stellte in [11] erstmals einen Zusammenhang zwischen Gitterbasenreduktion und Faktorisierung her, indem er das Faktorisieren ganzer Zahlen auf das "nächste Gittervektorproblem in der Eins-Norm" zurückführte. Adleman führte in [1] das Faktorisieren ganzer Zahlen sogar auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" zurück, allerdings unter zahlentheoretischen Annahmen. In [2] stellte Ajtai ein neues Ergebnis vor, in dem er das Faktorisieren ganzer Zahlen auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" ohne zusätzliche Annahmen zurückführte.