# Scalable Multi-Party Privacy-Preserving Gradient Tree Boosting over
Vertically Partitioned Dataset with Outsourced Computations

Kennedy Edemacu, Beakcheol Jang, Jong Wook Kim Kennedy Edemacu is with the
Department of Computer Science and Electrical Engineering, Muni University,
Arua, UgandaBeackcheol Jang is with the Graduate School of Information, Yonsei
University, Seoul, South KoreaJong Wook Kim is with the Department of Computer
Science, Sangmyung University, Seoul, South KoreaE-mail addresses:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Wook Kim is the
corresponding authors.

###### Abstract

Due to privacy concerns, multi-party gradient tree boosting algorithms have
become widely popular amongst machine learning researchers and practitioners.
However, limited existing works have focused on vertically partitioned
datasets, and the few existing works are either not scalable or tend to leak
information. Thus, in this work, we propose SSXGB which is a scalable and
secure multi-party gradient tree boosting framework for vertically partitioned
datasets with partially outsourced computations. Specifically, we employ an
additive homomorphic encryption (HE) scheme for security. We design two sub-
protocols based on the HE scheme to perform non-linear operations associated
with gradient tree boosting algorithms. Next, we propose a secure training and
a secure prediction algorithms under the SSXGB framework. Then we provide
theoretical security and communication analysis for the proposed framework.
Finally, we evaluate the performance of the framework with experiments using
two real-world datasets.

###### Index Terms:

Gradient tree boosting, multi-party machine learning, privacy-preservation,
homomorphic encryption, vertically partitioned dataset.

##  I Introduction

The privacy-preserving multi-party machine learning paradigm has shown
promising potential in encouraging collaboration between organizations while
preserving the privacy of their data [1]. The basic idea of the privacy-
preserving multi-party machine learning is that each collaborating party holds
a private dataset and trains a local model using the dataset. The local models
from the participating parties are then aggregated to create a single more
powerful model. Hence, different organizations can jointly train a machine
learning model without sharing their private datasets.

Although the privacy-preserving multi-party machine has attracted a lot of
attention recently, the majority of the existing works focus on linear
regression [2, 3], logistic regression [4, 5] and neural networks [6, 7] over
vertically and horizontally partitioned datasets111For horizontally
partitioned datasets, participants hold subsets of the samples with the same
features, while for vertically partitioned datasets, participants hold the
same samples with different features [8].

Like the above methods, gradient tree boosting [9] which is one of the most
popular machine learning methods has also received considerable attention due
to its effectiveness in a wide range of application areas such as fraud
detection [10], feature selection [11] and product recommendation [12].
Efforts to address the privacy concerns for gradient tree boosting in multi-
party setting are presented in [13, 14, 15, 16, 17, 18]. The datasets in [13,
14, 15] are horizontally partitioned while the datasets are vertically
partitioned in [16, 17, 18].

In this work, we focus on the latter dataset partitioning. The current privacy
preservation efforts proposed for the multi-party gradient tree boosting
method with vertically partitioned datasets have a number of limitations. In
[18], the proposed scheme is not scalable, it is limited to only two
collaborating parties. And in [16, 17], intermediate information gets revealed
during the model training. Thus, designing a scalable and yet secure gradient
tree boosting scheme has remained open for investigation, and hence we intend
to answer the question, how to construct a scalable and secure XGBoost [19]
over vertically partitioned datasets in this work.

Apart from the high memory usage challenge, the secure XGBoost model training
requires complicated computation primitives such as $division\text{ and
}argmax$ [18]. To address these challenges and build a scalable but secure
XGBoost over vertically partitioned datasets, we propose the SSXGB framework
that securely outsources and performs the complicated computations in
encrypted form. The key idea is to allow the participants to jointly train a
model by sharing their encrypted information with a server that in turn
collaborates with a second server to securely perform further computations to
complete the generation of the model. Specifically, we present an additive
homomorphic encryption (HE) scheme that provides the addition (Add) and
subtraction (Sub) primitives. We also present sub-protocols designed to
provide additional primitives such as the multiplication (Mult) and
comparisons. Next, we propose new sub-protocols based on the HE scheme for the
division (Div) and argmax primitives. We employ the secure computation
primitives to build the scalable and secure XGBoost model. Then, we present a
secure prediction algorithm for predictions based on the trained model. We
present the analysis of our framework and its implementation using real-world
datasets. A summary of our contributions are presented as follows:

  * •

We propose sub-protocols based on an additive HE scheme used to perform
primitive secure operations during a machine learning task. The sub-protocols
are collaboratively executed by two non-colluding servers.

  * •

We design a novel scalable and privacy-preserving multi-party XGBoost training
algorithm and a corresponding prediction algorithm. The algorithms are
constructed under the semi-honest security assumption and there is no limit on
the number of participants involved.

  * •

We conduct experiments using real-world datasets to demonstrate the
effectiveness and efficiency of our proposed framework.

The rest of the paper is organized as follows. In section II, we present the
related works. Section III contains the preliminary concepts. In section IV,
we present our proposed HE sub-protocols for non-linear operations. We present
the overview of the proposed SSXGB framework in section LABEL:sec:overview.
Sections V and VI present the secure training and prediction algorithms of the
SSXGB framework. In sectionVII, we present theoretical security and
communication analysis. Performance evaluation is presented in section VIII
and section IX concludes the paper.

##  II Related work

Recently, efforts devoted to multi-party machine learning researches have
shown a huge potential in addressing the training data scarcity problem while
preserving the data privacy [1, 5, 20, 21]. However, the majority of the works
focus on linear machine learning models. Little effort has been invested in
researching multi-party gradient tree boosting models. Currently, a multi-
party gradient tree boosting framework can be categorized as a horizontal or
vertical framework, depending on how its dataset is partitioned amongst the
collaborating participants.

###  II-A Horizontal Multi-party Gradient Tree Boosting Frameworks

In horizontal multi-party gradient tree boosting frameworks, dataset features
are shared amongst the collaborating participants. Several works have adopted
this approach. In [14], Ong et al. designed a multi-party gradient tree
boosting framework in which the participants exchange adaptive histogram
representation of their data during model learning. Liu et al. combined secret
sharing with homomorphic encryption to prevent participants from dropping out
and securely aggregate their gradients during XGBoost training [15]. [22]
employed an oblivious algorithm to prevent privacy violations at hardware
enclaves during learning of a multi-party gradient tree boosting model. In
[23], Yang et al. designed a multi-party tree boosting framework with anomaly
detection from extremely unbalanced datasets. [24] designed secure training
and prediction frameworks for multi-party gradient tree boosting. A secret
share scheme is employed for the secure training while a key agreement scheme
and an identity-based encryption and signature scheme are employed for the
secure prediction framework. Unlike the above frameworks, our work focuses on
vertically partitioned datasets.

###  II-B Vertical Multi-party Gradient Tree Boosting Frameworks

In vertical multi-party gradient tree boosting frameworks, sets of samples are
shared amongst the collaborating participants. Several existing efforts have
focused on addressing concerns in this setting. In [16], Cheng et al. designed
a lossless privacy-preserving multi-party gradient tree boosting framework
using a homomorphic encryption scheme. The framework achieves the same
accuracy as the non-federated gradient tree boosting frameworks. However, it
reveals the intermediate parameters during the training process which can lead
to privacy violations. In [18, 17], the authors proposed secure training and
prediction frameworks for privacy-preserving multi-party gradient tree
boosting. However, their schemes are unscalable, i.e., they are limited to two
parties. In contrast, in our work, we proposed a privacy-preserving multi-
party gradient tree boosting framework that is scalable and does not expose
the intermediate parameters.

##  III Preliminaries

This section summarizes the gradient tree boosting framework, XGBoost, and the
cryptographic foundations used to construct our proposed privacy-preserving
multi-party gradient tree boosting framework.

###  III-A XGBoost

XGBoost is an implementation of gradient tree boosting. It iteratively
minimizes the loss sum of all the samples in an additive manner [19].
Normally, the loss function $l(y,\hat{y})$ is defined to minimize the
difference between the predicted and the true values. In XGBoost, to obtain
the predicted values, regression trees over a given dataset are used. The
trees are greedily added to one another after every iteration [19, 16, 18].

To fit a tree, for each sample $i$, the algorithm generates the first order
derivative as $g_{i}$ and the second order derivative as $h_{i}$, i.e.,

$g_{i}=\partial_{\hat{y_{i}}^{(t-1)}}l(y_{i},\hat{y_{i}}^{(t-1)})\text{ and
}h_{i}=\partial^{2}_{\hat{y_{i}}^{(t-1)}}l(y_{i},\hat{y_{i}}^{(t-1)})$ (1)

