PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication-Computation Efficient Secure Aggregation for Federated Learning

Beongjun Choi, Jy-yong Sohn, Dong-Jun Han, Jaekyun Moon

arXiv:2012.05433v3cs.LGcs.CRcs.ITmath.IT

TL;DR

Federated learning can expose private data through transmitted model parameters, while secure aggregation protects privacy at high communication and computation cost. This paper proposes a sparse-graph secure aggregation scheme with graph conditions and an Erdős–Rényi design. The authors report comparable reliability and privacy using 20–30% of conventional secure aggregation’s resources in real-dataset experiments.

  • Problem

    Transmitted federated-learning models can reveal local data, while secure aggregation protects privacy at communication and computation costs that grow quadratically with client count.

    Source: §1 · p. 1, §3 · p. 4

  • Method

    CCESA uses a sparse assignment graph for selective secret sharing and establishes graph conditions for reliability and privacy, including an Erdős–Rényi design.

    Source: §1 · pp. 1–2, §4.3 · p. 7

  • Results

    20–30% of conventional secure aggregation’s resources achieve the same reported reliability and privacy levels in experiments on real datasets.

    Source: §6 · p. 10

  • Takeaways & Limitations

    CCESA offers a resource-efficient secure aggregation approach that preserves reported privacy and reliability in the evaluated federated-learning settings.

    Source: §6 · p. 10

    The privacy analysis assumes a trusted server and participating clients, with an eavesdropper able to access transmitted information.

    Source: §4.1 · p. 6

Abstract

from arXiv · show

Federated learning has been spotlighted as a way to train neural networks using distributed data with no need for individual nodes to share data. Unfortunately, it has also been shown that adversaries may be able to extract local data contents off model parameters transmitted during federated learning. A recent solution based on the secure aggregation primitive enabled privacy-preserving federated learning, but at the expense of significant extra communication/computational resources. In this paper, we propose a low-complexity scheme that provides data privacy using substantially reduced communication/computational resources relative to the existing secure solution. The key idea behind the suggested scheme is to design the topology of secret-sharing nodes as a sparse random graph instead of the complete graph corresponding to the existing solution. We first obtain the necessary and sufficient condition on the graph to guarantee both reliability and privacy. We then suggest using the Erd\H{o}s-R\'enyi graph in particular and provide theoretical guarantees on the reliability/privacy of the proposed scheme. Through extensive real-world experiments, we demonstrate that our scheme, using only $20 \sim 30\%$ of the resources required in the conventional scheme, maintains virtually the same levels of reliability and data privacy in practical federated learning systems.

1 INTRODUCTION

Federated learning can expose private training data through transmitted model updates, while secure aggregation protects privacy at substantial communication and computation cost. The paper proposes CCESA, which uses selective secret sharing to reduce those costs while targeting comparable privacy and reliability.

Motivation and related work

  • Model updates can reveal local training data, and secure aggregation addresses this risk but incurs communication and computation burdens that grow quadratically with client count.Differential-privacy approaches instead add noise and generally trade privacy against global-model convergence.Source: §1 · pp. 1–2

Experiments

  • Figure 2 reports that model inversion reveals the training image under unprotected federated averaging, but not under CCESA or secure aggregation.The figure caption states that CCESA requires 40% of secure aggregation’s communication/computational resources in this example.Source: Figure 2 · p. 2

Contributions

  • CCESA replaces the complete sharing topology with a low-degree graph and gives necessary and sufficient graph conditions for reliable, private aggregation.It also proposes an Erdős–Rényi graph design; the authors report theoretical guarantees and real-dataset experiments.Source: §1 · pp. 1–2

Related work

  • Secure multiparty computation protects privacy but can incur high communication burdens, while differential privacy adds noise to models or gradients.The related work describes differential-privacy methods as generally trading privacy level against global-model convergence.Source: §1 · p. 2
  • 3% of Turbo-aggregate’s communication bandwidth is required by CCESA in the stated scenario: m = 106, R = 32, n = 100, L = 10, and aK = aS = 256.Turbo-aggregate is described as using a circular aggregation topology; the comparison concerns communication bandwidth.Source: §1 · pp. 2–3

2 BACKGROUND

The background describes federated learning’s client-server update process and the cryptographic tools used by secure aggregation. In secure aggregation, clients mask local models and the server reconstructs the aggregate rather than individual models.

Federated learning

  • Each federated-learning round selects clients, sends them the current global model, and aggregates their locally updated models at the server.The server selects a set of cn clients, where 0 < c ≤ 1.Source: §2 · p. 3

