Gotowa bibliografia na temat „Codes linéaires par bloc”

Dans cet article, nous allons montrer comment l’analyse de la pièce Due di Uno (2002 - 03) d’Agostino di Scipio nous a conduits à la composition d’une nouvelle pièce originale. Nous proposons, dans un premier temps, l’analyse par modélisation orientée objet-opératoire comme un modèle d’analyse créative faite par un compositeur, démarche s’appuyant sur les fondements théoriques posés par Horacio Vaggione. Ensuite, nous interprétons les codes informatiques de la pièce Due di Uno en mettant en évidence un objet de contrôle algorithmique non linéaire, pour finalement l’émuler dans la composition d’une nouvelle pièce par l’un des auteurs en tant qu’analyste-compositeur, La Philosophie du temps pour piano et électronique en temps réel.

Dans les réseaux de communication distribués, les données sont collectées, compressées, et transmises depuis des nœuds distants vers un serveur central pour un traitement ultérieur. Cependant, l’objectif du serveur n’est pas toujours de reconstruire les données originales, mais plutôt de prendre des décisions à partir des données codées reçues. Dans ce contexte, le Test d’Hypothèses Distribué se concentre sur le cas particulier de deux sources et vise à effectuer une prise de décision directement à partir des données compressées, sans passer par une reconstruction préalable. Comme dans le test d’hypothèses classique, deux types d’erreurs sont pris en compte pour évaluer les performances : l’erreur de Type I (fausse alarme) et l’erreur de Type II (décision manquée). Le Test d’Hypothèses Distribué prend en compte une contrainte de débit sur le lien de communication, et l’objectif est de concevoir un schéma de codage afin de maximiser la décroissance exponentielle, appelée exposant d’erreur, de la probabilité d’erreur de Type II, tout en maintenant la probabilité d’erreur de Type I en dessous d’un seuil spécifié. Dans la littérature, ce cadre a principalement été étudié sous un angle théorique de l’information, et la plupart des travaux existants analysent les performances des schémas du Test d’Hypothèses Distribué en supposant des sources indépendantes et identiquement distribuées (i.i.d.).Dans la première partie de cette thèse, nous abordons un modèle plus réaliste et général de sources non-i.i.d. Ce modèle englobe des sources non stationnaires et non ergodiques, reflétant mieux les scénarios réels par rapport au cas i.i.d. Nous dérivons des bornes génériques sur l’exposant d’erreur pour le Test d’Hypothèses Distribué à l’aide d’outils du spectre de l’information pour ce modèle général de sources. Nous montrons la cohérence de ces bornes avec le cas i.i.d. et les caractérisons plus précisément pour deux modèles spécifiques de sources : les sources gaussiennes non-i.i.d., et les sources de type Gilbert-Elliot. De plus, l’étude du Test d’Hypothèses Distribué ne se limite pas à l’analyse des limites théoriques de l’information, mais inclut aussi le développement de schémas de codage pratiques pour ce cadre. Ainsi, dans la deuxième partie de cette thèse, nous développons et implémentons des schémas de codage pratiques de courte longueur, spécialement conçus pour le Test d’Hypothèses Distribué, qui n’avaient pas encore été étudiés dans la littérature. Ces schémas de codage sont basés sur des codes linéaires en blocs et visent des longueurs très courtes, appropriées pour le Test d’Hypothèses Distribué (moins de 100 bits). En outre, nous fournissons des expressions analytiques exactes pour les probabilités d’erreurs de Type I et Type II pour chaque schéma de codage proposé, offrant ainsi des outils utiles pour la conception optimale future de codes DHT. Le travail réalisé dans cette thèse pourrait servir de base à l’investigation théorique et pratique de schémas de codage dédiés à des tâches d’apprentissage plus complexes, telles que la classification
In distributed communication networks, data is gathered, compressed, and transmitted from remote nodes to a central server for further processing. However, often, the objective of the server is not to reconstruct the original data, but rather to make decisions based on the received coded data. In this context, Distributed Hypothesis Testing (DHT) focuses on the particular case of two sources and addresses decision-making directly from compressed data without prior reconstruction. As in conventional hypothesis testing, two types of errors are considered for performance evaluation: Type-I error (false alarm) and Type-II error (missed detection). DHT considers a rate-limited communication link, and the objective is to design a coding scheme so as to maximize the exponential decay, termed error exponent, of Type-II error probability, while keeping Type-I error probability below a specified threshold. In the literature, this setup was mostly investigated from an information-theoretic perspective, and most existing work analyze the performance of DHT schemes under the assumption of i.i.d. sources. In the first part of this PhD thesis, we address a more realistic and general model of non-i.i.d. sources. This model encompasses non-stationary and non-ergodic sources, and better reflects real-world scenarios compared to the i.i.d. case. We derive generic error exponent DHT bounds using information spectrum tools for the considered general source model. We show the consistency of these bounds with the i.i.d. case and further characterize these bounds for two specific source models: non-i.i.d. Gaussian sources, and Gilbert-Elliot sources. In addition, addressing DHT requires not only the investigation of information-theoretic limits, but also the development of practical coding schemes for this setup. Therefore, in the second part of this thesis, we develop and implement practical short-length coding schemes specifically for DHT, which had not yet been investigated in the literature. These coding schemes are based on linear block codes, and they target very short length which are appropriate for DHT (less than 100 bits). Additionally, we provide tights analytical expressions for the Type-I and Type-II error probabilities for each proposed coding scheme, which provides useful tools for further optimal DHT code designs. The work carried out in this PhD may serve as a basis for the theoretical and practical investigation of coding schemes dedicated to more complex learning tasks such as classification

