Optimizing Secure Decision Tree Inference Outsourcing

Fig. 1 illustrates a decision tree. As shown, each internal node (called decision node $\mathcal{D}_{j}$) is associated with a threshold $y_{j}$, while each leaf node $\mathcal{L}_{z}$ is associated with a prediction value $u_{z}$ indicating the possible inference result. Hence, given a decision tree with $J$ decision nodes and $Z$ leaf nodes, a threshold vector $\mathbf{y}=\{y_{0},\cdots,y_{J-1}\}$ and a prediction value vector $\mathbf{u}=\{u_{0},\cdots,u_{Z-1}\}$ are derived. The input for decision tree inference is an $I$-dimensional feature vector, denoted by $\textbf{x}=\{x_{0},\cdots,x_{I-1}\}$. There is an associated input selection mapping $\sigma:j\in\{0,1,\cdots,J-1\}\rightarrow i\in\{0,1,\cdots,I-1\}$. Decision tree inference with $\mathbf{x}$ as input works as follows. Firstly, the mapping $\sigma$ is used to select a feature $x_{i}$ from $\mathbf{x}$ for each $\mathcal{D}_{j}$. Secondly, starting from the root node, the Boolean function $f(x_{\sigma(j)})=(x_{\sigma(j)}<y_{j})$ is evaluated at each $\mathcal{D}_{j}$. The evaluation result $v_{j}$ decides whether to next take the left ($v_{j}=0$) or right ($v_{j}=1$) branch. Such evaluation terminates when a leaf node is reached. The depth $d$ is the length of the longest path between the root node and a leaf node. Table I provides a summary of the key notations. Without loss of generality and as the tree structure should be hidden, we will consider complete binary decision trees in our security design, which is also consistent with previous works [15, 16, 17, 18, 12]. It is noted that dummy nodes can be simply added to make non-complete decision trees complete [15].

Given a value $\alpha\in\mathbb{Z}_{2^{l}}$, its $2$-of-$2$ additive secret sharing is a pair $([\alpha]_{0}=\alpha-r$, $[\alpha]_{1}=r)$, where $r$ is a random value in $\mathbb{Z}_{2^{l}}$ and the subtraction is done in $\mathbb{Z}_{2^{l}}$ (i.e., result is modulo $2^{l}$). Given either $[\alpha]_{0}$ or $[\alpha]_{1}$, the value $\alpha$ is perfectly hidden. Suppose that two values $\alpha$ and $\beta$ are secret-shared among two parties $\mathcal{P}_{0}$ and $\mathcal{P}_{1}$, i.e., $\mathcal{P}_{0}$ holds $[\alpha]_{0}$ and $[\beta]_{0}$ while $\mathcal{P}_{1}$ holds $[\alpha]_{1}$ and $[\beta]_{1}$. The secret sharing $[\alpha+\beta]$ (resp. $[\alpha-\beta]$) of $\alpha+\beta$ (resp. $\alpha-\beta$) can be computed locally where each party $\mathcal{P}_{i}$ ($i\in\{0,1\}$) directly computes $[\alpha+\beta]_{i}=[\alpha]_{i}+[\beta]_{i}$ (resp. $[\alpha-\beta]_{i}=[\alpha]_{i}-[\beta]_{i}$). Multiplication by a constant $\gamma$ on the value $\alpha$ can also be done locally, i.e., $[\alpha\cdot\gamma]_{i}=\gamma\cdot[\alpha]_{i}$. Multiplication over two secret sharings $[\alpha]$ and $[\beta]$ can be supported by using the Beaver’s multiplication triple [19, 20]. That is, given the secret sharing of a multiplication triple $(t_{1},t_{2},t_{3})$ where $t_{3}=t_{1}\cdot t_{2}$, $[\alpha\cdot\beta]$ can be obtained with one round of interaction between the two parties. In particular, each party $\mathcal{P}_{i}$ first computes $[e]_{i}=[\alpha]_{i}-[t_{1}]_{i}$ and $[f]_{i}=[\beta]_{i}-[t_{2}]_{i}$. Then, $\mathcal{P}_{i}$ broadcasts $[e]_{i}$ and $[f]_{i}$, and recovers $e$ and $f$. Given this, each party $P_{i}$ computes $[\alpha\cdot\beta]_{i}=i\cdot e\times f+[t_{1}]_{i}\times f+[t_{2}]_{i}\times e+[t_{3}]_{i}$.