Cryptographic primitives

  • Shamir’s t-out-of-n secret sharing lets any t shares reconstruct a secret, while t−1 shares provide no information about it.Diffie-Hellman key agreement produces a secret shared by two clients, and authenticated encryption protects message integrity.Source: §2 · p. 3

Secure aggregation

  • Secure aggregation uses secret sharing, key agreement, and authenticated encryption to protect privacy while the server obtains the sum of clients’ local models.Its protocol has four steps: advertise keys, share keys, collect masked inputs, and unmask.Source: §2 · p. 3
  • In secure aggregation, clients mask their local models using pseudorandom values and pairwise secrets; the server reconstructs needed secrets from shares to obtain the model sum.The server collects masked models and uses the surviving clients’ responses during unmasking.Source: §2 · p. 4

3 SUGGESTED ALGORITHM

CCESA reduces secure-aggregation communication and computation by having clients exchange public keys and secret shares only with selected peers. Its assignment graph specifies these peer relationships, and the protocol adapts secret sharing and unmasking to that graph.

3 SUGGESTED ALGORITHM

  • Secure aggregation’s communication and computation resources grow quadratically with client count because each client receives information from every other client.CCESA’s subset-based exchange targets this overhead while maintaining reliability and privacy.Source: §3 · p. 4
  • Each client exchanges public keys and secret shares only with adjacent clients in the assignment graph, rather than with every other client.This reduces communication, secret-share and pseudorandom-value generation, and key-agreement work compared with conventional secure aggregation.Source: §3 · p. 4
  • The assignment graph’s edges specify which client pairs exchange public keys and secret shares; a complete graph makes CCESA equivalent to secure aggregation.The graph evolves across protocol steps as clients drop out.Source: §3 · pp. 4, 6
  • CCESA sends public keys to adjacent clients and applies t_i-out-of-(|Adj(i)| + 1) secret sharing to each client’s secrets.During unmasking, clients return shares and the server reconstructs secrets needed to aggregate masked local models.Source: §3 · pp. 4, 6
  • With five clients, client 1 exchanges data with two peers under CCESA instead of four under conventional secure aggregation, requiring half the bandwidth in the example.The reduced number of shares, pseudorandom values, and key agreements also lowers computation.Source: §3 · p. 6

4 THEORETICAL ANALYSIS

The analysis gives graph conditions for reliable and private aggregation, then applies them to Erdős–Rényi assignment graphs. Above the threshold p*, the scheme is asymptotically reliable and private, with finite-size error bounds and lower resource requirements than conventional secure aggregation.

4.1 PERFORMANCE METRICS

  • The analysis defines reliability as the server recovering the surviving clients’ model sum and privacy as concealing proper-subset sums from an eavesdropper.It assumes the server and participating clients are trusted; the eavesdropper may access information transmitted during the protocol.Source: §4.1 · p. 6

4.2 RESULTS FOR GENERAL ASSIGNMENT GRAPH G

  • Reliability holds if and only if every node in V3+ is informative, meaning it has at least t_i surviving adjacent shares.V3+ comprises V3 and its neighborhoods within V2.Source: §4.2 · p. 7
  • Privacy holds if and only if the assignment graph belongs to GC or GNI; connectivity of G3 is a sufficient privacy condition.The connected-graph argument relies on an inaccessible shared secret across any partition of surviving clients.Source: §4.2 · p. 7

4.3 RESULTS FOR ERD ˝OS-R´ENYI ASSIGNMENT GRAPH G

  • For CCESA on an Erdős–Rényi graph, each edge is independently included with probability p, and clients independently drop out at each protocol step.The analysis uses a common secret-sharing parameter t for all clients.Source: §4.3 · p. 7

4.3.1 FOR ASYMPTOTICALLY LARGE n

  • When p > p*, CCESA is asymptotically almost surely reliable and private, and p* decreases with n.The analysis gives separate lower bounds on p for reliability and privacy; the threshold’s decline with n implies improved scalability.Source: §4.3.1 · p. 8
  • CCESA’s additional bandwidth scales as O(√n log n), compared with O(n) for SA, and its computational burden falls by at least a factor of O(√n/log n).The paper attributes the computational reduction to fewer secret shares, pseudo-random values, and key agreements.Source: §4.3.1 · p. 8

4.3.2 FOR FINITE n

  • For finite n and p > p*, the privacy error bound is below 10^-40, while the reliability error bound is below 10^-2.A round flagged as unreliable may retain the previous global model; the paper reports that this does not harm accuracy in its experiments.Source: §4.3.2 · p. 8, Figure 4.1 · p. 9

5 EXPERIMENTS

Experiments compare CCESA with secure aggregation on face and CIFAR-10 datasets, evaluating running time, reliability, and privacy. CCESA reduces running time and communication/computation while achieving comparable model accuracy and resisting the reported privacy attacks.

