Studies cryptosystems built using error correcting codes, Hamming metric and metric rank. - Archive ouverte HAL Access content directly
Theses Year : 2009

Studies cryptosystems built using error correcting codes, Hamming metric and metric rank.

Etudes de systèmes cryptographiques construits à l'aide de codes correcteurs, en métrique de Hamming et en métrique rang.

(1)
1

Abstract

This thesis explores two different approaches to reduce the size of the public key cryptosystems based on error correcting codes. One idea that meaning is the use of families of codes with high correction capability, such as geometric codes. Since the attack Sidelnikov and Shestakov, we know that an attacker can find the structure of a Reed-Solomon code used in the public key. We have managed to adapt to the hyperelliptic curves attack method developed by cons Minder elliptic codes. We are particularly able to attack in polynomial time system Janwa and Moreno on codes developed geometric genus 2 or more. A second idea is the use of error correcting codes for the rank metric. This enormously complicates the decoding attacks, which can no longer use a window of information to try to decode. We can thus protect themselves against attacks decoding using a public key of Bollywood. In this context, we present a public key cryptosystem based on the problem of reconstruction of linear polynomials. We show that our system is fast, uses keys of reasonable size, and resists all known attacks in the state of the art.
Cette thèse étudie deux approches différentes visant à réduire la taille de la clé publique des cryptosystèmes à base de codes correcteurs. Une première idée en ce sens est l'utilisation de familles de codes à haute capacité de correction, comme les codes géométriques. Depuis l'attaque de Sidelnikov et Shestakov, on sait qu'un attaquant peut retrouver la structure d'un code de Reed-Solomon utilisé dans la clé publique. Nous avons réussi à adapter aux courbes hyperelliptiques la méthode d'attaque développée par Minder contre les codes elliptiques. Nous sommes notamment en mesure d'attaquer en temps polynomial le système de Janwa et Moreno développé sur des codes géométriques de genre 2 ou plus. Une seconde idée est l'utilisation de codes correcteurs pour la métrique rang. Celle-ci complique énormément les attaques par décodage, qui ne peuvent plus utiliser une fenêtre d'information pour tenter de décoder. On peut ainsi se prémunir des attaques par décodage en utilisant une clé publique de faible taille. Dans cette optique, nous présentons un cryptosystème à clé publique basé sur le problème de reconstruction de polynômes linéaires. Nous montrons que notre système est rapide, utilise des clés de taille raisonnable, et résiste à toutes les attaques connues dans l'état de l'art.
Fichier principal
Vignette du fichier
manuscrit.pdf (702.19 Ko) Télécharger le fichier
Loading...

Dates and versions

pastel-00005288 , version 1 (21-07-2010)

Identifiers

  • HAL Id : pastel-00005288 , version 1

Cite

Cédric Faure. Etudes de systèmes cryptographiques construits à l'aide de codes correcteurs, en métrique de Hamming et en métrique rang.. Sciences de l'information et de la communication. Ecole Polytechnique X, 2009. Français. ⟨NNT : ⟩. ⟨pastel-00005288⟩
396 View
595 Download

Share

Gmail Facebook Twitter LinkedIn More