Practical Secure Decision Tree Learning in a
Teletreatment Application
Sebastiaan de Hoogh1 , Berry Schoenmakers2 ,Ping Chen3 , and Harm op den Akker4
1

TU Delft s.j.a.dehoogh@tudelft.nl
TU Eindhoven berry@win.tue.nl
3
KU Leuven ping.chen@cs.kuleuven.be4
Roessingh R&D and U Twente h.opdenakker@rrd.nl
2

Abstract. In this paper we develop a range of practical cryptographic
protocols for secure decision tree learning, a primary problem in privacy preserving data mining. We focus on particular variants of the wellknown ID3 algorithm allowing a high level of security and performanceat the same time. Our approach is basically to design special-purpose secure multiparty computations, hence privacy will be guaranteed as longas the honest parties form a sufficiently large quorum.
Our main ID3 protocol will ensure that the entire database of transactions remains secret except for the information leaked from the decision
tree output by the protocol. We instantiate the underlying ID3 algorithm
such that the performance of the protocol is enhanced considerably, whileat the same time limiting the information leakage from the decision tree.
Concretely, we apply a threshold for the number of transactions below
which the decision tree will consist of a single leaf—limiting information
leakage. We base the choice of the “best” predicting attribute for theroot of a decision tree on the Gini index rather than the well-known information gain based on Shannon entropy, and we develop a particularly
efficient protocol for securely finding the attribute of highest Gini index.
Moreover, we present advanced secure ID3 protocols, which generate thedecision tree as a secret output, and which allow secure lookup of predictions (even hiding the transaction for which the prediction is made). In
all cases, the resulting decision trees are of the same quality as commonly
obtained for the ID3 algorithm.
We have implemented our protocols in Python using VIFF, where theunderlying protocols are based on Shamir secret sharing. Due to a judicious use of secret indexing and masking techniques, we are able to code
the protocols in a recursive manner without any loss of efficiency. To
demonstrate practical feasibility we apply the secure ID3 protocols to an
automated health care system of a real-life rehabilitation organization.

1

Introduction

Data mining is an evolving field that attempts to extract sensible informationfrom large databases without the need of a priori hypotheses. The goal of the design of these data mining algorithms is to be simple and efficient, while providing

sensible outputs (such as reliable predictions). Applications include improving
services to the (predicted) needs of customers, and automatization of services as
we will show below. In health care, for example, automation is of significant importance, since the cost of health care is increasing due to demographic changes
and longer life expectancies.
As a motivational example, we consider the following system from [AJH10]
that describes a fully automated system, that assists rehabilitation patients.
Rehabilitation patients should maintain a certain activity level for a smoothrehabilitation process. A patient is required to carry a small device that measures
his activity. The device connects to a smartphone which provides the patientwith feedback helping him to maintain his target activity level. The goal is toprovide advice in such a way that the patient will follow it. Using data mining
techniques the device is able to learn to which (type of) messages the patientis most compliant. In order to overcome the issue of cold start, data mining isapplied to patient data of other patients so that the application can be setup insuch a way that it provides on average messages to which new patients are likely
to comply. More specifically, a decision tree is extracted from old patient datathat predicts patients compliance to certain messages in certain circumstances.
Although decision trees may not reveal individual data records, algorithms
constructing decision trees require as inputs individual data records. But thisleads to privacy issues since patient data is by its nature confidential. Privacy
preserving data mining offers a solution. Its goal is to enable data mining onlarge databases without having access to (some of) the contents. Much researchhas been done in the field of privacy preserving data mining since the works of
Agrawal & Srikant [AS00] and Lindell & Pinkas [LP00]. The solutions can beclassified as follows, each having its own advantages and disadvantages [MGA12]:
Anonymization based, Pertubation based, Randomized Response based, Condensation Approach based, and Cryptography based.
Our cryptography based solution will focus on the generation of decision
trees using ID3. The cryptography based solutions provide provable security inthe framework of multiparty computation, but comes at the cost of time consuming protocols. There are many solutions in the literature that apply multiparty
computation techniques to securely evaluate ID3, such as [LP00,VCKP08,DZ02],[XHLS05,SM08,WXSY06,MD08]. All of them require that the database is partitioned in some special way among the computing parties.
In this paper we provide a cryptographic solution for extracting decision
trees using ID3 where the database is not partitioned over the parties. In fact,
no party is required to have any knowledge of a single entry of the database. We
assume that there are n ≥ 3 parties that wish to evaluate ID3 on a database
while having no access to its individual records. Together, they will learn thedesired decision tree and nothing more than what can be learned from the tree.
We assume that the servers are semi-honest and no more than n/2 servers will
collude trying to learn additional information.
In contrast to existing secure solutions we assume that no party has knowledge of any record of the database. Nevertheless, the resulting protocols performwell due to the minimal overhead imposed by our approach. In addition, ourprotocols are designed such that the implementation in VIFF is similar to astraightforward implementation of the original (unsecured) ID3 algorithm. Finally, we show that our protocols are applicable in practice by providing therunning times of the protocols on the database used in the rehabilitation application of [AJH10].
1.1

