Year: 2021

Abstract:
Vertical Federated Learning (VFL) enables multiple clients to collaboratively train a global model over vertically partitioned data without revealing private local information. Tree-based models, like XGBoost and LightGBM, have been widely used in VFL to enhance the interpretation and efficiency of training. However, there is a fundamental lack of research on how to conduct VFL securely over distributed labels. This work is the first to fill this gap by designing a novel protocol, called FEVERLESS, based on XGBoost. FEVERLESS leverages secure aggregation via information masking technique and global differential privacy provided by a fairly and randomly selected noise leader to prevent private information from being leaked in the training process. Furthermore, it provides label and data privacy against honest-but-curious adversary even in the case of collusion of n − 2 out of n clients. We present a comprehensive security and efficiency analysis for our design, and the empirical results from our experiments demonstrate that FEVERLESS is fast and secure. In particular, it outperforms the solution based on additive homomorphic encryption in runtime cost and provides better accuracy than the local differential privacy approach1.

heading: 1 INTRODUCTION
text: Traditional centralized deep learning models, demanding to collect a considerable amount of clients’ data to maintain high accuracy, to some degree, may increase the risk of data breaches. Data may not be easily shared among different entities due to privacy regulations and policies. To tackle this “Data Island” problem (Yang et al. (2019a)), Google proposed Federated Learning (FL) (McMahan et al. (2017)) to allow multiple clients to train a global model without sharing private data. The basic paradigm of FL is that all clients train local models with their own data, and then the information of local models, e.g., gradients, may be exchanged to produce a global model.
Based on different types of data partition (Yang et al. (2019a)), FL can be mainly categorized into Horizontal Federated Learning (HFL) and Vertical Federated Learning (VFL). The former focuses on training with horizontally partitioned data where clients share the same feature space but differing in data index set. Several research works (Shokri & Shmatikov (2015); Orekondy et al. (2019); Geiping et al. (2020); Li & Han (2019)) have found that training data of HFL is still at high risk of leakage although private data is kept locally. Other studies (Phong et al. (2018); Truex et al. (2019); Xu et al. (2019); Zhang et al. (2020); Zhu et al. (2020)) have been dedicated to enhancing the security of HFL. On the contrary, VFL is mainly applied in the scenario of training with vertically partitioned data (Wu et al. (2020); Cheng et al. (2021)) where clients share the same data index set but differing in feature space. In this paper, our principal focus is to achieve privacy-preserving training on VFL.
To best of our knowledge, many existing studies (Hardy et al. (2017); Nock et al. (2018); Liu et al. (2020); Yang et al. (2019b); Cheng et al. (2021); Chen & Guestrin (2016); Wu et al. (2020)) have proposed innovative approaches to prevent private information breaches in the context of VFL. Specifically, (Hardy et al. (2017)) introduced encryption-based privacy-preserving logistic regression to safeguard the information of data indexes. (Nock et al. (2018)) gave a comprehensive discussion on
1Code is available at: https://github.com/feverless111/vfl
the impact of ID resolution. (Yang et al. (2019b)) introduced a scheme without using a coordinator for a limited number of clients. Recently, (Liu et al. (2020)) proposed an asymmetrically VFL scheme for logistic regression tackling privacy concerns on ID alignment.
Unlike the training models used in the aforementioned works, XGBoost (Chen & Guestrin (2016)), which is one of the most popular models applied in VFL, can provide better interpretation, easier parameter tuning, and faster execution than deep learning in tabular data training (Goodfellow et al. (2016); LeCun et al. (2015)). These practical features and advantages draw academia and industry’s attention to the research on XGBoost, especially in the privacy-preserving context. (Wu et al. (2020)) introduced an approach for tree-based model training through a hybrid method composing homomorphic encryption and secure Multi-Party Computation (MPC) (Goldreich (1998); Bonawitz et al. (2017)). After that, (Cheng et al. (2021)) proposed a similar system to train XGBoost (Chen & Guestrin (2016)) securely over vertically partitioned data by using Additively Homomorphic Encryption (AHE). By applying Differential Privacy (DP) (Dwork (2008)), (Tian et al. (2020)) designed a VFL system to train GBDT without the need of encryption/decryption.
However, most of the above solutions based on AHE and MPC do not scale well in terms of efficiency on training XGBoost. Beyond that, all the existing schemes basically assume that training labels are managed and processed by a sole client. In practice, a VFL scheme supporting distributed labels is necessary. For instance, multiple hospitals, clinics and health centers currently may be set to COVID-19 test spots and aim to train a model, e.g., XGBoost, to predict with good interpretation if citizens (living in various locations) are infected based on their health records and symptoms. In this context, the labels (i.e., the test results) are likely distributed among different health authorities - even targeting to the same group of patients, and feature space is vertically portioned. For example, a cardiac hospital only maintains heart data for the patients, while a psychiatric center holds the mental records, in which both authorities may collect and manage each of its registered patient’s label locally. Another common scenario could be in the financial sector where multiple bank branches and e-commerce companies prefer to build a global model to predict if their customers may pay some service (e.g., car loan) on time. The banks have part of features about the customers (e.g., account balance, funding in-and-out records), while the companies may obtain other features (e.g., payment preference). Since the customers may get the same service, e.g., loan, from different institutions, it is clear that labels must be distributed rather than centralized. In addition to efficiency and functionality aspects, one may also consider capturing stronger security for VFL. Training an XGBoost usually should involve the computation of first and second-order derivatives of the loss function (note gradients and hessians contain labels’ information), and the aggregation of them is required in each round. In the context where the labels are held by different clients, if the gradients and hessians are transmitted in the form of plaintexts and the summations of them are known to an aggregator (whom could be one of the clients engages in training), inference and differential attacks (Appendix C) will be easily conducted by the aggregator, resulting in information leakage.
To tackle these problems, we propose a fast and secure VFL protocol, FEVERLESS, to train XGBoost (Appendix B.1) on distributed labels without disclosing both feature and label information. In our design, the privacy protection is guaranteed by secure aggregation (based on a masking scheme) and Global Differential Privacy (GDP) (Appendix B.6). We leverage masking instead of heavy-cost multiparty computation and we guarantee a “perfect secrecy” level for the masked data. In GDP, we use Verifiable Random Function (VRF) (Appendix B.5) to select a noise leader per round (who cannot be predicted and pre-compromised in advance) to aggregate noise from “selected” clients, which significantly maintains model accuracy.
Our contributions can be summarized as follows. (1) We define VFL in a more practical scenario where training labels are distributed over multiple clients. Beyond that, we develop FEVERLESS to train XGBoost securely and efficiently with the elegant combination of secure aggregation technique (based on Diffie-Hellman (DH) key exchange (Appendix B.2) and Key Derivation Function (KDF) (Appendix B.4)) and GDP. (2) We give a comprehensive security analysis to demonstrate that FEVERLESS is able to safeguard labels and features privacy in the semi-honest setting, but also maintain the robustness even for the case where n− 2 out of n clients commit collusion. (3) We implement FEVERLESS and perform training time and accuracy evaluation on different realworld datasets. The empirical results show that FEVERLESS can maintain efficiency and accuracy simultaneously, and its performance is comparable to the baseline - a ”pure” XGBoost without using any encryption and differential privacy. Specifically, training the credit card and bank marketing
datasets just takes 1% and 6.5% more runtime than the baseline and meanwhile, the accuracy is only lower than that of the baseline by 0.9% and 3.21%, respectively2.

heading: 2 PROBLEM FORMULATION