5 EXPERIMENTS

  • The experiments compared running time, reliability, and privacy on the AT&T face and CIFAR-10 datasets.For the AT&T face experiment, 40 clients trained using their own images.Source: §5 · p. 9

5.1 RUNNING TIME

  • CCESA required p times less running time than SA across tested n and qtotal settings.The paper attributes this to generating fewer secret shares and pseudo-random values and performing fewer key agreements.Source: §5.1 · p. 9
  • At p = 0.25, CCESA matched SA’s test accuracy in both i.i.d. and non-i.i.d. CIFAR-10 settings after 200 rounds, using 25% of the resources.With p = 0.3106, the provably minimum connection probability, it also achieved SA’s performance in both settings.Source: §5.1 · p. 9, Figure 5.2 · p. 10

5.3 PRIVACY

  • In model inversion tests, vanilla federated averaging revealed face characteristics, while SA and CCESA revealed no clue about the client’s face.For CIFAR-10 membership inference, attack accuracy was near 70% for federated averaging and near 50% for SA and CCESA.Source: §5.3 · p. 10

6 CONCLUSION

CCESA preserves federated learning reliability and privacy while reducing communication and computation compared with conventional secure aggregation.

6 CONCLUSION

  • CCESA uses only 20–30% of conventional secure aggregation resources while maintaining the same levels of reliability and privacy in real-dataset experiments.The paper also reports a graph-theoretic resource reduction of at least a factor of sqrt(n/log n).Source: §6 · p. 10

A ADDITIONAL EXPERIMENTAL RESULTS

On the AT&T Face dataset, CCESA’s reliability approaches that of secure aggregation as connection probability increases. At p = 0.7, it achieves secure aggregation’s test accuracy using 70% of its resources.

A.1 RELIABILITY

  • 70% of conventional resources sufficed for CCESA to match secure aggregation’s test accuracy on AT&T Face with n = 40 and t = 21.The experiment trained for 50 rounds; p = 0.7 sufficed in both qtotal settings, and resource use is proportional to np.Source: §A.1 · p. 11, Figure A.3 · p. 11

A.2 PRIVACY

The experiments report that CCESA preserves privacy against model inversion and membership inference attacks, matching secure aggregation rather than unprotected federated averaging. The proof excerpts connect privacy to the inability to recover the random masks that conceal partial sums.

A.2 PRIVACY

  • CCESA and secure aggregation prevented successful reconstruction of AT&T Face identities under model inversion, unlike federated averaging.The figure caption states that only the federated-averaging setup allowed reconstruction of the original training images.Source: §A.2 · p. 11, Figure A.4 · p. 12
  • On CIFAR-10, membership-inference precision stayed near the 50% random-guess baseline for CCESA and secure aggregation, while federated averaging reached nearly 70%.The paper also reports recall close to 1 for all schemes.Source: §A.2 · p. 11, Table A.3 · p. 11

B.1 PROOF OF THEOREM 1

  • Reliability requires the server to obtain at least t_i shares for each relevant client secret; fewer shares prevent reconstruction.The proof states that receiving at least t_i shares is sufficient for reliability and begins a converse argument when this condition fails.Source: §B.1 · p. 13

B.2 PROOF OF LEMMA 1

  • A connected graph G3 protects every proper, nonempty client subset’s partial sum because a crossing edge contributes a pseudorandom mask the eavesdropper cannot unmask.The proof identifies a crossing edge between the subset and its complement; unmasking its term requires a client secret key whose shares the server does not request.Source: §B.2 · pp. 13–14

B.3 PROOF OF THEOREM 2

The proof excerpts characterize privacy through graph structure and informative nodes, then use random-graph properties and probability bounds to establish reliability and privacy guarantees. They also outline bounds on failure and disconnection probabilities.

B.3 PROOF OF THEOREM 2

  • Privacy holds for the stated graph-evolution class when an eavesdropper cannot recover any proper, nonempty subset’s partial sum; an all-informative disconnected component yields a privacy violation.The proof argues that a non-informative node prevents recovery of both masking secrets, whereas an all-informative component can be exposed.Source: §B.3 · pp. 14–15

B.4 PROOF OF THEOREM 3

  • For an Erdős–Rényi assignment graph, a client’s degree is binomially distributed, and its successfully delivered shares are also modeled with a binomial distribution.The proof defines N_i as node degree and X_i as neighbors successfully sending client i’s shares.Source: §B.4 · p. 15