Related Work

Privacy preserving data mining using secure multiparty computation for solving
real-life problems is first demonstrated in [BTW12], where a secure data aggregation system was built for jointly collecting and analyzing financial data froma number of Estonian ICT companies. The application was deployed in the beginning of 2011 and is still in continuous use. However, their data analysis arelimited to basic data mining operations, such as sorting and filtering.
Many results on secure decision tree learning using multiparty computation,
however, can be found in the literature. We will briefly describe some of thembelow.
The first results on secure generation of decision trees using multiparty computation is from Lindell and Pinkas in 2000. In [LP00] they provide protocols
for secure ID3, where the database is horizontally partitioned over two parties.
They show how to efficiently compute the entropy based information gain byproviding two party protocols for computing x log x. Their protocols are basedon garbled circuits [Yao86].
Protocols for securely evaluating ID3 over horizontally partitioned data overmore than two parties are given in [XHLS05,SM08]. The former provide multiparty protocols computing the entropy based information gain based using
threshold homomorphic encryption and the latter applies similar protocols tocompute the information gain using the Gini index instead. In the same fashion[MD08] provides protocols for both vertically and horizontally partitioned datausing the Gini index, but with a trusted server to provide the parties with shares
instead of using homomorphic encryption.
In [DZ02] protocols for secure ID3 over vertically partitioned data over twoparties are described and in [WXSY06] protocols over vertically partitioned dataover more than two parties are described. Both solutions assume that all parties
have the class attribute and show how to gain efficiency by disclosing additional
information on the database. These issues have been addressed by [VCKP08],
where a secure set of protocols for vertically partitioned data over more than
two parties is discussed without disclosing any additional information and where
not all parties have the class attribute.

2

The ID3 Algorithm

Decision tree learning is a basic concept in data mining. A popular algorithm
is the Iterative Dichotomizer 3 (ID3) from [Qui86] that extracts a decision tree

Algorithm 2.1 ID3(T, R)
1: i∗ = arg maxi |T ∩ S0,i |2: if R = ∅ or |T | ≤ |T | or |T ∩ S0,i∗ | = |T | then3:
return hci∗ i
4: else5:k∗ = arg maxk f (T, Ak )6:
return hAk∗ , {ID3(T ∩ Sk∗ ,j , R \ {Ak∗ })}j i

from a dataset viewed as a table from a structured database. Each row is called atransaction and each column corresponds to an attribute. One of the attributes
is the target attribute or class attribute, which one wants to predict for new
transactions given values for the other attributes. For example, in the teletreatment scenario, the attributes include the gender and age of a patient as well as
specific attributes such as the advice given to the patient (e.g., “ go for a walkright now”) and the weather conditions; the class attribute indicates whether or
not the patient is compliant with the advice given.
We will use the following notation. Consider database T with attributes
A = {Ak }. Let C = A0 denote the class attribute. For each Ak ∈ A, let {akj }be the set of possible values for attribute Ak and let {ci } = {a0i } be the set of
possible values for the class attribute C. For any t ∈ T , we denote by t(Ak ) thevalue of attribute Ak in transaction t. Let Sk,j = {t ∈ T : t(Ak ) = akj } denotethe set of transactions in T for which attribute Ak has the value akj . Note that
{Sk,j }j forms a partition of T , which we will call the partition of T according
to Ak .
The overall approach of ID3 is to recursively choose the attribute that bestclassifies the transactions and partition the database according to the valuesof that attribute, see Algorithm 2.1. ID3 takes as input a set of transactions
T ⊆ T together with a set of non-class attributes R ⊆ A \ {C} over which thedecision tree is built. First the algorithm checks whether some stopping criterion
is satisfied. There are many common stopping criteria [RM05], each having its
own merits. We use the following three stopping criteria. Firstly, if no further
partition is possible, i.e., if R = ∅. Secondly, if the class attribute takes on only
one value, i.e., if |S0,i | = |T | for some i. And, finally, if the number of transactions
in a partition is relatively small, i.e., if |T |/|T | ≤ , for some small . In all cases
when a stopping criterion is satisfied, ID3 returns a leaf node containing thevalue for C that occurs most frequently in the transactions in T .
If none of the stopping criteria is satisfied, ID3 continues by choosing some
attribute Ak∗ ∈ R and returning a tree with root Ak∗ and a subtree generated
recursively as ID3(T ∩ Sk∗ ,j , R \ {Ak∗ }) for all possible values {ak∗ j } for attribute Ak∗ . The main task is to determine which attribute Ak ∈ R classifies
the transactions in T best. This relies on a measure for goodness of split. In
practice, the goodness of split is represented by some function f for which thevalue {f (T, Ak )} is maximal if Ak classifies the transactions in T best. We will
discuss two common choices for f in the next section.

