On the Gini-impurity Preservation For Privacy Random Forests
Authors: XinRan Xie
Man-Jie Yuan
Xuetong Bai
Wei Gao
Zhi-Hua Zhou
Venue: NeurIPS 2023 spotlight (2023)
Keywords: classification
random forests
privacy-preserving machine learng
data encrytion

Abstract: Random forests have been one successful ensemble algorithms in machine learning. Various techniques have been utilized to preserve the privacy of random forests from anonymization, differential privacy, homomorphic encryption, etc., whereas it rarely takes into account some crucial ingredients of learning algorithm. This work presents a new encryption to preserve data's Gini impurity, which plays a crucial role during the construction of random forests. Our basic idea is to modify the structure of binary search tree to store several examples in each node,  and encrypt data features by incorporating label and order information. Theoretically, we prove that our scheme preserves the minimum Gini impurity in ciphertexts without decrypting, and present the security guarantee for encryption. For random forests, we encrypt data features based on our Gini-impurity-preserving scheme, and take the homomorphic encryption scheme CKKS to encrypt data labels  due to their importance and privacy. We  conduct extensive experiments to show the effectiveness, efficiency and security of our proposed method.

On the Gini-impurity Preservation For Privacy Random Forests
Xin-Ran Xie, Man-Jie Yuan, Xue-Tong Bai, Wei Gao, Zhi-Hua Zhou National Key Laboratory for Novel Software Technology. Nanjing University, China School of Artificial Intelligence, Nanjing University, China {xiexr, , yuanmj, baixt, gaow, (hlouzh)&laadae nju. ajj.edu..co edu. cn
Abstract
Random forests have been one of the successful ensemble algorithms in machine learning. Various techniques have been utilized to preserve the privacy of random forests, such as anonymization, differential privacy, homomorphic encryption, etc. This work takes one step towards data encryption by incorporating some crucial ingredients of learning algorithm. Specifically, we develop new encryption preserve data's 's Gini impurity, which plays an important role during the construction of random forests. The basic idea is to modify the structure of binary search tree to store several examples in each node, and encrypt the data features by incorporating label and order information. Theoretically, preserve the minimum Gini impurity in ciphertexts without decrypting, and we also present the security guarantee for encryption. For random forests, encrypt data features based on our Gini-impurity peppuuttyypreeevinng scheme, and take the homomorphic encryption scheme CKKS encrypt data labels owing their importance and privacy. We finally present extensive empirical studies to validate the effectiveness, efficiency and security of proposed method.
scheme is proven
Introduction
From the pioneer work [1], random forests have been one successful ensemble algorithm [2-4], with diverse applications such ecology [5], computational biology [6], objection recognition [7], remote sensing [8], computer vision [9], etc. The basic idea is to construct large number of random trees individually and make prediction based on an average of their predictions. Numerous variants of random forests have been developed to improve performance under different settings [10-22], as well theoretical understandings on the success of random forests [21, 23-27J. The splitting criterion, such as Gini impurity and information gain, has been one of the most important ingredient during the construction of random forests [1, 28].
Various techniques have been adopted to preserve the privacy of random forests, especially for sensitive tasks such medical diagnosis, financial predictions, and For example, differential privacy [29] has been successfully applied to preserve the privacy random forests [30, 31] and decision trees [32-34], by adding certain noise perturbations. Another relevant approach is the secure multi-party computation for random forests and decision tree [35-39], where the privacy is preserved by multi-party joint computation over respective data inputs without leakage.
Homomorphic encryption [40-43] has been one the most important cryptosystems in privacy- preserving computing [44-47]. Based such scheme, various algorithms have been developed to train privacy random forests and decision trees [48-52], while some other methods only considered inference without training due computational costs [53-58]. In addition, LeFevre et al. [59] took
These authors contribute equally.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1:
Comparisons of communications and complexities for different Here, is the number of examples in training data, and T the cardinality of label space. Let and 8. the height and number of leaves of decision tree (h < x), respectively. Denote by the average number of possible splitting features and positions in the construction of decision trees, and is the number of clients for secure multi parttpaattt computation. '-' means the corresponding methods focusing only inference without training.
decision
Scheme
Trainin communication
Bandwidih
Training comp. complexity
Clicnt
Server
Predictive communication
Bandwidth
Predictive comp. complexity Paiacy
Server
model
SMCDT [61l
O(s)
O(jrn)
Obgira
O(egr)
0(1)
O(1)
O(1)
O(k)
PPIDS [36]
O(x)
O(p[jra)
Oinp"Svn)
O(sg [))
0(1)
O(1)
O(1)
O(k)
X
SID3 [37]
O(hp)
O(igr)
Obggre)
O(igr)
0(1)
0(1)
O(1)
O(f)
X
OPPC4.5 [39]
O(ep)
O(prr)
Oxjr(n p))
((mjrp))
0(1)
O(1)
O(1)
O(1))
PivotRFs [62]
O(ep)
Oljr +T))
O(agre)
O(kT7)
O(p)
O(k)
O(x)
O(k)
MulPRT's [63]
O(A)
Olloge + log d)
O hudi log
O log
O(R)
0(1)
O(R)
O(k)
PPD-ERTss [64]
O(hp)
O(k5r)
O(krra)
O(k3r)
((1)
O(1)
0(1)
0(h)
HFMdpRF [51]
O(N)
O(igr)
O(kgr)
O(KTrn)
0(1)
O(k]
0(K)
0(k)
SecureDT [65]
0(1)
0(1)
0(1)
0(x)
PrivaneDT [66]
0(1)
0(1)
0(1)
O(k)
Our werk
O(h)
O(k]
O(k)
O(Kjrn)
0(1)
O(1)
0(1)
0(k)
the anonymization [60] for random forests by grouping similar attributes so as to hardly identify
specific individual information.
This work takes step towards data encryption by incorporating some crucial ingredients of learning algorithm, and main contributions can be summarized as follows:
We present a new encryption to preserve data's Gini impurity, and the basic idea is to modify the structure of binary search trees to maintain several samples each node, and encrypt data's 's features by incorporating label and order information. Our scheme could change the data frequencies, which is also beneficial for data security.
Theoretically, prove the preservation of minimum Gini impurity in ciphertexts without decryption, which plays an important role on the construction of random forests. Our scheme also satisfies the security against Gini-impurity
aaat-iipurrtyy-peerving preseervese chosen plaintext attack.
We focus on the privacy random forests in the popular client-server protocol, and take our encryption for data features. We adopt homomorphic encryption CKKS to encrypt data labels. Our encrypted decision tree takes smaller communication and computational complexities, shown in Table
Gini-impuris
Extensive experiments show that encrypted random forests take significantly better performance than prior privacy random forests via encryption, anonymization and differential privacy, and are comparable to original (plaintexts) random forests without encryption. Our encrypted random forests make a good balance between computational cost and data security.
The rest of this work is constructed as follows: Section 2 introduces relevant work. Section presents an encryption data's Gini impurity. Section 4 proposes the encrypted random forests. Section 5 conducts extensive experiments. Section 6 concludes with future work.
Relevant Work
Homomorphic Eneryption (HE) is a cryptosystem, which allows operations encrypted data without access to a secret key [40]. We can perform some mathematical operations such as addition and multiplication operations on encrypted data without revealing sensitive information. Given an encryption function E(-) and a decryption function D(-), the HE scheme provides two operators @ and & such that, for every pair of plaintexts 21 and 22,
D (F()1) ( F((2)) .1 + and D (FF(1)) & F(xz)) 21 X
where + and x denote standard addition and multiplication operations, respectively.
Various HE schemes have been developed during the past years, e.g., ElGamal [67]. Paillier [68]. CKKS [42] encryption, etc. Relevant techniques have been successfully applied to machine learning tasks such as regression problem [69, 70]. neural network [71-75), collaborative filtering [76), etc. Generally, HE schemes are accompanied with high computational costs, and one main challenge is to maintain good trade-off among security, effectiveness and computational cost in real applications.

---

Opty +1
ayes +
Aigs tott Now +i
plaintexi
ciphertext
(G.
(G Psn.)
(22)
(G2 e2x,)
[Cg, (xa)
Ran-ke
Figure 1: A simple illustration for our encryption: each plaintext is encrypted into ciphertext vector (c,, ex,)) Here, random numbers < C2 ... < C. introduced preserve the Gini impurity for random forests, and take homomorphic encryption scheme for ei.j Ennchippb-) j) Eqn. (5), which is helpful for decryption.
Secure Multi-Party Computation (SMC) [77] is another cryptographic technique to jointly compute function from multiple private inputs with confidential, which has been used machine learning to protect privacy data, such neural network [78-80], k-means clustering [81-83], random forests and decision trees [35-39], etc. Differential privacy is introduced to preserve individual privacy by taking statistically inconsequential changes to data [84], and relevant techniques have been utilized in neural network [85-87], random forests [30, 31] and decision trees [32-34].
We introduce some notations used in this work. Write [r] 21,2.... r for integer 2 2. Let X' C IRd and y = [r] denote the feature and label space, respectively. A training sample is given by Sn { yı ); (22, v2): .... (z yn)}- Let |A| be the cardinality of set A, and [.] denotes the corresponding encrypted value. Net o²) be normal distribution of mean je and variance o².
3 An Encryption for Gini Impurity
This section presents the first eneryption to preserve the minimum Gini impurity over encrypted data without decryption. For simplicity, we give the detailed encryption on one-dimensional feature by incorporating label information, and make similar considerations for other dimensions.
3.1 Theoretical Analysis for Gini Impurity
Let A = =((1,,1)) (Ans }n be a dataset with labels E [r]. and define the Gini value as
Gini(A) = - Σ vE(T] Pr
where Py denotes the proportion of the label y. Let A {a; Uz): a, (as, Us) E A) and A" = (a; m:): a; > (a,, y:) E A} be the left and right subsets of w.r.t. a splitting point respectively. We define the Gini impurity w.r.t. dataset A and splitting point
Ic(A, a) wi Gini(A)) w, Gini(A))
(1)
where wy |//l/n and w, = //. Let (A) be the minimum Gini impurity of dataset A, i.e.,
(A) min,eR (la (A,
The minimum Gini impurity plays a crucial role on nodes splitting during the construction of random forests. We re-sort dataset A with non-decreasing order for a1, a2,-.. On follows:
A ((o)))(()).... (a(2) V22).. (a M(m))
where a(1) I app; S .... < a(j). and y(1) 9:2) ... Umm) denote their corresponding labels. By incorporating label information, we partition dataset A into several datasets I2, II, follows:
I { ( (ay). ... ((()))>(()))))
I = ((a B0) +1)) (a Hba) Vik +b,))
(4)
I, (aap +he- +1) Ml tha tb. ... (a B()))
Here, any two adjacent datasets have different labels, and all samples have an identical label one dataset Zy. i.c. y(0) yor for every (a v(o) I, and (a(r),2()) Iz.
3

---

Algorithm The Gini-impurtty-prsservee encryption
Input: Dataset A {(a1, y1), (an, Wn)}
Output: Binary search tree BT, ciphertexts {[ai].-... [an]}
Initialize: Tree BT = 0 with its cipher = Cmax/2 where Cmax = 2 logg n for i = 1,...,....... do
%% Step-l: Search a node for sample (a,, yi) in binary search tree BT Set t = root of BT, Emin = 0, Emax Cmax and index = 1 while is internal node and index==1 do
index= 0
if t.left + 0 and a, max(ay: (aj. Ms) t.lefft saeplessmples then
f t= t.left,, Ema = t.cipher, index =
else if (.right + 0 and a; (aj (d) E s.right.samples) then 1. -= L.right, mmin- L.iipher,, index =
end if
end while
Update = t.left Eqn. (6) true, and update = t.right Eqn. (7) is true
% Step-Il: Update the binary search tree BT
if y/ * yj for some (aj. yy) t.samples then
Split node t by Algorithm 2 with inputs of (a;, Vi) and the corresponding interval [fmin, mmax] end if
Append example (a:, y1) into l.smmllss and update Iciiperr Enc Enc (Kiphh, |1.sampless) Encrypt [a:] (I.cipher,, l.iiphe,,)
end for
We consider two important factors in encryption: i) preservation of the minimum Gini impurity 1a (A) over the encrypted data, and ii) cryptosystem for encoding and decoding data. Based on such recognition, we introduce the following encryption, for every example (a(s), M(0) E Iz.
[a = (Io I1. (a = [ (ct, EeEEEnnecaaaaa i))
for j = 1
(5)
(cg, Enc i k1 _............................... -...--.---.................... kz-1)) for 2 2 8
Here, Ci, C2...... Co are random numbers s.t. Ci < C2 < < C.. which aim to preserve the minimum Gini impurity. We take the homomorphic encryption scheme CKKS with public key kipub for [a Enc(Aipb:: lą - ... - ky-1) in Eqn. (5), and it is useful for decryption. Figure presents simple illustration for encryption, and the detailed decryption is given in Appendix A.
We now present our main theorem as follows:
Theorem 1.
We have (A) (A'),, for re-sort dataset A by Eqn. (3) and for the corresponding encrypted dataset A'
.... ([a H(n)) from Eqns. (4)-(5).
This theorem shows that our encryption could preserve the minimum Gini impurity over encrypted data. The detailed proof is presented in Appendix B, which involves the proof of piecewise mono- tonicity of Ta A, a) w.r.t. splitting point and then solves the minimum splitting point plaintexts, as well as the corresponding point on encrypted data.
3.2 Binary Search Tree for Encryption
We now present new binary search tree to encrypt ".,...,, dynamically, especially for un-ordered dataset A ((a); (()) v/),, ... (An, }n or when example (a;, v:) arrives in streaming data. We begin with alternative structure for binary search tree to maintain several samples node from Eqns. (4)-(5), rather than previous only one sample [88, 89]. Our new structure is given by
Struct Tree (Plaintext samples; Ciphertext cipher,, cipher2; Tree left, right)
The samples stores one or multiple samples from A, and cipher, and cipher2 are the first and second ciphertext in Eqn. (5), and left and right denote left and right child of the current node, respectively.
We initialize an empty tree BT = and set its cipher; = Cmax/2 with Cmax 2 logz n. and then we construct binary search tree iteratively. We maintain an interval [tmin m in each iteration as

---

Algorithm 2 Splitting node for encryption
Input: Example (ai, y:), node t of binary search tree BT, and interval [Lmins [max] Output: Updated node t
Initialize an empty node I with Lsamples {{aj, Ut) E t.samples: 0g < az) if Lsampless o @ then
if' t.left + 0 then
Set l.cipher, according to Eqn. (8), and update L.left = t.left, t.left
else
Set l.cipher, according to Eqn. (9), and update t.left =
end if
end
Initialize empty node with r.samples {(aj. V3) E I.samples: : 0j az) if r samples * 0 then if t.right + 0 then
Set r.cipher, according to Eqn. (10), and update r.right = t.right, t.right = r
else
Set r.cipher, according to Eqn. (1I), and update t.right
end if
end if
Update t.samples t.samples I.samples r.samples
to keep the increasing order of ciphertexts e C2 ...... Co in Eqn. (5). During the i-th iteration, receive a sample (a,, )1), and then take two steps as follows:
Step-l: Search node for sample (a;, y/) in binary search tree BT
Let be a node pointer with the initialization the root of BT. We search a path downward in BT by comparing with ag and the search will terminate when is leaf node or empty node.
For an internal node t, the search continues to its left child and updates fmax t.cipher, if
the left child t.left + 0
and < maj: (aj.U5) U5) E t.lestssapples
and the search continues to its right child and updates mii = t.cipher, if
the right child (.right + 0 and a, a min(ay: (a,, MU)) t.right saighessmmple] ; otherwise, the search terminates. This procedure can be easily implemented with a while loop.
necessary to consider two special cases after the above search. We update = L.left if
t.left # 0, min(ay: (azz Vj) E t.samples) and y: yy for all (az, Uy) t.left.samples. In similar manner, we update t.right if
(6)
tright * 0, 0; > max(a;: (1) E (.samples] and yi = My for all (a,, M3) E sriighs.samples.
(7)
Step-II: Update the binary search tree BT
After Step-I, we could find a node t for sample (a,, 9:) and the corresponding interval [tmin: tmux]- We directly append the example (a,, yr) into t.samples if ya = y for every (a.. E t.samples; otherwise, is necessary to split the node according to a,.
We initialize empty node with isamples = {(aj, Uj) t.samples: aj < ai). and it is sufficient to consider I.samples + Ó. left # 0. then we set
1/2 s.t. Lleft.cipher, l.cipher, < L.cipher,, (8) and update I.left t.left, t.left = 1; otherwise, we set
L.cipher (l.lef.ccphee,
I.cipher (1min + t.cipherr))/ / + s.t. Lcipher, E (Amin, (.iipher))
and update 1.left = I. Here, { is random number sampled from /O, 1), and notice that we may randomly sample & multiple times that the condition holds in Eqns (8)-(9,, respectively.
5

---

Algorithm 3 Finding the best splitting feature and position
Input:
Enerypted datasets [S available splitting feature and position [+]]]=] and secret key kisea
Output: index i
%%% Server:
for i [b] do
Calculate Gini impurity ([[,, [sl,)
from Eqn. (12) w.nt splitting feature and position [s];
end for
Send ciphertexts [Ic((S) to the client
%% Client:
Get the decrypted (c [[S [sl,))
Lo
Set -1 (eceesee ([ [s1,) = 0 for every E [ otherwise, set by Eqn. (13)
Send i* the server
We make similar update for the right child of node initialize an empty node r with r.samples {(aj, (()) E I.samples: 0j > ai), and consider r.samples & 0. If l.rihht of 0, then we set r.cipher, = (L.cipher, +
s.t. l.cipher, < rr.cipher, < &.right.cipher, (10)
and update r.right = t.right, t.right r; otherwise, we set r.cipher, (t.cipher, + m2 s.t. r.cipher, E " and update t.right r. Algorithm 2 presents the detailed descriptions on the splitting of node t.
(11)
Algorithm presents an overview of our cini-impurity-ae inpuritt-preserrinng preserving encryption, and the decryption is given in Appendix A. Our scheme does not only keep the minimum Gini impurity, but also change frequencies to prevent decryption from frequencies, which also beneficial for encryption [90]. Our scheme takes average of O( log n) computational complexity, since it requires O(log n) and O(1) computational complexities to search and update a node in each iteration, respectively. Finally, the average and worst space complexities are O(log n) and (n)) for encryption, respectively.
3.3 Security Analysis
For ciphertext vector [a] ([a]] [a]l)) in Eqn. (5), it suffices to discuss the first eiphertext [a] since the security of [a]2 has been analyzed in homomorphic encryption CKKS [42]. Following semantic security against chosen plaintext attacks [89, 91], we define a security game GameGIPCRA:
An adversary chooses two sequences with distinct plaintexts (af,..,, and {at. r. ,0h) and sends them challenger;
"et.....,da, J. and randomly sets their with each yf drawn independently and uniformly over [r]. The challenger encrypts {at.-- ] by Equs. (4) and (5), and sends the ciphertexts the adversary:
The challenger flips an unbiased coin E {0, 1} to select {at, corresponding labels f./..... 1/
The adversary outputs a guess of 6, i.c., which sequence is selected for encryption.
We then introduce the security against Gini-impurity preserving Definition 2. A scheme said be indistinguishable under wil---ipuutttteeeereee
ireerrity- chosen plaintext attack as follows.
chosen plaintext attack if the probability of outputs with the correct guess b is negligible for the adversary A GameCIPPA. that is,
P+[A(Gammennccn) ) bj 1 small constant.
The following theorem shows that our enerypted plaintexts sequences are indistinguishable. Theorem 3. Our scheme for the first ciphertexts [a.]],, ["a]i, ... [a.]] in Section 3.2 is security against Sinii-impurity-peeseeee
chosen plaintext attack.
The detailed proof is presented in Appendix C, and the basic idea is inspired from [88]. We take induction on n to show that data point (a/+1> 11+1) affects the constructed binary search trees with the same probability as = and = 1, and then the eiphertexts of data points (af+1: Mi+1) also follow the same distribution, i.e.,
P [[a]].-.. ... Iol.illaf.... ,a...) P ([a]],-- [attillat,.. .a411)

---

Table 2: Datasets
Dalasets
#inst
#eatt
Datasets
#inst
#Feat
Datasets
#lnst
iFeat
Datasets
#lnst
#Teat
wdbc
569
adver
3,279
1,558
allerons
13,750
adult
48,842
14
cancer
569
31
bibtex
7,396
1,836
house
22,784
minist 70,000
780
breast
699
php80
7,797
617
a9a
32,563
123
miniboone
72,998
51
diaeees
768
pendigits
10,992
amazon
32,769
runwalk 88,588
german
1,000
phish
11,055
30
bank
45,2
17
covtype
581,012
54
Enerypted Random Forests
For encrypted random forests, we follow the popular client-server protocols [31, 65, 66, 88]. A client encrypts training and testing data, and transfers encrypted data to an honest-but-curious server. The server trains random forests from the encrypted data with the aid of client, and finally returns predictions on encrypted testing data.
Encryption for training and testing datasets
Recall training data Sn, {ar,, .I)..... (æn, yn)} with æ;; ( Ti,d). The client constructs binary search trees BT, ... BTTa according to Algorithm over different dimensional features and labels in Sn, where BT, used encrypt features {=i.j.--. ; .nnj)
for j [d].
We take the homomorphic encryption CKKS [42] to encrypt training labels y1. Vn. Each label y/ is encoded with vector of size by one-hot method, and encrypt the vector by homomorphic encryption CKKS with public key kpub. The ciphertexts [v:] = [[v..]. [v. is given by
[m,|] = { Enc(kipu 1) for j yé: Enc (kiub. 0) otherwise.
We obtain the final training data [S.]]
[vil,,... ([I,II (v.1))
Let Sp. {æ1..... T.,r] } be testing data with instance ã; = (ăr.1, ... a.) For every plaintext His with E [n'] and j E [d], we search a node in the binary search tree BT,, similarly the node search (Step-I) in Section 3.2, and obtain its ciphertext [ = [t.ipherr Enc Enccaipab, i)]. We have the
encrypted testing data [$,,] [[
Construction on encrypted random forests
Encrypted random forests consist of individual decision trees DTI. DTm, where each tree DT constructed follows. We first take a bootstrap sample [S[]]] ] from [[,]] and initialize DT, with
one node of data [S We repeat the following procedure recursively for each leaf node, until the number of training samples smaller than a, or all instances have the same label in the leaf node:
Select a k-subset B from d available features randomly without replacement;
Find the best splitting feature in B and position by Gini impurity from the encrypted data;
Split the current node into left and right children via the best splitting position and feature.
Such construction is essentially similar to original random forests [1], whereas we require a different way find the best splitting feature and position based Gini impurity from the encrypted data.
Let / be the current leaf node for further splitting with the encrypted training data [S]]] C [Sx]] and [s]]..... , [s], denote all possible splitting features and positions in the scope of the corresponding feature subset from [ Here, the information of feature and position be derived from the corresponding index i E []] and subset B.
For each [g]. the server partitions the current encrypted training data [S]]] into left and right subsets, i.e., [[ and [SA according to the splitting feature and position [s] Let ni and n, be the number of training examples in [S and [S respectively, and denote by
(I Idd and [ = [[[=]].[[]]) ([= (...D.. From Eqn. (1), we have Gini impurity
[S = [[ Ivll), ...
II [+],))
Ln nr @ [T([S
+ m nr
ny
& II([S)))))
(12)
7

---

Table 3: Comparisons of prediction accuracies (mean / indicates that our enerypted random forests are significantly better/worse than other compared random forests (pairwise t-tests at 95% significance level). 'NA' means that no results were obtained after running out 10 seconds (about 11.6 days).
Dotase:
enerypsed RD's
Original
AncoyRi's
DiftiinR'ss
PPD BRTs
PivoRRsss
MulPRDs
HEMPRIS
wdbcc
9525 0141
961 7:100018
9099 0206
39982 0024
922722 0037
96092 0101
9510:2011 14
91952: 9009
cancer
W/66: 0082
982411.01 43
92711 0016
90341. 0576
900012 0022
9510 01 01
9606110000
.922 0024
breest
.955 0012
9801100011
.955
0021
9271 1. 0515
9678.1.01294
58061.0000
9169
9275 0023
german
.7899=0122 0124
80334.0200
.7300
7810:1 0158
75334.0122
77823-50054
70433
diabetes
7641= 0093
.6777.0309
0023
7328
.7448:.0198
74199400011
:6611
adver
9851= 0011
9688 0014
9278 0015
050 0051
NA
9664+.0043 0043
NA
NA
biblex
2007= 0054
7749 0027
7425: 0000
72001 01 10m
7461
01991 0193
NA
NA
php60
9380= 0024
8641 0005
8920 0051
NA
NA
NA
NA
pondights
9917=
9073: 0104
9154+: 0126
9639
9070
NA
phish
979R= 00766
97166:
99182
9555:2 0125
9401
eikerons
8795 0027
88:91.0015
81042 0105
83221 0.01
8589 0063
8571-1.0067+
6766110022
NA
house
.894 0007
891511.00.90
8255 1: 0011
$475 0025
8141
8508.1.0010
S742
NA
a9a
8321 0011
.900
.806:1 0027
7909 L.
8345-1.0144
.514410071
NA
amazon
9491:00109
9478:5.0000
.919
9104: 0335
9401
9400
bank
900991.0:4
849991
.940.1.0001
8827
adult
.8033 0019
.091110018
.8006. 0032
4225
.452210106
8243.1.0055
mnist
.9674 0105
99633+.0101
(9362: 0000
9059 01157
NA
NA
NA
NA
minboono
9497= 0018
9518 #:0013
8977: 0101
9131=t0104+
0301=t000021+
9501
NA
NA
runwalk
0784 0014
9708t.
9523= 007.4
9401 0340
9573:t
9511
NA
covtype
9640st:00
0015
wirticllss
2/16/2
20/MI1
26/V0
17/3/
14/60
10/10
19/00
where -o([st))) = =1 @ and [o([5)))))) 11 pr Pr. with
p (1/mz) (Ivil....... ,.r.., and pr (1/n,) & (b.I,....,,e,,..
Here, @. 3 1 and @ denote the CKKS element-wise homomorphic multiplication, dot, addition and subtraction functions, respectively, as in the work of [42].
The client gets plaintexts (Dec (keee, (a([S [ 1 [+)))))) by decrypting with the secret key ksee, when
the server sends ciphertexts [Ta([)) Il ()))))) -= If all instances have the same label in [S then
we have Dec(kisee Ta [o([5]] [[ = for each i E [j]. and we set i" = 11; otherwise, we set 1" as
i* arg argmeel {Dec(kse [c([S))Iss]))
(13)
The client sends index i' to the server for further splitting. Algorithm presents the detailed descriptions on finding the best splitting feature and position.
For encrypted decision tree, the client requires the O(k) computational complexity with leaves nodes, since the client performs constant basic operations for each node. The server takes the (ujrn) computational complexity for Eqn. (12), where j is average of number of possible splitting features and positions, and and n are the number of labels and training examples, respectively.
Our method takes (h) communication rounds of Oxxj) communication bandwidth to train an encrypted decision tree of height This is because we consider the breadth-first search and aggregate all nodes in the same height and send the client with single message one time.
We do not require bootstrapping for homomorphic encryption in 3-depth homomorphic multiplicative. since we independently compute the splitting feature and position for each node from Eqn. (12). This different from previous encrypted decision trees [51, 62), which could take expensive computational complexity for bootstrapping [40, 92].
Prediction on encrypted testing dataset
After getting decision trees DT,, DTm, we predict label [ = DT, ( ([x:]) @ ...... @ DT,, ([..)(
[[.]))
for test instance [[.]] [. The server sends ciphertexts { [[ [7..1] to the client, and the
client decrypts those ciphertexts, and gets the final plaintext label by j. arg maxxeei=(Dee [D [I,
During such prediction process, the server requires the (hh) computational complexity, since search from the root to leaf node of tree. The client takes O(1) rounds of communication and communication bandwidth to transfer the testing data and predicting ciphertext without interaction.
8

---

rureing tr (peccnda
bybbess garwon
pendigh yhah
meltceeA CONT
Figure 2: Comparisons of training running time on different random forests. Notice that the y-axis is in log-scale, and full black columns imply that result was obtained after running out 10 seconds (about 11.6 days).
Experiment
We conduct experiments on 20 datasets summarized in Table 2. Most datasets have been well- studied in previous random forests. In addition to the original (plaintexts) random forests [1], we compare with six state-of-the-art priveey-preserving random forests recent years.
AnonyRFs: random forests based anonymization with a top-down greedy search [59];
DiffPrivRFs: random forests based differential privacy [93];
PPD-ERTs: extremely randomized trees from distributed structured data [64];
random forests based on a hybrid of threshold partially homomorphic encryption and secure multiparty computation techniques [62];
PivotRFs:
MulPRFs: random forests based on the secure multiparty computation [94];
HEldpRFs: random forests with fully homomorphic encryption and low-degree polynomial approximations [51].
For all random forests, we train 100 individual decision trees, and randomly select Lvd candidate features during node splitting. We set a 10 for datasets of size smaller than 20,000 for our encrypted random forests; otherwise, set = 100, following [95]. For multi-class datasets, we take the one-vs-all method for MulPRFs, since it is limited to binary classification. Other parameters are set according to their respective references, and more details can be found in Appendix D.
Experimental comparisons
The performance is evaluated by five trials of 5-fold cross validation, and final prediction accuracies are obtained by averaging over these 25 runs, summarized in Table 3. It is evident that our encrypted random forests take comparable performance with original random forests [1] on plaintexts, which nicely supports our Theorem 1 on the preservation of minimum Gini impurity in the construction of random forests. Our encrypted random forests are also comparable to MulPRFs if they can obtain results within 10th seconds (about 11.6 days), since MulPRF's are essentially similar to original random forests, yet with different implementation of secure multi-party computation.
As be seen from Table and DiftPrivRFs, since the win/tie/loss counts show that our random forests win for most times and never lose. This is because AnonyRFs combine features by anonymization, while DiftPrivRFs add perturbations to features via differential privacy, therefore, both of them cause information lost in privacy process. Our random forests also achieve better performance than PivotRFs, since PivotRFs have to limit trees' depth for random forests due to heavy computations for HE and communications for secure multi partt computation.
random forests take significantly better performance than AnonyRFs
Our random forests also outperform PPD-ERTs and HEldpRFs if results obtained in 10t seconds, since PPD-ERT's adopt completely-random splitting, rather than selecting the minimum Gini impurity, while HEldpRFs take homomorphic encryption features and employ low-degree polynomial approximation. Those approaches have modified the structures original random forests.
Downloaded from www.openml.org

---

datasets without privacy Oursden: peleantidgoogg
7h6
Corope
Figure 3: Security comparisons for different schemes: the more red the area, the higher the security.
Running time
All experiments are performed by C++ on the Ubuntu with 256GB main memory (AMD Ryzen Threadripper 3970X). We compare the training running time of encrypted random forests and others, and the average CPU time (in seconds) is shown in Figure 2.
As expected, original random forests take the least running time preservation. Our encrypted random forests take larger running time than AnonyRFs and DiffPrivRFs because they essentially similar to original random forests, yet with simple modifications perturbations on features. Our encrypted random forests take better performance and higher security.
Our encrypted random forests take smaller running time than PPD-ERTs, PivotRFs, MulPRFs and HEIdpRFs, in particular for large datasets or high-dimensional datasets, where no results are obtained after rumning out 10 seconds (almost 1 11.6 days). Because PPD-ERTs, PivotRFs and MulPRFs require expensive communication cost for multi-parity computation, while PivotRFs and HEldpRFs take heavy computation costs HE scheme.
Security analysis
We present security analysis for the first ciphertext [a]]] in ciphertext vector [a] = ([a]),, [a]2), and the second ciphertext [a]2 2 be ensured by HE scheme. We compare with four state-of-thheaa encryptions: differential privacy [93], anonymization [59], order-preserving scheme [96] and HE scheme [42]. Here, we present results of six datasets and randomly selecting one feature, and trends are similar on other dimensions and datasets. More results can be found in Appendix D.
Figure 3 shows the comparison results, and take the bitwise leakage matrices to measure the security as in [97]: the more red the area, the higher the security. As expected, HE scheme presents the highest security, yet with heavy computational costs, for example, results obtained for datasets of size exceeding 3000 even after running out 10th seconds. is also observed that our scheme presents higher security than the other three schemes, since those schemes simply present perturbations, compression or preserve the entire order information regardless of learning ingredients. In comparison, scheme could make good balance between security and computational cost.
Conclusion
This work takes one step on data encryption from some crucial ingredients of learning algorithm. We present new encryption preserve data's Gini impurity, which plays a crucial role during the construction of random forests. For random forests, we encrypt data features based on our Gini-impurity- prreritiyppeeriinggggg scheme, and take the homomorphic eneryption scheme CKKS encrypt data labels. Both theoretically and empirically, we validate the effectiveness, efficiency and security of our proposed method. An interesting work is exploit other learning ingredients, such as gini index and information gain, for data encryption in the future.
Acknowledgements
The authors want to thank the reviewers for their helpful comments and suggestions. This research was supported by National Key R&D Program of China (2021ZD01 12802). NSFC (61921 001921006, 02376119), CAAl-Huawei MindSpore Open Fund, and Fundamental Research Funds for the Central Universities (2023300246). W. Gao is the corresponding author of this paper.
10

---

References
[1] L. Breiman. Random forests. Machine Learning, 45(1):5-32,
[2] G. Biau and E. Scornet. A random forest guided tour. Test, 25(2):197-227, 2016.
[3] L. Mentch and S. Zhou. Randomization as regularization: A degrees of freedom explanation for random forest success. Journal of Machine Learning Reseurch, 21:1-36, 2020.
[4] M. Vernández-Delgadoo E. Cernadas, S. Barro, and D. Amorim. Do need hundreds of classifiers to solve real world classification problems? Journal of Machine Learning Research, 15(1):3133-3181, 2014.
[5] D. Cutler, T. Edwards Jr, K. Beard, A. Cutler, K. Hess, J. Gibson, and J. Lawler. Random forests for classification in ecology. Ecology, 88(1 11):278-22722 2007.
[6] Y. Qi. Random forest for bioinformatics. In Ensemble Machine Learning, pages 307-323. Springer, 2012.
[7] Shotton, A. Fitzgibbon, M. Cook, T. Sharp, M. Finocchio, R. Moore, A. Kipman, and A. Blake. Real-time human pose recognition in parts from single depth images. Communications of the ACM, 56(1): 2013.
[8] M. Belgiu and Dragut. Random forest in remote sensing: A review of applications and future directions. ISPRS Journal of Photogrammetry and Remote Sensing,
[9] A. Criminisi and J. Shotton. Decision forests for computer vision and medical image analysis. Springer Science & Business Media, 2013.
[10] S. Basu, K. Kumbier, J. Brown, and Bin B. Yu. Iterative random forests to discover predictive and stable high-order interactions. Proceedings of the National Academy of Sciences, 115(8): 1943-1944 1948, 2018.
[11] M. Denil, D. Matheson, and N. Freitas. Consistency of online random forests. In Proceedings of the 30th International Conference on Machine Learning, pages 1254,1264, 2013.
[12] G. Louppe, L. Wehenkel, A. Sutera, and P. Geurts. Understanding variable importances in forests of randomized trees. Advances in Neural Information Processing Systems 26, 2013.
[13] P. Geurts, D. Ernst, and L. Wehenkel. Extremely randomized trees. Machine Leariing 63(1):
3-42, 2006.
[14] B. Lakshminarayanan, D. Roy, and Y. Teh. Mondrian forests: Efficient online random forests. Advances in Neural Information Processing Systems 27, pages 3140-3144 -144, 2014.
[15] X. Li, Y. Wang, S. Basu, K. Kumbier, and B. Yu. A debiased mdi feature importance measure for random forests. Advances in Neural Information Processing Systems 32, 2019.
[16] Y. Lin and Y. Jeon. Random forests and adaptive nearest neighbors. Journal of the American Statistical Association, 101(474):578-52) 2006.
[17] B. Menze, B. Kelm, D. Splitthoff, U. Koethe, and F. Hamprecht. On oblique random forests. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 453 469,469,22 2011.
[18] J. Rodriguez, L.. Kuncheva, and C. Alonso. Rotation forest: A new classifier ensemble method.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10) 16119)1:6111111 1630, 2006.
[19] S. Wager, T. Hastie, and B. Efron. Confidence intervals for random forests: The jackknife and the infinitesimal jackknife. Journal of Machine Learning Research, 15(1):1625-166 1651, 2014.
[20] Z. Zhou and J. Feng. Deep forest. National Science Review, 6(1):74-86, 2019.
[21] W. Gao, F. Xu, and 7.-H. Zhou. Towards convergence rate analysis of random forests for classification. Artificial Intelligence 313:103788, 2022.
[22] J.-Q. Guo, M.-Z. Teng, W. Gao, and 7.-H. Zhou. Fast provably robust decision trees and boosting, In 1nPror Proceedings of the 39th International Conference on Machine Learning, pages 8127-8144 2022.
[23] G. Biau, L. Devroye, and G. Lugosi. Consistency of random forests and other averaging classifiers. Journal of Machine Learning Research, 9:2015-2033 2008
[24] G. Biau. Analysis of a random forests model. Journal of Machine Learning Research, 13(1): 1063-1095, 2012.

---

[25] E. Scornet, G. Biau, and J. Vert. Consistency of random forests. Annals of Statistics, 43(4): 1716-17411 2015.
[26] Mourtada, S. Gaiffas, and E. Scornet. Universal consisteney and minimax rates for online mondrian forests. Advances in Neural Information Processing Systems 30, pages 3758-3767,
2017.
[27] C. Tang, D. Garreau, and U. von Luxburg. When do random forests fail. Advances in Neural Information Processing Systems 31, pages 2987-2997. 2018.
[28] Z.-H. Zhou, Ensemble Methods: Foundations and Algorithms. CRC Press, 2012.
[29] C. Dwork. Differential privacy. In Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming, pages 1-12, 2006.
[30] A. Patil and S. Singh. Differential private random forest. In Proceedings of the 3rd International Conference on Advances in Computing, Communications and Informatics, pages 2623-2630, 2014.
[31] X. Li, B. Qin, Y.-Y. Luo, and D. Zheng. A differential privacy budget allocation algorithm based on out-of-bag estimation in random forest. Mathematics, 10(22):4338, 2022.
[32] A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: The sulq framework. In Proceedings of the 24th ACM WGGMOD-SGACC-SIGANN Symposium on Principles of Database Systems, pages 128 238.138,20 2005.
[33] A. Friedman and A. Schuster. Data mining with differential privacy. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 493-502, 2010.
[34] S. Fletcher and M. Islam. Decision tree classification with differential privacy: A survey. ACM Computing Surveys, 52(4):1-33, 2019.
[35] S. Samet and A. Miri. Privacy preserving ID3 using gini index over horizontally partitioned data. In Proceedings of the 6th International Conference on Computer Systems and Applications, pages 645 651, 2008
[36] J. Vaidya, C. Clifton, M. Kantarcioglu, and A. Patterson. Privacy-preserving decision trees over vertically partitioned data, ACM Transactions on Knowledge Discovery from Data, 2(3):1-27, 2008.
[37] S. Hoogh, B. Schoenmakers, and P. Chen. Practical secure decision tree learning in tele- treatment application. In Proceedings of the 18th International Conference on Financial Cryptography and Data Security, pages 179-194, 2014.
[38] M. Joye and F. Salehi. Private yet efficient decision tree evaluation. In Proceedings of the 32nd Annual IFIP Conference on Data and Applications Security and Privacy, pages 249, 2018
[39] Y. Li, Z. Jiang, L. Yao, X. Wang, S. Yiu, and Z. Huang. Outsourced decision tree algorithm over horizontally and vertically partitioned dataset among multiple parties. Cluster Computing, 22(1):151--1593 2019.
C4.5
[40] C. Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Anmual ACM Symposium on Theory of Computing, pages 169-178, 2009.
[41] L. Ducas and D. Micciancio. Fhew: Bootstrapping homomorphic encryption in less than a second. In Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryplographic Techniques, pages 617-640, 2015.
[42] Cheon, A. Kim, M. Kim, and Y. Song. Homomorphic encryption for arithmetic of approximate numbers. In Proceedings of the 23rd International Conference on Theory and Application of Cryptology and Information Security, pages 409-437. 2017.
[43] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. Tfhe: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1) 33(1):34-91, 2020.
[44] R. Gilad-Bachrach N. Dowlin, K. Laine, K. Lauter, M. Nachrig, and J. Wernsing. Cryptonets: Applying neural networks to enerypted data with high throughput and accuracy. In Proceedings of the 33rd International Conference on Machine Learning, pages 201-210, 2016.
[45] Q. Lou, W. Lu, C. Hong, and I.. Jiang. Falcon: Fast spectral inference on encrypted data. Advances in Neural Information Processing Systems 33, pages 2364-2374, 2020.
12

---

[46] Z. Ghodsi, N. Jha, B. Reagen, and S. Garg. Circa: Stochastic ReLUs for private deep learning. Advances in Neural Information Processing Systems 34, pages 2241-2252 2021.
[47] X. Li, R. Dowsley, and M. Cock. Privacy-preserving feature selection with secure multiparty computation. In Proceedings of the 38th International Conference on Machine Learning, pages 5326-6336, 2021.
[48] A. Aloufi, P. Hu, H. Wong, and S. Chow. Blindfolded evaluation of random forests with multi-key homomorphic encryption. IEEE Transactions on Dependable and Secure Computing, 18(4):1821-1855, 2019.
[49] J. Li, X. Kuang, S. Lin, X. Ma, and Y. Tang. Privacy preservation for machine learning training and classification based on homomorphic encryption schemes. Information Sciences, 526:
169, 2020.
[50] L. Pulido-Gaytan, A. Tchernykh, J. Cortés-Mendoza, M. Babenko, and G. Radchenko. A survey on privacy-preservine machine learning with fully homomorphic encryption. In Proceedings of the 7th Latin American Conference on High Performance Computing, pages 115-129, 2021.
[51] A. Akavia, M. Leibovich, Y. Resheff, R. Ron, M. Shahar, and M. Vald. Privacy-preserving decision trees training and prediction. ACM Transactions on Privacy and Security, 25(3):1-30, 2022.
[52] K. Cong, D. Das, J. Park, and H. Pereira. Sortinghat: Efficient private decision tree evaluation via homomorphic encryption and transciphering. In Proceedings of the 29th ACM SIGSAC Conference Computer and Communications Security, pages 563-577, 2022.
[53] J. Brickell, D. Porter, V. Shmatikov, and E. Witchel. Privacy-preserving remote diagnostics. In Proceedings of the 14th ACM SIGSAC Conference on Computer and Communications Security, pages 498-507, 2007.
[54] M. Barni, P. Failla, V. Kolesnikov, R. Lazzeretti, A. Sadeghi, and T. Schneider. Secure evaluation of private linear branching programs with medical applications. Proceedings of the 17th European Symposium on Research in Computer Security, pages 424 439, 2009.
[55] R. Tai, J. Ma. Y. Zhao, and S. Chow. functions. Proceedings of the 22nd European Symposium on Research in Computer Security, pages 494-512, 2017.
decision trees evaluation via linear
[56] A. Tueno, F. Kerschbaum, and S. Katzenbeisser. Private evaluation of decision trees using sublinear cost, Proceedings on Privacy Enhancing Technologies, 2019(1):266 2019.
[57] Á. Kiss, M. Naderpour, J. Liu, N. Asokan, and T. Schneider. Sok: Modular and efficient private decision tree evaluation. In Proceedings of Privacy Enhancing Technologies, pages 187-208. 2019.
[58] K. Sarpatwar, N. Ratha, K. Nandakumar, K. Shanmugam, J. Rayfield, S. Pankanti, and R. Vac- ulín. Privacy enhanced decision tree inference. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pages 154-159, 2020.
[59] K. LeFevre, D. Wetitt, and R. Ramakrishnan. Mondrian multidimensional k-anonymity. In Proceedings of the 22nd International Conference on Data Engineering, pages 25-25, 2006.
[60] L. Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-
Systems, 10(05):557-570 2002.
[61] W. Du and Z. Zhan. Building decision tree classifier on private data. In Proceedings of the 14th IEEE International Conference on Privacy, Security and Data Mining, pages 1 1-8, 2002.
[62] Y. Wu, S. Cai, X. Xiao, G. Chen, and B. Ooi. Privacy preserving vertical federated learning for tree-based models. CoRR/abstract, 2008 06. 06170, 2020.
[63] K. Hamada, D. Ikarashi, R. Kikuchi, and K. Chida. Efficient decision tree training with new data structure for secure multi-party computation. CoRR/abstract, 21 21 2021.
[64] A. Aminifar, Rabbi, K. Pun, and Y. Lamo. Privacy preserving distributed extremely random- ized trees. In Proceedings of the 36th Annual ACM Symposium on Applied Computing, pages 1102-1105, 2021.
[65] M. De Cock, R. Dowsley, C. Horst, R. Katti, A. Nascimento, W. Poon, and S. Truex. Efficient and private scoring of decision trees, support vector machines and logistic regression models
13

---

based on pre-computation. IEEE Transactions on Dependable and Secure Computing, 16(2): 217-230, 2017.
[66] A. Tueno, Y. Boev, and F. Kerschbaum. Non-interactive private decision tree evaluation. In Pruceedings of the 34th Annual IFIP Conference on Duta and Applications Security and Privacy, pages 174-194, 2020.
[67] T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31:469 472, 1985.
[68] P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Proceedings of the 18th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 223 223-238, 1999.
[69] K. Han, S. Hong. J. Cheon, and D. Park. Logistic regression on homomorphic encrypted data at scale. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 9466 9471, 2019.
[70] P. Fenner and E. Pyzer-Knapp
Gaussian process regression A modular approach to the application of homomorphic encryption. In Proceedings of the 34th AAAI Conference Artificial Intelligence, pages 3866-3873, 2020.
[71] A. Sanyal, M. Kusner, A. Gascón, and V. Kanade. TAPAS: Tricks to accelerate (encrypted) prediction as service. In Proceedings of the 35th International Conference on Machine Learning, pages 4497-4506, 2018.
[72] Q. Lou, B. Feng, G. Fox, and L. Jiang. Glyph: Fast and accurately training deep neural networks on encrypted data. Advances in Neural Information Processing Systems 33, pages 9193-9200 2020.
[73] Q. Lou and L. Jiang. HEMET: A comoomoppic-enccytiionniii
privacy-preserving mobile neural network architecture. In Proceedings of the 38th International Conference on Machine Learning, pages 7102-7110, 2021.
[74] S. Pentyala, R. Dowsley, and M. Cock. Privacy-preservie video classification with convo- lutional neural networks. In Proceedings of the 38th International Conference Machine
Learning, pages 8487-8499 8499, 2021.
[75] E. Lee, J. Lee, J. Lee, Y. Kim, Y. Kim, J. No. and W. Choi. Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions. In Proceedings of the 39th International Conference on Machine Learning, pages 12403- 12422, 2022.
[76] Wang, Q. Tang, A. Arriaga, and P. Ryan. Novel collaborative filtering recommender friendly to privacy protection. In Proceedings of the 28th International Joint Conference Artificial Intelligence, pages 4809-4815, 2019.
[77] AC. Yao. Protocols for secure computations. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 160-164, 1982.
[78] S. Sayyad. Privacy preserving deep learning using secure multiparty computation. In Proceed- ings of the 2nd International Conference on Inventive Research in Computing Applications, pages 139-142, 2020.
[79] R. Shokri and V. Shmatikov. Privacy preserving deep learning. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1310-1321, 2015.
[80] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, HB. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. Practical secure aggregation for arivacy-preeervin machine learning. In proceedings of the 24th ACM SIGSAC Conference Computer and Communications Security, pages 1175-1191.
[81] J. Vaidya and C. Clifton. Privacy-preservve k-means clustering over vertically partitioned data. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 206-215, 2003.
[82] X. Yi and YC. Zhang. Equally contributory privacy preserving k-means clustering over vertically partitioned data. Information Systems, 38(1):97-107, 2013.
[83] Y. Fan, J. Bai, X. Lei, W. Lin, Q. Hu, G. Wu, J. Guo, and G. Tan. PPMCK: Privacy-preserving multi-party computing for k-means clustering. Parallel and Distributed Computing, 154:54633, 2021.
14

---

[84] C. Dwork. Differential privacy: A survey of results. In Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, pages 1-19, 2008.
[85] M. Abadi, A. Chu, I. Goodfellow, HB. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security, pages 308-318, 2016
[86] T. Ha, TK. Dang, TT. Dang, TA. Truong, and MT. Nguyen. Differrnniall privacy in deep learning: An overview. In Proceedings of the 12rd International Conference on Advanced Computing and Applications, pages 97-102, 2019.
[87] B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and CY. Zhang. Deep learning with label differential privacy. Advances in Neural Information Processing Systems 34, pages 27131- 27145, 2021.
[88] R. Popa. F. Li, and N. Zeldovich. An ideal-security protocol for arder-preserving encoding. In Proceedings of the 34th IEEE Conference on Symposium on Security and Privacy, pages 463-477, 2013.
[89] K. Florian. Frequency hiding order preserving encryption. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 656-667, 2015.
[90] M. Islam, M. Kuzu, and M. Kantarcioglu. Access pattern disclosure on searchable encryp- tion: Ramification, attack and mitigationjq. In Proceedings of the 19th Annual Network and Distributed System Security Symposium, page 12, 2012.
[91] S. Goldwasser and S. Micali. Probabilistic encryption how to play mental poker keeping secret all partial information. In Proceedings of the 14th Annual ACM Conference on Symposium on Theory of Computing, pages 365-377 1982.
[92] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachene. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, pages 3-33, 2016.
[93] N. Holohan, S. Braghin, P. Mac Aonghusa, and K. Levacher. Diffprivlib: The IBM differential privacy library. CoRR/abstract,
2019.
[94] K. Marcel. MP-SPDZ: A versatile framework for multi-pare computation. In Proceedings of the 27th ACM SIGSAC Conference on Computer and Communications Security, pages 1575-1590, 2020.
[95] P. Probst, M. Wright, and A. Boulesteix. Hyperparameters and tuning strategies for random forest. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 933::330,, 2019.
[96] R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Order preserving encryption for numeric data. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 563-574, 2004.
[97] C. Roy, B. Ding, S. Jha, W. Liu, and J. Zhou. Strengthening order preserving encryption with differential privacy. In Proceedings of the 29th ACM SIGSAC Conference on Computer and Communications Security. pages 2519-2533, 2022.
[98] M. Tschantz, S. Sen, and A. Datta. Sok: Differential privacy as causal property. In Proceedings of the 41st IEEE Conference on Symposium on Security and Privacy, pages 354-371, 2020.
[99] B. Fuller, M. Varia, A. Yerukhimovich, E. Shen, A. Hamlin, V. Gadepally, R. Shay, J. Mitchell, and R. Cunningham. Sok: Cryptographically protected database search. In Proceedings of the 38th IEEE Conference on Symposium on Security and Privacy, pages 172-191, 2017.
15

---

Algorithm 4 Decryption
Input: Tree node of BT, ciphertext [a,]
Output: plaintext 0;
while [[a]] * L.cipher, do
if [as]]I t.cipher, then
t.right
else if [[a]]] < &.cipher, then
= t.left
end if
end while
Return a; = L.samples(Dec(( [a:]]2])
A Detailed Decryption for Our Encryption Method
A.1 Decryption for Our Eneryption in Section 3.1
We present the decryption for ciphertext [a:]] = (I [a:12) in Equ. (5) by the following steps:
Find the partition Z, according to [a.]ı:
Decrypt ciphertext [a:]] by the CKKS secret key ksee and get index T Dec(Kises [a.]2) in partition Z,
Obtain the plaintext og as the r-th sample partition Ij.
A.2 Decryption for Our Encryption of Binary Search Tree in Section 3.2
We decrypt ciphertext [a.] ([a,]], [al]e) based binary search tree BT (in Section 3.2) and the CKKS secret key ksee by the following two steps, and Algorithm 4 presents the details of decryption:
Let node pointer with the initialization of the root of binary search tree BT. We then search a path downward in BT by comparing with [a,] The search continues to its left child if [a=]] < t.eipher, and update
t.left; the search continues its right child [a:]] > t.cipher, and update t = t.right until [a:]] t.cipher,.
*
Decrypt ciphertext [aa]2 by the CKKS secret key ksee, and get index T = Dec(ksses [a,]2) in t.samples. Then we use the index 7 to get the plaintext a; t.samples(T].
A.3 Formal Definition of Our Sini-imppuityypreseeee
Encryption
We present a formal definition of our Gini- imnirrtyy preserving encryption as follows:
S KeyGen(mmxx) Generate the secret state S by initializing binary search tree BT = 0. and security parameter Cmux: which is a random number with Gmax > n. We maintain an interval [imin /max] in each secret state S with min = 0 and fmx Cmax in the initial stage, so to keep ... with semi-order of plaintexts, and we have different ciphertext even for the same plaintexts.
the order of ciphertexts C1, .-. c in Eqn. (5). In this way, the ciphertexts are random numbers
S" [a.] < Encrypt( a,): Encrypt a, and update the secret state to S' as for receiving sample (a,, y:) as follows:
Search node for sample (a,, y:) in binary search tree BT as shown in Algorithm 1. Let t be a node pointer with the initialization of the root of BT. We search a path downward in BT by comparing with a, The search will terminate when is a leaf or an empty node.
Update the binary search tree BT. We directly append the example (a,, ys) into t.samples Oi V/ for every (aj: y/) t.samples; otherwise, it is necessary split the node according to a, Algorithm 2 presents the detailed descriptions on the splitting of node t.
Compute ciphertext [[u:] and update the state from S to S'. Append example (a;, y:) into 1.samples and update L.cipher, = Enc(kpuns (..ampless) We then compute the ciphertext [a.] = (t.cipher, t.cipher,), and update the state from S to S' through our BT.
16

---

a, t- Decrypt(SS, [a:]): Solve plaintext a, for ciphertext [as]] based on state S" with binary search tree BT and the CKKS secret key keec as follows:
Let t be a node pointer with initialing the root of binary search tree BT. We then search path downward in binary search tree BT by comparing with [[q]] The search continues to its left child if [a,11 < t.cipher, and update if [a:]] > t.cipher, and update t = t.right until [a,]1 t.cipher,
t.left: the search continues to its right child
Decrypt ciphertext [a:]2 by CKKS secret key kyeu and get index Dec(Hises [0:]2) in t.samples. Then we use the index 7 to get the plaintext a; t.samples(T].
B Proof of Theorem 1
Lemma 4. For dataset A ((11,1)); (an, Nn)), let I2, I,,...,, II be the corresponding partitions as defined by Eqn. (4). There exists a splitting point a* such that (c(A,a") = 1 (A) and
{max(ax: (ax, Uk) I3/2 + min(ay: (ak, Ms) E I++13/2} iE(a-1]
U
where Io(A, a*) and (A) are defined by Eqns. (1) and (2), respectively.
Proof. Without loss of generality, we assume that d1, 02 are distinct elements. Our goal is solve the optimal splitting point a" arg mingeR (Ig(A (A, a)}, and we begin with some notations used in our proof. For every label j E [r], we denote by
Vj = i E [m] 91 = f}1,
ie., the number of the label j in dataset A. Let a splitting point, which splits into left and right datasets A' and An that is,
4 {(as, Mi): as S a, (a;; yi) E A}
4 =
{(a;, y:): as a, (a:: ys) E A)
For any given a E and j E [r], we further denote by
Jf = li [m]: j.a; S a)l,
ie., the number of label j in subsets A. This follows that
(
(Vg 1/)2 | )2
Ic(A, a) wi wi
A
+ Wy
W
(n
JELT]
JE[T]
where wi = |A,,/n, and wp w/, In the following, we will explore the monotonicity of function Io(A, a) when
max (ax (ax, Mk) E I-13/2 + min(ax : (ax, ya) E 2,)/2 a < max(a (y), E I2/2 min(as (as,ya) yx) E I++ 3/2
for = 2,3, ... 8 ---1 It easy to observe that and v/ keep constants except for v/_,, where j. and denotes the label of instances in I,. It remains to discuss the variable v/., and we have
17

---

n12
1
Σ
(
2
vd
2-
1
Σ
(v3 - w/2
+
(u5 -1.)
Ov!.
w )2
W/
(w,)2
Wr
|E[r]
5E(r
2
Dj
1
Vj.
=
+ 2
Wr
jE(T
2
2
1
Vj
=
jE(
2
Vj. V/22
2
Vj.
V
+2
n
Wii
wp)
Wp
W1
1
Σ
(u/)²
(v3
v2)2
V/.
v!
V/.
v1.
V/
+
(w))
(u,))
10
ne0
is easy to observe that
Sn
and
S n for each E [7]
(14)
Wr
It is sufficient to consider two cases as follows:
We consider the first case
2
2
Vj
20,
Wr
jE(r)aidi
and this follows that
0
Σ
1
Vi
Wi
Wr.
jElT
v
Σ
Vjj
V/
Wi
Wr
W1
Wr
V!
Vj
Σ
Vj 1/
2n
2n
jElT
W1
Wr
jE(T)
Wi
Wr
We have
n
Vj
2n
Σ
(15)
Wr
jE(T)144
JE(T,,A
and it holds that Combining with Eqns. (14)-(16), we have
Vj.
(16)
Wr
wl
(Ic(A,a) 2 20. Ōnly
which proves the increasing function of (G a).
18

---

We now consider the second case
2
2
-
< <0,
jE(Flijs..
and this follows that
1/3
2
V/-
- V
wi
W4
wi
Wp
sE[r]
w/_
U/_
+
Vj.
Vj.
< 2n
3-
V/.
w1
Wr
wt
W1
101
Wr
We have
n
(lG(A,,)
1
Uj V$
2
+ 2
Vj.
50
v
0r
n
jElr
Wi
Wr)
Wr
W1
2
Vj
V/
+2
V/.
v).
D!
d-
= 0,,
W1
Wp
which proves the decreasing function of (c)
In summary, prove the piecewise monotonicity of (c,A, a) for
2 max(uu: (ak, E 2--1//2+ min (as, Uk) E I: a I max(ux: (ak, Uk) E /2// + min(as : (aR. E I,+1] 1/2,
with i 2.3..... ... 1. Moreover, easy to observe the monotonicity of IG(A, a) from v/} 0(j + j.) when
a E (-oo, (max(as (as, 0k) E I + min(as : (ak, E {I2)
and from Vi - / = 0 (j j+) when
[maxxfax (ax. yk) E I,-1} + minfax : (ax. Mee E [Z])/2, +00)
is not necessary to consider the splitting point a" > max(ax: : (ax, yk) E I.} with | = 0. as well as the splitting point a* < min(a; (ax, 9x) E I with | = 0, i.e., without splitting dataset A. This completes the proof.
Proof of Theorem
According to Lemma 6, we could find an optimal splitting point a' such that
maxfax : (ak. Uk) E IT} + min(ay (ax, yk) E Immb
a' E
U SE(s-1]
2
is easy to observe that, for E [s -1]
[A (max(ay: (ax, yu) E Ii} + min(ay (ax, yk) E 2++13/2) = Io(A, (c + (111)22).
where a is the identical ciphertext for those elements in I, and we complete the proof.
Based on Theorem 1, our encryption with binary search trees (Algorithm 1) can also preserve the minimum Gini impurity over encrypted data, which can be shown by the following theorem:
Theorem 5. We have (A) = (A), for re-sort dataset A by Eqn. (3) and for the corresponding encrypted dataset À = {[[ap)] (()))) ([ammllı B(m) } from Algorithm 1.
19

---

Proof. Our constructed binary search tree BT (Algorithm 1) maintains several samples on node. For each node t. we have t.cipher, t.right.cipher, and t.cipher, > cipher. In this way, we can obtain a monotone increasing sequence Z, I2. I. by inorder traversing the built Tree BT in Algorithm 1. Each Z for j E [s] contains several samples as follows:
I = {(x11) B(1)): (d(n))-(n))))
I = {((() (ik))))((k)) M(k +1)),, (a(ka)) 8(b2))
(17)
I. (1)
(a M(n))
where aw) < agy for (aze) m(n) E I, (00)) (e9) E I and j.
For each I, if there is only one identical label, i.e., M(a) y(e)) for every (a()))(()) (a(p) v(r))
Ij then we have (A) = (A) from Theorem 1. On the other hand, if the values are the same for all samples in Iy E (s)) i.e., (33 aw)) for every (azz). M(a)): (age), (ary)) E Ij, then this splitting
value is preserved without changing the minimum Gini-impurity of random forests. Hence, we also have (A) = (A), and this completes the proof.
C Proof of Theorem 3
".,,., and A' {{a),, ab, . their Given two sequences of distinct plaintext A {af. ag. ... ,oo) corresponding labels are randomly set as follows:
Sort A (aliy.aa (.( in ascending order, i.e., dii a/2) < alny for b {0,1}, 1}.
Set the corresponding labels (va), (()) (Wa) randomly and independently from uniform distribution on [r].
Then, have
Lemma 6. For dt < 02 < ... < an with = f0, 1}, we have the same Gini impurity for two
sequences A [(a] 11), (a 92), (0% yn)} and A {[a v1), (a y2), (a Dn)).
Proof. Let at be splitting point for b E {0, 1 and i E [ra]. and split A into left and right datasets A and A. according to af, that is,
A ot {a 31), (ah, 92). (a, v)) and A ((aa Bl+1), (af+2) V1+2), (oh 8n)3
For j E [r], denote by w/t and vz the cardinalities of subsets A and A with label j. respectively.
Then, the Gini impurity of dataset A and splitting point at given by
h2
b2
lo(A", ob)
i Σ
n
i
(n 1)2
SEIn]
JEIT]
and A For E 10, 440 og 4o
have the same labels {yz, v2. ... 9e and we have
1002
11)2
SElT]
jE(r]
Similarly, we have Σ (uj Σjen (, (ugn) and this completes the proof.
We can show that adversary can not distinguish the ciphertext of ((aaa) (d(a)>Wa)); (aln) Mon) from that of {(a)2) M()))... (at M(n)) in probabilistic perspective, i.c..
Pr (IafuyI.... ... Iag (a v()). ... (ojny (0m))Mmi)
= Pr (Ialy), ... (a way), ... (a/a) Viro))
(18)
20

---

We will prove Eqn. (18) by induction on n. We first have
For n 1, we have [ m and [ mma// with Crax mma according to the initialization in Algorithm 1. This follows that
22
Pr [oo Bas)) Pr (Ia9)]) Pr (Iotv))) Pr Bra)))
We assume that Eqn. (18) holds for = (i > 1), that is,
Pr (Io ... [af la vay), ... (alg v()))
= Pr (Io I( v(n)) ... (aty) B(x)
(19)
Let us consider the case n = i + 1. and we add the sample (d(+ M(++1y) in binary search tree BT (Algorithm 1). It is sufficient to consider two cases as follows:
If we do not need to split node for sample (d(x41y M(++1)) in Algorithm 1, then we have [nt++,y] = [1)l This is because d/1) < ((2) .... < oi--1) for b = and = 1, along with the same labels {y/,... 1/++1) }. Hence, obtain the same ciphertext for ((+1)) and 44tay i.e., 1 ciiipherr = t .cipher, This follows that
Pr [I ... [a Ia (a May), . (al) war) (ol M(t1))))))))))))))))
= Pr [a ... Ia (a v(n)) .. (a v())
and
Pr (Iaty ... [a [4 (a B(y)) .. (aty war). (a) Ma+1))
= Pr [atp ... Iats (atn vay). .. (ato) wai)
By induction assumption in Eqn. (19), we have
Pr (Ialn]l..... [afe] la (a vnn)) (al) v(s (a)+1)) (0(+11),(++1)))
Pr II Ia [ates)) v(y)) (ate) v(a) (ale41y 1((+1)))
If we need to split the node for (a (4 M(++1) in Algorithm 1, then we assume that ( and t! are the corresponding splitting nodes. We firstly initialize the empty node 1s and r., and update the ciphertext 1 .cipher, and nd .cipher, by Eqns (8)-(11), 1), respectively, Notice that the random number & in Eqns (8)-(1)) is sampled from (O, 1), and thus 1 .cipher, and (L -cipheer, are sampled from the same distribution. We have
Pr (19 (1 (iipherr [al v(y)), (olyy vi (a (o
Pr (e cipher, (ala) way), (a)))... ... (alg) v()) (((41))(6-1)))
Similarly, T .cipher, and r' .cipher are sampled from the same distribution, and we have Pr r P.cpherr M(1)). ... (afa) M(a) (o ()
Pr (f² cipher, (K vay), ... (aty win), (((41))8(0+1)))
For the (i + 1) iteration in Algorithm 1, we have
Pr (Iog)],- ..... [o [a II v(y) (ale vo) (afitz)) (aftt)))661))
Pr (Iainn ... La [1 v())
Pr (1) (f".cipher, (00 vn (ol. v1e) (al-
Pr (r".cipher, (aa Mnn) (a. v()) (a(+tn)
21

---

Table 4: Hyperparameter settings for tree ensemble models in experiments. - means that the parameter is not exist the corresponding method, and 'max bin' denotes the maximum splitting point of each feature.
Parameter
Our Work
PPD-ERTs
HEldpREss
FivetRFss
MulPRP:
AnonyRFss
DirPriRFss
Original RPs
depth
None
None
5
Nons
Nome
Nome
None
n_ I_essiiatooss max, features
100
100
100
100
100
100
100
Lvd
[vd]
[vdj
Lv
Lvd]
[vd]
[vd]
[vd]
differentia privacy level anonymization parameter mulli-party size p max_bin
and
Pr (Iaty)l.... Iaay [0 way) (atg, (()) (0/4433211
Pr [[aly]l.- .M. Ia ([ v(y) ... (()))())))))))))))))))))))))((
Pr (i' cippher [( swy) (oly v() (a (1)+
Pr (r) ciiherr [(a Mm)) (aty u()) (a ((41))))+1)))
This follows that
Pr (Ialy]l. ... Ia ( I. la I0 Ban)). (als u (a M(tt1)))
Pr (Pttatyl ..
vay)), (ata) u (a (((+1)) (((+4))-(--11)) M(+1)))
This completes the proof.
D Experimental Details
Experimental settings
We now present some details of compared methods in this work.
Original RFs": The orignal plaintext random forests [1] implemented by sklearn;
PPD-ERTs': The extremely randomized trees algorithm for learning from distributed horizontal partition data [64];
PivotRFs$: A private and efficient solution for tree- rrse-based models in a vertical federated learning setting [62], based on hybrid of threshold partially homomorphic encryption and secure multiparty computation techniques;
MulPRFs The original random forest [I] with the secure multiparty computation library MP-SPDZ [94], based on the sh2 protocol support semi-honest two-party computation:
RFss 7: The random forests based on anonymization library Mondrian, is top-down greedy data anonymization algorithm for relational dataset [59];
Dis Random forests based on differential privacy library Diffprivlib [93].
Tables 4 and 5 summarizes some hyperparameters settings in our experiments. Except for parameters 'n estimators' and 'a' in leaf splitting, other parameters set according to their respective references. We set security parameter > 6.4 according to rivacy-preserving requisites as in [89].
'The code is downloaded from github..cm//sciir com/scikir heapriii--aa///iiiiiiieeeee -laam
*The code is downloaded from wtt.:/...///mmmmmmnnaaeeeee poood
*The code is downloaded from
'The code is downloaded from wtthub.com/csire httpr/srrrmmmmiideeiiioo--eeeeee
"The code is downloaded from cetthuu.comlqiyunngoooo Mondrriaan
'The code is downloaded from Stttaat.coom/BM/dfffeeeeee privacc--l--iii---ii-birrr
22

