Scalable and Secure Polling in Dynamic Distributed Networks

We consider the problem of securely conducting a poll in synchronous dynamic networks equipped with a Public Key Infrastructure (PKI). Whereas previous distributed solutions had a communication cost of O(n^2) in an n nodes system, we present SPP (Secure and Private Polling), the first distributed polling protocol requiring 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 −ε)n Byzantine nodes for any constant 1/2 >ε > 0 (not depending on n), and outputs the exact value of the poll with high probability. SPP is composed of two sub-protocols, which we believe to be interesting on their own: SPP-Overlay maintains a structured overlay when nodes leave or join the network, and SPP-Computation conducts the actual poll. We validate the practicality of our approach through experimental evaluations and describe briefly two possible applications of SPP: (1) an optimal Byzantine Agreement protocol whose communication complexity is Θ(n log n) and (2) a protocol solving an open question of King and Saia in the context of aggregation functions, namely on the feasibility of performing multiparty secure aggregations with a communication complexity of o(n^2).

Presented at:
31st IEEE International Symposium on Reliable Distributed Systems, Irvine, California, October 8-11, 2012
Acceptance rate: 28/140= 20%

 Record created 2012-08-14, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)