2.1

Two Common Splitting Rules

We will use two common splitting rules for generating decision trees, based on
entropy and based on the Gini index, respectively. See, e.g., [Bre96].
The goodness of split based on entropy was originally used in the ID3 algorithm [Qui86]. The amount of information needed to identify the class of atransaction in a set T ⊆ T is given by the entropy:
X |T ∩ S0,i ||T ∩ S0,i |
log.
H(T ) = −
|T
|
|T |
i
Similarly, the amount of information needed to determine the class of a transaction in a set T given attribute Ak is given by the conditional entropy:
X |T ∩ Sk,j |H(T ∩ Sk,j ).
H(T |Ak ) =|T |j
ID3 is a greedy algorithm that recursively selects the attribute with maximal
information gain, which is defined by
IG(Ak ) = H(T ) − H(T |Ak ).
The best split is defined as the partition of T according to attribute Ak with thehighest information gain, or equivalently, with minimal H(T |Ak ).
Computing a logarithm securely is in general a complex task and requires
specialized protocols to be applicable in practice [LP00]. Instead of computing
a logarithm securely we choose to go a different well known splitting measure
to avoid secure computation of logarithms. Our protocols will be based on theGini index, which is another common splitting measure that can be implemented
using simple arithmetic only.
The Gini index measures the probability of incorrectly classifying transactions in T if classification is done randomly according to the distribution of theclass values in T [RS00], and is given by
X  |T ∩ S0,i | 2
G(T ) = 1 −.
|T |i
Similarly, the estimated conditional probability of incorrectly classifying transactions in T given attribute Ak is given by
X |T ∩ Sk,j |G(T |Ak ) =G(T ∩ Sk,j ).
|T |jOne can show that 0 ≤ G(T |Ak ) ≤ G(T ), such that
GG(Ak ) = G(T ) − G(T |Ak )defines the reduction of incorrect classifications in T given attribute Ak . Again,
the best split is defined as the partition T according to attribute Ak with thehighest Gini gain, or equivalently, with minimal G(T |Ak ).

3

Secure Computation Framework

We develop our protocols in a generic framework for secure computation. For
simplicity, we assume that all secret values are signed integers ranging over
Zp = {−bp/2c, . . . , −1, 0, 1, . . . , bp/2c} for a sufficiently large prime p. As a concrete instantiation of a secure computation framework we use the Virtually Ideal
Functionality Framework (VIFF), basically using Shamir secret sharing over Zp
to provide n-party computation secure against passive adversaries. Any secretvalue in Zp is thus represented by n shares in Zp , each party holding one share.
We assume that we have efficient integer arithmetic for secret values. As
usual, we take the cost of one multiplication x ∗ y as our basic unit of work. The
cost of one addition x + y or subtraction x − y is considered negligibly small
compared to the cost of one multiplication. Exact division (that is, x/y where x
is an integral multiple of y) costs about two multiplications.
Secure integer equality x = y and secure integer comparison x ≤ y arealso assumed to be available. Both of these operations yield a secret bit value,with 0 representing false and 1 representing true, and are at least an order ofmagnitude more expensive than secure multiplication. In our protocols, we also
use the operation arg max to securely find a location of the maximum value ina given list of N secret values, basically using N − 1 secure comparisons.
Furthermore, we will assume that secret subsets of a given finite (ordered)set V are represented as secret bit vectors of length |V |. For simplicity, we will
identify a secret set A ⊆ V with the bit vector representing it. So, for instance, tosecurely compute |A| it suffices to sum the entries of the bit vector representing
A, hence this operation is almost for free. Similarly, the disjoint union A ]B is obtained securely by taking the entrywise sum A + B of the bit vectors
representing A and B, and the symmetric difference A \ B for B ⊆ A is obtainedby taking the entrywise difference A − B. Moreover, we see that the intersection
A ∩ B is obtained securely by taking the entrywise product A ? B of the bit
vectors representing A and B (at the cost of |V | secure multiplications). Finally,
we note that frequently we need to compute only the size of the intersection|A ∩ B|, for which it suffices to take the dot product A · B.
We assume that the dot product can be computed securely at the cost of
one or at most a few secure multiplications, independent of the length of thevectors (see, e.g., [CdH10], using similar ideas as in [CDI05]). More precisely,
the communication cost of a secure dot product is independent of the length ofthe vectors (whereas the computational cost is still linear in the length of thevectors). The communication cost is the dominating cost factor in a framework
such as VIFF. By using dot products judiciously we are able to reduce the total
cost of our protocols considerably.

4

Secure ID3 Protocol

We present a secure multiparty protocol based on the recursive ID3 algorithm
presented in Sect. 2. The goal is to completely hide the contents of the transac-