heading: 2.1 SYSTEM MODEL
text: Before proceeding, we give some assumptions on our model. We suppose that a private set intersection (Kolesnikov et al. (2017); Pinkas et al. (2014)) has been used to align data IDs before the training starts, so that each client shares the same data index space I. But the names of features are not allowed to share among clients. As for the information of label distribution (indexes indicating a label belongs to which client, e.g., the label of i-th data instance is held by client A), we will consider the following conditions: (1) this information is revealed to the public in advance; or (2) the information is not allowed to publish but the training can still be accomplished (with extra cost).
We also consider that the training is conducted on a dataset with m samples composing with feature space X = {x1, · · · , xm}, each containing f features, and label set Y = {y1, · · · , ym}. Besides, features {X(c)j | j ∈ {1, · · · , f}} and labels {y (c) i | i ∈ {1, · · · ,m}} are held among n clients where each client has at least one feature and one label. X(c)j and y (c) i refer to j-th feature and i-th label owned by c-th client, respectively.
Considering a practical scenario wherein training labels are distributed among clients, we propose a new variant of VFL, named VFL over Distributed Labels (DL-VFL). The concrete definition is given as follows. Definition 1 (DL-VFL). Given a training set with m data samples consisting of feature space X , label space Y , index space I and clients set C, we have:
X c ∩ X c ′ = ∅,Yc ∩ Yc ′ = ∅, Ic = Ic ′ ,∀c, c ′ ∈ C, c 6= c ′ . (1)
A client c participating DL-VFL shares the same sample ID space I with the corresponding labels, where a single label belongs to only one client. And different clients hold the subset of X sampled from feature space. To achieve privacy-preserving XGBoost training, we further define two roles. Definition 2 (Source client). A source client with split candidates wants to compute the corresponding Lsplit based on Eq.(4). But some labels are missing so that ∑ gi and ∑ hi are unable to derive.
For the case that a source client does not hold all labels in the current split candidates, we propose a solution based on secure aggregation and global differential privacy to help the source client to compute Lsplit while safeguarding other clients’ privacy. We consider the two conditions regarding if label distribution is publicly known. We find that if we keep label distribution hidden, we will take extra communication overhead to perform training. The detailed explanation is given in Appendix F. Note each client may have a chance to act as a source client because all the labels are distributed, where the source client leads the Lsplit computation, and clients provide missing label values to the source client.
To achieve GDP, we define noise leader who is selected fairly and randomly from all clients (except for the source client) - preventing clients from being compromised beforehand. Definition 3 (Noise leader). By using VRF, a noise leader is responsible for generating the maximum leader score, aggregating differentially private noise from a portion of clients and adding the noise to the gradients and hessians.
Note we summary the main notations in Table 1 (see Appendix A).

heading: 2.2 THREAT MODEL
text: We mainly consider potential threats incurred by participating clients and the outside adversaries. We assume that all clients are honest-but-curious, which means they strictly follow designed algo-
2For banknote authentication dataset, FEVERLESS takes 13.96% more training time than the baseline, and the accuracy is 30.4% lower. This is because the model is trained by a small-scale dataset, so that the robustness is seriously affected by noise.
rithms but try to infer private information of other clients from the received messages. Besides, we also consider up to n − 2 clients’ collusion to conduct attacks, and at least one non-colluded client adds noise per round. Through authenticated channels, DH key exchange can be securely executed among clients. Other messages are transmitted by public channels, and outside attackers can eavesdrop on these channels and try to reveal information about clients during the whole DL-VFL process. Note this paper mainly focuses on solving privacy issues in training DL-VFL based on XGBoost. Thus, other attacks, like data poisoning and backdoor attacks deteriorating model performance, are orthogonal to our problem.

heading: 3 A PRACTICAL PRIVACY-PRESERVING PROTOCOL

heading: 3.1 FEVERLESS PROTOCOL DESCRIPTION
text: To prevent a source client from knowing gradients and hessians sent by other clients, one may directly use MPC (Damgård et al. (2012)) based on AHE (Paillier (1999); Wu et al. (2020)). But this method yields expensive computation cost. Getting rid of the complex mechanism like MPC, we leverage secure aggregation protocol via masking scheme based on DH key exchange(Bonawitz et al. (2017); Ács & Castelluccia (2011); Tian et al. (2020)). By further using KDF and Hash Function (see Appendix B.3&B.4), our masking (for gradients and hessians) can be derived without exchanging keys per training round. Our approach significantly reduces the communication cost but still maintains the robustness up to n − 2 colluded clients. Meanwhile, the secure aggregation can provide “perfect secrecy” for broadcast messages. After receiving the broadcast messages, the masking will be canceled out at the source client side. But only using the masking is unable to defend against differential attacks. One may consider using Local Differential Privacy (LDP) (Kairouz et al. (2014)) to make sure that each client may add noise to per send-out message, barely consuming any extra computation cost. The accumulated noise, from all clients, may seriously affect the model accuracy. To tackle this problem, we use a GDP (Wei et al. (2020)) approach with noise leader selection. A hybrid method is finally formed based on masking scheme and GDP, so that per client’s sensitive information can be protected by the “masks” and the aggregated values are secured by the noise which is injected by the chosen clients.
We briefly introduce our design, and the detailed algorithms and more explanations are given in Appendix D. Assume each client c ∈ [1, n] generates respective secret key skc and computes gradients g
(c) i and hessians h (c) i locally, where {i | yi ∈ Yc}. FEVERLESS works as follows.
1. Broadcast missing indexes. The source client broadcasts the mIDs= {i | yi /∈ Yc}. 2. Key exchange computation. Each client c computes public key pkc = gskc using secret keys skc, sends pkc to other clients and computes the corresponding shared keys3 {Sc,c′ = pk skc c′
= gskcskc′ | c, c ′ ∈ C, c 6= c′} based on secret key skc received public keys {pkc′ | c
′ ∈ C}. 3. Data masking. Each client c runs the masking generation algorithm to compute the maskings for protecting gradients and hessians. Specifically, based on KDF, clients’ indexes and the
number of queries, the masking generation algorithm is conducted by mask(c)g ← ∑ c 6=c′ ∣∣∣c−c′ ∣∣∣ c−c′ ·(
H(Sc,c′‖0‖query) ) , mask(c)h ← ∑ c 6=c′ ∣∣∣c−c′ ∣∣∣ c−c′ · ( H(Sc,c′‖1‖query) ) 4. Then the masked gra-
dients G(c) and hessians H(c) are generated by G(c) = ∑ i∈mIDs g (c) i + mask
(c) g −r(c)g , H(c) =∑
i∈mIDs h (c) i + mask (c) h −r (c) h .
4. Noise leader selection. Each client generates the selection score selecc using the VRF, H(SIGNskc(count,mIDs,r)), and broadcasts it, where count is the number of times clients conduct VRF, r is a fresh random number, and SIGN is the signature scheme (see Appendix B.5 for more details). The client with maximum score will be the noise leader. For ease of understanding, we assume client n with the largest selection score selectmaxn is the leader, in Figure 1.
3Shared keys are only generated once, and the KDF is used to generate the remaining maskings. 4For purpose of simplicity, we omit modular computations. The complete calculation processes are elabo-
rated on Algorithm 3-5.
5. Noise injection. a) Noise leader selects k clients adding noise. For the details of the selec-
tion, please see Algorithm 5 in Appendix D. b) The selected clients send {ñ(c)g = N(0,∆2gσ2) +
r (c) g , ñ (c) h = N(0,∆ 2 hσ 2) + r (c) h |c ∈ k} to noise leader, in which the r (c) g and r (c) h are two random values to mask noise. c) The leader aggregates the noise: Ñg = k · N(0,∆2gσ2) + Rg and Ñh = k · N(0,∆2hσ2) +Rh, and further adds them to G(n) and H(n), respectively. 6. Aggregation and computation. All clients send the masked values to the source client. The source client computes ∑n c=1G (c) + k·N(0,∆2gσ2), ∑n c=1H
(c) + k·N(0,∆2hσ2) and Lsplit. 7. Final update. The source client with maximum Lsplit updates model following XGBoost (Chen & Guestrin (2016)) and broadcasts the updated model and data indexes in child nodes as step 8.
Figure 1 gives an overview of FEVERLESS. Note this process can be conducted iteratively. For simplicity, the core calculation processes are shown here, and more details are in Appendix D.

