Radio Frequency IDentification (RFID) provides a way to automate identification and to store information in individual RFID tags. These tags can be attached or embedded in an item to be identified and are read when they enter a RFID reader's antenna field. The Electronic Product Code (EPC) Class 1 Generation 2 (Gen2 for short) is a proper example of passive RFID technology. It represents the key component of an RFID architecture named EPCglobal network. However, if the tag carries more than just an identifier, the privacy of the tag holder may be violated. In this thesis, we deal with privacy issues in two levels of the EPCglobal network to only let authorized entities access private data. Our goal is to ensure that the data exchange from RFID tags to middleware and enterprise applications guarantees the privacy requirements, in environments where privacy control is paramount, e.g., home healthcare monitoring systems. The first part of this dissertation is dedicated to securing data exchange between RFID readers and passive tags. We provide a key establishment and derivation protocol for Gen2 systems, called KEDGEN2, to handle the flawed security model of the Gen2 tag memory access. KEDGEN2 achieves secure data exchange, based on a key generation model adapted to Gen2 tags. To prove the security of our model, we specify the protocol using the High Level Protocol Specification Language (HLPSL) and verify the expected security properties, using the Constraint-Logic based Attack Searcher (CL-AtSe) model checking tool. The current version of the protocol guarantees mutual authentication of participants and forward secrecy of the keys in the presence of active adversaries. It also guarantees backward secrecy with active adversaries bounded by limited communication range, which is consistent with typical RFID environments. As for derived keys, we propose adapting the Solitaire cipher, as a Pseudo-random Number Generator. To complement our approach, an additional filter is added and described in the second part of this dissertation. We focus on the collection of tag information through the RFID middleware component. The middleware is a central point that sits between RFID readers and database applications. It is in charge of collecting, filtering and aggregating the requested events from heterogeneous RFID environments. Thus, the system at this point is likely to suffer from parameter manipulation and eavesdropping, raising privacy concerns. We propose a privacy-enhanced approach as a part of the RFID middleware of the EPCglobal network, which does not interfere with the standard interface. Our approach is policy driven using some enhanced contextual concepts of the extended Role Based Access Control model. We use specifically, the PrivOrBAC privacy-aware model to store and manage privacy preferences, taking the declared purpose, the accuracy and the explicit consent, as privacy requirements. To show the feasibility of our approach, we provide a proof-of-concept prototype that we apply to the Fosstrak plateform, an open-source implementation of the EPCglobal specifications.

The work presented in this document in an account of my work as a PhD student at LIX, Ecole Polytechnique, in the COMETE team under the supervision of Catuscia Palamidessi. During these studies, I have been in interested in the various aspects of concurrency covered by the COMETE team activities. The initial goal of my thesis was to investigate the aspects related to process calculi based formalisms to express and analyze Security Protocols. The ultimate goal was to makes some advances towards the automatic verification of security properties. In particular, I was interested in information-hiding protocols which require no cryptography, but normally use randomized mechanisms and therefore exhibit probabilistic behavior. Information hiding protocols are used typically in networks, and they are run by parties that reside in different locations of the system, and therefore interact asynchronously. The first work that I did was to try to give a correct meaning to the various notions of formal asynchronous communications used in various models, in particular between the field of concurrency and the field of distributed computing, where this was a recurrent question. These results are presented in the first part of this document. Being interested in the formal aspects of information-hiding problems, I took part in the preparation of the journal version of [BP09], and started preparing an automated probabilistic anonymity checker based on the formalism presented in this document. This lead to an initial draft of an implementation presented in http://vamp.gforge.inria.fr/. The formalism for this analysis is presented in the fourth part of this document. Another aspect of the verification of information hiding properties is that it requires to compute the probabilities of the possible outcomes for each scheduler. For this reason, this application quickly turned out to be highly inefficient. However, in an asynchronous system, a lot of transitions are confluent, which means that when evaluating a process, it is only necessary to choose one of the two confluent branches. Hence, I have worked on formalizing the possible optimizations based on the possible confluent computations. This work is presented in the second part of the document. Another interesting aspects of probabilistic protocols is the possibility to con- sider infinite runs. By doing such consideration, it is possible to verify the correction of some probabilistic protocols. For instance, in the case of the Crowds routing protocol, presented in Section 5.3, the protocol is considered correct because the probability of running into an infinite execution is null, hence the message will eventually be delivered. For this reason, I got interested in extending the meaning of a asynchronous probabilistic computations to the case of an infinite execution. As a matter of fact, the combination of infinite computation, confluence and probability is not easy to treat in the general case. The problem of confluence in concurrency is solved in an elegant way in an asyn- chronous paradigm called Concurrent Constraint Programming (CCP). Hence, I decided to study infinite computations in a probabilistic version of CCP. The problem, however, is that the meaning of the result of an infinite probabilistic computation was still an open problem also in that context. Hence, I studied a possible way to define this result, using the notion of valuations and sober spaces, and applied it to give a denotational semantics to probabilistic CCP, including infinite computations. This work is presented in the third part of the document. I have chosen a specific order for the various parts of this document that follows the various formal models that are used, in order to present each result along with the corresponding formalism. * In the first and second parts, I present the formal concurrent models, and in the particular asynchronous ones. * In the third part, I present the probabilistic CCP. This part also presents mathematic structures for the representation of infinite probabilistic executions. * Eventually, an application of both asynchronous and probabilistic models to the case of probabilistic information hiding is presented in the fourth part.

Les couplages sont des primitives cryptographiques qui interviennent désormais dans de nombreux protocoles. Dès lors, il est nécessaire de s'intéresser à leur calcul et à leur implémentation efficace. Pour ce faire, nous nous reposons sur une étude algorithmique et arithmétique de ces fonctions mathématiques. Les couplages sont des applications bilinéaires définies sur des courbes algébriques, plus particulièrement, dans le cas qui nous intéresse, des courbes elliptiques et hyperelliptiques. Nous avons choisi de nous concentrer sur une sous-famille de celles-ci : les courbes supersingulières dont les propriétés permettent d'obtenir à la fois des couplages symétriques et des algorithmes efficaces pour leur calcul. Nous décrivons alors une approche unifiée permettant d'établir une large variété d'algorithmes calculant des couplages. Nous l'appliquons notamment à la construc- tion d'un nouvel algorithme pour le calcul de couplages sur des courbes supersin- gulières de genre 2 et de caractéristique 2. Les calculs nécessaires aux couplages que nous décrivons s'appuient sur l'implé- mentation d'une arithmétique rapide pour les corps finis de petite caractéristique : la multiplication est l'opération critique qu'il convient d'optimiser. Nous présen- tons donc un algorithme de recherche exhaustive de formules de multiplication. Enfin, nous appliquons toutes les méthodes précédentes à la conception et l'im- plémentation de différents accélérateurs matériels pour le calcul de couplages sur différentes courbes dont les architectures ont été optimisées soit pour leur rapidité, soit pour leur compacité.

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.