PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Privacy-Preserving Distributed Learning

David Froelicher, Juan R. Troncoso-Pastoriza, Apostolos Pyrgelis, Sinem Sav, Joao Sa Sousa, Jean-Philippe Bossuat, Jean-Pierre Hubaux

arXiv:2005.09532v5cs.CR

TL;DR

Sensitive data are difficult to pool, while existing approaches leave gaps in privacy-preserving distributed training and complete workflow coverage. SPINDLE extends MapReduce with cooperative encrypted learning and prediction, and reports accuracy comparable to non-secure centralized training alongside scalability across data providers, dataset size, and features.

  • Problem

    Sensitive data are difficult to share, while prior solutions often cover only training or prediction and may not provide data and model confidentiality together.

    Source: §I · p. 1

  • Method

    SPINDLE extends MapReduce for cooperative gradient descent and prediction, using multiparty homomorphic encryption to protect data and models in a passive-adversary setting.

    Source: §I · p. 2

  • Results

    SPINDLE achieves accuracy comparable to non-secure centralized solutions and scales independently of provider count and linearly or better with local dataset size and feature count.

    Source: §X · p. 15

  • Takeaways & Limitations

    The reported results support privacy-preserving training and oblivious prediction on generalized linear models across distributed datasets.

    Source: §I · p. 2, §X · p. 15

Abstract

from arXiv · show

In this paper, we address the problem of privacy-preserving distributed learning and the evaluation of machine-learning models by analyzing it in the widespread MapReduce abstraction that we extend with privacy constraints. We design SPINDLE (Scalable Privacy-preservINg Distributed LEarning), the first distributed and privacy-preserving system that covers the complete ML workflow by enabling the execution of a cooperative gradient-descent and the evaluation of the obtained model and by preserving data and model confidentiality in a passive-adversary model with up to N-1 colluding parties. SPINDLE uses multiparty homomorphic encryption to execute parallel high-depth computations on encrypted data without significant overhead. We instantiate SPINDLE for the training and evaluation of generalized linear models on distributed datasets and show that it is able to accurately (on par with non-secure centrally-trained models) and efficiently (due to a multi-level parallelization of the computations) train models that require a high number of iterations on large input data with thousands of features, distributed among hundreds of data providers. For instance, it trains a logistic-regression model on a dataset of one million samples with 32 features distributed among 160 data providers in less than three minutes.

I. INTRODUCTION

Sensitive data are difficult to pool, while prior secure-learning approaches leave gaps in distributed training, workflow coverage, or security assumptions. SPINDLE extends MapReduce for privacy-preserving cooperative learning and prediction, and the paper reports accurate, scalable training on distributed data.

I. INTRODUCTION

  • Sensitive data are difficult to share, limiting access to the large and diverse datasets that machine-learning training usually requires.Data may be distributed across entities, and legal, financial, and reputational concerns can make sharing difficult.Source: §I · p. 1

II. RELATED WORK

  • SPINDLE targets gaps in prior work: secure training was less studied than prediction, and many distributed solutions covered only training or prediction or relied on limited-party assumptions.The paper also notes that some prior approaches focus on models with few features or are not quantum secure.Source: §I · p. 1

I. INTRODUCTION

  • SPINDLE extends MapReduce with privacy constraints to support distributed, privacy-preserving training and prediction across data providers that do not trust one another.The system uses cooperative gradient descent for a complete machine-learning workflow.Source: §I · p. 2
  • SPINDLE uses a quantum-resistant multiparty scheme in a passive-adversary model that tolerates all but one data provider being dishonest.It supports cooperative SGD and is instantiated for generalized linear models, including linear, logistic, and multinomial regression.Source: §I · p. 2
  • 83.9% accuracy in under 54 seconds: SPINDLE trained logistic regression on 11,500 samples and 90 features across 10 data providers, matching a non-secure centralized solution.The paper attributes its scalability to workload distribution, SIMD packing, and collective ciphertext refresh.Source: §I · p. 2
  • The paper also proposes parallel and SIMD computations, collective operations, and polynomial approximations to make multiparty encryption efficient, plus a graphical model for parameter selection.It evaluates SPINDLE against centralized and decentralized secure solutions for scalability and accuracy.Source: §I · p. 2

III. SECURE FEDERATED TRAINING AND EVALUATION

The paper frames secure federated training and evaluation as a workflow over horizontally partitioned data held by providers who collaborate but do not trust one another. Its extended MapReduce abstraction coordinates training and adds prediction on protected inputs.

