Résultat de la recherche
Properties and constructions of codes with the rank and the subspace metric
En 2000, Ahlswede, Cai, Li et Yeung ont découvert que l'utilisation de techniques de codage dans la transmission des données aux niveau des nœuds intermédiaires d'un réseau peut significativement augmenter le débit d'information transmis. Ces résultats sont à l'origine d'une nouvelle branche de recherche, appelée Network coding, qui s'occupe de l'efficacité et de la fiabilité des communications sur les réseaux.
La théorie des codes pour les réseaux a commencé à attirer l'attention de la communauté mathématique lorsqu'en 2008 Kötter et Kschischang ont proposé un setup mathématique rigoureux pour la correction des erreurs et des effacements sur les réseaux. Leur approche est basée sur deux classes de codes correcteurs, appelées rank-metric codes et subspace codes.
Dans cette thèse, nous nous concentrons principalement sur des problèmes mathématiques motivés par des applications en network coding. Plus précisément, on étudie des propriétés structurelles et des constructions de rank-metric codes et de subspace codes.
Dans la première partie de la thèse, nous étudions différentes constructions de subspace codes. Nous commençons avec une famille de codes, que nous appelons partial spread codes, qui ont une capacité de correction maximale et cardinalité asymptotiquement optimale. Nous montrons que les partial spread codes existent pour tous les paramètres, sont maximales par rapport à l'inclusion et qui peuvent être décodés efficacement.
Ensuite, nous nous concentrons sur les equidistant codes, une classe de subspace codes où deux éléments du code sont à égale distance l'un de l'autre. Nous fournissons une classification presque complète de tels codes, et montrons en particulier que les equidistant codes optimaux ont une structure très simple. Puis, nous montrons comment construire des equidistant codes de cardinalité asymptotiquement optimale et comment les décoder de manière efficace.
Enfin, nous nous concentrons sur une technique spécifique qui produit des subspace codes de grande cardinalité (la multilevel construction) et y étudions une conjecture énoncée par T. Etzion et N. Siberstein concernant les matrices sur les corps finis avec un profil donné et dont le rang est borné par une constante. Nous prouvons la conjecture dans les cas les plus importants du point de vue du network coding et utilisons nos résultats pour construire de nouveaux subspace codes avec la plus grande cardinalité connue pour leurs paramètres. Nous étudions également la conjecture de Etzion-Silberstein sur les corps algébriquement fermés et montrons que dans ce cas elle est fausse. Pour cela, nous utilisons des méthodes de géométrie algébrique.
La deuxième partie de la thèse est dédiée aux propriétés structurelles des rank-metric codes. Nous comparons les deux théories de la dualité des codes de Delsarte et de Gabidulin et montrons que la première généralise la seconde. Ensuite, nous donnons une preuve simple des identités de MacWilliams pour la famille générale des codes de Delsarte. Ces identités ont été montrées par Delsarte en utilisant des méthodes sophistiquées de combinatoire.
Nous montrons également que les propriétés les plus importantes des rank-metric codes peuvent être vues comme de simples conséquences de ces identités. Dans la deuxième partie du chapitre, nous étudions les anticodes optimaux pour la métrique du rang, et obtenons de nouvelles bornes pour les paramètres des rank-metric codes. Nous décrivons également les codes qui atteignent ces bornes. Comme application de nos résultats, nous répondons à des questions de combinatoire concernant les matrices sur les corps finis.
Ensuite, nous définissons et étudions des invariants algébriques pour les rank-metric codes (que nous appelons Delsarte generalized weights) qui généralisent des invariants connus définis pour la sous-classe spéciale des codes de Gabidulin. Nous montrons que nos invariants décrivent les codes et anticodes optimaux et étudions leur comportement par rapport à la théorie de la dualité des rank-metric codes. Plus précisément, nous montrons que les Delsarte generalized weights d'un code et les Delsarte generalized weights de son code dual se déterminent les uns les autres via une relation précise que nous décrivons explicitement.
Finalement nous examinons dans le dernier chapitre certains liens entre la théorie des codes sur les groupes abéliens finis et la théorie combinatoire des ensembles partiellement ordonnés. Nous généralisons des résultats pour les codes classiques et les rank-metric codes établies par d'autres auteurs. Plus précisément, nous définissons une famille générale des fonctions poids sur les groupes abéliens finis qui donnent des identités de MacWilliams inversibles pour les codes additifs. Nous étudions ces fonctions poids en utilisant des méthodes de la théorie des treillis. Cela nous permettra également de fournir une méthodologie efficace pour obtenir les identités de MacWilliams pour les codes sur les groupes.
Tout au long de la thèse, l'accent est mis sur les aspects mathématiques des différents problèmes traités., In 2000 Ahlswede, Cai, Li, and Yeung discovered that employing coding techniques in network transmissions at the intermediate nodes of the network may give substantial gains in information throughput. These results originated a new research field, called network coding, concerned with efficiency and reliability of communications over networks. Network coding started to draw the attention of the mathematical community in 2008, when Kötter and Kschischang proposed a rigorous mathematical setup for errors and erasures correction over networks. Their approach is based on rank-metric and subspace codes, mathematical objects that guarantee the reliability of a network communication.
In this dissertation we concentrate on mathematical problems motivated by network coding applications, studying structural properties and constructions of rank-metric and subspace codes.
In the first part of the dissertation we investigate constructions of subspace codes. We start presenting a family of codes, which we call partial spread codes, that have maximum correction capability and asymptotically optimal cardinality. We show that partial spread codes exist for all parameters, that are maximal with respect to containment, and that can be efficiently decoded.
Then we concentrate on equidistant codes, i.e., codes where every two codewords are at the same distance. We provide an almost complete classification of such codes, proving in particular that the optimal ones have a very simple structure. Then we show how to construct equidistant codes of asymptotically optimal cardinality, and how to decode them efficiently.
Finally, we focus on a specific technique that produces subspace codes of large cardinality (the so-called multilevel construction) and study a related mathematical conjecture by T. Etzion and N. Silberstein concerning matrices over finite fields with given shape and rank bounded from below. We establish the conjecture in the cases that are most relevant from the point of view of network coding, and use our results to produce new examples of subspace codes with the largest known cardinality for their parameters. We also investigate the Etzion-Silberstein conjecture over algebraically closed fields, and disprove it in this case using methods from algebraic geometry.
The second part of the dissertation is devoted to structural properties of rank-metric codes. We start comparing the duality theories of Delsarte and Gabidulin rank-metric codes, proving that the former generalizes the latter. Then we give a simple proof for the MacWilliams identities for the general family of Delsarte codes, originally established by Delsarte using sophisticated methods from combinatorics. We also show that the most important properties of rank-metric codes can be regarded as simple consequences of such identities. In a second part of the chapter we study optimal anticodes in the rank-metric, and prove some new bounds on the parameters of rank-metric codes, characterizing those attaining them. As an application of our results, we answer some questions concerning matrices over finite fields.
Then we introduce and study algebraic invariants for rank-metric codes (which we call generalized Delsarte weights), that extend known invariants defined on the special sub-class of Gabidulin rank-metric codes. We show that our invariants characterize optimal codes and anticodes, and that behave well with respect to the duality theory of rank-metric codes. More precisely, we prove that 5 the generalized Delsarte weights of a code and the generalized Delsarte weights of its dual code determine each other via a precise relation, which we explicitly derive.
Finally, in the last chapter we investigate some connections between the theory of codes over finite abelian groups and the combinatorial theory of finite posets and lattices, extending in particular some results for classical and rank-metric codes established by other authors to a more general framework. More precisely, we introduce a general family of weight functions on finite abelian groups that give rise to invertible MacWilliams identities for additive codes, and study such weight functions employing lattice theory methods. This will also allow us to provide a computationally effective viewpoint on the theory of MacWilliams identities for codes over groups.
Throughout the whole dissertation the main emphasis is on the mathematical aspects of the problems under study.
Point compression for the trace zero subgroup over a small degree extension field
Trace-zero subgroups of elliptic and twisted Edwards curves: a study for cryptographic applications
En 1999, Frey a proposé, pour la première fois, les sous-groupes de trace nulle des courbes elliptiques pour les applications à la cryptographie: il les a désignés comme une alternative valide, dans ce secteur, aux groupes classiques des points des courbes elliptiques. Considérons une courbe elliptique $E$ définie sur un corps fini $\mathbb{F}_q$, avec l'addition standard entre ses points. Etant donnée une extension de corps $\mathbb{F}_{q} \subseteq \mathbb{F}_{q^n}$ de degré $n$ premier et impair, le sous groupe de trace nulle de la courbe elliptique $E$, de degré $n$, est un sous-groupe du groupe des points de $E$ avec coordonnées dans $\mathbb{F}_{q^n}$.
En 2007, les courbes d'Edwards ont été introduites par Edwards, et elles ont été proposées pour les applications cryptographiques par Bernstein et Lange. Après, elles ont été généralisées aux courbes d'Edwards tordues. Les courbes d'Edwards tordues peuvent être considérées comme des courbes elliptiques speciales, décrites sous une nouvelle forme. Elles ont des advantages cryptographiques sur les courbes elliptiques dans la forme usuelle de Weierstrass. Les sous-groupes de trace nulle des courbes d'Edwards tordues sont definies de la même manière que les sous-groupes de trace nulle des courbes elliptiques.
Dans cette thèse, nous étudions les sous-groupes de trace nulle des courbes elliptiques et des courbes d'Edwards tordues, du point de vue de leur application potentielle à la cryptographie. En particulier, nous nous concentrons sur trois aspects distincts pour les sous-groupes de trace nulle: l'utilisation de représentations optimales des éléments du groupe, la construction d'algorithmes pour le produit scalaire, et l'étude de possibles attaques cryptographiques basés sur le problème du logarithme discret. Tous ces aspects sont tres importants pour l'efficacité et la sécurité d'un cryptosystème construit sur le groupe considéré.
A propos de représentations optimales de groupes, nous proposons deux représentations optimales pour les sous-groupes de trace nulle des courbes d'Edwards tordues. Nous donnons des algorithmes efficaces pour l'utilisation de nos représentations, et nous faisons des comparaisons avec les représentations analogues pour les sous-groupes de trace nulle des curbes elliptiques.
En ce qui concerne l'arithmétique efficace dans les sous-groupes de trace nulle, notre contribution consiste en un algorithme pour effectuer le produit scalaire dans les sous-groupes de trace nulle de degré trois. Cet algorithme suit une approche originale et il utilise des coordonnées optimales pour représenter les éléments du groupe.
Enfin, nous nous concentrons sur la sécurité des sous-groupes de trace nulle contre les attaques cryptographiques. Nous présentons une nouvelle variante de l'algorithme d'index calculus pour le problème du logarithme discret dans ces sous-groupes. Nous comparons la complexité de la résolution des systèmes polynômiaux obtenus avec notre méthode à celle de la résolution des systèmes construits avec l'unique autre spécialisation d'index calculus aux sous-groupes de trace nulle. Nous montrons que nos systèmes sont plus faciles à résoudre, dans les cas de sous-groupes de trace nulle de degré petit, qui sont les cas importantes pour les applications cryptographiques.
Dans l'algorithme pour le produit scalaire dans les sous-groupes de trace nulle de degré trois, et dans notre nouvelle méthode d'index calculus, nous utilisons les polynômes de sommation généralisés de courbes elliptiques. Ces polynômes sont présentés dans cette thèse pour la première fois, et ils peuvent être vus comme une généralisation originale des polynômes de sommation de courbes elliptiques de Semaev. Les polynômes de sommation généralisés permettent de trouver des relations entre points sur la courbe elliptique. Grâce à leur propriété géométrique, ils peuvent avoir des applications pertinentes en cryptographie., In 1999, Frey first suggested trace-zero subgroups of elliptic curves for applications to cryptography, as a valid alternative to the use of classical groups of points of elliptic curves in this sector. Take an elliptic curve $E$ defined over a finite field $\mathbb{F}_q$, with the standard addition between points. Given a field extension $\mathbb{F}_q\subseteq \mathbb{F}_{q^n}$ of odd prime degree $n$, the trace-zero subgroup of the elliptic curve $E$ of degree $n$ is a subgroup of the group of points of $E$ with coordinates in $\mathbb{F}_{q^n}$.
In 2007, Edwards curves were introduced by Edwards, and proposed for cryptographic applications by Bernstein and Lange. Right afterwards, they were generalized to twisted Edwards curves. Twisted Edwards curves can be seen as special elliptic curves, written in a new form. They have some cryptographic advantages over elliptic curves in the usual Weierstrass form. Trace-zero subgroups of twisted Edwards curves are defined in the same way as trace-zero subgroups of elliptic curves.
In this thesis, we study trace-zero subgroups of elliptic and twisted Edwards curves, from the point of view of their potential application to cryptography. In particular, we focus on three distinct aspects for trace-zero subgroups: the use of optimal representations for group elements, the construction of fast algorithms for scalar multiplication, and the study of possible cryptographic attacks based on the discrete logarithm problem. All these aspects are of great relevance for the efficiency and the security of a cryptosystem built on the given group.
Concerning optimal representations for group elements, we propose two optimal representations for trace-zero subgroups of twisted Edwards curves. We give efficient algorithms to deal with them, and we make comparisons with analogous representations for trace-zero subgroups of elliptic curves.
Concerning efficient arithmetic in trace-zero subgroups, our contribution consists of an algorithm to perform scalar multiplication in the trace-zero subgroup of degree three. This algorithm follows an original approach and makes use of optimal coordinates to represent the elements of the group.
Finally, we focus on the study of security of trace-zero subgroups against cryptographic attacks. We propose a new variant of the index calculus algorithm for the discrete logarithm problem in these subgroups. We compare the complexity of solving the polynomial systems obtained with our method with that of solving the systems computed with the only other specialization of the index calculus to trace-zero subgroups. We show that our systems are easier to solve in the case of trace-zero subgroups of small degree, that is the important case for cryptographic applications.
In both the algorithm for scalar multiplication in trace-zero subgroups of degree three, and in our new index calculus method for trace-zero subgroups, we make use of generalized summation polynomials of elliptic curves. Such polynomials are introduced in this thesis for the first time, and they can be seen as an original generalization of Semaev's summation polynomials of elliptic curves. Generalized summation polynomials allow to find relations between points on the elliptic curve. Thanks to their geometric property, they can have relevant applications to cryptography.