Pierre Loidreau

Liste des publications

Articles de recherche

Asymptotic behaviour of codes in rank metric over finite fields. P. Loidreau, in Designs, Codes and Cryptography 71(1), 105-118, 2014. In this paper, we recall some basic facts about the rank metric. We derive an asymptotic equivalent of the minimum rank distance of codes that reach the rank metric Gilbert--Varshamov bound. We show that the random codes reach GV-bound. Finally, we show that the optimal codes in rank metric have a packing density which is bounded by functions depending only on the base field and on the minimum distance. We show the potential interest in cryptographic applications.

Skew codes of prescribed distance or rank. L. Chaussade, P. Loidreau and F. Ulmer in Designs, Codes and Cryptography, 50(3), 267-284, 2009. Nous présentons deux méthodes de construction de codes en bloc de distance de Hamming ou bien de distance rang prescrite. Nous travaillons avec des anneaux de polynômes tordus et les codes que nous considérons sont des idéaux dans des quotients de ces anneaux. Il y a de forte relations avec les opérateurs linéaires aux différences ainsi qu'avec les polynômes linéaires.

Properties of subspace subcodes of Gabidulin codes. E. M. Gabidulin and P. Loidreau in Advances in Mathematics of Communication, 2(2), 147-158, 2008. Les sous-codes sur des sous-espaces de codes de Gabidulin sont isomorphes à des codes de Gabidulin de même distance rang minimale mais avec des paramètres plus réduits. On montre comment construire des algorithmes d'encodage et de décodage efficaces. On montre également que la somme directe des sous-codes sur des sous-espaces est isomorphe au produit direct de codes de Gabidulin. En utilisant cette structure on montre qu'il y a un grand nombre de motifs d'erreur corrigibles dont le rang excède la capacité de correction théorique des codes. Enfin on s'intéresse au cas des sous-codes sur des sous-corps qui est un cas particulier du cas précédent.

A new public-key cryptosystem based on the problem of reconstructing $p$-polynomials. C. Faure and P. Loidreau in Coding and Cryptography - Revised selected papers of WCC 2005, 2006, LNCS 3969, pp 304-315 Nous présentons un nouveau cryptosystème à clé publique dont la sécurité repose sur la difficulté de résoudre le problème de la reconstruction de $p$-polynôme.

A Welch-Berlekamp like algorithm for decoding Gabidulin codes. P. Loidreau, in Coding and Cryptography - Revised selected papers of WCC 2005, 2006 LNCS 3969, 36-45. On présente une nouvelle approche permettant de décoder les codes de Gabidulin. De la même manière que le décodage des codes de Reed-Solomon est une instance du problème de reconstruction de polynômes, on montre que le décodage des codes de Gabidulin est une instance du problème de la reconstruction des codes linéaires. Cette similitude conduit à la conception d'un algorithme efficace de décodage inspiré de l'algorithme de Welch-Berlekamp.

How to mask the structure of codes for a cryptographic use. T. P. Berger and P. Loidreau, in Designs, Codes and Cryptography, 35, 63-79, 2005. Dans cet article, nous montrons comment renforcer le cryptosystème à clé publique utilisant des propriétés de codes correcteurs contre les attaques connues tout en réduisant la taille de la clé publique. On utilise des propriétés de sous-codes pour masquer la structure des codes utilisés dans la conception. Nous proposons de nouveaux paramètres pour les cryptosystèmes permettant de réduire significativement les tailles de clés.

Codes derived from binary Goppa codes. P. Loidreau. Problems of Information Transmission, 37(2), 2001. Nous exhibons une nouvelle famille de codes binaires dérivés de la famille des codes de Goppa classiques. On généralise les propriétés des codes de Goppa à cette famille et déduisons des bornes sur la dimension et la distance minimale, ainsi que l'existence d'un algorithme de décodage en temps polynomial jusqu'à une capacité de correction d'erreurs construite.

