Tail-Hammer: Optimized Statistics for Anonymous Committees and Applications

---

Authors: B. David, L. Lavagnino, E. Pagnin, and P. Stankovski-Wagner
In: 15th International Conference on Security and Cryptography for Networks, 2026
Full Text:

---

Abstract

Techniques to randomly select sets of anonymous parties are ubiquitous in efficient and adaptively secure consensus protocols, as well as in Multi-Party Computation in the YOSO model, where each round is executed by a different random anonymous committee. Anonymous committee selection aims at randomly selecting a set of n parties (the committee), where at most t parties are corrupted (except with negligible probability), drawing from a population of $N ≫ n$ parties with at most $T$ corrupted parties. Additionally, each party knows (and can prove) if they belong to the committee, but ignores other members’ identities. A very common and efficient instantiation of anonymous committee selection is to select parties according to a VRF output, this however, leads to committees of probabilistic size ($n$ behaves as a Binomial random variable). Despite wide adoption, only [7] (Blum et al., CCS23) provides an analysis of VRF-based probabilistic anonymous committee selection that estimates the size of committees. This analysis relies on lose bounds (Chernoff) and approximations (Poisson). In this work, we revisit Blum et al.’s estimates and derive accurate closed-form formulas (based on a tight Binomial approximation), as well as an efficient high-precision library called Tail-Hammer for computing exact parameters. Notably, Tail-Hammer identifies smaller committee sizes (approximately -25% on average) than [7] for the same security level, leading to improved efficiency in protocols relying on random committee selection, also when anonymity is not needed. Our analysis applies to committee selection techniques that employ unbiased (uniformly random), or bounded-bias randomness, to both synchronous and asynchronous communication settings, and it can account for inactive parties. As a new application, we present a verifiable consistent broadcast protocol that leverages quorums in anonymous committees to achieve efficiency without requiring threshold signatures.

Keywords: Privacy, Accountability, Universal Composability, Anonymous Credentials.