Paper 2014/983

Public Verification of Private Effort

Giulia Alberini, Tal Moran, and Alon Rosen


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
pollinganonymityrandom graphspublic verifiabilityproof of workCAPTCHA
Contact author(s)
alon rosen @ idc ac il
2014-12-07: received
Short URL
Creative Commons Attribution


      author = {Giulia Alberini and Tal Moran and Alon Rosen},
      title = {Public Verification of Private Effort},
      howpublished = {Cryptology ePrint Archive, Paper 2014/983},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.