Weak keys in the McEliece public-key cryptosystem. P. Loidreau, N. Sendrier IEEE Transactions on Information Theory, 47(3), 1207-1211, Mars 2001. Nous montrons comment savoir si le code de Goppa utilisé dans une instance du cryptosystème de McEliece a un polynôme générateur dans un sous-corps du corps du support. De plus, lorsqu'une telle clé existe, on construit une attaque réalisable en pratique.

Comptes rendus de l'académie des sciences

Sur la Reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin. P. Loidreau Comptes Rendus de l'Académie des Sciences : Série I, 339(10):745-750, 2004. Nous présentons un problème de reconstruction de polynômes linéaires ainsi qu'un algorithme en temps polynomial de résolution de ce problème dans un cas simple. Nous en déduisons un algorithme alternatif performant de décodage des codes de Gabidulin.

Rapports de recherche

Manuscrits

Étude et Optimisation de Cryptosystèmes à Clé Publique Fondés sur la Théorie des Codes Correcteurs. P. Loidreau Thèse de doctorat de l'Ecole Polytechnique Cette thèse est consacrée à l'étude de la sécurité de systèmes de chiffrement à clé publique basés sur des propriétés de codes correcteurs d'erreurs, ainsi qu'au développement de nouveaux outils permettant de les renforcer. Tout d'abord nous introduisons les principes fondamentaux des systèmes de chiffrement à clé publique utilisant des codes correcteurs, tel le système de McEliece. Puis, nous introduisons les faiblesses et les forces d'un tel système. Enfin nous montrons que la famille des codes de Goppa originellement introduite pour jouer le rôle d'espace des clés reste la meilleure connue du point de vue de la résistance aux diverses attaques.

Métrique rang et cryptographie. P. Loidreau Document d'Habilitation à Diriger des Recherches Le document se compose de trois parties. La première partie s'attache à établir des propriétés générales de la métrique ainsi que de définir les notions classiques de décodage de codes, et les problèmes auxquels ils sont reliés. Le premier chapitre est consacré à une mise en place de la métrique rang. La seconde partie est consacrée à la présentation de familles de codes optimaux : la famille des codes de Gabidulin, ainsi que les familles de codes qui en dérivent.Dans une troisième partie, on présente les cryptosystèmes à clé publique fondés sur des problèmes difficiles de la métrique rang ainsi que les attaques contres ces systèmes utilisant des codes optimaux en métrique rang.

Actes de conférences

An evolution of GPT cryptosystem. P. Loidreau, in Proceedings of ACCT 2016, Fifteenth International Workshop on Algebraic and Combinatorial Coding Theory, Albena, 2016. The goal of the paper is to show how to design a Gabidulin based public-key cryptosystem resistant to all Overbeck's like attacks. The main idea consists in taking the coefficients of the right scrambler in a subspace of the coefficients field with sufficiently small dimension. This gives a rank multiplier and scrambles the structure of the code. We propose some parameters.

A new constellation for space-time coding. P. Loidreau and G. Robert, in Proceedings of the ninth international workshop on coding and cryptography, WCC 2015, 2015.

On cellular codes and their cryptographic applications. P. Loidreau, in Proceedings of ACCT 2014, Fourteenth International Workshop on Algebraic and Combinatorial Coding Theory, Zvenigorod, 2014. We present a family of codes generalizing the notion of quasi-cyclic codes. Generator matrices are formed with cells which are square matrices from a given commutative matrix algebra generated by a polynomial. We show that any divisor of the polynomial gives rise to a projected code with smaller parameters. By studying how this framework affects quasi-cyclic codes based cryptography, we show that it should be taken into account when designing such cryptosystems.

Rank metric and Gabidulin codes in characteristic 0., D. Augot, G. Robert and P. Loidreau, in Proceedings of IEEE International Symposium on InformationTheory, ISIT 2013.