Protocol 4.1 SID3(T, R)
1: foreach i do
2:
si = T · S0,i
3: i∗ = arg maxi si
4: if R = ∅ or (|T | ≤ |T | or si∗ = |T |) then5:
return hci∗ i
6: else7:
foreach i do
8:
Ui = T ? S0,i9:
foreach k s.t. Ak ∈ R do
10:
foreach j do
11:foreach i do
12:
xij =PUi · Sk,j13:
yj =Qα i xij + 1
14:
Dk = j yj
e k = Dk P (P x2ij )/yj ÷ Dk
15:
G
j

16:
17:

i

ek
k∗ = arg maxk G
return hAk∗ , {SID3(T ? Sk∗ ,j , R \ {Ak∗ })}j i

tional database except for the information leaked from the decision tree output
by the protocol.
Our recursive SID3 protocol is described below, see Protocol 4.1. Given a
database containing a set of transactions T with attributes in A, a decision tree
is obtained by the call SID3(T , A \ {C}), where C = A0 is the class attribute.
In general, the recursive protocol SID3(T, R) takes sets T ⊆ T and R ⊆ A \ {C}
as inputs. The decision tree output by the protocol is public, and therefore set
R is not secret either. Set T on the other hand is a secret input, represented asa secret bit vector of length |T |.
We will now give a step-by-step description of the SID3 protocol, assumingthat the sets Sk,j of transactions for which attribute Ak has value akj are given
as secret bit vectors, all of length |T |.
In lines 1–3 we determine the most frequently occurring class value ci∗ . First,
si is computed as the number of transactions in T with class value ci by taking
the dot product of the bit vectors representing T and S0,i , respectively. Subsequently, a class value ci∗ such that si∗ is maximal is determined. The value ofi∗ is public, but no further information on the secret values si is leaked.
Lines 4–5 cover the cases in which the decision tree consists of a single nodecontaining value ci∗ . Whether R = ∅ holds can be evaluated quickly as R is notsecret. If R 6= ∅ (which is usually the case) the test ‘|T | ≤ |T | or si∗ = |T |’is evaluated securely as follows. Input T is given as a secret bit vector, henceby summing its entries |T | is obtained as a secret value. The value si∗ is secretas well. Subsequently, using a secure comparison, a secure equality test, and asecure ‘or’, only the value of the test is revealed. This means, in particular, that
if the test evaluates to true, it remains hidden whether |T | ≤ |T | holds, whethersi∗ = |T | holds, or whether both conditions hold.

The remaining lines cover the case of a composite decision tree. Lines 7–15
e k which are used to determine ancover the computation of the secret values G
attribute Ak∗ of highest Gini index in line 16. The resulting decision tree isthen computed in line 17, with Ak∗ as root value, and with a decision tree fortransaction set T ∩ Sk∗ ,j as jth subtree.
e k are used to approximate the quantities Gk sufficiently well,
The quantities G
where
P
2
X
i |T ∩ S0,i ∩ Sk,j |.
Gk =|T ∩ Sk,j |j s.t. |T ∩Sk,j |6=0

It can be easily seen that finding an attribute of highest Gini index corresponds
to maximizing Gk over Ak ∈ R. However, secure computation of Gk requiresthat the indices j for which |T ∩ Sk,j | = 0 are not revealed. To this end, we
will replace the nonnegative values |T ∩ Sk,j | by positive values yj such that thee k is sufficiently similar to Gk , where
resulting quantity GP
X i x2ij
e
.
Gk =
yj
j
Here, entries xij = |T ∩S0,i ∩Sk,j | form a contingency table, and we set yj = α|T ∩Sk,j | + 1 for some sufficiently large integer constant α ≥ 1. In our experiments
in Sect. 6 it turns out that α = 8 suffices, as compared to the results for thealternative of setting yj = |T ∩ Sk,j | if |T ∩ Sk,j | > 0 and yj = 1 otherwise—ine k = Gk . We prefer to use yj = α|T ∩ Sk,j | + 1 aswhich case we have in fact G
secure evaluation of the alternative for yj requires a secure equality test, which
has a big impact on the performance; a disadvantage of this choice is that weneed to increase the size of the field Zp , as can be seen from the bit lengths usedin Table 6.1.
For each attribute Ak ∈ R, the secret values xij and yj are computed efficiently as follows. First, the bit vectors Ui representing the intersections T ∩ S0,iare computed as entrywise products of the bit vectors representing T and S0,i .
Then each xij is obtained as the dot productP of the bit vector Ui and the bit
vector representing Sk,j , and we set yj = α i xij + 1.
Finally, to avoid secure arithmetic over rational numbers, we take the comek :mon denominator of all terms in the sum G
PP 2 Q
xij
yl
j i
l6=j
ek =
Q
G
.
yl
l

