TU Darmstadt / ULB / TUprints

Designing and Improving Code-based Cryptosystems

Meziani, Mohammed (2014)
Designing and Improving Code-based Cryptosystems.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
thesis-meziani.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Designing and Improving Code-based Cryptosystems
Language: English
Referees: Buchmann, Prof. Dr. Johannes ; Cayrel, Dr. Pierre-Louis ; Otmani, Prof. Dr. Ayoub
Date: 21 May 2014
Place of Publication: Darmstadt
Date of oral examination: 3 June 2013
Abstract:

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.

Alternative Abstract:
Alternative AbstractLanguage

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.

German
URN: urn:nbn:de:tuda-tuprints-39727
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 23 May 2014 09:43
Last Modified: 23 May 2014 09:43
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3972
PPN: 340583940
Export:
Actions (login required)
View Item View Item