---

Table 5: Hyperparameter setting of samples' minimum number for leaves splitting in experiments.
Parameter
wahcc
cancer
breast
diabetes
german
adver
bibtex
phpB0
pendigits
phish
10
10
10
10
10
10
aileroos
house
amazon
miniborne
covtype
100
100
100
100
100
100
100
100
Table 6: The orders of magnitude improvement compared other approaches in Figure 2. 'NA' means that no results ohtained after running out 10 seconds (about 11.6 days).
Dataset
enerypted RFs
Original RFs
AnonyRPs
DiffPrivKFs
PPD-ERTs
PivorRFs
MulPRFs
HEldpkFs
wdbc
x10
x400
cancer
x10
x10-3
x10
x1.3
x10
X
x300
breast
x10
x10
x10
x13
X30
X10
german
x10
X10-3
X10
diabetes
x10
X10
x10
X2
x15
X25
X 850
adver
X10
X
NA
bibtex
X10
x10-3
X10
NA
332
NA
phpBO
x10
X10
x10
NA
NA
NA
NA
pendigits
X10
x10
X10
phish
x10
x10
x10
X1
X 139
X X848
NA
allerons
x10
X10
X10
x31
X
NA
house
X10
x10-4
X10
X1
X31
X
NA
a9a
x10
X10
X10
X1
4
X 762
NA
X10-4
x
X10
bank
x10
X10
x10
x1.5
X 149
X220
NA
adult
X10
X10-3
X10
X211
X276
NA
mnist
X10-4
X10-4
X10-4
NA
NA
NA
minibcone
x10
x10
x10
X2
X35
NA
NA
runwalk
x10
X10
X10
covlype
x10-3
x10-3
x10
x1
NA
NA
Running Time
We give the prediction time comparisons(in seconds) for different methods as shown in Figure 4. As can see, encrypted random forests take comparable running time with original random forests, AnonyRF's and DifiPrivRFs, since our Gini-impurity preserving encryption method only requires (h) time complexity without other additional operations, where (h) denotes the height of binary search tree BT.
Furthermore, our encrypted random forests show superior efficiency compared to other methods, such as MulPRFs, PPD-ERTs, PivotRFs, and HEldpRFs, with the training time obtained 106 seconds (almost 11.6 days). This is because MulPRFs, PivotRFs, and PPD-ERTs require expensive communication costs for multi-parity computation, while HEldpRFs takes heavy computation costs on HE scheme. We also present the orders of magnitude improvement of training and prediction time in Table and Table 7, respectively.
Security
We analyze the security across fourteen datasets by randomly selecting an attribute that share similar trend other dimensions. We compare our Gini-impurity-peeerry
scheme with other four Drivacyprrotcctinn methods: differential privacy [93], anonymization [59], order-preserving scheme [96] and HE scheme [42]. The results depicted in Figure 5.
Inspired from [97], we take the bitwise leakage matrix as our metric. An initial step is scale and discretize the feature space into integers within the range of [0, 27), and then we sample 200 representative samples from each dataset to evaluate the security the feature space. The primary objective in experiment is to safeguard as many bits of the plaintexts possible. This quantitative
23