Asymptotic behaviour of constante rate random codes in rank metric. P. Loidreau, in Proceedings of ACCT 2012, Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory We study the asymptotic behaviour of the minimum rank distance of constant rate random codes and random linear codes. In the case of linear codes, we show that the codes reach GV-bound.

Projected Subcodes of The Second Order Binary Reed-Muller Code. M. Legeay and P. Loidreau, in Proceedings of IEEE International Symposium on InformationTheory, ISIT 2012

Designing a rank metric based McEliece cryptosystem. P. Loidreau, in Post-Quantum Cryptography 2010 LNCS 6061, 142-152. Nous décrivons les cryptosystèmes de type McEliece reposants sur la métrique rang, qui furent introduits par Gabidulin, Paramonov et Tretjakov dans les années 90. Ensuite nous expliquons pourquoi l'attaque d'Overbeck marche si bien contre ces systèmes. Enfin nous montrons quels paramètres choisir pour que la taille de clé reste suffisamment petite, tout en gardant une bonne sécurité contre les attaques par structure et les attaques par décodage.

An algorithme to find linear approximations and its applicationto $8$ rounds of the DES. R. Fourquet, P. Loidreau and C. Tavernier, in Coding and Cryptography - Proceedings of the 6thInternational workshop on Coding and Cryptography, Nous concevons un algorithme qui détermine la liste de toutes les approximations linéaires en deçà d'un certain biais à partir d'une combinaison linéaire donnée de bits de sortie de la fonction de chiffrement. Nous montrons comment appliquer cet algorithmes à 8 tours du DES avec des biais équivalents à ceux obtenus par Matsui. Nous en déduisons une attaques fondées sur des techniques de décodage.

Designing an Efficient and Secure Public-Key Cryptosystem Based on Reducible Rank Codes. T. P. Berger and P. Loidreau, in Proceedings of INDOCRYPT 2004, LNCS 2656, 360-373, Springer, Berlin, 2003. Nous modifions le cryptosystèmes à clé publique utilisant la famille des codes rangs réductibles qui fut présenté par Ourivski, Gabidulin, Ammar et Honary en 2003. Le système proposé a un meilleur taux de transmission et est plus sûr que le système original. En effet on montre qu'il est résistant aux attaques dites par réaction et par renvoi de message.

Strengthening McEliece Cryptosystem. P. Loidreau, in Advances in Cryptology - ASIACRYPT 2000 LNCS 1976, 585--598, Décembre 2000. Le cryptosystème de McEliece constitue l'une des alternatives aux cryptosystèmes reposant sur des problématiques de théorie des nombres. Nous en présentons une modification qui renforce sa sécurité sans augmenter la taille de la clé publique. Nous montrons qu'il est possible d'utiliser des propriétés du groupe d'autormorphisme des codes pour construire des motifs d'erreurs décodabes et de grand poids.

On subcodes of codes in rank metric, E. M. Gabidulin and P. Loidreau, in ISIT 2005, Adelaide,

Security of the Niederreiter version of the GPT public-key cryptosystem. T. Berger and P. Loidreau, in ISIT 2002, Lausanne,

Large weight patterns decoding in Goppa codes and applicationsto cryptography. P. Loidreau, in ISIT 2000, Sorrento, En faisant agir le groupe de Galois sur le support, on peut corriger des erreurs de poids supérieur à la capacité de correction théorique des codes de Goppa binaires dont le polynôme générateur est à coefficients dans le corps stable du groupe de Galois.

Some weak keys in McEliece Public Key cryptosystem. P. Loidreau and N. Sendrier, in ISIT 98, MIT, Cambridge, Nous montrons que la famille des codes de Goppa binaires dont le polynôme générateur est pris à coefficient dans un sous-corps du corps constituant le support forment une famille de clés faibles pour le cryptosystème de McEliece.

Vous êtes ici :   Accueil   >>   Publications