Information Theoretic Secure Aggregation with User Dropouts
  In the robust secure aggregation problem, a server wishes to learn and only
learn the sum of the inputs of a number of users while some users may drop out
(i.e., may not respond). The identity of the dropped users is not known a
priori and the server needs to securely recover the sum of the remaining
surviving users. We consider the following minimal two-round model of secure
aggregation. Over the first round, any set of no fewer than $U$ users out of
$K$ users respond to the server and the server wants to learn the sum of the
inputs of all responding users. The remaining users are viewed as dropped. Over
the second round, any set of no fewer than $U$ users of the surviving users
respond (i.e., dropouts are still possible over the second round) and from the
information obtained from the surviving users over the two rounds, the server
can decode the desired sum. The security constraint is that even if the server
colludes with any $T$ users and the messages from the dropped users are
received by the server (e.g., delayed packets), the server is not able to infer
any additional information beyond the sum in the information theoretic sense.
For this information theoretic secure aggregation problem, we characterize the
optimal communication cost. When $U \leq T$, secure aggregation is not
feasible, and when $U > T$, to securely compute one symbol of the sum, the
minimum number of symbols sent from each user to the server is $1$ over the
first round, and $1/(U-T)$ over the second round.
