Kryptologie III.7 Komplexitätstheorie in der Kryptologie

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

1. Schaltnetze [PDF-Datei].
2. Schaltnetze für grundlegende Operationen [PDF-Datei].
3. Komplexitätsmaße für Schaltnetze [PDF-Datei].
4. Probabilistische Schaltnetze [PDF-Datei].
5. Polynomiale Schaltnetzfamilien [PDF-Datei].
6. Effiziente Algorithmen [PDF-Datei].
7. Harte Probleme [PDF-Datei].
8. Kryptographische Basisfunktionen [PDF-Datei].

Und der ganze Abschnitt am Stück als PDF-Datei.

Es gibt (mindestens) drei Gründe, warum die »gewöhnliche« Komplexitätstheorie (TURING-Maschinen) für die Kryptologie nicht ausreicht:

1. Die Komplexitätstheorie behandelt die Frage, ob der schlechteste Fall ('worst case') hart ist (d. h., nicht effizient berechenbar). Um eine effiziente Kryptoanalyse auszuschließen, muss der Normalfall hart sein. Insbesondere reicht die Aussage P ungleich NP nicht für die Existenz starker kryptographischer Basisfunktionen aus.
   
   Beispiele für ein solches Phänomen aus anderen Bereichen sind der NEWTON-Algorithmus zur Bestimmung von Polynom-Nullstellen und die Simplex-Methode zur linearen Optimierung, die im schlechtesten Fall hart, im Normalfall aber sehr effizient sind.
   
   »Ordinarily an algorithm that only occasionally works is useless, but a cryptanalysis algorithm that occasionally works makes the cryptosystem useless.« (Neal Wagner's Law CRYPTO4)
   
   
2. Man muss auch probabilistische Algorithmen zulassen, wie bei den zahlentheoretischen Problemen schon einigemale gesehen (sogenannte Monte-Carlo-Algorithmen, die sehr effizient sind, aber nicht immer das richtige Ergebnis liefern).
   
   Die exakte mathematische Behandlung verwendet stochastische Begriffe: Teile des Inputs enstammen einem Wahrscheinlichkeitsraum W; es werden Aussagen über die Verteilung des Outputs gemacht.
   
   
3. Der Kryptoanalytiker kann seine Methode an das konkrete Problem adaptieren; er benötigt nicht unbedingt einen universellen Algorithmus, der für alle Instanzen seines Problems effizient ist. Z. B. kann er je nach Länge des Schlüssels einen anderen Algorithmus zum Brechen der Chiffre wählen.

TURING-Maschinen reichen zur Formalisierung der in der Kryptologie nötigen Komplexitätstheorie also nicht. Man kann das beheben, indem man Familien von TURING-Maschinen zulässt - eine für jede Input-Länge - und auch probabilistischen Input einbezieht. Einfacher zu beschreiben und eleganter anzuwenden ist allerdings ein Maschinenmodell, das auf BOOLEschen Schaltnetzen (englisch: circuits) beruht: probabilistische polynomiale Schaltnetzfamilien (PPS). - Die Umsetzung der gängigen Algorithmen in Schaltnetze ist deutlich einfacher und intuitiver als die Programmierung einer TURING-Maschine.

Wirklich wünschenswert wären natürlich konkrete Komplexitätsaussagen der Art: »Zur Berechnung von ... sind mindestens (z. B.) 10⁸⁰ der folgenden Rechenschritte nötig: ...«. Derartige Ergebnisse hat leider keine Art von Komplexitätstheorie zu bieten, außer für ganz einfache Probleme wie die Auswertung eines Polynoms an einer Stelle. Damit könnte man dann wirklich Sicherheitsaussagen für Verschlüsselungsverfahren mathematisch beweisen, ohne auf unbewiesene Vermutungen und heuristische Argumente zurückgreifen zu müssen.

Die besten bekannten unteren Schranken für viele relevante Komplexitätsabschätzungen enthält das Buch von SHPARLINSKI, siehe das Literaturverzeichnis zur Vorlesung. Eine Einführung in die Schaltnetzkomplexität enthält das Buch

Ingo WEGENER: Komplexitätstheorie. Springer, Berlin 2003. ISBN3-540-00161-1.