heading: 3.2 THEORETICAL ANALYSIS
text: Computation cost: We use B and d to denote the number of buckets and the maximum depth respectively, and f (c) here represents the number of features held by a client c. For each client c, the computation cost can be divided into 4 parts: (1) Performing at most f (c) · B · NT · (2d − 1) times computation of Lsplit and w, taking O(f (c) · B · NT · 2d) time; (2) Creating n − 1 shared keys and 1 public key, which is O(n); (3) Conducting O(f (c) · B · NT · 2d) time to compute VRF outputs, select noise leader and generate noise; (4) Generating 2f (c) · B · NT · (2d − 1) maskings, which takes O(f (c) ·B ·NT · 2d ·n) time. Overall, each client’s computation complexity is O(f (c) ·B ·NT · 2d · n). Communication cost: Each client’s communication cost can be calculated as (1) Broadcasting at most f (c) · B · NT · (2d − 1) times of missing indexes mID; (2) Broadcasting 1 public key and receiving n − 1 public keys from other clients; (3) Broadcasting 1 leader selection score and sending noise to noise leader at most f (c) · B · NT · (2d − 1) times; (4) Sending source client 2 masked gradients and hessians of size 2dlog2Ne. Therefore the overall communication cost is f (c) · B · NT · (2d − 1) · (‖mID‖ · αI + αL + αN + n · αK2dlog2Ne), where αI , αL, αN and
αK refer to the number of bits of index, leader selection score, noise and public keys, respectively. Thus, we have the communication complexity O(f (c) ·B ·NT · 2d).

heading: 3.3 SECURITY ANALYSIS
text: We prove that FEVERLESS provides label and data privacy against an adversary controlling at most n − 2 clients in the semi-honest setting (Smart (2016)). Here, we provide a brief summary of our analysis and theorems. The formal proofs, in the random oracle model, are given in Appendix E. Label Privacy: Label privacy implies that the owner of a label among honest parties should not be leaked to the adversary. We achieve this by using a secure aggregation mechanism where the masks are created via DH key exchange and KDF. In brief, we show that because of the Decisional DH problem (see Definition 4), the adversary cannot distinguish the individual values from randomly chosen ones. That is why the adversary A cannot learn the owner of the label. Data Privacy: FEVERLESS provides data privacy, meaning that an adversary A cannot extract the data of any honest party. Individual data values are not separable from random values because of the secure masking. If the source client is not part of the adversary, no data information is leaked. But we require an additional countermeasure for the case where the source client is part of the adversary because it can collect the summation of the data values. We use differential privacy (Dwork et al. (2006a;b)) to achieve data privacy. Because of the noise added by differential privacy, the adversary cannot learn the individual data of an honest client. Moreover, we select the noise clients by the VRF which ensures that the noise leader cannot be predicted or compromised in advance.
Theorem 3.1 (A not including source client). There exists a PPT simulator Sim for all |C| := n ≥ 3, |X | := f ≥ n, |Y| := m ≥ 1, ⋃ c∈C X (c), ⋃ c∈C Y(c) and A ⊂ C so that |A| ≤ n− 2, the output of Sim is indistinguishable from the output of REAL : REALC,X ,YA (X C ,YC) ≡ Sim C,X ,Y A (XA,YA).
Theorem 3.2 (A including source client). There exists a PPT simulator Sim for all |C| := n ≥ 3, |X | := f ≥ n, |Y| := m ≥ 1, ⋃ c∈C X (c), ⋃ c∈C Y(c) and A ⊂ C so that |A| ≤ n− 2, the output of Sim is indistinguishable from the output of REAL:REALC,X ,YA (X C ,YC) ≡ Sim C,X ,Y A (G,H,XA,YA)
where G = ∑ i∈mIDs g (c) i + N(0, (∆gσ) 2), H = ∑ i∈mIDs h (c) i + N(0, (∆hσ) 2).
Theorem 3.3 (Privacy of the Inputs). No A ⊂ C such that |A| ≤ n − 2 can retrieve the individual values of the honest clients with probability 1 − ∑k̂ i=0 C i hC k̂−i n−2−h(Pt) k̂(1 − Pt)(n−k̂) Ck k̂−i Ck
k̂
, where
h and k̂ refer to the number of non-colluded clients and the number of clients who have selection score larger than threshold, respectively; and Pt is the probability of selection score larger than the threshold.

heading: 4 EXPERIMENT
text: We perform evaluations on accuracy, runtime performance and communication cost, and compare our design with two straightforward secure approaches: one is based on LDP (for accuracy), and the other is built on AHE with GDP (for runtime). These approaches are most-commonly-used components for privacy-preserving FL, and they could be the building blocks for complex mechanisms, e.g., MPC. We note the protocol should intuitively outperform those MPC-based solutions, and one may leverage our source code to make further comparison if interested. In the experiments, the baseline, which is the pure XGBoots algorithm, follows the training process of Figure 1 without using any privacy-preserving tools (steps Ë - Î). And LDP does not conduct DH key exchange but each client injects noise into the aggregation of gradients and hessians, while AHE follows Figure 1 except executing DH key exchange. In AHE, each client sends (additive) encrypted messages to source client after step Î. We here show the performance of the best case where there is only one (non-colluded and randomly selected) client adding noise per round (k = 1). For other results (where k 6= 1), see Appendix H.2. Note we present the communication cost in Appendix H.5).

heading: 4.1 EXPERIMENT SETUP
text: To present comprehensive results on accuracy, we set to be: 10, 5, 2 and 1, and δ is set to 10−5. In terms of accuracy and runtime, we evaluate different situations by varying the number of clients, the number of trees, and the maximum depth of trees (from 2 to 10). Other parameters regarding to training follow the suggestions in (Chen & Guestrin (2016)) and the library 5 of XGBoost. To deliver fair results, we conduct each test for 20 independent trials and then calculate the average.
Datasets. We run the experiments on three datasets - Credit Card (Yeh & Lien (2009)), Bank Marketing (Moro et al. (2014)) and Banknote Authentication6 - for classification tasks. To fairly investigate the model performance in DL-VFL, we make the labels as sparse as possible, and they are uniformally distributed on clients. We give the more details of experiment setup in Appendix G.

heading: 4.2 EVALUATION ON ACCURACY
text: In Figure 2, we present a clear picture on the accuracy performance based on the #tree and the maximum depth in (2, 10−5)−DP. We merge the #client in one tree structure, which means in one bar, and the value is the mean of accuracy when conducting on different numbers. The accuracy of the baseline in credit card (about 0.82) and bank marketing (nearly 0.9) remains unchanged as the #tree and maximum depth increases, while the accuracy in banknote authentication rises from 0.9 to approximately 1.0. To highlight the differences and ensure all results to be displayed clearly, we set the ranges of accuracy as [0.5, 0.9], [0.5, 1] and [0, 1] for the three datasets, respectively. Note the performance based on the #client is given in Appendix H.1. Comparing with the baseline, shown in the top and middle rows of the Figure 2, FEVERLESS and LDP suffer from continuously shrinking accuracy as tree structure becomes complex. This is so because the injected noises are accumulated into the model via the increase of query number. And the accuracy is easily affected by the depth. In the worst case where the #tree and maximum depth are both equal to 10, FEVERLESS decreases 10.37% (resp. 14.98% ), and LDP drops 24.78% (resp.24.59%) in credit card (resp. bank marketing). But on average, FEVERLESS’ accuracy only shrinks by around 0.9% (resp. 3.21%), while LDP suffers from estimated 3x (resp. 2x) accuracy loss. The difference in the degree of deterioration mainly comes from how much noise is added for each query. We note the deterioration of FEVERLESS is independent with the #client. Thus, we can maintain great accuracy even for the case where there exists a considerable amount of clients.
Despite the fact that less noise is added in FEVERLESS, we do not predict that the accuracy falls to the same level (around 50%, like randomly guess in binary classification) as LDP in the bottom row of Figure 2. This is so because the model is trained by an extremely small-size dataset, which makes it hard to maintain the robustness but relatively sensitive to noise. If setting a larger , we may see our advantage more clear. The experiments conducted on banknote authentication dataset with larger are given in Appendix H.3
To distinguish the performance between FEVERLESS and LDP more clearly, Figure 3 shows the comparison over different , when #depth and #tree are set to 10. The performance of the model is decayed as the decrease of . In the left (resp. middle) of the Figure 3, the averaged accuracy of FEVERLESS falls from 0.7686 to 0.5967 (resp. from 0.8517 to 0.6831), while that of LDP also decreases to 0.5299 (resp. 0.5853). We notice that the highest values of LDP stay at the same level as those of FEVERLESS. This is because, in the case of 2-client training, only one client needs to add the noise in LDP (which is identical to our GDP solution). At last, the worse case can be seen in the right of the Figure 3 due to the weak robustness of the model obtained from the banknote authentication. The results are much far away from the baseline there. But even in this case, FEVERLESS still holds a tiny advantage over LDP.

