TU Darmstadt / ULB / TUprints

Attacking and Defending Code-based Cryptosystems

Niebuhr, Robert (2012)
Attacking and Defending Code-based Cryptosystems.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
dissertation.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: Attacking and Defending Code-based Cryptosystems
Language: English
Referees: Buchmann, Prof. Johannes ; Paulo, Prof. Barreto ; Pierre-Louis, Prof. Cayrel
Date: 4 July 2012
Place of Publication: Darmstadt
Collation: 144
Date of oral examination: 28 June 2012
Abstract:

Today, cryptographic applications are used in nearly all areas of our lives, including the economy, health, military, and entertainment. Without them, society would change in ways we can hardly imagine. Since the publication of Shor's algorithm in 1994, however, we know that those cryptographic applications based on the problems of factoring and discrete logarithm are threatened by quantum computer attacks. Most current applications belong to this category. Code-based cryptography is conjectured to be secure against quantum computer attacks, and it has several other advantages. Firstly, it exhibits advanced security properties: for example, binary Goppa codes are considered a secure choice for many schemes, and the McEliece encryption scheme has not been broken in over 30 years since its publication (merely an adjustment of the parameters was necessary). Secondly, since code-based cryptosystems are based on linear algebra instead of, for example, arithmetic using floating-point numbers, they are usually very fast and can be implemented on devices with a low computing power and without cryptographic co-processor. Finally, the complexity of attacks against code-based schemes can usually be estimated accurately in the expected number of binary operations instead of relying on the asymptotic O-notation. This allows a precise computation of the security level a scheme provides. The major drawback of most code-based schemes is their large key size.

This thesis contributes to two important aspects in the development of cryptographic applications. The first concerns the use of secure cryptographic primitives. While schemes like the McEliece and Niederreiter encryption schemes have been studied for a long time and are considered secure, new schemes or variants of existing ones are constantly being developed. The objectives are to decrease the key size, create schemes with new properties, or to introduce other improvements. In order to assess the security of these schemes, they have to be subjected to all relevant attacks. We contribute to this aspect by introducing a new type of attack, a broadcast attack, and by improving and generalizing existing attacks. Secondly, once a secure primitive has been found, appropriate code parameters have to be selected. This choice needs to reflect several constraints. Most importantly, the parameters have to provide a sufficient security level. Other constraints concern different aspects of efficiency, e.g. encryption or decryption time, required bandwidth, memory size etc. Our contribution is the selection of optimal parameters for the McEliece cryptosystem and the QD-CFS signature scheme by applying Lenstra and Verheul's framework.

Alternative Abstract:
Alternative AbstractLanguage

Gegenwärtig werden kryptographische Anwendungen in fast allen Bereichen des Lebens genutzt, einschließlich Wirtschaft, Gesundheitswesen, Militär und Unterhaltung. Ohne sie würde sich unser Leben in unvorhersehbarer Weise verändern. Seit der Veröffentlichung von Shor's Algorithmus in 1994 ist allerdings bekannt, dass kryptographische Anwendungen, die auf den Problemen des Faktorisierens oder diskreten Logarithmus basieren, von Quantencomputer-Angriffen bedroht sind. Dazu gehören fast alle heutigen Anwendung. Es wird davon ausgegangen, dass code-basierte Kryptographie sicher ist gegen Angriffe von Quantencomputern. Darüber hinaus hat sie einige weitere Vorteile. Erstens weist sie gute Sicherheits-Eigenschaften auf: Beispielsweise werden binäre Goppacodes als eine sichere Wahl für code-basierte Anwendungen angesehen, und das McEliece-Verschlüsselungsverfahren wurde seit seiner Veröffentlichung vor über 30 Jahren nicht gebrochen (es war lediglich eine Anpassungen der Parameter erforderlich). Zweitens können code-basierte Anwendungen vergleichsweise einfach auf Geräten mit geringer Rechenkapazität und ohne kryptographischem Coprozessor laufen, da sie nur lineare Algebra nutzen, anstelle von z.B. Fließkommaberechnungen. Schließlich kann die Komplexität von Angriffen gegen code-basierte Anwendungen meist präzise in der erwarteten Anzahl von Operationen berechnet werden, ohne die asymptotische O-Notation nutzen zu müssen. Dies erlaubt eine genaue Berechnung des Sicherheitslevels dieser Anwendungen. Der hauptsächliche Nachteil der meisten code-basierten Anwendungen ist die beträchtliche Schlüsselgröße von mehreren Kilobyte bis Megabyte.

Diese Arbeit leistet einen Beitrag zu zwei wichtigen Aspekten der Entwicklung kryptographischer Anwendungen. Der erste betrifft die Verwendung sicherer Primitive. Während Verfahren wie McEliece und Niederreiter seit langer Zeit analysiert werden und heute als sicher gelten, werden kontinuierlich Varianten und neue Verfahren entwickelt. Die Zielsetzung ist typischerweise eine Verringerung der Schlüsselgröße oder die Präsentation neuer Eigenschaften und anderer Verbesserungen (wie z.B. höhere Effizienz). Zur Bestimmung der Sicherheit dieser neuen Verfahren, müssen diese gegen alle relevanten Angriffe getestet werden. Unser Beitrag besteht in der Entwicklung eines neuen Angriffs, des Broadcast-Angriffs, sowie der Weiterentwicklung und Generalisierung existierender Angriffe. Der zweite Aspekt betrifft die Wahl sicherer Parameter, welche für eine praktische Anwendung der Primitive erforderlich ist. Die hierfür zu berücksichtigen Einschränkungen sind in erster Linie die Gewährleistung eines ausreichenden Sicherheitslevels; weitere betreffen verschiedene Aspekte von Effizienz, z.B. Ver- und Entschlüsselungszeit, erforderliche Bandbreite oder Speichergröße usw. Unser Beitrag ist die Bestimmung optimaler Parameter für das McEliece-Verschlüsselungsverfahren sowie das QD-CFS Signaturschema durch Anwendung des Systems von Lenstra und Verheul.

German
Alternative keywords:
Alternative keywordsLanguage
Kryptographie, fehlerkorrigierende Codes, McEliece, Niederreiter, HyMES, Lenstra, Verheul, Broadcast Angriff, Statistisches Dekodieren, Information Set Decoding, broadcast attack, Auswahl optimaler ParameterGerman
Cryptography, error-correcting codes, McEliece, Niederreiter, HyMES, Lenstra, Verheul, broadcast attack, statistical decoding, information set decoding, generalized broadcast attack, selecting optimal parametersEnglish
URN: urn:nbn:de:tuda-tuprints-30312
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 09 Jul 2012 07:11
Last Modified: 09 Jul 2020 00:10
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3031
PPN: 305225294
Export:
Actions (login required)
View Item View Item