Skip to Main content Skip to Navigation
New interface
Conference papers

Efficient and Decentralized Polling Protocol for General Social Networks

Hoang Bao Thien 1 Abdessamad Imine 2 
2 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
Abstract : We address the polling problem in social networks where users want to preserve the confidentiality of their votes, obtain the correct final result, and hide, if any, their misbehaviors. Guerraoui et al. [15, 16] recently proposed polling protocols that neither rely on any central authority nor cryptography system. However, these protocols can be deployed safely and efficiently provided that the social graph structure should be transformed into a ring structure-based overlay and the number of participating users is a perfect square. Consequently, designing secure and efficient polling protocols regardless these constraints remains a challenging issue. In this paper, we present EPol, a simple decentralized polling protocol that is deployed on more general social graphs. More explicitly, we define a family of social graphs that satisfy what we call the m-broadcasting property (where m is not greater than the minimum node degree) and show their structures enable low communication cost and constitute necessary and sufficient condition to ensure vote privacy and limit the impact of dishonest users on the accuracy of the polling output. EPol is effective to compute more precisely the final result and the communication and spatial complexities are close to be linear.
Complete list of metadata
Contributor : Abdessamad Imine Connect in order to contact the contributor
Submitted on : Thursday, December 10, 2015 - 11:08:46 AM
Last modification on : Friday, January 21, 2022 - 3:08:55 AM



Hoang Bao Thien, Abdessamad Imine. Efficient and Decentralized Polling Protocol for General Social Networks. SSS 2015 - 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Aug 2015, Edmonton, Canada. pp.171-186, ⟨10.1007/978-3-319-21741-3_12⟩. ⟨hal-01241241⟩



Record views