On the Polling Problem for Social Networks
Résumé
We tackle the polling problem in social networks where the privacy of exchanged information and user reputation are very critical. Indeed, users want to preserve the confidentiality of their votes and to hide, if any, their misbehaviors. Recent works \cite{DBLP:conf/opodis/GuerraouiHKM09,DBLP:journals/jpdc/GuerraouiHKMV12} proposed polling protocols based on simple secret sharing scheme and without requiring any central authority or cryptography system. But these protocols can be deployed safely provided that %a number of assumptions is satisfied: the social graph structure should be transformed into a ring-based structure and the number of participating users is perfect square. Accordingly, devising polling protocols regardless these constraints remains a challenging issue. In this work, we propose a simple decentralized polling protocol that relies on the current state of social graphs. More explicitly, we define one family of social graphs and show their structures constitute necessary and sufficient condition to ensure vote privacy and limit the impact of dishonest users on the accuracy of the output of the poll. In a system of $N$ users with $D\le N/5$ dishonest ones (and similarly to the works \cite{DBLP:conf/opodis/GuerraouiHKM09,DBLP:journals/jpdc/GuerraouiHKMV12} where they considered $D<\sqrt{N}$), a \textit{privacy parameter} $k$ enables us to obtain the following results: (i) the probability to recover one vote of honest node is bounded by $\sum_{m=k+1}^{2k}\bigl(\frac{D}{N}\bigr)^{m}.\bigl(\frac{1}{2}\bigr)^{2k+1-m} $; (ii) the maximum number of votes revealed by dishonest nodes is $2D$; and, (iii) the maximum impact on the output is \linebreak $(6k+4)D$. Despite the use of richer social graph structures, we succeed to detect the misbehaving users by manipulating verification procedures based on shortest path scheme and routing tables. An experimental evaluation demonstrates that the dishonest coalition never affects the outcome of the poll outside the theoretical bound of $(6k+4)D$.
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 $.
Origine : Fichiers produits par l'(les) auteur(s)