Multivalued and Deterministic Peer-to-Peer Polling in Social Networks with Reputation Conscious Participants

摘要

We study the polling problem in a social network and present a private and precise n-ary voting protocol. We assume that members are concerned about their reputation in the sense that they do not want their votes to be disclosed and their potentially malicious actions to become public. Our protocol neither requires a central authority, strong cryptography, nor a randomization mechanism, using a simple secret sharing scheme and verification procedures to accurately determine the result of each poll. Our scalable protocol expands on the binary polling protocol by Guerraoui, Huguenin, Kermarrec and Monod and enables deterministic n-ary voting without significantly increasing the complexity of the protocol while preserving optimal voter privacy, allowing nodes to abstain from a poll--assuming honest nodes--and tabulating exact poll results. Misbehaving nodes are exposed with a non-zero probability and the probability of dishonest members violating voter privacy is balanced by their impact on the accuracy of the result. Limiting the number of dishonest nodes (B) such that they do not constitute a majority in any two consecutive groups of nodes and using a privacy parameter k, the impact of colluding malicious nodes is bounded by (2nk-k+1)B for any one element of the global tally and significantly less for all successive elements. Further, our algorithm improves on prior algorithms and ensures that voter privacy is optimally protected and that in the worst case, a node's vote is only compromised with probability (Bi/nk+1)k+1.