PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Dropout-resilient Aggregation for Privacy-preserving Machine Learning

Ziyao Liu, Jiale Guo, Kwok-Yan Lam, Jun Zhao

arXiv:2203.17044v1cs.CR

TL;DR

Privacy-preserving aggregation for large-scale ML must account for mobile clients that can drop out during execution. This paper combines HPRG with Shamir secret sharing to reduce interaction while retaining security against semi-honest and active malicious adversaries. The proposed scheme’s runtime decreases as dropout rates rise, and the authors report stronger dropout resilience than prior schemes.

  • Problem

    Large-scale PPML relies on resource-constrained mobile clients that may drop out, making dropout-resilient privacy-preserving aggregation an important problem.

    Source: §I · p. 2

  • Method

    The scheme combines HPRG with Shamir secret sharing, replacing interactive seed agreement and reducing client interaction for dropout handling.

    Source: §I · p. 3

  • Results

    The protocol’s runtime decreases as dropout rate increases, providing stronger dropout resilience than previous schemes.

    Source: §I · p. 3

  • Takeaways & Limitations

    The protocol computes private sums, tolerates dropout during execution, and is secure against semi-honest and active malicious adversaries with proper system parameters.

    Source: §VI · p. 15

Abstract

from arXiv · show

With the increasing adoption of data-hungry machine learning algorithms, personal data privacy has emerged as one of the key concerns that could hinder the success of digital transformation. As such, Privacy-Preserving Machine Learning (PPML) has received much attention from both academia and industry. However, organizations are faced with the dilemma that, on the one hand, they are encouraged to share data to enhance ML performance, but on the other hand, they could potentially be breaching the relevant data privacy regulations. Practical PPML typically allows multiple participants to individually train their ML models, which are then aggregated to construct a global model in a privacy-preserving manner, e.g., based on multi-party computation or homomorphic encryption. Nevertheless, in most important applications of large-scale PPML, e.g., by aggregating clients' gradients to update a global model for federated learning, such as consumer behavior modeling of mobile application services, some participants are inevitably resource-constrained mobile devices, which may drop out of the PPML system due to their mobility nature. Therefore, the resilience of privacy-preserving aggregation has become an important problem to be tackled. In this paper, we propose a scalable privacy-preserving aggregation scheme that can tolerate dropout by participants at any time, and is secure against both semi-honest and active malicious adversaries by setting proper system parameters. By replacing communication-intensive building blocks with a seed homomorphic pseudo-random generator, and relying on the additive homomorphic property of Shamir secret sharing scheme, our scheme outperforms state-of-the-art schemes by up to 6.37$\times$ in runtime and provides a stronger dropout-resilience. The simplicity of our scheme makes it attractive both for implementation and for further improvements.

I. INTRODUCTION

Large-scale privacy-preserving aggregation must protect participants’ data while accommodating mobile clients that may drop out. The paper combines HPRG with Shamir secret sharing to reduce protocol overhead and strengthen dropout resilience while retaining security against semi-honest and active malicious adversaries.

I. INTRODUCTION

  • Gradient leakage motivates cryptographic aggregation: gradients can reveal private training data, while differential privacy trades privacy protection against data usability and model performance.The introduction notes that attackers can recover images with pixel-wise accuracy and texts with token-wise matching from gradient information.Source: §I · p. 1
  • Resource-constrained mobile clients may drop out, and pair-wise Diffie–Hellman seed agreement has O(n^2) communication-round complexity; dropout can also sharply increase protocol runtime and invite malicious slowdown.The paper identifies active malicious dropping that slows the system as a potential attack.Source: §I · p. 2
  • Earlier efficiency approaches include limiting client communication, reducing computation, changing key exchange, or compressing gradients, but several alternatives have security, trust, scale, or dropout-resilience constraints.The paper selects SecAgg as its baseline and SecAgg+ as a state-of-the-art comparison, focusing on single-server schemes without non-collusion assumptions.Source: §I · pp. 2–3
  • HPRG-based seed generation replaces pair-wise Diffie–Hellman agreement, while Shamir secret sharing supports dropout handling with less client interaction and one server-side seed reconstruction.The proposed scheme retains t-out-of-n Shamir sharing and requires no extra trusted third party.Source: §I · p. 3
  • With proper system parameters, the proposed scheme is secure against semi-honest and active malicious adversaries even when clients drop out during execution.The authors describe the scheme as simple and attractive for implementation and further improvement.Source: §I · p. 3

