This research is concerned with the reliable delivery of scalable compressed data over lossy communication channels. Recent works proposed several strategies for assigning optimal code redundancies to elements of scalable data, which form a linear structure of dependency, under the assumption that all source elements are encoded onto a common group of network packets. Given large data and small network packets, such schemes require very long channel codes with high computational complexity. In networks with high loss, small packets are more desirable than long packets. The first contribution of this thesis is to propose a strategy for optimally assigning elements of the scalable data to clusters of packets, subject to constraints on packet size and code complexity. Given a packet cluster arrangement, the scheme then assigns optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results show that the proposed strategy can outperform the previous code assignment schemes subject to the above-mentioned constraints, particularly at high channel loss rates. Secondly, we modify these schemes to accommodate complex structures of dependency. Source elements are allocated to clusters of packets according to their dependency structure, subject to constraints on packet size and channel codeword length. Given a packet cluster arrangement, the proposed schemes assign optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results demonstrate the superiority of the proposed strategies for correctly modelling the dependency structure. The last contribution of this thesis is to propose a scheme for optimizing protection of scalable data where limited retransmission is possible. Previous work assumed that retransmission is not possible. For most real-time or interactive applications, however, retransmission of lost data may be possible up to some limit. In the present work we restrict our attention to streaming sources (e.g., video) where each source element can be transmitted in one or both of two time slots. An optimization algorithm determines the transmission and level of protection for each source element, using information about the success of earlier transmissions. Experimental results confirm the benefit of limited retransmission.