Cette thèse contribue à l’effort de cryptanalyse de primitives symétriques comme les chiffrements par bloc ou les générateurs pseudo-aléatoires. Elle étudie en particulier une famille de distingueurs fondés sur la propagation de sous-espaces vectoriels différentiels dans les chiffrements par bloc de construction SPN. Cette thèse propose également des méthodes permettant aux cryptographes de modéliser un problème de cryptanalyse de primitive symétrique en problème MILP (Mixed-Integer Linear Programming), afin d’exploiter certains logiciels solutionneurs de problèmes MILP très performants. Enfin, elle présente des techniques d’analyse algébrique des primitives symétriques, fondées sur le calcul d’une partie de leur forme algébrique normale, et utiles dans les attaques de type cube
This thesis contributes to the cryptanalysis effort needed to trust symmetric-key primitives like block-ciphers or pseudorandom generators. In particular, it studies a family of distinguishers based on subspace trails against SPN ciphers. This thesis also provides methods for modeling frequent cryptanalysis problems into MILP (Mixed-Integer Linear Programming) problems to allow cryptographers to benefit from the existence of very efficient MILP solvers. Finally, it presents techniques to analyze algebraic properties of symmetric-key primitives which could be useful to mount cube attacks

La methode de Lanczos est l'une des methodes iteratives les plus utilisees pour la resolution des systemes lineaires, cependant une division par zero (breakdown) peut etre rencontree. Dans la premiere partie de cette these, une approche unifiee de quelques strategies (mrz, biores non generique et csbcg) pour eviter cet inconvenient est proposee. Grace a cette approche, une nouvelle implantation de la methode biores non generique a ete etablie. Celle-ci requiert le stockage d'un nombre fixe de vecteurs. Dans la suite, nous nous sommes interesses a la resolution de systemes lineaires multiples ax = b avec a , r n , n, x, b , r n , s et s<
Ce lien nous a permis, d'une part, d'implanter la methode de lanczos par bloc via les relations de recurrence satisfaites par la famille rmfop et/ou la famille adjacente, d'autre part, d'introduire quelques methodes produit par bloc combinant l'une des methodes de type lanczos par bloc et celle de la plus profonde descente globale (bl-biostab, bl-bicgstab). Ces methodes ont l'avantage d'eviter l'utilisation de la matrice transposee de a et d'ameliorer la convergence des methodes initiales. Enfin, une procedure de near breakdown partiel a ete definie et appliquee au bl-bicgstab. Elle est basee sur le processus de gram-schmidt et sur une nouvelle notion de projection (projection produit). L'algorithme obtenu, appele pnb bl-bicgstab, evite les situations de near breakdown et remedie au probleme de deflation. Les exemples numeriques proposes montrent clairement l'efficacite de cette methode

