<figure><img src="image_1.png" /></figure>

HAL
open science

# Non-interactive Private Decision Tree Evaluation

Anselme Tueno, Yordan Boev, Florian Kerschbaum

► To cite this version:

Anselme Tueno, Yordan Boev, Florian Kerschbaum. Non-interactive Private Decision Tree Evaluation. 34th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jun 2020, Regensburg, Germany. pp.174-194, 10.1007/978-3-030-49669-2_10. hal-03243640

HAL Id: hal-03243640

https://inria.hal.science/hal-03243640

Submitted on 31 May 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Non-Interactive Private Decision Tree
Evaluation

Anselme Tueno¹(✉), Yordan Boev¹, and Florian Kerschbaum²

¹ SAP Security Research, Karlsruhe, Germany
anselme.kemgne.tueno@sap.com

² University of Waterloo, Canada

**Abstract** In this paper, we address the problem of privately evaluating a decision tree on private data. This scenario consists of a server holding a private decision tree model and a client interested in classifying its private attribute vector using the server's private model. The goal of the computation is to obtain the classification while preserving the privacy of both – the decision tree and the client input. After the computation, the client learns the classification result and nothing else, and the server learns nothing. Existing privacy-preserving protocols that address this problem use or combine different generic secure multiparty computation approaches resulting in several interactions between the client and the server. Our goal is to design and implement a novel client-server protocol that delegates the complete tree evaluation to the server while preserving privacy and reducing the overhead. The idea is to use fully (somewhat) homomorphic encryption and evaluate the tree on ciphertexts encrypted under the client's public key. However, since current somewhat homomorphic encryption schemes have high overhead, we combine efficient data representations with different algorithmic optimizations to keep the computational overhead and the communication cost low. As a result, we are able to provide the first non-interactive protocol, that allows the client to delegate the evaluation to the server by sending an encrypted input and receiving only the encryption of the result. Our scheme has only one round and evaluates a complete tree of depth 10 within seconds.

**Keywords:** Machine Learning, Private Decision Tree Evaluation, Secure Multiparty Computation, Fully/Somewhat Homomorphic Encryption

# 1 Introduction

Machine learning (ML) classifiers are valuable tools in many areas such as health-
care, finance, spam filtering, intrusion detection, remote diagnosis, etc. [37]. To
perform their task, these classifiers often require access to personal sensitive
data such as medical or financial records. Therefore, it is crucial to investigate
technologies that preserve the privacy of the data, while benefiting from the ad-
vantages of ML. On the one hand, the ML model itself may contain sensitive
data. On the other hand, the model may have been built on sensitive data. It
is known that white-box and sometimes even black-box access to a ML model
allows so-called *model inversion attacks* [17, 33, 38], which can compromise the
privacy of the training data. As a result, making the ML model public could
violate the privacy of the training data.

In this paper, we therefore address the problem of private decision tree eval-
uation (PDTE) on private data. This scenario consists of a server holding a
private decision tree model and a client wanting to classify its private attribute
vector using the server's private model. The goal of the computation is to obtain
the classification while preserving the privacy of both – the decision tree and
the client input. After the computation, the classification result is revealed only
to the client, and beyond that, nothing further is revealed. The problem can be
solved using any generic secure multiparty computation.

Generic secure multiparty computation [16,20] can implement PDTE. There
exist frameworks such as ObliVM [27] or CBMC-GC [17], HyCC [8] that are able
to automate the transformation of the plaintext decision tree program, written
in a high level programming language, into oblivious programs suitable for se-
cure computation. Their straightforward application to decision tree programs
does certainly improve performance. However, the size of the resulting oblivious
program is still proportional to the size of the tree. As a result generic solution
are in general inefficient, in particular when the size of the tree is large.

Specialized protocols [2, 4, 7, 23, 24, 32, 34, 38] exploit the domain knowledge
of the problem at hand and make use of generic techniques only where it is ne-
cessary, resulting in more efficient solutions. Existing protocols for PDTE have
several rounds requiring several interactions between the client and the server.
Moreover, the communication cost depends on the size of the decision tree, while
only a single classification is required by the client. Finally, they also require com-
putational power from the client that depends on the size of the tree.

Our goal is to design and implement a novel client-server protocol that del-
egates the complete tree evaluation to the server while preserving privacy and
keeping the performance acceptable. The idea is to use fully or somewhat homo-
morphic encryption (FHE/SHE) and evaluate the tree on ciphertexts encrypted
under the client's public key. As a result, no intermediate or final computational
result is revealed to the evaluating server. However, since current SHE/FHE
schemes have high overhead, we combine efficient data representations with dif-
ferent algorithmic optimizations to keep the computational overhead and the
communication cost low. At the end, the computational overhead might still be
higher than in existing protocols, however the computation task can be par-
allelized resulting in a reduced computation time. As a result, we are able to
provide the first non-interactive protocol, that allows the client to delegate the
evaluation to the server by sending an encrypted input and receiving only the en-
cryption of the result. Finally, existing approaches are secure in the semi-honest
model (i.e., parties follow the protocol) and can be made *one-sided simulatable*
using techniques that may double the computation and communication costs.
A one-sided simulatable protocol forces the client to behave semi-honestly and
guarantees that a malicious server learns nothing [22]. Our approach is one-sided
simulatable by default, as the client does no more than encrypting its input and decrypting the final result of the computation (simulating the client is straightforward), while the server evaluates on ciphertexts encrypted with a semantically secure encryption under the client's public key.

Concrete motivation of our approach are machine learning settings (with applications in areas such as healthcare, finance etc.) where the server is computationally powerful, the client is computationally weak and the network connection is not very fast. Our contributions are as follows:

- We propose a non-interactive protocol for PDTE. Our scheme allows the client to delegate the evaluation to the server by sending an encrypted input and receiving only the encryption of the result.

- We propose PDT-BIN which is an instantiation of the main protocol with binary representation of the input. We combine efficient data representations with different algorithmic optimizations to keep the computational overhead and the communication cost low.

- Finally, we implement and benchmark using HElib [21] and TFHE [11].

The remainder of the paper is structured as follows. We review preliminaries in Section 2 before defining correctness and security of our protocol in Section 3. The basic construction itself is described in Section 4. In Section 5, we describe implementation and optimization using a binary representation. We discuss implementation and evaluation details in Section 6. We review related work in Section 7 before concluding our work in Section 8. Due to space constraints, we discuss further details in the appendix.

## 2 Preliminaries

For ease of exposition, we abstract away the mathematical technicalities behind HE and refer to the literature [1, 5, 10, 19, 31]. We start with the notation.

**Notation.** In this paper, $\mu$ denotes the bit length of attribute values, $n$ denotes the dimension of the attribute vector, $m$ denotes the number of decision nodes, $d$ denotes the depth of the decision tree.

**Homomorphic Encryption.** We focus on (lattice-based) homomorphic encryption (HE) schemes that allow many chained additions and multiplications to be computed on plaintext. In these schemes, the plaintext space is usually a ring $\mathbb{Z}_q[X]/(X^N + 1)$, where $q$ is prime and $N$ might be a power of 2.

A HE consists of the usual algorithms for key generation ($pk, sk \leftarrow KGen(\lambda)$), encryption $Enc(pk, m)$ (we denote $Enc(pk, m)$ by $[m]$), decryption $Dec(sk, c)$. HE has an additional evaluation algorithm $Eval(pk, f, c_1, ..., c_n)$ that takes $pk$, an $n$-ary function $f$ and ciphertexts $c_1, ..., c_n$. It outputs a ciphertext $c$ such that if $c_i = [m_i]$ then it holds: $Dec(sk, Eval(f, [m_1], ..., [m_n])) = Dec(sk, [f(m_1, ..., m_n)])$. We require HE to be IND-CPA secure.

