Decoding algorithms of algebraic codes and cryptography
Décodage des codes algébriques et cryptographie
Résumé
I discuss the decoding problem of two important families of algebraic
codes: binary cyclic codes and $q$-ary Reed-Solomon codes (and also
algebraic geometry codes). Concerning cyclic codes, they do not have a
generic decoding algorithm, except for the case of the BCH codes and
related codes (Hartmann-Tzeng, Roos bound). Among these codes are the
quadratic residue codes, for which there is no generic decoding
algorithm, but which have good parameters. I present and study a
system of equations related the syndrom decoding of cyclic codes.
These equations can be solved by Gröbner tools. We thus obtain
decoding algorithms with good complexity for these codes. This work
was a part of the PHD thesis of Magali Bardet.
Regarding Reed-Solomon codes, they can be seen as {\em evaluation
codes}, and the associated decoding problem amounts to finding
approximations of a function by low degree polynomials. A major
progress has been achieved by Guruswami and Sudan, who have produced
an algorithm which can decode much more errors than classical ones, by
relaxing the hypothesis that the solution be unique. I have found
improvements of this algorithm, which speed it, and make it
deterministic (notably by removing a fectorization over finite
fields), either in the Reed-Solomon case, or in the algebraic geometry
case. This achievements were made when I directed Lancelot Pecquet PHD
thesis.
From the theoretical point of view, I have studied mutlivariate
generalizations, which correspond either to products of Reed-Solomon
codes, or to Reed-Muller codes. I then obtain a good decoding radius,
for codes with small rate. In the case of Reed-Muller codes over the
binary field, Cédric Tavernier, in his PHD thesis under my direction,
has found and implemented an efficient algorithm, more than the
algorithms based on the Guruswami-Sudan method.
I have also studied the negative aspects of syndrom decoding of
general linear codes, and of the the decoding of Reed-Solomon codes,
when the number of errors is high, aiming at applications in
cryptography. In the first case, I have built a cryptographic hash
function with a security reduction, that is to say, to find an attack
on the hash function is equivalent to solve a difficult coding
problem. I have also built a new primitive for public key encryption,
relying on the difficulty of decoding Reed-Solomon codes.
In a more applied domain, I have proposed, with Raghav Bhaskar, a new
protocol for multiusers group key agreement, founded on the discrete
logarithm problem. Raghav Bhaskar has given a security proof of this
protocol, in his PHD thesis under my direction. We have also discussed
how to adapt the protocol to messages losses, since our protocol is
among the few which can resist such losses.
codes: binary cyclic codes and $q$-ary Reed-Solomon codes (and also
algebraic geometry codes). Concerning cyclic codes, they do not have a
generic decoding algorithm, except for the case of the BCH codes and
related codes (Hartmann-Tzeng, Roos bound). Among these codes are the
quadratic residue codes, for which there is no generic decoding
algorithm, but which have good parameters. I present and study a
system of equations related the syndrom decoding of cyclic codes.
These equations can be solved by Gröbner tools. We thus obtain
decoding algorithms with good complexity for these codes. This work
was a part of the PHD thesis of Magali Bardet.
Regarding Reed-Solomon codes, they can be seen as {\em evaluation
codes}, and the associated decoding problem amounts to finding
approximations of a function by low degree polynomials. A major
progress has been achieved by Guruswami and Sudan, who have produced
an algorithm which can decode much more errors than classical ones, by
relaxing the hypothesis that the solution be unique. I have found
improvements of this algorithm, which speed it, and make it
deterministic (notably by removing a fectorization over finite
fields), either in the Reed-Solomon case, or in the algebraic geometry
case. This achievements were made when I directed Lancelot Pecquet PHD
thesis.
From the theoretical point of view, I have studied mutlivariate
generalizations, which correspond either to products of Reed-Solomon
codes, or to Reed-Muller codes. I then obtain a good decoding radius,
for codes with small rate. In the case of Reed-Muller codes over the
binary field, Cédric Tavernier, in his PHD thesis under my direction,
has found and implemented an efficient algorithm, more than the
algorithms based on the Guruswami-Sudan method.
I have also studied the negative aspects of syndrom decoding of
general linear codes, and of the the decoding of Reed-Solomon codes,
when the number of errors is high, aiming at applications in
cryptography. In the first case, I have built a cryptographic hash
function with a security reduction, that is to say, to find an attack
on the hash function is equivalent to solve a difficult coding
problem. I have also built a new primitive for public key encryption,
relying on the difficulty of decoding Reed-Solomon codes.
In a more applied domain, I have proposed, with Raghav Bhaskar, a new
protocol for multiusers group key agreement, founded on the discrete
logarithm problem. Raghav Bhaskar has given a security proof of this
protocol, in his PHD thesis under my direction. We have also discussed
how to adapt the protocol to messages losses, since our protocol is
among the few which can resist such losses.
Je traite du décodage de deux grandes familles de codes algébriques :
les codes cycliques binaires et les codes de Reed-Solomon sur un
alphabet $q$-aire (ainsi que les codes géométriques). En ce qui
concerne les codes cycliques, ceux-ci n'ont pas d'algorithme générique
de décodage, mis à part les codes BCH ou assimilés (bornes de
Hartman-Tzeng, de Roos). Au premier rang des codes intéressants pour
lesquels on ne connaît pas d'algorithme de décodage {\em générique}
figurent les {\em codes à résidus quadratiques}, qui ont de bons
paramètres. J'étudie une mise en équation du problème du décodage par
syndrôme de ces codes, que l'on peut résoudre avec des outils de base
de Gröbner. On obtient ainsi des algorithmes de décodage de complexité
raisonnable pour ces codes. Ces travaux ont fait l'objet d'une partie
de la thèse de Magali Bardet.
En ce qui concerne les codes de Reed-Solomon, ceux-ci peuvent être vus
comme des {\em codes d'évaluation}, et le problème de décodage associé
revient à approcher une fonction par des polynômes de base degré. De
grands progrès ont été réalisés par Guruswami et Sudan, qui ont trouvé
un algorithme qui décode bien au delà des rayons classiques de
décodage, en relaxant l'hypothèse que la solution doit être unique. Je
propose d'améliorer certaines étapes de cet algorithme, en le rendant
plus rapide et déterministe (notamment en évitant une factorisation de
polynôme sur un corps fini), dans le cas des codes Reed-Solomon, et
dans le cas des codes géométriques. Ces travaux ont été effectués en
encadrant Lancelot Pecquet.
Du point de vue théorique, j'ai étudié des généralisations
multivariées, qui correspondent à certains codes: les codes produits
de Reed-Solomon, et les codes de Reed-Muller. On obtient ainsi un bon
rayon de décodage, dans le cas des codes de petit taux. Dans le cas de
codes de Reed-Muller sur l'alphabet binaire, Cédric Tavernier, dans sa
thèse sous ma direction, a produit et implanté un algorithme efficace,
plus que ceux basés sur l'algorithme de Guruswami-Sudan.
J'ai étudié les aspects négatifs du problème de décodage par syndrôme
des codes linéaires, et du décodage des codes de Reed-Solomon, quand
le nombre d'erreurs est élevé, en but d'application en cryptographie.
Dans le premier cas, j'ai construit une fonction de hachage
cryptographique à réduction de sécurité, c'est-à-dire que trouver une
faiblesse dans le fonction de hachage revient à résoudre un problème
réputé difficile de codage. J'ai aussi construit une nouvelle
primitive de chiffrement à clé publique, reposant sur la difficulté de
décoder les codes de Reed-Solomon.
Dans un domaine plus appliqué, j'ai proposé avec Raghav Bhaskar un
nouvel algorithme d'échange de clé multi-utilisateurs, fondé sur le
problème du logarithme discret. Raghav Bhaskar a fourni une preuve de
sécurité de ce protocole, pendant sa thèse sous ma direction. Nous
avons aussi étudié comment adapter ce protocole aux pertes de
messages, car notre protocole est un des seuls qui est robuste à ces
pertes.
les codes cycliques binaires et les codes de Reed-Solomon sur un
alphabet $q$-aire (ainsi que les codes géométriques). En ce qui
concerne les codes cycliques, ceux-ci n'ont pas d'algorithme générique
de décodage, mis à part les codes BCH ou assimilés (bornes de
Hartman-Tzeng, de Roos). Au premier rang des codes intéressants pour
lesquels on ne connaît pas d'algorithme de décodage {\em générique}
figurent les {\em codes à résidus quadratiques}, qui ont de bons
paramètres. J'étudie une mise en équation du problème du décodage par
syndrôme de ces codes, que l'on peut résoudre avec des outils de base
de Gröbner. On obtient ainsi des algorithmes de décodage de complexité
raisonnable pour ces codes. Ces travaux ont fait l'objet d'une partie
de la thèse de Magali Bardet.
En ce qui concerne les codes de Reed-Solomon, ceux-ci peuvent être vus
comme des {\em codes d'évaluation}, et le problème de décodage associé
revient à approcher une fonction par des polynômes de base degré. De
grands progrès ont été réalisés par Guruswami et Sudan, qui ont trouvé
un algorithme qui décode bien au delà des rayons classiques de
décodage, en relaxant l'hypothèse que la solution doit être unique. Je
propose d'améliorer certaines étapes de cet algorithme, en le rendant
plus rapide et déterministe (notamment en évitant une factorisation de
polynôme sur un corps fini), dans le cas des codes Reed-Solomon, et
dans le cas des codes géométriques. Ces travaux ont été effectués en
encadrant Lancelot Pecquet.
Du point de vue théorique, j'ai étudié des généralisations
multivariées, qui correspondent à certains codes: les codes produits
de Reed-Solomon, et les codes de Reed-Muller. On obtient ainsi un bon
rayon de décodage, dans le cas des codes de petit taux. Dans le cas de
codes de Reed-Muller sur l'alphabet binaire, Cédric Tavernier, dans sa
thèse sous ma direction, a produit et implanté un algorithme efficace,
plus que ceux basés sur l'algorithme de Guruswami-Sudan.
J'ai étudié les aspects négatifs du problème de décodage par syndrôme
des codes linéaires, et du décodage des codes de Reed-Solomon, quand
le nombre d'erreurs est élevé, en but d'application en cryptographie.
Dans le premier cas, j'ai construit une fonction de hachage
cryptographique à réduction de sécurité, c'est-à-dire que trouver une
faiblesse dans le fonction de hachage revient à résoudre un problème
réputé difficile de codage. J'ai aussi construit une nouvelle
primitive de chiffrement à clé publique, reposant sur la difficulté de
décoder les codes de Reed-Solomon.
Dans un domaine plus appliqué, j'ai proposé avec Raghav Bhaskar un
nouvel algorithme d'échange de clé multi-utilisateurs, fondé sur le
problème du logarithme discret. Raghav Bhaskar a fourni une preuve de
sécurité de ce protocole, pendant sa thèse sous ma direction. Nous
avons aussi étudié comment adapter ce protocole aux pertes de
messages, car notre protocole est un des seuls qui est robuste à ces
pertes.