On the Polling Problem for Social Networks

Hoang Bao Thien 1 Abdessamad Imine 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Résumé : Nous abordons le probléme de sondage dans les réseaux sociaux oú le caractére secret des informations échangées et la réputation de l'utilisateur sont trés critiques. En effet, les utilisateurs désirent préserver la confidentialité de leur vote et dissimuler, le cas échéant, leurs mauvais comportements. Des travaux récents~\cite{DBLP:conf/opodis/GuerraouiHKM09,DBLP:journals/jpdc/GuerraouiHKMV12} ont proposé des protocoles de sondage basés sur la partage de secret et nécessitant aucune infrastructure cryptographique. Néanmoins, ces protocoles ne sont applicables que si le graphe social a une structure d'anneau et le nombre d'utilisateurs est un carré parfait. En conséquence, l'élaboration de protocoles de sondage indépendamment de ces contraintes reste un probléme ouvert. Dans ce rapport, nous proposons un protocole décentralisé de sondage qui s'appuie sur l'état réel des graphes sociaux. Plus précisément, nous définissons une famille de graphes et montrons que leurs structures constituent la condition nécessaire et suffisante pour assurer la confidentialité du vote et limiter l'impact des utilisateurs malhonnêtes sur la précision de la sortie du scrutin. Dans un systéme de $N$ utilisateurs, tel que $D\le N/5$ sont malhonnêtes (et similairement aux travaux~\cite{DBLP:conf/opodis/GuerraouiHKM09,DBLP:journals/jpdc/GuerraouiHKMV12} qui se limitaient á $D<\sqrt{N}$)), un paramétre de confidentialité $k$ nous permet d'obtenir les résultats suivants : (i) la probabilité de récupérer la voix d'un noeud honnête est bornée par $\sum_{m=k+1}^{2k}\bigl(\frac{D}{N}\bigr)^{m}.\bigl(\frac{1}{2}\bigr)^{2k+1-m}$ ; (ii) le nombre maximum de votes révélés par des n{\oe}uds malhonnêtes est de $2D $ ; et, (iii) l'impact maximum sur la sortie est $(6k +4) D $. Malgré l'utilisation de riches structures de graphes sociaux, nous sommes parvenus á détecter les comportements des utilisateurs malhonnêtes en manipulant des procédures de vérification s'appuyant sur le calcul du plus court chemin et des tables de routage. Une évaluation expérimentale montre que l'influence de la coalition d'utilisateurs malhonnêtes sur le résultat du scrutin ne dépassera pas la borne théorique de $ (6k +4) D $.
Type de document :
Rapport
[Research Report] RR-8055, INRIA. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00727599
Contributeur : Hoang Bao Thien <>
Soumis le : lundi 1 octobre 2012 - 13:20:03
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 18:36:18

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00727599, version 2

Citation

Hoang Bao Thien, Abdessamad Imine. On the Polling Problem for Social Networks. [Research Report] RR-8055, INRIA. 2012. 〈hal-00727599v2〉

Partager

Métriques

Consultations de la notice

420

Téléchargements de fichiers

564