heading: 4.3 EVALUATION ON TRAINING TIME
text: To highlight the runtime complexity, we average the results varying by client number into one tree structure as well. We further set the ranges of time as [0s, 9,500s], [0s, 3,500s] and [0s, 110s] for the datasets to deliver visible results. Note since the banknote dataset contains the least samples, it
5https://xgboost.readthedocs.io/ 6https://archive.ics.uci.edu/ml/datasets/banknote+authentication
does deliver the best training efficiency here. Figure 4 presents the comparison on the training time by varying maximum depth and the number of trees among the datasets.
The training time increases exponentially and linearly with depth and the number of tree, which is consistent with our analysis given in Section 3.2. In Figure 4, compared with the baseline, the runtime of FEVERLESS at most increases 110.3s (resp. 50s, 4.3s), while AHE requires around 70x spike (resp. 48x, 21x) in credit card (resp. bank marketing, banknote authentication), where #depth and #trees are equal to 10. For the average case, FEVERLESS consumes Approx. 1%(resp.6.5%, 13.96%) more training time than the baseline, while AHE requires the 351%(resp.155.1%, 674%) extra, w.r.t. the three datasets. Its poor performances are due to the laborious calculations in encryption, in which each client has to conduct an encryption per query. By contrast, the masksings in FEVERLESS avoid these excessive costs. We further investigate the runtime performance on the #client in Appendix H.

heading: 5 CONCLUSION AND FUTURE WORK
text: We consider a practical scenario where labels are distributedly maintained by different clients for VFL. By leveraging secure aggregation and GDP, we present a novel system, FEVERLESS, to train XGBoost securely. FEVERLESS can achieve perfect secrecy for label and data, and adversaries cannot learn any information about the data if the source client is not corrupted. With DP against differential attack, the source client knows nothing more than summation. Our design is also robust for the collusion of n−2 out of n clients. The experiment results show that FEVERLESS is fast and accurate, only taking 1% extra training time, and sacrificing 0.9% accuracy, as compared to the pure XGBoost. In Appendix F, we discuss how to reduce noise, hide distribution of labels and use other security tools. Although our system achieves great performance in terms of security and efficiency, its accuracy still does not work well in small-scale datasets. This remains an open problem. And we will also consider secure solutions against malicious adversaries.

heading: A NOTATIONS
text: The frequently used notations are summarized in Table 1.

heading: B PRELIMINARIES
text: B.1 XGBOOST
XGBoost (Chen & Guestrin (2016)) is a popular tree-based model in tabular data training that can provide better interpretation, easier parameters tuning and faster execution speed than deep learning Goodfellow et al. (2016); LeCun et al. (2015). It also outperforms other well-known boosting tree systems in terms of accuracy and efficiency, like Spark MLLib Meng et al. (2016) and H2O Chen & Guestrin (2016), especially for large-scale datasets. Therefore, in this paper, we consider using XGBoost as a building block for classification tasks.
Assume that a training set with m data points composing with feature space X = {x1, · · · , xm} and label space Y = {y1, · · · , ym}. Before training starts, every feature will be sorted based their values, and split candidates will be set for features. XGBoost builds trees based on the determination of defined splits candidates and some pruning conditions. Specifically, computing gradients and hessians first according to Eq.(2) and Eq.(3) for each data entry, where y(t−1)i denotes the prediction of previous tree for i-th data point, and yi is the label of i-th data point:
gi = 1
1 + e−y (t−1) i
− yi = ŷi − yi, (2)
hi = e−y
(t−1) i
(1 + e−y (t−1) i )2
. (3)
For splitting nodes, the XGBoost algorithm determines the best split candidate from all others based on maximum Lsplit in Eq.(4), where λ and γ are regularization parameters:
Lsplit = 1
2 [
∑ i∈IL gi∑
i∈IL hi + λ +
∑ i∈IR gi∑
i∈IR hi + λ −
∑ i∈I gi∑
i∈I hi + λ ]− γ. (4)
The current node will be the leaf node if the following conditions are fulfilled: reaching the maximum depth of tree, the maximum value of impurity is less than preset threshold. The calculation of the leaf value follows Eq.(5):
w = − ∑ i∈I gi∑
i∈I hi + λ . (5)

heading: B.2 DIFFIE-HELLMAN KEY EXCHANGE
text: Based on Decision Diffie-Hellman (DDH) hard problem (Boneh (1998)) defined below, DiffieHellman key exchange (DH) (Diffie & Hellman (1976)) provides a method used for exchanging keys across public communication channels. Without losing generality and correctness, it consists of a tuple of algorithms (Param.Gen, Key.Gen, Key.Exc). The algorithm (G, g, q) ← Param.Gen (1α) generates public parameters (a group G with prime order q generated by a generator g) based on secure parameter α. (ski, pki) ← Key.Gen(G, g, q) allows client i to generate secret key (ski
$←− Zq) and compute public key (pki ← gski ). Shared key is computed by (pk
skj i , pk ski j ) ← Key.Exc(ski, pki, skj , pkj). Inspired by (Bonawitz et al. (2017); Ács & Castelluccia (2011)), we utilize shared keys as maskings to protect information of labels against inference attack during transmitting in public channels. The correctness requires pkskji = pk ski j . The security relies on the DDH problem (Boneh (1998)), which is defined as:
Definition 4 (Decision Diffie-Hellman). Let G be a group with prime order q and g be the fixed generator of the group. The Probabilistic Polynomial Time (PPT) adversary A is given and ga and gb where a and b are randomly chosen. The probability of A distinguishing (ga, gb, gab) and (ga, gb, gc) for a randomly chosen c is negligible:∣∣∣Pr[a, b $←− Zq : A(g, ga, gb, gab) = true]−
Pr [ a, b, c $←− Zq : A(g, ga, gb, gc) = true ]∣∣∣ < negl(α).

heading: B.3 PSEUDO-RANDOM GENERATOR AND HASH FUNCTION
text: Pseudo-Random Generator (PRG) (Håstad et al. (1999)) is an algorithm which is able to generate random numbers. The ”pseudo-random” here means that the generated number is not truly random but has the similar properties with random number. Generally, the pseudo-random numbers are determined by given initial values a.k.a seeds. In cryptographic applications, a secure PRG requires attackers not knowing seeds can distinguish a truly random number from a output of PRG with a negligible probability. Similar with PRG, hash function allows mapping arbitrary size of data to a fixed bit value. For reducing communication cost of FEVERLESS, we use SHAKE-256 (Sha (2015)), one of the hash functions in SHA-3 (Aumasson et al. (2008)) family, to generate customize size of maskings.

heading: B.4 KEY DERIVATION FUNCTION
text: Key Derivation Function (KDF) (Krawczyk & Eronen (2010)) is a kind of hash function that derives multiple secret keys from a main key by utilizing Pesudo-Random Function (PRF) (Kaliski (2005)). In general, KDF algorithm DK ← KDF (mainkey, salt, rounds) derives keys DK based on a main key, a cryptographic salt and current round of processing algorithm. The security requires a secure KDF is robust for brute-force attack or dictionary attack. Inspired by (Zdziarski (2012)) where key shares generated by DH key exchange are converted to AES keys, in this paper, we use KDF to generate maskings for every round to reduce communication cost. The main key we use is generated by DH key exchange.
B.5 VERIFIABLE RANDOM FUNCTION
Verifiable Random Function (VRF) (Micali et al. (1999)) is a PRF providing verifiable proofs of correctness of outputs. It is a tool widely used in cryptocurrencies, smart contracts and leader selection in distributed systems (Micali (2016)). Basically, given a input x, a signature scheme and a hash function, a practical leader selection scheme with VRF (Micali (2016)) works as:
Sleader ← H(signski(x)) (6) where ski is the secret key for i-th client, and the maximum leader score Sleader is used to determine leader. The security and unforgeability of VRF requires that the signature scheme has the property of uniqueness, and hash function is able to map the signature to a random string with fixed size. The correctness of this Sleader is proved by the signature of x.