The encryption algorithm $Enc$ adds ‘noise’ to the ciphertext which increases during homomorphic evaluation. While addition of ciphertexts increases the
noise slightly, the multiplication increases it significantly [5]. If the noise becomes too large then correct decryption is no longer possible. To prevent this from happening, one can either keep the circuit's depth of the function $f$ low enough or use bootstrapping procedure which reduces the noise in a ciphertext, i.e., fully HE (FHE). In this paper, we will consider both bootstrapping and the possibility of keeping the circuit's depth low by designing our PDTE using so-called leveled FHE. A leveled FHE has an extra parameter $L$ such that the scheme can evaluate all circuits of depth at most $L$ without bootstrapping.

**Homomorphic Operations.** We assume a BGV type HE scheme [5]. Plaintexts can be encrypted using an integer representation (an integer $x_i$ is encrypted as $[x_i]$) or a binary representation (each bit of the bit representation $x_i^b = x_{i\mu} \dots x_{i1}$ is encrypted). We describe below HE operations in the binary representation (i.e., arithmetic operations mod 2). They work similarly in the integer representation.

The FHE scheme might support Smart and Vercauteren's ciphertext packing (SVCP) technique [31] to pack many plaintexts in one ciphertext. Using SVCP, a ciphertext consists of a fixed number $s$ of slots, each capable of holding one plaintext, i.e. $[\cdot|\cdot|\dots|\cdot]$. The encryption of a bit $b$ replicates $b$ to all slots, i.e., $[b] = [b|b|\dots|b]$. However, we can also pack the bits of $x_i^b$ in one ciphertext and will denote it by $[\tilde{x}_i] = [x_{i\mu}|\dots|x_{i1}|0|\dots|0]$.

The computation relies on some built-in routines, that allow homomorphic operations on encrypted data. The relevant routines for our scheme are: addition (SHEADD), multiplication (SHEMULT) and comparison (SHECMP). These routines are compatible with the ciphertext packing technique (i.e., operations are replicated on all slots in a SIMD manner).

The routine SHEADD performs a component-wise addition modulo two, i.e., we have: SHEADD($[b_{i1}|\dots|b_{is}$], $[b_{j1}|\dots|b_{js}$]) = $[b_{i1} \oplus b_{j1}|\dots|b_{is} \oplus b_{js}]$. Similarly, SHEMULT performs component-wise multiplication modulo two, i.e., we have: SHEMULT($[b_{i1}|\dots|b_{is}$], $[b_{j1}|\dots|b_{js}$]) = $[b_{i1} \cdot b_{j1}|\dots|b_{is} \cdot b_{js}]$. We will denote addition and multiplication by $\oplus$ and $\otimes$, respectively.

Let $x_i, x_j$ be two integers, $b_{ij} = [x_i > x_j]$, $b_{ji} = [x_j > x_i]$, the routine SHECMP takes $[x_i^b]$, $[x_j^b]$, compares $x_i$ and $x_j$ and returns $[b_{ij}]$, $[b_{ji}]$: $([b_{ij}], [b_{ji}]) \leftarrow SHECMP([x_i^b], [x_j^b])$. Note that, if the inputs to SHECMP encrypt the same value, then the routine outputs two ciphertexts of 0. This routine implements the comparison circuit described in [9].

If ciphertext packing is enabled, then we also assume that HE supports shift operations. Given a packed ciphertext $[b_1|\dots|b_s]$, the shift left operation shifts all slots to the left by a given offset, using zero-fill, i.e., shifting $[b_1|\dots|b_s]$ by $i$ positions returns $[b_i|\dots|b_s|0|\dots|0]$.

## 3 Definitions

This section introduces relevant definitions. With $[a, b]$, we denote the set of all integers from $a$ to $b$. Let $c_0, \dots, c_{k-1}$ be the classification labels, $k \in \mathbb{N}_{>0}$.

**Definition 1 (Decision Tree).** A decision tree (DT) is a function $\mathcal{T}: \mathbb{Z}^n \rightarrow \{c_0, \dots, c_{k-1}\}$ that maps an attribute vector $x = (x_0, \dots, x_{n-1})$ to a finite set of
classification labels. A DT consists of internal or decision nodes containing a test condition, and leaf nodes containing a classification label. A decision tree model consists of a DT and the following functions: a function thr that assigns to each decision node a threshold value, thr : [0, m − 1] → ℤ ; a function att that assigns to each decision node an attribute index, att : [0, m − 1] → [0, n − 1], and; a labeling function lab that assigns to each leaf node a label, lab : [ m, M − 1] → { c$_{0}$, . . . , c$_{k}$$_{−}$$_{1}$ } . The decision at each decision node is a ‘greater-than’ comparison between the assigned threshold and attribute values, i.e., the decision at node v is [ x$_{att}$ ( v ) ≥ thr ( v )]. We use M = ( T , thr , att ) to denote a decision tree model.

**Definition 2 (Decision Tree Evaluation).** Given an attribute vector x = (x₀, ..., x$_{n-1}$) and M = (T, thr, att), then starting at the root, the Decision Tree Evaluation (DTE) evaluates at each reached node v the decision b ← [x$_{att}$ (v) ≥ thr(v)] and moves either to the left (if b = 0) or right (if b = 1) subsequent node. The evaluation returns the label of the reached leaf as result of the computation. We denote this by T(x).

**Definition 3 (Private DTE).** Given a client with a private $x = (x_0, \dots, x_{n-1})$ and a server with a private $\mathcal{M} = (\mathcal{T}, \mathcal{thr}, \mathcal{att})$, a private DTE (PDTE) functionality evaluates the model $\mathcal{M}$ on input $x$, then reveals to the client the classification label $\mathcal{T}(x)$ and nothing else, while the server learns nothing, i.e., $\mathcal{F}_{\text{PDTE}}(\mathcal{M}, x) \to (\varepsilon, \mathcal{T}(x))$.

**Definition 4 (Correctness).** Given a client with a private $x = (x_0, \dots, x_{n-1})$ and a server with a private $\mathcal{M} = (\mathcal{T}, \mathcal{thr}, \mathcal{att})$, a protocol $\Pi$ correctly implements a PDTE functionality if after the computation it holds for the result $c$ obtained by the client that $c = \mathcal{T}(x)$.

Two distributions $\mathcal{D}_1$ and $\mathcal{D}_2$ are *computationally indistinguishable* (denoted $\mathcal{D}_1 \stackrel{c}{\equiv} \mathcal{D}_2$) if no probabilistic polynomial time (PPT) algorithm can distinguish them except with negligible probability. In SMC protocols, the *view* of a party consists of its input and the sequence of messages that it has received during the protocol execution [20].

**Definition 5 (PDTE Security).** Given a client $C$ with a private input $x = (x_0, \dots, x_{n-1})$ and a server $S$ with a private model $\mathcal{M} = (\mathcal{T}, \mathcal{thr}, \mathcal{att})$, a protocol $\Pi_{\text{PDTE}}$ securely implements the PDTE functionality in the semi-honest model if the following holds: there exists a PPT algorithm $\text{Sim}_S^{\text{pdte}}$ that simulates the server's view $\text{View}_S^{\Pi_{\text{PDTE}}}$ given only $\mathcal{M} = (\mathcal{T}, \mathcal{thr}, \mathcal{att})$, i.e., $\text{Sim}_S^{\text{pdte}}(\mathcal{M}, \varepsilon) \stackrel{c}{\equiv} \text{View}_S^{\Pi_{\text{PDTE}}}(\mathcal{M}, x)$; there exists a PPT algorithm $\text{Sim}_C^{\text{pdte}}$ that simulates the client's view $\text{View}_C^{\Pi_{\text{PDTE}}}$ given only $x$ and $\mathcal{T}(x)$, i.e., $\text{Sim}_C^{\text{pdte}}(x, \mathcal{T}(x)) \stackrel{c}{\equiv} \text{View}_C^{\Pi_{\text{PDTE}}}(\mathcal{M}, x)$.