where $\hat{y_{i}}^{(t-1)}$ denotes the predicted value for the last
iteration.

The sum of $g_{i}$ and $h_{i}$ for a nodes’ instance set $I_{j}$ can be
computed as:

$G_{j}=\sum_{i\in I_{j}}g_{i}\text{ and }H_{j}=\sum_{i\in I_{j}}h_{i}.$ (2)

The optimal weight $w^{\ast}_{j}$ for the leaf node is obtained as:

$w^{\ast}_{j}=-\frac{\sum_{i\in I_{j}}g_{i}}{\sum_{i\in I_{j}}h_{i}+\lambda}$
(3)

where $\lambda$ is the regularizer for the leaf weight.

At each iteration, i.e., during the construction of each tree, Equation 4, is
iteratively used for split decisions at each intermediate node from depth 0
until the maximum depth is reached.

${L}_{split}=\frac{1}{2}[\frac{(\sum_{i\in I_{L}}g_{i})^{2}}{\sum_{i\in
I_{L}}h_{i}+\lambda}+\frac{(\sum_{i\in I_{R}}g_{i})^{2}}{\sum_{i\in
I_{R}}h_{i}+\lambda}-\frac{(\sum_{i\in I}g_{i})^{2}}{\sum_{i\in
I}h_{i}+\lambda}]-\gamma$ (4)

where $\gamma$ is the regularizer for the leaf number, and $I_{L}\text{ and
}I_{R}$ are the instance set for the left and right child nodes. Thus,
$G_{L}=\sum_{i\in I_{L}}g_{i}$ and $H_{L}=\sum_{i\in I_{L}}h_{i}$ denote the
sum of $g_{i}$ and $h_{i}$ for the left child node instance space, and
$G_{R}=\sum_{i\in I_{R}}g_{i}$ and $H_{R}=\sum_{i\in I_{R}}h_{i}$ denote the
sum of $g_{i}$ and $h_{i}$ for the right child node instance space.

###  III-B Homomorphic Encryption (HE)

In this work, we adopt the BCP Scheme [25, 26], which is an additive
homomorphic encryption scheme. The scheme comprises the following algorithms:

(1) Setup($k$): For a given security parameter $k$, and two large primes $p$
and $q$ of length $k$ bits, the algorithm generates the public parameters
($pp$) and the master key ($mk$) as follows. First, it computes $N=pq$. It
then randomly chooses $g\in\mathbb{Z}^{*}_{N^{2}}$ of order
$pp^{\prime}qq^{\prime}$ (s.t. $g^{p^{\prime}q^{\prime}}=1+kN$ for
$k\in[1,N-1]$), where $p^{\prime}=\frac{p-1}{2}$ and
$q^{\prime}=\frac{q-1}{2}$. The algorithm outputs $pp$ as ($N,g,k$) and $mk$
as ($p^{\prime},q^{\prime}$).

(2) KeyGen($pp$): Generates the public-secret key pairs for users. To generate
the key pair for a user $i$, the algorithm randomly picks
$a_{i}\in\mathbb{Z}_{N^{2}}$, and outputs the public key ($pk_{i}$) as
$h_{i}=g^{a_{i}}\text{ mod }N^{2}$ and the secret key ($sk_{i}$) as $a_{i}$.

(3) Enc($pp,pk_{i},m$): Encrypts the message $m\in\mathbb{Z}_{N}$ under the
public key $pk_{i}$. To encrypt $m$, the algorithm randomly chooses
$r\in\mathbb{Z}_{N^{2}}$ and outputs the ciphertext ($CT$) as ($A,B$), where

$A=g^{r}\text{mod }N^{2}\text{ and }B=h_{i}^{r}(1+mN)\text{mod }N^{2}.$

(4) Dec($pp,sk_{i},CT$): Recovers the message $m$ from $CT=(A,B)$ using the
corresponding $sk_{i}=a_{i}$. The recovery is performed as follows:

$m=\frac{B/(A^{a_{i}})-1\text{ mod }N^{2}}{N}.$ (5)

Note that the above recovery is successful only for the $pk_{i}$-$sk_{i}$
pair.

(5) mDec($pp,pk_{i},mk,CT$): Recovers any properly created ciphertext using
the master key, i.e., the algorithm can decrypt $CT$ encrypted under any
users’ public key $pk_{i}$ (so long as $pk_{i}$ is legitimate). For the
decryption to proceed, first $a\text{ mod }N$ and $r\text{ mod }N$ are
computed as:

$a\text{ mod }N=\frac{h^{p^{\prime}q^{\prime}}-1\text{ mod
}N^{2}}{N}.k^{-1}\text{ mod }N$ (6)

and

$r\text{ mod }N=\frac{A^{p^{\prime}q^{\prime}}-1\text{ mod
}N^{2}}{N}.k^{-1}\text{ mod }N,$ (7)

where $k^{-1}$ is the inverse of $k\text{ mod }N$. $m$ is recovered from $CT$
as:

$m=\frac{(B/(g^{\gamma}))^{p^{\prime}q^{\prime}}-1\text{ mod
}N^{2}}{N}.\delta\text{ mod }N,$ (8)

where $\delta$ is the inverse of $p^{\prime}q^{\prime}\text{ mod }N$ and
$\gamma:=ar\text{ mod }N$.

###  III-C BCP Sub-protocols

To perform arithmetic operations homomophically, [26, 25, 27] proposed the
following subprotocols.

(a) KeyProd: The sub-protocol transforms the encryptions under the different
user public keys $pk_{1},\cdots,pk_{n}$ to encryptions under a joint public
key $pk_{\Sigma}:=\prod_{i=1}^{n}pk_{i}$. The transformation is an interactive
process that involves two non-colluding servers (see [26] for the details).
The encryption under the joint public key $pk_{\Sigma}$ can only be decrypted
using the sum of all the user secret keys $sk_{\Sigma}=\sum_{1}^{n}sk_{i}$ or
the master key.

(b) Add: Returns the encrypted sum of two encrypted messages. Suppose, two
messages $m_{1}$ and $m_{2}$ are encrypted as ⟦$m_{1}\text{\textrbrackdbl}$
and ⟦$m_{2}$⟧, respectively. ⟦$.\text{\textrbrackdbl}$ denotes an encryption
operation under the joint public key in our case. The Add sub-protocol sums
the two ciphertexts as ⟦$m_{1}+m_{2}$⟧. The fact that the BCP HE scheme
achieves its additive nature under the same public key straightaway simplifies
the Add sub-protocol. The encryptions under different user public keys can
first be transformed to be under the same public key using the KeyProd sub-
protocol, then followed by their addition. Thus, the sum of two encryptions
($A,B$) and ($A^{\prime},B^{\prime}$) under the same public key can be
computed as (see [26] for the details):

$(\bar{A},\bar{B})\leftarrow(A.A^{\prime}\text{mod
}N^{2},B.B^{\prime}\text{mod }N^{2}).$

(c) Mult: The Mult sub-protocol returns the encrypted product of two
ciphertexts. The process involves interaction between two non-colluding
servers (see [26] for the details). Thus, given two ciphertexts ⟦$m_{1}$⟧and
⟦$m_{2}$⟧, the Mult sub-protocol returns ⟦$m_{1}\times m_{2}$⟧.

(d) TransDec: The TransDec sub-protocol does the opposite of the KeyProd sub-
protocol. It transforms the encryptions under the joint public key
$pk_{\Sigma}$ to encryptions under the user public keys
$pk_{1},\cdots,pk_{n}$. The transformation process involves interactions
between two non-colluding servers (see [26] for the details).

(e) Neg: The Neg sub-protocol negates an encrypted message. For example, given
an encryption of a message $m$ as ⟦$m$⟧, the Neg subprotocol transforms it to
⟦$-m\text{\textrbrackdbl}$ as (see [25, 27] for the details):

$\big{(}g^{(N-1).r}\text{mod }N^{2},h^{(N-1).r}(1+m.N)^{N-1}\text{mod
}N^{2}\big{)}=\text{\textlbrackdbl}-m\text{\textrbrackdbl}.$

(f) Exp: Using the same principles as in (e) above, the Exp sub-protocol
returns the product of an encrypted message ⟦$m\text{\textrbrackdbl}$ and a
constant $k$ as ⟦$km$ ⟧. It can be computed as below:

$\big{(}g^{(N+k).r}\text{mod }N^{2},h^{(N+k).r}(1+m.N)^{N+k}\text{mod
}N^{2}\big{)}=\text{\textlbrackdbl}km\text{\textrbrackdbl}.$

The correctness is similar to the Neg sub-protocol.