heading: B.6 DIFFERENTIAL PRIVACY
text: Differential Privacy (DP) (Dwork et al. (2006a;b)) is a data protection system targeting on publishing statistical information of datasets while keeping individual data private. The security of DP requires that adversaries cannot distinguish statistically change from two datasets where an arbitrary data point is different.
The most widely used DP mechanism is called ( , δ)-DP requiring less noise injected than original proposed -DP but with the same privacy level. The formal definition is given as follows. Definition 5. (( , δ) - Differential Privacy) Given two real positive numbers ( , δ) and a randomized algorithm A: Dn → Y , the algorithm A provides ( , δ) - differential privacy if for all data sets D, D
′ ∈ Dn differing in only one data sample, and all S ⊆ Y: Pr[A(D) ∈ S] ≤ exp( ) · Pr[A(D ′ ) ∈ S] + δ. (7)
Note the noise N ∼ N(0,∆2σ2) will be put into the output of the algorithm, where ∆ is l2 - norm sensitivity of D and σ = √ 2 ln(1.25/δ) (Abadi et al. (2016)).

heading: C PRIVACY CONCERN
text: Since we assume feature names are not public information for all clients, and the values of features never leave from clients, the privacy issues are mainly incurred by the leakage of label information.
C.1 INFERENCE ATTACK
During training process, gradients and hessians are sent to source client for Lsplit computation. For classification task, the single gradient is in range (−1, 0)∪(0, 1) for binary classification. According to Eq.(2), a label can be inferred as 1 and 0 if the range is (−1, 0) and (0, 1), respectively. Besides, hessian illustrated in Eq.(3) can leak a prediction of the corresponding data sample. With training processing, the prediction is increasingly closer to a true label. The source client and outside attackers can infer the true label with high probability. Gradients and hessians cannot be transmitted in plaintext. We thus use secure aggregation scheme to protect them from inference attack.

heading: C.2 DIFFERENTIAL ATTACK
text: Differential attack can happen anytime and many times during the calculation of gradients and hessians. Figure 5 describes an example of differential attack taking place in single node split. After sorting feature1, the semi-honest source client defines 2 split candidates and further computes G{2,5} = g2 + g5 and G{1,2,3,5} = g2 + g5 + g1 + g3 for the candidates 1 and 2, respectively. Since the source client holds label 2, even if G{2,5} is derived by secure aggregation, the g5 still can be revealed by G{2,5} − g2. Another example for differential attack is shown in Figure 6. Assume split candidate 1 is the one for splitting root node. In the current tree structure, source client may split right node by computing Lsplit of split candidate 2. In this case, G{1,3} should be aggregated by source client. And the g5 can be revealed by G{1,2,3,5} −G{1,3} − g2, where G{1,2,3,5} is computed in the previous node.

heading: D MORE DETAILS ON FEVERLESS PROTOCOL
text: D.1 XGBOOST TRAINING OVER DISTRIBUTED LABELS
At the initial stage, we allow all clients to agree on a tree structure (maximum depth and the number of trees) and the learning rate for updating prediction. To avoid overfitting problem, we should define regularization parameters. Threshold impurity is also another vital parameter used to identify tree and leaf nodes via the maximum impurity. After that, we should choose , δ for DP, hash function for masking generation and noise leader selection. Besides, we select a multiplicative group G with order q generated by a generator g and a large prime number p to run DH.
At initialization process, all clients set parameters and sort their own feature based on values. Then, split candidates can be defined, and data samples between two different candidates will be grouped as a bucket. At the end, all entries are assigned initialized values to calculate the derivatives of loss function. The detailed algorithm is described as follows.
Algorithm 1: Initialization 1 Set parameters: all clients agree on the maximum depth of a tree d, the number of trees (NT ),
learning rate (η), regularization parameters (λ, γ), the threshold of Lsplit, , δ, p, g, selection portion (p) and hash function
2 for c ∈ [1, n] do 3 for each feature j owned by c do 4 sort(X(c)j ) 5 define buckets: Bjz 6 end 7 set initialized values: ŷi(c) 8 end
After initialization, all clients can invoke Algorithm 2 to train model collaboratively. The inputs are from feature space consisting of features X(c)j and labels y (c) i distributed on different clients, respectively; while the output is a trained XGBoost model that can be used for prediction. Generally, trees are built one by one. And we see from line 4-10 in Algorithm 2 that each client can compute gradients and hessians at beginning of a new tree construction.
Following that, clients are to split current node. Note that XGBoost training in DL-VFL requires each client to calculate G and H . If the labels in some buckets are incomplete, the corresponding
gradients and hessians cannot be computed. Thus, each client should first broadcast missing data index setmID (see line 15-17 in Algorithm 2). Based on the predefined bucketBjz ,mID can be defined if labels in Bjz are not held by clients. In each broadcast, a client sending messages is regarded as a source client. Then others send the corresponding g(c ′ ) i and h (c ′ )
i back to the source client to computeLsplit through Algorithm 3-5 depicted in Appendix D.2. After finding a maximum impurity Lcsplit max, the current node will be split to “left” and “right” nodes if L c split max>threshold Lsplit, in which the value of the split candidate is own by c. In node splitting, clients should set a given
Algorithm 2: Protocol overview
1 Input: {X(c)j | j ∈ f, c ∈ |C|}: features, {y (c) i | i ∈ m, c ∈ |C|}: labels 2 Output: XGBoost model 3 Building trees: 4 for nt ∈ [1, NT ] do 5 for c ∈ [1, n] do 6 for each data entry i owned by c do 7 g
(c) i ← ∂ŷi(c)Loss(ŷi (c), y (c) i )
8 h (c) i ← ∂2ŷi(c)Loss(ŷi (c), y (c) i )
9 end 10 end 11 for each node in the current tree do 12 while current depth <d do 13 for c ∈ [1, n] do 14 for each feature j owned by c do 15 for each Bjz owned by c do 16 BroadcastmID = {i | yi /∈ Yc} 17 end 18 aggregate G, H by Algorithm 3-5 19 compute Lsplit according to Eq.(4) 20 end 21 find the maximum L(c)split and broadcast 22 end 23 L
(c) split max ← max({L (c) split | c ∈ [1, n]})
24 if L(c)split max ≤ threshold Lsplit then 25 set current node as leaf node 26 c computes w and broadcast 27 Break 28 else 29 c splits current node to left node and right node, and broadcasts data index of them. 30 end 31 end 32 set remaining nodes as leaf nodes 33 c computes w and broadcast 34 clients participating in calculation of w: update ŷi(c) 35 end 36 end
node as ”leaf” if current depth reaches the predefined maximum depth or the maximum Lsplit is less than the predefined threshold of Lsplit (see line 12, 24-32 in Algorithm 2). The derivation of leaf value is followed by Eq. 5 where G and H are intaken. Since a leaf node is either “left” or “right” split by one of the clients in C from its parent node, this client knows G and H and leaf value can be derived. Finally, this leaf value will be broadcast, and clients who own the corresponding g(c)i and h
(c) i can use it to update predictions. The details for the above process are shown in Algorithm 2.