Fig. 2 shows our system architecture, comprised of the provider, the client, and two cloud servers hosted by independent and geographically separated cloud services. Such architecture follows the state-of-the-art prior work [12]. The provider (e.g., a medical institution) owns a decision tree model and provides inference services to the client with the power of cloud computing, i.e., outsourcing the inference service to the cloud. Due to concerns on the proprietary decision tree, the provider would only provide an encrypted version. The client (e.g., a patient) holds a feature vector which may encode private information such as weight, height, heart rate, and blood pressure, and wants to use the intelligent inference service to obtain a prediction about, e.g., her health. As the feature vector is privacy-sensitive, the client is only willing to provide a ciphertext.

The power of the cloud is considered to be supplied by the two cloud servers $\mathcal{C}_{0}$ and $\mathcal{C}_{1}$, which jointly provide the secure decision tree inference service. Such a two-server model not only appeared in the prior work [12] on secure outsourced decision tree inference, but has also been recently used to facilitate security designs in different applications [21, 22, 23, 13, 24], with tailored use according to problem specifics. The prominent advantage of such a two-server model is that it allows the provider and the client to go offline after supplying the encrypted inputs, and the secure inference computation is can be fully run at the cloud. Besides, it is compatible with the working paradigm of additive secret sharing, which is applied for the encryption of the decision tree and feature vector. Each cloud server receives shares of the decision tree and feature vector. They jointly do the processing and produce secret-shared inference result which can be retrieved by the client on demand to reconstruct the inference result.

It is noted that as the two cloud servers are assumed from different trust domains, a practical consideration on realistic deployment is that the two cloud servers be situated in different geographic regions and communicate over a WAN, which is a more reasonable setting compared to local networks. In this case, the latency due to interactions between the cloud servers should be taken into account as an important factor in the secure system design.

Following prior work on secure outsourced decision tree inference as well as most of existing works on privacy-preserving machine learning [12, 23, 22], we consider a semi-honest adversary setting in our system. A semi-honest adversary would honestly follow our protocol, yet attempts to infer private information beyond its access rights. In our system, it is considered that each entity (cloud server, client, provider) might be corrupted by such adversary. For the cloud server entity, we follow previous works under the two-server model ([22, 12, 13, 23, 24, 21]) and assume they are non-colluding. Namely, the two cloud servers are not corrupted by an adversary at the same time.

Consistent with [12], we consider that the values in the client’s feature vector $\mathbf{x}$ as well as the inference result (i.e., the prediction value $u^{*}$ corresponding to $\mathbf{x}$) should be kept private for the client. For the provider, there is a need to keep private the proprietary parameters/information of the decision tree model, including each decision node’s threshold $y$, the mapping $\sigma$ for feature selection, and the prediction value of each leaf node (except the inference result revealed to the client per inference). It is also required that the client learns no additional private information about the decision tree other than the prediction value corresponding to her feature vector. Following prior work [15, 12], we assume some generic meta-parameters as public, including the depth $d$, the dimension $I$, and the number $l$ of bits for value representation. We deem dealing with adversarial machine learning attacks out of the scope.

Our system is aimed at secure outsourcing of decision tree inference with high efficiency. Treating local efficiency as the first priority in our design philosophy, we first aim to shift as much processing as possible to the cloud, reducing the local performance complexities (particularly with respect to the provider in our system). On top of such consideration, we further aim to achieve high efficiency at the cloud through optimizing the processing. Our deign mainly relies on the delicate use of the lightweight additive secret sharing technique, rather than uses resource-intensive garbled circuits and homomorphic encryption.

