FEVERLESS: Fast and Secure Vertical Federated Learning based on XGBoost for Decentralized Labels
Authors: Rui Wang
Oğuzhan Ersoy
Hangyu Zhu
Yaochu Jin
Kaitai Liang
Venue: ICLR 2022 Submitted (2022)

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 experiment results 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 approach.

Under review as a conference paper at ICLR 2022
FEVERLESS: FAST AND SECURE VERTICAL FEDER- ATED LEARNING BASED ON XGBOOST FOR DECEN- TRALIZED LABELS
Anonymous authors Paper under double-bling blind review
ABSTRACT
Vertical Federated Learning (VFL) enables multiple clients to collaboratively train a global model over vertically partitioned data without revealing private local in- formation. 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 dis- tributed labels. This work is the first to fill this gap by designing a novel protocol, called FEVERLESS, based on XGBoost. FEVERLESS leverages secure aggre- gation 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, provides label and data pri- vacy against honest-bur 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, outperforms the solution based additive homomorphic encryption in runtime cost and provides better accuracy than the local differential privacy approact
adversary even in the case of collusion of n - 2
INTRODUCTION
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 privacy regulations and policies. To tackle this "Data Island" problem (Yang et al. (2). Google proposed Federated Learning (FL) (McMahan) al. (2017)) to allow multiple clients train 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); OOekondy et al.) (2019) 9);;
Geiping et al. (2020); [i & 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. (011));
Xu al. 2019); Zhang et al. (2020); (Zhu 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 al. (2020); Cheng al. (202T) 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): 7): Nock al. (2018): Liu et al. et al. (202T): & Guestrin (2016):
:): Wu et al, (020 have pro- posed innovative approaches prevent private information breaches in the context of VFL. Specif- ically, (Hardy et al. (2017)) introduced encryption- privacy-preservin logistic regression to safeguard the information of data indexes. (Nock al. (2018) gave comprehensive discussion on
2020))[Yang et (2019)))
"Code available http:://ghhuaaccom//fertsss11/1/

---

