Designing and Improving Code-based Cryptosystems

In modern cryptography, the security of the most secure cryptographic primitives is based on hard problems coming from number theory such as the factorization and the discrete logarithm problem.However, being mainly based on the intractability of those problems seems to be risky. In 1994, Peter Shor showed how these two problems can be solved in polynomial time using a quantum computer.

In contrast, crypttographic primitives based on problems from coding theory are believed to resistquantum computer based attacks and the best known attacks have exponential running time. Alongwith post-quantum security, code-based systems offer other advantages for present-day applicationsdue to their excellent algorithmic efficiency. Actually, they run faster than traditional cryptosystemslike RSA, since they only require very simple operations like shifts and XORs instead of expensivecomputations over big integers. However, although efficient, most code-based schemes suffer fromconsiderably large key sizes. Codes with algebraic structure such as quasi-cyclic and quasi-dyadiccodes, were proposed to overcome the key size issue, but it has been shown to be insecure against algebraic cryptanalysis.

This thesis contributes to the research and development of code-based cryptosystems. In particular,we are interested in developing as well as improving three important primitives: stream ciphers andhash functions. We study the FSB hash function and the SYND stream cipher and find a way to con-siderably improve their efficiency, while maintaining the security reduction to the same NP-complete problems.

Independently of these results, we address and solve the problem of selecting appropriate parametersets for the binary Goppa code-based McEliece cryptosystem. Based on the Lenstra-Verheul model,we also provide, for the first time, a framework allowing to choose optimal parameters that offer adesired security level in a given year.

In der modernen Kryptographie basiert die Sicherheit der meisten beweisbar sicheren kryptographis-chen Primitiven auf schwierigen Problemen aus der Zahlentheorie wie beispielsweise das Faktorisierungs-und das diskrete Logarithmusproblem. Allerdings allein auf die Hartnäckigkeit dieser Probleme vertrauen scheint riskant zu sein. Im Jahr 1994 zeigte Peter Shor wie beide genannten Probleme in polynomieller Zeit (und somit effizient) mit Hilfe von Quantencomputern gelöst werden können.

Im Gegensatz dazu, sollen kryptographischen Primitive, welche auf Probleme aus der Kodierungs-theorie basieren, gegen Quantuncomputerangriffe resistent sein und die uns heute bekannten Angriffebeno¨tigen exponentielle Laufzeit. Neben der Post-Quantum Sicherheit bieten Code basierte Systemeweitere Vorteile fr die heutigen Anwendungen aufgrund ihrer hervorragenden algorithmischen Effizienz. In der Tat sind sie schneller als herkömmliche Kryptosysteme wie RSA, da sie nur sehr einfache Operationen wie Verschiebungen und XORs benötigen, anstatt den blichen teuren Berechnungen ber große Zahlen. Trotz herausstechender Effizienz leiden die meisten Code basierten Systeme von zu großen Schlüsselgrößen. Die Einführung von Codes mit algebraischer Struktur wie quasi-zyklische und quasi-dyadische Codes, half das Schlüsselgrößenproblem zu berwinden, allerdings hat sich ergeben,dass sie anfällig auf algebraische Kryptoanalyse waren.

Diese Dissertation leistet einen Beitrag zur Forschung und Entwicklung von Code-basierten Kryp-tosysteme. Insbesondere interessieren wir uns für die Entwicklung sowie die Verbesserung der drei wichtigen Primitive: Stromchiffren und Hash-Funktionen. Wir untersuchen die FSB Hashfunktion und die SYND Stromchiffre und zeigen wie deutlich ihre Effizienz verbessert werden kann, whärend die Sicherheitsreduktionen auf die gleichen NP-vollständigen Probleme erhalten und gültig bleiben.

Unabhängig von diesen Ergebnissen, adressieren und lösen wir das Problem der Auswahl geeigneter Parametern für den Goppa Code basierten McEliece Kryptosystem. Basierend auf dem Lenstra-Verheul Modell bieten wir auch, zum ersten Mal, ein Framework, das ermöglicht eine Auswahl von optimalen Parametern zu bestimmen, welche die gewünschte Sicherheitsstufe in einem bestimmtenund konkreten Jahr erfüllt.