Cette thèse porte sur les liens entre les codes correcteurs d'erreurs et les matrices de diffusion linéaires utilisées en cryptographie symétrique. L'objectif est d'étudier les constructions possibles de codes MDS additifs définis sur le groupe (Fm2, +) des m-uplets binaires et de minimiser le coût de l'implémentation matérielle ou logicielles de ces matrices de diffusion. Cette thèse commence par l'étude des codes définis sur un anneau de polynômes du type F[x]/f(x), qui généralisent les codes quasi-cycliques. Elle se poursuit par l'étude des codes additifs systématiques définis sur (Fm2, +) et leur lien avec la diffusion linéaire en cryptographie symétrique. Un point important de la thèse est l'introduction de codes à coefficient dans l'anneau des endomorphismes de Fm2. Le lien entre les codes qui sont des sous-modules à gauche et les codes additifs est mis en évidence. La dernière partie porte sur l'étude et la construction de matrices de diffusion MDS ayant de bonnes propriétés pour la cryptographie, à savoir les matrices circulantes, les matrices dyadiques, ainsi que les matrices ayant des représentations creuses minimisant leur implémentation
This PhD focuses on the links between error correcting codes and diffusion matrices used in cryptography symmetric. The goal is to study the possible construction of additives MDS codes defined over the group (Fm2, +) of binary m-tuples and minimize cost of hardware or software implementation of these diffusion matrices. This thesis begins with the study of codes defined over the polynomial ring F[x]/f(x), these codes are a generalization of quasi-cyclic codes, and continues with the study of additive systematic codes over (Fm2, +) and there relation with linear diffusion on symmetric cryptography. An important point of this thesis is the introduction of codes with coefficients in the ring of endomorphisms of Fm2. The link between codes which are a left-submodules and additive codes have been identified. The last part focuses on the study and construction of efficient diffusion MDS matrices for the cryptographic applications, namely the circulantes matrices, dyadic matrices, and matrices with hollow representation, in ordre to minimize their implementations

Depuis la fin des années 90, les cryptosystèmes implantés sur carte à puce doivent faire face à deux grandes catégories d'attaques : les attaques par canaux cachés et les attaques par injection de fautes. Pour s'en prémunir, des contre-mesures sont élaborées, puis validées en considérant un modèle d'attaquant bien défini. Les travaux réalisés dans cette thèse se concentrent sur la protection des cryptosystèmes symétriques contre les attaques par canaux cachés. Plus précisément, on s'intéresse aux contre-mesures de masquage permettant de se prémunir des attaques statistiques d'ordre supérieur pour lesquelles un attaquant est capable de cibler t valeurs intermédiaires. Après avoir rappelé l'analogie entre les contre-mesures de masquage et les schémas de partage de secret, on présente la construction des schémas de partage de secret à partir de codes linéaires, introduite par James L. Massey en 1993. En adaptant cette construction et des outils issus du calcul multi-parties, on propose une méthode générique de contre-mesure de masquage résistante aux attaques statistiques d'ordre supérieur. De plus, en fonction des cryptosystèmes à protéger et donc des opérations à effectuer, cette solution permet d'optimiserle coût induit par les contre-mesures en sélectionnant les codes les plus adéquats. Dans cette optique, on propose deux contre-mesures de masquage pour implanter le cryptosystème AES. La première est basée sur une famille de code d'évaluation proche de celle utilisée pour le schéma de partage de secret de Shamir, tandis que la seconde considéré la famille des codes auto-duaux et faiblement auto-duaux ayant leur matrice génératrice à coefficient sur F2 ou F4. Ces deux alternatives se révèlent plus efficaces que les contremesures de masquage publiées en 2011 et basées sur le schéma de partage de secret de Shamir. De plus la seconde s'avère compétitive pour t=1 comparée aux solutions usuelles
Since the late 90s, the implementation of cryptosystems on smart card faces two kinds of attacks : side-channel attacks and fault injection attacks. Countermeasures are then developed and validated by considering a well-defined attacker model. This thesis focuses on the protection of symmetric cryptosystems against side-channel attacks. Specifically, we are interested in masking countermeasures in order to tackle high-order attacks for which an attacker is capable of targeting t intermediate values. After recalling the analogy between masking countermeasures and secret sharing schemes, the construction of secret sharing schemes from linear codes introduced by James L. Massey in 1993 is presented.By adapting this construction together with tools from the field of Multi-Party Computation, we propose a generic masking countermeasure resistant to high-order attacks. Furthermore, depending on the cryptosystem to protect, this solution optimizes the cost of the countermeasure by selecting the most appropriate code. In this context, we propose two countermeasures to implement the AES cryptosystem. The first is based on a family of evaluation codes similar to the Reed Solomon code used in the secret sharing scheme of Shamir. The second considers the family of self-dual and self-orthogonal codes generated by a matrix defined over GF(2) or GF(4). These two alternatives are more effective than masking countermeasures from 2011 based on Shamir's secret sharing scheme. Moreover, for t=1, the second solution is competitive with usual solutions