A protocol $\Pi_{\text{PDTE}}$ securely implements the PDTE functionality with one-sided simulation if the following conditions hold: For every pair $x, x'$ of different client's inputs, it holds $\text{View}_S^{\Pi_{\text{PDTE}}}(\mathcal{M}, x) \stackrel{c}{\equiv} \text{View}_S^{\Pi_{\text{PDTE}}}(\mathcal{M}, x')$; and $\Pi_{\text{PDTE}}$ is simulatable against every PPT adversary controlling $C$.
# 4 The Basic Protocol

We present a modular description of our protocol starting by the data structure.

## 4.1 Data Structure

We follow the idea of previous protocols [4, 12, 32] of marking edges of the tree with comparison result. So if the comparison at node v is the bit b then we mark the right edge to v with b and the left edge with 1-b. For convenience, we will instead store this information at the child nodes of v and refer to it as cmp.

**Definition 6 (Data Structure).** For a decision tree model $\mathcal{M} = (\mathcal{T}, \text{thr}, \text{att})$, we let Node be a data structure that for each node v defines the following fields: v thresholds stores the threshold $\text{thr}(v)$ of v; v.alIndex stores the associated index $\text{att}(v)$; v.parent stores the pointer to the parent node (null for the root); v.left stores the pointer to the left child node (null for each leaf); v.right stores the pointer to the right child node (null for each leaf); v.cmp is computed during the tree evaluation and stores the comparison bit $b \leftarrow [x_{\text{att}(v.parent)} \ge \text{thr}(v.parent)]$ if v is a right node. Otherwise it stores 1-b; v.cLabel stores the classification label if v is a leaf node and the empty string otherwise. We use $\mathcal{D}$ to denote the set of all decision nodes and $\mathcal{L}$ the set of all leaf nodes of $\mathcal{M}$. As a result, we use the equivalent notation $\mathcal{M} = (\mathcal{T}, \text{thr}, \text{att}) = (\mathcal{D}, \mathcal{L})$.

With the data structure defined above, we now define the classification function.

**Definition 7 (Classification Function).** Let $x = (x_0, \dots, x_{n-1})$ be the attribute vector and $\mathcal{M} = (\mathcal{D}, \mathcal{L})$ be the DT model. We define the classification function to be $f_c(x, \mathcal{M}) = \text{tr}(x, \text{root})$, where root is the root node and tr is the traverse function define as:

$$ \text{tr}(x, v) = \begin{cases} \text{tr}(x, v.\text{left}) & \text{if } v \in \mathcal{D} \text{ and } x_{v.\text{alIndex}} < v.\text{threshold} \\ \text{tr}(x, v.\text{right}) & \text{if } v \in \mathcal{D} \text{ and } x_{v.\text{alIndex}} \ge v.\text{threshold} \\ v & \text{if } v \in \mathcal{L} \end{cases} $$

**Lemma 1.** Let $x = (x_0, \dots, x_{n-1})$ be an attribute vector and $\mathcal{M} = (\mathcal{T}, \text{thr}, \text{att}) = (\mathcal{D}, \mathcal{L})$ a DT model. We have $\mathcal{T}(x) = b \cdot \text{tr}(x, \text{root.right}) + (1-b) \cdot \text{tr}(x, \text{root.left})$, where $b = [x_{\text{att}(\text{root})} \ge \text{thr}(\text{root})]$ is the comparison at the root node.

*Proof.* The proof follows by induction on the depth of the tree. In the base case, we have a tree of depth one (i.e., the root and two leaves). In the induction step, we have two trees of depth d and we joint them by adding a new root.

## 4.2 Algorithms

**Initialization.** The Initialization consists of a one-time key generation. The client generates appropriate pair (pk, sk) of public and private keys for a HE scheme, and sends pk to the server. For each input classification, the client just
<table><caption>Algorithm 1: Aggregating Decision Bits</caption><tr><td>1: function EVALPATHS(D, L)</td><td>7: [[v.right.cmp]] &larr; [[v.right.cmp]] &sqcap; [[v.cmp]]</td></tr><tr><td>2: let Q be a queue</td><td>8: if v.left &isin; D then</td></tr><tr><td>3: Qenqueue(root)</td><td>9: Qenqueue(v.left)</td></tr><tr><td>4: while Q.empty() = false do</td><td>10: if v.right &isin; D then</td></tr><tr><td>5: v &larr; Q dequeue()</td><td>11: Qenqueue(v.right)</td></tr><tr><td>6: [[v.left.cmp]] &larr; [[v.left.cmp]] &sqcap; [[v.cmp]]</td><td></td></tr></table>

encrypts its input and sends it to the server. The size of homomorphic ciphertexts are in general very large. To reduce the communication cost of sending client's input, one can use a trusted randomizer that does not take part in the real protocol and is not allowed to collaborate with the server. The trusted randomizer generates a list of random strings $r$ and sends the encrypted strings $[r]$ to server and the list of $r$'s to the client. For an input $x$, the client then sends $x + r$ to the server in the real protocol. This technique is similar to the commodity based cryptography [3] with the difference that the client can play the role of the randomizer itself and sends the list of $[[r]]$'s (when the network is not too busy) before the protocol's start.

**Computing Decision Bits.** The server starts by computing for each node $v \in D$ the comparison bit $b \leftarrow [x_{att}(v) \ge \text{thr}(v)]$ and stores $b$ at the right child node ($v$.right.cmp = $b$) and $1-b$ at the left child node ($v$.left.cmp = $1-b$). We refer to this algorithm as EVALDNODE($D$, $[[x]]$).

**Aggregating Decision Bits.** Then for each leaf node $v$, the server aggregates the comparison bits along the path from the root to $v$. We implement it using a queue and traversing the tree in BFS as illustrated in Algorithm 1.

**Finalizing.** After Aggregating the decision bits along the path to the leaf nodes, each leaf node $v$ stores either $v$.cmp = 0 or $v$.cmp = 1. Then, the server aggregates the decision bits at the leaves by computing for each leaf $v$ the value $[[v.cmp]] \sqcap [[v.cLabel]]$ and summing all the results. We refer to this algorithm as FINALIZE($L$).

**Putting It All Together.** As illustrated in Protocol 2, the whole computation is performed by the server. It sequentially computes the algorithms described above and sends the resulting ciphertext to the client. The client decrypts and outputs the classification label. The correctness follows from Lemma 1.

# 5 Binary Implementation

In this section, we describe PDT-BIN, an instantiation of the basic scheme that requires encoding the plaintexts using their bit representation. Hence, ciphertexts encrypt bits and arithmetic operations are done mod 2.

## 5.1 Input Encoding

We encrypt plaintext bitwise. For each plaintext $x_i$ with bit representation $x_i^b = x_{i\mu} \dots x_{i1}$, we use $[[x_i^b]]$ to denote the vector $([x_{i\mu}], \dots, [x_{i1}])$, consisting
<figure><img src="image_3.png" /><figcaption>Protocol 2: The Basic Protocol</figcaption></figure>

of encryptions of the bits of $x_i$. As a result, the client needs to send $n\mu$ ciphertexts for the $n$ attribute values. Unfortunately, homomorphic ciphertexts might be quite large. We can already use the trusted randomizer as explained before to send blinded inputs instead of ciphertexts in this phase. This, however, improves only the online communication. We additionally want to use the SVCP SIMD technique that allows to pack many plaintexts into the same ciphertext and manipulate them together during homomorphic operations.

## 5.2 Ciphertext Packing

In the binary encoding, ciphertext packing means that each ciphertext encrypts $s$ bits, where $s$ is the number of slots in the ciphertext. Then we can use this property in three different ways. First, one could pack the bit representation of each classification label in a single ciphertext and allow the server to send back a single ciphertext to the client. Second, one could encrypt several attributes together and classify them with a single protocol evaluation. Finally, one could encrypt multiple decision node thresholds that must be compared to the same attribute in the DT model.

**Packing Classification Label's Bits.** Aggregating the decision bits using Algorithm 1 produces for each leaf $v \in \mathcal{L}$ a decision bit $[b_v]$ which encrypts 1 for the classification leaf and 0 otherwise. Moreover, because of SVCP, the bit $b_v$ is replicated to all slots. Now, let $k$ be the number of classification labels (i.e., $|\mathcal{L}| = k$) and its bitlength be $|k|$. For each $v \in \mathcal{L}$, we let $c_v$ denote the classification label $v$. **cLabel** which is $|k|$-bit long and has bit representation $c_v^b = c_{v|k|} \dots c_{v1}$ with corresponding packed encryption $[\tilde{c}_v] = [c_{v|k|} | \dots | c_{v1} | 0 | \dots | 0]$. As a result, computing $[b_v] \sqcup [\tilde{c}_v]$ for each leaf $v \in \mathcal{L}$ and summing over all leaves results
<figure><img src="image_4.png" /><figcaption>Figure 3: Packing Attribute Values</figcaption></figure>

in the correct classification label. Note that, this assumes that one is classifying
only one vector and not many as in the the next case.

**Packing Attribute Values.** Let $x^{(1)}, \dots, x^{(s)}$ be $s$ possible attribute vectors with $x^{(l)} = [x_1^{(l)}, \dots, x_n^{(l)}]$, $1 \le l \le s$. For each $x_i^{(l)}$, let $x_i^{(l)\mathrm{b}} = x_{i\mu}^{(l)}, \dots, x_{i1}^{(l)}$ be the bit representation. Then, the client generates for each attribute $x_i$ the ciphertexts $[[cx_{i\mu}]]$, $\dots$, $[[cx_{i2}]]$, $[[cx_{i1}]]$ as illustrated in Figure 3a.

To shorten the notation, let $y_j$ denote the threshold of the $j$-th decision
node (i.e., $y_j = v_j$.threshold) and assume $v_j$.alindex = $i$. The server just encrypts
each threshold bitwise which automatically replicates the bit to all slots. This is
illustrated in Figure 3b.

Note that $([cy_{j\mu}], \dots, [cy_{j1}]) = [y_j^b]$ holds because of SVCP. The above described encoding allows to compare $s$ attribute values together with one threshold. This is possible because the routine SHECMP is compatible with SVCP such that we have: SHECMP $([cx_{i\mu}], \dots, [cx_{i1}]), [y_j^b]) = ([b_{ij}^{(1)}|\dots|b_{ij}^{(s)}], [b_{ji}^{(1)}|\dots|b_{ji}^{(s)}]),$ where $b_{ij}^{(l)} = [x_i^{(l)} > y_j]$ and $b_{ji}^{(l)} = [y_j > x_i^{(l)}]$. This results in a single ciphertext such that the $l$-th slot contains the comparison result between $b_{ij}^{(l)}$.

