PaperlayerView exact revision on arXiv

Source-linked AI summary

Privacy Preserving Vertical Federated Learning for Tree-based Models

Yuncheng Wu, Shaofeng Cai, Xiaokui Xiao, Gang Chen, Beng Chin Ooi

arXiv:2008.06170v1cs.CRcs.LG

TL;DR

The paper addresses privacy-preserving tree learning when clients share users but hold disjoint features and only one client has labels. It proposes Pivot, a hybrid TPHE-MPC solution with basic and enhanced protocols, achieving comparable accuracy and high efficiency without a trusted third party.

  • Problem

    Existing vertical FL solutions can require plaintext label sharing, trusted hardware, or non-colluding servers, conflicting with the setting where labels remain private at one client.

  • Method

    Pivot combines threshold partially homomorphic encryption and MPC to train and predict with vertical decision trees, while its enhanced protocol conceals split thresholds and leaf labels.

  • Results

    Pivot achieves accuracy comparable to non-private algorithms and high efficiency, with basic and enhanced protocols reaching up to 37.5x and 4.5x training-time speedups over an MPC baseline.

  • Takeaways & Limitations

    Pivot provides strong privacy guarantees for vertical tree-based models and extends to random forests and gradient boosting decision trees.

  • Takeaways & Limitations

    Releasing less information from the tree increases privacy but reduces efficiency and interpretability.

Abstract

from arXiv · show

Federated learning (FL) is an emerging paradigm that enables multiple organizations to jointly train a model without revealing their private data to each other. This paper studies {\it vertical} federated learning, which tackles the scenarios where (i) collaborating organizations own data of the same set of users but with disjoint features, and (ii) only one organization holds the labels. We propose Pivot, a novel solution for privacy preserving vertical decision tree training and prediction, ensuring that no intermediate information is disclosed other than those the clients have agreed to release (i.e., the final tree model and the prediction output). Pivot does not rely on any trusted third party and provides protection against a semi-honest adversary that may compromise $m-1$ out of $m$ clients. We further identify two privacy leakages when the trained decision tree model is released in plaintext and propose an enhanced protocol to mitigate them. The proposed solution can also be extended to tree ensemble models, e.g., random forest (RF) and gradient boosting decision tree (GBDT) by treating single decision trees as building blocks. Theoretical and experimental analysis suggest that Pivot is efficient for the privacy achieved.

1. INTRODUCTION

Vertical federated learning lets organizations with the same records but disjoint features collaborate when labels remain with one client. Pivot addresses privacy and efficiency gaps in vertical tree-based learning without a trusted third party.

  • Motivation: Vertical federated learning combines disjoint features held by different clients for the same records, unlike the mainly studied horizontal setting.The paper illustrates this with a bank and Fintech company jointly evaluating credit-card applications.
  • Motivation: Existing privacy-preserving vertical FL solutions either assume plaintext label sharing, rely on potentially vulnerable secure hardware, or require non-colluding outsourced servers.These assumptions are insufficient when labels belong to one client and cannot be revealed to the others.
  • Pivot: Pivot provides privacy-preserving vertical decision-tree training and prediction without a trusted third party against a semi-honest adversary compromising up to m−1 of m clients.Its hybrid design combines threshold partially homomorphic encryption with MPC, using each where appropriate.
  • Pivot: The basic protocol supports classification and regression trees and distributed prediction, while the enhanced protocol conceals selected parts of the released tree model.Pivot also extends to random forests and gradient boosting decision trees.
  • Evaluation: Pivot achieves accuracy comparable to non-private algorithms and up to 37.5x and 4.5x training-time speedups over an MPC baseline for its basic and enhanced protocols.The evaluations cover DT, RF, and GBDT models on real and synthetic datasets.

2. PRELIMINARIES

The preliminaries introduce the cryptographic primitives and tree-learning procedures underlying Pivot. They explain threshold homomorphic encryption, secret-sharing MPC, and CART-based tree construction and ensembles.

  • Cryptographic primitives: Paillier partially homomorphic encryption supports restricted computation over ciphertexts through key generation, encryption, decryption, and homomorphic operations.The paper uses threshold PHE so decryption requires participation from all clients.
  • Cryptographic primitives: MPC with additive secret sharing keeps inputs and intermediate results secret, while secure addition, multiplication, comparison, division, and exponential operations form computation building blocks.Outputs remain secretly shared unless they are reconstructed.
  • Tree models: CART recursively stops at pruning conditions, creates majority-class or mean-value leaves, or selects a best split and partitions the data into two subtrees.Classification uses impurity gain, whereas regression uses label variance and variance gain.
  • Tree models: The paper considers binary CART trees and notes that tree ensembles such as random forests and gradient boosting decision trees can be built from individual trees.Other tree variants, including ID3 and C4.5, can also be generalized.

