OPODIS 2009: Principles of Distributed Systems pp 144-158

# Decentralized Polling with Respectable Participants

• Rachid Guerraoui
• Kévin Huguenin
• Anne-Marie Kermarrec
• Maxime Monod
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 5923)

## Abstract

We consider the polling problem in a social network where participants care about their reputation: they do not want their vote to be disclosed nor their misbehaving, if any, to be publicly exposed. Assuming this reputation concern, we show that a simple secret sharing scheme, combined with verification procedures, can efficiently enable polling without the need for any central authority or heavyweight cryptography.

More specifically, we present DPol, a simple and scalable distributed polling protocol where misbehaving nodes are exposed with a non-zero probability and the probability of dishonest participants violating privacy is balanced with their impact on the accuracy of the polling result. The trade-off is captured by a generic parameter of the protocol, an integer k we call the privacy parameter, so that in a system of N nodes with $$B<\sqrt{N}$$ dishonest participants, the probability of disclosing a participant’s vote is bounded by (B/N)k + 1, whereas the impact on the polling result is bounded by (6k + 2) B.

We report on the deployment of DPolover 400 PlanetLab nodes. The polling result suffers a relative error of less than 10% in the face of message losses, crashes and asynchrony inherent in PlanetLab. In the presence of dishonest nodes, our experiments show that the impact on the polling result is (4k + 1) B on average, consistently lower that the theoretical bound of (6k + 2) B.

## Preview

### References

1. 1.
2. 2.
Benaloh, J.C.: Secret sharing homomorphisms: Keeping shares of a secret secret. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 251–260. Springer, Heidelberg (1987)Google Scholar
3. 3.
Castro, M., Liskov, B.: Practical Byzantine Fault Tolerance and Proactive Recovery. TOCS 20(4), 398–461 (2002)
4. 4.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Ruppert, E.: Secretive birds: Privacy in population protocols. In: Tovar, E., Tsigas, P., Fouchal, H. (eds.) OPODIS 2007. LNCS, vol. 4878, pp. 329–342. Springer, Heidelberg (2007)
5. 5.
Doodle: Easy Scheduling, http://www.doodle.com
6. 6.
Malkhi, D., Margo, O., Pavlov, E.: E-Voting without ‘Cryptography’. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 1–15. Springer, Heidelberg (2003)
7. 7.
Malkhi, D., Pavlov, E.: Anonymity without ‘Cryptography’. In: Syverson, P.F. (ed.) FC 2001. LNCS, vol. 2339, pp. 108–126. Springer, Heidelberg (2002)Google Scholar
8. 8.
Rabin, T., Ben-Or, M.: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority. In: STOC, pp. 73–85 (1989)Google Scholar
9. 9.
Richmond, R.: Facebook Tests the Power of Democracy, April 23 (2009)Google Scholar
10. 10.
Rivest, R., Shamir, A., Tauman, Y.: How to Share a Secret. CACM 22, 612–613 (1979)Google Scholar
11. 11.
Rivest, R., Smith, W.: Three Vvoting Protocols: ThreeBallot, VAV, and twin. In: EVT, p. 16 (2007)Google Scholar
12. 12.
13. 13.
Yu, H., Gibbons, P., Kaminsky, M., Xiao, F.: SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks. In: SP, pp. 3–17 (2008)Google Scholar

## Authors and Affiliations

• Rachid Guerraoui
• 1
• Kévin Huguenin
• 2
• Anne-Marie Kermarrec
• 3
• Maxime Monod
• 1
1. 1.EPFL
2. 2.Université de Rennes 1 / IRISA
3. 3.INRIA Rennes - Bretagne Atlantique
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7525094747543335, "perplexity": 19359.623601516396}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-43/segments/1508187824104.30/warc/CC-MAIN-20171020120608-20171020140608-00723.warc.gz"}