II. UNDERLYING CRYPTOGRAPHIC PRIMITIVES

The section introduces cryptographic primitives used by the protocol, including Shamir secret sharing. In its t-out-of-n form, Shamir sharing lets parties reconstruct a secret from t shares, and its additive homomorphism permits shared secrets to be summed.

II. UNDERLYING CRYPTOGRAPHIC PRIMITIVES

  • The section reviews Shamir secret sharing, homomorphic pseudorandom generators, and signature schemes as underlying cryptographic primitives.The supplied Shamir passages explain threshold sharing and its additive homomorphism.Source: §II · p. 3

A. Shamir Secret Sharing

  • In t-out-of-n Shamir sharing, a degree-(t−1) polynomial encodes the secret as its constant term, and any t shares suffice to reconstruct it.Fewer than t shares cannot reconstruct the secret.Source: A. Shamir Secret Sharing · pp. 3–4
  • Shamir sharing is additive homomorphic when both secrets use the same participant point set: parties add corresponding shares locally, and the sum can be reconstructed.The passage specifies that the shared point set is commonly {1, 2, …, n}.Source: A. Shamir Secret Sharing · p. 4

B. Homomorphic Pseudorandom Generator

The section defines pseudorandom generators and the seed-homomorphic property used to construct an HPRG, then describes signature generation, verification, and security. The HPRG construction uses a DDH-based design, while the signature scheme addresses message origin and forgery.

B. Homomorphic Pseudorandom Generator

  • An HPRG is a PRG whose outputs combine according to the combination of their seeds.The section defines a PRG as generating a sequence of approximate random numbers and describes HPRG as seed homomorphic.Source: B. Homomorphic Pseudorandom Generator · p. 4
  • Under the DDH assumption, the construction generates a mask sequence by evaluating F(s, i) at indices matching the input vector length.The section presents a DDH-based HPRG as an efficiency-security trade-off compared with less practical standard-model alternatives based on learning with errors.Source: B. Homomorphic Pseudorandom Generator · p. 4

C. Signature Scheme

  • A signature scheme proves message origin using key generation, signing, and verification algorithms.Verification returns whether the signature corresponds to the message and public key.Source: C. Signature Scheme · p. 4
  • The scheme’s stated security target is UF-CMA: forging a valid signature on a previously unsigned message without the secret key has negligible probability.The section characterizes this as security against universal forgery under chosen message attack.Source: C. Signature Scheme · pp. 4–5

III. PROPOSED SCHEME

The proposed scheme aims to privately aggregate clients’ model vectors despite client dropout, under semi-honest and active malicious threat models. It masks each model and uses Shamir secret sharing so the server can reconstruct the aggregate from a threshold of connected clients.

III. PROPOSED SCHEME

  • The scheme targets private summation of clients’ locally trained models while allowing clients to drop out during aggregation.The threat model includes semi-honest participants and active malicious participants, with additional protection against the latter under an upper bound on adversaries.Source: §III · p. 5

A. Masking Models

  • Clients mask model elements before upload; revealing individual masks to the server would let it recover the corresponding models.The text motivates element-wise masking because using the same random value across all model elements could expose the original model’s distribution.Source: A. Masking Models · p. 5
  • In the initial partial-information approach, privacy is preserved, but the server can reconstruct the aggregate mask only if it receives every client’s partial information.The passage identifies this all-clients-connected requirement as the approach’s dropout limitation.Source: A. Masking Models · p. 5

B. Handling dropout clients

  • With t-out-of-n Shamir sharing, the server can reconstruct the mask from connected clients when at least t shares are available.Each client locally combines shares it holds into partial information about the aggregate mask; Shamir reconstruction recovers the secret from a threshold set.Source: B. Handling dropout clients · p. 5

C. More efficiently generating masks

