La cryptographie basée sur les codes n'est pas largement déployée dans la pratique. Principalement à cause de son inconvénient majeur: des tailles de clés énormes. Dans cette thèse, nous proposons deux approches différentes pour résoudre ce problème. Le premier utilise des codes algébriques, présentant un moyen de construire des codes de Goppa qui admettent une représentation compacte. Ce sont les Codes de Goppa p-adiques. Nous montrons comment construire ces codes pour instancier des systèmes de chiffrement à clé publique, comment étendre cette approche pour instancier un schéma de signature et, enfin, comment généraliser cet approche pour définir des codes de caractéristique plus grande au égale à deux. En résumé, nous avons réussi à produire des clés très compact basé sur la renommée famille de codes de Goppa. Bien qu'efficace, codes de Goppa p-adiques ont une propriété non souhaitable: une forte structure algébrique. Cela nous amène à notre deuxième approche, en utilisant des codes LDPC avec densité augmentée, ou tout simplement des codes MDPC. Ce sont des codes basés sur des graphes, qui sont libres de structure algébrique. Il est très raisonnable de supposer que les codes MDPC sont distinguable seulement en trouvant des mots de code de poids faible dans son dual. Ceci constitue un avantage important non seulement par rapport à tous les autres variantes du système de McEliece à clés compactes, mais aussi en ce qui concerne la version classique basée sur les codes de Goppa binaires. Ici, les clés compactes sont obtenus en utilisant une structure quasi-cyclique.

Quelques résultats en cryptographie symétrique, pour les modèles de confiance dans les réseaux ambiants et la sécurité dans les réseaux de capteurs sans fil

Les tiers de confiance sont essentiels aux communications sécurisées. Par exemple, dans une infrastructure de gestion de clés, l'autorité de certification est la clé de voute de l'authentification en garantissant le lien entre une identité et une clé publique. Une carte à puce se doit, pour sa part, d'assurer la confidentialité et l'intégrité des données secrètes lorsqu'elle sert de stockage de données cryptographiques. En effet, si ces garanties sont mises en défaut dans l'une de ces situations, alors la sécurité globale du système peut en être affectée. Plusieurs approches permettent de réduire l'importance des tiers de confiance, telles qu'accroître la difficulté de recouvrer la clé secrète, en la distribuant parmi plusieurs entités, ou limiter l'impact d'une fuite d'information secrète, comme dans les cryptosystèmes "intrusion-resilient" ou "forward-secure". Dans cette thèse, nous considérons deux méthodes complémentaires. La première méthode consiste à utiliser des mots de passe, ou des clés secrètes de faible entropie, qui n'ont pas besoin d'être stockés dans un dispositif cryptographique sécurisé. Malgré la faible entropie du secret, de tels protocoles peuvent fournir un niveau d'assurance satisfaisant pour la plupart des applications. On considère en particulier la mise en accord de clés. La deuxième méthode limite le besoin de garantie de la part des tiers de confiance en utilisant un cryptosystème basé sur l'identité, dans lequel la clé publique d'un utilisateur peut être une chaîne de caractères arbitraire, telle qu'une adresse email. Comme ces systèmes fournissent une résistance aux collusions, ils peuvent aussi être utilisés pour réduire les dommages causés par l'exposition de clés secrètes en générant des secrets indépendants pour chaque période de temps ou pour chaque périphérique/entité. Par ailleurs, ces systèmes basés sur l'identité permettent aux utilisateurs d'avoir un contrôle plus fin sur les capacités de déchiffrement des tiers, en limitant les conséquences liées à un mauvais usage.