---

Table 7: The orders of magnitude improvement compared other approaches in Figure 4. 'NA' means that no results obtained after running 10 seconds (about 11.6 days).
Duraset
Our enerypted RFs
Original RPs
AnonyRes
DiffPricRes
PPD-ERTs
PivarRFs
MulPRES
HEldpRFs
wobc breast
x3
x3
x3
x38
x1, 220
x93
x4, 000
x11,
x25
X31
27
x308
x11, 631
X776
x44, 736
german
x4
X5
X4
X115
x2, 615
X421
x9, 615
diabetes
X64,
adver
x3
X4
X10
NA
x3, 821
NA
NA
biotex
x1
X1
X1
NA
x1, 528
NA
NA
php80
pendigits
X6
X6
X10
23384
X48, 947
NA
NA
phish
X6
X8
X1, 966
X1, 7619
X2,
NA
ailerons
X30,
house
X6
X9
X8
x1, 581
x30, 400
x3, 600
NA
a8a
X6
X10
X5, 482
X 000
250
NA
X64,
x7,500
bank
x14
X18
X
X5, 637
X X75,500
110, 000
NA
adult
X4
X5
X4
x1, 967
X22, 054
87,
NA
mnist
miniboone
X6
X9
x9
x1, 800
x75, 000 000
NA
NA
runwalk
x12
X18
X66
x2, 413
X84, 000
NA
NA
covtype
Our Gorenngeed I7
RS Ciganl Fix
Aeceylis
000 Praee's
200 HAMW
iEecsry
TIMAS
datasets
Figure Comparisons the prediction running time on different random forest. Notice that the y-axis in log-scale, and full black columns imply that no result was obtained after running out 10th seconds for training (about 11.6 days).
assessment is visualized through color map: the z-axis represents the individual bits (1 through 7), while the y-axis indicates the rank order of the 200 sampled datasets.
The color gradient, ranging from white to red, represents the degree of security, with white correlating to minimal security and to maximal security. The security degree was normalized within [o, 1 range to ensure results' consistency. For instance, security degree of ( with white color indicates no security, while a security degree of with red color suggests the highest level of security.
As expected, the HE scheme presents the highest security, yet with heavy computational costs. For example, datasets exceeding 3000 samples yielded no results under the HE scheme, even with an extended runtime of 10th seconds. It is also observed that our proposed scheme demonstrated superior security efficacy compared the other three scheme: differential privacy [93], anonymization [59] and order- preserving scheme [96]. Since those schemes rely on mere data perturbations, compressions, or order information preservation. comparison, our scheme makes good balance between security and computational cost.
E Proof of Bitwise Leakage
In this section, we present comprehensive evaluation of the security properties for our Gini-impurity preserving methods, full homomorphic encryption, anonymization technique, and differential privacy

---

methods. The security analysis is conducted in the feature space using the bitwise leakage matrix which is proposed by [97].
We focus on a discrete and finite feature space with a fixed size as [97]. The feature space is defined X' [0,2 2, which means that the feature size is m bits, and the space ranges from 0 to 2m
: Let D be the true distribution over the feature space, and dataset S = {a....., an are sampled independently and identically from distribution D.
The adversary A possesses two types knowledge to achieve the goal of recovering plaintexts:
Auxiliary knowledge about distribution D' over the feature space X [98], which provides additional information to the adversary.
Ciphertexts [S] corresponding S, which represents the snapshot of the encrypted data store, as described in Fuller et al. [99].
We re-sort dataset with a non-decreasing order, i.e., {a<1)> a(2)," .M
((n) where a()) S ((2) S < (nn). Let (i) be the i-th sample in S. and (i) be the j-th bit of S(i) with [n] and j [m]. Then, denote by b()) the adversary's guess for ((i) through the auxiliary knowledge distribution D' follows:
b( arg max Pro (5()))) b) - = bE(1.))
0 for for Ep (S 1/2,
< 1/2
for E [n] and j E [m]] The adversary aims to correctly guess the plaintext (()) using the auxiliary knowledge D'. Let L be n x m matrix with
((i Pr (5()) b
DD, D') for i [m] and j E [m]
Similarly to [97], we have
Prp (S(i))) = =0 Σ
PRD (5 = 8) for E [r]] and j [m]
SES
and Pro (S))) = 1) 1 Pro (5()) = 0), where 8رy denotes the j-th bit of with sg =
{s|s E and [t] 0}. This follows that
[(i,j) Pr (8(1)) DD))'
Σ
Prp (S(i) =)
aES S
The variable L(i.j) represents the probability that an adversary can accurately guess the j-th bit measure of the information security for the ciphertexts [[ in the sense that a lower value of L(i,j) signifies a higher degree of security. Specifically, the bitwise information security of [i)] can be quantified 1-L(i, and this metric provides a precise and quantitative assessment of the encryption scheme's security properties.
of the plaintext ((). This metric can be considered
Specifically, investigate the correlation among elements of L(i.)), plaintexts, ciphertexts and secret keys. We explore the impact different encryption parameters on the structure and behavior of ((. Our analysis reveals that the leakage pattern of C(i,)) j) is highly dependent the specific encryption scheme. Therefore, it is crucial to carefully design and select the appropriate encryption scheme to minimize the risk of information leakage.
We now present the analysis of bitwise leakage matrix L(i,j) for our encryption method as follows. Theorem 7. For our Gimi-impprityy-reeeevnnn encryption and plaintexts S, have
T(S(g) ) = (()))) n
L(i,)) Σ
X
Σ SES
Prp (S(i) = 8) + small constant
QE(L--Rth
Proof. Our Gini-impurity- preseriiy encryption transfers multiple plaintexts in I,r (i' E [k)) to the identical first dimension ciphertext, i.e., Gy,, as shown in Eqn. (5). Hence, the / ciphertext or corresponds to multiple plaintexts, and the adversary will guess the true plaintext S(i) of ciphertext
25

---

Dhrichrre Difirctial Arseymizaice
shene
IIII
Der ctars
Arceyrizatin Ordepee shens
Ill ctone
WEN
Geneas
Are
Corgge
Figure 5: Comparisons the security degree for the feature space through the bitwise Ieakage matrix.
Cyr. Since the adversary only knows that i' 1 ciphertexts smaller than cy and k i' ciphertexts are larger than cr, the adversary can guess the plaintext ((i) from
(S l E [i, k + :]}
with the same probability, In this way, the probability adversary guessing (i) is
I(S(a) ((i)a))
Σ
n k
gEli.n
k+b]
Let b(i) be the adversary's 's guess for S()) b)) we have
b(1) arg max Pro (S(i) =) - -{ bE(0.1)
0 for for
(S S 1/2 Ep (S(i(a) 1/2.
The probability for the adversary correctly identifies the j-th bit of the plaintext S(i) is
L(i,j) Pij
Σ
Prp (S(i) s) + small constant,
and we complete the proof from Lemma 8.
Lemma 8 (Roy et al. (97]). Let D be the input distribution and S = {ai...., .n. denotes the dataset with each data point sampled i..dd. from D, then we have
(7)
Pro (S(1)= a')=
Σ j=n-it1
(Pro (a < a')) a')) (Pro (a = a'))² for Pro (a a') = 0,
and
Prp (5(i) = = Σ (") (Pro (a = a')) (Pro (a > a'))² for Pro (a < <d) = =0;
otherwise.
Pro (S(i) = =²)=
Σ Σ
n
min(i.a-++1)
k k- k- j j+ 1) A AK-Lin-
j=1 k ma (axijj-(((j)))))
where
Ak-Lan-k-jt1 = (Pro (a < ( (Pro (a d')) (P) -
26

---

We now provide similar analysis of bitwise leakage matrix C for e-local differential privacy. Theorem 9. For c-local differential privacy, we have
L(i,j) = ( + + (S()) S + small constant,
where S and S' denotes the plaintexts and ciphertexts, respectively, and
b(i) arg max PED (8(0))) b) { if [ 1/2, bE(0,1)
if ED 1/2.
Proof. We concern c-local differential privacy by adding noise to each individual value. If the adversary attempts infer the original plaintext S(i), then it relies on the e-differential privacy disturbed data (i) and the auxiliary knowledge distribution D', The adversary guesses the j-th bit of the i-th plaintext (t through a process of deduction follows:
for b( = 1 and S (1)( = 1 for b(i) = 0 and (1 0 otherwise
randomly select from 13
This follows that
L(i,j) Pr (5(0p) = + Pr = - + small constant.
This completes the proof.
In order to gain a deeper understanding the security for the k-anonymous algorithm, we conduct an analysis of the bitwise leakage matrix L. This matrix represents the amount of information leakage that occurs when the original data X is compressed into m partitions K,, K2, Are by the
k-anonymous algorithm follows:
K1 {a(1) .((k)))
K2 (((K+1).0(k.+40 " a(kk))
K, {ask-- 1+1) ((kc)1 ((n)
The bitwise leakage matrix quantifies the amount of information that can be inferred about an individual from the corresponding partitions. By analyzing this matrix, can determine the level of privacy that maintained by the k-anonymous algorithm and identify any potential vulnerabilities that could be exploited by adversary. Then, we give the analysis of bitwise leakage matrix L for k-anonymous algorithm as follows.
Theorem 10. For k-anonymous algorithm and the plaintexts we have
L(i.j) Pr (S(1) b(i)):) + small constan, where ((11 denotes the j-th bit of (i) with S(i) E Kg [t]) and
6(0) = arg max be (0(
|m = Pro (x) FE
Σ
Proof. The k-anonymity is privacy-preserving technique that aims to protect the identity of individ- uals in dataset. It works by grouping together individuals with similar attributes and pooling their data in larger group, thus making it difficult for an adversary to identify any specific individual in the group. The k-anonymity ensures that each group has at least & individuals with the same attribute values, which further enhances the security of the data.
When the original data S(1) pooled in the group Kg E [4]), the adversary attempts to guess the j-th bit of the plaintext S ((i) using the auxiliary knowledge distribution D' and Kgp. To achieve this,
27

---

the adversary guesses b()) as the value corresponding to the maximum probability of the j-th bit in group Ky as follows:
6(0) = arg max
Σ xEKg
Mei = b) (r)
be (0.1)
This completes the proof.
28


Reviews:
[{"review_id": "mJIElasCe3", "reviewer": "Reviewer_2RPe", "summary": "This work focuses on the privacy of random forests. The authors develop a new encryption to preserve the Gini impurity of data, which plays an important role on the construction of random forests. Based on this new encryption, the authors introduce an effective algorithm for privacy random forests under the client-server protocol. Theoretical analysis is presented to guarantee the correctness and security of the proposed algorithm, and extensive experiments validates the effectiveness, efficiency and security of the proposed algorithm. In particularly, the privacy random forests take significantly better performance than previous privacy random forests via encryption, anonymization and differential privacy, and are even comparable to original plaintexts random forests without encryption. ", "questions": "1. Is the proposed method able to handle multiclass data? Does the number of classes impact the efficiency of the encryption method? If the number of classes is large, could this potentially lead to a sparsity problem?\n2. In Algorithm 1, could the selection of the parameter c_max be inappropriate and subsequently affect the ciphertext?\n3. I notice that a few methods presented in Table 1 were not included in the experimental comparisons. Could the authors elaborate on this?\n", "limitations": "The authors recognize certain constraints of their proposed method, including the security aspects highlighted in Theorem 3, and the general applicability across varying datasets as evidenced through experiments. However, I encourage the authors to review the proposed method to identify if any limitations persist, specifically those related to computational demands and sensitivity to hyperparameters.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Random forests have been one successful algorithm with diverse applications, and this work focuses on the privacy of random forests, which is an important problem and direction in machine learning. Previous methods on this issue take anonymization, differential privacy and homomorphic encryption, to preserve the privacy of random forests, whereas this work explore the data encryption from the crucial ingredients of learning algorithm, i.e., the Gini impurity for random forests. \n1.\tAn interesting encryption with some potential direction: This work proposes an interesting encryption to preserve the minimum Gini impurity, which has been a crucial ingredient on the construction of random forests. The authors also propose an interesting binary search tree for data encryption with O(logn) computational complexity, and it is suitable for real-time or online implementation. This work may motivate us some new direction on data encryption from some crucial ingredients of learning algorithm, and such research could make a bridge between machine learning and encryption. \n2.\tAn effective and efficient privacy-preserved random forests: Based on the encryption of Gini-impurity preservation, the authors present an effective and efficient privacy-preserved random forests under the client-server protocol. As can be seen in Table 1, the proposed random decision tree takes the smallest communication and computational complexities during the training and predictive process of random forests in comparisons with previous privacy-preserving decision trees.\n3.\tSome theoretical supports for proposed algorithm: The authors prove the preservation of minimum Gini impurity in ciphertexts without decryption, which plays an important role on the construction of random forests. The proposed scheme also satisfies the security against Gini-impurity-preserving chosen plaintext attack. \n4.\tGood empirical results: Extensive experiments show that the proposed encrypted random forests take significantly better performance than previous privacy random forests via encryption, anonymization and differential privacy, and are comparable to original (plaintexts) random forests without encryption. The authors also show a good balance between computational cost and data security for the proposed algorithm.\n", "weaknesses": "\n1.\tThe English presentation should be improved over the whole submission.\n2.\tThe authors could present more detailed analysis on the Gini-impurity-preserving chosen plaintext attack, with necessary background knowledge on similar security threats.\n3.\tThe authors could present the space cost of the proposed encryption algorithm, and it remains unclear whether the algorithm's memory overhead during encryption is significant, especially when dealing with large-scale datasets.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[Q1] Is the proposed method able to handle multiclass data? Does the number of classes impact the efficiency of the encryption method? If the number of classes is large, could this potentially lead to a sparsity problem?\n\n[A1] We will clarify that our method could deal with multiclass data efficiently when the number of classes is smaller than 1000, and we could use permutation and compressions techniques for more classes to reduce the sparsity problem.\n\n[Q2] In Algorithm 1, could the selection of the parameter c_max be inappropriate and subsequently affect the ciphertext? \n\n[A2] We will clarify that the parameter c_max=2^{lambda * log_2(# of plaintexts)}, where lambda >6.4 is the security parameter for ciphertexts as in (Kerschbaum et al., 2015). The larger the c_max, the better the security. It is not inappropriate to select smaller c_\\max since the ciphertext’s accuracy may exceeds the expression range of computer.\n\n[Q3] … a few methods presented in Table 1 were not included in the experimental comparisons.\n\n[A3] We will clarify that Table 3 summaries the experimental comparisons for the most representative privacy-preserving random forests in recent years, and we omit some comparisons with methods in Table 1 due to pages limitation, as well as relatively weaker performance, which has been shown by previous methods (Aminifar et al., 2021, Akavia et al., 2022).  \n\nWe will introduce Gini-impurity-preserving chosen plaintext attack with some details, present space cost, and improve this work according to your suggestions. Thank you."}, {"review_id": "IdBuTfdsdL", "reviewer": "Reviewer_Emcz", "summary": "This work focuses on security and privacy for machine learning, especially random forest and its splitting criterion, Gini impurity. In order to do that, this work proposes a new encryption scheme for features of data, which is against chosen plaintext attack. Moreover, this work utilizes a homomorphic encryption CKKS to encrypt labels of data for secure random forests model.\n", "questions": "1. In section 4, authors mention [50, 72, 76, 77]. Since they relate to this work, do authors consider to update asymptotical analysis in table 1?", "limitations": "1. Chosen plaintext attack somehow is not sufficient in the real world application. If the work can guarantee chosen ciphertext attack, it could be a stronger scheme.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. In Table 1, this work shows comparisons of asymptotical analysis on training/predictive communication/computation cost and demonstrates their work has advantages over other existing approaches.\n2. As shown in Table 3, this work uses a lot of datasets to compare with existing approaches to convince audience on this approach in practice.\n3. BST encryption avoids computationally expensive sorting.", "weaknesses": "1. Instead of putting proofs in appendix. It is better to use few sentences about how to prove theorems.\n2. This work is lack of a related work section to walk through existing work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[Q1] In section 4, authors mention [50, 72, 76, 77]. Since they relate to this work, do authors consider to update asymptotical analysis in table 1?\n\n[A1] We will clarify that our asymptotical analysis includes [50] in table 1, but does not include [72,76,77], since [76,77] only focuses on prediction without training, while [72] only studies order-preserving scheme without tree training and prediction. We will update relevant asymptotical analysis in table 1 as follows:\n\n\n\n|Scheme|Training |communication | Training comp. |complexity|Predictive  |communication|Predictive comp. |complexity | Model privacy  |\n|  :----: | ----:  |   :---- | ----: |  :----| ----: | :----| ----: |  :---- |:----: |\n|    |  Rounds |  Bandwidth |  Client&emsp;  |  Server |     Rounds | Bandwidth |    Client &emsp;  |  Server |  |\n|[72] |  $×$  &emsp; |  &emsp; $×$ | $×$  &emsp;  |  &emsp;  $×$  | $×$   &emsp; | &emsp;   $×$ | $×$  &emsp; | &emsp;    $×$ |  $×$|\n|[76]|  $×$   &emsp; |  &emsp;  $×$ |  $×$    &emsp;| &emsp;   $×$ |  $O(1)$    &emsp; |  &emsp; $O(1)$   | $O(1) $   &emsp;|  &emsp;   $O(κ) $  |  $√$ |\n|[77] |  $×$   &emsp; |  &emsp;   $×$   |  $×$    &emsp; |  &emsp;  $×$   | $ O(1) $ &emsp; |   &emsp; $O(1) $   | $O(1)$   &emsp; | &emsp;    $O(κ)$   |   $ √ $|\nour  |  $O(h)$  &ensp; | &ensp;  $O(κ\\bar{ȷ})$  |  $O(κ) $  &ensp; | &ensp; $O(κ\\bar{ȷ}τn)$ |  $O(1)$ &emsp;  |  &emsp;    $O(1) $ | $O(1) $ &emsp;|  &emsp;  $O(h)$    |  $√$ |\n\nOur method takes smaller computational complexity (O(h)) in server since h<κ. \n\n[Q2] Chosen plaintext attack somehow is not sufficient in the real world application. If the work can guarantee chosen ciphertext attack, it could be a stronger scheme.\n\n[A2] We will clarify that our chosen plaintext attack is a tradeoff between security and computation cost, and we can present the chosen ciphertext attack by modifying Alg. 2, motivated by Boldyreva et al. (2012). The basic idea is to introduce additional random perturbations and split each I_i in Alg. 2, whereas this yields expensive computational and space costs for encrypting and training.\n\nWe will add a section to introduce relevant work, and present the proof sketches for main theorems according to your suggestions. Thank you."}, {"review_id": "CMHwIexqbo", "reviewer": "Reviewer_1ntL", "summary": "This work investigates the privacy-preserving random forest, and the main contributions include an interesting property-preserving encryption method that can preserve data’s Gini impurity. Based on the proposed encryption method, the authors present an innovative privacy-preserving training and prediction algorithm for random forests in a client-server protocol, which can achieve the smallest communication and computational complexities in comparison with prior works. The method is supported by theoretical results, which provide justifications to preserve data’s Gini impurity and showed that the proposed algorithm is secure against Gini-impurity-preserving chosen plaintext attack. Finally, extensive experiments on various datasets are conducted to demonstrate the efficacy, efficiency, and security of the proposed method.", "questions": "-\tHomomorphic encryption is used to encrypt labels, and it is known that homomorphic encryption has a high computation overhead; does this impact the efficacy of the proposed method?\n-\tAs shown in Table 3, the proposed encrypted random forests perform better than the original random forests on two datasets. Can you provide explanation for the improved efficacy on these datasets?\n-\tCan the proposed Gini-impurity-preserving encryption method be extended to Gini index or information gain?\n-\tIn Algo. 1 , will the selection of $c_{max}$ impact the security of proposed method? \n", "limitations": "The authors have mentioned the limitations in security of the proposed method, such as the encryption method is secure against Gini-impurity-preserving chosen plaintext attack, and the server is honest-but-curious. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well-written and easy to follow. It provides novel algorithms and solid theories with encouraging empirical results. The main idea of designing new encryption algorithm for decision trees that can preserve minimum Gini impurity is interesting and convincing for me.\n\n- Novel perspective on privacy-preserving machine learning. This paper introduces a novel perspective on privacy-preserving random forest by focusing on preserving minimum Gini impurity in encryption, since Gini impurity is exactly the information that random forests require during training and inference. This sheds new insights into the design of privacy-preserving machine learning algorithms with corresponding new property-preserving encryption methods, which is worthy of systemic further study for the potential enhancement of the efficacy and accuracy of privacy computing.\n- Innovative solution with solid analysis. The idea of the proposed minimum Gini impurity preserving encryption is innovative and interesting. It uses a new binary search tree to encrypt data dynamically by incorporating labels’ information, which is a novel way to encrypt data for decision trees, and the proposed encryption method incurs little additional computational cost.  The communication complexity, security and the correctness of proposed method are also well-analysed.\n- Well-founded experiments results. The empirical study provide accuracy and running time comparisons with various relevant methods, as well as a visual analysis of security. The encouraging result shows that the proposed method can effectively achieve a better balance among accuracy, communication, running time and data security.\n", "weaknesses": "Despite many strengths, there are several points where certain details could be further improved.\n\n-\tThe paragraph about ``Gini-impurity-preserving chosen plaintext attack’’ feels somewhat abstract. As it relates to the security analysis of proposed method, additional explanation could help reduce the reading difficulty for readers. Including a more detailed explanation in appendix might make this critical point more accessible.\n-\tThe interpretation of Figure 3 and the bitwise leakage matrices is a little confusing to me. It is not very clear to me what is the intuition of such matrices. It may be beneficial to provide a brief introduction on it to help readers comprehend Figure 3 more easily.\n-\tThe introduction about homomorphic encryption and CKKS seems to be brief. More details may be provided in appendix for readers unfamiliar with homomorphic encryption.\n-\tIn Figure 6 from the appendix, the ``Differential Privacy’’ at the top is blocked by the figure of bitwise leakage matrices.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[Q1] Homomorphic encryption is used to encrypt labels … high computation overhead … does this impact the efficacy of the proposed method?\n\n[A1] We will clarify that the encrypt labels (by homomorphic encryption) are only used for majority voting in random forests, and it does not require bootstrapping in HE without high computations due to 3-depth homomorphic multiplicative. In contrast, Previous HE work (Wu et al., 2020; Akavia et al., 2022) requires expensive computation costs for bootstrapping during training and prediction.\n\n[Q2] … Table 3, the proposed encrypted random forests perform better than the original random forests on two datasets…explanation…\n\n[A2] We will clarify that our method could achieve better performance as for some noisy datasets, since we encrypt different plaintext features into one ciphertext feature, and this could improve data robustness to noise. \n\n[Q3] Can the proposed Gini-impurity-preserving encryption method be extended to Gini index or information gain?\n\n[A3] We will clarify that our Gini-impurity-preserving encryption can be generalized to other information-theoretic statistics such as Gini index or information gain, and the key problem is to show the piecewise monotonicity of information statistics w.r.t. splitting point.\n\n[Q4] In Algo. 1 , will the selection of c_{max} impact the security of proposed method? \n\n[A4] We will clarify that we select c_{max}=2^{lambda * log_2(# of plaintexts)} with lambda >6.4 as done in (Kerschbaum et al., 2015), while a smaller c_{max} does not guarantee ciphertext’s accuracy within expression range of computer.\n\nWe will provide more details on CKKS, Gini-impurity-preserving chosen plaintext attack and bitwise leakage matrices, and improve Figure 6 according to your suggestions. Thank you. "}, {"review_id": "FbHoM3Ebdq", "reviewer": "Reviewer_B6q6", "summary": "This work develops a new encryption to maintain the data's Gini impurity and combines it with CKKS to perform random forests training and predicting, which outperforms other SOTAs in terms of the trade-off between latency and security level.", "questions": "same with weakness", "limitations": "same with weakness", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper gets solid technique details and corresponding theoretical proof.\n2. The author gives extensive experiment results and a wide range of datasets which shows the scalability of the proposed methods. ", "weaknesses": "1. One weakness would be the limited application scenario. It would be better to have some variants for other applications. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[Q1] One weakness would be the limited application scenario. It would be better to have some variants for other applications.\n\n[A1] We will clarify that our work takes the first step on encryption by incorporating some learning ingredient, i.e., Gini impurity, and we can present some variants such as gini index and information gain, where the key idea is to show the piecewise monotonicity of information statistics w.r.t. splitting point. Those schemes can be applied to more learning scenarios such as Boosting, GBDT, LightGBT, etc.\n\nWe will improve this work according to your suggestions. Thank you."}, {"review_id": "m4civcpoKW", "reviewer": "Reviewer_PTBU", "summary": "This paper presents a novel encryption mechanism for isolation forest algorithms that preserves the Gini impurity metric. The authors provide theoretical evidence demonstrating that the proposed mechanism effectively preserves the Gini impurity and withstands attacks. Additionally, the authors have conducted comprehensive experiments to evaluate the accuracy and security of the proposed mechanism.", "questions": "Based on the concerns regarding the unsolid theoretical guarantee and unclear writing, it seems that the current version of the paper may not be suitable for publication in NeurIPS. While the paper presents interesting results, addressing these issues is crucial for ensuring the quality and suitability of the paper for a prestigious conference like NeurIPS. It is recommended that the authors revise and improve the theoretical guarantee and clarity of the writing before considering submission to NeurIPS or any other reputable publication venue.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 3, "strengths": "This paper presents novel and intriguing findings. The proposed encryption mechanism is innovative, and the experiments conducted seem to be extensive and thorough. Additionally, the experimental results demonstrate the promising performance of the proposed mechanism in terms of both accuracy and security.", "weaknesses": "1.  It appears that there are concerns regarding the solidity of the proof for the theoretical guarantee in the security analysis (Theorem 3). After reviewing the proof provided in the appendix, it is evident that the proof relies on experimental analysis utilizing different random seeds rather than a traditional mathematical proof. This raises questions about the rigorousness of the proof and its validity.\n\n2. The paper requires improvement in terms of writing quality. In addition to the listed typos and grammar mistakes below, it is advisable for the authors to provide more background knowledge to enhance the reader's understanding. Furthermore, I suggest that the authors explain the motivation behind the proposed mechanism (Equations (4) and (5)) using a more informal language to aid comprehension.\n\nI have noticed some typos and grammar mistakes in the abstract and introduction sections. However, I also observed grammar errors throughout the entire paper. \n  1. Line 1, \"algorithms\" should be ``algorithm\".\n   \n  2. Line 3, \"from anonymization\" might be \"such as anonymization\".\n\n  3. Line 4, \"it rarely takes into account\" should be changed to \"they rarely take into account\". \n\n  4. Line 8, \"encrypt data features\" should be changed to \"encrypt the data features\".\n\n  5. Line 14, \"effectiveness, efficiency and security\" should be changed to \"effectiveness, efficiency, and security\".\n\n  6. In the first sentence (Line 16), \"one successful ensemble algorithms\" should be ``one successful ensemble algorithm\".\n\n  7. Line 30, \"cryptosystems\" should be \"cryptosystem\".\n\n  8. Line 22, \"ingredients\" should be \"ingredient\".\n\n  9.  Line 61, \"Given encryption function\" should be \"Given an encryption function\". \"and decryption function\" should be \"and a decryption function\". \"HE scheme\" should be \"the HE scheme\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[Q1] … regarding the solidity of the proof for the theoretical guarantee in the security analysis (Theorem 3) … the proof relies on experimental analysis utilizing different random seeds rather than a traditional mathematical proof. This raises questions about the rigorousness of the proof and its validity.\n\n[A1] We will clarify that Theorem 3’ proof follows the cryptographic framework (Kerschbaum et al., 2015), which shows that Algorithm 1 yields the same ciphertext for any random seed and for any plaintext sequences {a_i^0} and {a_i^1}, which does not rely on experimental analysis. We can also present a traditional mathematical proof with rigorousness, inspired by Popa et al. (2013). The basic idea is to prove that, by induction on n, \n$P({[a_0^0] ,…,[a_i^0]}|{a_0^0,...,a_i^0}) =P({[a_0^1],…,[a_i^1]}|{a_0^1,...,a_i^1}) &ensp;for &ensp;i=0…n$,\nand then restrict an attacker's ability of accurate guess to a chance of success no more than 1/2. Here, $[a]$ denotes the ciphertext of $a$.\n \n\n[Q2]  I suggest that the authors explain the motivation behind the proposed mechanism (Equations (4) and (5)) …\n\n[A2] We will clarify that our motivation is that the Gini impurity does not changed by encrypting adjacent plaintexts with the same label into an identical value, which can be shown in Theorem 1. Hence, Eqn. (4) sorts and partitions plaintexts into different groups based on label information, and Eqn. (5) encodes different values within each group into the same ciphertext.\n\nWe will improve the writing quality, and provide more background knowledge according to your suggestions. Thank you."}]

Author rebuttal:

Meta-review: The paper presents an innovative approach to privacy-preserving random forests by introducing a new encryption scheme that maintains the Gini impurity metric. 

The key strengths highlighted by reviewers include that  1). The paper targets pressing challenges in the realm of privacy and machine learning; 2). The proposed encryption scheme and its integration with random forests is a novel contribution; 3). The method's effectiveness is evident both through empirical demonstrations and supported by theoretical findings.

Given the overwhelmingly positive feedback from reviewers and the important niche the paper fills, AC recommends accepting this paper.

To enhance the overall quality of the paper, authors are strongly encouraged to revise their paper according to reviewers' detailed feedback, particularly regarding typographical errors and any unclear claims.
Decision: Accept (spotlight)