4.5.4 Knapsacks mit geringer Dichte

Einer der besten Algorithmen für das allgemeine Subset-Sum Problem ist der Meet-in-the-Middle Algorithmus.
Für Knapsack-Vektoren mit geringer Dichte gibt es eine effektivere Methode. Hierbei wird das Subset-Sum Problem reduziert auf das Problem, einen Vektor zu finden, der eine kleine Länge hat.

Definition
Gegeben sei ein Knapsack-Vektor A = (a₁, ..., a_n). Sei a_max das größte Element in A: a_max = max_i a_i, i = 1 ... n. Dann ist die Dichte d_A des Knapsack-Vektors A

In Kryptosystemen, die auf dem Subset-Sum Problem basieren, ist die Dichte eines Knapsacks fast immer kleiner als Eins, da andernfalls mehrere Teilmengen A' von A existieren können, die sich zu einer Summe s aufsummieren. Dann wäre eine eindeutige Entschlüsselung nicht mehr möglich.

Definition
Ein Vektor v aus Rⁿ ist ein geordnetes Tupel mit Elementen v_i aus R:

Definition
Sei v = (v₁, v₂, ..., v_n) ein Vektor aus Rⁿ. Dann hat v die (euklidische) Länge

Definition
Sei {b_i}_i=1...m eine Menge von Vektoren aus Rⁿ mit m <= n. Genau dann ist {b_i} linear abhängig, wenn es k_i aus R gibt mit

Definition
Sei {b_i}_i=1...n eine Menge von n linear unabhängigen Vektoren aus Rⁿ. Dann ist {b_i}_i=1...n eine Basis für Rⁿ. Jeder Vektor v aus Rⁿ kann eindeutig geschrieben werden kann als Linearkombination der Menge {b_i}_i=1...n

Definition
Seien m linear unabhängige Vektoren {b_i}_i=1...m gegeben, m <= n. Dann ist das Gitter (lattice) L, das von {b_i}_i=1...m erzeugt wird, die Menge aller ganzzahligen Linearkombinationen von {b_i}:

Eng verbunden mit einem Gitter L ist das kürzeste-Vektor Problem (SVP: shortest vector problem): für ein gegebenes Gitter L ist der kürzeste Vektor aus L zu finden, der ungleich dem Nullvektor ist.
Nimmt man als Länge eines Vektors die Supremumsnorm, dann ist das Problem NP-hart. Für die euklidische Norm jedoch läßt sich die Aussage nicht machen. Es ist ein offenes Problem.
(Die Supremumsnorm || ||₈eines Vektors v = (v₁, ..., v_n) ist definiert als ||v||₈ = max |v_i|_i=1...n.)

Ein Gitter L kann durch mehrere Basen beschrieben werden. Eine "gute" Basis für ein Gitter besteht aus Vektoren mit möglichst "kleinen" Längen und wird reduzierte Basis gennant. Die Gitter-Reduktions-Theorie befasst sich damit, "gute" Basen für ein Gitter L zu erzeugen.

Algorithmen, die eine gegebene Basis B für ein Gitter L in eine reduzierte Basis überführen, werden Gitter-Basis-Reduktionsalgorithmen genannt. Ein Vertreter dieser Algorithmen ist der nach seinen Entwicklern Lenstra, Lenstra und Lovász benannte L³-Algorithmus. Eine L³-reduzierte Basis hat u.a. die Eigenschaft, dass ihr erster Vektor, b'₁ um höchstens einen exponentiellen Faktor größer ist als der kleinste nichtnull Vektor aus L (bzgl. der euklidischen Länge):

Im Folgenden wird gezeigt, wie ein Subset-Sum Problem gelöst werden kann, wenn der Knapsack-Vektor eine geringe Dichte hat. Da kryptographische Knapsack-Vektoren fast immer eine Dichte kleiner als Eins haben, trifft dieses Verfahren auch auf diese zu.

Gegeben

• öffentlicher Knapsack-Schlüssel B = (b₁, ..., b_n)
• Chiffre c = pB = b₁p₁ + ... + b_np_n, p_i aus {0, 1}

Gesucht

• Die Klartextnachricht p

Um aus B und c die Nachricht p zu erhalten, führe nacheinander folgende Schritte aus:

1. Bilde aus dem öffentlichen Schlüssel B und dem Chiffretext c folgende (n+1)×(n+1)-Matrix M
   

   M =
   	1	0	0	...	0	tb1
   	0	1	0	...	0	tb2
   	0	0	1	...	0	tb3
   	...	...	...	...	...	...
   	0	0	0	...	1	tbn
   	0.5	0.5	0.5	...	0.5	tc

   Dabei ist t eine ganze Zahl mit t > (n/4)^1/2.

   Definiere den Vektor m_i als die i-te Zeile von M, i = 1...(n+1). Sei L das Gitter, das von {m_i}_i=1...n erzeugt wird.

   Sei nun p = (p₁, p₂, ..., p_n) die Klartextnachricht, aus der der Chiffretext c hervorgegangen ist.
   Betrachte den Vektor y = p₁m₁ + p₂m₂ + ... + p_nm_n - m_n+1. Da p_i aus {0, 1}, liegt y im Gitter L, das von {m_i} erzeugt wird.
   Vektorenaddition wird durchgeführt, indem die einzelnen Komponenten addiert werden. Die einzelnen Komponenten y_i des Vektors y lauten deshalb
    

   y1 =	p1 + 0 + ... + 0 - 0.5 =  p1 - 0.5
   y2 =	0 + p2 + 0 + ... + 0 - 0.5 = p2 - 0.5
   ...
   yi =	0 + ... + 0 + pi + 0 + ... +0 - 0.5 = pi - 0.5
   ...
   yn =	0 + ... + 0 + pn - 0.5 = pn - 0.5
   yn+1 =	t(b1p1 + b2p2 + ... + bnpn) - tc = 0

   Da p_i aus {0, 1}, gilt y = (±0.5, ±0.5, ..., ±0.5, 0) und ||y|| = (n/4)^1/2. Die Länge von y ist also gering.
   Wenn nun die Dichte des Knapsack-Vektors B, d_B, klein ist, B also große Elemente hat, dann sind die meisten Vektoren, die aus {m_i}_i=1...(n+1) durch ganzzahligeLinearkombinationen entstehen, groß.

2. Der nächste Schritt besteht darin, die Basis {m_i}_i=1...(n+1) zu reduzieren.
3. Sei {m'_i}_i=1...(n+1) die erhaltene reduzierte Basis. Nun wird die Basis überprüft, ob sie Vektoren m'_i enthält, die folgende Form haben:
   m'_i = (±0.5, ±0.5, ..., ±0.5, 0)
   
   Falls kein solcher Vektor m'_i in der Basis enthalten ist, gibt es entweder keine Lösung für (B, c) oder der Basis-Reduktions-Algorithmus hat keine geeignete reduzierte Basis ermittelt.

   Für jeden Vektor m'_k aus {b'_i} mit m'_k = (±0.5, ±0.5, ..., ±0.5, 0) werden nun folgende Schritte ausgeführt:

   • Definiere den Vektor X = (x₁, x₂, ..., x_n) durch x_i = 0.5 + m'_{k, i} , i = 1 ... n
   • Berechne die Summe s = XB = x₁b₁ + ... + x_nb_n
   • Falls s = c, ist X der gesuchte Lösungsvektor für (B, c), d.h. X ist die Klartextnachricht
   
   Falls s != c, dann
   • definiere X = (x₁, x₂, ..., x_n) durch x_i = 0.5 - m'_{k, i} , i = 1 ... n
   • berechne die Summe s = XB = x₁b₁ + ... + x_nb_n
   • Falls s = c, ist X die Klartextnachricht für den Chiffretext c

In [CO91] wird gezeigt, dass das Subset-Sum Problem für Knapsack-Vektoren mit Dichte d < 0.9408... fast immer gelöst werden kann.
Voraussetzung ist ein Orakel: ein fiktiver Algorithmus, der eine gegebene Basis für ein Gitter L derart reduziert, dass die dabei erhaltene reduzierte Basis IMMER den kürzesten nichtnull Vektor aus L enthält.
Gesucht ist dann die Wahrscheinlichkeit, dass (±0.5, ±0.5, ..., ±0.5, 0) der kleinste Vektor in L ist.
Andersherum, die Wahrscheinlichkeit, dass ein küzerer Vektor aus L existiert als (±0.5, ±0.5, ..., ±0.5, 0), geht gegen Null, wenn n gegen unendlich geht und der Knapsack-Vektor eine Dichte d < 0,9408... hat.

Die Voraussetzung, den kürzesten Vektor aus L zu finden, trifft beim L³ Algorithmus nicht zu. Hier kann u.a. nur garantiert werden, dass der erste Vektor der reduzierten Basis B', b'₁, in der Länge beschränkt ist:

||b'₁|| <= 2^(n-1)/2||v||, v aus L

In der Praxis ist der L³-Algorithmus aber wesentlich besser als die eben erwähnte Abschätzung.

---

Applet starten

 

Shamirs Algorithmus