(g) Sub: The Sub sub-protocol returns the difference between two ciphertexts.
For example, given $m_{1}$ and $m_{2}$ encrypted as ⟦$m_{1}$⟧ and ⟦$m_{2}$⟧,
respectively, the Sub sub-protocol returns ⟦$m_{1}-m_{2}$⟧. We describe the
sub-protocol as follows: First, ⟦$m_{2}$⟧ is negated using the Neg sub-
protocol. Then, the Add is used to complete the process. Thus,

$\text{\textlbrackdbl}m_{1}-m_{2}\text{\textrbrackdbl}=\text{{Add}}(\text{\textlbrackdbl}m_{1}\text{\textrbrackdbl},\text{{Neg}}(\text{\textlbrackdbl}m_{2}\text{\textrbrackdbl})).$

(h) LGT: The less than or greater than (LGT) sub-protocol shows the
relationship between two ciphertexts, i.e.,
$\text{\textlbrackdbl}m_{1}\text{\textrbrackdbl}\geq\text{\textlbrackdbl}m_{2}\text{\textrbrackdbl}$
or
$\text{\textlbrackdbl}m_{1}\text{\textrbrackdbl}<\text{\textlbrackdbl}m_{2}\text{\textrbrackdbl}$.
The sub-protocol returns $1$ if
$\text{\textlbrackdbl}m_{1}\text{\textrbrackdbl}<\text{\textlbrackdbl}m_{2}\text{\textrbrackdbl}$,
it returns $0$ otherwise. It is an adaptation of the SLT protocol in [27]. A
detailed description is presented in Appendix A.

##  IV Proposed Computation Primitives

Figure 1: Illustration of the Div sub-protocol

Building gradient tree boosting algorithms requires more complicated
computation primitives such the division and argmax. The division sub-protocol
based on BCP scheme proposed in [27] is inefficient and unsuitable for our
setting. Thus, we propose two sub-protocols Div and Sargmax based on the BCP
HE scheme to perform the division and argmax operations, respectively.

####  IV-1 Div

The Div sub-protocol outputs the encrypted division of two ciphertexts. Given
two ciphertexts $\text{\textlbrackdbl}m_{1}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}m_{2}\text{\textrbrackdbl}$, the Div sub-protocol
returns $\text{\textlbrackdbl}m_{1}\div m_{2}\text{\textrbrackdbl}$, $m_{1}$
being the nominator and $m_{2}$ the denominator. The protocol is run
interactively between two non-colluding servers, say server C and server S as
illustrated in Figure 1.

Using the Exp sub-protocol, the server C first masks the ciphertexts
$\text{\textlbrackdbl}m_{1}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}m_{2}\text{\textrbrackdbl}$ as
$\text{\textlbrackdbl}\tau_{1}m_{1}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}\tau_{2}m_{2}\text{\textrbrackdbl}$, respectively. Where
$\tau_{1},\tau_{2}\in\mathbb{Z}_{N}$. The server C then sends
$\text{\textlbrackdbl}\tau_{1}m_{1}+\tau_{2}m_{2}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}\tau_{1}m_{2}\text{\textrbrackdbl}$ to the server S. The
two ciphertexts are decrypted by the server S. In plaintext, the server S
performs $\frac{1}{\tau_{1}m_{2}}\times(\tau_{1}m_{1}+\tau_{2}m_{2})$ and
encrypts the result and send it back to the server C. The server C extracts
$\text{\textlbrackdbl}\frac{m_{1}}{m_{2}}\text{\textrbrackdbl}$ by subtracting
$\text{\textlbrackdbl}\frac{\tau_{2}}{\tau_{1}}\text{\textrbrackdbl}$ out of
the result received from the server S. See Appendix B for the proof of
correctness.

####  IV-2 Sargmax

The Sargmax sub-protocol returns the arguments of the maximum value. In our
case, the maximum value returned is in encrypted form. The maximum encrypted
value is obtained using the LGT sub-protocol. Once the maximum value is
obtained, its associated arguments are returned as the Sargmax sub-protocol’s
result. The details are shown in Algorithm 1.

1 function Sargmax(dict)

2

3//Input: dict -is a dictionary of encrypted values

4 max=None

5 for  _key in dict.keys()_ do

6 if  _max==None_ then

7 max = dict[key]

8 else

9 //Securely compare the encrypted values

10 LGT(max, dict[key])

11 if  _max $>$dict[key]_ then

12 max=max

13 else

14 max=dict[key]

15 end if

16

17 end if

18

19 end for

20 return key

21 end

Algorithm 1 Secure argmax Computation Algorithm

In this section, we first describe the involved entities, followed by the
workflow of our proposed framework.

###  IV-A Entities of the Framework

Figure 2: Entities of our proposed framework

Our proposed framework comprises three types of entities: a set of
participants, and two servers S and C as illustrated in Figure 2.

Participants: Participants are volunteers willing to take part in multi-party
gradient tree boosting model learning. In this work, each participant holds a
portion of a vertically partitioned dataset. We refer to the participant
holding the label feature as Label Bearing Participant (LBP). There is only
one LBP. Each participant only interacts with Server C. Additionally, each
participants holds a public-private key pair.

Server S: S holds $pk_{\Sigma}$, $mk$ and $pk_{1},\cdots,pk_{n}$. Thus, S can
decrypt any legitimately encrypted message. However, S only communicates
directly with server C, i.e., it does not directly access the participants’
data. It mainly helps with decrypting masked data from server C. We assume
that S is honest-but-curious [28, 29, 30].

Server C: C holds $pk_{\Sigma}$ and $pk_{1},\cdots,pk_{n}$. C directly
communicates with all the other entities. It has access to the instance space
and encrypted intermediate parameters received from the participants. C and S
then collaboratively perform computations on the received parameters to build
the model. All the data from C to S are masked to prevent S from observing the
actual contents of the data. We also assume that C is honest-but-curious. An
example of C is a cloud server.

###  IV-B Workflow of Our Proposed Scheme

The general workflow of our proposed SSXGB training is shown in Algorithm 2.
As shown in Algorithm 2, three major protocols namely: LBPXGBTRAIN, SBUILDTREE
and SPREDTREE are invoked during the model learning. To prevent inference
attacks on label information, we adopt the second proposal of [16], where the
first tree is built by the LBP. The LBPXGBTRAIN protocol is thus executed by
the LBP for the above purpose.

1 function SXGBTRAIN(X, Y)

2

3//Input: X:$\\{\text{X}^{i}\\}_{i=1}^{n}$ is an aggregation of Xi from $n$
participants.

4 //Input: Y is the label borne by the LBP

5 for  _t= $\text{1},\cdots,\text{T}$_ do

6 if  _TreeList==Empty_ then

7 LBPXGBTRAIN($\text{X}^{lbp}\text{, Y}$)

8 else

9 Compute:
⟦Gt-1⟧:$\sum_{i}(\text{\textlbrackdbl}g_{t-1}\text{\textrbrackdbl})$ and
⟦Ht-1⟧: $\sum_{i}(\text{\textlbrackdbl}h_{t-1}\text{\textrbrackdbl})$

10 //Construct a tree using ⟦Gt-1⟧and ⟦Ht-1⟧

11 $F_{t}=\text{SB{\scriptsize UILD}T{\scriptsize
REE}}$($\text{\textlbrackdbl}G_{t-1}\text{\textrbrackdbl},\text{\textlbrackdbl}H_{t-1}$⟧)

12 //Predict using the current tree

13 ⟦$\hat{Y}_{t}\text{\textrbrackdbl}=\text{SP{\scriptsize RED}T{\scriptsize
REE}}$($F_{t},X$)

14 TREELIST$.\text{append}(F_{t})$

15 ⟦$\hat{Y}\text{\textrbrackdbl= \textlbrackdbl}\hat{Y}\text{\textrbrackdbl+
\textlbrackdbl}\hat{Y}_{t}\text{\textrbrackdbl}$

16 end if

17

18 end for

19 return TREELIST

20 end

Algorithm 2 Scalable and Secure XGBoost Training

Once the LBPXGBTRAIN protocol is executed, the returned parameters are
encrypted and sent to server C for the rest of the participants to join the
process. The two protocols SBUILDTREE and SPREDTREE are then iteratively
executed by all the participants and the servers to complete the model
learning process. At each iteration $t$, the SBUILDTREE is invoked to securely
build a tree, while the SPREDTREE is invoked to make predictions using the
built tree at $t$. Finally, the protocol returns a trained model TREELIST. The
details are presented in the subsequent sections.

##  V Scalable and Secure Multi-Party XGBoost Building

This section presents the building of our proposed SSXGB model over vertically
partitioned dataset. We specify that all participants bear distinct sets of
data features. The LBP bears the label feature. We also assume that the
participants have the same samples. We emphasize that server C operates only
on encrypted data and does not have direct access to the participants’ data,
including the label.

