Search

Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed–Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed–Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code., Les code en métrique rang attirent l’attention depuis quelques années en raison de leur application possible au codage réseau linéaire aléatoire (random linear network coding), à la cryptographie à clé publique, au codage espace-temps et aux systèmes de stockage distribué. Une construction de codes algébriques en métrique rang de cardinalité optimale a été introduite par Delsarte, Gabidulin et Roth il y a quelques décennies. Ces codes sont considérés comme l’équivalent des codes de Reed – Solomon et ils sont basés sur l’évaluation de polynômes linéarisés. Ils sont maintenant appelés les codes de Gabidulin. Cette thèse traite des codes en bloc et des codes convolutifs en métrique rang avec l’objectif de développer et d’étudier des algorithmes de décodage efficaces pour ces deux classes de codes. Après une introduction dans le chapitre 1, le chapitre 2 fournit une introduction rapide aux codes en métrique rang et leurs propriétés. Dans le chapitre 3, on considère des approches efficaces pour décoder les codes de Gabidulin. Lapremière partie de ce chapitre traite des algorithmes rapides pour les opérations sur les polynômes linéarisés. La deuxième partie de ce chapitre résume tout d’abord les techniques connues pour le décodage jusqu’à la moitié de la distance rang minimale (bounded minimum distance decoding) des codes de Gabidulin, qui sont basées sur les syndromes et sur la résolution d’une équation clé. Ensuite, nous présentons et nous prouvons un nouvel algorithme efficace pour le décodage jusqu’à la moitié de la distance minimale des codes de Gabidulin. Le chapitre 4 est consacré aux codes de Gabidulin entrelacés et à leur décodage au-delà de la moitié de la distance rang minimale. Dans ce chapitre, nous décrivons d’abord les deux approches connues pour le décodage unique et nous tirons une relation entre eux et leurs probabilités de défaillance. Ensuite, nous présentons un nouvel algorithme de décodage des codes de Gabidulin entrelacés basé sur l’interpolation des polynômes linéarisés. Nous prouvons la justesse de ses deux étapes principales — l’interpolation et la recherche des racines — et montrons que chacune d’elles peut être effectuée en résolvant un système d’équations linéaires. Jusqu’à présent, aucun algorithme de décodage en liste en temps polynomial pour les codes de Gabidulin n’est connu et en fait il n’est même pas clair que cela soit possible. Cela nous a motivé à étudier, dans le chapitre 5, les possibilités du décodage en liste en temps polynomial des codes en métrique rang. Cette analyse est effectuée par le calcul de bornes sur la taille de la liste des codes en métriques rang en général et des codes de Gabidulin en particulier. Étonnamment, les trois nouvelles bornes révèlent toutes un comportement des codes en métrique rang qui est complètement différent de celui des codes en métrique de Hamming. Enfin, dans le chapitre 6, on introduit des codes convolutifs en métrique rang. Ce qui nous motive à considérer ces codes est le codage réseau linéaire aléatoire multi-shot, où le réseau inconnu varie avec le temps et est utilisé plusieurs fois. Les codes convolutifs créent des dépendances entre les utilisations différentes du réseau aun de se adapter aux canaux difficiles. Basé sur des codes en bloc en métrique rang (en particulier les codes de Gabidulin), nous donnons deux constructions explicites des codes convolutifs en métrique rang. Les codes en bloc sous-jacents nous permettent de développer un algorithme de décodage des erreurs et des effacements efficace pour la deuxième construction, qui garantit de corriger toutes les séquences d’erreurs de poids rang jusqu’à la moitié de la distance rang active des lignes. Un résumé et un aperçu des problèmes futurs de recherche sont donnés à la fin de chaque chapitre. Finalement, le chapitre 7 conclut cette thèse.

An open question about Gabidulin codes is whether polynomial-time list decoding beyond half the minimum distance is possible or not. In this contribution, we give a lower and an upper bound on the list size, i.e., the number of codewords in a ball around the received word. The lower bound shows that if the radius of this ball is greater than the Johnson radius, this list size can be exponential and hence, no polynomial-time list decoding is possible. The upper bound on the list size uses subspace properties., Comment: Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2012), Pomorie : Bulgaria (2012)

International audience; The Schmidt–Sidorenko–Bossert scheme extends a low-rate Reed–Solomon code to an Interleaved Reed–Solomon code and achieves the decoding radius of Sudan’s original list decoding algorithm while the decoding result remains unambiguous. We adapt this result to the case of Generalized Reed–Solomon codes and calculate the parameters of the corresponding Interleaved Generalized Reed–Solomon code. Furthermore, the failure probability is derived.

