Achieving Privacy, Efficiency and Fault Tolerance in Aggregate Computations on Massive Star Networks

Abstract

This paper describes how Shamir secret sharing can be used for efficient fault-tolerant privacy preserving aggregation in a star topology, i.e., a massive number of participants connected to a single untrusted aggregator. The privacy constraints are that the participants do not discover each other’s data, and the aggregator obtains the final results while remaining oblivious to each participant’s individual contribution to the aggregate. In achieving these goals, previous work in this area has either assumed a trusted dealer that distributes keys to the participants and the aggregator, or a key authority that withholds the decryption key from the aggregator, or secret sharing by the participants that either requires pairwise communication amongst the participants or incurs $O(N^2)$ ciphertext computation at the aggregator. In contrast, we develop a protocol based on secret sharing and homomorphic encryption that eliminates the need for a trusted dealer or a key authority. We also eliminate all pairwise communication amongst the participants and still require overhead that is significantly less than quadratic in the number of participants. Our protocol arranges the participants in a hierarchy that enables easy parallelization, while allowing for user churn, i.e., a limited number of participants can go offline after providing their data, and new participants can join at a later stage of the computation.