1function LBPXGBTRAIN($\text{X}^{lbp}\text{, Y}$)

2

3//Input: Xlbp:$\\{x^{i,j}_{M\times\mathcal{N}_{lbp}}\\}$ where
$\mathcal{N}_{lbp}$ is the number of features borne by the LBP

4 //Input: Y:$\\{y\\}^{M}_{i=1}$ is the label

5 //Compute the base score

6 F${}_{0}=\text{C{\scriptsize OMPUTE}B{\scriptsize ASE}S{\scriptsize
CORE}(Y)}$

7 TREELIST = []

8 //Initial prediction

9 $\hat{\text{Y}}=F_{0}$

10 Compute: G0:$\sum_{i}g_{0}$ and H0:$\sum_{i}h_{0}$

11 //Construct a tree using $\text{G}_{0}$ and $\text{H}_{0}$

12 $\text{F}_{1}=\text{B{\scriptsize UILD}T{\scriptsize
REE}}$($\text{G}_{0},\text{H}_{0}$)

13 //Predict using the tree $F_{1}$

14 $\hat{\text{Y}}_{1}=\text{P{\scriptsize RED}T{\scriptsize
REE}}$($F_{1},X^{lbp}$)

15 $\hat{\text{Y}}=\hat{\text{Y}}+\hat{\text{Y}}_{1}$

16 //Encrypt the base score and the tree node values, and update the model
list

17
TREELIST$.\text{append(Enc(F}_{0}\text{)}_{pk_{lbp}},\text{Enc(F}_{1}\text{)}_{pk_{lbp}})$

18 //Encrypt the label information and the updated prediction matrix

19 Enc($\text{Y)}_{pk_{lbp}}$, Enc($\hat{\text{Y}}\text{)}_{pk_{lbp}}$

20 return TREELIST, Enc($\text{Y)}_{pk_{lbp}}$,
Enc($\hat{\text{Y}}\text{)}_{pk_{lbp}}$

21 end

Algorithm 3 The First Tree Building by the LBP

###  V-A The First Secure Tree Building by LBP

As stated in the previous section, to prevent participants from inferring on
the label information, we adopt the proposal of [16] in which the LBP builds
the first tree. The LBPXGBTRAIN function shown in Algorithm 3 is invoked for
that purpose. The LBPXGBTRAIN function takes as input the dataset (Xlbp, Y),
where Xlbp is the feature matrix of the LBP and Y is the label information. In
other words, the LBP does not require the other participants’ data to build
the first tree. Since there is no collaboration in building the first tree,
the sub-routines: COMPUTEBASESCORE, BUILDTREE and PREDTREE for computing the
base score, building the first tree and making the initial predictions,
respectively, are consistent with the mechanisms of XGBoost [19].

Once the first tree is constructed, LBP encrypts the base score and the node
values of the tree with its public key ($pk_{lbp}$). Next, it updates the
model with the encrypted base score and the tree. It also encrypts the label
information and the prediction matrix with its public key. Finally, it returns
TREELIST, Enc($\text{Y)}_{pk_{lbp}}$ and
Enc($\hat{\text{Y}}\text{)}_{pk_{lbp}}$. The returned parameters are sent to
server C to continue with the model training.

1function SBUILDSPREDTREE($\text{\textlbrackdbl
G}_{t-1}\text{\textrbrackdbl},\text{\textlbrackdbl
H}_{t-1}\text{\textrbrackdbl}$)

2

3//Input:-
⟦Gt-1⟧:$\\{\text{\textlbrackdbl}g_{t-1}\text{\textrbrackdbl}\\}_{i=1}^{M}$,
⟦Ht-1⟧:$\\{\text{\textlbrackdbl}h_{t-1}\text{\textrbrackdbl}\\}_{i=1}^{M}$

4 /* Computed by SERVER C */

5 if  _R OOTNODE==None_ then

6 //Register the current node as the root node

7 ROOTNODE=CURRENTNODE

8 end if

9

10 /* Computed at each PARTICIPANT $i$ */

11 foreach  _feature $j$_ do

12 Propose split candidates $\\{x\\}^{j,0},\cdots,\\{x\\}^{j,K}$

13 end foreach

14 foreach  _$\\{x\\}^{j,k}$_ do

15 Compute $\text{\textlbrackdbl G}^{j,k}_{t-1}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl H}^{j,k}_{t-1}\text{\textrbrackdbl}$

16 Create a lookup table and record $j,k$ and $\\{x\\}^{j,k}$ in the table

17 Create a tuple ($j,k$)

18 end foreach

19 Send the tuple (($j,k$), $\text{\textlbrackdbl
G}^{j,k}_{t-1}\text{\textrbrackdbl},\text{\textlbrackdbl H}^{j,k}_{t-1}$⟧) to
SERVER C

20 /* Computed by SERVER C */

21 $j_{opt},k_{opt}$ = SSPLITNODE($\text{\textlbrackdbl
G}^{j,k}_{t-1}\text{\textrbrackdbl},\text{\textlbrackdbl
H}^{j,k}_{t-1}\text{\textrbrackdbl}$, $\mathcal{T}$)

22

23 /* Computed at the optimal PARTICIPANT */

24 Receive the optimal $j_{opt},k_{opt}$ from SERVER C

25 Check the lookup for $\\{x\\}^{j,k}$ associated with $j_{opt},k_{opt}$

26 Partition I based on $\\{x\\}^{j,k}$

27 Record the instance space IL with SERVER C

28 end

Algorithm 4 Secure BUILD and PRED TREE

###  V-B Secure BUILDTREE and PREDTREE

Once the first tree is built by the LBP and the results are returned to server
C, the rest of the participants can join to continue with the model training.
First, the servers C and S collaboratively transform the parameters from the
LBP encrypted under the public key $pk_{lbp}$ to be under the joint public key
$pk_{\Sigma}$ using the KeyProd sub-protocol discussed in Section III. For
example, the encrypted label information Enc($\text{Y)}_{pk_{lbp}}$ is
transformed to ⟦Y⟧, the encrypted prediction matrix
Enc($\hat{\text{Y}}\text{)}_{pk_{lbp}}$ is transformed to ⟦$\hat{\text{Y}}$⟧,
etc. Then server C computes the first and second order derivatives using the
encrypted parameters for all the instances. Next, the joint model building
resumes using the SBUILDSPREDTREE protocol shown in Algorithm 4.

The SBUILDSPREDTREE protocol is executed by multiple entities. The algorithm
takes in as input the encrypted first and second order derivatives computed by
server C. The execution begins in server C, which assigns the current node as
the root node if there exists no root node. Next, each participant, including
the LBP proposes split candidate values for each of their features as in [19].
For ease of understanding, we shall refer to all the participants including
the LBP as participant $i$. For each split candidate, each participant $i$
computes $\text{\textlbrackdbl
G}_{t-1}\text{\textrbrackdbl},\text{\textlbrackdbl
H}_{t-1}\text{\textrbrackdbl}$ which are associated with the left branch
according to [19]. Each participant $i$ also creates a lookup table to record
the split candidate information. Then, for each split candidate, each
participant $i$ sends the parameter tuple
$\mathcal{T}$=(($j,k\text{)},\text{\textlbrackdbl
G}^{j,k}_{t-1}\text{\textrbrackdbl},\text{\textlbrackdbl H}^{j,k}_{t-1}$⟧) to
the server C.

Server C then securely identifies the optimal split feature and value using
the SSPLITNODE algorithm, and sends the result to the participant bearing the
feature (optimal participant). The optimal participant then decrypts the
optimal value for the optimal feature and splits the current node’s instance
space accordingly. Finally, the optimal participant registers the left branch
instance space IL with server C after the partition.

1 function
SSPLITNODE($\text{\textlbrackdbl}G_{t-1}\text{\textrbrackdbl},\text{\textlbrackdbl}H_{t-1}\text{\textrbrackdbl}$,
$\mathcal{T}$)

2

3//Input:-
⟦Gt-1⟧:$\\{\text{\textlbrackdbl}g_{t-1}\text{\textrbrackdbl}\\}^{M}_{i=1}$,
⟦Ht-1⟧:$\\{\text{\textlbrackdbl}h_{t-1}\text{\textrbrackdbl}\\}^{M}_{i=1}$,
and $\mathcal{T}$.

4 /*Collaboratively Computed by SERVER S and SERVER C*/

5 if  _C URRENTNODE==LEAFNODE_ then

6 //Compute the weight of the leaf node