Under review as a conference paper at ICLR 2022
the impact of ID resolution. (Yang al. (2019b) introduced scheme without using coordina- tor 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, easter 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 indus- try'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); (Bonawiz et al. (2017)) After that, (Cheng et al. (202)) proposed a similar system to train XGBoost (Chen & Guestrin (2066) securely over vertically partitioned data by using Additively Homomorphic En- cryption (AHE). By applying Differential Privacy (DP) (Dwork (008). (Tian et al. (2020) de-
signed VFL system to train GBDT without the need of encryption/decrypiion.
However, most of the above solutions based on AHE and MPC do not scale well in terms of effi- ciency 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 their health records and symptoms. In this context, the labels (i.e., the test results) are likely distributed among different health authorities- even targeting 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 la- bel 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 (c.g.. payment preference). Since the customers may get the same service, c.g., loan, from different insti- tutions, 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 fast and secure VFL protocol, FEVERLESS, to train XG- Boost [Appendix[B.] (B.T) on distributed labels without disclosing both feature and label information. In our design, the privacy protection is guaranteed by secure aggregation (based on masking scheme) and Global Differential Privacy (GDP) (Appendix [B66). We leverage masking instead heavy-cost multiparty computation and we guarantee a "perfect secrecy" level for the masked data. In GDP, we use Verifiable Random Function (VRF) (Appendix B35)) 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 FEVERLES train XGBoost securely and efficiently with the elegant combination of secure aggregation technique (based on Hellie-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 2 out of n clients commit collusion.
(3) We implement FEVERLESS and perform training time and accuracy evaluation on different real- world 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
2

---

Under review as a conference paper at ICLR 2022
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%, %, respectively 2
PROBLEM FORMULATION
2.1
SYSTEM MODEL
Before proceeding, we give some assumptions on our model. We suppose that private set inter- section (Kolesnikov al.] (2017); Pinkas et al. (2014) has been used 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,- , .. J. each containing f features, and label set y = {21.- 3mm Besides, features {X} () j E (1.... ,f} and labels {x!-) (c) | i E {I,... [1......). .m} are held among n clients where each client has at least one feature and one label. x and (( 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 variant of VFL, named VFL over Distributed Labels (DL-VFL). The concrete definition is given as follows.
Definition 1 (DL-VFL). Given training set with m data samples consisting of feature space X, label space y, index space and clients set C, we have:
X n x 0, ny = 0,I V',' EC,
Vc,
(I)
A client 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-preservin XGBoost training, we further define two roles. Definition (Source client). A source client with split candidates wants to compute the correspond- ing siphit based Eq. 4 But some labels are missing that Σ 9i and Σ h, are unable derive.
For the case that source client does not hold all labels in the current split candidates, we propose solution based secure aggregation and global differential privacy to help the source client to compute Laptit 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 chance to act source client because all the labels are distributed, where the source client leads the Lepiit 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 (Noise leader). By using VRF, a noise leader is responsible for generating the maximum leader score, aggregating differentaally private noise from a portion of clients and adding the noise to the gradients and hessians.
Note we summary the main notations in Table T (see Appendix A
2.2 THREAT MODEL
We mainly consider potential threats incurred by participating clients and the outside adversaries. We assume that all clients are honest-but but-curiouu, which means they strictly follow designed algo-
For 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 small-scale dataset, so that the robustness seriously affected by noise.
3

---

Under review as a conference paper at ICLR 2022
rithms but try to infer private information of other clients from the received messages. Besides, also consider up to n 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 eaves- drop these channels and try reveal information about clients during the whole DL.-VIL, 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.
A PRACTICAL PRIVACY-PRESERVIE PROTOCOL
3.1 FEVERLESS PROTOCOL DESCRIPTION
To prevent a source client from knowing gradients and hessians sent by other clients, one may directly use MPC (Damgård et al. 20122) based AHE (Paillier (1999); Wu al. (2020). But this method yields expensive computation cost. Getting rid of the complex mechanism like MPC, leverage secure aggregation protocol via masking scheme based on DH key exchange (Bonawitz et al. 2017); Acs & Castelluccia (2011); Tian et al. (2020)) By further using KDF and Hash Function (see Appendix BB44 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 al.) 20144) 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 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 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 given in Ap- pendix D Assume each client E [1, n] generates respective secret key ske and computes gradients (c)
9i and hessians ( locally, where {il y E )² FEVERLESS works follows.
1. Broadcast missing indexes. The source client broadcasts the mIDs= {i ye & y*).
2. Key exchange computation. Each client computes public key pkc g th using secret keys ske, sends phic to other clients and computes the corresponding shared keys
3 (S e, phake g sk sk
c, E C, J'} based on secret key ske received public keys {pk& C CC.
Data masking. Each client e runs the masking generation algorithm to compute the mask- ings for protecting gradients and hessians. Specifically, based on KDF, clients' indexes and the
l--o"
number of queries, the masking generation algorithm is conducted by mask, (c) < -coed |
Then the masked gra- dients G(e) and hessians H(e) are generated by G(e) = EiemIDs mask (c)
(H(S [10]] ((o)))))))) mask (e)
k
+ Eoyd c-d (H(See/llllquery))
(c) g
(c) H(e) =
EIEmID. (c) + mask) -((()
4. Noise leader selection. Each client generates the selection score selec, using the VRF, H(SIGN.k, (count, MIDs, x)), ). and broadcasts it, where count is the number of times clients
conduct VRF, r is fresh random number, and SIGN is the signature scheme (see Appendix B.3 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 select is the leader, in Figure |
'hared keys are only generated once, and the KDF is used to generate the remaining maskings. 'For purpose of simplicity, we omit modular computations. The complete calculation processes are clabo-
rated Algorithm X
4

---

Under review as a conference paper at ICLR 2022
5. Noise injection. a) Noise leader selects it clients adding noise. For the details of the selec-
tion, please see Algorithm in Appendix D b) The selected clients send {ng N(O, 470)) +
ng n o² le k} to noise leader, in which the r/ and r/()) are two ran-
(0) (e)
dom values to mask noise. c) The leader aggregates the noise: Ng = k N(O, 2302) + Rg and NA = k- NO, + RR, and further adds them to ((n) and (m)), respectively.
6. Aggregation and computation. All clients send the masked values the source client. The source client computes 20 G(+) + k-N(O, Az0²), >e H((e) + k-N(O, 2)) and Laplit-
7. Final update. The source client with maximum Lsptit updates model following XGBoost CCen & Guestrin 2016)) and broadcasts the updated model and data indexes in child nodes as step 8.
Figure 1 gives 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
u N(O.64o
mt00
update
seles
0
8
must!
SLx
R
mosk
Brondract Chaunel
S,y
T0
6
Σ
moak 10
solete
Ric
Σ
Σ
mosk
pka
glv + KG
celect Eaat
Σ
mask
Moise
+7
Inacher
Figure 1: Overview of FEVERLESS.
Source client broadcasts missing IDs, aggregates
gradients and hessians securely, updates model and broadcasts nodes IDs. ---- : DH key ex- change and maskings generation.
Noise leader selection. Broadcast missing indexes. KKey exchange computation. @Dat masking. Noise leader selection. @Global noise injection. Aggregation and computation. 70 Final update and broadcast updated model. Note sensitive data are in red. The maskings in @ protect data from source client, and the noise in aggregated gradients and hessians prevents source client from conducting differential attack.
3.2 THEORETICAL ANALYSIS
Computation cost: We use B and d to denote the number of buckets and the maximum depth respectively, and f(() 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(e) B NT (2d 1) times computation of Leplit and w, taking O(f(e) B NT 2d) time; (2) Creating n 1 shared keys and 1 public key, which is O(n); (3) Conducting O(f(e) B NT 2d) time to compute VRF outputs, select noise leader and generate noise; (4) Generating 2)(e) B NT (2 1)
maskings, which takes O(f(e). NT--T22 .n) time. Overall, each client's 's computation complexity is O(f()) NT. 2d nn).
Communication cost: Each client's communication cost can be calculated as (1) Broadcasting most f(e) B NT (2d 1) times of missing indexes mID: (2) Broadcasting 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(e) B NT (2d 1) times; (4) Sending source client 2 masked gradients and hessians of size 2[log2N] Therefore the overall communication cost is
p(e). B NT (2d -1) ([ImDD] ou + az. + ON + 2xx((log2NN) where or Oz, ON and
5

---

Under review as a conference paper at ICLR 2022
о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 24).
3.3 SECURITY ANALYSIS
We prove that FEVERLESS provides label and data privacy against an adversary controlling at most n - clients in the semi-honest setting (Smart (0016)) Here, we provide a brief summary of our analysis and theorems. The formal proofs, in the random oracle model, are given in Appendix [ 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 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 cannot extract the data of any honest party. Individual data values are not separable from random values because of the secure masking. the source client is not part of the adversary, no data information leaked. But we require an additional countermeasure for the case where the source client is part of the adversary because can collect the summation of the data values. We use differential privacy (Dwork et al.) (006a b)) to achieve data privacy. Because of the noise added by differential privacy, the adversary cannot learn the individual data an honest client. Moreover, we select the noise clients by the VRF which ensures that the noise leader cannot be predicted compromised in advance.
Theorem 3.1 (A not including source client). There exists PPT simulator Sim for all [C|:= := n
| := f 2 n, | := m 2 1, Usee X((), Usee yte) and A C So that |A| S n -0. 2, the outpu of Sim is indistinguishable from the output of REAL: REAL C.X.V (20,2/) Sim A
C.X.Y (XA, )A).
Theorem 3.2 (A including source client). There exists a PPT simulator Sim for all [C] := N 3, | = f2 n, |D == m 2 1, UsEe X(0), Ucee Vooo and C C so that |A] S n 2, the outpur of Sim is indistinguishable from the output of REAL: A
C. (Ne )e = Sim A (e)
C.X.3' (G. H, X y'A)
where G EiEmIDo N(O, (A, EiEmID h + N(O, (Ano))).
Theorem 3.3 (Privacy of the Inputs). No A C C such that |A| nn
- can retrieve the individual C
values of the honest clients with probability Σi Cj ch- (P
where C
h and i refer to the number of non-colluded clients and the number of clients who have selection score larger than threshold, respectively; and P. is the probability of selection score larger than the threshold.
EXPERIMENT
We perform evaluations on accuracy, runtime performance and communication cost, and compare our design with two straightforward secure approaches: one is based LDP (for accuracy), and the other is built on AHE with GDP (for runtime). These approaches are most-commonly-unse ponents for 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 [] without using any sriaacy-reserving 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 I except executing DH key exchange. In AHE, each client sends (additive) encrypted messages to source client after step 6. We here show the performance of the best case where there is only one inon-colluded and randomly selected) client adding noise per round (k = 1). For other results (where l: of 1), see Appendix H.2 Note present the communication cost in Appendix H.5
com- FL, and they could be the building blocks for complex mechanisms,

---

Under review as a conference paper at ICLR 2022
4.1 EXPERIMENT SETUP
To present comprehensive results on accuracy, we set e to be: 10, 5, 2 and 1, and ó is set to 10 In terms of aceuracy 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 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 (Ych & Lien (2009), Bank Marketing (Moro et al. (2014)) and Banknote Authentication for classification tasks. To fairly investigate the model performance in DL-VFL, we make the labels as sparse as possible, and they uniformally distributed on clients. We give the more details of experiment setup in Appendix G
4.2 EVALUATION ON ACCURACY
In Figure 2 we present a clear picture on the accuracy performance based on the #tree and the maximum depth in (2, 10 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 approximately 1.0. To highlight the differences and ensure all results to be displayed clearly, we set the ranges of accuracy as 00.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.T 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.599) 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 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 e are given in Appendix
To distinguish the performance between FEVERLESS and LDP more clearly, Figure shows the comparison over different c, when #depth and #tree are set to 10. The performance of the model decayed as the decrease of c. 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 tiny advantage over LDP.
4.3 EVALUATION ON TRAINING TIME
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 [Os, 9,500s], [Os, 3,500s] and [Os, 110s] for the datasets to deliver visible results. Note since the banknote dataset contains the least samples, it
7

---

Under review as a conference paper at ICLR 2022
Dotaset Credit card
Buselin
Nasurnyy 2.8
077
0.7
0.6
68
rumber troes
1
number tros
10
Oopth
number of treee
10
dopth
Dutasel: Burk marketing
0.0
0.0
0.8
0.8
0.6
0.8
0.5
P.0
rumbor trods
depth
number of 1900
depth
number of trees
Oeptth
Baseline
Faveriess
LDP
Acsuney
Accumay
Aocursty
0.5.
04
6
number
depth
number
0both
number
Ceptth
Figure 2: Comparison among the baseline, FEVERLESS and LDP under Top row: Credit card dataset, accuracy range: [0.5, 0.9]. Middle row: Bank marketing, accuracy range: [0.5, 1]. Bottom row: Banknote authentication, accuracy range: [0, 1].
Fevertess Baselie
0.3
0.
0.9
0.8
0.8
foourdy
Accursyy
0.6
6.6
0
4 0
0.
0.5
0.5
0
10s8on=10
opoiion-6
op5 lmn-
opd
4po8on-10
opoilone5
spolor-2
opallon-1
opailon-10
opallon65
Figure 3: Comparison of accuracy by varying in depth=10, the number of 10e Left: Credit card. Middle: Bank marketing. Right: Banknote authentication. Accuracy ranges from 0.4 to
8

---

Under review as a conference paper at ICLR 2022
does deliver the best training efficiency here. Figure 4 presents the comparison the training time by varying maximum depth and the number of trees among the datasets.
Datacet:: Credit card
Feveriesa
AHE
MAX
0000
5000
2000
2000
2000
2000
10
10g 0
deprs
number yous
depth
Dotannt: Dank marketing
Porurkoza
0002
2000
2000
1200
1000
1000
10g
10
10
10g 0
depth
Humber of troe
Based
Feverisss
AHE
100
100
Thmee
Timeto
20
depth
trees
death
number tree
Figure 4: Comparison of time. Top row: Credit card dataset, range: [Os, 9,500s]. Middle row: Bank marketing, range: [0s, 3,500s]. Bottom row: Banknote authentication, range: [Os, 110s].
The training time increases exponentially and linearly with depth and the number of tree, which is consistent with analysis given in Section 3.2 In Figure 4 compared with the baseline, the runtime of FEVERLESS at most increases II0.3s (resp. 50s, 4.3s), while AHE requires around 70x spike (resp. 48x, 21x) in credit card (resp. bank marketing, banknote authentica- tion), where #depth and #trees are equal to 10. For the average case, FEVERLESS consumes Approx. (res....6.55)) 13.96%) more training time than the baseline, while AHE requires the 351%(resp..55. 15, 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
5 CONCLUSION AND FUTURE WORK
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, 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 - out n clients. The experiment results show that FEVERLESS 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.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308 318, 2016.
G. Ács and C. Castelluccia. I have a dream! (differentially private smart metering). In Information Hiding, 2011.
Marc Antonini, Michel Barlaud, Pierre Mathieu, and Ingrid Daubechies. Image coding using wavelet transform. IEEE Transactions on image processing, 1(2):205-220, 1992.
Jean-Philippee Aumasson, Luca Henzen, Willi Meier, and Raphael C-W Phan. Sha-3 proposal blake. Submission to NIST, 92, 2008.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 17., pp. 1175-1191, New York, NY, USA, 2017. Associa- tion for Computing Machinery. ISBN 9781450349468. Tictps://dbi.org/110 wwt.e.11113333380 3133989
doi: 10.11457113395663133992, URL
Dan Bonch, The decision diffie-hellman problem. In ANTS, volume 1423 of Lecture Notes in Computer Science, pp. 48 63. Springer, 1998.
Lin Chen, Lei Xu, Nolan Shah, Zhimin Gao, Yang Lu, and Weidong Shi. On security analysis of oloof--f-elapsed---e -imppsedddeeeeeeeeeeeee (poet). In International Symposium on Stabilization, Safety, and Security of Distributed Systems, pp. 297. Springer, 2017.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing, KDD '1. pp. 785-794, New York, NY, USA, 2016. Association for Computing Machin- ery. ISBN 9781450342322. doi: 10.114572999722.239778
URL httph:htps/oooot http::://oo..rg///1
1145/2939672 293977222999555
Kewei Cheng, Tao Fan, Yilun Jin, Yang Liu, Tianjian Chen, Dimitrios Papadopoulos, and Qiang Yang. Secureboost: A lossless federated learning framework, 2021.
Amie Corso. Performance analysis of proof-offelapsee--ime (poet) consensus in the sawtooth blockchain framework. PhD thesis, University of Oregon, 2019.
Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Annual Cryptology Conference, pp. 643-662. Springer, 2012.
Whitfield Diffie and Martin Hellman. New directions in eryptography. IEEE transactions Infor- mation Theory, 22(6):644-654, 1976.
Cynthia Dwork. Differential privacy: A survey of results. In Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li (eds.), Theory and Applications of Models of Computation, pp- 1-19, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3-540-79222
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006b.
Morris Dworkin. Sha-3 standard: Permutation-hasse hash and extendable functions. 2015.
10

---

Under review as a conference paper at ICLR 2022
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients how easy is to break privacy in federated learning? In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin A.das.....vvacc in Neural Information Processing Systems, volume 33, pp- 16937-16947. Curran Associates, Inc., 2020. URL 9ae61 9aa61126220ccbb1445--99 hc//pppprr/2000///1e///ceddddddd ott.a//00000.111111e222220000053
ngs, neurips. pddf
Oded Goldreich. Secure multi- parlt computation. Manuseript. Preliminary version, 78, 1998.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume MIT press Cambridge, 2016.
Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Richard Nock, Giorgio Patrini, Guillaume Smith, and Brian Thorne Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv preprint arXiv: 2017.
Johan Håstad, Russell Impagliazzo, Leonid Levin, and Michael Luby. pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4): (((4)::364411)) 1396, 1999.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27:2879-2889 2014.
Burt Kaliski. Pseudorandom Function, pp. 485-485. Springer US, Boston, MA, 2005. ISBN 978- 0-387-23483-0. doi: 10.100770-3877-23463 7_329 URL batps:://ael..org/111.. 0-387-234833
329
Aqeel Sahi Khader and David Lai. Preventing man-in-the-middle attack in diffie-hellman key ex- change protocol. In 2015 22nd international conference on telecommunications (ICT), pp. 204- 208. IEEE, 2015.
Vladimir Kolesnikov, Naor Matania, Benny Pinkas. Mike Rosulek, and Ni Trieu. Practical multi- party private set intersection from symmetric-key techniques. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1257-1272 2017.
Hugo Krawezyk and Pasi Eronen. basad-based sttractanddeexpand key derivation function (hkdf). Technical report, RFC 5869, May, 2010.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553):436 444, 2015.
Hongyu Li and Tianqi Han. An end-to-end encrypted neural network for gradient updates transmis- sion in federated learning. arXiv preprint arXiv: 1908. 083.08844. 2019.
arXiv:1908.088
Yang Liu, Xiong Zhang, and Libin Wang. Asymmetrically vertical federated learning. arXiv preprint 20X:022004.07427. 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efffieeett learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
Xiangrui Meng, Joseph Bradley, Burak Yavuz, Evan Sparks, Shivaram Venkataraman, Davies Liu, Jeremy Freeman, DB Tsai, Manish Amde, Sean Owen, et al. Mllib: Machine learning in apache spark. The Journal of Machine Learning Research, 17(1):1235-1241, 2016.
Silvio Micali. ALGORAND: the efficient and democratic ledger. CoRR, abs/1607.01341, 2016.
URL htttht/pp//aiiii org/ abs/ / 1607.11077.00 01341
Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In 40th annual symposium on foundations of computer science (cat. No. 99CB37039), pp. 120-130. IEEE, 1999.
Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014.
Sotiris Nikoletseas and José DP Rolim. Theoretical aspects of distributed computing in sensor networks. Springer, 2011.
11

