You are looking at a specific version 20141207:153438 of this paper. See the latest version.

Paper 2014/983

Public Verification of Private Effort

Giulia Alberini and Tal Moran and Alon Rosen

Abstract

We introduce a new framework for polling responses from a large population. Our framework allows gathering information without violating the responders' anonymity and at the same time enables public verification of the poll's result. In contrast to prior approaches to the problem, we do not require trusting the pollster for faithfully announcing the poll's results, nor do we rely on strong identity verification. 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
pollinganonymityrandom graphspublic verifiabilityproof of workCAPTCHA
Contact author(s)
alon rosen @ idc ac il
History
2014-12-07: received
Short URL
https://ia.cr/2014/983
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.