7 $\text{\textlbrackdbl}w^{*}\text{\textrbrackdbl}$ =
$\text{{Div}(}\Sigma_{i}\\{\text{\textlbrackdbl}g\text{\textrbrackdbl}\\}^{i},(\Sigma_{i}\\{\text{\textlbrackdbl}h\text{\textrbrackdbl}\\}^{i}+\text{\textlbrackdbl}\lambda\text{\textrbrackdbl}))$

8 $\\{\text{\textlbrackdbl}\hat{\text{y}}\text{\textrbrackdbl}\\}^{i}$ =
$\text{\textlbrackdbl}w^{*}\text{\textrbrackdbl}$

9 return $\text{\textlbrackdbl}\hat{\text{Y}}\text{\textrbrackdbl}$

10 end if

11 //Compute the CURRENTNODE’s gain ($cgain$)

12
$\text{\textlbrackdbl}G\text{\textrbrackdbl}=\Sigma_{i}\\{\text{\textlbrackdbl}g\text{\textrbrackdbl}\\}^{i}$

13
$\text{\textlbrackdbl}H\text{\textrbrackdbl}=\Sigma_{i}\\{\text{\textlbrackdbl}h\text{\textrbrackdbl}\\}^{i}$

14
$\text{\textlbrackdbl}cgain\text{\textrbrackdbl}=\text{{Div}(}\text{{Mult}(\textlbrackdbl}G\text{\textrbrackdbl},\text{\textlbrackdbl}G\text{\textrbrackdbl}\text{)},\text{(\textlbrackdbl}H\text{\textrbrackdbl}+\text{\textlbrackdbl}\lambda\text{\textrbrackdbl))}$

15 //Initialize the gain dictionary

16 $gainDict=\\{\\}$

17 //Enumerate all the PARTICIPANTS

18 for  _p= $0,\cdots,P$_ do

19 //Enumerate all the features of a PARTICIPANT

20 for  _j= $0,\cdots,J$_ do

21 //Enumerate all the proposed thresholds

22 for  _k= $0,\cdots,K$_ do

23 Receive $\text{\textlbrackdbl}G_{L}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}H_{L}\text{\textrbrackdbl}$ from a PARTICIPANT

24 //Compute the first derivative for the right branch

25
$\text{\textlbrackdbl}G_{R}\text{\textrbrackdbl}=\text{{Sub}(\textlbrackdbl}G\text{\textrbrackdbl},\text{\textlbrackdbl}G_{L}\text{\textrbrackdbl}\text{)}$

26 //Compute the second derivatives for the right branch

27
$\text{\textlbrackdbl}H_{R}\text{\textrbrackdbl}=\text{{Sub}(}\text{\textlbrackdbl}H\text{\textrbrackdbl},\text{\textlbrackdbl}H_{L}\text{\textrbrackdbl}\text{)}$

28 //Compute gains

29
$\text{\textlbrackdbl}lgain\text{\textrbrackdbl}=\text{{Div}(}\text{(\textlbrackdbl}G_{L}\text{\textrbrackdbl}\text{)}^{2},\text{(}\text{\textlbrackdbl}H_{L}\text{\textrbrackdbl}+\text{\textlbrackdbl}\lambda\text{\textrbrackdbl}\text{))}$

30
$\text{\textlbrackdbl}rgain\text{\textrbrackdbl}=\text{{Div}(\textlbrackdbl}G_{R}\text{\textrbrackdbl)}^{2},\text{(\textlbrackdbl}H_{R}\text{\textrbrackdbl}+\text{\textlbrackdbl}\lambda\text{\textrbrackdbl}\text{))}$

31
$\text{\textlbrackdbl}gain\text{\textrbrackdbl}=lgain+(\text{{Sub}(}rgain,cgain\text{)})$

32 //Update the gain dictionary

33 $gainDict[(p,j,k)]=\text{\textlbrackdbl}gain\text{\textrbrackdbl}$

34 end for

35

36 end for

37

38 end for

39 $\text{j}_{optimal},\text{k}_{optimal}$ =
$\underset{j,k}{\mathrm{Sargmax}}$($gainDict$)

40 return $\text{j}_{opt},\text{k}_{opt}$ to optimal participant p

41 Server C receives IL from optimal participant p

42 Server C partitions its instance space into IL and IR

43 Server C associates the CURRENTNODE with the optimal participant p as
[$\text{p}:Node^{j,k}$]

44 end

Algorithm 5 Securely Finding Node Split

###  V-C Secure Node Split Decision

From Equation 4, it can be observed that the optimal split can be obtained if
the values of $G_{L}\text{ and }H_{L}$, and $G_{R}\text{ and }H_{R}$ can be
obtained. Hence, the secure split finding algorithm SSPLITNODE shown in
Algorithm 5 takes as input the first and second encrypted derivatives
$\text{\textlbrackdbl}G_{t-1}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}H_{t-1}\text{\textrbrackdbl}$ and the parameter tuple
$\mathcal{T}$. In this context, we simply use
$\text{\textlbrackdbl}G\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}H\text{\textrbrackdbl}$ for
$\text{\textlbrackdbl}G_{t-1}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}H_{t-1}\text{\textrbrackdbl}$, respectively.

First, the algorithm returns and stores the encrypted prediction matrix if the
current node is a leaf node (shown in lines 4-9 of Algorithm 5). Otherwise,
the algorithm proceeds to securely identify the optimal score. It enumerates
all the participants, their features and the proposed encrypted split
candidates for each of the features. For each proposed split candidate, the
algorithm computes an encrypted gain (shown in lines 21-30 of Algorithm 5).
The encrypted gains for all the proposed split candidates are stored in a
dictionary. The algorithm then executes the Sargmax primitive algorithm to
identify the optimal feature $j_{opt}$ and the threshold value $k_{opt}$.
Next, server C sends the optimal parameters $j_{opt}$ and $k_{opt}$ to the
optimal participant bearing the pair $j_{opt}-k_{opt}$. Then server C receives
IL from the optimal participant and uses it to split its instance space into
IL and IR. Server C then stores the current node and associates it with the
optimal participant.

##  VI Secure Prediction

1function SPREDICT(TREELIST, $x^{i,j}_{1\times\mathcal{N}}$)

2 //Input:-TREELIST and $x^{i,j}_{1\times\mathcal{N}}$, where $\mathcal{N}$ is
the number of features for the record

3 /* Computed by all the entities */

4 //Client c encrypt the values of the record

5 $\text{Enc}(x^{i,j}_{1\times\mathcal{N}})_{pk_{c}}$

6 Send the encrypted record to the SERVER C

7 while  _True_ do

8 //Start from the ROOTNODE

9 if  _C URRENTNODE $!=$ LEAFNODE_ then

10 SERVER C identifies feature $j$ for the split at CURRENTNODE

11 SERVER C identifies the PARTICIPANT $p$ bearing the feature $j$

12 //Transform the encryption to be under the public key of the PARTICIPANT
$p$

13
$\text{Enc(}x^{i,j}+r\text{)}_{pk_{c}}\leftarrow\text{Enc(}x^{i,j}\text{)}_{pk_{c}}+\text{Enc(r)}_{pk_{c}}$

14 SERVER C send $\text{Enc(}x^{i,j}+r\text{)}_{pk_{c}}$ to SERVER S

15 SERVER S decrypts $\text{Enc(}x^{i,j}+r\text{)}_{pk_{c}}$ using mDec

16 SERVER S re-encrypts as $\text{Enc(}x^{i,j}+r\text{)}_{pk_{p}}$ and sends
to SERVER C

17 SERVER C extracts $\text{Enc(}x^{i,j}\text{)}_{pk_{p}}$ as:
$\text{Enc(}x^{i,j}\text{)}_{pk_{p}}\leftarrow\text{Enc(}x^{i,j}+r\text{)}_{pk_{p}}-\text{Enc(r)}_{pk_{p}}$

18 //Collaboration with the participant bearing the optimal feature for the
current node

19 SERVER C sends $\text{Enc(}x^{i,j}\text{)}_{pk_{p}}$ to the PARTICIPANT $p$
bearing the feature $j$

20 PARTICIPANT $p$ decrypts $\text{Enc(}x^{i,j}\text{)}_{pk_{p}}$ and compares
it with the threshold value at the node

21 Based on whether $x^{i,j}$ is greater or less than the threshold,
PARTICIPANT $p$ decides on the tree branch to follow

22 PARTICIPANT $p$ forwards the decision to SERVER C to continue with the
process at NEXTNODE

23 //Update the CURRENTNODE

24 CURRENTNODE = NEXTNODE

25 else

26 Return the encrypted weight ⟦w⟧of the LEAFNODE

27 end if

28

29 end while

30

Algorithm 6 Secure Prediction Algorithm