3. SOLUTION OVERVIEW

Pivot formalizes vertical tree learning and prediction among clients sharing sample identities but holding disjoint features and labels concentrated at one super client. Its protocols expose only agreed outputs while handling stronger concealment requirements.

  • Setting and assumptions: Pivot assumes clients share sample IDs while holding different features, with the common samples aligned privately and labels held by one super client.Private set intersection techniques are used without revealing samples outside the intersection.
  • Setting and assumptions: The security model is semi-honest and permits a static adversary to corrupt up to m−1 clients, without granting additional trust to the super client.The adversary may infer information from received messages while following the protocol.
  • Security formulation: Security requires that an adversary learn no more than the corrupted clients’ data and the final output, formalized through ideal and real protocol interactions.The ideal functionality abstracts computation by a trusted third party that returns the final output.
  • Functionality: The basic functionality releases a plaintext tree model, while the enhanced functionality releases only split features and conceals thresholds and leaf prediction labels.These choices define the information available to clients after training.
  • Protocol overview: Pivot proceeds through initialization, model training, and model prediction, with enhanced prediction revealing only the predicted label.Clients first agree on the algorithm and predefined information to release.

4. BASIC PROTOCOL

Pivot’s basic protocol trains vertical classification and regression trees without exposing plaintext labels or intermediate results, using local encrypted computation plus MPC for split selection. It also supports distributed prediction while limiting disclosure to the released tree model and predicted output.

  • Pivot combines homomorphic encryption with MPC: clients compute split statistics locally and invoke MPC only for operations such as best-split determination.This hybrid design avoids the high communication complexity of applying MPC to all O(nd) secretly shared values.
  • The basic protocol supports classification-tree and regression-tree training, followed by distributed prediction using the resulting tree model.
  • Clients represent each node’s available samples with an encrypted mask vector and recursively update encrypted masks for the two child nodes after selecting a split.The encrypted mask preserves which samples belong to a node while allowing branch-specific updates.
  • For each candidate split, clients derive encrypted child-node sample counts and class counts, convert them to secret shares, and use shared statistics to identify the best split.For classification, the shared counts support computing class fractions and evaluating Gini impurity.
  • Distributed prediction has clients update an encrypted prediction vector in round-robin order, preserving only the path-consistent predicted output during prediction.Each client eliminates incompatible paths using its local feature values before passing the encrypted vector onward.
  • The protocol’s basic security theorem states that it securely realizes the training and prediction functionalities against a semi-honest adversary corrupting up to m −1 of m clients.

5. ENHANCED PROTOCOL

The basic protocol can leak training labels and feature values when clients collude using plaintext tree information. The enhanced protocol conceals split thresholds and leaf labels, improving privacy at a cost to efficiency and interpretability.

  • 5.1 PRIVACY LEAKAGES: Plaintext tree models enable colluding clients to infer training labels or feature values from split information and their own data.Label leakage occurs without a super client feature on a path; feature-value leakage can occur when the super client participates in collusion.
  • 5.1 PRIVACY LEAKAGES: Colluding clients can infer class labels for samples partitioned by known feature splits and plaintext leaf labels.In the example, clients infer class 2 for samples satisfying D_age > 30 ⋀ deposit ≤5000, and the opposite class for the remaining subset.
  • 5.1 PRIVACY LEAKAGES: Colluding clients can infer target-client feature values after identifying a node’s sample set and separating it using the super client’s labels.The example infers deposit ≤5000 for one label-defined subset and the converse for the other.
  • 5.2 HIDING LABEL AND SPLIT THRESHOLD: Leaf labels are encrypted rather than reconstructed in plaintext, preventing clients from directly observing them.Clients encrypt their secret shares and combine them using homomorphic addition.
  • 5.2 HIDING LABEL AND SPLIT THRESHOLD: The enhanced protocol hides internal split thresholds through private split selection and encrypted mask-vector updating.An encrypted indicator vector privately selects the split, while homomorphic operations update the encrypted sample mask.
  • 5.2 HIDING LABEL AND SPLIT THRESHOLD: Releasing less model information increases privacy but reduces efficiency and interpretability.The paper frames this as a trade-off in the released model.
  • 5.2 HIDING LABEL AND SPLIT THRESHOLD: The enhanced protocol securely realizes model training and prediction against a semi-honest adversary corrupting up to m−1 of m clients.Its additional privacy computations use threshold Paillier encryption and MPC conversion.