Aggregating decision bits remains unchanged as described in Algorithm 1. It results in a packed ciphertext $[[b_v]] = [[b_v^{(1)}|\dots|b_v^{(s)}]]$ for each leaf $v \in \mathcal{L}$, where $b_v^{(l)} = 1$ if $x^{(l)}$ classifies to leaf $v$ and $b_u^{(l)} = 0$ for all other leaf $u \in \mathcal{L} \setminus \{v\}$.

For the classification label $c_v$ of a leaf node $v \in \mathcal{L}$, let $[[c_v^b]] = ([c_{v|k}], \dots, [c_{v1}])$ denote the encryption of the bit representation $c_v^b = c_{v|k}|\dots|c_{v1}$. To select the correct classification label algorithm FINALIZE($\mathcal{L}$) is updated as follows. We compute $[[c_{v|k}]] \sqcap [[b_v]], \dots, [[c_{v1}] \sqcap [[b_v]]$ for each leaf $v \in \mathcal{L}$ and sum them componentwise over all leaves. This results in the encrypted bit representation of the correct classification labels.

**Packing Threshold Values.** In this case, the client encrypts a single attribute in one ciphertext, while the server encrypts multiple threshold values in a single ciphertext. Hence, for an attribute value $x_i$, the client generates the ciphertexts similar to in Figure 3a. Let $m_i$ be the number of decision nodes that compare to the attribute $x_i$ (i.e., $m_i = |\{v_j \in \mathcal{D} : v_j.alindex = i\}|$). The server packs all corresponding threshold values in $\lfloor \frac{m_i}{s} \rfloor$ ciphertext(s).

The packing of threshold values allows to compare one attribute value against
multiple threshold values together. Unfortunately, we do not have access to the
slots while performing homomorphic operation. Hence, to aggregate the decision
bits, we make $m_i$ copies of the resulting packed decision bits and shift left each decision bit to the first slot. Then the aggregation of the decision bits and the finalizing algorithm work as in the previous case with the only difference that only the result in the first slot matters and the remaining can be set to 0.

## 5.3 Efficient Path Evaluation

Homomorphic multiplication increases the noise significantly [5]. To evaluate paths, we need to keep the multiplication depth small.

**Definition 8 (Multiplicative Depth).** Let $f$ be a function, $C_f$ be a boolean circuit that computes $f$ and consists of AND-gates or multiplication (modulo 2) gates and XOR-gates or addition (modulo 2) gates. The circuit depth of $C_f$ is the maximal length of a path from an input gate to an output gate. The multiplicative depth of $C_f$ is the path from an input gate to an output gate with the largest number of multiplications gates.

Path evaluation requires to homomorphically compute $f([a_1, \dots, a_n]) = \Pi_{i=1}^n a_i$, where the $a_i$ are comparison results on the path.

**Lemma 2 (Logarithmic Multiplicative Depth).** Let $[a_1, \dots, a_n]$ be an array of $n$ integers and $f$ be the function: $f([a_1, \dots, a_n]) = [a'_1, \dots, a'_{\lceil \frac{n}{2} \rceil}]$, where

$$a'_{i} = \begin{cases} a_{2i-1} \cdot a_{2i} & \text{if } (n \bmod 2 = 0) \lor (i < \lceil \frac{n}{2} \rceil), \\ a_n & \text{if } (n \bmod 2 = 1) \land (i = \lceil \frac{n}{2} \rceil). \end{cases}$$

Moreover, let $f$ be an iterated function where $f^i$ is the $i$-th iterate defined as:

$$f^i([a_1, \dots, a_n]) = \begin{cases} [a_1, \dots, a_n] & \text{if } i = 0, \\ f(f^{i-1}([a_1, \dots, a_n])) & \text{if } i \ge 1. \end{cases}$$

The $|n|$-th iterate $f^{|n|}$ of $f$ computes $\Pi_{i=1}^n a_i$ and has multiplicative depth $|n| - 1$ if $n$ is a power of two and $|n|$ otherwise, where $|n| = \log n$ is the bitlength of $n$: $f^{|n|}([a_1, \dots, a_n]) = [\Pi_{i=1}^n a_i]$.

Due to space constraints, we provide the algorithm for path evaluation with multiplicative depth in the Appendix (Algorithm 6). This algorithm consists of a main function EVALPATHSE that collects for each leaf $v$ encrypted comparison results on the path from the root to $v$, and a sub-function EVALMUL which multiplies comparison results according to Lemma 2.

Although highly parallelizable, EVALPATHSE is still not optimal, as each path is considered individually. Since multiple paths in a binary tree share a common prefix (from the root), one would ideally want to handle common prefixes one time and not many times for each leaf. This can be solved using memoization technique which is an optimization that stores results of expensive function calls such that they can be used latter if needed. Unfortunately, naive memoization
would require a complex synchronization in a multi-threaded environment and linear multiplicative depth. The next section describes a pre-computation on the tree, that would allow us to have the best of both worlds - multiplication with logarithmic depth along the paths, while reusing the result of common prefixes.

## 5.4 Improving Path Evaluation with Pre-Computation

The idea behind this optimization is to use directed acyclic graph which we want to define first.

**Definition 9 (DAG).** A directed acyclic graph (DAG) is a graph with directed edges in which there are no cycles. A vertex v of a DAG is said to be reachable from another vertex u if there exists a non-trivial path that starts at u and ends at v. The reachability relationship is a partial order ≤ and we say that two vertices u and v are ordered as u ≤ v if there exists a directed path from u to v.

We require our DAGs to have a unique maximum element. The edges in the DAG define dependency relation between vertices.

**Definition 10 (Dependency Graph).** Let $h$ be the function that takes two DAGs $G_1, G_2$ and returns a DAG $G_3$ that connects the maxima of $G_1$ and $G_2$. We define the function $g([a_1, \dots, a_n])$ that takes an array of integers and returns:

- a graph with a single vertex labeled with $a_1$ if $n=1$

- $h(g([a_1, \dots, a_{n'}]), g([a_{n'+1}, \dots, a_n]))$ if $n > 1$ holds, where $n' = 2^{|n|-1}$ and $|n|$ denotes the bitlength of $n$.

We call the DAG $G$ generated by $G = g([a_1, \dots, a_n])$ a dependency graph. For each edge $(a_i, a_j)$ in $G$ such that $i < j$, we say that $a_j$ depends on $a_i$ and denote this by adding $a_i$ in the dependency list of $a_j$. We require that if $L(j) = [a_{i_1}, \dots, a_{i_{|L(j)|}}]$ is the dependency list of $a_j$ then it holds $i_1 > i_2 > \dots i_{|L(j)|}$.

An example of dependency graph generated by the function $g([a_1, \dots, a_n])$ is illustrated in Figure 4a for $n=4$ and $n=5$.

**Lemma 3.** Let $[a_1, \dots, a_n]$ be an array of $n$ integers. Then $g([a_1, \dots, a_n])$ as defined above generates a DAG whose maximum element is marked with $a_n$.

**Lemma 4.** Let $[a_1, \dots, a_n]$ be an array of $n$ integers, $G = g([a_1, \dots, a_n])$ be a DAG as above, and $L(j) = [a_{i_1}, \dots, a_{i_{|L(j)|}}]$ be the dependency list of $a_j$. Then the algorithm in Figure 4b computes $\Pi_{i=1}^n a_i$ with a multiplicative depth of $\log(n)$.

The proofs of Lemmas 3 and 4 follow by induction similar to Lemma 2. Before describing the improved path evaluation algorithm, we first extend our Node data structure by adding to it a new field representing a stack denoted dag, that stores the dependency list. Moreover, we group the nodes of the DT by level and use an array denoted level[], such that level[0] stores a pointer to the root and level[i] stores pointers to the child nodes of level[i-1] for $i \ge 1$.
<figure><img src="image_5.png" /><figcaption>Figure 4: DAG Pre-computation and Multiplication Algorithm using DAG</figcaption></figure>

Now, we are ready to describe the improved path evaluation algorithm which consists of a pre-computation step and an online step.

The pre-computation is a one-time computation that depends only on the structure of the DT and requires no encryption. As described in Algorithm 7, its main function COMPUTEDAG uses the leveled structure of the tree and the dependency graph defined above to compute the dependency list of each node in the tree (i.e., the DAG defined above). The sub-function ADDEDGE is used to actually add nodes to the dependency list of another node (i.e., by adding edges between these nodes in the DAG).

The online step is described in Algorithm 8. It follows the idea of the algorithm in Figure 4b by multiplying decision bit level-wise depending on the dependency lists. The correctness follows from Lemma 4.

# 6 Evaluation

In this section, we discuss some implementation details and evaluate our schemes.

## 6.1 Implementation Details

We implemented our algorithms using HElib [21] and TFHE [10, 11]. We also implemented the main algorithm using an arithmetic circuit based on Lin-Tzeng comparison protocol [26,35]. We refer to this implementation as PDT-INT. HElib is a C++ library that implements FHE. The current version includes an implementation of the BGV scheme [5]. HElib also includes various optimizations that make FHE runs faster, including ciphertext packing (SVCP) techniques [31].

TFHE is a C/C++ library that implements FHE proposed by Chillotti et al. [10]. It allows to evaluate any boolean circuit on encrypted data. The current version implements a very fast gate-by-gate bootstrapping, i.e., bootstrapping is performed after each gate evaluation. Future versions will include leveled FHE and ciphertext packing Chillotti et al. [10]. Dai and Sunar [13, 14] propose an implementation of TFHE on CUDA-enabled GPUs that is 26 times faster.
<figure><img src="image_6.png" /><figcaption>Figure 5: PDT-BIN Runtime</figcaption></figure>

We evaluated our scheme on an AWS instance with Intel(R) Xeon(R) Plat-
inum 8124M CPU @ 3.00GHz running Ubuntu 18.04.2 LTS; with 36 CPUs, 144
GB Memory and 8 GB SSD. As the bottleneck of our scheme is the overhead
of the HE, we focus on the computation done by the server. We describe HE
parameters and the performance of basic operations in Appendix A.

6.2 Performance of Pdt-Bin

In this section, we report on our experiment with PDT-BIN on complete trees.
Recall that for FHE supporting SIMD, we can use attribute values packing
that allows to evaluate many attribute vectors together. We, therefore, focus
on attribute packing to show the advantage of SIMD. Figure 5a illustrates the
amortized runtime of PDT-BIN with HElib. That is, the time of one PDTE
evaluation divided by the number of slots in a ciphertext. As one can expect,
the runtime clearly depends on the bitlength of the attribute values and the
depth of the tree. The results show a clear advantage of HElib when classifying
large data sets. For paths aggregation, we proposed EVALPATHSE (Algorithm 6)
and EVALPATHSP (Algorithm 8). Figure 5b illustrates PDT-BIN runtime using
these algorithms in a multi-threaded environment and shows a clear advantage
of EVALPATHSP which will be used in the remaining experiments with PDT-BIN.
Figure 5c illustrates the runtime of PDT-BIN with HElibmed showing that the
computation cost is dominated by the computation of decision bits which in-
volves homomorphic evaluation of comparison circuits. In Figure 5d, we report
the evaluation of PDT-BIN using TFHE, which shows a clear advantage com-
pared to HElib. For the same experiment with 72 threads, TFHE evaluates a
<table><caption>Table 1: Runtime (in seconds) on Real Datasets: λ is the security level. μ is the input bit length. #thd is the number of threads. Column ‘one’ is the time for one protocol run while ‘am.’ is the amortized time (e.g., the time for one run divided by s).</caption><thead><tr><th rowspan="2">λ<br>μ<br>#thd</th><th rowspan="2">n, d, m</th><th colspan="2">PDT-BIN<br>(TFHE)</th><th colspan="2">PDT-BIN<br>(HElib)</th><th colspan="2">PDT-INT<br>(HElib)</th><th colspan="2">[28]<br>(HElib)</th></tr><tr><th>one</th><th>am.</th><th>one</th><th>am.</th><th>one</th><th>am.</th><th>one</th><th>am.</th></tr></thead><tbody><tr><td>Heart-disease</td><td>13, 3, 5</td><td>0.94</td><td>0.05</td><td>40.61</td><td>0.0073</td><td>45.59</td><td>0.59</td><td>0.25</td></tr><tr><td>Housing</td><td>13, 13, 92</td><td>6.30</td><td>0.35</td><td>252.38</td><td>0.90</td><td>428.23</td><td>10.27</td><td>1.98</td></tr><tr><td>Spambase</td><td>57, 17, 58</td><td>3.66</td><td>0.24</td><td>174.46</td><td>0.72</td><td>339.60</td><td>6.88</td><td>1.80</td></tr><tr><td>Artificial</td><td>16, 10, 500</td><td>22.39</td><td>1.81</td><td>1303.55</td><td>0.75</td><td>2207.13</td><td>56.37</td><td>10.42</td></tr></tbody></table>

complete tree of depth 10 and 64-bit input in less than 80 seconds, while HElib takes about 400 seconds for 16-bit input. Recall that, a CUDA implementation [13,14] of TFHE can further improve the time of PDT-BIN using TFHE.

## 6.3 Performance on Real Datasets

We also performed experiments on real datasets from the UCI repository [36]. For PDT-BIN, we reported the costs for HElib (single and amortized) and the costs for TFHE. Since TFHE evaluates only boolean circuits, we only have implementation and evaluation of PDT-INT with HElib. We also illustrate in Table 1 the costs of two best previous works that rely only on HE, whereby the figures are taken from the respective papers [28, 32]. For one protocol run, PDT-BIN with TFHE is much more faster than PDT-BIN with HElib which is also faster than PDT-INT with HElib. However, because of the large number of slots, the amortized cost of PDT-BIN with HElib is better. For 16-bit inputs, our amortized time with HElib and our time with TFHE outperform XCMP [28] which used 12-bit inputs. For the same input bitlength, XCMP is still much more better than our one run using HElib, since the multiplicative depth is just 3. However, our schemes still have a better communication and PDT-BIN has no leakage. While the scheme of Tai et al. [32] in the semi-honest model has a better time for 64-bit inputs than our schemes for 16-bit inputs, it requires a fast network communication and at least double cost in the malicious model. The efficiency of Tai et al. is in part due to their ECC implementation of the lifted ElGamal, which allows a fast runtime and smaller ciphertexts, but is not secure against a quantum attacker, unlike lattice-based FHE as used in our schemes.

## 7 Related Work

Our work is related to secure multiparty computation (SMC) [16, 20], private function evaluation (PFE) [25, 30] particularly privacy-preserving DT evaluation [2, 4, 7, 23, 24, 32, 34, 38] which we briefly review in this section and refer to the literature for more details. Brikell et al. [7] propose the first protocol for PDTE
<table><caption>Table 2: Comparison of PDTE protocols.</caption><thead><tr><th>Scheme</th><th>Rounds</th><th>Tools</th><th>Communication</th><th>Comparisons</th><th>Leakage</th></tr></thead><tbody><tr><td>[7]</td><td>≈5</td><td>HE+GC</td><td>O(2<sup>d</sup>)</td><td>d</td><td>m, d</td></tr><tr><td>[2]</td><td>≈4</td><td>HE+GC</td><td>O(2<sup>d</sup>)</td><td>d</td><td>m, d</td></tr><tr><td>[4]</td><td>≥6</td><td>FHE/SHE</td><td>O(2<sup>d</sup>)</td><td>m</td><td>m</td></tr><tr><td>[38]</td><td>6</td><td>HE+OT</td><td>O(2<sup>d</sup>)</td><td>m</td><td>m</td></tr><tr><td>[32]</td><td>4</td><td>HE</td><td>O(2<sup>d</sup>)</td><td>m</td><td>m</td></tr><tr><td>[12]</td><td>≈9</td><td>SS</td><td>O(2<sup>d</sup>)</td><td>m</td><td>m, d</td></tr><tr><td rowspan="2">[34]</td><td rowspan="2">O(d)</td><td>GC, OT</td><td>O(2<sup>d</sup>)</td><td rowspan="2">d</td><td rowspan="2">m, d</td></tr><tr><td>ORAM</td><td>O(d<sup>2</sup>)</td></tr><tr><td>[28]</td><td>1</td><td>FHE/SHE</td><td>O(2<sup>d</sup>)</td><td>m</td><td>m</td></tr><tr><td>PDT-BIN</td><td>1</td><td>FHE/SHE</td><td>O(1), O(d)</td><td>m</td><td>-</td></tr><tr><td>PDT-INT</td><td>1</td><td>FHE/SHE</td><td>O(2<sup>d</sup>/s)</td><td>m</td><td>m</td></tr></tbody></table>

<table><caption>Table 3: Comparison of 1-round PDTE protocols.</caption><thead><tr><th>Scheme</th><th>SIMD</th><th>Generic</th><th>Output-<br>expressive</th><th>Multiplicative<br>Depth</th><th>Output<br>Length</th></tr></thead><tbody><tr><td>[28]</td><td>no</td><td>no</td><td>no</td><td>3</td><td>2<sup>d+1</sup></td></tr><tr><td>PDT-BIN</td><td>yes</td><td>yes</td><td>yes</td><td>|μ| + |d| + 2</td><td>1 or d</td></tr><tr><td>PDT-INT</td><td>yes</td><td>yes</td><td>no</td><td>|μ| + 1</td><td>[2<sup>d</sup>/s]</td></tr></tbody></table>

by combining additively HE and garbled circuits (GC) in a novel way. Although the evaluation time of Brikell et al.'s scheme is sublinear in the tree size, the secure program itself and hence the communication cost is linear and therefore not efficient for large trees. Barni et al. [2] improve the previous scheme by reducing the computation costs by a constant factor. Bost et al. [4] represent the DT as a multivariate polynomial. The parties evaluate this polynomial interactively and encrypted under the client's public key using a fully HE Wu et al. [38] use different techniques that require only additively HE (AHE). They use the DGK protocol [15] for comparison and reveal to the server comparison bits encrypted under the client's public key. Tai et al. [32] use the DGK comparison protocol [15] and AHE as well, but mark the edges with the comparison results at each node. Tueno et al. [34] represent the tree as an array. Then, they traverse the tree interactively and use secure array indexing to select the next node and attribute. Kiss et al. [24] propose a modular design consisting of the sub-functionalities: selection of attributes, integer comparison, and evaluation of paths. De Cock et al. [12] follow the same idea as some previous schemes, but operate in the information theoretic model using secret sharing (SS) based SMC and commodity-based cryptography [3]. Using a polynomial encoding of the inputs and BGV homomorphic scheme [5], Lu et al. [28] propose a non-interactive comparison protocol called XCMP which is *output expressive* (i.e., it preserves additive homomorphism). They implement the scheme of Tai et al. [32] using XCMP. The resulting PDTE is non-interactive and efficient because of the small *multiplicative depth*. However, it is not *generic*, as it primarily works for small
inputs and depends explicitly on BGV-type HE scheme. Moreover, it does not support *SIMD* operations and is no longer output expressive as XCMP. Hence, it cannot be extended to a larger protocol (e.g., random forest [6]) while preserving the non-interactive property. Finally, its *output length* (i.e., the number of resulted ciphertexts from server computation) is exponential in the depth *d* of the tree, while the output length of our binary instantiation *PDT-BIN* is at most linear in *d*. A comparison of PDTE protocols is summarized in Tables 2 and 3. A more detailed complexity analysis of our schemes is described in Appendix C.

## 8 Conclusion

While almost all existing PDTE protocols require many interaction between the client and the server, we designed and implemented novel client-server protocols that delegate the complete evaluation to the server while preserving privacy and keeping the overhead low. Our solutions rely on SHE/FHE and evaluate the tree on ciphertexts encrypted under the client's public key. Since current SHE/FHE schemes have high overhead, we combine efficient data representations with different algorithmic optimizations to keep the computational overhead and the communication cost low.

## References

1. Albrecht, M., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Hoffstein, J., Lauter, K., Lokam, S., Micciancio, D., Moody, D., Morrison, T., Sahai, A., Vaikuntanathan, V.: Homomorphic encryption security standard. Tech. rep., HomomorphicEncryption.org, Cambridge MA (March 2018)

2. Barni, M., Failla, P., Kolesnikov, V., Lazzeretti, R., Sadeghi, A.R., Schneider, T.: Secure evaluation of private linear branching programs with medical applications. In: ESORICS. pp. 424–439. Springer-Verlag, Berlin, Heidelberg (2009)

3. Beaver, D.: Commodity-based cryptography (extended abstract). In: STOC. pp. 446–455. ACM, New York, NY, USA (1997)

4. Bost, R., Popa, R.A., Tu, S., Goldwasser, S.: Machine learning classification over encrypted data. In: NDSS (2015)

5. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: Fully homomorphic encryption without bootstrapping. ECCC 18, 111 (2011)

6. Breiman, L.: Random forests. Mach. Learn. 45(1), 5–32 (Oct 2001)

7. Brickell, J., Porter, D.E., Shmatikov, V., Witchel, E.: Privacy-preserving remote diagnostics. In: CCS. pp. 498–507. ACM, New York, NY, USA (2007)

8. Büscher, N., Demmler, D., Katzenbeisser, S., Kretzmer, D., Schneider, T.: Hycc: Compilation of hybrid protocols for practical secure computation. In: CCS ’18. pp. 847–861 (2018)

9. Cheon, J.H., Kim, M., Kim, M.: Search-and-compute on encrypted data. In: FC. pp. 142–159 (2015)

10. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: fast fully homomorphic encryption over the torus. IACR Cryptology ePrint Archive 2018, 421 (2018)
11. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: Fast fully homomorphic encryption library (August 2016), https://tfhe.github.io/tfhe/

12. Cock, M.D., Dowsley, R., Horst, C., Katti, R.S., Nascimento, A.C.A., Poon, W., Truex, S.: Efficient and private scoring of decision trees, support vector machines and logistic regression models based on pre-computation. IEEE Trans. Dependable Sec. Comput. **16**(2), 217–230 (2019)

13. Dai, W., Sunar, B.: cuhe: A homomorphic encryption accelerator library. In: BalkanCryptSec 2015 (September 2015)

14. Dai, W., Sunar, B.: Cuda-accelerated fully homomorphic encryption library (August 2019), https://github.com/vernamlab/cuFHE

15. Damgård, I., Geisler, M., Krøigaard, M.: Efficient and secure comparison for on-line auctions. In: ACISP. pp. 416–430 (2007)

16. Damgård, I., Pastro, V., Smart, N.P., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: CRYPTO '12. pp. 643–662 (2012)

17. Franz, M., Holzer, A., Katzenbeisser, S., Schallhart, C., Veith, H.: CBMC-GC: an ANSI C compiler for secure two-party computations. In: CC '14. pp. 244–249 (2014)

18. Fredrikson, M., Jha, S., Ristenpart, T.: Model inversion attacks that exploit confidence information and basic countermeasures. In: CCS. pp. 1322–1333 (2015)

19. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC. pp. 169–178. ACM, New York, NY, USA (2009)

20. Goldreich, O.: Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, New York, NY, USA (2004)

21. Halevi, S., Shoup, V.: Algorithms in helib. In: CRYPTO (1). Lecture Notes in Computer Science, vol. 8616, pp. 554–571. Springer (2014)

22. Hazay, C., Lindell, Y.: Efficient Secure Two-Party Protocols: Techniques and Constructions. Springer-Verlag New York, Inc., New York, NY, USA, 1st edn. (2010)

23. Joye, M., Salehi, F.: Private yet efficient decision tree evaluation. In: DBSec. Lecture Notes in Computer Science, vol. 10980, pp. 243–259. Springer (2018)

24. Kiss, Á., Naderpour, M., Liu, J., Asokan, N., Schneider, T.: Sok: Modular and efficient private decision tree evaluation. PoPETs **2019**(2), 187–208 (2019)

25. Kiss, A., Schneider, T.: Valiant's universal circuit is practical. In: EUROCRYPT '2016. pp. 699–728 (2016)

26. Lin, H., Tzeng, W.: An efficient solution to the millionaires' problem based on homomorphic encryption. In: ACNS. pp. 456–466 (2005)

27. Liu, C., Wang, X.S., Nayak, K., Huang, Y., Shi, E.: Oblivm: A programming framework for secure computation. In: SP. pp. 359–376 (2015)

28. Lu, W.j., Zhou, J.j., Sakuma, J.: Non-interactive and output expressive private comparison from homomorphic encryption. In: ASIACCS '18. pp. 67–74 (2018)

29. mcl library (September 2019), https://github.com/herumi/mcl/

30. Mohassel, P., Sadeghian, S.S., Smart, N.P.: Actively secure private function evaluation. In: ASIACRYPT. pp. 486–505 (2014)

31. Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. Des. Codes Cryptography **71**(1), 57–81 (2014)

32. Tai, R.K.H., Ma, J.P.K., Zhao, Y., Chow, S.S.M.: Privacy-preserving decision trees evaluation via linear functions. In: ESORICS. pp. 494–512 (2017)

33. Tramèr, F., Zhang, F., Juels, A., Reiter, M.K., Ristenpart, T.: Stealing machine learning models via prediction apis. In: USENIX. pp. 601–618 (2016)

34. Tueno, A., Kerschbaum, F., Katzenbeisser, S.: Private evaluation of decision trees using sublinear cost. PoPETs **2019**, 266–286
35. Tueno, A., Kerschbaum, F., Katzenbeisser, S., Boev, Y., Qureshi, M.: Secure computation of the kth-ranked element in a star network. In: FC '20 (2020)

36. Uci repository. http://archive.ics.uci.edu/ml/index.php (2019)

37. Witten, I.H., Frank, E., Hall, M.A.: Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 3rd edn. (2011)

38. Wu, D.J., Feng, T., Naehrig, M., Lauter, K.: Privately evaluating decision trees and random forests. PoPETs 2016(4), 335–355 (2016)

39. Wu, X., Fredrikson, M., Jha, S., Naughton, J.F.: A methodology for formalizing model-inversion attacks. In: CSF. pp. 355–370 (2016)

## A Encryption Parameters and Basic Operations

Recall that FHE schemes – as considered in this paper – are usually defined over a ring $Z[X]/(X^N + 1)$ and that the encryption scheme might be a leveled FHE with parameter $L$. For HElib, the parameters $N$ and $L$ determines how to generate encryption keys for a security level $\lambda$ which is at least 128 in all our experiments. The degree of the ring polynomial in HElib is not necessarily a power of 2. The ring polynomial is chosen among the cyclotomic polynomials. For HElib, we abuse the notation and use $N$ to denote the $N$-th cyclotomic polynomial. Given the value of $L$ and other parameters, the HElib function FindM(·) computes the $N$-th cyclotomic polynomial, that guarantees a security level at least equal to a given security parameter $\lambda$. Table 4 summarizes the parameters we used for key generation and the resulting sizes for encryption keys and ciphertexts. We refer to it as *homomorphic context* or just *context*. For HElib, one needs to choose $L$ large enough than the depth of the circuit to be evaluated and then computes an appropriate value for $N$ that ensures a security level at least 128. We experimented with tree different contexts (HElib$_{small}$, HElib$_{med}$, HElib$_{big}$) for the binary representation used in PDT-BIN, and HElib$_{int}$ for the integer representation used in PDT-INT. For TFHE, the default value of $N$ is 1024 and the security level is 128 while $L$ is infinite because of the gate-by-gate bootstrapping. We used the context TFHE$_{128}$ to evaluate PDT-BIN with TFHE. The last two columns of Table 4 reports the average runtime for encryption and decryption over 100 runs.

<table><caption>Table 4: HE Parameters and Results: For HElib, column $N$ is not the degree of the ring polynomial, but the $N$-th cyclotomic polynomial. It is computed in HElib using a function called FindM(·).</caption><thead><tr><th>Name</th><th>L</th><th>N</th><th>λ<br>(bits)</th><th>Slots</th><th>sk<br>(MB)</th><th>pk<br>(MB)</th><th>Ctxt<br>(MB)</th><th>Enc<br>(ms)</th><th>Dec<br>(ms)</th></tr></thead><tbody><tr><td>HElib<sub>small</sub></td><td>200</td><td>13981</td><td>151</td><td>600</td><td>52.2</td><td>51.6</td><td>1.7</td><td>59.21</td><td>26.08</td></tr><tr><td>HElib<sub>med</sub></td><td>300</td><td>18631</td><td>153</td><td>720</td><td>135.4</td><td>134.1</td><td>3.7</td><td>124.39</td><td>54.31</td></tr><tr><td>HElib<sub>big</sub></td><td>500</td><td>32109</td><td>132</td><td>1800</td><td>370.1</td><td>367.1</td><td>8.8</td><td>283.49</td><td>127.11</td></tr><tr><td>HElib<sub>int</sub></td><td>450</td><td>24793</td><td>138.161</td><td>6198</td><td>370.1</td><td>367.1</td><td>8.8</td><td>323.41</td><td>88.63</td></tr><tr><td>TFHE<sub>128</sub></td><td>∞</td><td>1024</td><td>128</td><td>1</td><td>82.1</td><td>82.1</td><td>0.002</td><td>0.04842</td><td>0.00129</td></tr></tbody></table>
<figure><img src="image_7.png" /><figcaption>Algorithm 6: Paths Evaluation with log Multiplicative Depth</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Algorithm 7: Pre-computation of Multiplication DAG</figcaption></figure>

## B Security Analysis

It is straightforward to see that our protocols are secure. There is no interaction with the client during the computation and a semi-honest server sees only IND-CPA ciphertexts. A semi-honest client only learns the encryption of the result. A malicious server can only return a false classification result. This is inherent to PFE where the function (the DT in our case) is an input to the computation. A malicious client can send a too 'noisy' ciphertext, such that after the computation at the server a correct decryption is not possible, leaking some information. This attack works only with level FHE and is easy to deal with, namely the computation of a ciphertext capacity is a public function which the server can use to check the ciphertexts before starting the computation. As PDT-BIN returns the bit representation of the resulted classification label whose bitlength is public (i.e., the set of possible classification labels is known to the client), there is no leakage beyond the final output. PDT-INT returns as many ciphertexts as there are leaves and, therefore, leaks the number of decision nodes.
Input: nodes stored by level in array level

Output: Updated v.cmp for each v ∈ L

1: function EVALPATHSP

2: for i = 1 to d do ▷ top to bottom level

3: for each v ∈ level[i] do

4: while NOT v.dag.empty() do ▷ stack

5: w ← v.dag.pop()

6: [[v.cmp]] ← [[v.cmp]] ⋄ [[w.cmp]]

<caption>Algorithm 8: Aggregate Decision Bits with DAG</caption>

C Complexity analysis

We now analyse the complexity of our schemes. We assume that the decision
tree is a complete tree with depth *d*.

**Complexity of Pdt-Bin.** The SHE comparison circuit has multiplicative depth $|\mu - 1| + 1$ and requires $O(\mu \cdot |\mu|)$ multiplications [9]. That is, the evaluation of all decision nodes requires $O(2^d \mu \cdot |\mu|)$ multiplications. The path evaluation has a multiplicative depth of $|d - 1|$ and requires for all $2^d$ paths $O(d2^d)$ multiplications. The evaluation of the leaves has a multiplicative depth of 1 and requires in total $2^d$ multiplications. The total multiplicative depth for PDT-BIN is, therefore, $|\mu - 1| + |d - 1| + 2 \approx |\mu| + |d| + 2$ while the total number of multiplications is $O(2^d \mu \cdot |\mu| + d2^d + 2^d) \approx O(d2^d)$.

For the label packing, the bit representation of each classification label is
packed in one ciphertext. This hold for the final result as well. As a result, if the
tree is complete and all classification labels are distinct, then the server sends
$[\frac{d}{s}]$ ciphertext(s) to client. In practice, however, $[\frac{d}{s}] = 1$ holds as $d$ is smaller
that the number $s$ of slots.

For threshold packing, the decision bit $b_v$ at node $v$ is encrypted as $[[b_v|0|...|0]]$.
By encrypting the classification label $c_i = c_{i|k}|...|c_{i1}$ as $[[c_{i|k}|0|...|0]]$, ..., $[[c_{i1}|0|...|0]]$,
the final result $c_l$ will be encrypted similarly such that with extra shifts, we
can build the ciphertext $[[c_{l|k}|...|c_{l1}|0|...|0]]$. As a result, the server sends only 1
ciphertext back to the client.

For other cases (e.g., attribute packing, or no packing at all as in the current
implementation of TFHE), the bits of a classification label are encrypted separat-
ately which holds for the final result as well. As a result the server sends back *d*
ciphertexts to the client.

**Complexity of Pdt-Int.** The modified Lin-Tzeng comparison circuit has multiplicative $|\mu - 1|$ and requires $O(\mu - 1)$ multiplications. As a result, the evaluation of all decision node requires $O((\mu - 1)2^d)$ multiplications. In PDT-INT, the path evaluation does not requires any multiplication. However, the leave evaluation has a multiplicative depth of 1 and requires in total $2^d$ multiplications. The total multiplicative depth for PDT-INT is therefore $|\mu - 1| + 1 \approx |\mu| + 1$ while the total number of multiplications is $O((\mu - 1)2^d + 2^d) \approx O(2^d)$.

For PDT-INT, it is not possible to aggregate the leaves as in PDT-BIN. If the
client is classifying many inputs, the server must send $2^d$ ciphertexts back. If
the client is classifying only one input, then the server can use shifts to pack the
result in $\lfloor \frac{2^d}{s} \rfloor$ ciphertext(s).