Our proposed secure prediction algorithm is collaboratively executed by all
the entities as shown in Algorithm 6. The SPREDICT algorithm takes as input
the trained model TREELIST and a record to be predicted
$x^{i,j}_{1\times\mathcal{N}}$ with $N$ number of features. Suppose
$x^{i,j}_{1\times\mathcal{N}}$ is held by a client c with a public key
$pk_{c}$. To make predictions on the record, the client first encrypts the
record with his public key as
$\text{Enc}(x^{i,j}_{1\times\mathcal{N}})_{pk_{c}}$ and sends it to server C.
This prevents the privacy of the record from server C. Next, server C compares
and passes the record down the tree, starting from the root node. At each
node, server C identifies the participant $p$ holding the node, and the $j,k$
pair associated with the node. Server C then transforms the record value for
the feature $j$ of the participant $p$’s to be under the public key of the
participant $p$ as $\text{Enc}(x^{i,j})_{pk_{p}}$ (shown in lines 12-17 of
Algorithm 6). Server C then sends $\text{Enc}(x^{i,j})_{pk_{p}}$ to the
participant $p$. Next, $p$ decrypts the $\text{Enc}(x^{i,j})_{pk_{p}}$ using
his secret key and compares the value with the node’s threshold in plaintext.
Depending on the comparison result, the participant decides on whether to
follow the left or the right child nodes of the current node and sends the
decision to server C. Server C repeats the process until a leaf node is
reached. Once a leaf node is reached, the algorithm returns the encrypted
weight ⟦w⟧of the leaf node stored in server C as its result. The final
prediction result is obtained by cumulating the predictions of all the trees
in TREELIST.

##  VII Analysis

###  VII-A Security Analysis

We consider the semi-honest (non-colluding) model in our security analysis,
i.e., we consider the scenario where all the entities adhere to the protocols
but try to gather information about the other entities’ input and intermediate
parameters as much as they can.

####  VII-A1 Security of BCP sub-protocols

First, we present the security analysis of all the sub-protocols used in this
work. The security of the KeyProd, Add, Mult, TransDec, Sub, Exp and Neg sub-
protocols under the semi-honest model have already been proven in [26, 25].

Div: Similar to the other sub-protocols, the security of the Div sub-protocol
is based on blinding or masking the plaintext. Given the ciphertexts
(numerator and denominator), we employ the properties of the homomorphic
encryption to blind the ciphertexts with random elements. These random
elements serve as keys. When server S decrypts the ciphertexts, without
knowing the random blinding elements, it cannot obtain any information about
the nominator and the denominator. They look random. On the other hand, since
server C does not have access to the decryption key, it also does not obtain
any information about the ciphertexts. Note that we assume the two servers do
not collude. Thus, the Div sub-protocol is secure in the semi-honest security
model.

LGT and Sargmax: The security of the LGT sub-protocol is based on the fact
that server S only computes on the difference between two data values. Thus,
server S obtains no information about the actual data, hence making the sub-
protocol secure in the semi-honest model. Therefore, our proposed Sargmax sub-
protocol which relies on the LGT is also secure in the semi-honest model.

####  VII-A2 Security of SSXGB

The security analysis of the SSXGB can be split into three parts: server S
part, server C part and participant part.

Server S part: Server S does not have access to the sample and feature space.
It only collaborates with Server C in performing computations. However, the
computations performed by server S are on masked values. Thus, no information
gets leaked to server S.

Server C part: Server C has access to the sample and feature space, and it
stores leaf nodes. It also know which participant hold which feature. However,
the intermediate values it has access to are encrypted, and it only performs
computations on the encrypted values. Although it stores the leaf nodes, the
leaf values are kept in encrypted form. Thus, no information gets leaked to
server C.

Participant part: Each participant has access to the sample space for each
split. Each participant knows the intermediate nodes it holds. However, each
participant does not know the actual values of the intermediate parameters
apart from the LBP immediately after the construction of the first tree. The
participants also do not have access to the leaf nodes. Thus, no information
leaks to the participants.

Since there is no information leakage in the involved entities, the proposed
SSXGB is secure in the semi-honest model.

###  VII-B Communication Overhead Analysis

We analyze the communication overhead in terms of analyzing the communication
costs associated with a single split. Here, we look at server C - participant
and server C - server S communication costs.

server C - participant communication cost: The server C - participant
communication cost is similar to that of [16]. Given $\zeta$ as the ciphertext
size, $n$ as the number of samples for the current node, $q$ as the number of
samples in a bucket and $d$ as the number of features held by a participant,
the communication cost can be computed as $2\times\zeta\times d\times(n/q)$.

server C - server S communication cost: During each split, the server C -
server S communication cost can be computed as
$12\times\zeta+(3\times\zeta\times(n/q)\times D)$, where $D$ is the total
number of features. Our proposed SSXGB experiences fairly heavy communication
overhead during the collaborative computation of gains by the two servers.

##  VIII Performance Evaluation

This section presents experiments to demonstrate the effectiveness and
efficiency of the proposed SSXGB.

###  VIII-A Experimental Setup

####  VIII-A1 Hardware and Software

All the experiments were performed using a desktop computer having Intel Core
i5-6500 CPU with 3.20GHz$\times$ 4 speed and 16GB RAM running Ubuntu 20.04
operating system. We used Python 3.8.5 and gmpy2 library for the
implementation. We also used Cython 0.29.23 to speed up sections of the code.
The participant and server functionalities were all executed in the same
computer. Thus, latency is ignored in the experiments.

####  VIII-A2 Datasets

We experimented using two datasets: Iris [31] and MNIST [32]. The Iris dataset
comprises three classes of iris plants, each with 50 instances. Each instance
bears the features of sepal length, sepal width, petal length and petal width.
Thus, the dataset contains 150 instances with 4 features (150$\times$4).

The MNIST dataset consists of 70,000 samples of gray-scale handwritten images
of digits (0-9). The training set contains 60,000 samples while the test set
contains 10,000 samples. Each gray-scale sample has 28$\times$28 (784) pixels.
Thus, the training set is (60,000$\times$784) and the test set is
(10,000$\times$784).

###  VIII-B Evaluation of SSXGB

(a) Accuracy with Iris (b) Accuracy with MNIST (c) Loss with Iris (d) Loss
with MNIST

Figure 3: Training convergence with the Iris and MNIST datasets

First, we evaluate the regression effectiveness of the proposed SSXGB with the
two datasets. The effectiveness is measured in terms of regression accuracy
and loss.

Setup Configuration: We simulated the two servers, and four (4) participants
for the Iris dataset and sixteen (16) participants for the MNIST dataset. In
each case, one of the participants serves as an LBP. We partitioned the
datasets vertically and shared the features between the participants, i.e.,
for the Iris dataset, each participant held one (1) feature and for the MNIST
dataset, each participant held forty-nine (49) features. Since we performed
regression analysis, we considered only two classes. Thus, we take ”Iris-
setosa” as positive for the Iris dataset and the rest of the classes as
negative. To make the dataset balanced, we synthetically generated 50 more
instances of the ”Iris-setosa” class. Meanwhile, for the MNIST dataset, we
take the digits 0-4 as positive and 5-9 as negative. During each simulation,
we set the learning rate as 0.08, and the sampling rate as 0.8 for both
samples and features. We set maximum depths as 6 and 4 for the MNIST and Iris
datasets experiments, respectively. We employed the approximated sigmoid
function in [33].

Results: Figure 3 presents the accuracy and loss against the training round
with the Iris and MNIST datasets. We can observe that the proposed SSXGB
converges slowly in comparison with the XGBoost scheme, and it is slightly
less effective as compared to the XGBoost, i.e., the accuracy of 0.9789 vs
0.9826 for the MNIST dataset and 0.97712 vs 0.97778 for the Iris dataset. The
accuracy loss in SSXGB can be attributed to the use of the approximated
sigmoid function and the restrictive nature of training the first tree.
However, the slight loss in accuracy is totally acceptable.

###  VIII-C Privacy-Preservation Computation Overhead

Table I: Computation Times of BCP Algorithms and Sub-protocols Operation | Key Size (bits)
---|---
| 512 | 1024 | 2048
Enc | 10.61 ms | 12.02 ms | 16.98 ms
Dec | 18.27 ms | 29.13 ms | 38.64 ms
mDec | 29.34 ms | 40.96 ms | 63.72 ms
KeyProd | 0.02 ms | 0.05 ms | 0.11 ms
Add | 8.86 ms | 10.23 ms | 12.61 ms
Mult | 180.74 ms | 259.97 ms | 310.03 ms
TransDec | 161.20 ms | 196.69 ms | 283.74 ms
Exp | 2.04 ms | 2.32 ms | 4.01 ms
Sub | 8.93 ms | 12.06 ms | 13.02 ms
LGT | 120.17 ms | 143.72 ms | 171.05 ms
Div | 140.29 ms | 183.18 ms | 251.67 ms