heading: D.2 SECURE AGGREGATION WITH GLOBAL DIFFERENTIAL PRIVACY
text: In line 15-19 of Algorithm 2, source client is able to compute Lsplit from the requested missing data indexes and the aggregation of received messages. To avoid that inference and differential attacks are conducted on labels by source client and outside adversaries, we propose a privacy-preserving approach, shown in Algorithm 3-5, to “twist” the DH key exchange, noise leader selection and secure aggregation together. This method represents a viable alternative to train XGBoost securely in DL-VFL without demanding excessive computational resources and affecting model accuracy.
To generate the secure-but-can-be-cancelled-out maskings, we adopt DH here. In Algorithm 3, all clients randomly select numbers as their secret keys and generate the corresponding public keys. For any two clients in the set C, they will exchange public key and compute the corresponding shared keys. For simplicity, we do not describe the signature scheme for DH. We assume DH is conducted on authenticated channels, which means the man-in-the-middle attack (Khader & Lai (2015)) should be invalid here.
Algorithm 3: Diffie-Hellman key exchange 1 for c ∈ [1, n] do 2 skc ← Z∗p 3 end 4 for c ∈ [1, n] do 5 pkc = g
skc mod p 6 for c
′ ∈ [1, n] ∧ c′ 6= c do 7 Sc,c′ = pk sk c ′
c mod p 8 end 9 end
If the shared keys are used as maskings directly, our system is not robust for clients collusion unless the amount of communication has been sacrificed as a cost to update maskings per round. But the communication complexity is exponentially increased with the number of clients for a single node splitting. Considering the structure of trees, the overall communication complexity will be O(2d ·NT · n2), which may not scale well in practical applications. To tackle this issue, we use KDF to update maskings per round automatically. Specifically, in line 24-25 of Algorithm 5, shared keys are taken as main keys. 0 and 1 are salt values for gradients and hessians, respectively. Since query in each round varies, the generated maskings should be dynamic accordingly. Besides, the sign of maskings is determined by the indexes of clients. In this way, we only need to use DH once, and the communication complexity is independent with tree structure.
To enable FEVERLESS to hold against differential attack, we use GDP approach allowing the chosen one to inject a global noise to aggregated values per round. The approach is quite subtle. If the noise leader is selected by source client, the system will be vulnerable to the collusion. Moreover, a client could be easily identified as a target if we choose it in advance, e.g., selecting a list of leaders before the training. To avoid these issues and limit the probability of collusion to the greatest extent, we use VRF to iteratively select the leader (see Algorithm 4) to securely inject a global noise. The input of VRF includes mIDs and a fresh random number r (line 4 in Algorithm 4), so that this client will not be predicted and set beforehand - reducing its chance to be corrupted in advance by outsiders and the source client.
All clients can broadcast their scores and then the one who holds the “max value” will become the leader. Then the leader re-generates a selection score as score threshold (selecthreshold) and sends it to the rest of the clients. (line 2-6 in Algorithm 5). The clients send the masked noise back to the leader if the re-generated score is larger than the threshold (line 7-13 in Algorithm 5). Subsequently, the leader will select k̂ clients, notify them and aggregate these masked noise to generate a global noise with a random number. In this context, even these selected clients are colluded (note at least one is not) with noise leader and source client, there is still a noise that cannot be recovered, safeguarding the training differentially private. Note since the noise is masked by the random number, the source client (even colluding with the leader) cannot recover the “pure” global
Algorithm 4: Noise leader selection 1 count = 1 2 for each time run this algorithm do 3 for c ∈ [1, n] ∧ c 6= source client do 4 selecc ← H(SIGNskc(count,mIDs,r)) 5 Broadcast 6 end 7 selecmaxc ← max({selecc | c ∈ [1, n]}) 8 set c as noise leader 9 count+=1
10 end
noise to conduct differential attack. And each client adds a noise with a probability p. If k out of k̂ are non-colluded, the probability of collusion is (1 − kn )
h. To cancel out the randomness, the selected clients will subtract the same randomness from masked messages (line 28-31 in Algorithm 5).
Considering that the source client may procrastinate the leader selection and noise injection procedure so as to buy some time for its colluded clients to prepare sufficient large VRF values to participate into the competition of selection and adding noise. One may apply a heartbeat protocol (Nikoletseas & Rolim (2011)) to prevent that a new selected leader intentionally halts the noise adding stage for a long period, say 1 min. If there is no response from the leader after for a short while, a new leader will be randomly selected. Furthermore, the heartbeat may help to solve the problem that the leader accidentally drops from the network. We note that the heartbeat protocol is not our main focus in this paper.
Before replying to source client, we have that the clients with labels put maskings to gradients and hessians, and for those without labels, they just generate and later send out maskings, in which the noise leader (i.e. one of the maskings generators) injects the noise. In this way, the maskings, guaranteeing perfect secrecy of the messages, will be cancelled out after the values aggregation, and the differentially private noise will solidate indistinguishability of individual data entry.
Note that in line 24-34 of Algorithm 5, the maskings and masked values are in the range [0, N − 1]. And N should be sufficiently large to avoid overflow, and the summation of gradients and hessians should not exceed N .
Algorithm 5: Secure aggregation with global differential privacy 1 Noise injection: 2 if c = leader then 3 selecthresholdc ← H(SIGNskc(count,mIDs,r)) 4 Broadcast 5 count+=1 6 end 7 for c ∈ [1, n] ∧ c 6= source client ∧ c 6= noise leader do 8 selecc ← H(SIGNskc(count,mIDs,r)) 9 if selecc > selecthresholdc then
10 send ñ(c)g = N(0,∆2gσ 2) + r (c) g and ñ (c) h = N(0,∆ 2 hσ 2) + r (c) h to noise leader 11 count+=1 12 end 13 end 14 if c = leader then
15 c selects k clients from clients of sending noise, k = d|{ñ(c)g }| · pe 16 if k < 1 then 17 redo noise injection 18 end 19 notify k clients 20 noise aggregation: Ñg = k · N(0,∆2gσ2) +Rg , Ñh = k · N(0,∆2hσ2) +Rh 21 end 22 Secure aggregation: 23 for c ∈ [1, n] do
24 mask (c) g ← (∑ c 6=c′ ∣∣∣c−c′ ∣∣∣ c−c′ · ( H(Sc,c′‖0‖query) mod N )) mod N
25 mask (c) h ← (∑ c 6=c′ ∣∣∣c−c′ ∣∣∣ c−c′ · ( H(Sc,c′‖1‖query) mod N )) mod N
26 G(c) = ∑ i∈mIDs g (c) i + mask (c) g mod N
27 H(c) = ∑ i∈mIDs h (c) i + mask (c) h mod N 28 if selecc > selecthresholdc ∧ received notification then 29 G(c) = G(c) − r(c)g mod N 30 H(c) = H(c) − r(c)h mod N 31 end 32 if c = leader then 33 G(c) = G(c) + Ñg mod N
34 H(c) = H(c) + Ñh mod N 35 end 36 send {G(c), H(c)} to source client 37 end

heading: E SECURITY ANALYSIS
text: We investigate the security and privacy properties of our protocol. First, we define the security model of our setting and the properties. Then, we prove that our protocol satisfies these properties.
Security Model. Our security is based on the random oracle model (ROM) (Smart (2016)) where the hash function outputs uniformly random value for a new query and the same value for a previously answered query.
Adversarial Model. Our protocol is designed for semi-honest security model (Smart (2016)) where all parties follow the protocol while trying to obtain information regarding other parties’ inputs. We assume that the source client can collude with other clients, but the size of colluding clients is no more than n− 2.