La cryptographie à base de réseaux euclidiens est aujourd'hui un domaine scientifique en pleine expansion et connait une évolution rapide et accélérée par l'attractivité du chiffrement complètement homomorphe ou des applications multilinéaires cryptographiques. Ses propriétés sont très attractives : une sécurité pouvant être réduite à la difficulté des pires cas de problèmes sur les réseaux euclidiens, une efficacité asymptotique quasi-optimale et une résistance présupposée aux ordinateurs quantiques. Cependant, on dénombre encore peu de résultats de recherche sur les constructions à visée pratique pour un niveau de sécurité fixé. Cette thèse s'inscrit dans cette direction et travaille à réduire l'écart entre la théorie et la pratique de la cryptographie à clé publique récente. Dans cette thèse, nous concevons et implémentons une signature numérique basée sur les réseaux euclidiens, deux schémas de chiffrement complètement homomorphe et des applications multilinéaires cryptographiques. Notre signature digitale ultra-performante, BLISS, ouvre la voie à la mise en pratique de la cryptographie à base de réseaux sur petites architectures et est un candidat sérieux à la cryptographie post-quantique. Nos schémas de chiffrement complètement homomorphes permettent d'évaluer des circuits non triviaux de manière compétitive. Finalement, nous proposons la première implémentation d'applications multilinéaires et réalisons, pour la première fois, un échange de clé non interactif entre plus de trois participants en quelques secondes.

Le problème du logarithme discret sur courbes elliptiques est à la base de nombreux protocoles cryptographiques, dans la mesure où on ne connaît jusqu'à présent aucun algorithme permettant de l'attaquer efficacement. Du point de vue de la cryptanalyse, certaines approches basées sur des méthodes de calcul d'indices, et s'appuyant sur la résolution de systèmes pour la recherche de relations, sont toutefois prometteuses. La première partie de cette thèse est consacrée aux techniques de calcul de bases de Gröbner appliquées à la résolution de systèmes polynomiaux. Après une description détaillée des algorithmes F4 et F5 de Faugère considérés comme les plus performants actuellement, on présente et analyse une variante de l'algorithme F4, particulièrement utile pour la résolution de nombreux systèmes "similaires". Plusieurs exemples d'applications de ce nouvel algorithme sont donnés à la fois au domaine du calcul formel et de la cryptographie, montrant que pour certaines attaques algébriques, cette variante est plus efficace que F4 et F5. Etant munis de ces nouveaux outils, on étudie dans la seconde partie le problème du logarithme discret sur courbes algébriques. Après une présentation rapide des attaques existantes sur ce type de courbes dans un contexte général, on s'intéresse plus particulièrement aux courbes elliptiques définies sur des extensions de corps finis. On donne ainsi une description complète des techniques GHS, puis des méthodes d'attaques par décomposition introduites par Gaudry et Diem. On présente notamment des variantes de ces méthodes de décompositions permettant, grâce aux outils introduits en première partie de cette thèse, de fragiliser le DLP (et des problèmes reliés) sur courbes elliptiques sur une gamme plus large d'extensions de corps finis. Enfin, une nouvelle approche combinant les attaques par recouvrement ainsi que les méthodes de décompositions est proposée : cette attaque permet entre autres de calculer complètement le logarithme discret sur des courbes elliptiques définies sur des extensions sextiques de taille jamais atteinte auparavant.

Les travaux présentés dans ce mémoire résument l'ensemble de mes activités dans le domaine de la résilience et du respect de la vie privée dans les systèmes ubiquitaires mobiles. Ils s'orientent sur trois axes principaux : l'utilisation de la réfléxivité pour la construction d'architectures sûres, la résilience des systèmes mobiquitaires (architectures, algorithmes et leur évalution), et la geoprivacy. Le premier axe concerne la tolérance aux fautes pour les systèmes distribués, sous un angle architecture et langage. Dans ces travaux, j' ai étudié l'utilisation de la réflexivité à la compilation et à l'exécution afin de faciliter l'implémentation de mécanismes de tolérance aux fautes indépendemment de l'application. L'utilisation de la réflexivité a été étudiée dans le cadre de travaux théoriques, concernant la réflexivité multi-niveaux, ou plus pratiques, comme la mise en oeuvre de la réflexivité sur des composants sur étagères, dans une architecture logicielle embarquée, ou pour permettre l'adaptation de mécanismes de tolérance aux fautes à l'exécution. Le chapitre 1 présente ces différents travaux. Le deuxième axe concerne la tolérance aux fautes dans les systèmes mobiles. Mon approche a été d'aborder la mobilité comme un atout et non pas comme une difficulté. Cette approche m'a mené à étudier la notion de communication de groupes géographiques : comment définir un groupe d'entités communicantes en fonction de leur localisation respective ou en fonction de leur proximité. J'ai ensuite, sous l'angle du pair-à-pair, proposé un système de sauvegarde coopérative de données, où les noeuds mobiles participants offrent un service de stockage sécurisé qu'ils peuvent utiliser afin de sauvegarder leurs données critiques. Cette solution a été également déclinée pour offrir un système de boîte noire virtuelle pour l'automobile. Ces travaux ont été traités sous des angles algorithmique et architecturaux, mais également sous l'angle de l'évaluation de la sûreté de fonctionnement, à la fois analytique et expérimentale. Ces travaux font l'objet du chapitre 2. Dans le cadre de mes recherches sur la résilience des systèmes mobiquitaires, des questions d'ordre déontologique ont été soulevées : comment exploiter des données de mobilité individuelles tout en préservant la vie privée des individus ? C'est à cette occasion que je me suis intéressé à ce que l'on peut nommer la geoprivacy. Ce domaine représente maintenant la majeure partie de mes travaux, tant sous l'angle des attaques que sous celui de la protection. Nous proposons un modèle Markovien de mobilité individuelle, outil à la fois compact, précis, intelligible et facilement adaptable pour représenter la mobilité d'un individu. Sur la base de ce modèle de mobilité, nous proposons plusieurs attaques qui ciblent par exemple la prédiction des déplacements futurs, ou encore la des-anonymisation. En ce qui concerne la protection de la geoprivacy, nous travaillons actuellement sur des abstractions de niveau intergiciel, tel les locanymes ou les localisation vérifiées, afin de proposer une architecture sûre et respectueuse de la vie privée pour les systèmes géolocalisés. Le chapitre 3 aborde ces aspects de ma recherche. Ces différents travaux se sont enchaînés dans un mélange de hasard, de sérendipité et de poursuite d'un objectif commun : fournir des moyens algorithmiques et architecturaux pour la résilience des systèmes informatiques actuels, à savoir distribués, mobiles, ubiquitaires. Les techniques et outils que j'utilise pour aborder cette problématique large auront été divers et variés, cela participe à mon expérience, sans cesse renouvelée. De nombreuses pistes de recherche sont encore ouvertes et sont exposées dans le chapitre 4.

Avec l'avènement des réseaux électroniques et en particulier d'Internet, de plus en plus de nouveaux services sont apparus. Il est désormais possible de faire ses achats en ligne, de consulter ses comptes en banque, de partager des informations sur les réseaux sociaux ou encore d'héberger ses documents et programmes sur des services sécurisés, les fameux "clouds"... Tous ces services ont conduit à se poser la question d'avec qui ou quoi nous communiquons. Pour répondre à cette interrogation, un nouveau terme, identité numérique a été proposé. Cette identité numérique constitue un enjeu majeur pour un certain nombre d'acteurs et en particulier pour un opérateur de télécommunications. Dans cette thèse, nous proposons d'aborder l'identité numérique en nous intéressant aux deux problématiques que sont la sécurité et la protection de la vie privée. Pour cela, trois contributions sont détaillées à commencer par une méthode d'analyse des systèmes de gestion d'identités (SGI) basée sur une cartographie des acteurs et des fonctions de la gestion d'identités. Nous montrons comment cette dernière peut permettre d'évaluer un système de gestion d'identité vis à vis des deux problématiques. A partir des évaluations réalisées, nous proposons ensuite une deuxième contribution sous la forme d'un système de gestion d'identités novateur centré sur l'utilisateur. Celui-ci met à profit des technologies comme Android, les services Web et les cartes à puces. Enfin, nous proposons un pare-feu sémantique qui protège la vie privée des utilisateurs de smartphone Android en se basant sur des ontologies.

Avec l'utilisation de notre carte bancaire pour payer un achat sur Internet ou de notre téléphone portable pour nous connecter aux réseaux sociaux, les transactions électroniques font partie de notre quotidien et sont désormais incontournables. Malheureusement, lors de tels échanges, un grand nombre de données personnelles sont transférées et une telle informatisation n'est pas sans conséquence. Les problèmes de sécurisation et de protection de ces données sont bien présents. Dans cette thèse, nous nous concentrons sur la problématique de la protection de la vie privée des utilisateurs dans des systèmes informatiques. Pour cela, nous nous intéressons à trois domaines d'actualité. Dans un premier temps, nous proposons un système de gestion des données centré sur l'utilisateur. Ainsi, lors de sa navigation sur Internet, l'internaute sera guidé et aura la possibilité de faire appel aux huit fonctionnalités offertes par l'application. Un second problème, sur lequel nous avons travaillé, est le cas des dossiers médicaux des patients et de l'accès à ces documents confidentiels. Nous proposons une architecture de e-santé permettant la protection des informations personnelles des patients au sein d'un établissement de santé et entre plusieurs établissements. Pour finir, nous avons travaillé dans le domaine de la monétique et plus précisément sur le paiement en ligne. Nous exposons ainsi trois nouveaux protocoles respectant davantage les données personnelles des internautes. Deux d'entre eux sont une amélioration de protocoles existants : 3D-Secure et le protocole d'Ashrafi et Ng. La dernière architecture, totalement nouvelle, permet de procéder à un paiement sur Internet sans fournir aucune information bancaire du client. Pour chacune de ces infrastructures, des exigences de sécurité et de protection de la vie privée sont décrites. Les solutions existantes, ainsi que celles proposées, sont détaillées et analysées en fonction de ces exigences. Les propositions d'architectures respectueuses de la vie privée ont toutes fait l'objet d'une preuve de concept avec une implémentation logicielle.

The present thesis addresses the MPEG-4 AVC stream watermarking and considers two theoretical and applicative challenges, namely ownership protection and content integrity verification.From the theoretical point of view, the thesis main challenge is to develop a unitary watermarking framework (insertion/detection) able to serve the two above mentioned applications in the compressed domain. From the methodological point of view, the challenge is to instantiate this theoretical framework for serving the targeted applications. The thesis first main contribution consists in building the theoretical framework for the multi symbol watermarking based on quantization index modulation (m-QIM). The insertion rule is analytically designed by extending the binary QIM rule. The detection rule is optimized so as to ensure minimal probability of error under additive white Gaussian noise distributed attacks. It is thus demonstrated that the data payload can be increased by a factor of log2m, for prescribed transparency and additive Gaussian noise power. A data payload of 150 bits per minute, i.e. about 20 times larger than the limit imposed by the DCI standard, is obtained. The thesis second main theoretical contribution consists in specifying a preprocessing MPEG-4 AVC shaping operation which can eliminate the intra-frame drift effect. The drift represents the distortion spread in the compressed stream related to the MPEG encoding paradigm. In this respect, the drift distortion propagation problem in MPEG-4 AVC is algebraically expressed and the corresponding equations system is solved under drift-free constraints. The drift-free shaping results in gain in transparency of 2 dB in PSNR

After reviewing some properties of the two dimensional hyperbolic toral automorphism called Arnold's discrete cat map, including its generalizations with matrices having positive unit determinant, this thesis contains a definition of a novel cat map where the elements of the matrix are found in the sequence of Pell numbers. This mapping is therefore denoted as Pell's cat map. The main result of this thesis is a theorem determining the upper bound for the minimal period of Pell's cat map. From numerical results four conjectures regarding properties of Pell's cat map are also stated. A brief exposition of some applications of Arnold's discrete cat map is found in the last part of the thesis.