Scalable and Secure Aggregation in Distributed Networks

Sebastien Gambs 1, 2 Rachid Guerraoui 3, 4 Hamza Harkous 3 Florian Huc 3 Anne-Marie Kermarrec 5
1 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique , CentraleSupélec
2 CIDER
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
5 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : 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.
Type de document :
Pré-publication, Document de travail
2011
Liste complète des métadonnées

https://hal.inria.fr/hal-00660056
Contributeur : Sébastien Gambs <>
Soumis le : dimanche 15 janvier 2012 - 15:22:22
Dernière modification le : vendredi 16 novembre 2018 - 01:39:32

Lien texte intégral

Identifiants

  • HAL Id : hal-00660056, version 1
  • ARXIV : 1107.5419

Citation

Sebastien Gambs, Rachid Guerraoui, Hamza Harkous, Florian Huc, Anne-Marie Kermarrec. Scalable and Secure Aggregation in Distributed Networks. 2011. 〈hal-00660056〉

Partager

Métriques

Consultations de la notice

1202