heading: E.1 PRIVACY GOALS
text: Our privacy goals can be summarized as: • Label privacy: No adversary controlling at most n−2 clients can learn who is the owner of a label among the honest parties. • Data privacy: No adversary controlling at most n − 2 clients can extract the data of an honest party.
We first investigate the case where the source client is not part of the adversary. In the following theorem, we show that there exists a simulator Sim that simulates the joint view of clients in A by only using the inputs belonging to them. This implies that A does not learn more than what they have. Theorem E.1 (A not including source client). There exists a PPT simulator Sim for all |C| := n ≥ 3, |X | := f ≥ n, |Y| := m ≥ 1, ⋃ c∈C X (c), ⋃ c∈C Y(c) and A ⊂ C such that |A| ≤ n − 2, the output of Sim is indistinguishable from the output of REAL:
REAL C,X ,Y A (X C ,YC) ≡ SimC,X ,YA (X A,YA) (8)
Proof. In order to prove that simulator Sim can simulate the outputs of the honest parties in H := C − A, we show that the distribution of the inputs belonging to the rest of the network cannot be distinguished from a randomly generated data. In this way, the simulator can use any dummy values as inputs of the honest parties to simulate their outputs.
We will simulate the view of the A regarding the messages broadcast by the honest clients. A client c, first makes a key exchange with others, then after some internal operations, outputs G(c) and H(c) values. Let us investigate G(c) value, which is in the form of ∑ i∈mIDs g (c) i + mask (c) g , except for the noise leader who has additional noise of N(0, (∆gσ)2). The mask values are computed as∑ c 6=c′ |c−c′| c−c′ · H(Sc,c′‖0‖query) mod N .
Here, we will use a hybrid model where we modify the protocol in several steps, and for each step, we will show that modifications are indistinguishable for the adversary A. In the end, we will achieve a hybrid that can be simulated by Sim.
Hybrid1: The first hybrid directly follows the protocol. The distribution of the variables and the view of A is the same as REAL. Hybrid2: In the second hybrid, we replace the agreed keys between honest clients Sc,c′ for all c, c′ ∈ H with random values rc,c′ ∈ G where G is the group of key exchange protocol G. In the original protocol, Diffie-Hellman key exchange is used. The replacement is indistinguishable for the adversary because of the decision Diffie-Hellman assumption given in Definition 4.
Also, note that these random values are only available to parties involved in the key exchange unless they are corrupted by the adversary.
Hybrid3: In this hybrid, we replace the mask values of honest clients mask (c) g for all c ∈ H with random values R(c). Note that with the replacement in the previous step, the mask values are
computed via ∑ c6=c′ |c−c′| c−c′ · H(rc,c′‖0‖query) mod N where rc,c′ ∈ ZN is a random value that is unknown to the adversary (if both c and c′ are honest). Because of the random oracle model, the output of the hash function will be a uniformly random value that is also unknown to the adversary. Since there are at most n − 2 clients in A , we have at least two honest clients c and c′ for which the adversary cannot know the uniformly chosen output of H(rc,c′‖0‖query). Then, the modular summation of these outputs includes at least one value that the adversary does not know and is uniformly random. Thus, it cannot be distinguishable from a random value R(c).
Hybrid4: In this hybrid, we replace gradients of honest clients g (c) i for all c ∈ H with ’0’s. This is done by replacing mask values with R(c) := R(c) − ∑ i∈mIDs g (c) i mod N to keep the G
(c) value the same. From the adversary’s perspective, sinceR(c) values are unknown and uniformly randomly chosen, the replacement is not distinguishable.
In Hybrid4, we replace the gradients of honest parties with ’0’s, and the mask values are replaced by R(c) which is unknown to the adversary and chosen from a uniform distribution. Thus, a simulator Sim can simulate the outputs of honest parties G(c) without necessarily knowing their inputs.
The same can be analyzed for hessian value, H(c). Since the masking values of G(c) and H(c) are different and the hash function is modeled as a random oracle, the randomness in both parts of them are independent of each other and indistinguishable by the adversary A. Overall, the simulator Sim can simulate our protocol.
Thus, the view of the A can be simulated by replacing the inputs of the honest parties with zeros. Thus, the adversary does not learn any information on the inputs of the honest parties.
Now, we analyze the case where the source client is part of the A. We show that there exists a simulator Sim that simulates the joint view of clients in A by only using the inputs belonging to them and the summations G and H . This implies that A does not learn more than what they have and the summation. Theorem E.2 (A including source client). There exists a PPT simulator Sim for all |C| := n ≥ 3, |X | := f ≥ n, |Y| := m ≥ 1, ⋃ c∈C X (c), ⋃ c∈C Y(c) and A ⊂ C such that |A| ≤ n− 2, the output of Sim is indistinguishable from the output of REAL:
REAL C,X ,Y A (X C ,YC) ≡ SimC,X ,YA (G,H,X A,YA) (9)
where G = ∑ i∈mIDs g (c) i + N(0, (∆gσ) 2), H = ∑ i∈mIDs h (c) i + N(0, (∆hσ) 2).
Proof. Here, we again show that Sim can simulate the outputs of the honest parties in H without knowing their inputs. Unlike Theorem E.1, Sim is also given the summations G and H because the adversary includes the source client.
We can use the same hybrids with Theorem E.1 until Hybrid4, this is because that the inputs of the honest clients are not required yet. We need to update Hybrid4 such that it takes into account the summation. Here are the hybrids for the A with source client: Hybrid1,Hybrid2,Hybrid3: The same with Theorem E.1.
Hybrid4: In this hybrid, we replace gradients of honest clients g (c) i for all c ∈ H with ’0’s, except one c′ which will be equal to ∑ i∈mIDs g (H) i mod N = G − ∑ i∈mIDs g (A) i mod N . The honest client c′ is randomly chosen among H. From the adversary’s perspective, since R(c) are unknown uniformly random chosen values, the replacement is not distinguishable.
Overall, the view of theA can be simulated by replacing the inputs of the honest parties with zeros, except one with ∑ i∈mIDs g (H) i mod N . Thus, A does not learn any information from the honest
clients, except the summation ∑ i∈mIDs g (H) i mod N .
With Theorem E.2, we show that even the adversaryAwith source client cannot know more than the summation of gradient and hessian values, G and H . The proof is done via Sim without requiring
individual data of the honest clients except for the summation. This implies that the adversary cannot distinguish which party provided which gradient or hessian values. Moreover, the parties who do not have any of the requested g or h values will send ’0’ together with the mask (and noise for the leader). This implies that we provide label privacy. Meaning that the adversary cannot distinguish which label’s g or h values are coming from which honest client.
In the case when the adversary includes the source client, the summation of gradient and hessian values can be known to the adversary. In the following theorem, we show that these summations do not leak any individual data due to differential privacy.
Theorem E.3 (Privacy of the Inputs). No A ⊂ C such that |A| ≤ n− 2 can retrieve the individual values of the honest clients with probability
1− k̂∑ i=0 CihC k̂−i n−2−h(Pt) k̂(1− Pt)(n−k̂) Ck k̂−i Ck k̂ ,
where h and k̂ refer to the number of non-colluded clients and the number of clients who have selection score larger than threshold. Pt is the probability of selection score larger than the threshold.
Proof. If the adversary does not include the source client, then following the previous theorems, the adversary cannot know any of the inputs belonging to the honest parties. Otherwise, it knows the summations G and H . Since we apply differential privacy (Dwork et al. (2006a;b)), the summation cannot leak information regarding the inputs. According to Definition 5, we add differentially private noise guaranteeing the security of individual data points while summation can be calculated.
Proof of probability. Note noise leader selects k clients from n clients (rather than itself and the source client) to add noise. Suppose that there are h non-colluded clients out of n − 2 clients, the number of clients whose selection scores are larger than the threshold is k̂. The number of events is
C k̂n−2−h + C 1 hC k̂−1 n−2−h + · · ·+ C k̂ hC 0 n−2−h,
in which the events are that {“there are k̂ colluded clients out of k̂ clients and 0 non-colluded client”,· · · ,“there are 0 colluded client out of k̂ clients and k̂ non-colluded clients”}. Therefore,
P (Ei) = C i h(Pt) i(1− Pt)h−i · C k̂−in−2−h(Pt) k̂−i(1− Pt)(n−h−k̂+i)
= CihC k̂−i n−2−h(Pt) k̂(1− Pt)(n−k̂),
where Pt is the probability that the selection score is larger than the threshold, and Ei is i-th event. Then, the probability that noise leader selects k colluded clients from k̂ clients is P0 = Ck
k̂−i Ck
k̂
. At the
end, the probability of all aggregated noise coming from colluded clients is
k̂∑ i=0 P (Ei) · P0 = k̂∑ i=0 Cih(Pt) i(1− Pt)h−i · C k̂−in−2−h(Pt) k̂−i(1− Pt)(n−h−k̂+i)
= k̂∑ i=0 CihC k̂−i n−2−h(Pt) k̂(1− Pt)(n−k̂) Ck k̂−i Ck k̂ .
Conversely, the probability of at least one non-colluded client participating in noise injection is
1− k̂∑ i=0 CihC k̂−i n−2−h(Pt) k̂(1− Pt)(n−k̂) Ck k̂−i Ck k̂ .
Note that because of the secure aggregation, the adversary cannot learn anything but the summation. Thus, our protocol does not require the addition of noise to each data. Instead, we only require the noise leader to add the noise, which prevents the retrieval of the individual data from the summation.
In Theorems E.1 and E.2, we show that A cannot distinguish the individual values from randomly chosen values and can only know the summation if the source is part of the adversary. In Theorem E.3, we show that A cannot extract the individual values of the users from the summation due to the added noise and differential privacy. Thus, our protocol satisfies data privacy. In other words, the adversary cannot learn the data point of an honest client.
It is important to note that since the noise leader is selected via VRF, no adversary can guess if any honest party will be the leader in the upcoming round beforehand. This provides additional security regarding the manipulation of the noise leader.

