TY - GEN
AB - 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/2-\epsilon)n$ malicious nodes for any constant $1/2 > \epsilon > 0$ (not depending on $n$), and outputs the exact value of the aggregated function with high probability.
T1 - Scalable and Secure Aggregation in Distributed Networks
DA - 2011
AU - Gambs, Sebastien
AU - Guerraoui, Rachid
AU - Harkous, Hamza
AU - Huc, Florian
AU - Kermarrec, Anne-Marie
PB - CoRR
ID - 208765
UR - http://infoscience.epfl.ch/record/208765/files/scal_secur_aggreg_dn1107.5419v3.pdf
ER -