This dissertation considers several coding techniques based on Reed-Solomon (RS) and low-density parity-check (LDPC) codes. These two prominent families of error-correcting codes have attracted a great amount of interest from both theorists and practitioners and have been applied in many communication scenarios. In particular, data storage systems have greatly benefited from these codes in improving the reliability of the storage media. The first part of this dissertation presents a unified framework based on rate-distortion (RD) theory to analyze and optimize multiple decoding trials of RS codes. Finding the best set of candidate decoding patterns is shown to be equivalent to a covering problem which can be solved asymptotically by RD theory. The proposed approach helps understand the asymptotic performance-versus-complexity trade-off of these multiple-attempt decoding algorithms and can be applied to a wide range of decoders and error models. In the second part, we consider spatially-coupled (SC) codes, or terminated LDPC convolutional codes, over intersymbol-interference (ISI) channels under joint iterative decoding. We empirically observe the phenomenon of threshold saturation whereby the belief-propagation (BP) threshold of the SC ensemble is improved to the maximum a posteriori (MAP) threshold of the underlying ensemble. More specifically, we derive a generalized extrinsic information transfer (GEXIT) curve for the joint decoder that naturally obeys the area theorem and estimate the MAP and BP thresholds. We also conjecture that SC codes due to threshold saturation can universally approach the symmetric information rate of ISI channels. In the third part, a similar analysis is used to analyze the MAP thresholds of LDPC codes for several multiuser systems, namely a noisy Slepian-Wolf problem and a multiple access channel with erasures. We provide rigorous analysis and derive upper bounds on the MAP thresholds which are shown to be tight in some cases. This analysis is a first step towards proving threshold saturation for these systems which would imply SC codes with joint BP decoding can universally approach the entire capacity region of the corresponding systems.

Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher-Kiayias-Yung is extended to the polynomials whose degrees are allowed to be distinct. Furthermore, it is observed that probability of the algorithm can be increased. Specifically, for a finite field $F$, we present a probabilistic algorithm which can recover polynomials $p_1,ldots, p_r in F[x]$ of degree less than $k_1,k_2,ldots,k_r$, respectively with given field evaluations $p_l(z_i) = y_{i,l}$ for all $i in I$, $|I|=t$ and $l in [r]$ with probability at least $1 - (n - t)/|F|$ and with time complexity at most $O((nr)^3)$. Next, by using this algorithm, we present a probabilistic decoder for interleaved Reed-Solomon codes. It is observed that interleaved Reed-Solomon codes over $F$ with rate $R$ can be decoded up to burst error rate $frac{r}{r+1}(1 - R)$ probabilistically for an interleaving parameter $r$. It is proved that a Reed-Solomon code RS$(n / k)$ can be decoded up to error rate $frac{r}{r+1}(1 - R&#039 / )$ for $R&#039 / = frac{(k-1)(r+1)+2}{2n}$ when probabilistic interleaved Reed-Solomon decoders are applied. Similarly, for a finite field $F_{q^2}$, it is proved that $q$-folded Hermitian codes over $F_{q^{2q}}$ with rate $R$ can be decoded up to error rate $frac{q}{q+1}(1 - R)$ probabilistically. On the other hand, it is observed that interleaved codes whose subcodes would have different minimum distances can be list decodable up to radius of minimum of list decoding radiuses of subcodes. Specifically, we present a list decoding algorithm for $C$, which is interleaving of $C_1,ldots, C_b$ whose minimum distances would be different, decoding up to radius of minimum of list decoding radiuses of $C_1,ldots, C_b$ with list size polynomial in the maximum of list sizes of $C_1,ldots, C_b$ and with time complexity polynomial in list size of $C$ and $b$. Next, by using this list decoding algorithm for interleaved codes, we obtained new list decoding algorithm for $qh$-folded Hermitian codes for $q$ standing for field size the code defined and $h$ is any positive integer. The decoding algorithm list decodes $qh$-folded Hermitian codes for radius that is generally better than radius of Guruswami-Sudan algorithm, with time complexity and list size polynomial in list size of $h$-folded Reed-Solomon codes defined over $F_{q^2}$.

Deux défis de la théorie du codage algébrique sont traités dans cette thèse. Le premier est le décodage efficace (dur et souple) de codes de Reed--Solomon généralisés sur les corps finis en métrique de Hamming. La motivation pour résoudre ce problème vieux de plus de 50 ans a été renouvelée par la découverte par Guruswami et Sudan à la fin du 20ème siècle d'un algorithme polynomial de décodage jusqu'au rayon Johnson basé sur l'interpolation. Les premières méthodes de décodage algébrique des codes de Reed--Solomon généralisés faisaient appel à une équation clé, c'est à dire, une description polynomiale du problème de décodage. La reformulation de l'approche à base d'interpolation en termes d'équations clés est un thème central de cette thèse. Cette contribution couvre plusieurs aspects des équations clés pour le décodage dur ainsi que pour la variante décodage souple de l'algorithme de Guruswami--Sudan pour les codes de Reed--Solomon généralisés. Pour toutes ces variantes un algorithme de décodage efficace est proposé. Le deuxième sujet de cette thèse est la formulation et le décodage jusqu'à certaines bornes inférieures sur leur distance minimale de codes en blocs linéaires cycliques. La caractéristique principale est l'intégration d'un code cyclique donné dans un code cyclique produit (généralisé). Nous donnons donc une description détaillée du code produit cyclique et des codes cycliques produits généralisés. Nous prouvons plusieurs bornes inférieures sur la distance minimale de codes cycliques linéaires qui permettent d'améliorer ou de généraliser des bornes connues. De plus, nous donnons des algorithmes de décodage d'erreurs/d'effacements [jusqu'à ces bornes] en temps quadratique.

[pt] Há, nos dias atuais, uma crescente demanda pelo transporte de video sobre IP, i.e., para distribuição de conteúdo pela Internet, por serviços de IPTV em definição padrão e em alta definição e, mesmo para uso interno nas redes de emissoras tradicionais de televisão, que transportam contribuições de elevada qualidade para seus programas. Em tais aplicações, o conteúdo dos programas é transportado usando MPEG-2 ou MPEG-4, sob a forma de MPEG-2 Transport Streams, encapsulados com protocolos tais como RTP, UDP e IP. As redes IP, que são modelizadas como Redes com Apagamento de Pacotes (PEC) não foram, no entanto, concebidas para o transporte de mídias em tempo real, esbarra portanto em problemas comuns como perdas de pacotes e jitter, gerando perturbações que se refletem na recepção do conteúdo. Os métodos tradicionais para superar estas dificuldades, como por exemplo, os que se baseiam em retransmissões usando protocolos ARQ (Automatic Repeat on Request), não são uma solução eficiente para proteger a transmissão de multimídia em tempo real. A proteção de multimídia transmitida em tempo real via IP recorre, neste caso, aos códigos para canal. Há códigos para canal recomendados em RFC s e Padrões, usados amplamente pelos fabricantes de equipamento. Os modernos Códigos Fontanais, possuem características atraentes para o transporte de conteúdos multimídia em tempo real. Neste trabalho, simulações são realizadas, onde o conteúdo encapsulado em Transport Stream, é protegido com Códigos Fontanais antes do encapsulamento para o envio através da rede. A título de comparação, o experimento é realizado também usando outros códigos para canal recomendados. Para realizar a comparação são usadas medições padronizadas do Transport Stream, medições objetivas como artefatos de blocagem e finalmente uma análise subjetiva do conteúdo recebido é usada. O trabalho conclui com a proposta de um Codificador de canal adaptável para Transport Stream. / [en] There is a growing demand for the transport of video over IP today, i.e., for content distribution over the Internet, IPTV services in Standard and High Definition, or even inside traditional broadcasters networks, transporting broadcast quality contributions to the main program. In such applications, the source encoded MPEG-2 or -4 content is transported in the form of MPEG-2 Transport Streams, encapsulated over network protocols. However, IP networks, which can be modeled as Packet Erasure Networks (PEC), were not originally designed for the transport of real time media. There are problems, such as packet drops and jitter, which generate severe impairments in the content that is decoded at the reception. Traditional methods for overcoming these problems, as for example retransmissions performed by Automatic Repeat Request (ARQ) protocols, are not suitable for real-time multimedia protection. Channel coding is the solution of choice for protecting real-time multimedia over IP. There are channel coding schemes specified in open recommendations and Standards, widely adopted by equipment vendors today. Fountain Codes present very attractive characteristics for the transport of real-time multimedia. In the present work, simulations with a Fountain code, protecting Transport Stream contents prior to network encapsulation, are presented. The experiment if repeated with other channel coding techniques commonly employed today. In order to analyze the decoded contents and obtain comparative results, standardized Transport Stream measurements, objective Blocking Artifacts measurements and subjective analysis of the decoded samples are employed. This work is concluded with the proposal of a Transport Stream Adaptive channel encoder, that is explained in Appendix-B.

Orientadores: Dalton Soares Arantes, Júlio César Rodrigues Fernandes de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T18:41:53Z (GMT). No. of bitstreams: 1 Salvador_ArleyHenrique_M.pdf: 3542397 bytes, checksum: 0847a4269c07c0969394ba0b40491987 (MD5) Previous issue date: 2015 / Resumo: Este trabalho apresenta a implementação de uma arquitetura paralela de um código corretor de erros para aplicações em redes ópticas que utilizam a técnica Foward Error Correction (FEC). O algoritmo FEC especificamente tratado neste trabalho é o Reed-Solomon, que é destinado principalmente a sistemas que sofrem influência causada por erros em rajadas somados ao sinal durante a transmissão, o que o torna adequado para transmissões ópticas. São expostas estruturas seriais de codificador e decodificador FEC e as etapas para convertê-las para uma estrutura paralela. Após descrever as etapas de conversão de uma estrutura serial para paralela é apresentada a estrutura do codificador/decodficador FEC Reed-Solomon RS(255,239) com estrutura paralela para operar em redes ópticas a uma taxa de 100 Gbit/s. Esta descrição exemplificativa é o objetivo principal deste trabalho. A implementação paralela do FEC oferece como vantagem a capacidade de processar os dados de forma rápida, permitindo o emprego desta solução em sistemas com altas taxas de dados. Foi elaborado um ambiente de testes com uma aplicação em redes de transporte óptico, ou Optical Transport Network (OTN). Esta funcionalidade consiste de um Transponder, que tem a função de mapear um cliente de 100 Gigabits Ethernet dentro de uma estrutura de quadro destinado a transmissão de dados em redes ópticas. Deste modo, pôde-se comprovar os resultados e o desempenho da estrutura proposta / Abstract: This paper presents the implementation of a parallel architecture error-correcting code for optical applications that uses the Forward Error Correction (FEC) technique. The FEC algorithm specifically addressed in this work is applied to the Reed-Solomon, which is mainly intended for systems that are harmed by burst errors, which makes it suitable for optical transmissions. A serial FEC encoder/decoder structure and the steps to convert it to a parallel approach are addressed in this work. An example of method that generates an encoder/decoder for a RS(255,239) Reed-Solomon code with parallel structure, able to operate at 100 Gbit/s data rate in optical networks, is also presented. The parallel implementation offers higher FEC processing speeds to handle higher throughputs. A test environment was designed with an application in optical transport networks (OTN). This feature consists a transponder which maps a 100 Gigabit Ethernet client inside an OTN frame structure. With this setup the expected results for the proposed FEC circuitry could be experimentally verified / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

<p>Predmet istraživanja doktorske disertacije je faktorizacija polinoma dve promenljive sa celobrojnim koeficijentima pomoću njima pridruženih Newton-ovih poligona. Formalizacija potrebnog i dovoljnog uslova za postojanje netrivijalne faktorizacije polinoma dve promenljive sa celobrojnim koeficijentima omogućava konstrukciju efektivnog algoritma za faktorizaciju. Konačno, dobijeni teorijski rezultati su primenjeni na dekodiranje jedne klase Reed &ndash; Solomon kodova, miksa dve kodne reči.</p> / <p>The research subject of the thesis is factorization of bivariate polynomials with integer coefficients via associated Newton polygons. Formalization of the necessary and sufficient condition for the existence of a non &ndash; trivial factorization of an arbitrary bivariate polynomial with integer coefficients obtains theoretical basis for construction of an effective factorization algorithm. Finally, these theoretical results are applied in decoding special class of Reed &ndash; Solomon codewords, mixture of two codewords.</p>

Detta arbete är ett examensarbete i matematik på kandidatnivå vid Växjö universitet. Det är en studie av kodningsteori i allmänhet med fokusering på cykliska koder och Reed-Solomon-koder i synnerhet. Reed-Solomon-koderna används för att skapa McElieces kryptosystem. En kortfattad analys av McElieces kryptosystems säkerhet görs tillsammans med en genomgång av kända sätt att forcera denna typ av kryptosystem. Här visar det sig att användning av Reed-Solomon-kod försvagar kryptosystemet i förhållande till om den ursprungligt föreslagna Goppa-koden används. För att kunna göra denna säkerhetsanalys görs också en kortfattad genomgång av komplexitetsteori och vad det innebär att ett problem är NP-fullständigt. Nyckelord: Kodningsteori, Kodteori, Cykliska koder, BCH-koder, Reed-Solomon-koder, McElieces kryptosystem, Kryptering, Kodforcering, Komplexitetsteori, NP-fullständigt / This work is produced on bachelor level in mathematics at University of Växjö. It is a study of coding theory with focus on cyclic codes in general and Reed-Solomon codes in detail. Reed-Solomon codes are used for implementing McEliece's crypto system. A short analysis of McEliece's crypto system security is also made together with a description of some known ways to break this type of cryptosystem. It is shown that using Reed-Solomon codes weaken this cryptosystem compared to using the original supposed Goppa codes. The security analyse also need a short summary of complexity theory and what it means that a problem is NP-complete. Keywords: Coding theory, Cyclic codes, BCH codes, Reed-Solomon codes, McEliece's cryptography system, Cryptography, Code breaking, Complexity theory, NP-complete

<p>Detta arbete är ett examensarbete i matematik på kandidatnivå vid Växjö universitet. Det är en studie av kodningsteori i allmänhet med fokusering på cykliska koder och Reed-Solomon-koder i synnerhet. Reed-Solomon-koderna används för att skapa McElieces kryptosystem. En kortfattad analys av McElieces kryptosystems säkerhet görs tillsammans med en genomgång av kända sätt att forcera denna typ av kryptosystem. Här visar det sig att användning av Reed-Solomon-kod försvagar kryptosystemet i förhållande till om den ursprungligt föreslagna Goppa-koden används. För att kunna göra denna säkerhetsanalys görs också en kortfattad genomgång av komplexitetsteori och vad det innebär att ett problem är NP-fullständigt.</p><p><strong>Nyckelord: </strong>Kodningsteori, Kodteori, Cykliska koder, BCH-koder, Reed-Solomon-koder, McElieces kryptosystem, Kryptering, Kodforcering, Komplexitetsteori, NP-fullständigt</p> / <p>This work is produced on bachelor level in mathematics at University of Växjö. It is a study of coding theory with focus on cyclic codes in general and Reed-Solomon codes in detail. Reed-Solomon codes are used for implementing McEliece's crypto system. A short analysis of McEliece's crypto system security is also made together with a description of some known ways to break this type of cryptosystem. It is shown that using Reed-Solomon codes weaken this cryptosystem compared to using the original supposed Goppa codes. The security analyse also need a short summary of complexity theory and what it means that a problem is NP-complete.</p><p><strong>Keywords:</strong> Coding theory, Cyclic codes, BCH codes, Reed-Solomon codes, McEliece's cryptography system, Cryptography, Code breaking, Complexity theory, NP-complete</p>

Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits. / Contrary to the cryptosystems based on number theory, the security of cryptosystems based on error correcting codes appears to be resistant to the emergence of quantum computers. Another advantage of these systems is that the encryption and decryption are very fast, about five times faster for encryption, and 10 to 100 times faster for decryption compared to RSA cryptosystem. Nowadays, the interest of scientific community in code-based cryptography is highly motivated by the latest announcement of the National Institute of Standards and Technology (NIST). They initiated the Post-Quantum cryptography Project which aims to define new standards for quantum resistant cryptography and fixed the deadline for public key cryptographic algorithm submissions for November 2017. This announcement motivates to study the security of existing schemes in order to find out whether they are secure. This thesis thus presents several attacks which dismantle several code-based encryption schemes. We started by a cryptanalysis of a modified version of the Sidelnikov cryptosystem proposed by Gueye and Mboup [GM13] which is based on Reed-Muller codes. This modified scheme consists in inserting random columns in the secret generating matrix or parity check matrix. The cryptanalysis relies on the computation of the square of the public code. The particular nature of Reed-Muller which are defined by means of multivariate binary polynomials, permits to predict the values of the dimensions of the square codes and then to fully recover in polynomial time the secret positions of the random columns. Our work shows that the insertion of random columns in the Sidelnikov scheme does not bring any security improvement. The second result is an improved cryptanalysis of several variants of the GPT cryptosystem which is a rank-metric scheme based on Gabidulin codes. We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. [Gab08, GRH09, RGH11] with the goal to resist Overbeck’s structural attack [Ove08], are actually still vulnerable to that attack. We show that by applying the Frobeniusoperator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code, but with a lower length. In particular, the code obtained by this way corrects less errors than thesecret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometrictransformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existingtechniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed. To finish, we studied the security of the Faure-Loidreau encryption scheme [FL05] which is also a rank-metric scheme based on Gabidulin codes. Inspired by our precedent work and, although the structure of the scheme differs considerably from the classical setting of the GPT cryptosystem, we show that for a range of parameters, this scheme is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck’s attack on an appropriate public code. As an example we break in a few seconds parameters with 80-bit security claim.