e k are integers, and we canThis way, both the numerator and denominator of Gemaximize Gk using integer arithmetic only, as x ÷ y ≤ x0 ÷ y 0 is equivalent toxy 0 ≤ x0 y for y, y 0 > 0. The test xy 0 ≤ x0 y is further optimized by actually
evaluating (x, y) · (y 0 , −x0 ) ≤ 0, hencePusing a single dot product instead of two
multiplications. Of course, the terms x2ij are also each computed using a single
idot product.

In the actual code used in the experiments of Sect.P6 we have applied somefurther optimizations throughout. For instance, since i Ui = T , one can save
one entrywise product in lines 7–8, which speeds up this part by a factor of
two in case the class attribute takes on two values only. Similarly, one entrywise
product can be saved in line 17.

5

Secure ID3 in Other Settings

We show how minor changes to SID3 allow efficient generation of secret decision trees. In addition, we show that if the database is horizontally partitioned
between the parties, then minor changes to SID3 allow generation of a publicdecision tree with communication complexity that is independent of the numberof transactions in the database.
5.1

Secret Output and Secret Prediction

There are some serious restrictions when hiding the resulting decision tree.
Firstly, when any third party is allowed to ask for decisions from the secrettree, it may be able to reconstruct or build an equivalent tree by querying thetree often enough. A strategy could be, for example, to generate its own databaseby querying the secret tree, and apply ID3 to the generated database.
Secondly, not revealing any information about the decision tree requires hiding the shape of the tree. This would lead to a tree of worst case size, which isexponential. Indeed, a database with m attributes each taking possibly ` values
has at most `m leaves. Moreover, in this case it is useless to apply ID3: one
could simply compute the best class for all possible `m paths. The resulting tree
is of maximum size as required and can be computed much more efficiently byjust partitioning the database into all possible paths along the attribute values.
More precisely, one would run SID3S(T, m, ⊥), where ⊥ indicates that there isnothing to output when the original database T is empty, see Protocol 5.1.
In line 4 of SID3S the index i∗ of the most frequent class value in T is computed similar to line 3 of SID3. However, i∗ should not be revealed. Therefore,
we use its secret unary representation, which is a vector containing zeros only,
except at position i∗ , where it contains a 1. Thus, to hide i∗ we apply a variantof arg maxi that returns a length |{cj }| secret unary representation of the valuei∗ , say i∗ . Then ci∗ can be computed securely and without interaction by thedot product (c1 , . . . , c|C| ) · i∗ , since {ci } is public. This is applied in lines 1–4 of
SID3S.
As a tradeoff between security and efficiency one could choose to reveal some
information on the shape of the tree, e.g., the length of the paths. This avoids
exponential growth of the tree. In this case we need to take care of the following
two things: Firstly, we cannot reveal the attribute representing the next best split
and leaf values as this would leak the entire decision tree. Secondly, we should
ensure that all attributes take the same number of values. Indeed, one could
learn information about the attribute label of each non-leaf node by observing

Protocol 5.1 SID3S(T, k, c)
1: if |T | =6 0 then2:
foreach i do
3:
si = T · S0,i4:i∗ = arg maxi si
5:c = ci∗6: if k = 0 then7:
return hci
8: else9:
return hAk , {SID3S(T ? Sk,j , k − 1, c)}j i

the number of children it has. The latter can be ensured simply by adding dummy
values to each attribute.
Thus, ID3 is applied as before, except for opening the values of the leaves
and opening the values of the next best split. Not opening the values of the next
best split leads to a bit more complicated partitioning of the tree. Fore example,
we need to prevent a selected attribute to be selected again in some subsequent
call to ID3. Protocol 5.2 computes the secret decision tree for T and reveals only
the depth of each path. We will discuss line by line the changes with respect to
SID3.
Firstly, as we observed in SID3S, the index i∗ of the most frequent class value
in T is computed similar to line 3 of SID3, but should not be revealed. So, inlines 1–5 of SID3T we again apply the variant of arg maxi that returns a length|{cj }| secret unary representation of the value i∗ , such that ci∗ can be computed
securely and without interaction using a dot product.
Secondly, instead of R ⊆ A being public it should be secret to avoid revealing
which attribute is selected in previous recursions. This will affect lines 4, 16,
and 17 of SID3. We let R be represented by a secret bit vector, where its kth
entry is equal to [Ak ∈ R] with [true] = 1 and [false] = 0.
In line 4 of SID3 one checks whether R = ∅. However, since R is secretit cannot be used to perform this check. To check whether R = ∅ without
communication, observe that R = ∅ if and only if the current path is maximal,
or, equivalently, when the recursive call to ID3 is in depth |A| − 1. Therefore,
we use a public counter r that is initialized to |A| − 1 and decreases by one after
each recursive call to ID3. The condition R = ∅ is replaced by r = 0, see line 4of SID3T.
Line 16 of SID3 computes and reveals the attribute with the best Gini index among the available attributes given by R. To ensure selection among theavailable attributes in the secret set R we proceed as follows. First we come k for all k, and then we choose attribute Ak∗ obliviously such thatpute Ge
Gk∗ − [Ak 6∈ R] is maximal, see line 16 of SID3T. This ensures selection ofe k that has not been selected already. Indeed, if
an attribute with maximal G
attribute Ak has already been selected then its value in all transactions con-Protocol 5.2 SID3T(T, R, r)
1: foreach i do
2:
si = T · S0,i
3: i∗ = arg maxi si
4: if r = 0 or (|T | ≤ |T | or si∗ = |T |) then5:
return hci∗ i
6: else7:
foreach i do
8:
Ui = T ? S0,i9:
foreach k do
10:foreach j do
11:foreach i do
12:
xij =PUi · Sk,j13:
yj =Qα i xij + 1
14:
Dk = j yj
e k = Dk P (P x2ij )/yj ÷ Dk
15:
G
j

16:
17:

i

e k − [Ak 6∈ R]
k∗ = arg maxk G
return hAk∗ , {SID3T(T ? Sk∗ ,j , R \ {Ak∗ }, r − 1)}j i

e k = 0 andsidered by successive recursive calls to ID3 is constant, so that Gee
Gk − [Ak 6∈ R] = −1 < 0 ≤ Gv − [Av 6∈ R] for any available attribute Av .
Since Ak∗ should remain secret, in line 16 we apply again the variant ofarg maxi that returns a length |A − 1| secret unary representation of the valuek ∗ , say k∗ . We let Ak∗ be represented by the secret unary representation of its
index k ∗ . To update T by T ? Sk∗ ,j , in line 17, we first need to compute Sk∗ ,j ,which is done using the following dot productSk∗ ,j = S1,j , S2,j , . . . , S|A|−1,j · k∗ ,which is interactive, since both Si,j and k∗ are secret.
Finally, in line 17 of SID3, R \ {k ∗ } can be easily computed since R nor Ak∗
are secret. Updating the secret representation of R in SID3T can be done without
interaction by the entrywise subtraction by the secret unary representation ofk ∗ . Indeed, R \ {Ak∗ } is equivalent to setting the bit [Ak∗ ∈ R] to zero. Let k∗ be
the secret unary representation of k ∗ then the entrywise subtraction of the secret
representation of R by k∗ will only affect the k ∗ th entry of the secret bit vector
for R, where it becomes [Ak∗ ∈ R] − 1. Since Ak∗ is selected it was available
so that [Ak∗ ∈ R] = 1, and subtraction by one will result in [Ak∗ ∈ R] = 0 as
required in the next recursive call.
With respect to complexity, selecting the next best attribute requires |A| − 2
secure comparisons in each recursive call as opposed to only |R| − 1 secure comparisons in SID3. Computing Sk∗ ,j requires `|T | secure dot products in addition
to the `|T | multiplications for computing T ? Sk∗ ,j .
Protocol 5.3 computes the class from a secret tree B, given a secret transaction t as follows. Let t be a secret transaction, where its kth entry is a unary
representation of the index of the value t(Ak ). So the jth value of the kth entry

Protocol 5.3 Class(t, B)
1: if B = hci then2:
return c
3: else4:
m = t · BP15:
returnj mj · Class(t, B2j )of t is equal to 1 if t(Ak ) = akj and it is equal to 0 otherwise. Note that B = hci
if B is a single leaf node and B = hB1 , B2 i = hAk , (B21 , . . . , B2` )i otherwise,
where B2j is the resulting tree of SID3T(Sk,j , R \ Ak , |A| − 2). Recall that Ak is
secret and is represented by the length |A| − 1 secret unary representation of its
index k.
P
If B = hci, then t gets class c, else t gets class j (t · B1 )j Class(t, B2j ).

