eCommons

 

Secure Distributed Computation in the Presence of Dynamic Participation

Other Titles

Author(s)

Abstract

Distributed 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.

Journal / Series

Volume & Issue

Description

163 pages

Sponsorship

Date Issued

2022-08

Publisher

Keywords

distributed computation; distributed consensus; federated learning; secure aggregation; security; timing model

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Shi, Runting

Committee Co-Chair

Committee Member

Pass, Rafael N.
Myers, Andrew C.

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record