Since HE is crucial for privacy preservation in our proposed SSXGB,
identifying a suitable configuration for the BCP scheme was paramount. Thus,
we implemented the BCP scheme and measured the computation times of its
algorithms and sub-protocols under different key sizes. For each operation,
the experiment was repeated 20 times and we obtained the average computation
times.

Results: The results are shown in Table I. We can see that the computation
times increase with the increase in key size for all the algorithms and sub-
protocols. Amongst the BCP algorithms, the mDec is computationally the most
demanding while encryption is computationally the least demanding. Meanwhile,
amongst the sub-protocols, the Mult is computationally the most demanding
while KeyProd is compuatationally the least demanding. For the KeyProd, we
only considered a joint public key from two users and the joint public key
generation does not involve encryption of data as in [26]. Also, for the
TransDec, we considered only two users. Based on the shown computation times
and security requirements, we considered the key size of 1024 during the
implementation of the SSXGB.

###  VIII-D Efficiency of SSXGB

Finally, we investigate the efficiency of the proposed SSXGB by examining its
running time. We performed the investigation under a varying number of
participants. We considered the running time for training using the two
datasets. Figure 4 shows the running time of training using the MNIST and Iris
datasets against the varying number of participants. Since we intended to
examine the running time comparatively for the datasets and the Iris dataset
has only 4 features, we limited the number of participants to only 4. And, in
Figure 4, it can be observed that there is no significant change in running
time against the varying number of participants. We can attribute this to the
number of features and samples remaining almost the same under the vertically
partitioned datasets, hence the number of feature and sample operations remain
fairly constant. However, the running time is higher for the MNIST dataset
compared to the Iris dataset. This is mainly because the MNIST dataset has
more features and samples as compared to the Iris dataset.

Figure 4: Running time of the SSXGB with the Iris and MNIST datasets

##  IX Conclusion

In this work, we proposed SSXGB framework for scalable and privacy-preserving
multi-party gradient tree boosting over vertically partitioned datasets with
outsourced computations. We adopted BCP HE for secure computations and
proposed sub-protocols based on the BCP HE for two non-linear operations of
gradient tree boosting. Analysis of the framework shows that no information
gets leaked to any entities under the semi-honest security model. We also
implemented the secure training algorithm of the SSXGB framework. We performed
experiments using two real-world datasets. The results show that the SSXGB is
scalable and reasonably effective. In the future, we shall aim to minimize the
communication overhead of the proposed framework.

## References

  * [1] M. Gong, J. Feng, and Y. Xie, “Privacy-enhanced multi-party deep learning,” _Neural Networks_ , vol. 121, pp. 484–496, 2020.
  * [2] M. d. Cock, R. Dowsley, A. C. Nascimento, and S. C. Newman, “Fast, privacy preserving linear regression over distributed datasets based on pre-distributed data,” in _Proceedings of the 8th ACM Workshop on Artificial Intelligence and Security_ , 2015, pp. 3–14.
  * [3] R. Hall, S. E. Fienberg, and Y. Nardi, “Secure multiple linear regression based on homomorphic encryption,” _Journal of Official Statistics_ , vol. 27, no. 4, p. 669, 2011.
  * [4] M. Kim, Y. Song, S. Wang, Y. Xia, and X. Jiang, “Secure logistic regression based on homomorphic encryption: Design and evaluation,” _JMIR medical informatics_ , vol. 6, no. 2, p. e19, 2018.
  * [5] Y. Aono, T. Hayashi, L. T. Phong, and L. Wang, “Privacy-preserving logistic regression with distributed data sources via homomorphic encryption,” _IEICE TRANSACTIONS on Information and Systems_ , vol. 99, no. 8, pp. 2079–2089, 2016.
  * [6] L. Zheng, C. Chen, Y. Liu, B. Wu, X. Wu, L. Wang, L. Wang, J. Zhou, and S. Yang, “Industrial scale privacy preserving deep neural network,” _arXiv preprint arXiv:2003.05198_ , 2020.
  * [7] T. T. Phuong _et al._ , “Privacy-preserving deep learning via weight transmission,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 11, pp. 3003–3015, 2019.
  * [8] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, pp. 1–19, 2019.
  * [9] J. H. Friedman, “Greedy function approximation: a gradient boosting machine,” _Annals of statistics_ , pp. 1189–1232, 2001.
  * [10] E.-A. Minastireanu and G. Mesnita, “Light gbm machine learning algorithm to online click fraud detection,” _J. Inform. Assur. Cybersecur_ , vol. 2019, 2019.
  * [11] R. Punmiya and S. Choe, “Energy theft detection using gradient boosting theft detector with feature engineering-based preprocessing,” _IEEE Transactions on Smart Grid_ , vol. 10, no. 2, pp. 2326–2329, 2019.
  * [12] Y. Wang, D. Feng, D. Li, X. Chen, Y. Zhao, and X. Niu, “A mobile recommendation system based on logistic regression and gradient boosting decision trees,” in _2016 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2016, pp. 1896–1902.
  * [13] Q. Li, Z. Wen, and B. He, “Practical federated gradient boosting decision trees,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 04, 2020, pp. 4642–4649.
  * [14] Y. J. Ong, Y. Zhou, N. Baracaldo, and H. Ludwig, “Adaptive histogram-based gradient boosted trees for federated learning,” _arXiv preprint arXiv:2012.06670_ , 2020.
  * [15] Y. Liu, Z. Ma, X. Liu, S. Ma, S. Nepal, and R. Deng, “Boosting privately: Privacy-preserving federated extreme boosting for mobile crowdsensing,” _arXiv preprint arXiv:1907.10218_ , 2019.
  * [16] K. Cheng, T. Fan, Y. Jin, Y. Liu, T. Chen, and Q. Yang, “Secureboost: A lossless federated learning framework,” _arXiv preprint arXiv:1901.08755_ , 2019.
  * [17] Z. Feng, H. Xiong, C. Song, S. Yang, B. Zhao, L. Wang, Z. Chen, S. Yang, L. Liu, and J. Huan, “Securegbm: Secure multi-party gradient boosting,” in _2019 IEEE International Conference on Big Data (Big Data)_. IEEE, 2019, pp. 1312–1321.
  * [18] W. Fang, C. Chen, J. Tan, C. Yu, Y. Lu, L. Wang, L. Wang, J. Zhou _et al._ , “A hybrid-domain framework for secure gradient tree boosting,” _arXiv preprint arXiv:2005.08479_ , 2020.
  * [19] T. Chen and C. Guestrin, “Xgboost: A scalable tree boosting system,” in _Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining_ , 2016, pp. 785–794.
  * [20] Y. Aono, T. Hayashi, L. Wang, S. Moriai _et al._ , “Privacy-preserving deep learning via additively homomorphic encryption,” _IEEE Transactions on Information Forensics and Security_ , vol. 13, no. 5, pp. 1333–1345, 2017.
  * [21] R. Shokri and V. Shmatikov, “Privacy-preserving deep learning,” in _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , 2015, pp. 1310–1321.
  * [22] C. Leung, “Towards privacy-preserving collaborative gradient boosted decision tree learning,” 2020.
  * [23] M. Yang, L. Song, J. Xu, C. Li, and G. Tan, “The tradeoff between privacy and accuracy in anomaly detection using federated xgboost,” _arXiv preprint arXiv:1907.07157_ , 2019.
  * [24] Z. Wang, Y. Yang, Y. Liu, X. Liu, B. B. Gupta, and J. Ma, “Cloud-based federated boosting for mobile crowdsensing,” _arXiv preprint arXiv:2005.05304_ , 2020.
  * [25] E. Bresson, D. Catalano, and D. Pointcheval, “A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications,” in _International Conference on the Theory and Application of Cryptology and Information Security_. Springer, 2003, pp. 37–54.
  * [26] A. Peter, E. Tews, and S. Katzenbeisser, “Efficiently outsourcing multiparty computation under multiple keys,” _IEEE transactions on information forensics and security_ , vol. 8, no. 12, pp. 2046–2058, 2013.
  * [27] X. Liu, R. H. Deng, K. R. Choo, and J. Weng, “An efficient privacy-preserving outsourced calculation toolkit with multiple keys,” _IEEE Transactions on Information Forensics and Security_ , vol. 11, no. 11, pp. 2401–2414, 2016.
  * [28] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial Intelligence and Statistics_. PMLR, 2017, pp. 1273–1282.
  * [29] S. Truex, N. Baracaldo, A. Anwar, T. Steinke, H. Ludwig, R. Zhang, and Y. Zhou, “A hybrid approach to privacy-preserving federated learning,” in _Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security_ , 2019, pp. 1–11.
  * [30] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in _proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1175–1191.
  * [31] R. A. Fisher, “Iris data set,” 1936. [Online]. Available: https://archive.ics.uci.edu/ml/datasets/iris
  * [32] Y. LeCun, C. Cortes, and C. Burges, “Mnist handwritten digit database,” _ATT Labs_ , vol. 2, 2010. [Online]. Available: http://yann.lecun.com/exdb/mnist
  * [33] T. Chen and S. Zhong, “Privacy-preserving backpropagation neural network learning,” _IEEE Transactions on Neural Networks_ , vol. 20, no. 10, pp. 1554–1564, 2009.

