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, Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : 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 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 paper, 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 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$.
Type de document :
Communication dans un congrès
Baldoni, Roberto and Flocchini, Paola and Binoy, Ravindran. International Conference On Principles Of DIstributed Systems (OPODIS), Dec 2012, Rome, Italy. Springer, 7702, 2012, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/hal-00759889
Contributeur : Abdessamad Imine <>
Soumis le : lundi 3 décembre 2012 - 10:18:16
Dernière modification le : jeudi 15 février 2018 - 08:48:14

Identifiants

  • HAL Id : hal-00759889, version 1

Citation

Hoang Bao Thien, Abdessamad Imine. On the Polling Problem for Social Networks. Baldoni, Roberto and Flocchini, Paola and Binoy, Ravindran. International Conference On Principles Of DIstributed Systems (OPODIS), Dec 2012, Rome, Italy. Springer, 7702, 2012, Lecture Notes in Computer Science. 〈hal-00759889〉

Partager

Métriques

Consultations de la notice

197