6. THEORETICAL ANALYSIS

The paper analyzes computational costs for Pivot’s basic and enhanced protocols, separating expensive threshold decryption and secure comparison operations. Enhanced training is more costly, while prediction depends on the client count and computation costs.

  • 6. THEORETICAL ANALYSIS: The analysis models homomorphic, secret-sharing, threshold-decryption, and secure-comparison costs separately for training and prediction.Ce and Cs denote encrypted-value and secretly shared-value computation costs; Cd and Cc denote threshold decryption and secure comparison.
  • 6. THEORETICAL ANALYSIS: Basic prediction costs O(mt)Ce + O(1)Cd, whereas enhanced prediction includes O(t)(Cs + Cc).Here t is the number of internal nodes in the analyzed prediction procedure.
  • 6. THEORETICAL ANALYSIS: Enhanced training always costs more than basic training because private split selection and encrypted mask-vector updating add computations.The comparison concerns computational cost, while prediction superiority depends on m and the relationship between ciphertext and secure computation costs.

7. EXTENSIONS TO OTHER ML MODELS

Pivot extends from single decision trees to random forests and GBDTs, while its reusable primitives also support other vertical federated models. The GBDT extension protects intermediate training labels but requires additional computation.

  • 7.1 RANDOM FOREST: Pivot extends to random forests by building trees separately and aggregating encrypted tree predictions through voting or averaging.Classification uses secure maximum computation for majority voting; regression uses homomorphic computation of the mean.
  • 7.2 GRADIENT BOOSTING DECISION TREE: GBDT requires protecting each round’s intermediate training labels from the super client while sequentially building trees.The next tree’s labels are prediction losses derived from previous trees.
  • 7.2 GRADIENT BOOSTING DECISION TREE: A GBDT regression forest keeps round-specific labels encrypted and computes subsequent labels from encrypted predictions and prior labels.The paper describes this for W rounds, with one regression tree built per round.
  • 7.2 GRADIENT BOOSTING DECISION TREE: The GBDT optimization reduces cost by updating encrypted intermediate values and the mask vector once at the beginning of each round.The client holding the best split performs the update and broadcasts the resulting values.
  • 7.2 GRADIENT BOOSTING DECISION TREE: GBDT classification uses one-vs-the-rest, training W ∗c regression trees across c classes.After each round, clients obtain c trees and encrypted prediction outputs for each training sample.
  • 7.3 OTHER MACHINE LEARNING MODELS: Pivot’s threshold-encryption, conversion, and secure-computation primitives can also be reused for vertical logistic regression and neural networks.The paper illustrates vertical logistic regression with encrypted weights, secret-shared aggregation, and encrypted weight updates.

8. EXPERIMENTS