At a high level, our design is comprised of four phases: secure input preparation, secure feature selection, secure decision node evaluation, and secure inference generation. The secure input preparation phase requires the provider (resp. the client) to encrypt the decision tree (resp. feature vector), and send the ciphertexts to the cloud servers. The secure feature selection phase is to securely select for each decision node a certain feature from the feature vector, in such a way that the cloud servers are oblivious to the mapping between decision nodes and features. The secure decision node evaluation phase securely evaluates the Boolean function at each decision node and output the ciphertext of the evaluation result. The secure inference generation phase is to leverage the ciphertexts of the evaluation results at decision nodes to generate the ciphertext of the ultimate decision tree inference result, which can then be retrieved by the client for recovery. Note that following the previous work [12], we assume that the data-independent multiplication triples are pre-generated and made available to the two cloud servers for use in our design, which can be efficiently achieved via a semi-honest third party [25, 12]. Our focus is on the latency-sensitive online inference procedure.

The client encrypts her feature vector $\mathbf{x}$ via additive secret sharing applied in an element-wise manner. In particular, the client generates two secret shares: $[\mathbf{x}]_{0}=\mathbf{x}-\mathbf{r}$ and $[\mathbf{x}]_{1}=\mathbf{r}$. For the provider, he encrypts the decision tree as follows. Firstly, the vector $\mathbf{y}$ of thresholds at decision nodes and the vector $\mathbf{u}$ of prediction values at leaf nodes are encrypted through additive secret sharing, with the secret shares $[\mathbf{y}]_{0}$, $[\mathbf{y}]_{1}$, $[\mathbf{u}]_{0}$, and $[\mathbf{u}]_{1}$ produced. Then, we need to consider how to properly encrypt the mapping $\sigma$ which is used for feature selection.

We note that the prior work [12] constructs a binary matrix of size $J\times I$ in such a manner that the $j$-th row vector is a binary vector with $I$ elements where all are $0$ except for the one at position $\sigma(j)$ being set to $1$. In this way, feature selection is then realized via matrix-vector multiplication between the binary matrix and the feature vector, which can be securely supported under additive secret sharing. Unfortunately, such an approach imposes on the provider multiplicative $O(J\cdot I)$ performance complexity which depends on the number $J$ of decision nodes as well as the dimension $I$ of the feature vector.

Differently, in order to minimize the costs of the provider, our new insight is to instead construct an index vector $\mathcal{I}$ which is comprised of the selection index values for decision nodes and thus the complexity only depends on the number $J$ of decision nodes, i.e., $O(J)$. The selection index value for a decision node $\mathcal{D}_{j}$ is represented as $\mathcal{I}_{j}\in[0,I-1]$. The secure usage of this index vector will be described shortly in the phase of secure feature selection. The provider also encrypts this index vector via additive secret sharing and produces $[\mathcal{I}]_{0}$ and $[\mathcal{I}]_{1}$. After the above processing, the provider sends the shares $[\mathbf{y}]_{m}$, $[\mathbf{u}]_{m}$, and $[\mathcal{I}]_{m}$ to each cloud server $\mathcal{C}_{m}$ ($m\in\{0,1\}$).

Upon receiving the shares of the client’s feature vector and the provider’s decision tree, the cloud servers first perform secure feature selection which produces the secret sharing of a certain feature for each decision node, based on the encrypted index vector $\mathcal{I}$. Note that hereafter all arithmetic operations are conducted by default in the ring $\mathbb{Z}_{2^{l}}$, unless otherwise stated.

We now describe how secure feature selection is achieved in our design. For each decision node $\mathcal{D}_{j}$, the processing of secure feature selection would require as input the shares of the client’ feature vector $\mathbf{x}$ and the shares of the corresponding index value $\mathcal{I}_{j}$ in the index vector $\mathcal{I}$. The output is the secret sharing of the selected feature $x_{\mathcal{I}_{j}}$ for the decision node $\mathcal{D}_{j}$.