A. Problem Statement

  • The setting has a horizontally partitioned dataset: each data provider holds a subset of samples, and a querier can request training or evaluation on its own input.The querier may also be one of the data providers.Source: A. Problem Statement · p. 3
  • Providers collaborate on training and evaluation but do not trust one another, so the workflow must protect their data and collectively learned models.They are interconnected in a topology intended to enable efficient computation.Source: A. Problem Statement · p. 3
  • The extended MapReduce workflow adds PREDICTION to PREPARE, MAP, COMBINE, and REDUCE, allowing protected inputs to be evaluated with the protected global model.Training locally updates provider models, combines their results, and updates the global model.Source: A. Problem Statement · p. 4

IV. SPINDLE DESIGN

SPINDLE implements cooperative gradient descent and encrypted prediction within the extended MapReduce workflow. It combines local SGD updates with global model aggregation and uses multiparty homomorphic encryption to protect distributed generalized linear-model training and evaluation.

IV. SPINDLE DESIGN

  • SPINDLE applies multiparty fully homomorphic encryption to cooperative gradient descent and encrypted prediction for generalized linear models.The design instantiates the extended MapReduce workflow through secure, interactive protocols.Source: §IV · pp. 4–5

A. Background

  • Cooperative SGD lets providers perform multiple local updates before aggregating their weights into global weights for subsequent computations.The paper presents a synchronous version; the elastic rate controls how much providers can diverge from the global model.Source: A. Background · p. 5
  • Multiparty homomorphic encryption keeps the model collectively encrypted: parties can compute using a collective public key, while decryption requires their collaboration.The scheme also permits collective key switching without decrypting.Source: A. Background · pp. 5–6
  • The paper considers linear, logistic, and multinomial regression as generalized linear models, relating the linear predictor to class labels through an activation function.For multinomial regression, weights are represented as a matrix with one column per class.Source: A. Background · p. 5
  • CKKS supports approximate arithmetic on encrypted vectors, with cryptographic parameters chosen to provide at least 128-bit security.After operations increase noise and scale, ciphertexts are rescaled; at level zero, they must be bootstrapped.Source: A. Background · p. 5

B. SPINDLE Protocols

SPINDLE trains generalized linear models through repeated local gradient-descent updates across data providers. Its training workflow prepares shared parameters and keys, computes encrypted local updates, combines them, and produces a broadcast encrypted global model.

B. SPINDLE Protocols

  • The section applies Protocol 1 to generalized linear models, with MAP representing multiple local gradient-descent iterations.For multinomial regression, the operations repeat for each label class.Source: B. SPINDLE Protocols · p. 6

1) TRAINING:

  • PREPARE agrees on iteration and learning parameters, initializes distributed CKKS keys and local weights, and precomputes operations involving each provider’s data.The learning parameters are α, ρ, and batch size b.Source: 1) TRAINING · p. 6
  • During MAP, each provider performs m cooperative gradient-descent updates on batches of b samples and c features, then rerandomizes its final local weights.Rerandomization adds a fresh encryption of zero to the final local weights.Source: 1) TRAINING · p. 6
  • Encrypted logistic and multinomial activations use polynomial approximations: least-squares for sigmoid and Chebyshev approximations for softmax.The softmax procedure subtracts an approximated maximum before approximation to avoid exponential-value explosion.Source: 1) TRAINING · pp. 6–7
  • After g MAP, COMBINE, and REDUCE iterations, the data providers obtain and broadcast the encrypted global model.The reducer combines updated local weights with the previous global weights using the learning and elastic rates.Source: 1) TRAINING · p. 7

2) PREDICTION:

Prediction encrypts a querier’s input under the collective public key and computes encrypted predictions using the trained model. The providers then switch the result encryption to the querier’s key so only the querier can decrypt it.

2) PREDICTION:

  • The encrypted prediction values are produced by multiplying encrypted querier inputs by the encrypted trained weights and applying the activation function.The procedure yields one prediction per input row.Source: 2) PREDICTION · p. 7
  • The querier encrypts input data under the collective public key before prediction computation.The model computation remains in the encrypted domain.Source: 2) PREDICTION · p. 7
  • The data providers collectively switch encrypted predictions from the collective key to the querier’s public key, leaving decryption to the querier.The key-switching operation uses the querier’s public key and the providers’ secret keys.Source: 2) PREDICTION · p. 7

V. SYSTEM OPERATIONS

