A secure ad-hoc survey scheme enables a survey authority to — without 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 those — and only those — users can anonymously complete exactly one submission. We present a formalization of secure ad-hoc surveys and a provably-secure (based on specific intractability assumptions in the Random Oracle Model) implementation, called ANONIZE. Our performance analysis shows that ANONIZE enables securely implementing million-person anonymous surveys using a single modern workstation. As far as we know, ANONIZE constitutes the first implementation of a large-scale anonymous survey system that scales to millions of users.