heading: F DISCUSSION
text: To reduce the negative impact brought by noise, according to infinity divisibility of Gaussian distribution (Patel & Read (1996)), one may split global noise (N(0, (∆σ)2)) into n parts (N(0, (∆σ) 2
n )). But a drawback is that the privacy budget will increase linearly as an increasing number of colluded clients appear. For example, if GDP achieves -DP , in the worst case where there are n−1 colluded clients, the privacy budget will raise to n× . Hiding labels distribution. In the semi-honest setting, if the source client sends the missing indexes consistently, adversaries may figure out which labels are distributed (on the source clients) by statistical analysis. We show that this issue can be tackled. In the proposed protocol, source client broadcasts the missing data indexes mID (line 16 of Algorithm 2). Under the semi-honest setting, if source client sends missing indexes consistently, the adversaries will figure out which labels are distributed on source clients by statistic analysis. We note that FEVERLESS can be expanded to avoid this type of leakage by yielding extra communication overheads. Specifically, during broadcasting period, source client should send indexes of one bucket instead of mID, and the rest of protocol remains constant. In this way, others cannot distinguish the distribution of labels because all clients share the same index set I. If we assume labels are uniformly distributed on each client, the extra overheads are restricted to |I|/|C|. This cost is clearly noticeable in those datasets with a large number of data points.
Other security tools. The masking scheme realizing secure aggregation may be replaced with an MPC (Damgård et al. (2012); Wu et al. (2020)) or additively homomorphic encryption (Paillier (1999)). However, the major defect of these tools is that they entail labor-intensive calculation with regard to encryption, which may not scale well in large-scale datasets. Due to this concern, we only put light-weight computation in FEVERLESE and further, we enhance the security to “perfect secrecy”.
In our design, the selection of noise leader is captured by VRF. We note that there may be other options to fulfil the goal. For example, Proof of Elapsed Time (PoET) (Chen et al. (2017); Corso (2019)) is an interesting and effective mechanism which is used to maintain the consensus of distributed peers in Hyperledger Sawtooth. It provides a fair and trusted lottery strategy to select a block winner (per consensus round). Sharing the same philosophy with the VRF, it may be deployed in our protocol to yield leader. And building a more efficient noise leader selection algorithm could be an interesting open problem.

heading: G MORE DETAILS ON EXPERIMENT SETUP
text: All the experiments are implemented in Python, and conducted on a cluster of machines with Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz, with 15GB RAM in a local area network.
Intuitively, the smaller we set, more secure FEVERLESS will be; but larger noise will be added. We note the above statement can be seen from the experimental results. As for the cryptographic tools, we set the key size of DH and Paillier as 160 bits and 1024 bits respectively(to save some time in running the experiments). This size can reach a symmetric security level with 80 bits key length. Note one may indeed increase the key size to obtain stronger security 7, but this will bring a longer experiment time as a side effect. We use 1024-bit MODP Group with 160-bit Prime Order Subgroup from RFC 5114 8 for DH Key exchange. SHAKE-256 (Dworkin (2015)), a member of SHA3 (Dworkin (2015)) family, is used as a hash function in leader selection and secure aggregation.
•Credit Card: It is a commercial dataset used for predicting whether costumers will make payment on time. It provides 30,000 samples, and each sample composes of 23 features. • Bank marketing: Consisting with 45,211 data points and 17 features, the goal of bank marketing is to predict if a client will subscribe a term deposit. • Banknote authentication: Offering 1,372 data points and 4 features, this dataset is used to classify authenticated and unauthenticated banknotes. Note that different from traditional tabular data, features in the dataset are extracted from images that are taken from genuine and forged banknotelike specimens through Wavelet Transform (Antonini et al. (1992)). Using the small-scale dataset, the trained model may not be robust for noise, which brings negative impact on accuracy.

heading: H ADDITIONAL EXPERIMENTS AND FIGURES
text: We present additional experiments, and all the experimental settings follow those defined in Section 4.1. In each presented figure, we show the results executed on the datesets Credit card (left), Bank Marketing (middle) and Banknote Authentication (right). Note that the comparison among FEVERLESS, LDP, and AHE requires a condition that #client=2; when #client=1, we can only show the results of the baseline. And the average performance of FEVERLESS in these figures is highlighted as the red dotted line.
Via the experiments, we elaborate that how the accuracy varies with the increasing number of client among the baseline, FEVERLESS and LDP, w.r.t. different tree structures and . Figure 7-18 are presented for the best case where only a non-colluded client adds the noise. And other cases are demonstrated in Figure 19-26 with the selection scores: 1/2 and 1/3. Beyond those, we also add the comparison results for AHE in Table 2-4 with = 2.
In general, without any added noise, the baseline can reach the highest accuracy and meanwhile, the accuracy remains stable as the client number increases. The performance of FEVERLESS is right behind that of baseline but still keeps stable. Note there are slight fluctuations in some figures (e.g. Figure 10, 12 and 14), especially for the case where complex tree structure and small are used. The LDP approach does harm accuracy, which can be seen from the continuously and significantly falling bars in the figures. Naturally, when more clients engage into the training, more noise should be added into the model. This makes LDP’s performance far lower than the red line.
Note that banknote dataset is composed of 4 features. In the VFL setting, every client should have at least one feature. Therefore, we can only allow up to 4 clients to participate in the training. Beside, FEVERLESS does not perform well in banknote dataset. This is so because the model is trained by a small number of samples, so that the robustness is seriously affected by noise.

heading: H.1 BEST CASE: ACCURACY ON CLIENT NUMBER
text: 7Note a stronger security level will not affect the training accuracy. 8https://tools.ietf.org/html/rfc5114

heading: AHE

heading: AHE

heading: AHE

heading: H.2 OTHER CASES: ACCURACY ON CLIENT NUMBER

heading: H.3 ADDITIONAL RESULTS ON ACCURACY FOR BANKNOTE AUTHENTICATION

heading: H.4 ADDITIONAL RESULTS ON TIME
text: In Figure 29-33, we show the time performance based on various numbers of client, tree and depth. Besides, we present the concrete results in Table 5-7. Table 8 also shows more specific runtime of tree construction in #tree=4 and depth=4 among baseline, FEVERLESS, LDP and AHE. In general, the runtime of FEVERLESS is slightly higher that that of the baseline. Compared to AHE, FEVERLESS significantly reduces training time while preserving privacy. This advantage is clearly seen from the cases using complex tree structures. Note that AHE can be replaced by other more complex cartographic solutions, such as secure MPC, which can also maintain data/label privacy. But the MPC-based solutions will consume more runtime.

heading: AHE

heading: AHE

heading: AHE

heading: AHE

heading: LDP

heading: H.5 RESULTS ON COMMUNICATION COST
text: In Figure 34-36, we demonstrate the communication cost based on the numbers of clients, tree and depth. For the convenience of comparison, we set #clients=4, #tree=4 and depth=4 as default. We use Table 9-11 to elaborate the concrete costs. To sum up, we see that the communication cost of FEVERLESS is almost the same as those of the baseline and LDP. But as compared to AHE, FEVERLESS significantly reduces costs while maintaining privacy.

heading: AHE

heading: LDP

Review summaries:
The paper introduces a novel setting for vertical federated learning in which labels are distributed among clients, and proposes a novel fast and secure protocol for this setting based on XGBoost . The protocol enables secure aggregation of gradients and hessians for XGBoost via (a) a masking scheme based on Diffie-Hellman key exchange and a key derivation function and (b) global differential privacy. Security analysis presented in the paper demonstrate that label/feature privacy is persevered even if n-2 clients collude. Finally, the efficacy of the proposed protocol is demonstrated via experimental evaluations on multiple datasets.

This paper studies vertical federated learning for fast and secure XGBoost training where labels are distributed among multiple parties.  Most previous works focus on labels are centralized in one party and adapt cryptography such as homomorphic encryption, multi-party computation, and differential privacy to protect the data and label privacy. This paper instead assumes decentralized labels and combines existing secure aggregation and global differential privacy to safeguard the data and label privacy. 

The paper proposes a new approach called FEVERLESS to conduct vertical federated learning over distributed labels. In the studied setting, the clients have different features of the same sample, and the labels are distributed over different clients. To get the gradients of the samples with missing labels, the clients utilize Diffie-Hellman key exchange, key derivation function, and differential privacy to send the masked gradients to the source client. Then, the source client computes the gain based on the gradients, and the split candidate with the maximum gain is selected as the split point. The authors prove that FEVERLESS protects label and data privacy against an adversary controlling at most n-2 clients. The experiments show that FEVERLESS can achieve comparable accuracy compared with XGBoost.