5.2

Horizontally Partitioned Database

If the database T is horizontally partitioned and if the resulting tree is madepublic, then there is no need to securely split the database by computing amask. Given a set of transactions, each party can locally compute any partition
of T according to some attribute. Hence, the communication complexity will be
independent of |T |, which is a significant improvement in practice where |T | isrelatively large compared to |A|. Checking the stopping criteria and computing
the Gini index, however, requires knowledge of the entire database and requires
interaction.
Let {Tz } be the partition of T such that each Pz owns Tz . Observe that{Sz:k,j }, where Sz:k,j = {t ∈ Tz : t(Ak ) = akj }, is a partition of Sk,j where
each block Sz:k,j can be computed by party Pz locally. Furthermore, if {Tz } isa horizontal partition of some T ⊆ T , then {Tz ∩ Sz:k,j } forms a partition of
T ∩ Sk,j . To jointly compute |T ∩ Sk,j |, each party Pz computes first |Tz ∩ Sz:k,j |and shares the result with
P all other parties. Then all parties locally computeshares of |T ∩ Sk,j | =z |Tz ∩ Sz:k,j | by summing the received shares. Thisaffects lines 2 and 12 in SID3.
Protocol 5.4 shows how to securely compute the decision tree for a horizontally partitioned T . With id we denote the identity of the party running theprotocol.
With respect to efficiency, computing the entries of the contingency table
xij requires each party to share their local contingency table. With respect tocommunication, this is equivalent to performing |A−1||{cj }| dot products, whichis the same as for the computation of the contingency table in ID3. However,splitting the database requires no interaction anymore. This saves O(|T |) secure
multiplications. In fact, the communication complexity of the resulting protocol
is independent of |T |.

