We propose an ``effort based'' polling protocol whose results can be publicly verified by constructing a ``responder certification graph'' whose nodes are labeled by responders' replies to the poll, and whose edges cross-certify that adjacent nodes correspond to honest participants. Cross-certification is achieved using a newly introduced (privately verifiable) ``Private Proof of Effort'' (PPE). In effect, our protocol gives a general method for converting privately-verifiable proofs into a publicly-verifiable protocol. The soundness of the transformation relies on expansion properties of the certification graph.
Our results are applicable to a variety of settings in which crowd-sourced information gathering is required. This includes crypto-currencies, political polling, elections, recommendation systems, viewer voting in TV shows, and prediction markets.Category / Keywords: cryptographic protocols / polling, anonymity, random graphs, public verifiability, proof of work, CAPTCHA Date: received 6 Dec 2014 Contact author: alon rosen at idc ac il Available format(s): PDF | BibTeX Citation Version: 20141207:153438 (All versions of this report) Short URL: ia.cr/2014/983 Discussion forum: Show discussion | Start new discussion