The scheme uses HPRG to generate masks from seeds while retaining the additive relationship needed for aggregation. It masks vectors multiplicatively, then recovers the sum through discrete logarithms under stated parameter conditions.

C. More efficiently generating masks

  • HPRG’s additive homomorphism lets the server cancel the combined mask when aggregating masked client vectors.The section explains that ordinary PRG seed-based masks do not provide the needed aggregation relation, whereas HPRG does.Source: C. More efficiently generating masks · p. 6
  • The scheme uses random group masks and requires P > q > n * max(x_i) to avoid overflow in the aggregation result.The passage states that the multiplicative mask hides information about x_i and that q is the order of the finite cyclic group.Source: C. More efficiently generating masks · p. 6
  • 12.5 seconds: the stated runtime for computing 1024-bit discrete logarithms over a 64-bit plaintext space, with n = 500 and 50K vector entries.The passage says Pollard’s lambda method takes roughly square-root time in the plaintext space.Source: C. More efficiently generating masks · p. 6

D. Putting it all together

The integrated protocol distributes seed shares, masks client updates with HPRG, and uses Shamir sharing to recover the aggregate mask. Its threshold recovery supports aggregation despite client dropouts, while replacing pairwise masking with additive Shamir sharing reduces communication overhead.

D. Putting it all together

  • Clients share seed information, generate HPRG masks for their updates, and send masked updates for server aggregation and mask recovery.The server reconstructs the final mask from Shamir shares and removes it from the aggregate of the connected clients’ masked updates.Source: D. Putting it all together · p. 6
  • Using Shamir’s additive property instead of pairwise masking reduces communication overhead and requires no additional Shamir shares once enough shares of the final mask are collected.The text characterizes this as stronger dropout-resilience with respect to efficiency than SecAgg-based schemes.Source: D. Putting it all together · p. 6

E. Proposed secure aggregation protocol

  • The server can recover the correct aggregate when more than t clients remain connected, including updates uploaded before a client drops out.An uploaded masked model remains usable if its client shared its seed; a client that shared a seed but never uploaded a model is excluded from the recovered mask.Source: E. Proposed secure aggregation protocol · pp. 6–7
  • The protocol’s synchronous-channel assumption bounds the wait for the server’s list of clients that uploaded masked models.Clients use that list to determine which seed shares contribute to the final mask.Source: E. Proposed secure aggregation protocol · p. 7
  • Removing pairwise DH seed agreement gives the protocol a simpler structure than SecAgg.The comparison identifies pairwise DH key agreement as SecAgg’s most communication-intensive building block.Source: E. Proposed secure aggregation protocol · p. 7

IV. SECURITY ANALYSIS

The security analysis considers a server that stays online while clients may drop out, and adversarial coalitions of fewer than the threshold number of clients. The HPRG-based protocol is analyzed against semi-honest clients, both with and without server collusion.

IV. SECURITY ANALYSIS

  • The server remains online while clients may abort at any protocol point; the security definition requires coalitions of fewer than t clients to learn nothing about honest clients’ inputs.The analysis also considers coalitions that include the server.Source: §IV · p. 7

A. Semi-honest Model

  • With an honest server, a simulator can reproduce the views of semi-honest client coalitions using their actual inputs and dummy inputs for other participants.The theorem states this for coalitions of fewer than t clients.Source: A. Semi-honest Model · p. 7
  • With server collusion, the proof uses Shamir secrecy and HPRG security in a hybrid argument to show simulated adversary views are computationally indistinguishable from real views.The proof replaces honest clients’ masked models with random values while preserving the stated distribution.Source: A. Semi-honest Model · pp. 7, 9
  • Clients share seeds using t-out-of-n Shamir secret sharing, then use HPRG-generated masks to protect their locally trained models before aggregation.The protocol aggregates the models of connected clients.Source: A. Semi-honest Model · p. 8

B. Active Malicious Model

The active-malicious analysis considers adversaries that may deviate during execution, so correctness is not guaranteed. It describes consistency checks and proves privacy claims for client and server threat settings.