The experiments evaluate Pivot’s accuracy and efficiency for decision trees and ensemble extensions under varying system and model parameters. Pivot achieves accuracy comparable to non-private baselines, while protocol variants and parallel decryption substantially affect runtime.

  • Experimental design: Experiments evaluate Pivot’s basic and enhanced protocols for decision trees and ensemble extensions, measuring accuracy, training time, and prediction time.The efficiency evaluation varies clients, samples, per-client features, splits, tree depth, and ensemble size.
  • Experimental design: Accuracy is compared against non-private decision tree, random forest, and gradient boosting baselines on three real-world datasets.Each accuracy experiment uses 10 independent trials and reports the average result.
  • Accuracy evaluation: Pivot algorithms achieve accuracy comparable to non-private baselines, with slight losses attributed to fixed-point truncation and unoptimized basic implementations.Table 3 reports the model-accuracy comparison for Pivot-DT, Pivot-RF, and Pivot-GBDT.
  • Training efficiency: Training time increases with the number of clients because threshold decryption and secure computations require more communication rounds.Pivot-Enhanced is slower than Pivot-Basic because additional model-update computations are dominated by O(n) ciphertext multiplications.
  • Training efficiency: 2.7 times is the maximum reported training-time reduction from parallelizing threshold decryption in Pivot-Enhanced-PP.The secure computations remain unparallelized, while threshold decryption uses parallelism.
  • Prediction efficiency: Pivot-Enhanced prediction is slower than Pivot-Basic at larger client counts, while Pivot-Basic outperforms it when tree depth h ≥3.Pivot-Basic’s prediction communication scales linearly with m, whereas Pivot-Enhanced uses a stable number of secure comparisons as m grows.
  • Baseline comparison: Pivot-Basic and Pivot-Enhanced achieve up to about 19.8x and 4.5x speedup over SPDZ-DT, respectively, as client count increases.At n = 200K, the reported speedups over SPDZ-DT are about 37.5x for Pivot-Basic and 1.8x for Pivot-Enhanced.

9. FURTHER PROTECTIONS

The paper extends Pivot beyond its semi-honest setting with mechanisms for malicious security and differential privacy. These extensions use verifiable computation and noise addition to strengthen protection during training and prediction.

  • 9.1 Extension to Malicious Model: Pivot is extended to address malicious adversaries, who may deviate from the protocol to infer private data.The extension targets behaviors such as omitting an encrypted share before threshold decryption.
  • 9.1 Extension to Malicious Model: Zero-knowledge proofs and authenticated shares in SPDZ verify local computations and detect incorrect reconstructions under malicious behavior.Incorrect verification causes the execution to abort.
  • 9.1 Extension to Malicious Model: The maliciously secure extension commits training data and verifies split selection, encrypted statistics, pruning checks, leaf labels, and prediction updates.Clients prove that computations use the committed split and label indicator vectors throughout training.
  • 9.1 Extension to Malicious Model: The enhanced protocol hides the selected split threshold by privately selecting its indicator vector from a secretly shared selection mask.This uses homomorphic dot products with a committed split-indicator matrix.
  • 9.2 Incorporating Differential Privacy: The differential-privacy extension adds secretly shared Laplace noise to count queries before pruning and leaf-label computation.The count-query sensitivity is Δ=1, and the per-query noise is Lap(Δ/ϵ).
  • 9.2 Incorporating Differential Privacy: The resulting training guarantee is ϵB-DP with ϵB = 2(h + 1)ϵ under computational differential privacy.Each tree node consumes 2ϵ because the pruning-condition query is required.

10. RELATED WORK

Prior approaches to privacy-preserving vertical tree learning either reveal sensitive intermediate information, require plaintext labels, or rely on strong infrastructure assumptions. Pivot instead keeps intermediate training and prediction information hidden.

  • Privacy-preserving vertical tree models: Existing vertical tree solutions may reveal labels or intermediate information in plaintext, compromising client data privacy.Some methods disclose the available sample IDs on tree nodes or the prediction path.
  • General privacy techniques: Secure hardware approaches rely on a trusted third party and remain vulnerable to side-channel attacks.These assumptions are unacceptable to many organizations.
  • General privacy techniques: MPC-based alternatives can require data outsourcing to multiple non-colluding servers, making their assumptions difficult to ensure in practice.The paper characterizes this non-collusion requirement as strong.
  • Collaborative prediction: Unlike prior collaborative prediction methods, Pivot reveals no intermediate information beyond the final prediction output in the vertical FL setting.This addresses leakage of the prediction path when clients jointly hold model shares and feature subsets.

11. CONCLUSIONS

The paper presents Pivot as a privacy-preserving solution for vertical tree-based models with basic and enhanced protocols. Its experiments report comparable accuracy to non-private algorithms and high efficiency.

  • Contributions: Pivot provides two protocols for privacy-preserving vertical tree-based models.The basic protocol hides intermediate information, while the enhanced protocol mitigates additional privacy leakages.
  • Privacy guarantees: The basic protocol guarantees that no intermediate information is disclosed during execution.The enhanced protocol further mitigates leakages that may occur in the basic protocol.
  • Empirical findings: Pivot achieves accuracy comparable to non-private algorithms and is highly efficient in the reported experiments.
Loading 2008.06170v1…