In this paper, list decoding of crisscross errors in arrays over finite fields is considered. For this purpose, the so-called cover metric is used, where the cover of a matrix is a set of rows and columns which contains all non-zero elements of the matrix. A Johnson-like upper bound on the maximum list size in the cover metric is derived, showing that the list of codewords has polynomial size up to a certain radius. Furthermore, a simple list decoding algorithm for a known optimal code construction is presented, which decodes errors in the cover metric up to our upper bound. These results reveal significant differences between the cover metric and the rank metric and show that the cover metric is more suitable for correcting crisscross errors.

Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed-Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. The unique decoding algorithm recovers most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed-Solomon codes and block codes in Hamming metric, respectively. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes.

This dissertation treats information- and coding-theoretic aspects of modern data storage systems. We propose and analyze models that abstract different aspects of such memories with a particular focus on reliability and efficiency. The first two parts discuss the communication over channels with many parallel and unordered data sequences that are additionally perturbed by errors. In the third part, we analyze cost constrained systems for efficient DNA synthesis. Diese Dissertation befasst sich mit informations- und kodierungstheoretischen Aspekten moderner digitaler Datenträger. Wir entwerfen und analysieren Modelle, welche verschiedene Aspekte dieser Speicher beleuchten, mit einem besonderen Augenmerk auf Zuverlässigkeit und Effizienz. In den ersten zwei Teilen beschäftigen wir uns mit der Kommunikation über Kanäle mit vielen parallelen und ungeordneten Datensträngen, welche durch Fehler korrumpiert werden können. In dem dritten Teil analysieren wir kostbeschränkte Systeme für effiziente DNA Synthese.

This thesis studies code-based cryptography. First, three problems related to code-based cryptography are investigated and algorithms to solve them are presented. Then, attacks on the Twisted Reed-Solomon based McEliece scheme and on an implementation of the Hamming Quasi-Cyclic are developed. Last, the new scheme, LIGA, is proposed. It is based on the hardness of list decoding and interleaved decoding of Gabidulin codes; it features short ciphertext and key sizes, and no decryption failures. Diese Arbeit behandelt codebasierte Kryptographie. Zuerst werden drei diesbezügliche Probleme untersucht und Algorithmen zum Lösen dieser Probleme vorgestellt. Danach werden Angriffe auf das Twisted Reed-Solomon basierte McEliece System und auf eine Implementierung von Hamming Quasi-Cyclic entwickelt. Zuletzt wird das neue System LIGA vorgestellt. Es basiert auf Listen- und Verschränkungsdecodierung von Gabidulin Codes und zeichnet sich durch kurze Geheimtexte und Schlüsselgrößen aus.

This work investigates different concepts related distributed storage, starting from codes with locality properties, such as maximally recoverable codes for grid-like topologies, regenerating partial MDS codes, and lifted affine-invariant codes. Then, the application of interleaving, a powerful method for increasing the error decoding radius, to the class of alternant codes is analyzed. Finally, new bounds on the rate of private information retrieval in the coded storage setting are derived. Diese Arbeit untersucht verschiedene Aspekte verteilter Datenspeicherung, angefangen mit lokal korrigierbaren Codes mit Gitterstruktur, Regeneration oder affiner Invarianz. Danach folgt eine Analyse der Anwendung von Codeverschränkung, einer mächtigen Methode zur Vergrößerung des Dekodierradius, auf die durch Teilkörper definierten Unterräume von Reed-Solomon Codes. Letztendlich werden neue Schranken an die Rate von privater Datenabfrage aus kodierten Speichersystemen hergeleitet.

In this work, secret-key generation based on a three-party compound source is studied where the communication rate between legitimate users is limited. A robust secret-key generation protocol is introduced which guarantees security and reliability for all elements of the compound set. In this case, the secret-key capacity is derived as a function of the communication rate upper-bound while the size of the uncertainty set is arbitrary (possibly infinite) and the set of marginals is finite. In dieser Arbeit wird die Secret-Key Erzeugung mittels einer dreifachen Compoundquelle untersucht, wobei die Kommunikationsrate zwischen den legitimen Benutzern begrenzt ist. Es wird ein Protokoll zur robusten Secret-Key Erzeugung eingeführt, das Sicherheit und Zuverlässigkeit für alle Elemente der Compoundmenge garantiert. In diesem Fall wird die Secret-Key Kapazität als Funktion der oberen Schranke der Kommunikationsrate hergeleitet, wobei die Größe der Unsicherheitsmenge beliebig (möglicherweise unendlich) und die Menge der Randverteilungen endlich ist.