---

Under review as a conference paper at ICLR 2022
Richard Nock, Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Giorgio Patrini, Guillaume Smith, and Brian Thome Entity resolution and federated learning get a federated resolution. arXiv preprint arXhv:1803.04033. 2018.
Tribhuvanesh Orekondy, Seong Joon Oh, Yang Zhang, Bernt Schiele, and Mario Fritz. Gradient- leaks: Understanding and controlling deanonymization in federated learning. In NeurIPS Work- shop on Federated Learning for Data Privacy and Confidentiality, 2019.
Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In TAMC. Springer, 1999.
J.K. Patel and C.B. Read. Handbook of the Normal Distribution, Second Edition. Statistics: A Series of Texthooks and Monographs. Taylor & Francis, 1996. ISBN 9780824793425. URL mation Forensics and Security, 13(5) 2018. doi: 10. 10.1000/1FSS.21..27707
wtw.lle..nn/oookeee. https::/bboks..oot http:/oks...ooo.e..////o/////// ee 2m0 EQgoC
Le Trieu Phong, Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. Privacy- preserving deep learning via additively homomorphic encryption. IEEE Transactions on Infor-
Benny Pinkas, Thomas Schneider, and Michael Zohner. Faster private set intersection based on {OT) extension. In 23rd {USENIX) Security Symposium (( ((USENIX) Security 14), pp. 797-812, 2014.
NIST Sha. standard: Permutation- based hash and extendable-outpu functions. federal information processing standards publication 202, 2015, 2015.
Reza Shokri and Vitaly Shmatikov. Srivacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS '15, pp. 1310-1321, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 978 9781450338325. doi:
0111445/281103..288
BtLhttps::/ /ttp://.............////1101022. 2813667
Nigel P. Smart. Cryptography Made Simple. Information Security and Cryptography. Springer, 2016.
Zhihua Tian, Rui Zhang, Xiaoyang Hou, Jian Liu, and Kui Ren. Federboost: Private federated learning for gbdt, 2020.
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and federated learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, AlSec' 19, pp. 1-11, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 450366336 doi: 10.1145/3338501. 3357370. URL http:tttt///o....oo org 0 1tt.://11.111111111111111 11111113353100 3357370
Yi Zhou. A hybrid approach
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-346) 2020.
Yuncheng Wu, Shaofeng Cai, Xiaokui Xiao, Gang Chen, and Beng Chin Ooi. Privacy preserving vertical federated learning for tree-based models. Proc. VLDB Endow. 13(12):000--203, July 2020. ISSN 2150-8097. doi: 10. 10.1147783407790.3400
URL Stttps://doi.ozg/
14778/ 04778/3407790 3407811
Runhua Xu, Nathalie Baracaldo, Yi Zhou, Ali Anwar, and Heiko Ludwig. Hybridalpha: An efficient federated learning. In Proceedings of the 12th ACM Workshop
approach for on Artificial Intelligence and Security. AlSec' 19, pp. 13-23, New York, NY, USA, 2019. Associ- ation for Computing Machinery, ISBN 45036633,,33,, doi: 10. 00.1145/338551.33357733 URL
https: http///oi.ogg/////
.oo. /0. 11
3357371
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Trans. Intell. Syst. Technol. 10(2), Jamuary 2019a. ISSN 2157-6904. doi: 10. 10.1145/3298981. URL //dot .org/ 100 1145 14959298911
12

---

Under review as a conference paper at ICLR 2022
Shengwen Yang, Bing Ren, Xuhui Zhou, and Liping Liu. Parallel distributed logistic regression for vertical federated learning without third-part partyp coordinator. arXiv preprint arXiv: arXiv:191..09825 2019b.
I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2): 2473 -473-2480, 2009.
Jonathan Zdziarski. Hacking and securing iOS applications: stealing data, hijacking software, and how to prevent it. O'Reeill Media, Inc.", 2012.
Chengliang Zhang, Suyi Li, Junzhe Xia, Wei Wang. Feng Yan, and Yang Liu. Batcherypt: Efficient homomorphic encryption for cross-silo federated learning. In 2020 USENIX An- mual Technical Conference (USENIX ATC 20), pp. 493-506. USENIX Association, July 2020. ISBN 978-1-939133-1444 URL presentation/ chenae//ggaaaannnnngggaaaee
Hangyu Zhu, Rui Wang, Yaochu Jin, Kaitai Liang, and Jianting Ning. Distributed additive encryption and quantization for privacy preserving federated deep learning. arXiv preprint 1rXiv:2011.12623, 2020.
13

---

