CAnonize: A Compact Anonymous Survey Protocol
Authors: Marie Lonfils (UCLouvain), Olivier Pereira (UCLouvain), Thomas Peters (UCLouvain), Moti Yung (Google LLC, Columbia University)
Volume: 2026
Issue: 4
Pages: 396–414
DOI: https://doi.org/10.56553/popets-2026-0127
Artifact: Available, Functional, Reproduced
Abstract: Online surveys are frequently used to collect feedback on sensitive topics, yet most deployed platforms rely on authenticated accounts, cookies, or operator-enforced policies to protect anonymity and limit participation. These approaches offer limited protection against retrospective deanonymization in the event of database compromise. The anonymous survey primitive addresses this problem by enabling authenticated yet anonymous submissions with at-most-once participation per survey, without requiring a trusted setup. Current solutions may however be computationally demanding when aiming for large scale deployment. We revisit this primitive and present CAnonize, a new anonymous survey protocol that considerably improves the efficiency compared to the state of the art, while also relying on weaker computational assumptions and preserving a strong corruption model: our protocol relies solely on the SXDH assumption in asymmetric bilinear groups (q-type assumptions were used before), and offers unlinkability under adaptive corruption of the registration authority, survey authorities, and users, even under full transcript exposure and post-compromise database leakage. We confirm the efficiency benefits and practicality of CAnonize through a prototype implementation in Rust: using the BLS12-381 curves, the running times for submitting and processing a survey response are below 100ms for the user and for the survey authority.
Keywords: anonymous surveys, privacy enhancing technologies, pairing-based cryptography, Groth–Sahai proofs, structure-preserving signatures
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
