Scalable and Secure Aggregation in Distributed Networks

We consider the problem of computing an aggregation function in a \emph{secure} and \emph{scalable} way. Whereas previous distributed solutions with similar security guarantees have a communication cost of $O(n^3)$, we present a distributed protocol that requires only a communication complexity of $O(n{\log }^{3}n)$, which we prove is near-optimal. Our protocol ensures perfect security against a computationally-bounded adversary, tolerates $(1\mathrm{/}2-ϵ)n$ malicious nodes for any constant $1\mathrm{/}2>ϵ>0$ (not depending on $n$), and outputs the exact value of the aggregated function with high probability.