To accomplish this functionality for our secure outsourced decision tree services, we make an observation that this indeed can be treated as oblivious array-entry read, where the encrypted feature vector could be treated as an encrypted array, and the encrypted index value is used to obliviously select an entry from the array. We leverage this observation and identify that an approach from a very recent work [26] is suited for our scenario. Using this approach as a basis, we devise the scheme for secure feature selection, which is given in Fig. 3.

The intuition is as follows. For ease of notation, we let $\mathbf{p}_{0}$ (resp. $\mathbf{p}_{1}$) denote the share of the feature vector $[\mathbf{x}]_{0}$ (resp. $[\mathbf{x}]_{1}$) at the cloud server $\mathcal{C}_{0}$ (resp. $\mathcal{C}_{1}$). Each cloud server $\mathcal{C}_{m}$ ($m\in\{0,1\}$) first creates a new array $\mathbf{p}^{\prime}_{m}$ which is derived from $\mathbf{p}_{m}$ by shifting its indices and entries under fixed random values (per feature selection). Then, given the secret sharing of a target index value $\mathcal{I}_{j}$, $\mathcal{C}_{0}$ engages in an interaction with $\mathcal{C}_{1}$ so as to receive the entry located at the shifted index $((\mathcal{I}_{j}+s_{1})\bmod 2^{l})\bmod I$ in $\mathbf{p}^{\prime}_{1}$ which corresponds to $\mathcal{I}_{j}$. Since the random value $s_{1}$ in the shifted index is only known to $\mathcal{C}_{1}$ and the corresponding entry is masked by a random value $r_{1}$, $\mathcal{C}_{0}$ is oblivious to the original index $\mathcal{I}_{j}$ as well as the share $\mathbf{p}_{1}[\mathcal{I}_{j}]$ held by $\mathcal{C}_{1}$. Similarly, $\mathcal{C}_{1}$ obtains the entry located at the shifted index in $\mathbf{p}^{\prime}_{0}$ which corresponds to $\mathcal{I}_{j}$, while learning no information about the plain index $\mathcal{I}_{j}$ and the share of the corresponding entry value held by $\mathcal{C}_{0}$. Next, the two cloud servers engage in an interaction which essentially performs secret re-sharing so as to obtain the secret sharing of the selected feature $x_{\mathcal{I}_{j}}$.

With the secret sharings of the threshold $y_{j}$ and selected feature $x_{\mathcal{I}_{j}}$ at each decision node $\mathcal{D}_{j}$, the cloud servers now perform secure decision node evaluation. As this basically requires secure comparison of secret-shared values, the prior work [12] transforms the problem of secure decision node evaluation to a simplified bit extraction problem in the secret sharing domain. The key idea is to securely extract the most significant bit (MSB) of the subtraction result $\Delta=y_{j}-x_{\mathcal{I}_{j}}$ as the evaluation result at decision node $\mathcal{D}_{j}$.

Despite the effectiveness, their solution is limited in that it poses linear $O(l)$ round complexity. This would lead to high performance overhead in the realistic scenario where the two cloud servers are situated in different geographic regions and connected over WAN, which is a more reasonable setting than local networks given that the two cloud servers are assumed to be non-colluding [13]. The basic idea in [12] is to implement a $l$-bit full adder logic in the secret sharing domain. Specifically, the shares of the difference value $\Delta$ at the two cloud servers are represented in bitwise form respectively. Then, a $l$-bit full adder logic is applied to add in the secret sharing domain the two binary inputs in a bitwise manner, where carry bits are calculated and propagated, and finally produce the MSB of the difference value $\Delta$. We note that the work [12] uses a classical and standard adder logic called ripple carry adder, as shown in Fig. 4.

In the ripple carry adder, for each full adder, the two bits that are to be added are available instantly. However, each full adder has to wait for the carry input to arrive from its previous adder. This means that the carry input for the full adder producing the MSB should wait after the carry has rippled through all previous full adders. Note that computing the carry output of each full adder in the secret sharing domain requires interactions between the two cloud servers, thus leading to $O(l)$ round complexity.