Protocol 5.4 SID3P(T, R)
1: foreach i do2:
sid:i = Share(Tz · Sz:0,i )
3:foreach Pz 6= Pid do
4:
Receive(s
z:i )
P
5:
si = z sz:i
6: i∗ = arg maxi si
7: if R = ∅ or (|T | ≤ |T | or si∗ = |T |) then8:
return hci∗ i
9: else10:
foreach i do
11:
Uid:i = Tz ? Sid:0,i12:
foreach k s.t. Ak ∈ R do
13:
foreach i do
14:
foreach j do
15:
xid:ij = Share(Uid:i · Sid:k,j )16:
foreach j do
17:
foreach i do18:
foreach Pz 6= Pid do
19:
Receive(xz:ij )
P20:
xij =P z xz:ij
21:
yj =Qα i xij + 1
22:
Dk = j yj
e k = Dk P (P x2ij )/yj ÷ Dk
23:
G
j

i

24:
25:

ek
k∗ = arg maxk G
return hAk∗ , {SID3P(T ? Sk∗ ,j , R \ {Ak })}j i

6

Performance Results

To analyze the performance of our protocols in a practical setting, we have built
applications using the Virtual Ideal Functionality Framework (VIFF). VIFF isa general software framework for doing secure multiparty computation [Gei10],which provides researchers and programmers with the basic building blocks (orsub-protocols) as APIs to allow rapid prototyping of new protocols and building
practical applications. For improved efficiency, we use the ‘boost’ extension to
VIFF, which greatly improves the performance of VIFF applications [Kel10]. The
comparison protocols applied are the probabilistic equality test from [NO07] andthe integer comparison from [EFG+ 09].
We run the protocols for three players on different network ports on a 64bit Windows 7 PC, with Intel Core i5-3470 CPU @3.20GHz (2 cores, 4 hyperthreads), 16GB memory. Even on such a moderately fast PC and even though theperformance overhead of VIFF is intrinsically large, the absolute timings range
from a few seconds to a few minutes only, showing the practical feasibility of
our approach. A marked advantage of VIFF specifically for implementing secure
ID3 protocols is the fact scheduling is done dynamically at runtime, dependingon the shape of the decision tree as it develops.

Table 6.1: Performance results
Data
Size Measure bit length SID3 SID3T SID3P
ek
SPECT 267
41
27s
43s
24s
G
Gk
32
57s
88s
54s
ek
Scale
625
G
76
9s
17s
7s
Gk
49
11s
17s
8s
ek
1728
95
18s
29s
10s
Car
G
Gk
74
20s
33s
12s
ek
G
69
46s 104s
26s
KRKPA7 3196
Gk57
73s 142s
50s
ek[AJH10] 2196
G
78
68s 185s
40s
Gk
63
96s 255s
69s

We have tested the performance of our ID3 protocols with the benchmarking
data set from the UCI Machine Learning Repository [FA10] and with the data
set from [AJH10]. Table 6.1 shows the performance results of our protocols. The
threshold for early stopping is set to  = 5% of the data set. The parametere k is set to α = 8, which is sufficiently large to ensure thatfor computing G
the protocols return basically the same decision trees as obtained using Gk (thedecision trees are identical for all data sets, except for SPECT, where some minor
differences are visible).
Note that the required size modulus p of the prime field is affected by α.
Indeed, the size of each xij is increased by log2 (α) so that the size yj (Line 13
of SID3) is increased by at most ` log2 (α) bits, where ` denotes the maximum
number of values an attribute from A takes. This in turn affects the communication complexity of the integer comparisons which are proportional to thegiven bit length of the inputs. The bit length b in Table 6.1 denotes the numberof bits required to simulate integer arithmetic over Zp . In our experiments, thestatistical security parameter is set to 30 bits. As a consequence the prime p ischosen such that log2 p ≈ b + 31.

Acknowledgements
This work was supported by the Dutch national program COMMIT.

References
AJH10.

AS00.

H. op den Akker, V.M. Jones, and H.J. Hermens. Predicting feedback
compliance in a teletreatment application. In Proceedings of ISABEL 2010:
the 3rd International Symposium on Applied Sciences in Biomedical andCommunication Technologies, Rome, Italy, 2010.
R. Agrawal and R. Srikant. Privacy-preserving data mining. In Proceedingsof the 2000 ACM SIGMOD International Conference on Management of
Data, SIGMOD 2000, pages 439–450, New York, NY, USA, 2000. ACM.