##  Appendix A Details of the LGT Sub-protocol

Figure 5: The LGT sub-protocol

The LGT sub-protocol is an adaptation of the SLT sub-protocol in [27]. The
only difference is that we intentionally reveal the result of the comparison
to the server C. An illustration of the sub-protocol is shown in Figure 5.
Given two ciphertexts ⟦m${}_{1}\text{\textrbrackdbl}$ and
⟦m${}_{2}\text{\textrbrackdbl}$ encrypted under the joint public key
$pk_{\Sigma}$. To determine if ⟦m1⟧$\geq$⟦m${}_{2}\text{\textrbrackdbl}$ or
⟦m1⟧$<$⟦m2⟧, the following procedures are collaboratively performed by servers
C and S.

As in [27], first server C uses the Exp sub-protocol to multiply the
ciphertexts by two as ⟦2m${}_{1}\text{\textrbrackdbl}$ and ⟦2m2⟧. Server C
also encrypts 1 using the Enc algorithm as ⟦1⟧, and adds the result to
⟦2m${}_{1}\text{\textrbrackdbl}$ as ⟦2m1 \+ 1⟧.

Server C then flips a coin $s$. If $s=1$, server C uses the Sub sub-protocol
and computes ⟦$l\text{\textrbrackdbl}$ as (⟦2m1 \+ 1⟧- ⟦2m2⟧). Otherwise,
⟦$l\text{\textrbrackdbl}$ is computed as (⟦2m2⟧- ⟦2m1+1⟧). Server C then sends
⟦$l\text{\textrbrackdbl}$ to server S.

Server S uses the mDec algorithm to decrypt ⟦$l\text{\textrbrackdbl}$ as $l$.
Server S then computes $\mathcal{L}(l)$222$\mathcal{L}(x)$ denotes the bit
length of $x$. See [27] for the details. If $\mathcal{L}(l)>\mathcal{N}/2$,
server S sets $u^{\prime}=1$, otherwise $u^{\prime}=0$. Server S then returns
$u^{\prime}$ to server C.

Next, server C checks for $s$, and if $s=1$, server C sets $u^{*}=u^{\prime}$.
Otherwise, $u^{*}=1-u^{\prime}$. If $u^{*}=0$, m${}_{1}\geq$m2, otherwise
m${}_{1}<$m2.

##  Appendix B Proof of correctness for the Div subprotocol

Consider the division of $\text{\textlbrackdbl}m_{1}\text{\textrbrackdbl}$ by
$\text{\textlbrackdbl}m_{2}\text{\textrbrackdbl}$
($\text{\textlbrackdbl}m_{1}\div m_{2}\text{\textrbrackdbl}$) using the Div
subprotocol. For the purpose of this proof, we assume
$\text{\textlbrackdbl}m_{1}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}m_{2}\text{\textrbrackdbl}$ are encrypted under the same
public key. First, the server C, randomly selects
$\tau_{{}_{1}},\tau_{{}_{2}}\in\mathbb{Z}_{N}$. Using the Exp subprotocol, the
server C generates
$\text{\textlbrackdbl}\tau_{{}_{1}}m_{1}\text{\textrbrackdbl}$,
$\text{\textlbrackdbl}\tau_{{}_{2}}m_{2}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}\tau_{{}_{1}}m_{2}\text{\textrbrackdbl}$ as follows:

$\begin{split}\text{\textlbrackdbl}\tau_{{}_{1}}m_{1}\text{\textrbrackdbl}&=\big{(}g^{\tau_{{}_{1}}.r_{{}_{1}}}\text{mod
}N^{2},h^{\tau_{{}_{1}}.r_{{}_{1}}}(1+\tau_{{}_{1}}.m_{1}.N)\text{mod
}N^{2}\big{)}\\\
\text{\textlbrackdbl}\tau_{{}_{2}}m_{2}\text{\textrbrackdbl}&=\big{(}g^{\tau_{{}_{2}}.r_{{}_{2}}}\text{mod
}N^{2},h^{\tau_{{}_{2}}.r_{{}_{2}}}(1+\tau_{{}_{2}}.m_{2}.N)\text{mod
}N^{2}\big{)}\\\
\text{\textlbrackdbl}\tau_{{}_{1}}m_{2}\text{\textrbrackdbl}&=\big{(}g^{\tau_{{}_{1}}.r_{{}_{3}}}\text{mod
}N^{2},h^{\tau_{{}_{1}}.r_{{}_{3}}}(1+\tau_{{}_{1}}.m_{2}.N)\text{mod
}N^{2}\big{)}\end{split}$ (9)

Using the Add subprotocol, the server C computes
$\text{\textlbrackdbl}\tau_{{}_{1}}m_{1}+\tau_{{}_{2}}m_{2}\text{\textrbrackdbl}$
as:

$\begin{split}\text{\textlbrackdbl}\tau_{{}_{1}}m_{1}+\tau_{{}_{2}}m_{2}\text{\textrbrackdbl}&=\big{(}g^{(\tau_{{}_{1}}r_{{}_{1}}+\tau_{{}_{2}}r_{{}_{2}})}\text{mod
}N^{2},\\\
&h^{(\tau_{{}_{1}}r_{{}_{1}}+\tau_{{}_{2}}r_{{}_{2}})}(1+(\tau_{{}_{1}}m_{1}+\tau_{{}_{2}}m_{2})N)\text{mod
}N^{2}\big{)}\end{split}$ (10)

The server C then sends
$\text{\textlbrackdbl}\tau_{{}_{1}}m_{2}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}\tau_{{}_{1}}m_{1}+\tau_{{}_{2}}m_{2}\text{\textrbrackdbl}$
to the server S. Using the mDec algorithm, the server S decrypts
$\text{\textlbrackdbl}\tau_{{}_{1}}m_{2}\text{\textrbrackdbl}$ and
$\text{\textlbrackdbl}\tau_{{}_{1}}m_{1}+\tau_{{}_{2}}m_{2}\text{\textrbrackdbl}$
as $\tau_{{}_{1}}m_{2}$ and $\tau_{{}_{1}}m_{1}+\tau_{{}_{2}}m_{2}$,
respectively. In plaintext, the server S then computes
($\frac{m_{1}}{m_{2}}+\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}$) as:

$(\frac{m_{1}}{m_{2}}+\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}})=\frac{1}{\tau_{{}_{1}}m_{2}}(\tau_{{}_{1}}m_{1}+\tau_{{}_{2}}m_{2})$
(11)

Next, the server S encrypts
$(\frac{m_{1}}{m_{2}}+\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}})$ to
$\text{\textlbrackdbl}\frac{m_{1}}{m_{2}}+\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}\text{\textrbrackdbl}$
as:

$\text{\textlbrackdbl}\frac{m_{1}}{m_{2}}+\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}\text{\textrbrackdbl}=\big{(}g^{r}\text{mod
}N^{2},h^{r}(1+(\frac{m_{1}}{m_{2}}+\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}).N)\text{mod
}N^{2}\big{)}$ (12)

and sends the result to server C.

After receiving
$\text{\textlbrackdbl}\frac{m_{1}}{m_{2}}+\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}\text{\textrbrackdbl}$,
the server C computes $\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}$ in plaintext and
encrypts it as
$\text{\textlbrackdbl}\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}\text{\textrbrackdbl}$.
The server C extracts
$\text{\textlbrackdbl}\frac{m_{1}}{m_{2}}\text{\textrbrackdbl}$ using the Sub
subprotocol as:

$\text{\textlbrackdbl}\frac{m_{1}}{m_{2}}\text{\textrbrackdbl}=\text{{Sub}}(\text{\textlbrackdbl}\frac{m_{1}}{m_{2}}+\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}\text{\textrbrackdbl},\text{\textlbrackdbl}\frac{\tau_{{}_{2}}}{\tau_{{}_{1}}}\text{\textrbrackdbl}).$
(13)