Our design follows [12] in terms of the same strategy of secure MSB bit extraction for secure decision node evaluation, yet aims to reduce the round complexity. Through the design introduced below, we manage to reduce the round complexity from linear to logarithmic. Our observation is that the use of the more advanced carry look-ahead adder can solve the carry delay problem presented in the ripple carry adder [14]. At a high level, a carry look-ahead adder is able to calculate the carry in advance based on only the input bits. It works as follows. Firstly, two terms are defined for the carry look-ahead adder: the carry generate signal $G_{i}$ and the carry propagate signal $P_{i}$, where $G_{i}=a_{i}\cdot b_{i}$ and $P_{i}=a_{i}+b_{i}$. Note that these two terms are only based on the input bits and can be computed instantly given the input bits. Then, the original carry calculation $c_{i+1}=a_{i}\cdot b_{i}+(a_{i}+b_{i})\cdot c_{i}$ as in the ripple carry adder can then be re-formulated as $c_{i+1}=G_{i}+P_{i}\cdot c_{i}$. Such re-formulation allows a carry to be computed without waiting for the carry to ripple through all previous stages, as demonstrated by the following example (a $4$-bit carry look-ahead adder):

1. 1.

   $c_{1}=G_{0}+P_{0}\cdot c_{0}=G_{0}$;

2. 2.

   $c_{2}=G_{1}+P_{1}\cdot c_{1}=G_{1}+P_{1}\cdot G_{0}$;

3. 3.

   $c_{3}=G_{2}+P_{2}\cdot c_{2}=G_{2}+P_{2}\cdot(G_{1}+P_{1}\cdot G_{0})$;

4. 4.

   $c_{4}=G_{3}+P_{3}\cdot c_{3}=G_{3}+P_{3}\cdot(G_{2}+P_{2}\cdot(G_{1}+P_{1}\cdot G_{0}))$.

It can be seen that each carry can be computed without waiting for the calculation of all previous carries.

With the application of the carry look-ahead adder for MSB computation for secure decision node evaluation, we only need to focus on the calculation of the carry $c_{l-1}$ (e.g., $c_{3}$ in the above example for $4$-bit inputs). That is, after computing $c_{l-1}$, the MSB can be derived via $MSB=a_{l-1}+b_{l-1}+c_{l-1}$ . Note that $c_{l-1}=G_{l-2}+P_{l-2}\cdot G_{l-3}+\cdots+P_{l-2}\cdots P_{1}\cdot G_{0}$. We now need to consider how to properly organize the computation of the carry $c_{l-1}$ so that we could effectively achieve $O(\log_{2}l)$ round complexity. Our observation is that such a computation can be supported by forming a binary tree over the carry generate terms, carry propagate terms, and a binary operator $\diamond$ (illustrated in Fig. 5(a)) defined as: $(G^{*},P^{*})=(G^{\prime\prime},P^{\prime\prime})\diamond(G^{\prime},P^{\prime})$, where $G^{*}=G^{\prime\prime}+G^{\prime}\cdot P^{\prime\prime}$ and $P^{*}=P^{\prime\prime}\cdot P^{\prime}$. For demonstration of this idea, we show in Fig. 5(b) an example on how the carry bit essential for MSB computation can be computed in a recursive manner based on a tree structure, in the case of $8$-bit inputs. As shown, a pair of the carry generate and propagate terms is put as a leaf node of the tree. Then, the processing is done upwards attributing to each internal node the value corresponding to the application of the operator $\diamond$ between its two children. Such processing leads to $\lceil{\log_{2}l}\rceil$ rounds in computing the essential carry $c_{l-1}$.

For simplicity of illustration, we show here the details for the case of $4$-bit inputs to concretely demonstrate the computation. In the first round, the following terms are computed: $(G^{1}_{1},P^{1}_{1})=(G_{2},P_{2})\diamond(G_{1},P_{1})$, $(G^{1}_{0},P^{1}_{0})=(G_{0},P_{0})$. In the second round, the following term is computed: $(G^{2}_{0},P^{2}_{0})=(G^{1}_{1},P^{1}_{1})\diamond(G^{1}_{0},P^{1}_{0})$. Based on the definition of the binary operator $\diamond$, we first have $G^{1}_{1}=G_{2}+G_{1}\cdot P_{2},P^{1}_{1}=P_{2}\cdot P_{1}$. Then, we have $G^{2}_{0}=G^{1}_{1}+G^{1}_{0}\cdot P^{1}_{1}=G_{2}+G_{1}\cdot P_{2}+G_{0}\cdot P_{2}P_{1}$, which corresponds to the carry $c_{3}$.

