Efficient decision tree training with new data structure for secure multi-party computation

Let us start with defining notation. Consider a dataset $D$ with $m$ input attributes $X_{1},\dots,X_{m}$ and an output attribute $Y$. Suppose there are $n$ samples, each sample being a pair of an input tuple $x$ and a class label $y$. Here, $x$ is an $m$-tuple, and $y$ is a value of the output attribute $Y$. The $j$-th element of $x$ represents a value of the input attribute $X_{j}$. A decision tree consists of a binary tree and some additional information. Each internal node (non-leaf node) has a condition called a test of the form $X_{j}<t$. It asks if the $j$-th element in a given input tuple is less than a threshold $t$ or not. Each edge is assigned a possible outcome of its source node’s test, that is, true or false. An edge whose assigned outcome is true (false) is called a true edge (false edge, respectively). A child node whose incoming edge is a true edge (false edge) is called a true-child node (false-child node, respectively). Each leaf node is assigned a class label called leaf label. This information is used to predict a class label for a given input tuple as follows. Starting from the root node, we repeat evaluating the test of the internal node we reach and tracing an outgoing edge that is assigned the same value as the test outcome. When we reach a leaf node, we output its leaf label as the predicted class label.

A typical decision tree training algorithm is shown in Algorithm 1. It trains a tree recursively from the root node to a leaf node in a top-down fashion. At each node, it checks if the stopping criterion is satisfied using the given training dataset $\mathcal{D}$ to determine the node type. If the stopping criterion is satisfied, the current node is set to be a leaf node. Then, it sets the most frequent class label in the dataset to the leaf label of the current node, and outputs a tree whose root is this node. If the stopping criterion is not satisfied, the current node is set as an internal node. In this case, we select a test of the form $X_{j}<t$ that gives the best data splitting with respect to a predetermined criterion, and split the training dataset $\mathcal{D}$ into $\mathcal{D}_{X_{j}<t}$ and $\mathcal{D}_{X_{j}\geq t}$ according to this test, where $\mathcal{D}_{X_{j}<t}:=\{(x,y)\in\mathcal{D}\mid x(X_{j})<t\}$ and $\mathcal{D}_{X_{j}\geq t}:=\{(x,y)\in\mathcal{D}\mid x(X_{j})\geq t\}$. It then recursively trains decision trees $\mathcal{T}_{X_{j}<t}$ and $\mathcal{T}_{X_{j}\geq t}$ with $\mathcal{D}_{X_{j}<t}$ and $\mathcal{D}_{X_{j}\geq t}$ as the training data, respectively, and sets the roots of these trees as the child nodes of the current node, and outputs a tree whose root is the current node.

We use the commonly used stopping criterion: (1) the height of the node is $h$, or (2) the dataset cannot be split further (i.e., (i) all class labels are the same, or (ii) all input tuples are the same), where $h$ is an upper bound of the tree height, which is typically given as a hyperparameter.

The size and shape of the decision tree depends on which tests are selected at the internal nodes. In general, it is desirable to make the tree as small as possible, but the problem of constructing a decision tree that minimizes the sum of the lengths of the paths from the root to each leaf is known to be NP-hard [HR76]. Therefore, we usually define a measure for goodness of local splitting and select a test that maximizes this measure.

Commonly used measures for goodness of split include the information gain used in ID3 [Qui86] and the Gini index used in CART [BFOS84]. We use the Gini index, which is also used in previous studies such as [dHSCodA14, AEV21] due to its ease of computation in MPC.

Two types of Gini indices are defined: one for a dataset and one for a dataset and a test. The Gini index for a dataset $\mathcal{D}$, which we denote by $\operatorname{\sf Gini_{\mathit{}}}(\mathcal{D})$, is defined as follows:

where $\mathcal{D}_{Y=c}:=\{(x,y)\in\mathcal{D}\mid y=c\}$ is a subset of $\mathcal{D}$ whose class label is $c$. Intuitively, the smaller $\operatorname{\sf Gini_{\mathit{}}}(\mathcal{D})$ is, the purer $\mathcal{D}$ becomes in terms of class labels.

