Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars profile

Fall 2015 Schedule
Winter 2016 Schedule

2013/06/04, MC103, 12 - 12:30

Verifiable Anonymous Polling
Giulia Alberini , PhD student, SOCS McGill

Area: Cryptography


We introduce a new framework for polling responses from a large population of humans. Our framework allows to gather 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 (a prerequisite for publicly verifiable voting systems).

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 human votes. Cross-certification is achieved using a newly introduced (privately verifiable) proof of "human effort" (PHE). The proof relies on expansion properties of the certification graph. In effect, our protocol can be thought of as a method for converting certain types of private-coin protocols into a publicly-verifiable protocol.

Our results are applicable to a variety of settings in which crowd-sourced information gathering is required. This includes political polling, recommendation systems, viewer voting in TV shows and prediction markets.