B.5 PROOF OF THEOREM 4

  • The privacy proof lower-bounds success using connectivity of the induced graph G3 and applies the Erdős–Rényi connectivity threshold.It states that CCESA is almost surely private when p exceeds p⋆, with the bound tied to the probability that G3 is connected.Source: §B.5 · p. 16

B.6 PROOF OF THEOREM 5

  • The reliability-bound proof estimates the probability that a client secret is not reconstructed using a Chernoff bound and the reliability condition.It defines failure as receiving fewer than t shares and invokes Theorem 1 to bound system reliability.Source: §B.6 · p. 17

B.7 PROOF OF THEOREM 6

  • The disconnection-probability proof bounds graph failure by considering disconnected subsets and the probability that G3 has a given number of vertices.The excerpt expresses the bound through P(G3 has m vertices) and the probability an Erdős–Rényi graph is disconnected.Source: §B.7 · p. 17

C.1 COMMUNICATION COST

CCESA’s sparse client connections reduce communication and computation relative to conventional secure aggregation, with costs governed by each client’s graph degree. The section derives the per-client communication components and asymptotic costs for both clients and server.

C.1 COMMUNICATION COST

  • Each client’s additional bandwidth is 2(|Adj(i)| + 1)aK + (5|Adj(i)| + 1)aS, excluding its mR-bit model vector.The four components are key exchange, encrypted shares, the masked model, and shares sent to the server.Source: §C.1 · p. 18
  • With p = (1 + ϵ)p⋆, CCESA adds O(√n log n) bandwidth per client, versus O(n) for secure aggregation.The comparison uses B_CC E S A = O(√n log n) and B_S A = O(n) as stated in the passage.Source: §C.1 · p. 18

C.2 COMPUTATIONAL COST

  • With p = (1 + ϵ)p⋆, client computation is O(n log n + m√n log n), and server computation is O(mn log n + n² log n).For secure aggregation, client computation is O(n² + mn) and server computation is O(mn²).Source: §C.2 · p. 18

D RELIABILITY AND PRIVACY OF CCESA

For the selected graph probability, the analysis establishes high-probability reliability and privacy for CCESA. The secret-sharing threshold must also balance dropout tolerance against protection from the server’s unmasking attack.

D RELIABILITY AND PRIVACY OF CCESA

  • CCESA(n, p⋆) is reliable with probability at least 1 − O(ne^−√n log n) and private with probability at least 1 − O(n^−C), for arbitrary C > 0.The analysis assumes p = p⋆ and selects t according to the rule in Section E.Source: D RELIABILITY AND PRIVACY OF CCESA · pp. 18–20

E DESIGNING THE PARAMETER t FOR THE SECRET SHARING

  • The threshold t trades off dropout tolerance against unmasking risk: smaller t tolerates more dropouts, but an excessively small t can expose local models to the server.The design chooses the minimum threshold that avoids the unmasking attack; the proposition states that t > 2 gives asymptotic security against it.Source: E DESIGNING THE PARAMETER t FOR THE… · p. 20

F.1 AT & T FACE DATASET

The experimental passages specify datasets, client allocations, training setups, connection probabilities, and cryptographic implementation choices. They do not report the experiment outcomes in this request’s supplied passages.

F.1 AT & T FACE DATASET

  • The AT&T Face experiment uses 40 clients, each holding images from one member, with softmax regression trained for 50 local epochs and 50 global rounds.The SGD learning rate is 0.05.Source: §F.1 · p. 21

F.2.1 RELIABILITY EXPERIMENT IN FIG. 5.2

  • The reliability experiment allocates 50,000 images across 1,000 clients using either i.i.d. 50-image partitions or non-i.i.d. assignments of two shards per client.It uses VGG-11, SGD with learning rate 0.1 and momentum 0.5, and three local epochs.Source: §F.2.1 · p. 21

F.2.2 PRIVACY EXPERIMENTS IN TABLE 5.2 AND TABLE A.3

  • The privacy experiments assign i.i.d. training data across 10 clients, using the architecture, optimizer, and local-epoch settings from Section F.2.1.Source: §F.2.2 · p. 21

F.3 CONNECTION PROBABILITY SETUP IN FIG. 4.1

  • The connection-probability experiment selects p = p⋆(n, qtotal) for different n and qtotal values.The passage directs readers to Table F.4 for the specific probabilities.Source: §F.3 · p. 21, Table F.4 · p. 21

F.4 RUNNING TIME EXPERIMENT IN TABLE 5.1

  • The CCESA implementation uses AES-GCM with 128-bit keys, elliptic-curve Diffie–Hellman with SHA-256, and Shamir secret sharing.The passage also specifies a NumPy random-integer function for the pseudorandom generator.Source: §F.4 · p. 21
Loading 2012.05433v3…