Under review as a conference paper at ICLR 2022
A
NOTATIONS
The frequently used notations are summarized in Table 1
Table 1: Notations summary
Notation
Description
X
feature space
(c)
j-th feature owned by e-th client
32
i-th data point with features
y
label space
y
the label of i-th data point owned by c-th client
I
data index space
C
clients set
93
(c)
the gradient i-th data point owned by e-th client
h
the hessian of i-th data point owned by c-th client
G
summation of gradients
summation hessians
number of data entries
n
number of clients
number of features the maximum depth of tree
d
6,
parameters of differential privacy
Ag
sensitivity gradients
D
sensitivity of hessians
Leplit
impurity score
W
leaf value
pke
public key generated by e-th client
ske
secret key owned by e-th client
9
generator of multiplicative group
B2
z-th bucket of j-th feature
B PRELIMINARIES
B.1 XGBooST
XGBoost (Chen Guestrin (2016) a popular tree-based model in tabular data training that can provide better interpretation, casier parameters tuning and faster execution speed than deep learning Goodfellow et al. (2016); LeCun et al. (015).. It also outperforms other well-known boosting tree systems in terms of accuracy and efficiency, like Spark MILib Meng et al. (2016) and H2O Chen & Guestrin (2016), especially for large-scale datasets. Therefore, in this paper, we consider using XGBoost as building block for classification tasks.
Assume that training set with m data points composing with feature space and label space = -....... 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! of previous tree for i-th data point, and y is the label of i-th data point:
(. Fmm]
(t-1) denotes the prediction
9
(1-1)
y4 01
Vd.
(2)
1 -
h4
(3)
(1 + E- "2
14

---

Under review as a conference paper at ICLR 2022
For splitting nodes, the XGBoost algorithm determines the best split candidate from all others based on maximum Lpplst in Eq. where and are regularization parameters:
ΣiEr 9: I eplit 2 Eien. h4 + X Eietn by + Eier h1 + 7
Eier,
Eierg
(4)
The current node will be the leaf node if the following conditions are fulfilled: reaching the maxi- mum depth of tree, the maximum value of impurity is less than preset threshold. The calculation of the leaf value follows Eq.
Eier 96 Σiel hi +
W
(5)
B.2 DIEFIE-HELLMAN KEY EXCHINNG
Based Decision Dillie-Hellman (DDH) hard problem (Boneh (1998)) defined below, Diffie- Hellman key exchange (DH) (Diffie & Hellman (176)) provides a method used for exchang-
ing keys across public communication channels. Without losing generality and correctness, consists of tuple of algorithms (Param.Gen Gen, Key.Gen, Key.Exc). The algorithm (G.g.9) 9) & Param.Gen (1") generates public parameters (a group G with prime order q generated by a gen- erator g) based on secure parameter a. (shi,, <- Key.Gen(G, 9. q) allows client i to gener- ate secret key (sk; e Zg)) and compute public key (pk, + g)h.). Shared key is computed by (pk:)h pk. + Key.Exc(sk;, ph: sky, pk;)). Inspired by (Bonawitz al. (2117); Ács & Castel- luccia (20TT). we utilize shared keys maskings to protect information of labels against inference
attack during transmitting in public channels. The correctness requires pk; sk; pk.t The security relies on the DDH problem (Boneh (1998)), which is defined as:
Definition 4 (Decision Diffie-Hellman) Let G be group with prime order q and be the fixed generator of the group. The Probabilistic Polynomial Time (PPT) adversary A is given and go and ge where and b are randomly chosen. The probability of A distinguishing (9 """""""""""""""""""""""" ghh and .g g²) for a randomly chosen is negligible:
Pr (Pr(a,be' By ::(gg A(g.9".. "".""""." .h. = true
Pr bria,b,c b, 8 Z, Alg,g" . ,g9) = true
< na))(a))
B.3 PSEUDO-RANDOM GENERATOR AND HASH FUNCTION
Pseudo-Random Generator (PRG) Hástad et al. (199)) is 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-randon numbers determined by given initial values a.k.a seeds. In cryptographic applications, à secure PRG requires attackers not knowing seeds can distinguish truly random number from output of PRG with negligible probability. Similar with PRG, hash function allows mapping arbitrary size of data to 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. (008)) family, to generate customize size of maskings.
B.4 KEY DERIVATION FUNCTION
Key Derivation Function (KDF) Krawezyk Eronen (2010) is a kind of hash function that derives multiple secret keys from main key by utilizing Pesudo-Random Function (PRF) (Kaliski (2055). In general, KDF algorithm DK + KDF (mainkey, salt, rounds) derives keys DK based on 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 converted to AES keys, in this paper, use KDF to generate maskings for every round to reduce communication cost. The main key we use is generated by DH key exchange.
15

---

Under review as a conference paper at ICLR 2022
B.5 VERIFIABLE RANDOM FUNCTION
Verifiable Random Function (VRF) (Micali et al. (1999)) is a PRF providing verifiable proof' of correctness of outputs. It is tool widely used in cryptoeurrencies, smart contracts and leader selection in distributed systems (Micali (2016)) Basically, given a input v, a signature scheme and a hash function, practical leader selection scheme with VRF (Micali (2016)) works as:
Steader f- H(sign.,,,.1))
(6)
where sky is the secret key for i-th client, and the maximum leader score Steader 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 map the signature to random string with fixed size. The correctness of this Steader is proved by the signature of x.
B.6 DIFFERENTIAL PRIVACY
Differential Privacy (DP) (Dwork et al. (2066a b)) is data protection system targeting 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 arbitrary data point is different.
The most widely used DP mechanism is called (c, 6DD requiring less noise injected than original proposed e-DP but with the same privacy level. The formal definition given as follows.
Definition 5. ((c, 5) Differential Privacy) Given two real positive numbers (c, 8) and a random-
ized algorithm A: D + y, the algorithm A provides (e, 8) differential privacy if for all data sets D, D' E D differing in only one data sample, and all S S y: Pr(A(D) E S) S exp(e) Pr[A(D') E E S]+ +.
Note the noise N ~ ((0,, NO,, 2 will be put into the output of the algorithm, where A is norm sensitivity of D and (1.25/))) (Abadi al. (2016)).
C PRIVACY CONCERN
Since we assume feature names are not public information for all clients, and the values of features never leave from clients, the privacy issues mainly incurred by the leakage of label information.
C.I INFERENCE ATTACK
During training process, gradients and hessians are sent to source client for Leplit computation. For classification task, the single gradient is in range (-1, (0, 1) for binary classification. According to ( a label can be inferred as and 0 if the range is (-1,0) 0) and (0, 1), respectively. Besides, hessian illustrated in Bq. 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 attack- ers 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.
C.2 DIFFERENTIAL ATTACK
Differential attack can happen anytime and many times during the calculation of gradients and hes- sians. Figure 5 describes an example of differential attack taking place in single node split. Af- ter sorting featurel, the semi-honest source client defines split candidates and further computes G[2,5) 92 + 95 and (1122,,55 92 + 95 91 + g3 for the candidates I and 2, respectively, Since the source client holds label 2, even G(2.5) is derived by secure aggregation, the go still can be revealed by G(2,3) 92-
Another example for differential attack shown in Figure Assume split candidate is the one for splitting root node. In the current tree structure, source client may split right node by computing Lypta of split candidate 2. In this case, G(1,3) should be aggregated by source client. And the Is can be revealed by (11223355 G(1,3) 92, where ((1223355) is computed in the previous node.
16

---

Under review as a conference paper at ICLR 2022
Featuret Labe
D
Featurel
Label
D
Featured Labe
sgad
72
canditale
3
185
37.0
condidate
dient
Clert2
Figure A differential attack on single node split
Model
[1 (1244.
[2.5]
[1.3.4]
ID Feature! Labal
Fealurce Label
Featured
Label
148
37.4
spill candicato
80
37.3
Sourcw clinn
Cheet
Claett
Figure 6: A differential attack multiply node splits
D MORE DETAILS ON FEVERLESS PROTOCOL
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, 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 e, ô for DP, hash function for masking generation and noise leader selection. Besides, we select a multiplicative group with order q generated by generator g and 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 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 follows.
Algorithm 1: Initialization
Set parameters: all clients agree the maximum depth of tree d, the number of trees (NT), learning rate (17). regularization parameters (X, 7), the threshold Leplit c, 6, p. g. selection portion (p) and hash function
for e E [1, do
for each feature j owned by do
sort(x)o)
define buckets: Bi
end
set initialized values: y/ (c)
end
After initialization, all clients invoke Algorithm 2 to train model collaboratively. The inputs are from feature space consisting features ((() and labels y: distributed on different clients, respectively; while the output is trained XGBoost model that can be used for prediction. Generally, trees are built one by one. And we see from line 4-10 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- DL-VFL requires each client calculate G and H. If the labels in some buckets are incomplete, the corresponding
17

---

Under review as a conference paper at ICLR 2022
gradients and hessians cannot be computed. Thus, each client should first broadeast missing data index set mID (see line 15-17 in Algorithm 2). Based on the predefined bucket B1, mlD can be de- fined if labels in B not held by clients. In each broadcast, client sending messages is regarded
as a source client. Then others send the corresponding 9; (e') and n, back to the source client to compute lipptit through Algorithm 3 depicted in Appendix(D.2 After finding maximum impurity spptit mant the current node will be split to "left" and "right" nodes sptit max >theeholld La splits which the value of the split candidate is own by c. In node splitting, clients should set given
Algorithm 2: Protocol overview
Input: (x/=) | E f,e c E [C]]: features, (u,
m, c E [C]]: labels
Output: XGBoost model
Building trees:
for nt E [T] do
for e E [1, do
for each data entry owned by do
9, - 0g Loss(I) (9. "))")
4 - 02 Loss Loss (c) 13. (c)
end
end
11
for each node in the current tree do
while current depth <d do for e [1, n. do for each feature j owned by do
13
for each Bi owned by do Broadcast mID = (i y/ $ )*}
16
end
aggregate G, H by Algorithm 3 compute Leptit according to Eq end
18
find the maximum [fce split and broadcast
21
end
(e) split mar + max if (c) split_maz S Uhreshold Leptie then
sptit split cE [1,
23
24
25
set current node as leaf node e computes and broadcast
27
Break
28
else
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
e computes w and broadcast
clients participating in calculation of w: update ş).
(c)
38 end
36 end
node as "leaf" if current depth reaches the predefined maximum depth or the maximum Luptit is less than the predefined threshold of Lapist (see line 12, 24-32 in Algorithm 2). The derivation of leaf value is followed by Eq. [ where and H are intaken. Since a leaf node is either "left" or "right" split by one of the clients
from its parent node, this client knows G and H/ and leaf value can be
(c) derived. Finally, this leaf value will be broadcast, and clients who own the corresponding 9; and h it update predictions. The details for the above process shown in Algorithm
18

---

Under review as a conference paper at ICLR 2022
D.2 SECURE AGGREGATION WITH GLOBAL DIFFERENTIAL PRIVACY
In line 15-19 of Algorithm 2 source client is able to compute Laplit from the requested missing data indexes and the aggregation of received messages. To avoid that inference and differential attacks conducted on labels by source client and outside adversaries, we propose
approach, shown in Algorithm 3 S to "twist" the DH key exchange, noise leader selection and secure aggregation together. This method represents viable alternative to train XGBoost securely in DL-VFL without demanding excessive computational resources and affecting model accuracy.
To generate the secure- secure-but-cant but-can-be caan--e-cancelled out maskings, adopt DH here. In Algorithm B] 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 thi--i-the-middlee attack (Khader & Lai (015)) should be invalid here.
Algorithm 3: Hellien key exchange
for o [1, do shic + En
end
for
C [1, do phc =9 =gth, g=k=modp p
for é' E [1,n] A # do
s
Sedd = pkc mod p
end
end
If the shared keys are used 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 n,,, 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. and 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 cho- sen one to inject 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 target if we choose it in advance, e.g., selecting list of leaders before the training. To avoid these issues and limit the probability of collusion to the greatest extent, use VRF to iteratively select the leader (see Algorithm
4 securely inject a global noise. The input of VRF includes ml Ds and fresh random number (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- re-generates a selection score as score threshold (selectbreskol) and sends it to the rest of the clients. (line 2-6 in Algorithm 5p. 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 & 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 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
19

---

Under review as a conference paper at ICLR 2022
Algorithm 4: Noise leader selection
count
for each time this algorithm do
for e e [1, A # source client do
selec, + (SIGNsk, (count, mIDs, r
Broadcast
end
selec max((selece | c [1,n]])
set as noise leader count+=1
end
noise to conduct differential attack. And each client adds a noise with a probability p. If l out of are non-colluded, the probability of collusion is (1 4) 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 pro- cedure 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 proto- col (Nikoletseas & Rolim (211T) to prevent that a new selected leader intentionally halts the noise adding stage for a long period, say min. If there no response from the leader after for a short while, 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 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 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.
20

---

Under review as a conference paper at ICLR 2022
Algorithm 5: Secure aggregation with global differential privacy
Noise injection:
leader then
sclec +-
(count, mIDs, r))
Broadcast
count+=1
end for
C [1 A + source diinnt A c e noise leader do selec, + H (SIGNsk, (count, mIDs, r))
selec, selec then
10
send fig N(0, 220) +g and n = N(0, ((0,4).0)) + r
to noise leader
II
count+=1
12
end
13
end
if c leader then
e selects & clients from clients sending noise, = [1(ng H.pp
15
16
if < 1 then
17
redo noise injection end
19
notify 1: clients
noise aggregation: N₂ k. N(0, Rg. No. k NNO, 2702) Rr.
21 end
22 Secure aggregation:
23 for c [1, do
24
mask
(c)
Eojo
c-c
H(S (|0|[/ue))))) mod N) mod N
m (0) -
Eejd
c-c
(H(S o.d ( [[]]|qeery) mod N) mod N
25
c-c
26
G(d) Eiemi De
mask mod H(e) Eigmi Da (.(0 + mask mod N
27
selec, > selec threshhrlshlld A received notification then
28
G(e) G(e)) (c) mod N
H = (c) h mod N end
30
31
32
i leader then
G(d) ((e) + Ng mod N
33
H (()) + Nr mod N
end %6
send (G(e), H(e) to source client
end
21

---

Under review as a conference paper at ICLR 2022
E SECURITY ANALYSIS
We investigate the security and privacy properties of our protocol. First, we define the security model of our setting and the properties. Then, prove that our protocol satisfies these properties.
Security Model. Our security is based on the random oracle model (ROM) (Smart (0016) where the hash function outputs uniformly random value for a new query and the same value for a previ- ously answered query.
Adversarial Model. Our protocol 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 2. 2.
E.1 PRIVACY GOALS
Our privacy goals can be summarized as:
Label privacy: No adversary controlling most n -2 clients can learn who the owner of label among the honest parties.
Data privacy: No adversary controlling most n 2 clients can extract the data of an honest
party.
We first investigate the case where the source client not part of the adversary. 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 (AA not including source client), There exists a PPT simulator Sim for all [C] = n 2
3. | := f 2 n, [Y] == m 2 1, Ucee X(e), Useg Vie) and A C C. such that |A| I n - 2, the output of Sim is indistinguishabl from the output of REAL:
REAL C.N.N (XC,
Sim (XA,)
(8)
Proof. In order to prove that simulator Sim can simulate the outputs of the honest parties in H == A, we show that the distribution 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 first makes a key exchange with others, then after some internal operations, outputs ((e) and (e) values. Let us investigate G(e) value, which in the form of Eigm g. mask, except for the noise leader who has additional noise of N(O, (A))) The mask values are computed as Enjer le-c'l c-c"
(c)
H(SS.er [/0[//////rrrr 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.
Hybrid;: The first hybrid directly follows the protocol. The distribution of the variables and the view of A is the same as REAL.
Hybridy: In the second hybrid, we replace the agreed keys between honest clients Soe for all c, E 7. with random values To,e' E G where G' is the group of key exchange protocol G. In the original protocol, Diffie-Hellman key exchange is used. The replacement indistinguishable for the adversary because of the decision Diffie- Hellman assumption given in Definition g
Also, note that these random values are only available to parties involved the key exchange unless they are corrupted by the adversary.
Hybridg: In this hybrid, replace the mask values of honest clients mask (c) for all E H with random values R(O), Note that with the replacement in the previous step, the mask values
22

---

Under review as a conference paper at ICLR 2022
k-dl
computed via E e-e! H(re,e (1fc:e/ll))))r))) mod N where To,e NN is random value that is unknown the adversary (if both e 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 clients in AA we have at least two honest clients and c' for which the adversary cannot know the uniformly chosen output of H(rc,e' [[][querr). Then, the modular summation of these outputs includes least one value that the adversary does not know and is uniformly random. Thus, it cannot be distinguishable from random value R!(s)
Hybrid,: In this hybrid, we replace gradients of honest clients g. for all E H with 'O's. This is (e) mod N to keep the G value done by replacing mask values with R(e) R(() Eiemi Ds 9i
the same, From the adversary's perspective, since R!(e) values are unknown and uniformly randomly chosen, the replacement is not distinguishable.
In Hybrid4, we replace the gradients of honest parties with 'O's, and the mask values are replaced by Rie) which is unknown to the adversary and chosen from a uniform distribution. Thus, a simula- tor Sim can simulate the outputs of honest parties G(e) without necessarily knowing their inputs.
The same can be analyzed for hessian value, H(o), Since the masking values of G and H are different and the hash function is modeled 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 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 PPT simulator Sim for all |C] := n 2 3, | := f 2 n, D' == m 2 1, Ucec 2((e), Usec Viee) and A C C such that |A| S n 2, the output of Sim is indistinguishable from the outpur of REAL:
C.N. (x
Sim C.X.V (G,
where
G=
Σ iEmIDs
+ MOO (A (A)
Σ dEMIDs
h ( N(0,
Proof. Here, we again show that Sim can simulate the outputs of the honest parties in H. without knowing their inputs. Unlike Theorem E.I Sim is also given the summations G and H because the adversary includes the source client.
We can the same hybrids with Theorem E. until Hybrid4, this is because that the inputs of the honest clients are not required yet. We need to update Hybrid; such that it takes into account the summation. Here are the hybrids for the A with source client:
Hybrid, Hlybridd,Hybride The same with Theorem E.I
Hybridy: In this hybrid, we replace gradients of honest clients g for all c H with 'O's, except one é' which will equal to EiEmID 9i (74) mod G G- Ei-EEemDDAL (A) mod N. The honest client è' is randomly chosen among H. From the adversary's perspective, since R((e) are unknown uniformly random chosen values, the replacement not distinguishable.
Overall, the view of the A can be simulated by replacing the inputs of the honest parties with zeros, except one with EtEmIDe 9; (H) mod N. Thus, A does not learn any information from the honest clients, except the summation EiemIDs Di
(H) mod N.
With Theorem E.2 we show that even the adversary A with source client cannot know more than the summation of gradient and hessian values, G and H. The proof is done via Sim without requiring
23

---

Under review as a conference paper at ICLR 2022
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 h values will send 'O' 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 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 the adversary. In the following theorem, show that these summations do not leak any individual data due to differential privacy.
Theorem E.3 (Privacy of the Inputs). No A C C such that |A| S n - can retrieve the individual values of the honest clients with probability
Ck
1-
Ck
1=0
where h and i refer the number of non-colluded clients and the number of clients who have lection score larger than threshold. Pe 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 | add differentially private noise guaranteeing the security of individual data points while summation can be calculated.
Proof of probability. Note noise leader selects clients from clients (rather than itself and the source client) to add noise. Suppose that there are h non-colluded clients out of n clients, the number of clients whose selection scores are larger than the threshold is k. The number of events is
+
C.O.
Ch..
in which the events are that {"there are colluded clients out of À clients and 0 non-colluded "oantt",...,"tlbee are 0 colluded client out of & clients and & non-colluded clients"). Therefore,
P(E)) = = P₂) Ch- (PA) hi P.) =
where P. is the probability that the selection score larger than the threshold, and E3 is i-th event. Then, the probability that noise leader selects k colluded clients from clients Po = At the end, the probability of all aggregated noise coming from colluded clients is
C
&
Σ P(E) Po = Σ (1
........................... (P)) -1 (n.)(n
t=0
&
(P)) -.)
1=0
Conversely, the probability least one non-colluded client participating in noise injection
(p)(nn k)
C
1=0
Note that because of the secure aggregation, the adversary cannot learn anything but the summation. Thus, protocol does not require the addition of noise to each data. Instead, only require the noise leader to add the noise, which prevents the retrieval of the individual data from the summation.
24

---

Under review as a conference paper at ICLR 2022
In Theorems E.1 and E.2 show that A cannot distinguish the individual values from randomly chosen values and can only know the summation the source is part of the adversary. In Theo- rem E.3 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 honest client.
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.
F DISCUSSION
To reduce the negative impact brought by noise, according to infinity divisibility of Gaussian distri- bution (Patel & Read 1996)), one may split global noise (O, (Ao)?)) into parts (N(0, (Aa)² ))- But drawback is that the privacy budget will increase linearly as an increasing number of colluded clients appear. For example, if GDP achieves e-DP, in the worst case where there are n colluded clients, the privacy budget will raise to n x 6.
Hiding labels distribution. In the semi-honest setting, if the source client sends the missing in- dexes 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 m/D (line 16 of Algorithm 2). Under the semi-honest setting, 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 broad- casting period, source client should send indexes of one bucket instead of m, and the rest of protocol remains constant. In this way, others cannot distinguish the distribution of labels because all clients share the same index Z. If we assume labels are uniformly distributed on each client, the extra overheads are restricted to [Z]/|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 Damgard et al. (012); Wu 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 interesting and effective mechanism which is used to maintain the consensus of dis- tributed 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 more efficient noise leader selection algorithm could be an interesting open problem.
25

---

Under review as a conference paper at ICLR 2022
G MORE DETAILS ON EXPERIMENT SETUP
All the experiments are implemented in Python, and conducted on a cluster of machines with In- tel(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 0 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 /4 for DH Key exchange. SHAKE-255 (Dworkin (2015). member of SHA3 (Dworkin 2015)
family, is used as a hash function in leader selection and secure aggregation.
Credit Card: It 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.
Consisting with 45,211 data points and 17 features, the goal of bank marketing is predict if a client will subscribe term deposit.
Bank marketing:
Banknote authentication: Offering 1,372 data points and 4 features, this dataset is used to clas- sify 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 banknote- like specimens through Wavelet Transform (Antonini et al. (1922). Using the small-scale dataset, the trained model may not be robust for noise, which brings negative impact on accuracy.
H ADDITIONAL EXPERIMENTS AND FIGURES
We present additional experiments, and all the experimental settings follow those defined in Section 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 FEVER- LESS, 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 e. Figure 7-18 are presented for the best case where only a non-colluded client adds the noise. And other cases 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 with c= 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 e 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 trained by a small number of samples, so that the robustness is seriously affected by noise.
H.1 BEST CASE: ACCURACY ON CLIENT NUMBER
Nooe a stronger security level will not affect the training accuracy. https://mnnk..iefffo///m///f1f1
26

---

Under review as a conference paper at ICLR 2022
Nandow Cr
Mumtoe Clens
Figure 7: Comparison of accuracy depth: 10, the number of trees: 10, epsilon: 10.
Figure& 8: Comparison of accuracy in depth:10, the number of trees: 10, epsilon:5.
TRAM Maruray
4.00
09-
02-
6.58
04
Figure 9: Comparison of accuracy in depth:10, the number of trees: 10, epsilon:2.
Cad
Lunkada
100
Bustow
Figure 10: Comparison of accuracy in depth: 10, the number of trees: 10, epsilon:1.
Esriintt cethercctton
40
Figure 11: Comparison of accuracy in depth:8, the number of trees:8, epsilon: 10.
27

---

Under review as a conference paper at ICLR 2022
Maricia
ACC
4.1
0.44
Homiere Dhrik
Figure 12: Comparison of accuracy in depth:8, the number of trees:8, epsilon:5.
Konts Judion
KMM
34-
304
0.79
34
52
14
Figure 13: Comparison of accuracy in depth:8, the number of trees:8, epsilon:2.
Crest Cord
Best Mottcking
3--
Figure 14: Comparison of accuracy in depth:8, the number of trees:8, epsilon:l.
A.72
6700
617
Car
Figure 15: Comparison of accuracy in depth:6, the number of trees:6, epsilon: 10.
Eask Parosgg
3.03
3.04
K16
C59
8,00
UPP
kember
Figure 16: Comparison of accuracy in depth:6, the number of trees:6, epsilon:5.
28

---

Under review as a conference paper at ICLR 2022
DEPP Exikee
440
Numaer ar
Figure 17: Comparison of accuracy in depth:6, the number of trees:6, epsilon:2.
AC2
Oer OFOOI Notertitte
Figure 18: Comparison of accuracy in depth:6, the number of trees:6, epsilon:
Baseline
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree:
Depth:2
0.8186
0.82
0.8175
0.8173
0.8111
Depth:4
0.8219
0.8197
0.8203
0.8226
0.8215
Depth:6
0.8213
0.8204
0.8195
0.8192
0,8206
Depth:8
0.8181
0.8203
0.821
0.8163
0.816
Depth: 10
0.8126
0.8155
0.816
0.8171
0.8191
FEVERLESS
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.8228
0.8185
0.8138
0.8146
0.8119
Depth:4
0.8209
0.8183
0.8201
0.8213
0.817
Depth:6
0.8167
0.8155
0.8126
0.8022
0.8009
Depth:8
0.8044
0.7929
0.7795
0.7625
0.752
Depth: 10
0.7726
0.7547
0.7194
0.6734
0.6821
AHE
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.8185
0.8185
0.8225
0.8208
0.817
Depth:4
0.8295
0.8195
0.8145
0.8187
0.8178
Depth:6
0.8195
0.8185
0.814
0.816
0.8053
Depth:8
0.807
0.7958
0.7983
0.7748
0.7668
Depth: 10
0.7457
0.7168
0.719
0.7302
0.6825
LDP
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.8195
0.8167
0.8187
0.8146
0.8143
Depth:4
0.819
0.8176
0.8173
0.8154
0.8107
Depth:6
0.8119
0.8067
0.7942
0.7842
0.7745
Depth:8
0.7752
0.744
0.7259
0.7058
0.68 14
Depth: 1O
0.6843
0.6333
0.6022
0.5772
0.5713
Table Comparison of accuracy among Baseline, LDP, FEVERLESS and AHE with Credit Card.
29

---

Under review as a conference paper at ICLR 2022
Baseline
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree:
Depth:2
0.8887
0,893
0.8926
0.8944
0.8962
Depth:4
0.9125
0.9101
0.9136
0.9111
0.9111
Depth:6
0.9168
0.9143
0,9132
0.915
0.9154
Depth:8
0.9118
0.9182
0.9175
0.9145
0,9172
D0
0.9117
0.9115
0.9108
0.9125
0,9152
FEVERLESS
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.8878
0.8908
0.8927
0.8938
0.8972
Depth:4
0.9051
0.9042
0.905
0.9079
0.90588
Depth:6
0.9029
0.8985
0.9032
0.8974
0.8914
Depth:8
0.893
0.8869
0.8666
0,8699
0,8509
10
0.8424
0.852
0.81
0.8122
0.7654
AHE
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree:
Depth:2
0.887
0.8908
0.8929
0.8962
0.8931
Depth:4
0.911
0.9071
0.9026
0.9126
0.9125
Depth:6
0.9025
0.8994
0.8979
0.8995
0,9012
Depth:8
0.8864
0.8885
0.8723
0.8687
0.8541
Depth: 10
0.8503
0.8479
0.8229
0.8148
0.761
LDP
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree:10
Depth:2
0.889
0.8923
0.892
0.8939
0.8924
Depth:4
0.9048
0.9054
0.9047
0.904
0.9027
Depth:6
0.8983
0.8916
0.8865
0.8816
0.8769
Depth:8
0.8697
0.8523
0.8346
0.823
0.8042
Depth: 10
0.7951
0.7561
0.7251
0.6891
0.6693
Table 3: Comparison of accuracy among Baseline, LDP, FEVERLESS and AHE with Bank Mar- keting.
30

---

Under review as a conference paper at ICLR 2022
Baseline
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.84364
0.8444
0.8785
0.8858
0.9229
Depth:4
0.9455
0.9513
0.9607
0.9651
0.9738
Depth:6
0.9629
0.9783
0.9869
0.9935
0.992
Depth:8
0.9818
0.9855
0.9847
0.9913
0.9884
Depth: 10
0.9818
0.9876
0,9833
0.992
0.9884
REVERLESS
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree:
Depth:2
0.8465
0,8604
0.8655
0,864
0,8553
Depth:4
0.8487
0.8378
0.7847
0,8022
0.8058
D
0.7033
0.6676
0.6378
0.5964
0.5905
Depth:8
0.632
0.5738
0.5804
0.5425
0.5084
Depth: 10
0.5193
0.5396
0.5084
0.4676
0.4865
AHE
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.8473
0.8625
0.8662
0.8716
0.859
Depth:4
0.9033
0.8273
0.8058
0.7971
0.7455
Depth:6
0.7251
0.6545
0.6629
0.6436
0.5778
Depth:8
0.6022
0.5611
0.5258
0.4924
0.5255
Depth:
0.4945
0.4953
0.5015
0.4931
0,5022
LDP
Accuracy
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.8415
0.8419
0.841
0.8476
0.8439
Depth:4
0.8536
0.8204
0.7634
0.7336
0.729
Depth:6
0.7442
0.6606
0.5743
0.5404
0,5343
Depth:8
0.5387
0.5406
0.5549
0.5375
0.5127
Depth: 10
0.4848
0.4924
0.4926
0.479
0.5072
Table 4: Comparison of accuracy among Baseline, LDP, FEVERLESS and AHE with Banknote Authentication.
31

---

Under review as a conference paper at ICLR 2022
H.2
OTHER CASES: ACCURACY ON CLIENT NUMBER
Bace Merdding
1.0
Figure 19: Comparison of accuracy in depth:8, the number of trees:8, epsilon:5, selection score: 1/2.
Eariacaa AstHTTCcean
Figure 20: Comparison of accuracy in depth:8, the number of trees:8, epsilon:2, selection score:
Cedi
Eack Medezing
Dunimett Rud entication
600
LDN
Figure 21: Comparison of accuracy in depth:8, the number of trees:8, epsilon:5, selection score: 1/3.
OeB. Car
Mahdis
12
Kame
Figure 22: Comparison of accuracy in depth:8, the number of trees:8, epsilon:2, selection score: 1/3.
32

---

Under review as a conference paper at ICLR 2022
$3.0
$113
2037
3393
2.10
Figure 23: Comparison of accuracy in depth:6, the number of trees:6, epsilon:5, selection score: 1/2.
Figure 24: Comparison of accuracy in depth:6, the number of trees:6, epsilon:2, selection score: 1/2.
6.12
Figure 25: Comparison of accuracy in depth:6, the number of trees:6, epsilon:5, selection score: 1/3.
Oredit Care
Bank Martetie
famemiicaioo
124
Figure 26: Comparison of accuracy in depth:6, the number of trees:6, epsilon:2, selection score: 1/3.
33

---

Under review as a conference paper at ICLR 2022
H.3
ADDITIONAL RESULTS ON ACCURACY FOR BANKNOTE AUTHENTICATION
0-8
380
Raader
750
Figure 27: Comparison of accuracy in epsilon:30. Left:depth:6, the number of trees:6. Mid- 8le:depth:8, the number of trees:8. Right:depth:10, 10, the number of trees:
8.50
4.005
304
Saabee
/0
Figure 28: Comparison of accuracy in e0silon:50. Left:depth:6, the number of trees:6. Mid- dle:depth:8, the number of trees:8. Right:depth: 10, the number of trees: 10
34

---

Under review as a conference paper at ICLR 2022
H.4 ADDITIONAL RESULTS ON TIME
In Figure 33 we show the time performance based on various numbers of client, tree and depth. Besides, we present the concrete results in Table 7 Table 8 also shows more specific runtime of tree construction in #tree=4 and depth=4 among baseline, FEVERLESS, LDP and AHE. In gen- eral. the runtime of FEVERLESS is slightly higher that that of the baseline. Compared FEVERLESS significantly reduces training time while preserving privacy. This advantage is clearly seen from the cases using complex tree structures. Note that AHE can 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.
AHE,
Nattotay
Autiont cotion
Figure 29: Comparison of runtime in depth: 10, the number of trees:10.
Hanaatin
Dartnets
Figure 30: Comparison of runtime in depth:8, the number of trees:8.
Hovolasa
Figure 31: Comparison of runtime in depth:6, the number of trees:6.
35

---

Under review as a conference paper at ICLR 2022
Ordii Crr
York Varutng
A4
Vato 4Oara
Figure 32: Comparison of runtime in depth:4, the number of trees:4.
Click Card
Outc Nariec
BEEr See Auther cstion
Figure 33: Comparison of runtime in depth:2, the number of trees:2.
Baseline
Time(s)
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
13
28
41
56
66
Depth:4
51
109
164
211
259
Depth:6
126
239
332
404
527
Depth:8
197
378
574
710
868
Depth: IO
312
591
830
1144
1484
FEVERLES
Time(s)
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
16
33
49
65
81
Depth:4
63
124
189
244
303
Depth:6
123
239
350
454
564
Depth:8
258
463
519
687
798
Depth:10
308
518
813
1129
1584
AHE
Time(s)
#tree:2
#tree:4
#trec:6
#tree:8
#trec: 10
Depth:2
19
38
58
77
96
Depth:4
168
252
335
459
Depth:6
303
636
954
1143
1360
Depth:8 775
1547
2366
3158
3873
Depth:10
1685
3420
5320
7360
9268
Table 5: Comparison of runtime among Baseline, LDP, FEVERLESS and AHE with Credit Card.
36

---

Under review as a conference paper at ICLR 2022
Baseline
Time(s)
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
17
27
37
47
Depth:4
36
76
131
168
222
Depth:6
148
247
335
421
Depth:8
164
285
402
575
748
Depth:10
299
576
844
1007
1093
FEVERLE LRSS
Time(s)
#tree:2
#tree:4
#tree:6
#tree:8
#tree:10 10
Depth:2
18
27
37
46
Depth:4
33
151
161
Depth:6
75
150
215
251
316
Depth:8
160
320
453
593
723
Depth:
294
548
785
872
1043
AHE
Time(s)
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
22
33
44
56
Depth:4
43
87
130
174
216
Depth:6
147
293
437
600
674
Depth:8
413
840
1240
1628
1773
Depth: 10
808
1613
2379
2955
3481
Table 6: Comparison of runtime among Bascline, LDP, FEVERLESS and AHE with Bank Market- ing.
Baseline
Time(s)
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.36
0.7
0.88
1.33
1.48
Depth:4
1.13
2.33
3.84
3.94
4.99
Depth:6
1.92
3.88
5.81
7.42
9.17
Depth:8
2.89
5.82
6.4
10.06
11.07
Depth:10 10
3.54
6.14
7.03
8.36
10.69
FEVERLES FES
Time(s)
#tree:2
#tree:4
#tree:6
#tree:8
#tree: 10
Depth:2
0.28
0.57
0.84
1.11
1.4
Depth:4
1.08
2.19
3.22
4.32
5.22
Depth:6
2.38
4.25
6.39
8.54
10.48
Depth:8
3.66
6.78
8.42
8.71
13.11
Depth:10
4.34
7.72
8.71
10.25
14.97
AHE
Time(s)
#tree:2
#tree:4
#trec:6
#tree:8
#tree: 10
Depth:2
1.23
2.45
3.72
4.9
6.18
Depth:4
5.75
11.76
17.8
23.85
29.55
Depth:6
14.15
29.11
44.11
59.44
76.75
Depth:8
22.29
41.68
65.28
82,45
101.17
Depth:10
21.12
46.45
64.58
82.85
102.3
Table 7: Comparison of runtime among Baseline, LDP, FEVERLESS and AHE with Banknote Authentication.
37

---

Under review as a conference paper at ICLR 2022
Baseline
Time(s)
Credit Card
Bank Marketing
Banknote Authentication
Tree Construction
29.98
17.96
0.483
Tree 2 Construction
28.32
17.94
0.477
Tree 3 Construction
26.34
17.96
0.473
Tree 4 Construction
25.09
17.09
0.449
Total
109.73
70.95
1.883
LDP
Time(s)
Credit Card
Bank Marketing
Banknote Authentication
Tree 1 Construction
28.44
19.42
0.563
Tree 2 Construction
26.62
18.77
0.559
Tree 3 Construction
27.22
18.68
0.516
Tree 4 Construction
28.04
19.53
0.577
Total
110.22
75.53
2.216
FEVERLESS
Time(s)
Credit Card
Bank Marketing
Banknote Authentication
Key exchange
0.006
0.006
0.006
Tree Construction
31.77
18.43
0.763
Tree 2 Construction
28.95
18.54
0.623
Tree 3 Construction
27.38
19.51
0.651
Tree Construction
27.29
19.05
0.67
Total
115.39
75.53
2.713
AHE
Time(s)
Credit Card
Bank Marketing
Banknote Authentication
Encryption
9.03
6
2.37
Tree Construction
51.62
25.65
3.91
Tree 2 Construction
51.03
26.2
3.84
Tree 3 Construction
52.17
25.78
3.93
Tree 4 Construction
53.55
25.01
3.92
Total
217.4
108.64
17.964
Table 8: Comparison of runtime among Baseline, LDP, FEVERLESS and AHE with Credit Card, Bank Marketing and Banknote Authentication. #clients=4, #tree=4, depth=4.
38

---

Under review as a conference paper at ICLR 2022
H.5 RESULTS ON COMMUNICATION COST
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 default. We use Table I to elaborate the concrete costs. To sum up, we see that the communication cost of FEVERLESS is almost the same as those of the bascline and LDP. But as compared AHE, FEVERLESS significantly reduces costs while maintaining privacy.
Ore Care
Drai Martecing
Duntzect Aughor tootee
Figure 34: Comparison of communication cost on the number of clients.
Cruok
Martedan
mooiing
Best ng
seeetin
Figure 35: Comparison of communication cost depth.
bud
Nambel we
Forrrber of Poot
Figure 36: Comparison of communication cost on the number of trees.
39

---

Under review as a conference paper at ICLR 2022
Baseline
Communication cost (byte)
Client 1
Client 2
Client 3
Client 4
Total
Missing IDs
46318623.75
75988029.38
80983170
79199803. 13
282489626.3
Key exchange
0
Noise leader selection
0
0
0
Sending noise
0
0
Sending messages
148824
131760
127480
130352
538416
XGBoost update
460444.375
227560.75
50247.25
209665.75
947918, 125
Total
46927892.13
76347350.13
81160897.25
79539820.88
283975960.4
LDP
Communication cost (byte)
Client 1
Client 2
Client 3
Client
Total
Missing IDs
64407678.75
82033042.5
80595855
57890778.72 75
284927355
Key exchange
0
Noise leader selection
0
0
0
Sending noise
0
0
Sending noised messages
140792
127432
129544
142280
540048
XGBoost update
235180
15745.375
412955.5
284301.C ...30..66555.
9481 1481
Total
64783650.75
82176219.88
81138354.5
58317360.38
286415585.5
FEVERLESS
Communication cost (byte)
Client 1
Client 2
Client 3
Client
Total
Missing IDs
63060322.5
78762268.13
62603476.85
78498995.63
282925063.J
Key exchange
60
60
240
Noise leader selection
29092
26552
29272
26732
111648
Sending noise
9556
8788
9728
8920
36992
Sending masked messages
116400
106224
117112
106952
446688
XGBoost update
441000.875
53475.5
402234.625
50431.25
947142.25
Total
63656431.38
78957367.63
63161883.5
78692090.88
284467773.4
AHE
Communication cost (byte)
Client 1
Client 2
Client 3
Client 4
Total
Missing IDs
6347611 11.25
80963026.88 888
63239242.5
80651070
288329450,6
Key exchange
0
Noise leader selection
27040
25084
27408
25228
104760
Sending noise
8876
8420
9028
8512
34836
Sending encrypted messages
3462144
321 1264
3508992
3229952
13412352
XGBoost update
40627.375
229334.75
563730.625
113990
947682.75
Total
67014798.63
84437129.63
67348401.13
84028752
302829081.
Table 9; Comparison of communication cost among Baseline, LDP, FEVERLESS and AHE with
Credit Card.
40

---

Under review as a conference paper at ICLR 2022
Baseline
Communication cost (byte)
Client
Client
Client 3
Client 4
Total
Missing IDs
92296068
64006710
15700788
15439038
187442604
Key exchange
0
0
0
0
0
Noise leader selection
0
0
0
Sending noise
0
0
Sending messages
29880
44480
61456
61560
197376
XGBoost update
409814
479272
299368
335316
1523770
Total
92735762
64530462
16061612
15835914
189163750
LDP
Communication cost (byte)
Client
Client
Client 3
Client 4
Total
Missing IDs
41687712
47518512
53953062
44605836
187765
122
Key exchange
0
0
0
Noise leader selection
0
0
0
Sending noise
0
Sending noised messages
53248
47688
46816
48760
196512
XGBoost update
826220
396448
245826
53278
1521772
Total
42567180
47962648
54245704
44707874
189483406
FEVERLESS
Communication cost (byte)
Client
Client
Client 3
Client 4
Total
Missing IDs
48943962
42453876
26117958
71374524
188890320
Key exchange
60
60
60
60
240
Noise leader selection
11720
11772
14136
9856
47484
Sending noise
3840
3968
4620
3080
15508
Sending masked messages
46904
47120
56560
39448
190032
XGBoost update
68820
334874
456742
661876
1522312
Total
49075306
42851670
26650076
72088844
190665896
AHE
Communication cost (byte)
Client
Client
Client 3
Client 4
Total
Missing IDs
41995818
40671666
61365564
42890796
186923844
Key exchange
0
0
0
Noise leader selection
12752
12008
10656
11732
47148
Sending noise
4148
3900
3580
4112
15740
Sending encrypted messages
1632768
1537792
1364992
1502464
6038016
XGBoost update
58
301552
264726
374816
1522588
Total
44226980
42526918
63009518
44783920
194547336
Table 10: Comparison of communication cost among Baseline, LDP, FEVERLESS and AHE with
Bank Marketing.
41

---

Under review as a conference paper at ICLR 2022
Baseline
Communication cost (byte)
Client
1
Client 2
Client
Client 4
Total
Missing IDs
596475
626793.75
407826.375
606742.15 12.
2237837.25
Key exchange
0
0
0
Noise leader selection
0
0
0
Sending noise
0
0
Sending messages
30400
29944
34504
31008
125856
XGBoost update
7496.75
128
22279.5
4403.75
34308
Total
634371.75
6568665.55
464609.875
642153.875
2398001.22
LDP
Communication cost (byte)
Client 1
Client 2
Client
Client 4
Total
Missing IDs
4411
15.125
610937.25
601907.624
619855.5
2273815.5
Key exchange
0
0
Noise leader selection
0
0
0
Sending noise
0
0
Sending noised messages
33920
29984
30792
29912
124608
XGBoost update
16694.5
92
10253
7273.125
34312.625
Total
491729.625
641013.25
642952.625
657040.625
2432736.
FEVERLESS
Communication cost (byte)
Client 1
Client 2
Client
Client 4
Total
Missing IDs
540828.75
608693.25
630403.
573725.625
22.6
2353650,75
Key exchange
60
60
60
240
Noise leader selection
7384
6848
6852
7308
28392
Sending noise
2572
2212
2220
2388
9392
Sending masked messages
29552
27424
27424
29264
113664
XGBoost update
7528.125
7366.5
8258.5
11079.5
34232.625
Total
587924.875
652603.75
675217.625
623825.125
2539571.378
AHE
Communication cost (byte)
Client 1
Client 2
Client
Client 4
Total
Missing IDs
543852.375
601610.625
602340.75
592997. 625
2340801.375
Key exchange
0
Noise leader selection
7512
7200
7324
7148
29184
Sending noise
2596
2360
2396
2352
9704
Sending encrypted messages
962304
922112
938240
915968
3738624
XGBoost update
14504.625
3886.625
9163.5
6616.5
34171.25
Total
1530769
1537169.25
1559464.25
1525082.125
6152484.625
Table 11: Comparison of communication cost among Baseline, LDP, FEVERLESS and AHE with
Banknote Authentication.
42


Reviews:
[{"review_id": "rCb4yaAucy", "reviewer": "Reviewer_chCc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: \n1. The problem addressed in this paper is of practical importance for many real-world applications.\n2. The challenges and the proposed solutions are well motivated.\n3. The paper is also very well-written and has a nice flow.\n\n\nCons:\n1. Several typos: for example:  “multiply hospitals” should be “multiple”.\n2. The main contribution of the paper is to loose the assumption of centralized labels to decentralized labels. Adapting existing secure aggregation to outperform homomorphic encryption-based VFL on latency or differential privacy on accuracy is straightforward. As such, the paper has a limited novelty from the ML perspective.\n3. The proposed method has shown improved performance over HE on the aspect of training time and DP on the aspect of accuracy. The paper, however, fails to compare with HE on the aspect of accuracy and DP HE on the aspect of latency. \n", "summary_of_the_paper": "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. ", "summary_of_the_review": "The problem addressed in this paper is of practical importance for many real-world applications. Thus, I would like to see its presentation at the conference. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Rd6JSeSz0rq", "reviewer": "Reviewer_dHiP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. There are several writing issues with the paper -\ni) There should be a background section that introduces the crypto primitives briefly - the main body should be self-contained.\nii) Formal security theorems should be presented in the main paper - only full proofs should be in the Appendix.\niii) A copy-edit pass is required for the paper - some examples\n\"In practice, a VFL scheme supporting distributed labels\nis of necessity.\" --> is necessary\n\"without disclosing both feature\" --> without disclosing either ... or..\n\"where a single label is only associated with a client.\" - client is associated with a single label\n\n2. There is a fundamental flaw in the security guarantee of the paper - the source client and the noise leader could collude, this would reveal the aggregation without noise (the noise can be subtracted out).\n3. I could not understand the problem setting - the motivating examples are hospitals and banks. But would not every patient visit a particular hospital or a particular bank (based on locality etc), how is this different from horizontal data split?\n4. I could understand why would the info that client A holds label a be made public (Sec 2.3)? Is not label privacy a goal of the scheme?\n5. I was confused with the term label space $\\mathcal{Y}=\\{y_1,\\cdots,y_m\\}$ - it seems like the label set and not space (label space would be the space of classes like binary for covid test and so on). Also I am confused with the notation $X_j| j \\in {1,\\cdots, f\\}$ since the number of features is $d$ (instead of $f$)?\n6. Evaluation is inadequate - performance microbenchmarks such as break down of client/ noise leader and source client time, bandwidth analysis etc are missing.", "summary_of_the_paper": "The paper proposes a secure protocol in the FL setting for XGBoost where the dataset is vertically split. The proposed mechanism is based on masking and selecting a random client to generate DP noise.", "summary_of_the_review": "There are several writing issues in the paper. Additionally, the paper suffers from a security flaw.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "QicKyAt88g4", "reviewer": "Reviewer_NGrb", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides a comprehensive security analysis of the proposed protocol. However, I have the following concerns.\n1. The paper is not easy to read. The preliminary and many details about the algorithm are put into the appendix, which is not friendly to the readers.\n2. The paper provides two examples (i.e., hospitals, bank branches) to demonstrate that the distributed label setting is common in practice. However, these two examples are not convincing. In these two examples, the training examples are usually distributed to the clients (e.g., customers are registered to distinct branches as mentioned in the paper), which is more like a horizontal federated learning setting.\n3. In the proposed algorithm, the clients send the sum of the gradients $G$ to the source client. However, the source client needs to know $G_L$ and $G_R$ to compute the gain.  How does the client split the received $G$ into $G_L$ and $G_R$?\n4. For a missing label of the source client, there may be multiple clients that hold the label. Then, the noises are injected into the gradients of the same sample. In this case, what is the overall privacy budget for the sample? Also, does the algorithm still work in such as case?\n5. The datasets used in the experiments are small. The authors should better conduct experiments on a dataset with at least a million samples.\n6. It is not clear to compare the exact performance of different approaches in Figure 2 and Figure 4. The authors can add a table to show the accuracy and time of different approaches with a default depth and number of trees.\n7. In the computation cost, the time complexity of generated masks is O(xxx * n), while the overall complexity is O(xxx + n). Is it a typo?\n", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, I think the paper can be significantly improved in writing. The paper does not convince me about the importance of the distributed label setting. Moreover, I do not fully understand how the algorithm work. Please refer to my main reviews.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "G78HE0OOlpe", "reviewer": "Reviewer_Wj2y", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\n1. The writing and figures are clear. \n\n2. Thorough review of background material.\n\n3. Theoretical and empirical analysis of computation and communication costs demonstrate that the proposed approach compares very favorably to MPC-based solutions. \n\n4. Thorough security analysis proves that the proposed approach is robust to collusion of up to n-2 clients. \n\n5. The proposed combination of Diffie-Hellman key exchange and global differential privacy is ingenious and the experimental results demonstrate the clear advantage of using this combination compared to local differential privacy at each client.\n\n6. The proposed novel setting for vertical federated learning with decentralized labels is very well motivated as shown from the COVID19 example highlighted in the paper. \n\n\n### Weaknesses \n\n1. The proposed method performs poorly on small datasets.\n\n\n\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper introduces a novel setting for VFL with decentralized labels, which is very well motivated, and proposes novel protocol for this setting, which is ingenious and shows significant advantages compared to existing methods.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the problem tackled is important but raise several substantial issues that justify not to accept the paper in its current form. I would encourage the authors to clarify further the crypto part of the paper (dHiP, 2., 4.) and work on how to relax or improve the model assumptions (NGrb). Also, the author's reply to chCc, point 2. becomes more disputable as federated learning is further developed. The argument can be refined.

On a personal note, the statement of Theorem 3.3 could be made clearer, in particular in simplifying (while weakening a bit) the probability bound.

AC.
Decision: Reject