Bre96.

L. Breiman. Technical note: Some properties of splitting criteria. Machine
Learning, 24:41–47, 1996.
BTW12. Dan Bogdanov, Riivo Talviste, and Jan Willemson. Deploying secure multiparty computation for financial data analysis. In Proceedings of the Sixteenth International Conference on Financial Cryptography and Data Security, FC ’12, 2012.
CdH10.
Octavian Catrina and Sebastiaan de Hoogh. Secure multiparty linear programming using fixed-point arithmetic. In Proceedings of the 15th European
conference on Research in computer security, ESORICS’10, pages 134–150,
2010.
CDI05.
R. Cramer, I. Damgård, and Y. Ishai. Share conversion, pseudorandom
secret-sharing and applications to secure computation. In Proceedings of
the Second international conference on Theory of Cryptography, TCC’05,
pages 342–362, Berlin, Heidelberg, 2005. Springer-Verlag.
DZ02.
Wenliang Du and Zhijun Zhan. Building decision tree classifier on private
data. In Proceedings of the IEEE international conference on Privacy, security and data mining-Volume 14, pages 1–8. Australian Computer Society,
Inc., 2002.
EFG+ 09. Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, and T. Toft.
Privacy-preserving face recognition. In Proceedings of the 9th International
Symposium on Privacy Enhancing Technologies, PETS ’09, pages 235–253,
Berlin, Heidelberg, 2009. Springer-Verlag.
FA10.
A. Frank and A. Asuncion. UCI machine learning repository, 2010.
Gei10.
Martin Geisler. Cryptographic Protocols: Theory and Implementation. PhD
thesis, Aarhus University, Denmark, February 2010.
Kel10.
Marcel Keller. VIFF boost extension. http://lists.viff.dk/pipermail/viff-devel-viff.dk/2010-August/000847.html, 2010.
LP00.
Yehuda Lindell and Benny Pinkas. Privacy preserving data mining. In
Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’00, pages 36–54, London, UK, UK, 2000.
Springer-Verlag.
MD08.
Qingkai Ma and Ping Deng. Secure multi-party protocols for privacy preserving data mining. In Yingshu Li, DungT. Huynh, SajalK. Das, andDing-Zhu Du, editors, Wireless Algorithms, Systems, and Applications, volume 5258 of Lecture Notes in Computer Science, pages 526–537. Springer
Berlin Heidelberg, 2008.
MGA12. Majid Bashir Malik, M. Asger Ghazi, and Rashid Ali. Privacy preserving
data mining techniques: Current scenario and future prospects. In Proceedings of the 2012 Third International Conference on Computer and Communication Technology, ICCCT ’12, pages 26–32, Washington, DC, USA,2012. IEEE Computer Society.
NO07.
T. Nishide and K. Ohta. Multiparty computation for interval, equality, andcomparison without bit-decomposition protocol. In Proceedings of the 10thinternational conference on Practice and theory in public-key cryptography,
PKC’07, pages 343–360, Berlin, Heidelberg, 2007. Springer-Verlag.
Qui86.
J. R. Quinlan. Induction of decision trees. Mach. Learn., 1(1):81–106,
March 1986.
RM05.
Lior Rokach and Oded Maimon. Decision trees. In The Data Mining andKnowledge Discovery Handbook, pages 165–192. Springer US, 2005.

RS00.

Laura E. Raileanu and Kilian Stoffel. Theoretical comparison between theGini index and information gain criteria. Annals of Mathematics and Artificial Intelligence, 41:77–93, 2000.
SM08.
Saeed Samet and Ali Miri. Privacy preserving ID3 using Gini index overhorizontally partitioned data. In Computer Systems and Applications, 2008.
AICCSA 2008. IEEE/ACS International Conference on, pages 645–651.
IEEE, 2008.
VCKP08. Jaideep Vaidya, Chris Clifton, Murat Kantarcıoğlu, and A. Scott Patterson.
Privacy-preserving decision trees over vertically partitioned data. ACM
Trans. Knowl. Discov. Data, 2(3):14:1–14:27, October 2008.
WXSY06. Ke Wang, Yabo Xu, Rong She, and Philip S Yu. Classification spanningprivate databases. In PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, volume 21, page 293. Menlo
Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.
XHLS05. Ming-Jun Xiao, Liu-Sheng Huang, Yong-Long Luo, and Hong Shen. Privacy
preserving ID3 algorithm over horizontally partitioned data. In Parallel andDistributed Computing, Applications and Technologies, 2005. PDCAT 2005.
Sixth International Conference on, pages 239–243. IEEE, 2005.
Yao86.
A. Yao. How to generate and exchange secrets. In Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS ’86), pages 162–167.
IEEE Computer Society, 1986.