Cette thèse présente un travail sur les méthodes itératives pour résoudre des systèmes linéaires en réduisant les communications pendant les calculs parallèles. Principalement, on est intéressé par les systèmes linéaires qui proviennent des simulations de réservoirs. Trois approches, que l’on peut considérer comme indépendantes, sont présentées. Nous considérons les systèmes linéaires non-symétriques (resp. symétriques), cela correspond au schéma explicite (resp. implicite) du problème modèle. On commence par présenter une approche qui ajoute plusieurs directions de recherche à chaque itération au lieu d’une seule direction comme dans le cas des méthodes classiques. Ensuite, on considère les stratégies de recyclage des espaces de recherche. Ces stratégies réduisent, par un facteur considérable, le nombre d’itérations global pour résoudre une séquence de systèmes linéaires. On fait un rappel des stratégies existantes et l’on en présente une nouvelle. On introduit et détaille l’implémentation parallèle de ces méthodes en utilisant un langage bas niveau. On présente des résultats numériques séquentiels et parallèles. Finalement, on considère la méthode de décomposition de domaine algébrique. Dans un environnement algébrique, on étudie le préconditionneur de Schwarz additif à deux niveaux. On fournit la forme algébrique explicite d’une classe d’espaces grossiers locaux qui bornent le conditionnement par un nombre donné a priori
This thesis presents a work on iterative methods for solving linear systems that aim at reducing the communication in parallel computing. The main type of linear systems in which we are interested arises from a real-life reservoir simulation. Both schemes, implicit and explicit, of modelling the system are taken into account. Three approaches are studied separately. We consider non-symmetric (resp. symmetric) linear systems. This corresponds to the explicit (resp. implicit) formulation of the model problem. We start by presenting an approach that adds multiple search directions per iteration rather than one as in the classic iterative methods. Then, we discuss different strategies of recycling search subspaces. These strategies reduce the global iteration count of a considerable factor during a sequence of linear systems. We review different existing strategies and present a new one. We discuss the parallel implementation of these methods using a low-level language. Numerical experiments for both sequential and parallel implementations are presented. We also consider the algebraic domain decomposition approach. In an algebraic framework, we study the two-level additive Schwarz preconditioner. We provide the algebraic explicit form of a class of local coarse spaces that bounds the spectral condition number of the preconditioned matrix by a number pre-defined

Cette thèse s'inscrit dans le cadre de l'analyse d'un schéma de transmission pour les communications pour les mobiles par satellites. L'objectif est de proposer un schéma de transmission offrant un bon compromis entre la puissance de la porteuse, l'efficacité spectrale de la chaîne de communications, le temps d'entrelacement total et la complexité du récepteur. La modulation de référence utilisée durant ces travaux est la Modulation Codée en Treillis (MCT) d'Ungerboeck 8-PSK à 8 états de taux 2/3. Un modèle de canal mobile-satellite prenant en compte la vitesse du mobile, la fréquence et l'angle de site du terminal par rapport au satellite en visibilité a été développé. La statistique du canal est du type Rice/Rayleigh-Lognormale. Les performances de cette chaîne de communications de référence en terme de Taux d'Erreur Binaire (TEB) ont été analysées pour une chaîne concaténée composée de code Reed-Solomon (RS) et de MCT. Pour ce faire, une méthode semi-analytique est proposée en considérant dans un premier temps un entrelacement infini. Cette méthode permet d'obtenir de faibles valeurs de TEB en un temps de calcul raisonnable (qqs mn). Par la suite, l'influence du temps d'entrelacement sur les performances en terme de TEB est analysée. La dernière étape a consisté à étudier l'apport de la diversité de satellites (pour des systèmes utilisant des constellations en orbite basse, une diversité d'ordre 2 à 3 peut être envisagée sans trop de contraintes) sur les performances en terme de TEB. La technique de combinaison en réception retenue est la technique Maximal Ratio Combining (MRC). Les performances en terme de TEB sont non seulement évaluées pour la chaîne MCT seule mais aussi pour la chaîne concaténée RS-MCT.