With all the above insights in mind, we now elaborate on how to support secure decision node evaluation by taking advantage of the carry look-ahead adder in the ciphertext domain. From the definition of the operator $\diamond$, it is noted that only addition and multiplication are required (in $\mathbb{Z}_{2}$). So it is easy to see this operator can be securely realized in the ciphertext domain via secret-shared addition and multiplication. We denote the secure realization of the operator as $(\left\langle{G^{*}}\right\rangle,\left\langle{P^{*}}\right\rangle)=(\left\langle{G^{\prime\prime}}\right\rangle,\left\langle{P^{\prime\prime}}\right\rangle)\tilde{\diamond}(\left\langle{G^{\prime}}\right\rangle,\left\langle{P^{\prime}}\right\rangle)$, where $\left\langle{\cdot}\right\rangle$ denotes secret sharing in $\mathbb{Z}_{2}$. Note that each call of the operator needs $2$ parallel secret-shared multiplications.

The details of secure decision node evaluation are provided in Fig. 6. It is noted that for simplicity and without loss of generality, we demonstrate the procedure assuming that $l=64$, which is the practical parameter setting to be used in our experiments, and also consistent with the state-the-art work [12]. Also, to clearly show the computation that can be done in parallel in each round of secure carry computation, we intentionally avoid the use of nested loops. From the procedure shown in Fig. 6, we can see that for the practical setting $l=64$, only $7$ rounds are required through our design for obtaining the secret sharing $\left\langle{v}\right\rangle$ of the comparison result, in comparison with $125$ rounds in the state-of-the-art work [12].

We also point out that the improvement on communication rounds does not sacrifice the computation efficiency in terms of number of multiplications (in $\mathbb{Z}_{2}$). Through analysis, our new design requires $3l-5$ ($187$ for $l=64$) multiplications while the prior work requires $3l-5$ ($187$ for $l=64$) multiplications as well. We remark that although in principle the carry look-ahead adder has higher circuit complexity than the ripple carry adder when computing all carries is required, our design only needs the computation of the essential carry $c_{l-1}$. This accounts for why our new design does not enlarge the computation cost in secure decision node evaluation compared with [12].

With the secret-shared evaluation results available at each decision node, we now describe how to leverage them to enable the two cloud servers to generate the encrypted inference result. We note that there are two approaches on how to use the decision node evaluation results [12]: a path cost-based approach and a polynomial-based approach. From the perspective of client cost, the main difference between these approaches is that the path cost-based approach imposes on the client high communication complexity exponentially scaling with the tree depth, while the polynomial-based approach only incurs constant $O(1)$ and minimal communication cost (just two shares) for the client.

Given that high local efficiency is our first priority, our system makes use of the polynomial-based approach. This approach works as follows. Starting from the root node, the left outgoing edge of each decision node $\mathcal{D}_{j}$ is assigned the value $1-v_{j}$ (denoted as $E^{L}_{j}=1-v_{j}$), while the right outgoing edge is assigned the value $v_{j}$ (denoted as $E^{R}_{j}=v_{j}$). Then, a term $g_{z}$ is computed for each path by multiplying the edge values of that path. As mentioned before, only the term for the path leading to the leaf node carrying the inference result will have the value $1$, and all other terms are $0$. Then, we can proceed by multiplying each term $g_{z}$ with the prediction value $u_{z}$ of each corresponding leaf node and computing the sum, i.e., $u^{*}=\sum\nolimits_{z}{u_{z}g_{z}}$, which will lead to the expected inference result $u^{*}$.

