TUD Technische Universität Darmstadt
Universitäts- und Landesbibliothek		 ULB Darmstadt

EPDA - Elektronische Publikationen Darmstadt

Autor: Overbeck, Raphael
Titel:Public Key Cryptography based on Coding Theory
Dissertation:TU Darmstadt, Fachbereich Informatik, 2007

Die Dokumente in PDF 1.3 (mit Adobe Acrobat Reader 4.0 zu lesen):

Overbeck_Dissertation_ULB.pdf (545341 Byte)

Abstract auf Deutsch:


In dieser Arbeit betrachten wir sowohl den statistischen Fehlerkorrekturalgorithmus zum Lösen des allgemeinen Problems der Fehlerkorrektur als auch die Varianten des Kryptosystems von J.R. McEliece, welche auf Gabidulincodes basieren. Der erste Teil der Doktorarbeit behandelt die generellen Konzepte codierungstheoriebasierter Kryptographie und die Sicherheit der zugrunde liegenden Probleme. Nach einer Einleitung zu den grundlegenden Begriffen und Prinzipien betrachten wir zunächst den statistischen Fehlerkorrekturalgorithmus (welcher als eine Variante des iterativen Decodieren gesehen werden kann. Für einen gegebenen Code sucht der statistischen Fehlerkorrekturalgorithmus zunächst eine große Menge kleiner Codewörter im dualen Code und ist dann imstande, einen gewissen Anteil fehlerhafter Codewörter in konstanter Zeit zu korrigieren. Dieses kann ein großer Vorteil sein, wenn man viele fehlerhafte Nachrichten korrigieren muß. Im ursprünglichen Artikel findet sich leider keine Analyse der Phase der Vorberechnungen. Experimente belegen, daß die dort angegebenen Grenzen der Speicherkomplexität zu optimistisch sind. Wir analysieren detailliert die Speicherkomplexität des Algorithmus und bestimmen neue theoretisch fundierte Grenzen. In unseren Experimenten zeigt sich, daß diese neuen Grenzen präziser als die vorherigen sind, welches die vereinfachenden Annahmen bestätigt, welche wir für unsere Analyse benötigen. Weiterhin analysieren wir die Zeitkomplexität der Vorberechnungen und folgern, daß diese wesentlich höher ist, als vom Autor des ursprünglichen Artikels angegeben. Ein Nachteil der ursprünglichen Version des Algorithmus ist das Vernachlässigen eines Großteils der mit der Vorberechnung gewonnenen Information. Wir zeigen, wie man den Algorithmus verbessern kann, indem man die Information aus den Vorberechnungen besser nutzt. Trotz der Verbesserung ist unsere Variante des statistischen Fehlerkorrekturalgorithmus langsamer als ein einzelner Aufruf des Algorithmus von Canteaut und Chabaud zum Lösen des allgemeinen Problems der Fehlerkorrektur. Folglich schließen wir, daß die aktuell vorgeschlagenen Parameter für das McEliece Kryptosystem weiterhin als sicher anzunehmen sind. Nichtsdestotrotz scheint eine weitere Verbesserung des statistischen Fehlerkorrekturalgorithmus möglich, falls ein signifikantes Beschleunigen der Vorberechnungen erreicht werden kann. Ferner könnten die von uns dargestellten Methoden auf das iterative Decodieren übertragen werden. Deshalb bleibt es eine offene Frage, ob Angriffe auf das McEliece Kryptosystem existieren, welche besser als die bislang bekannten sind. Der zweite Teil der Arbeit ist Gabidulincodes und ihrer Anwendung in der Kryptographie wie im GPT Kryptosystem von der EuroCrypt'91 und dessen Varianten gewidmet. Die in Gabidulincodes verwendete Norm ist die Rangnorm und nicht die Hamming Norm, weswegen sie die Korrektur von Fehlermustern ermöglichen. Wir präsentieren einen neuen Fehlerkorrekturalgorithmus, welcher auf ``interleaved'' Gabidulincodes übertragbar ist. Dort ermöglicht er in den meisten Fällen die Korrektur von Rangdistanzfehlern bis zum Anteil der im Codewort redundanten Information, welches weit über die normale Fehlerkorrekturkapazität hinaus geht. Das Resultat ist damit analog zu dem von Bleichenbacher, Kiayias und Yung für GRS Codes. Die Frage, ob Gabidulincodes für die Anwendung in der Kryptographie geeignet sind, wurde zwar in den vergangenen Jahren verstärkt diskutiert, blieb aber ungelöst. Der Vorschlag von Gabidulin, Paramonov und Tretjakov ist vielversprechend, da das Problem der Fehlerkorrektur in der Rangnorm schwieriger ist als in der Hamming Norm. Daher bieten solche Codes eine bessere Sicherheit gegenüber allgemeinen Algorithmen zur Fehlerkorrektur, während die Größe des öffentlichen Schlüssels kleiner ist als beim Kryptosystem von McEliece. Trotz der höheren Sicherheit gegenüber den Angriffen auf die Schlüsseltexte gelang es Gibson in den Jahren '95 und '96 das GPT Kryptosystem mit den ursprünglich vorgeschlagenen Parametern zu brechen, indem er den privaten Schlüssel angriff. Wir fassen die in der Folge vorgeschlagenen Strategien zusammen, die Angriffe auf den privaten Schlüssel verhindern sollten. Diese Strategien sind sehr interessant, da die meisten bei allen auf Codierungstheorie basierten Kryptosystemen eingesetzt werden können und zu einem sicheren asymmetrischen Kryptosystem führen können (aber dies nicht notwendigerweise tun). Weiterhin analysieren wir diese Strategien auf ihre Wirksamkeit bei Gabidulincodes, und betrachten sowohl die Sicherheit der Schlüsseltexte als auch die der privaten Schlüssel. Zunächst zeigen wir, wie man mit unserem neuen Fehlerkorrekturalgorithmus für Gabidulincodes Schlüsseltexte des GPT Kryptosystems in Polynomialzeit angreifen kann. Danach übertragen wir unsere überlegungen auf Angriffe auf den privaten Schlüssel. Wir zeigen abschließend, daß die Struktur der Gabidulincodes erlaubt, den privaten Schlüssel in allen Parametersätzen und Varianten des GPT Kryptosystems anzugreifen.

Abstract auf Englisch:

In this thesis we view the statistical decoding algorithm, which tries to solve the general decoding problem as well as the variants of the McEliece cryptosystem based on Gabidulin codes. The first part of the thesis is dedicated to the general concept of public key cryptography on the basis of coding theory and the security of the underlying problems. Thus after presenting the basic principles, we study the proposal of statistical decoding (which can be seen as a variant of iterative decoding). For a given code, the statistical decoding algorithm precomputes many low weight check vectors and is afterwards able to correct a certain fraction of erroneous codewords in constant time. This can be a great advantage if there are many erroneous messages to decode. Unfortunately, in the original paper an analysis of the precomputation phase is not included and in experiments given bounds for the space complexity of the statistical decoding algorithm turned out to be too optimistic. We give a robust space complexity analysis of the proposed algorithm and deduce new theoretical bounds. In experiments, these new bounds proof to be more accurate than the previous ones, corroborating some simplifying assumptions in our analysis. Further, we analyze the time complexity of the precomputation phase and draw the conclusion that it is much higher than estimated. A main flaw of the initial algorithm is the fact that most of the information obtained during the precomputation phase is discarded. We improve the statistical decoding algorithm by taking more information out of the precomputation. This results in an algorithm with better success probability as the initial one. Nevertheless, even this improved algorithm turns out to be slower than a single run of the Canteaut and Chabaud algorithm. We thus conclude that for the McEliece PKC the parameter sets currently proposed remain secure. However, following our approach, further improvement of the statistical algorithm seems to be possible, especially if one could achieve a significant speed-up of the precomputation. Further, the presented methods could be combined with the iterative decoding approach. Therefore, the question if there are better attacks on the McEliece cryptosystem than the existing ones remains open. The second part of the thesis is dedicated to Gabidulin codes and their application to cryptography like in the GPT proposal from EuroCrypt'91 and its variants. Gabidulin codes use \textnormal{rank distance} instead of hamming distance and thus can be used to correct pattern errors in communication channels. We present a new error correction algorithm for Gabidulin codes, which can be extended to interleaved Gabidulin codes. We show that this extension allows to correct errors in rank metric up to the amount of redundancy in a large number of cases, which is far beyond the initial error correction bound. Consequently our result is analogous to the one of Bleichenbacher, Kiayias and Yung for GRS codes. The question whether Gabidulin codes can be used for cryptographic applications was strongly discussed in the last years, but remained unsolved. The GTP proposal by Gabidulin, Paramonov and Tretjakov is promising, as the general decoding problem in rank metric is more difficult than in hamming metric. Thus, this variant offers more resistance to general decoding attacks than the McEliece scheme while having a much smaller public key size. However, the GPT cryptosystem was attacked by Gibson in '95 and '96, who showed how to recover the secret key for initial parameter sets. We gather up the sequently proposed strategies to prevent an attacker from recovering the secret key, which are highly interesting as most of them are applicable to all code based cryptosystems and can (but do not necessarily) lead to secure public key cryptosystems. Further, we analyze the effectiveness of these strategies in the case of GPT under two different aspects: The security of the ciphertexts and the security of the secret keys. First, we show how to take profit of our new error correction algorithm for Gabidulin codes, to attack ciphertexts of cryptosystems using Gabidulin codes in polynomial time. In a second part, we show how to identify the structure of the underlying Gabidulin code in the public key and develop a polynomial time key recovery attack.
Dokument aufgenommen :2007-06-12
URL:http://elib.tu-darmstadt.de/diss/000823