Decentralized polling with respectable participants

We consider the polling problem in a social network: participants express support for a given option and expect an outcome reflecting the opinion of the majority. Individuals in a social network care about their reputation: they do not want their vote to be disclosed or any potential misbehavior to be publicly exposed. We exploit this social aspect of users to model dishonest behavior, and show that a simple secret sharing scheme, combined with lightweight verification procedures, enables private and accurate polling without requiring any central authority or cryptography.We present DPol, a simple and scalable distributed polling protocol in which misbehaving nodes are exposed with positive probability and in which the probability of honest participants having their privacy violated is traded off against the impact of dishonest participants on the accuracy of the polling result. The trade-off is captured by a generic parameter of the protocol, an integer kk called the privacy parameter. In a system of NN nodes with BB dishonest participants, the probability of disclosing a participant’s vote is bounded by (B/N)k+1(B/N)k+1, whereas the impact on the score of each polling option is at most (3k+2)B(3k+2)B, with high probability when dishonest users are a minority (i.e., B

► Social network users’ concerns for reputations are an incentive to behave well.
► Verifications and secret sharing achieve accurate and private polling in social networks.
► Peer-to-peer architecture provides scalability while facilitating verifica- tions.