The Gini index for a dataset $\mathcal{D}$ and a test $X_{j}<t$, which we denote by $\operatorname{\sf G_{\mathit{X_{j}<t}}}(\mathcal{D})$, is defined using $\operatorname{\sf Gini_{\mathit{}}}$ as follows:

Intuitively, the smaller $\operatorname{\sf G_{\mathit{X_{j}<t}}}(\mathcal{D})$ is, the purer each split dataset becomes (and hence the better the test is). Therefore, to find the best test for splitting a dataset $\mathcal{D}$, we compute a test $T$ that minimizes $\operatorname{\sf G_{\mathit{T}}}(\mathcal{D})$ [HKP11].

Abspoel et al. [AEV21] showed that minimization of $\operatorname{\sf G_{\mathit{X_{j}<t}}}(\mathcal{D})$ is equivalent to maximization of $\operatorname{\sf G^{\prime}_{\mathit{X_{j}<t}}}(\mathcal{D})$ defined as

where $\mathcal{D}_{X_{j}<t\wedge Y=c}:=\{(x,y)\in\mathcal{D}\mid x(X_{j})<t\wedge y=c\}$ and $\mathcal{D}_{X_{j}\geq t\wedge Y=c}:=\{(x,y)\in\mathcal{D}\mid x(X_{j})\geq t\wedge y=c\}$. We refer to it as modified Gini index and use it as a measure in our protocol.

We assume a simple ABB named $\mathcal{F}_{\rm ABB}$ over a ring $\mathbb{Z}_{M}$ for some integer $M$ as shown in Fig. 1. We denote a value referred to by a name $x$ stored in $\mathcal{F}_{\rm ABB}$ as $[\![x]\!]$. In a typical case, where $\mathcal{F}_{\rm ABB}$ is realized by a secret sharing based MPC, $[\![x]\!]$ means that $x$ is secret shared. We say a value is private if it is stored in $\mathcal{F}_{\rm ABB}$.

We identify residue classes in $\mathbb{Z}_{M}$ with their representatives in $[0,M)$. We assume $M$ is sufficiently large such that vector indices can be stored in $\mathcal{F}_{\rm ABB}$. We also assume that the number of parties $C$ is constant.

For notational simplicity, $[\![z]\!]\leftarrow\operatorname{\sf Add}([\![x]\!],[\![y]\!])$, $[\![z]\!]\leftarrow\operatorname{\sf Mul}([\![x]\!],[\![y]\!])$, $[\![z]\!]\leftarrow\operatorname{\sf EQ}([\![x]\!],[\![y]\!])$, and $[\![z]\!]\leftarrow\operatorname{\sf LT}([\![x]\!],[\![y]\!])$ are also written as $[\![z]\!]\leftarrow[\![x]\!]+[\![y]\!]$, $[\![z]\!]\leftarrow[\![x]\!]\times[\![y]\!]$, $[\![z]\!]\leftarrow([\![x]\!]\stackrel{{\scriptstyle?}}{{=}}[\![y]\!])$, and $[\![z]\!]\leftarrow([\![x]\!]\stackrel{{\scriptstyle?}}{{<}}[\![y]\!])$, respectively. Furthermore, we denote $[\![x_{1}]\!]+[\![x_{2}]\!]+\dots+[\![x_{n}]\!]$ by $\sum_{i=1}^{n}[\![x_{i}]\!]$.

We define the cost of an MPC protocol as the number of invocations of ABB operations other than linear combination of private values. That is, we assume that the parties can compute $\operatorname{\sf Add}([\![x]\!],[\![y]\!])$, $\operatorname{\sf Add}(c,[\![y]\!])$, $\operatorname{\sf Add}([\![x]\!],c)$, $\operatorname{\sf Mul}(c,[\![y]\!])$, and $\operatorname{\sf Mul}([\![x]\!],c)$ for free, where $[\![x]\!]$ and $[\![y]\!]$ are private values and $c$ is a public value. This cost models the communication complexity on a typical MPC based on a linear secret sharing scheme, in which the parties can locally compute linear combination of secret shared values. We refer to ABB operations, except for linear combinations of private values, as non-free operations.

