A coding-theoretic approach to cryptanalysis

Diese Arbeit beschäftigt sich mit der Anwendbarkeit codierungstheoretischer Methoden in der Kryptanalyse und liefert neue Einsichten in die Sicherheit verschiedener kryptographischer Verfahren. 1) Es wird ein verallgemeinertes Framework für die Klasse sogenannter "Information Set Decoding" (ISD) Algorithmen eingeführt. 2) Es wird ein neuer ISD Algorithmus vorgestellt, der durch Anwendung der sogenannten Repräsentationstechnik zu einer exponentiellen Verbesserung der asymptotischen Laufzeit führt. Innerhalb des verallgemeinerten Frameworks wird ein formaler Beweis der asymptotischen Verbesserung für Codes beliebiger Rate 0<R<1 geführt. 3) Es werden verschiedene Anwendungen in der Kryptanalyse diskutiert, bspw. wird die Sicherheit der McEliece Einwegfunktion untersucht und es werden spezielle Instanzen der "Learning Parities with Noise" Annahme effizient gebrochen. Ein wesentlicher Teil dieses Abschnittes ist eine detaillierte nicht-asymptotische Analyse der vorgestellten Algorithmen.In this thesis we study the applicability of coding-theoretic algorithms to cryptanalysis and provide new insights into the practical security of different cryptographic primitives. 1) We introduce a new generalised framework for the class of "Information Set Decoding" (ISD) algorithms. 2) By applying the so-called representation technique, we design a new ISD algorithm which asymptotically achieves an exponential improvement over all known methods. Within the generalised ISD framework we provide a rigorous formal proof of superiority of the new algorithm for arbitrary code rates 0<R