ANONIZE: A Large-Scale Anonymous Survey System – Susan Hohenberger Johns Hopkins University; Steven Myers Indiana University; abhi shelat University of Virginia; Rafael Pass Cornell University.
“A secure ad-hoc survey scheme enables a survey authority to independently (with- out any interaction) select an ad-hoc group of registered users based only on their identities (e.g., their email addresses), and create a survey where only selected users can anonymously submit exactly one response. We present a formalization of secure ad-hoc surveys and present:
• an abstract provably-secure implementation based on standard cryptographic building blocks (which in particular are implied by the existence of enhanced trapdoor permutations in the CRS model);
• a practical instantiation of our abstract protocol, called anonize, which is provably- secure in the random oracle model based on cryptographic assumptions on groups with bilinear maps.
As far as we know, ANONIZE constitutes the first implementation of a large-scale secure computation protocol (of non-trivial functionalities) that can scale to millions of users…

We study the basic conflict between anonymity and authenticity in large network set- tings. Companies, universities, health providers and government agencies routinely con- duct asynchronous and real-time data collection surveys for targeted groups of users over the Internet. To do so, they aim for authenticity (i.e., ensuring that only the legitimate users can participate in the data collections) and anonymity (i.e., ensuring that the there is no link between the legitimate user and his/her data so that users are more likely to submit honest feedback). The intrinsic conflict between these two goals may result in users self-censoring or purposely biasing data they submit.
A simple example is a course evaluation for a university class. A typical implementation of such a survey requires a trusted third party (such as the university or some external party) to ensure that feedback is collected anonymously from the participants and that only authorized participants, i.e., the students enrolled in a particular class, can submit feedback for that class. In such trusted-party implementations, students are required to authenticate themselves with their university IDs and thus leave a link be- tween their evaluation and their identity; they are trusting the survey collector to keep such links private.”