Secure Distributed Computation in the Presence of Dynamic Participation

dc.contributor.authorGuo, Yue
dc.contributor.chairShi, Runting
dc.contributor.committeeMemberPass, Rafael N.
dc.contributor.committeeMemberMyers, Andrew C.
dc.description163 pages
dc.description.abstractDistributed computing applications are booming in the Internet era as they enable mutually distrusting parties to collaborate and achieve a common goal. One of the major challenges in designing distributed computation protocols is to make progress and provide security guarantees while participants might not be always online. This work explores the solutions of secure distributed computation in the presence of dynamic participation and includes two main results. First, we propose a new timing model, weak synchrony, which combines the advantages of classical synchronous and partially synchronous model. Second, we provide a new secure aggregation protocol, MicroFedML, which improves on the performance of the state-of-the-art work while providing the same level of security guarantee and also supporting rejoining of temporarily offline participants.The synchronous timing model is broadly applied in both theoretical designs and practical applications due to its robustness properties. In the synchronous model, it is assumed that messages between honest participants are delivered within a bounded delay ∆ which is a parameter known to the protocol. This assumption allows protocols to be resilient against less than 1/2 malicious participants. However, it also has a drawback that if an honest node ever experiences a short outage during which it is not able to receive honest messages within delay ∆, this node is considered to be corrupted and the protocol does not provide any consistency or liveness guarantee for it from that point on. As an alternative, the partially synchronous model assumes the existence but not the knowledge of an upper bound of message delivery time between honest nodes, allowing the temporary offline period to be regarded as a long message delay. Unfortunately, protocols in the partially synchronous model cannot achieve the same level of malicious resiliency as in the synchronous model, as the well-known result shows that the resiliency upper bound of the partially synchronous model is only 1/3. In our work, we propose a new timing model, χ-weak-synchrony, which quantifies the network status more accurately and combines the advantages of both of the traditional timing models. It assumes a known upper bound ∆ on message delivery time between honest and online participants. As long as there are more than χ-fraction of participants being honest and online in each round, a protocol in this model guarantees both liveness and consensus for all honest participants. We give constructions of a consensus protocol and an MPC protocol in the 1/2-weakly synchronous model and a lower-bound result showing that the threshold 1/2 is optimal. Next, from a practical perspective, we discuss supporting dynamic participation in secure aggregation. Secure aggregation is a technique that allows a set of users to compute the aggregation of their private data with the aid of an entrusted server. It provides strong privacy guarantees and has been well-studied in the context of privacy-preserving federated learning. An important problem in privacy-preserving federated learning with constrained computation and wireless network resources is the computation and communication overhead which wastes bandwidth, increases training time, and can even affect model accuracy if many users drop out due to high cost. The seminal work of Bonawitz et al. and the work of Bell et al. have constructed secure aggregation protocols for a very large number of users which handle dropout users in a federated learning setting. However, these works suffer from high round complexity (defined as the number of times that users exchange messages with the server) and overhead in every training iteration. In this work, we propose and implement MicroFedML, a new secure aggregation scheme with lower round complexity and computation overhead than existing works which achieve the same level of security. It uses a relaxation of the synchronous model which assumes a known upper bound on round time while allowing users to drop offline at any time point and come back online in later iterations. MicroFedML reduces the computational burden by at least 100 times for 500 users (or more depending on the number of users) and the message size by 50 times compared to prior work. Our system performs best when the input domain is not too large. Notable use cases include gradient sparsification, quantization, and weight regularization in federated learning.
dc.subjectdistributed computation
dc.subjectdistributed consensus
dc.subjectfederated learning
dc.subjectsecure aggregation
dc.subjecttiming model
dc.titleSecure Distributed Computation in the Presence of Dynamic Participation
dc.typedissertation or thesis
dcterms.license Science University of Philosophy D., Computer Science


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1012.53 KB
Adobe Portable Document Format