SPINDLE’s system operations optimize homomorphic computations by managing expensive cryptographic operations and parallelizing encrypted vector-matrix multiplication and activation evaluation.

V. SYSTEM OPERATIONS

  • Rescaling and distributed bootstrapping are scheduled to reduce the overhead of sequential ciphertext operations and high multiplicative depth.The section identifies these choices as part of optimizing the protocols.Source: §V · p. 7
  • The MAP protocol’s encrypted computation includes a sequence of vector-matrix multiplications followed by activation-function evaluation.The operations are performed in the encrypted domain.Source: §V · p. 7
  • The system operations section covers both cryptographic-operation scheduling and efficient execution of the MAP protocol.It discusses distributed CKKS properties as the basis for these optimizations.Source: §V · p. 7

A. Cryptographic Operations

SPINDLE reduces cryptographic overhead through selective rescaling, relinearization, and bootstrapping, and adapts packing for encrypted MAP vector-matrix multiplications. It chooses between row-based and diagonal packing according to the learning setup and available threads.

A. Cryptographic Operations

  • SPINDLE delays rescaling until ciphertext scale approaches qτ and generally relinearizes after each ciphertext-ciphertext multiplication to control size and degree.Relinearization can be deferred when that lowers computational complexity.Source: A. Cryptographic Operations · p. 7

B. MAP Vector-Matrix Multiplications

  • Figure 2 shows packing approaches for executing Protocol 2, lines 4 and 5, assuming c·b<N/2 and using an example with c=b=4.Dash elements are plaintext values, and everything else is encrypted. Dup duplicates and adds; rowP packs rows in one ciphertext.Source: Figure 2 · p. 8

A. Cryptographic Operations

  • Global bootstrap reduces the number of bootstrap operations, while local or hybrid bootstrap permits more local iterations; the preferred trade-off depends on update frequency and dataset.Local bootstrapping runs in parallel across providers, amortizing its overhead, whereas global bootstrapping constrains local iterations by ciphertext levels and multiplication depth.Source: A. Cryptographic Operations · p. 8

B. MAP Vector-Matrix Multiplications

  • Packed ciphertext vectors support SIMD operations across slots, while ciphertext rotations combine values stored in different slots.The packing approaches target the two sequential encrypted vector-matrix multiplications in each local SGD iteration.Source: B. MAP Vector-Matrix Multiplications · p. 8
  • The row-based approach packs matrix rows and uses masking, while the diagonal approach diagonalizes the input matrix and avoids masking.The diagonal approach uses multiplicative depth a_m+2, fewer levels than row-based packing’s a_m+4.Source: B. MAP Vector-Matrix Multiplications · pp. 8–9
  • SPINDLE selects row-based or diagonal packing at each provider using feature count, batch size, and available threads.Diagonal packing is embarrassingly parallel, which can amortize its rotations and multiplications across threads.Source: B. MAP Vector-Matrix Multiplications · p. 9

C. Optimized Activation Function

The section optimizes encrypted activation computations, lays out linked learning and cryptographic parameter choices, and establishes confidentiality for training and prediction against a passive adversary controlling all but one party.

C. Optimized Activation Function

  • Polynomial approximations of sigmoid and softmax use an adapted baby-step giant-step algorithm to reduce multiplicative depth.The stated depth is ⌈log(d)⌉ for degree d≤7 and ⌈log(d)+1⌉ otherwise.Source: C. Optimized Activation Function · p. 9

VI. SYSTEM CONFIGURATION

  • The parameter graph links cryptographic and learning parameters, with input features and precision connected to both clusters through plaintext scale Δ.Circles denote learning parameters and dotted circles denote cryptographic parameters.Source: §VI · p. 9, Figure 3 · p. 9
  • Parameter selection starts with ciphertext degree N for packing at least c elements, then sets security parameters, precision, modulus levels, and learning parameters in relation to the data.The learning rate α and elastic rate ρ have minimum values limited by scale Δ.Source: §VI · p. 9

VII. SECURITY ANALYSIS

  • SPINDLE provides data and model confidentiality for training and prediction with CKKS parameters ensuring post-quantum security level λ against a passive adversary corrupting at most |S|−1 parties.The paper supports this claim with a real/ideal simulation argument.Source: §VII · p. 10
  • The security argument relies on encrypted exchanges, aggregation of encrypted MAP outputs, and re-randomization between iterations to prevent information leakage from successive outputs.The paper states that CKKS security rests on the decisional-RLWE problem and that DBootstrap security is established separately.Source: §VII · p. 10
  • Because intermediate and final model weights are never revealed during training, SPINDLE thwarts active federated-learning and model-inversion attacks by design.Source: §VII · p. 10

