  Federated learning enables users to collaboratively train a machine learning
model over their private datasets. Secure aggregation protocols are employed to
mitigate information leakage about the local datasets. This setup, however,
still leaks the participation of a user in a training iteration, which can also
be sensitive. Protecting user anonymity is even more challenging in dynamic
environments where users may (re)join or leave the training process at any
point of time. In this paper, we introduce AnoFel, the first framework to
support private and anonymous dynamic participation in federated learning.
AnoFel leverages several cryptographic primitives, the concept of anonymity
sets, differential privacy, and a public bulletin board to support anonymous
user registration, as well as unlinkable and confidential model updates
submission. Additionally, our system allows dynamic participation, where users
can join or leave at any time, without needing any recovery protocol or
interaction. To assess security, we formalize a notion for privacy and
anonymity in federated learning, and formally prove that AnoFel satisfies this
notion. To the best of our knowledge, our system is the first solution with
provable anonymity guarantees. To assess efficiency, we provide a concrete
implementation of AnoFel, and conduct experiments showing its ability to
support learning applications scaling to a large number of clients. For an
MNIST classification task with 512 clients, the client setup takes less than 3
sec, and a training iteration can be finished in 3.2 sec. We also compare our
system with prior work and demonstrate its practicality for contemporary
learning tasks.
