The Fundamental Price of Secure Aggregation in Differentially Private
  Federated Learning
  We consider the problem of training a $d$ dimensional model with distributed
differential privacy (DP) where secure aggregation (SecAgg) is used to ensure
that the server only sees the noisy sum of $n$ model updates in every training
round. Taking into account the constraints imposed by SecAgg, we characterize
the fundamental communication cost required to obtain the best accuracy
achievable under $\varepsilon$ central DP (i.e. under a fully trusted server
and no communication constraints). Our results show that $\tilde{O}\left(
\min(n^2\varepsilon^2, d) \right)$ bits per client are both sufficient and
necessary, and this fundamental limit can be achieved by a linear scheme based
on sparse random projections. This provides a significant improvement relative
to state-of-the-art SecAgg distributed DP schemes which use
$\tilde{O}(d\log(d/\varepsilon^2))$ bits per client.
  Empirically, we evaluate our proposed scheme on real-world federated learning
tasks. We find that our theoretical analysis is well matched in practice. In
particular, we show that we can reduce the communication cost significantly to
under $1.2$ bits per parameter in realistic privacy settings without decreasing
test-time performance. Our work hence theoretically and empirically specifies
the fundamental price of using SecAgg.