B. Active Malicious Model

  • Under active adversaries, correctness is not guaranteed because adversaries may deviate by sending fraudulent messages or distorting outputs; the analysis considers privacy of honest clients’ inputs.For malicious clients and an honest server, the security theorem covers coalitions of fewer than t clients.Source: B. Active Malicious Model · p. 9
  • Clients sign the server’s connected-client list and verify the forwarded signatures, checking that participants share the same view of connected clients.The consistency check costs one communication round and may cause additional client dropouts.Source: B. Active Malicious Model · p. 9
  • For active malicious clients and a malicious server, the simulator may query an ideal function for sums over dynamically selected honest-client subsets.The theorem’s simulator learns the required sum for a subset meeting the stated lower bound δ.Source: B. Active Malicious Model · p. 10
  • The active-malicious security claim limits what adversaries learn to sums of inputs for subsets L with at least δ honest participants.This is the stated privacy conclusion of the proof.Source: B. Active Malicious Model · p. 11

1) Malicious clients with honest server:

With an honest server, the consistency check ensures each honest client views the correct connected-client list.

1) Malicious clients with honest server:

2) Honest clients with malicious server:

A malicious server can exploit different connected-client lists to leak an honest client’s input, so the threshold must exceed half the clients.

2) Honest clients with malicious server:

  • For n clients, the threshold must be t ≥⌊n 2 ⌋+ 1 to prevent the illustrated different-list attack from leaking an honest client’s input.With t = 2, the example’s lists yield mask products whose quotient reveals a client’s mask and causes input leakage.Source: 2) Honest clients with malicious server · p. 11

3) Malicious clients and server:

With an active malicious server and clients, malicious clients can sign multiple lists, allowing a consistency check to pass while a client’s input is leaked. The section then analyzes the threshold needed for security.

3) Malicious clients and server:

  • With six clients, threshold t = 4, and two active malicious clients signing two different lists, both lists pass consistency checks and client u6’s input is leaked.The example shows this can occur even with t ≥ ⌊n/2⌋+1.Source: 3) Malicious clients and server · p. 11
  • The threshold analysis considers two fraudulent lists, counting honest and malicious signatures separately, and requires each list to have at least t effective signatures to pass consistency checks.Source: 3) Malicious clients and server · p. 11
  • The analysis assumes the number of adversaries nc cannot exceed n/3 and states that a minimum security threshold t can be derived under this bound.Source: 3) Malicious clients and server · p. 11

V. PERFORMANCE ANALYSIS

The performance analysis characterizes the scheme’s computational and communication costs, then evaluates it under varying system sizes and dropout rates. The experiments report lower runtime than SecAgg and SecAgg+ in high-dropout, large-scale settings, while also identifying a discrete-log computation boundary for large neural networks.

A. Complexity analysis

  • Per-client computation is O(n^2 + m), server computation is O(n), per-client communication is O(m + n), and server communication is O(n^2 + mn).Source: A. Complexity analysis · p. 11
  • The scheme retains SecAgg’s maximum dropout tolerance and SecAgg+’s resilience while its runtime decreases as dropout increases.Source: A. Complexity analysis · pp. 11–12

B. Experiments

C. Further discussions

The discussion delineates privacy risks and constraints on integrating defenses, while the conclusion presents the protocol as efficient, dropout-resilient, and secure against semi-honest and active malicious adversaries.

C. Further discussions

  • The protocol protects clients’ gradient vectors, but intermediate and final global models are revealed to participants, leaving it vulnerable to membership inference.Protecting global models would require integration with existing HE- or MPC-based solutions, which may add substantial overhead for large neural networks.Source: C. Further discussions · p. 14
  • Defense integration is constrained: methods that evaluate clients’ locally trained models require server access and breach the privacy requirements of secure aggregation.Methods evaluating selected updates can integrate straightforwardly; BaFFLe is given as an example because it validates the new global model without leaking clients’ models to the server.Source: C. Further discussions · p. 14

VI. CONCLUSIONS

  • The conclusion presents a sum-aggregation protocol that preserves input privacy, permits dropout during execution, and is secure against semi-honest and active malicious adversaries with proper parameters.The authors describe it as efficient and suitable for large-scale PPML scenarios.Source: §VI · p. 15

Related papers

Loading 2203.17044v1…