VIII. SYSTEM EVALUATION

SPINDLE’s evaluation examines its communication and computation complexity, then measures cryptographic-operation speed, model performance, and scalability. The results show accuracy close to non-private baselines alongside costs and scaling behavior that depend on the workload and configuration.

A. Theoretical Analysis

  • SPINDLE’s communication complexity is linear in provider count, iterations, and ciphertext size; MAP computation is linear in provider count and iterations and logarithmic in feature count and batch size.DA packing has higher computation complexity than RBA but is embarrassingly parallel and can be more time-efficient depending on available threads.Source: A. Theoretical Analysis · pp. 10–11

B. Empirical Evaluation

  • At SP1, DBootstrap takes 0.6 seconds versus 26 seconds for Han and Ki’s CKKS bootstrapping, which provides about 108-bit rather than 128-bit security.With SP2 and 40 data providers, DBootstrap takes 0.25 seconds versus about 20 seconds for Han and Ki’s solution.Source: Table I · p. 11, B. Empirical Evaluation · p. 11
  • Up to 0.8% accuracy loss versus centralized cleartext training; SPINDLE also achieves almost the same accuracy as DNP, with training taking 1–2 orders of magnitude longer than DNP.The comparison excludes centralized training times because the settings are not fairly comparable.Source: Table II · p. 12, B. Empirical Evaluation · p. 12
  • With fixed data per provider, execution time stays constant as providers increase; with fixed total data, it decreases linearly, and with a fixed provider count, it increases linearly with data size.Increasing batch size as providers hold more records can further reduce execution time.Source: Figure 4 · p. 12, Figure 4b
  • At 256 features on 24 threads, DA takes 165 seconds versus 330 seconds for RBA and 365 seconds for encrypted-input RBA.RBA-E execution time is 7% higher than RBA; parallelization is efficient up to 28 features, after which both approaches scale linearly.Source: B. Empirical Evaluation · pp. 12–13
  • SPINDLE consistently outperforms centralized HE solutions, while existing HE-SMC distributed solutions lack at least one of its confidentiality, workflow, or distributed-gradient-descent features.SPINDLE scales almost independently of provider count and can support hundreds of providers, including up to N-1 dishonest providers.Source: B. Empirical Evaluation · p. 13

IX. EXTENSIONS

The section introduces extensions to SPINDLE for malicious adversaries, dynamic data providers, quality control, and more complex models.

IX. EXTENSIONS

  • SPINDLE can be extended to withstand malicious adversaries, support dynamic data providers, enable quality control, and handle more complex ML models.The section presents these as extensions to the system.Source: §IX · p. 13

A. Malicious Adversaries

The paper describes safeguards and optional extensions for SPINDLE, then concludes that it supports scalable, privacy-preserving training and prediction for generalized linear models.

A. Malicious Adversaries

  • Range proofs and input constraints can limit malicious training interference, but plausible in-range inputs can still enable poisoning attacks.Publishing computation transcripts and proving correct inputs can also make training auditable.Source: A. Malicious Adversaries · p. 14
  • Prediction safeguards include published computation transcripts and signed input-knowledge proofs; limiting query counts can mitigate inference, while differential privacy is proposed as a possible improvement.The choice of privacy parameters is nontrivial, and minimizing released non-encrypted information is described as more practical in dynamic systems.Source: A. Malicious Adversaries · p. 14

B. Modular Extensions

  • Optional extensions include threshold encryption for unresponsive providers, dynamic role assignment, collective stopping, and data-preparation quality controls.Similar accuracy to centralized training requires providers’ local labels to be similarly distributed; asynchronous SGD variants may address response-time or data imbalances.Source: B. Modular Extensions · p. 14

C. More Complex ML Models.

  • SPINDLE can extend beyond generalized linear models to models such as neural networks, provided activation functions are practically approximable by polynomials and encrypted computations can be packed efficiently.Neural networks pose challenges from sequential layers and the resulting higher multiplicative-depth circuits.Source: C. More Complex ML Models · p. 14

X. CONCLUSION

  • SPINDLE achieves accuracy comparable to non-secure centralized solutions and scales independently of data-provider count, and linearly or better with local dataset size and feature count.The conclusion attributes its performance to concurrent local computation and multiparty protocols that replace costly homomorphic operations.Source: §X · p. 15