We show known protocols that we will use as building blocks for our protocols. The protocols shown here are limited to those that can be built on $\mathcal{F}_{\rm ABB}$ for completeness. Some MPC implementations may provide the same functionality more efficiently, in which case we can use them instead of the protocols listed here to run our protocol more efficiently.

We start by defining some simple protocols.

• •

  $[\![z]\!]\leftarrow[\![x]\!]\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mu\mkern 5.0mu\mathbin{\operator@font{\textsf{OR}}}\penalty 900\mkern 5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mu[\![y]\!]$ computes logical disjunction of bits $x$ and $y$ as $[\![x]\!]+[\![y]\!]-[\![x]\!]\times[\![y]\!]$, using $O(1)$ non-free operations in $O(1)$ rounds.

• •

  $[\![z]\!]\leftarrow\lnot[\![x]\!]$ computes negation of a bit $x$ as $1-[\![x]\!]$, using no non-free operations.

• •

  $[\![z]\!]\leftarrow\operatorname{\sf IfElse}([\![c]\!],[\![t]\!],[\![f]\!])$ receives a bit $c$ and two values $t$ and $f$, and computes $t$ if $c=1$, $f$ otherwise, as $[\![f]\!]+[\![c]\!]\times([\![t]\!]-[\![f]\!])$, using $O(1)$ non-free operations in $O(1)$ rounds.

• •

  $[\![z]\!]\leftarrow\operatorname{\sf Max}([\![x]\!],[\![y]\!])$ computes the maximum value of $x$ and $y$ as $\operatorname{\sf IfElse}(([\![x]\!]\stackrel{{\scriptstyle?}}{{<}}[\![y]\!]),[\![y]\!],[\![x]\!])$, using $O(1)$ non-free operations in $O(1)$ rounds.

We require an extended $\operatorname{\sf Max}$ protocol, which we call $\operatorname{\sf VectMax}$. We let $[\![z]\!]\leftarrow\operatorname{\sf VectMax}([\![\vec{x}]\!],[\![\vec{y}]\!])$ denote the operation that computes a private value $[\![z]\!]$ such that $[\![\vec{x}]\!]$ and $[\![\vec{y}]\!]$ are private vectors of the same length $n$, $i=\mathop{\rm arg~{}max}\limits_{j\in[1,n]}\vec{x}[j]$, and $z=\vec{y}[j]$. We use the construction by Abspoel et al. [AEV21], which uses $O(n)$ non-free operations in $O(\log n)$ rounds.

We require three permutation-related protocols $\operatorname{\sf Shuffle}$, $\operatorname{\sf Apply}$, and $\operatorname{\sf Unapply}$. Let $S_{n}$ be a symmetric group on $[1,n]$. That is, $S_{n}$ is the set of all bijective functions from $[1,n]$ to $[1,n]$. A permutation is an element of $S_{n}$. Applying a permutation $\pi\in S_{n}$ to a vector $\vec{x}$ of length $n$ is the operation of rearranging $\vec{x}$ into a vector $\vec{z}$ satisfying $\vec{z}[\pi(i)]=\vec{x}[i]$ for $i\in[1,n]$. We denote this operation as $\pi(\vec{x})$. Now we define the three protocols. Let $[\![\pi]\!]\leftarrow\operatorname{\sf Shuffle}(n)$, where $n$ is an integer, denote the operation that computes $[\![\pi]\!]$, such that $\pi$ is a uniformly randomly chosen element of $S_{n}$. Let $[\![\vec{z}]\!]\leftarrow\operatorname{\sf Apply}([\![\pi]\!],[\![\vec{x}]\!])$, where $\pi\in S_{n}$ is a permutation and $\vec{x}$ is a vector of length $n$, denote the operation that computes $[\![\vec{z}]\!]$, such that $[\![\vec{z}]\!]=\pi(\vec{x})$. Let $[\![\vec{z}]\!]\leftarrow\operatorname{\sf Unapply}([\![\pi]\!],[\![\vec{x}]\!])$, where $\pi\in S_{n}$ is a permutation and $\vec{x}$ is a vector of length $n$, denote the operation that computes $[\![\vec{z}]\!]$, such that $[\![\vec{z}]\!]=\pi^{-1}(\vec{x})$. We use the construction by Falk and Ostrovsky [FO21]. In their construction, a private permutation is represented as a set of private control bits for Waksman permutation network [Wak68]. All these protocols use $O(n\log n)$ non-free operations in $O(\log n)$ rounds. Note that we do not use the $\operatorname{\sf Shuffle}$ protocol directly in our protocols, but it is required as a component of the construction of $\operatorname{\sf SortPerm}$ protocol shown below.