We use the decision tree in Fig. 1 as an example to concretely demonstrate the computation. Firstly, there are four terms $\{g_{z}\}^{4}_{z=1}$ given that the depth is $2$ and thus four paths/leaf nodes. These terms are computed as follows: $g_{1}=(1-v_{1})\cdot(1-v_{2})$, $g_{2}=(1-v_{1})\cdot v_{2}$, $g_{3}=v_{1}\cdot(1-v_{3})$, and $g_{4}=v_{1}\cdot v_{3}$. Suppose that the feature vector is evaluated along the path of the leaf node $\mathcal{L}_{3}$. We have $v_{1}=1$ and $v_{3}=0$, and so we have $g_{1}=0\cdot(1-v_{2})=0$, $g_{2}=0\cdot v_{2}=0$, $g_{3}=1\cdot(1-0)=1$, and $g_{4}=1\cdot 0=0$. It can be seen that all the terms except the term $g_{3}$ corresponding to $\mathcal{L}_{3}$ has zero value. So we have $\sum\nolimits^{4}_{z=1}{u_{z}g_{z}}=u_{3}$, obtaining the expected inference result. The secure realization of this approach in our system for secure inference generation basically follows that of [12]. For completeness, we give the details of secure inference generation in Fig. 7, which realizes polynomial mechanism introduced above in the secret sharing domain.

Our protocol is implemented in C++. For the oblivious transfer primitive, we rely on the libOTe library [27] which provides implementation of the protocol in [28]. Cloud-side experiments are conducted over two AWS t3.xlarge instances equipped with Intel Xeon Platinum 8175M CPU (2.50GHz and 16GB RAM): one in Europe (London) and one in US East (N. Virginia). The average latency is $75.422$ ms and bandwidth is $161$ Mbits/s. These two instances are situated in different regions for simulating the real-world scenario that the cloud servers are in different trust domains. The provider and the client are evaluated on an AWS t2.xlarge instance possessing an Intel Xeon E5-2676 v3 processor (2.40GHz and 16GB RAM). We test with synthetic decision trees with realistic configurations, following prior works [15, 16, 12]. The tree depth $d$ varies from $3$ to $17$, and the dimension $I$ of the feature vector varies from $9$ to $57$. We make comparison with the state-of-the-art prior work by Zheng et al. [12] (the ZDWWN protocol).

We first evaluate the performance on the local side, i.e., the provider and the client. Fig. 8 and Fig. 9 show the communication and computation costs of the provider for varying decisions trees, along with comparison with the ZDWWN protocol. As the provider in our design just constructs an index vector of $O(J)$ size rather than a matrix of size $O(J\cdot I)$ as in the ZDWWN protocol, he can enjoy significant cost savings. For different decision trees being tested, the communication cost of the provider ranges from $0.0003$ MB to $6$ MB in our system, while it is from $0.0016$ MB to $118$ MB in the ZDWWN protocol. In terms of the provider’s running time, it varies from $0.01$ ms to $33.842$ ms in our system, while it is from $0.013$ ms to $619.723$ ms in the ZDWWN protocol. Overall, our system can offer the provider up to $19\times$ savings (average of $7\times$) in communication. In computation, our system can offer the provider up to $18\times$ savings (average of $5\times$). In Table II, we give the communication cost and computation cost of the client respectively. It is noted that the client has minimal costs which only scales with the dimension of the feature vector. Recall that the client in our system has the same cost as in the ZDWWN protocol, given that the polynomial-based mechanism is used in the phase of secure inference generation which allows the client to only receive the two shares of the inference result.

We now examine the performance on the cloud side. Firstly, we show in Fig. 10 the amount of data transferred between the cloud servers in our system and make comparison with the ZDWWN protocol. Our design has relatively higher communication cost (average of $1.9\times$) than the ZDWWN protocol, which is mainly due to the sue of OT in the secure feature selection phase and the secret-shared multiplications in the secure inference generation phase. We emphasize that such overhead in these two phases is the trade-off for the substantial efficiency improvement on the provider side, which is the first priority in our design philosophy.