APPENDIX A MULTIPARTY HOMOMORPHIC ENCRYPTION (MHE)

The appendices describe CKKS and distributed CKKS operations used in SPINDLE, then outline encrypted polynomial and maximum-function approximations.

APPENDIX A MULTIPARTY HOMOMORPHIC ENCRYPTION (MHE)

  • CKKS operations cover encryption and decryption, addition, multiplication, rotation, rescaling, relinearization, and bootstrapping.The notation uses v for cleartext values and sk, pk, and evk for secret, public, and evaluation keys.Source: Appendix A · p. 17
  • Distributed CKKS protocols generate collective keys, refresh ciphertexts through bootstrapping, switch ciphertexts between public keys without decrypting, and decrypt collectively.These protocols require all data providers to contribute their secret keys.Source: Appendix A · p. 17

APPENDIX B ACTIVATION FUNCTIONS

  • Encrypted polynomial approximation evaluates an activation polynomial by inductively computing powers of the encrypted input and recursively combining quotient and remainder polynomials.The procedure selects a recursion parameter based on the polynomial degree.Source: Appendix B · p. 18
  • The maximum-function protocol takes an encrypted matrix, approximation intervals, and degrees, and returns encrypted approximations of each column’s maximum.Its procedure applies polynomial approximations and combines the resulting values.Source: Appendix B · p. 18

APPENDIX C SECURITY OF DBOOTSTRAP(·)

The appendix adapts distributed BFV bootstrapping to CKKS and argues that its security follows from the prior passive-adversary proof plus an indistinguishability assumption.

APPENDIX C SECURITY OF DBOOTSTRAP(·)

  • The CKKS distributed bootstrapping protocol follows the BFV protocol’s steps, collectively refreshing a ciphertext while relying on different computational assumptions.Its masked shares are statistically or computationally hiding rather than unconditionally hiding.Source: Appendix C · p. 18
  • Security of the adapted protocol follows the passive-adversary BFV proof with the additional assumption that Lemma 1 holds.The lemma states that the two specified distributions are λ-indistinguishable, with distinguishing probability bounded by 2^-λ.Source: Appendix C · pp. 18–19
  • The appendix bounds the probability that a masked message coefficient is distinguishable from a uniform sample by 2^-λ, and says the adapted protocol has the original protocol’s computational security at the same security parameter.The parties need an estimate of message magnitude to derive δ, and the modulus must accommodate the additions of N masks.Source: Appendix C · pp. 18–19

APPENDIX D EVALUATION

The evaluation appendix analyzes SPINDLE’s complexity, identifies the datasets used to assess it, and compares it with existing solutions. It also provides evaluation tables and a symbol reference.

APPENDIX D EVALUATION

  • Table IV presents SPINDLE’s evaluation, and the K-fold=5 baseline comparison reports training and prediction times in seconds.The supplied table caption identifies the comparison setup but does not provide specific table values.Source: Table IV · p. 19, Appendix D · p. 19

A. Theoretical Analysis

  • The complexity analysis reports that HB count depends on g and m; DA packing raises computation complexity but its operations can be amortized by N1·N2 with available threads.Appendix D also provides a complete complexity analysis and extends Table II in Table IVb with learning and approximation parameters.Source: A. Theoretical Analysis · p. 19, Appendix D · p. 19

B. Evaluation Datasets

  • SPINDLE is evaluated on CalCOFI for linear regression, BCW, PIMA, and ESR for logistic regression, and MNIST for multinomial regression.The datasets range from 699 records and 9 features for BCW to 812,174 records and 2 features for CalCOFI.Source: B. Evaluation Datasets · p. 19

C. Comparison with Prior Art

  • The prior-art comparison includes centralized encrypted solutions, Drynx, Prio, and Helen, with CES estimated using non-multiparty CKKS.Helen uses ADMM with additive homomorphic encryption and secret sharing; its comparison with SPINDLE is intended only as an intuition because the environments differ.Source: C. Comparison with Prior Art · p. 20
  • SPINDLE scales better than Helen as the number of samples increases and with more features, where it is almost 10x better.The comparison uses different experimental environments and excludes Helen’s proof-generation time.Source: Table V · p. 20, C. Comparison with Prior Art · p. 20

APPENDIX E NOTATIONS

  • Appendix E provides a table of frequently used symbols and notations.The supplied passage gives the table title but not the individual symbols or definitions.Source: Table VI · p. 21

Related papers

Loading 2005.09532v5…