Parmi les différents critères qu'une fonction booléenne doit satisfaire en cryptographie, on s'intéresse à la non-linéarité. Pour une fonction booléenne donnée, cette notion mesure la distance de Hamming qui la sépare des fonctions de degré au plus 1. C'est un critère naturel pour évaluer la complexité d'une fonction cryptographique, celle-ci ne devant pas admettreune approximation qui soit simple, comme par une fonction de degré 1, ou plus généralement une fonction de bas degré. Ainsi, il est important de considérer plus généralement, la non-linéarité d'ordre supérieur, qui pour un ordre donné r, mesure la distance d'une fonction donnée à l'ensemble des fonctions de degré au plus r. Cette notion est également importante pour les fonctions vectorielles, i.e., celles à plusieurs sorties. Quand le nombre de variables est grand, presque toutes les fonctions ont une non-linéarité (d'ordre 1) voisine d'une certaine valeur, assez élevée. Dans un premier travail, on étend ce résultat à l'ordre 2. Cette méthode qui consiste à observer comment les boules de Hamming recouvrent l'hypercube des fonctions booléennes, nous conduit naturellement vers une borne de décodage théorique des codes de Reed-Muller d'ordre 1, coïncidant au même endroit où se concentre la non-linéarité de presque toutes les fonctions ; une approche nouvelle pour un résultat pas entièrement nouveau. On étudie aussi la non-linéarité des fonctions vectorielles. On montre avec une approche différente, que le comportement asymptotique est le même que celui des fonctions booléennes: une concentration de la non-linéarité autour d'une valeur assez élevée
Among the different criteria that a Boolean function must satisfy in symmetric cryptography, we focus on the nonlinearity of these. This notion measures the Hamming distance between a given function and the set of functions with degree at most 1. It is a natural criterion to evaluate the complexity of a cryptographic function that must not have a simple approximation as by a function of degree 1, or more generally, a function of low degree. Hence, it is important to consider the higher order nonlinearity, which for a given order r, measures the distance between a given function and the set of all functions of degree at most r. This notion is equally important for multi-output Boolean functions. When the number of variables is large enough, almost all Boolean functions have nonlinearities lying in a small neighbourhood of a certain high value. We prove that this fact holds when considering the second-order nonlinearity. Our method which consists in observing how the Hamming balls pack the hypercube of Boolean functions led quite naturally to a theoretical decoding bound for the first-order Reed-Muller code, coinciding with the concentration point of the nonlinearity of almost all functions. This was a new approach for a result which is not entirely new. We also studied the nonlinearity of multi-output functions. We proved with a different approach, that the asymptotic behaviour of multi-output functions is the same as the single-output ones: a concentration of the nonlinearity around a certain large value

Cette thèse s'articule principalement autour de la théorie des codes et des fonctions booléennes liés à la cryptographie. Deux axes sont suivis : la première partie est dédiée à la non-linéarité des fonctions booléennes, alors que la deuxième partie présente des applications en cryptographie d'objets provenant de ces théories. Motivé par la conjecture de Patterson et Wiedemann, nous proposons une généralisation de la construction par réunions d'orbites suivant l'action d'un groupe, où la minimisât!on de l'amplitude spectrale se ramène à deux sous-problèmes que nous étudions : l'estimation de sommes de Gauss et l'estimation de sommes d'exponentielles incomplètes. Plusieurs conditions et pistes de résolution de la conjecture sont alors détaillées. Ce travail nous permet de construire a sympto tique ment des fonctions de non-linéarité plus élevée que la moyenne et nous obtenons de plus, suivant ce principe, un exemple de recollement quadratique hautement non-linéaire proche de la borne de Patterson et Wiedemann en dimension 15. Dans la deuxième partie, nous portons tout d'abord notre attention sur des protocoles cryptographiques dits à faibles ressources. Des fonctions booléennes résistantes à la cryptanalyse différentielle sont utilisées afin de protéger le protocole HB+ d'une attaque par le milieu. À partir d'un deuxième protocole basé sur un principe de bruitage, nous effectuons un parallèle avec la théorie du canal à jarretière de Wyner, ce qui permet d'accroître la sécurité. D'autre part, dans le cadre de l'authentification de données variables dans le temps, une adaptation du cryptosystème de McEliece est détaillée afin de contrôler l'accès aux fonctions de vérification.

Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets
A distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs