1. Problème de Sondage dans les Réseaux Sociaux Décentralisés
- Author
-
Hoang, Bao Thien, Combination of approaches to the security of infinite states systems (CASSIS), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)-Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), INRIA CORDI/CASSIS team, ANR Streams project, LORIA/Université de Lorraine, Université de Lorraine, Abdessamad Imine, Christophe Ringeissen, CASSIS - INRIA Nancy, ANR-10-SEGI-0010,STREAMS,Solutions pair-à-pair pour le Web social temps-réel(2010), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Protocole de sondage ,Adding friends ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Réseaux sociaux ,Partage de secret ,Algorithmes centralisé et décentralisé ,Vie privée ,Centralized and decentralized algorithms ,Social networks ,[INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI] ,[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] ,Polling protocol ,Privacy ,Problème d’édition dans les graphes ,Graph editing ,Ajout de contacts ,Secret sharing - Abstract
One of the current practical, useful but sensitive topic in social networks is polling problemwhere the privacy of exchanged information and user reputation are very critical. Indeed, userswant to preserve the confidentiality of their votes and to hide, if any, their misbehaviors. Recently,Guerraoui et al. proposed polling protocols based on simple secret sharing scheme and withoutrequiring any central authority or cryptography system. However these protocols can be deployedsafely and efficiently provided that the social graph structure should be transformed into a ringstructure-based overlay and the number of participating users is perfect square. In this thesis,we address the problem of deploying decentralized polling protocols for general social graphsand how to transform these graphs in order to increase the privacy and/or accuracy properties.First, we propose three simple decentralized polling protocols that rely on the current state ofsocial graphs. The two first protocols use synchronous and asynchronous models and verificationprocedures to detect the misbehaving users. The third protocol is an asynchronous one thatdoes not require any verification procedures and contains a method for efficiently broadcastingmessage under a family of social graphs satisfying what we call the m-broadcasting property.Second, we formalize the “adding friends” problem such that we can reuse the social graphs aftersome minimum structural modifications consisting in adding new friendship relations. We alsodevise algorithms for solving this problem in centralized and decentralized networks. We validateour solutions with some performance evaluations which show that our protocols are accurate,and inside the theoretical bounds.; Un des thèmes pratiques, mais hautement sensibles, est le problème de sondage dans les réseauxso ciaux où le caractère secret des informations sélectionnées et la réputation de l’utilisateur sonttrès critiques. En effet, les utilisateurs désirent préserver la confidentialité de leurs votes et dissimuler, le cas échéant, leurs mauvais comp ortements. Récemment, Guerraoui et al. ont proposédes protocoles de sondage basés sur la partage de secret et ne nécessitant aucune infrastructure cryptographique. Néanmoins, ces protocoles ne sont applicables que si le graphe social aune structure d’anneau et le nombre d’utilisateurs est un carré parfait. Dans cette thèse, noustraitons, d’une part, du problème du déploiement décentralisé des protocoles de sondage qui sontbasés sur des graphes sociaux ayant des structures générales, et d’autre part, du problème detransformation des graphes sociaux pour augmenter les propriétés de vie privée et de précision,nécessaires au déroulement sûr et rentable du sondage décentralisé. Premièrement, nous proposons trois protocoles décentralisés qui s’appuient sur l’état originel (sans transformation) desgraphes sociaux. Les deux premiers protocoles utilisent respectivement des modèles de communication synchrone et asynchrone, et manipulent des procédures de vérification pour détecter lesutilisateurs malhonnêtes. Quant au troisième protocole, il est asynchrone et ne nécessite pasde procédures de vérification. Pour que ce protocole permette une diffusion efficace de messages, nous avons défini une propriété sur les graphes sociaux, appelée “ m-broadcasting”. Dansla deuxième partie de la thèse, nous formalisons le problème de “l’ajout des amis” qui consiste àtrouver une transformation optimale des graphes sociaux pour les adapter au partage de secret.Pour résoudre ce problème, nous présentons deux algorithmes selon deux approches différentes:centralisée et décentralisée. Une évaluation expérimentale montre que nos protocoles sont préciset restreints aux bornes théoriques.
- Published
- 2015