We also require a protocol $\operatorname{\sf SortPerm}$ to compute a permutation that stably sorts given keys. We let

denote the operation that computes $[\![\pi]\!]$ such that $\vec{x}_{1},\vec{x}_{2},\dots,\vec{x}_{k}$ are vectors of length $n$ and applying $\pi\in S_{n}$ to $((\vec{x}_{1}[1],\dots,\vec{x}_{k}[1]),\dots,(\vec{x}_{1}[n],\dots,\vec{x}_{k}[n]))$ lexicographically and stably sorts them. We use the construction by Laud and Willemson [LW14]. The protocol use $O(n\log n)$ non-free operations in $O(\log n)$ rounds. Note that we can construct the composition of private and public permutations that is needed for the $\operatorname{\sf SortPerm}$ construction, since our private permutation is a set of control bits for Waksman permutation network.

To simplify the description, we introduce a small subprotocol $\operatorname{\sf Sort}$ for sorting private vectors. We let

denote the following procedure:

1. 1.

   $[\![\pi]\!]\leftarrow\operatorname{\sf SortPerm}([\![\vec{x}_{1}]\!],\allowbreak\dots,\allowbreak[\![\vec{x}_{k}]\!])$;

2. 2.

   $[\![\vec{z}_{j}]\!]\leftarrow\operatorname{\sf Apply}(\allowbreak[\![\pi]\!],\allowbreak[\![\vec{y}_{j}]\!])$ for $j\in[1,m]$.

We sometimes use similar notation when the same operation is applied to multiple inputs. For example,

means parallel execution of $[\![z_{j}]\!]\leftarrow\operatorname{\sf IfElse}([\![c]\!],[\![t_{j}]\!],[\![f_{j}]\!])$ for $j\in[1,m]$ and

means parallel execution of $[\![z_{j}]\!]\leftarrow\operatorname{\sf VectMax}([\![\vec{x}]\!],[\![\vec{y}_{j}]\!])$ for $j\in[1,m]$.

If vectors are given for a protocol defined for scalar values, it means that the protocol is applied on an element-by-element basis. That is, $[\![\vec{z}]\!]\leftarrow[\![\vec{x}]\!]\times[\![\vec{y}]\!]$ means parallel execution of $[\![\vec{z}[i]]\!]\leftarrow[\![\vec{x}[i]]\!]\times[\![\vec{y}[i]]\!]$ for $i\in[1,n]$, and $[\![\vec{z}]\!]\leftarrow\operatorname{\sf IfElse}([\![\vec{c}]\!],[\![\vec{t}]\!],[\![\vec{f}]\!])$ means parallel execution of $[\![\vec{z}[i]]\!]\leftarrow\operatorname{\sf IfElse}([\![\vec{c}[i]]\!],[\![\vec{t}[i]]\!],[\![\vec{f}[i]]\!])$ for $i\in[1,n]$.

If some of the inputs are scalar, the same scalar values are used for all executions. For example, $[\![\vec{z}]\!]\leftarrow 2\times[\![\vec{y}]\!]$ means parallel execution of $[\![\vec{z}[i]]\!]\leftarrow 2\times[\![\vec{y}[i]]\!]$ for $i\in[1,n]$, and $[\![\vec{z}]\!]\leftarrow\operatorname{\sf IfElse}([\![c]\!],[\![\vec{t}]\!],1)$ means parallel execution of $[\![\vec{z}[i]]\!]\leftarrow\operatorname{\sf IfElse}([\![c]\!],[\![\vec{t}[i]]\!],1)$ for $i\in[1,n]$.