# Securely Outsourcing ID3 Decision Tree in Cloud Computing

Authors: Ye Li; Zoe L. Jiang; Xuan Wang; Junbin Fang; En Zhang; Xianmin Wang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

With the wide application of Internet of Things (IoT), a huge number of data are collected from IoT networks and are required to be processed, such as data mining. Although it is popular to outsource storage and computation to cloud, it may invade privacy of participants’ information. Cryptography-based privacy-preserving data mining has been proposed to protect the privacy of participating parties’ data for this process. However, it is still an open problem to handle with multiparticipant’s ciphertext computation and analysis. And these algorithms rely on the semihonest security model which requires all parties to follow the protocol rules. In this paper, we address the challenge of outsourcing ID3 decision tree algorithm in the malicious model. Particularly, to securely store and compute private data, the two-participant symmetric homomorphic encryption supporting addition and multiplication is proposed. To keep from malicious behaviors of cloud computing server, the secure garbled circuits are adopted to propose the privacy-preserving weight average protocol. Security and performance are analyzed.


---

## Body

## 1. Introduction

In the modern Internet of Things (IoT), huge data are collected from sensor-networks and need to be provided for analysis by high-effective techniques, such as data mining. This process requires enormous computation and storage to support; cloud computing technology can provide the corresponding support. However, this process may leak the privacy of participants’ information. The privacy-preserving data mining (PPDM) based on encryption method has emerged as a solution to this problem.Privacy-Preserving Data Mining Framework.Considering different frameworks and theories, PPDM was originated by Lindell et al. [1] and Agrawal et al. [2] in 2002, respectively. Lindell’s framework is essentially a secure cryptography-based two-participant computation protocol without outsourcing. In other words, two parties can interactively compute (x1+x2)ln(x1+x2) on their private input x1 and x2. Agrawal’s framework is essentially a single-participant disturbance-based data storage and computation outsourcing algorithm. In particular, one party can upload disturbed data to server for private computation. With the development of cloud computation and IoT, a multiparty storage and computation outsourcing framework is preferred.Cryptography-based privacy-preserving data mining supporting one-party outsourcing has been studied [3, 4], with homomorphic encryption. However, multiple-key homomorphic encryption is an open problem when multiple parties are involved in the outsourcing framework. For example, how to execute ciphertext addition and multiplication on ciphertexts encrypted by different public keys?Security Models.We usually consider two different security models, including the semihonest and malicious security model. The definition in the semihonest model requires that all the users need to follow the rules of protocol. But we allow the dishonest users to obtain internal states of the other users. In the malicious model, different from the first security model, the corrupted users are allowed to deviate from the specified protocol. The success of the adversary means that the adversary can get the results of these protocols.Data Distribution.Three types of distributed datasets are defined in related works, including the horizontally distributed datasets, vertically distributed datasets, and arbitrarily distributed datasets. The users in the horizontally distributed dataset can keep divided parts for the same attributes. However, in the vertical datasets, users are allowed to keep different attributes. In the last one, the datasets can be arbitrarily divided and stored by the users.Due to the existence of malicious participants in the real environment, malicious participants may not follow the protocol. For example, they can intentionally tamper with the data, suspend the protocol anytime during the execution of the protocol, and so on. To solve this problem, this paper combines the noncontact commitment and confusion circuit mechanism, studies the average computing protocol based on confusion circuit, and then proposes the framework of a secure cryptography-based two-participant protocol with data storage and computation outsourcing. The framework consists of two data owners and two cloud servers (cloud storage server (CSS) and cloud computing server (CCS)). Each data owner has a horizontally distributed private database that is encrypted before being outsourced to the cloud for storage and computation.


### 1.1. Our Contribution

We decompose the key function of distributed ID3 decision tree,Gain(S,Ai), into counting, (x1+x2)/(a1+a2), sum, multiplication, and comparison.In counting, we propose the Secure Equivalent Testing (SET) protocol to calculate the number of items for each attribute value based on the encrypted data.To calculate the value of(x1+x2)/(a1+a2) in malicious model, we implement the Outsourcing Secure Circuit (OSC) protocol.To perform the sum and multiplication operations over ciphertext, we adopt the Paillier encryption system and implement the Secure Multiplication (SM) protocol.To execute comparison over ciphertext, we adopt the Secure Minimum out of 2 Numbers (SMIN2) protocol.


### 1.2. Related Work

Distributed PPDM without Outsourcing.Distributed PPDM without outsourcing is mainly for data stored and calculated locally by the participant, based on distributed data based on various data mining methods, which can be decomposed to different operations, such as average calculation, calculation, and calculation of logarithmic vector inner product. Then the cryptography-based technology is used to design various privacy-preserving computing protocols. In 2002, Lindell and Pinkas [1] proposed a secure ID3 decision tree algorithm over horizontally partitioned data. They decompose the distributed ID3 algorithm to multilogarithmic calculation, polynomial evaluation calculation, and data comparison, and then designed the security log protocol, polynomial evaluation protocol, and secure comparison protocol, so as to achieve privacy-preserving in distributed ID3 algorithm. In 2007, Emekci et al. [5] implemented a secure addition computational protocol based on the secret sharing algorithm and extended the secure logarithmic computing protocol from two parties to multiple parties; thus realizing the multiparty participation of the privacy protection ID3 method. However, the complexity of the algorithm increases exponentially when the participant data are more numerous. In 2012, Lory et al. [6] used Chebyshev polynomial expansion to replace Taylor expansion in [1], thus further improving the computational efficiency of secure logarithmic computing protocols. However, their agreements still have limited efficiency in the implementation of privacy protection protocols.Different from above, in 2003, Vaidya et al. [7, 8] designed a multiparty privacy-preserving ID3 algorithm of vertically distributed data sets. They vectorized all attribute value information by constructing constraint sets and then computed it by using the method of secure intersection protocol, thus designing privacy-preserving ID3 for vertically distributed data sets.In 2007, Han and Ng [9] proposed a multiparty distributed privacy-preserving ID3 method based on arbitrary distributed data sets. Firstly, each participant’s data set is vectorized, and then the attribute value information is computed by using security intersection protocol and so on. Then, the entropy value of each attribute is computed by using security logarithm computation protocol and so on. Thus, the ID3 decision tree classification method of privacy protection based on arbitrary distributed data set is obtained. However, with the increase of the number of participants, the computing volume of the client increases exponentially.Li et al. [10] and Gao et al. [11] addressed the Naive Bayes Learning for aggregated arbitrary distributed databases.PPDM with Computation Outsourcing.Cryptography-based privacy-preserving data mining has a lot of encryption and decryption operations in the computation process. Therefore, it is difficult for large-scale data processing. As a measure for solving resource-restricted problems, the outsourcing technique has been widely used in cloud computing applications, such as data sharing [12, 13], data storing [14, 15], data updating [16, 17], and social network analysis [18, 19]. In this context, we need to rely on security outsourcing technology to outsource computing or storage tasks of all participants to the cloud to process, thus greatly reducing the computing/storage load of each participant. In 2014, Liu et al. [3] adopted a new encryption scheme that supports both addition and multiplication over cipher texts. In this scheme, most of the computations are performed on the cloud, which reduces the computation workload of the data owner. However, the scheme is limited to a single party’s data mining operation. Chen et al. [20] designed new algorithms for secure outsourcing of modular exponentiations. In 2015, Bost et al. [21] proposed the privacy-preserving hyperplane decision, Naive Bayesian, and decision tree classification algorithms, and through the semihonest model, secure two-party computation model to prove that the above scheme can satisfy the semantic security (Semantic Security); and the related protocol makes it possible to design an adaptive enhancement algorithm (Adaptive Boosting) combine to further enhance the accuracy of the algorithm; building a classifier can be used to construct the privacy protection of the library, the further development of the classification algorithms for privacy-preserving technology in the future lays a solid foundation.PPDM with Multiparticipant Data Storage and Computation Outsourcing.In 2013, Peter et al. [22] proposed a new solution for the outsourcing of multiparty computation. Such a technique can be used in our setting. But as the security analysis in the previous works, they can only achieve security in the semihonest model. In [23], a new protocol was proposed to achieve data mining for two parties. In [24], association rule mining was addressed in the malicious model. In [25], the privacy-preservingKNN classification was addressed. In [26], the deep learning task was addressed. Besides the above related work, several fundamental secure algorithms, such as dynamic homomorphic encryption [27, 28], authentication [29, 30], and light-weight multiparty computation [31], which have also been considered in the malicious model, have been proposed. However, to the best of our knowledge, no existing study has considered a method for outsourcing computation in the malicious model.In this study, the secure outsourcing of ID3 data mining is considered in the malicious model for the cloud environment. We show how to solve the outsourcing problem for ID3 protocol over horizontally partitioned data.


## 1.1. Our Contribution

We decompose the key function of distributed ID3 decision tree,Gain(S,Ai), into counting, (x1+x2)/(a1+a2), sum, multiplication, and comparison.In counting, we propose the Secure Equivalent Testing (SET) protocol to calculate the number of items for each attribute value based on the encrypted data.To calculate the value of(x1+x2)/(a1+a2) in malicious model, we implement the Outsourcing Secure Circuit (OSC) protocol.To perform the sum and multiplication operations over ciphertext, we adopt the Paillier encryption system and implement the Secure Multiplication (SM) protocol.To execute comparison over ciphertext, we adopt the Secure Minimum out of 2 Numbers (SMIN2) protocol.


## 1.2. Related Work

Distributed PPDM without Outsourcing.Distributed PPDM without outsourcing is mainly for data stored and calculated locally by the participant, based on distributed data based on various data mining methods, which can be decomposed to different operations, such as average calculation, calculation, and calculation of logarithmic vector inner product. Then the cryptography-based technology is used to design various privacy-preserving computing protocols. In 2002, Lindell and Pinkas [1] proposed a secure ID3 decision tree algorithm over horizontally partitioned data. They decompose the distributed ID3 algorithm to multilogarithmic calculation, polynomial evaluation calculation, and data comparison, and then designed the security log protocol, polynomial evaluation protocol, and secure comparison protocol, so as to achieve privacy-preserving in distributed ID3 algorithm. In 2007, Emekci et al. [5] implemented a secure addition computational protocol based on the secret sharing algorithm and extended the secure logarithmic computing protocol from two parties to multiple parties; thus realizing the multiparty participation of the privacy protection ID3 method. However, the complexity of the algorithm increases exponentially when the participant data are more numerous. In 2012, Lory et al. [6] used Chebyshev polynomial expansion to replace Taylor expansion in [1], thus further improving the computational efficiency of secure logarithmic computing protocols. However, their agreements still have limited efficiency in the implementation of privacy protection protocols.Different from above, in 2003, Vaidya et al. [7, 8] designed a multiparty privacy-preserving ID3 algorithm of vertically distributed data sets. They vectorized all attribute value information by constructing constraint sets and then computed it by using the method of secure intersection protocol, thus designing privacy-preserving ID3 for vertically distributed data sets.In 2007, Han and Ng [9] proposed a multiparty distributed privacy-preserving ID3 method based on arbitrary distributed data sets. Firstly, each participant’s data set is vectorized, and then the attribute value information is computed by using security intersection protocol and so on. Then, the entropy value of each attribute is computed by using security logarithm computation protocol and so on. Thus, the ID3 decision tree classification method of privacy protection based on arbitrary distributed data set is obtained. However, with the increase of the number of participants, the computing volume of the client increases exponentially.Li et al. [10] and Gao et al. [11] addressed the Naive Bayes Learning for aggregated arbitrary distributed databases.PPDM with Computation Outsourcing.Cryptography-based privacy-preserving data mining has a lot of encryption and decryption operations in the computation process. Therefore, it is difficult for large-scale data processing. As a measure for solving resource-restricted problems, the outsourcing technique has been widely used in cloud computing applications, such as data sharing [12, 13], data storing [14, 15], data updating [16, 17], and social network analysis [18, 19]. In this context, we need to rely on security outsourcing technology to outsource computing or storage tasks of all participants to the cloud to process, thus greatly reducing the computing/storage load of each participant. In 2014, Liu et al. [3] adopted a new encryption scheme that supports both addition and multiplication over cipher texts. In this scheme, most of the computations are performed on the cloud, which reduces the computation workload of the data owner. However, the scheme is limited to a single party’s data mining operation. Chen et al. [20] designed new algorithms for secure outsourcing of modular exponentiations. In 2015, Bost et al. [21] proposed the privacy-preserving hyperplane decision, Naive Bayesian, and decision tree classification algorithms, and through the semihonest model, secure two-party computation model to prove that the above scheme can satisfy the semantic security (Semantic Security); and the related protocol makes it possible to design an adaptive enhancement algorithm (Adaptive Boosting) combine to further enhance the accuracy of the algorithm; building a classifier can be used to construct the privacy protection of the library, the further development of the classification algorithms for privacy-preserving technology in the future lays a solid foundation.PPDM with Multiparticipant Data Storage and Computation Outsourcing.In 2013, Peter et al. [22] proposed a new solution for the outsourcing of multiparty computation. Such a technique can be used in our setting. But as the security analysis in the previous works, they can only achieve security in the semihonest model. In [23], a new protocol was proposed to achieve data mining for two parties. In [24], association rule mining was addressed in the malicious model. In [25], the privacy-preservingKNN classification was addressed. In [26], the deep learning task was addressed. Besides the above related work, several fundamental secure algorithms, such as dynamic homomorphic encryption [27, 28], authentication [29, 30], and light-weight multiparty computation [31], which have also been considered in the malicious model, have been proposed. However, to the best of our knowledge, no existing study has considered a method for outsourcing computation in the malicious model.In this study, the secure outsourcing of ID3 data mining is considered in the malicious model for the cloud environment. We show how to solve the outsourcing problem for ID3 protocol over horizontally partitioned data.


## 2. Preliminaries

In this section, we present a brief overview of the preliminaries used in this paper, including the ID3 decision tree algorithm, Paillier’s homomorphic encryption scheme, and the other related protocols.


### 2.1. Distribute ID3 Decision Tree Algorithm

The ID3 algorithm description is given as follows. It builds a decision tree in a top-down manner with the information of samples. Starting at the root, the best object classification will be obtained. The best prediction is computed with theinformation gain. Theinformation gain of an attribute At is defined as(1)GainS,At=EntropyS-∑atj∈AtSatjSEntropySatjAssume that there are 2 parties,P=Pi∣i=1,2, with 2 databases, S=Si∣i=1,2. Each party Pi has one database Si. All databases share the same general attribute (column) set A=At∣t=1,2,..,p and each attribute At has several general discrete attribute values, denoted by At=atj∣j=1,2,…,mt, and one class attribute C=cj∣j=1,2,...,m.Without considering privacy, each partyPi shares his own Satjcji,Satji and Scji to all other parties. As a result, any party can calculate Entropy(S) and Entropy(Satj).(2)EntropyS=∑j=1m-ScjS⁡log2⁡ScjS=∑j=1m-∑i=1nScjiSlog2⁡∑i=1nScjiSwhereScj is the subset of S with tuples that have value cj for class attribute C. Scji equals the set of transactions with class attribute C set to cj in database Si.Then the value ofEntropySaj can be calculated as(3)EntropySatj=∑j=1mt-∑i=1nSatjcji∑i=1nSatji·log2⁡∑i=1nSatjcji∑i=1nSatjiwhereSatjcj is the subset of S with tuples that have values aj for attribute At and cj for class attribute C.Therefore, (3) can be easily computed by party Pi and parties Pjj≠i all of the values Satji and Satjcji from its database. Each party Pj then sums these together with the values Satjj and Satjcjj from its database and completes the computation.Then each party can calculateGainS,At value at its own side.


### 2.2. Paillier’s Homomorphic Encryption Scheme

Homomorphic encryption is a special type of encryption in which the result of applying a special algebraic operation to plain texts can be obtained by applying another algebraic operation (which may be different or the same) to the corresponding ciphertexts. Thus, even when the user does not know the plain texts, he/she can still obtain the results of applying that algebraic operation to the plain texts.Letm1 and m2 be two plain texts with encryptions E(m1) and E(m2), respectively.The Paillier encryption scheme [32] is described as follows: (4)Em1⊕Em2=Em1+m2


### 2.3. Li’s Symmetric Homomorphic Encryption Scheme

The description of symmetric homomorphic encryption scheme proposed by Li et al. [33] is as follows.(i)
KeyGen():(5)s,q,p⟵KeyGenλKeyGen() is used to generate key for users as SK=(s,q). p and q are primes with the condition that p≫q. s is chosen from ZN∗.(ii)
Encsk():(6)Encskm,d=sdrq+mmodp.d is a small positive integer, which is denoted asciphertext degree in this paper.(iii)
Decsk():(7)Decskc,d=c×s-dmodpmodq.


#### 2.3.1. Properties of the Proposed Homomorphic Encryption

Homomorphic Multiplication.Let c1, c2 be the ciphertexts of two plaintexts m1, m2. Then we have c1=sd1(r1q+m1)modp and c2=sd2(r2q+m2)modp for some random ingredients r1 and r2. And we can obtain that(8)c1×c2modp=sd1r1q+m1modp×sd2r2q+m2modp=sd1+d2r1r2q+r1m2+r2m1q+m1×m2modp=Encskm1×m2,d1+d2.Homomorphic Addition (9) c 1 + c 2   m o d  p = s d r 1 q + m 1   m o d  p + s d r 2 q + m 2   m o d  p = s d r 1 + r 2 q + m 1 + m 2   m o d  p = E n c s k m 1 + m 2 , dReaders may refer to [18] for details on the scheme.


### 2.4. Garbling Scheme

A garbling scheme [34] consists of four algorithms, which is denoted by G=(Gb,En,De,Ev). f can be transformed by Gb into (F,e,d). Note that F is the garbled circuit. The encoding and decoding information algorithms are denoted by e,d. The output of garbled Y can be encrypted and get the result y=De(d,Y).


### 2.5. Noninteractive Commitment

A noninteractive commitment scheme [35] is also required in our paper, denoted by (Comcrs,Chkcrs). The distribution of Comcrs(x;r) is determined by the value of r as Comcrs(x).


### 2.6. Basic Cryptographic Subprotocols

In this section, we present a set of cryptographic subprotocols that will be used as subroutines when constructing the proposed protocol.


#### 2.6.1. Outsourcing Secure Comparison Protocol (OSCP)

The value ofm is kept secure from the cloud and users. The value of c=E(mmodq) is computed. SK is kept by the data owner (Algorithm 1).Algorithm 1:Secure outsourcing comparison (OSCP).
1. The computation at Data owner: Compute τ=Encsk(1) for the cloud. 2. The computation at cloud: u , v are chosen such that u ≫ v v ≫ max ⁡ ( α , β ) ( q - 1 ) 2 ≫ β × u + v - α × u + v ≫ - ( q - 1 ) 2 3. The cloud compute the following value for the data owner: Φ = c u + τ v   m o d  p, and sends Φ. 4. Data Owner computes the following values: φ = D e c s k ( S K , Φ , d ) = ( m × u + v )   m o d  q, and comparesφ with (q-1)/2. Ifφ<q-1/2,m≥0. Otherwise, m<0.


#### 2.6.2. Secure Equivalent Testing Protocol (SET)

With two ciphertextsc1=Encsk(m1) and c2=Encsk(m2),SET is to compute f and decide if the plaintexts are identical (m1=m2) (Algorithm 2).Algorithm 2:Secure equivalent testing protocol (SET).
Two ciphertext are computed by the cloud asc1=Encsk(m1) and c2=Encsk(m2). 1. The cloud computesc00=Encsk(m00)=c1-c2 and c01=Encsk(m01)=c2-c1. 2. Check ifm00≥0 or m01≥0 and computes ifm00≥0∧m01<0, f0=1,f1=0. else if m00<0∧m01≥0, f0=0,f1=1. 3. The value off is computed as follows: f = f 0 ⊕ f 1. Iff=0, set m1=m2.


#### 2.6.3. Secure Multiplication Protocol (SMP)

The algorithm is described as in Algorithm3.Algorithm 3: S M ( E p k ( x ) , E p k ( y ) ) → E p k ( x y ).
The values are computedEpk(x) and Epk(y); P keeps (pk,sk). 1.C: ( a ) Choose rx,ry∈ZN ( b )  x′←Epk(x)Epk(rx), y′←Epk(y)Epk(ry) ( c ) computes and sends x′,y′ to P 2.P computes: ( a )  hx←Dsk(x′), hy←Dsk(y′), h←hxhy mod N, h′←Epk(h) ( b ) The value of h′ is sent to C 3.C computes: ( a )  s←h′Epk(x)N-ry, s′←sEpkyN-rx ( b )  Epk(xy)←s′EpkrxryN-1


#### 2.6.4. Secure Minimum out of 2 Numbers Protocol (SMIN2)

The algorithm is described as in Algorithm4.Algorithm 4:Secure Minimum out of 2 Numbers Protocol (SMIN2).
1.C: ( a ) The function is chosen F ( b ) for  i=1  to  λ  do E p k ( u i v i ) ← S M ( E p k ( u i ) , E p k ( v i ) ). if  F: u>v  then W i ← E p k ( u i ) E p k ( u i v i ) N - 1, end else W i ← E p k ( v i ) E p k ( u i v i ) N - 1 end G i ← E p k ( u i ⊕ v i ),Hi←Hi-1riGi;ri∈R Z N and H0=E(0) Φ i ← E p k ( - 1 ) H i, L i ← W i Φ i r i ′ ; r i ′ ∈ Z N end ( c ) Sends L to P 2.P: ( a )  Mi←D(Li), for 1≤i≤λ ( b ) if  ∃j  such that  Mj=1  then α ← 1 (which means u>v) end else α ← 0 (which means u<v) end


### 2.7. Secure Circuit Protocol (SCP)

We denote the three parties of the protocol byCSS1, CSS2, and CCS and their respective inputs by x1, x2, or x3∗. Their goal is to securely compute the function y=f(x1,x2,x3∗)=x1·x2/x3∗ [34] (Algorithm 5).Algorithm 5:Secure circuit protocol (SCP).
Input:  CSS1 has x1, CSS2 has x2 Output:  (x1+x2)/(a1+a2) 1. CCS: ( a ) Randomly selects crs for commitment, and sends crs to CSS1 and CSS2. ( b ) Generates the random number λ and share it secretly as λ=λ1⊕λ2, sends lambda1 to CSS1, and sends lambda2 to CSS2. 2.CSS1: Select seed r←0,1k for pseudo random function PRF and send r to CSS2. 3.CSS1 and CSS2: (a) Generate corresponding circuit Gb(1κ,f)→(F,e,d) based on function f=x1+x2∗λ. (b) Random selection ofb1,b2←{0,1}4m and generate the following commitments for all j∈[4m] and t∈{0,1}: ( C 1 , j t , σ 1 , j t ) ← C o m c r s ( e [ j , b 1 [ j ] ⊕ t ] ). ( C 2 , j t , σ 2 , j t ) ← C o m c r s ( e [ j , b 2 [ j ] ⊕ t ] ). ( c )  CSS1 and CSS2 send the following information to CCS: ( b 1 2 m + 1 ⋯ 4 m , F , { C 1 , j t } j , t ). ( b 2 2 m + 1 ⋯ 4 m , F , { C 2 , j t } j , t ). 4. CCS: Abort ifCSS1 and CSS2 report different values for these items. 5.CSS1 and CSS2: ( a )  CSS1 sends decommitment σ 1 , j x 1 [ j ] ⊕ b 1 [ j ], σ1,2m+jλ1[j]⊕b1[2m+j], σ2,jx1[j]⊕b2[j] and σ2,2m+jλ1[j]⊕b2[2m+j] to CCS ( b )  CSS2 sends decommitment σ1,m+jx2[j]⊕b1[m+j], σ1,3m+jλ2[j]⊕b1[3m+j], σ2,m+jx2[j]⊕b2[m+j] and σ2,3m+jλ2[j]⊕b2[3m+j] to CCS. 6. CCS:(a) For j∈[4m], compute Xj=ChkcrsC1,joj,σ1,joj, X′j=ChkcrsC2,joj,σ2,joj, for the appropriate o[j]. If any call to C h k returns ⊥, then abort. Similarly, CCS knows the values b12m+1⋯4m and b22m+1⋯4m, and aborts if CSS1 or CSS2 can not open the corresponding commitments of λ1 and λ2: C1,2m+jλ1j⊕b12m+j, C1,3m+jλ2j⊕b13m+j, C2,2m+jλ1j⊕b22m+j and C2,3m+jλ2j⊕b23m+j. ( b ) Run Y←Ev(F,X) and Y′←Ev(F,X′), then broadcasts Y and Y′ to CSS1 and CSS2. 7.CSS1 and CSS2: Compute x1+x2/a1+a2=De(d,Y)/De(d,Y′).For simplicity, we assume that|xi|=|y|=m. All communication between parties is via private point-to-point channels. Next, we assume that CSS1 and CSS2 can learn the same output y, while CCS can get the garbled values for the portion of the output wires corresponding to its own outputs only. CCS cannot get the output y with these garbled values. This protocol uses a garbling scheme, a four-tuple algorithm δ=(Gb,En,De,Ev), as the underlying algorithm. Gb is a randomized garbling algorithm that transforms a function of a triple. En and De are encoding and decoding algorithms, respectively. Ev is an algorithm that produces a garbled output for a garbled input and garbled circuit. Further, Chk is an algorithm that can verify commitments.


## 2.1. Distribute ID3 Decision Tree Algorithm

The ID3 algorithm description is given as follows. It builds a decision tree in a top-down manner with the information of samples. Starting at the root, the best object classification will be obtained. The best prediction is computed with theinformation gain. Theinformation gain of an attribute At is defined as(1)GainS,At=EntropyS-∑atj∈AtSatjSEntropySatjAssume that there are 2 parties,P=Pi∣i=1,2, with 2 databases, S=Si∣i=1,2. Each party Pi has one database Si. All databases share the same general attribute (column) set A=At∣t=1,2,..,p and each attribute At has several general discrete attribute values, denoted by At=atj∣j=1,2,…,mt, and one class attribute C=cj∣j=1,2,...,m.Without considering privacy, each partyPi shares his own Satjcji,Satji and Scji to all other parties. As a result, any party can calculate Entropy(S) and Entropy(Satj).(2)EntropyS=∑j=1m-ScjS⁡log2⁡ScjS=∑j=1m-∑i=1nScjiSlog2⁡∑i=1nScjiSwhereScj is the subset of S with tuples that have value cj for class attribute C. Scji equals the set of transactions with class attribute C set to cj in database Si.Then the value ofEntropySaj can be calculated as(3)EntropySatj=∑j=1mt-∑i=1nSatjcji∑i=1nSatji·log2⁡∑i=1nSatjcji∑i=1nSatjiwhereSatjcj is the subset of S with tuples that have values aj for attribute At and cj for class attribute C.Therefore, (3) can be easily computed by party Pi and parties Pjj≠i all of the values Satji and Satjcji from its database. Each party Pj then sums these together with the values Satjj and Satjcjj from its database and completes the computation.Then each party can calculateGainS,At value at its own side.


## 2.2. Paillier’s Homomorphic Encryption Scheme

Homomorphic encryption is a special type of encryption in which the result of applying a special algebraic operation to plain texts can be obtained by applying another algebraic operation (which may be different or the same) to the corresponding ciphertexts. Thus, even when the user does not know the plain texts, he/she can still obtain the results of applying that algebraic operation to the plain texts.Letm1 and m2 be two plain texts with encryptions E(m1) and E(m2), respectively.The Paillier encryption scheme [32] is described as follows: (4)Em1⊕Em2=Em1+m2


## 2.3. Li’s Symmetric Homomorphic Encryption Scheme

The description of symmetric homomorphic encryption scheme proposed by Li et al. [33] is as follows.(i)
KeyGen():(5)s,q,p⟵KeyGenλKeyGen() is used to generate key for users as SK=(s,q). p and q are primes with the condition that p≫q. s is chosen from ZN∗.(ii)
Encsk():(6)Encskm,d=sdrq+mmodp.d is a small positive integer, which is denoted asciphertext degree in this paper.(iii)
Decsk():(7)Decskc,d=c×s-dmodpmodq.


### 2.3.1. Properties of the Proposed Homomorphic Encryption

Homomorphic Multiplication.Let c1, c2 be the ciphertexts of two plaintexts m1, m2. Then we have c1=sd1(r1q+m1)modp and c2=sd2(r2q+m2)modp for some random ingredients r1 and r2. And we can obtain that(8)c1×c2modp=sd1r1q+m1modp×sd2r2q+m2modp=sd1+d2r1r2q+r1m2+r2m1q+m1×m2modp=Encskm1×m2,d1+d2.Homomorphic Addition (9) c 1 + c 2   m o d  p = s d r 1 q + m 1   m o d  p + s d r 2 q + m 2   m o d  p = s d r 1 + r 2 q + m 1 + m 2   m o d  p = E n c s k m 1 + m 2 , dReaders may refer to [18] for details on the scheme.


## 2.3.1. Properties of the Proposed Homomorphic Encryption

Homomorphic Multiplication.Let c1, c2 be the ciphertexts of two plaintexts m1, m2. Then we have c1=sd1(r1q+m1)modp and c2=sd2(r2q+m2)modp for some random ingredients r1 and r2. And we can obtain that(8)c1×c2modp=sd1r1q+m1modp×sd2r2q+m2modp=sd1+d2r1r2q+r1m2+r2m1q+m1×m2modp=Encskm1×m2,d1+d2.Homomorphic Addition (9) c 1 + c 2   m o d  p = s d r 1 q + m 1   m o d  p + s d r 2 q + m 2   m o d  p = s d r 1 + r 2 q + m 1 + m 2   m o d  p = E n c s k m 1 + m 2 , dReaders may refer to [18] for details on the scheme.


## 2.4. Garbling Scheme

A garbling scheme [34] consists of four algorithms, which is denoted by G=(Gb,En,De,Ev). f can be transformed by Gb into (F,e,d). Note that F is the garbled circuit. The encoding and decoding information algorithms are denoted by e,d. The output of garbled Y can be encrypted and get the result y=De(d,Y).


## 2.5. Noninteractive Commitment

A noninteractive commitment scheme [35] is also required in our paper, denoted by (Comcrs,Chkcrs). The distribution of Comcrs(x;r) is determined by the value of r as Comcrs(x).


## 2.6. Basic Cryptographic Subprotocols

In this section, we present a set of cryptographic subprotocols that will be used as subroutines when constructing the proposed protocol.


### 2.6.1. Outsourcing Secure Comparison Protocol (OSCP)

The value ofm is kept secure from the cloud and users. The value of c=E(mmodq) is computed. SK is kept by the data owner (Algorithm 1).Algorithm 1:Secure outsourcing comparison (OSCP).
1. The computation at Data owner: Compute τ=Encsk(1) for the cloud. 2. The computation at cloud: u , v are chosen such that u ≫ v v ≫ max ⁡ ( α , β ) ( q - 1 ) 2 ≫ β × u + v - α × u + v ≫ - ( q - 1 ) 2 3. The cloud compute the following value for the data owner: Φ = c u + τ v   m o d  p, and sends Φ. 4. Data Owner computes the following values: φ = D e c s k ( S K , Φ , d ) = ( m × u + v )   m o d  q, and comparesφ with (q-1)/2. Ifφ<q-1/2,m≥0. Otherwise, m<0.


### 2.6.2. Secure Equivalent Testing Protocol (SET)

With two ciphertextsc1=Encsk(m1) and c2=Encsk(m2),SET is to compute f and decide if the plaintexts are identical (m1=m2) (Algorithm 2).Algorithm 2:Secure equivalent testing protocol (SET).
Two ciphertext are computed by the cloud asc1=Encsk(m1) and c2=Encsk(m2). 1. The cloud computesc00=Encsk(m00)=c1-c2 and c01=Encsk(m01)=c2-c1. 2. Check ifm00≥0 or m01≥0 and computes ifm00≥0∧m01<0, f0=1,f1=0. else if m00<0∧m01≥0, f0=0,f1=1. 3. The value off is computed as follows: f = f 0 ⊕ f 1. Iff=0, set m1=m2.


### 2.6.3. Secure Multiplication Protocol (SMP)

The algorithm is described as in Algorithm3.Algorithm 3: S M ( E p k ( x ) , E p k ( y ) ) → E p k ( x y ).
The values are computedEpk(x) and Epk(y); P keeps (pk,sk). 1.C: ( a ) Choose rx,ry∈ZN ( b )  x′←Epk(x)Epk(rx), y′←Epk(y)Epk(ry) ( c ) computes and sends x′,y′ to P 2.P computes: ( a )  hx←Dsk(x′), hy←Dsk(y′), h←hxhy mod N, h′←Epk(h) ( b ) The value of h′ is sent to C 3.C computes: ( a )  s←h′Epk(x)N-ry, s′←sEpkyN-rx ( b )  Epk(xy)←s′EpkrxryN-1


### 2.6.4. Secure Minimum out of 2 Numbers Protocol (SMIN2)

The algorithm is described as in Algorithm4.Algorithm 4:Secure Minimum out of 2 Numbers Protocol (SMIN2).
1.C: ( a ) The function is chosen F ( b ) for  i=1  to  λ  do E p k ( u i v i ) ← S M ( E p k ( u i ) , E p k ( v i ) ). if  F: u>v  then W i ← E p k ( u i ) E p k ( u i v i ) N - 1, end else W i ← E p k ( v i ) E p k ( u i v i ) N - 1 end G i ← E p k ( u i ⊕ v i ),Hi←Hi-1riGi;ri∈R Z N and H0=E(0) Φ i ← E p k ( - 1 ) H i, L i ← W i Φ i r i ′ ; r i ′ ∈ Z N end ( c ) Sends L to P 2.P: ( a )  Mi←D(Li), for 1≤i≤λ ( b ) if  ∃j  such that  Mj=1  then α ← 1 (which means u>v) end else α ← 0 (which means u<v) end


## 2.6.1. Outsourcing Secure Comparison Protocol (OSCP)

The value ofm is kept secure from the cloud and users. The value of c=E(mmodq) is computed. SK is kept by the data owner (Algorithm 1).Algorithm 1:Secure outsourcing comparison (OSCP).
1. The computation at Data owner: Compute τ=Encsk(1) for the cloud. 2. The computation at cloud: u , v are chosen such that u ≫ v v ≫ max ⁡ ( α , β ) ( q - 1 ) 2 ≫ β × u + v - α × u + v ≫ - ( q - 1 ) 2 3. The cloud compute the following value for the data owner: Φ = c u + τ v   m o d  p, and sends Φ. 4. Data Owner computes the following values: φ = D e c s k ( S K , Φ , d ) = ( m × u + v )   m o d  q, and comparesφ with (q-1)/2. Ifφ<q-1/2,m≥0. Otherwise, m<0.


## 2.6.2. Secure Equivalent Testing Protocol (SET)

With two ciphertextsc1=Encsk(m1) and c2=Encsk(m2),SET is to compute f and decide if the plaintexts are identical (m1=m2) (Algorithm 2).Algorithm 2:Secure equivalent testing protocol (SET).
Two ciphertext are computed by the cloud asc1=Encsk(m1) and c2=Encsk(m2). 1. The cloud computesc00=Encsk(m00)=c1-c2 and c01=Encsk(m01)=c2-c1. 2. Check ifm00≥0 or m01≥0 and computes ifm00≥0∧m01<0, f0=1,f1=0. else if m00<0∧m01≥0, f0=0,f1=1. 3. The value off is computed as follows: f = f 0 ⊕ f 1. Iff=0, set m1=m2.


## 2.6.3. Secure Multiplication Protocol (SMP)

The algorithm is described as in Algorithm3.Algorithm 3: S M ( E p k ( x ) , E p k ( y ) ) → E p k ( x y ).
The values are computedEpk(x) and Epk(y); P keeps (pk,sk). 1.C: ( a ) Choose rx,ry∈ZN ( b )  x′←Epk(x)Epk(rx), y′←Epk(y)Epk(ry) ( c ) computes and sends x′,y′ to P 2.P computes: ( a )  hx←Dsk(x′), hy←Dsk(y′), h←hxhy mod N, h′←Epk(h) ( b ) The value of h′ is sent to C 3.C computes: ( a )  s←h′Epk(x)N-ry, s′←sEpkyN-rx ( b )  Epk(xy)←s′EpkrxryN-1


## 2.6.4. Secure Minimum out of 2 Numbers Protocol (SMIN2)

The algorithm is described as in Algorithm4.Algorithm 4:Secure Minimum out of 2 Numbers Protocol (SMIN2).
1.C: ( a ) The function is chosen F ( b ) for  i=1  to  λ  do E p k ( u i v i ) ← S M ( E p k ( u i ) , E p k ( v i ) ). if  F: u>v  then W i ← E p k ( u i ) E p k ( u i v i ) N - 1, end else W i ← E p k ( v i ) E p k ( u i v i ) N - 1 end G i ← E p k ( u i ⊕ v i ),Hi←Hi-1riGi;ri∈R Z N and H0=E(0) Φ i ← E p k ( - 1 ) H i, L i ← W i Φ i r i ′ ; r i ′ ∈ Z N end ( c ) Sends L to P 2.P: ( a )  Mi←D(Li), for 1≤i≤λ ( b ) if  ∃j  such that  Mj=1  then α ← 1 (which means u>v) end else α ← 0 (which means u<v) end


## 2.7. Secure Circuit Protocol (SCP)

We denote the three parties of the protocol byCSS1, CSS2, and CCS and their respective inputs by x1, x2, or x3∗. Their goal is to securely compute the function y=f(x1,x2,x3∗)=x1·x2/x3∗ [34] (Algorithm 5).Algorithm 5:Secure circuit protocol (SCP).
Input:  CSS1 has x1, CSS2 has x2 Output:  (x1+x2)/(a1+a2) 1. CCS: ( a ) Randomly selects crs for commitment, and sends crs to CSS1 and CSS2. ( b ) Generates the random number λ and share it secretly as λ=λ1⊕λ2, sends lambda1 to CSS1, and sends lambda2 to CSS2. 2.CSS1: Select seed r←0,1k for pseudo random function PRF and send r to CSS2. 3.CSS1 and CSS2: (a) Generate corresponding circuit Gb(1κ,f)→(F,e,d) based on function f=x1+x2∗λ. (b) Random selection ofb1,b2←{0,1}4m and generate the following commitments for all j∈[4m] and t∈{0,1}: ( C 1 , j t , σ 1 , j t ) ← C o m c r s ( e [ j , b 1 [ j ] ⊕ t ] ). ( C 2 , j t , σ 2 , j t ) ← C o m c r s ( e [ j , b 2 [ j ] ⊕ t ] ). ( c )  CSS1 and CSS2 send the following information to CCS: ( b 1 2 m + 1 ⋯ 4 m , F , { C 1 , j t } j , t ). ( b 2 2 m + 1 ⋯ 4 m , F , { C 2 , j t } j , t ). 4. CCS: Abort ifCSS1 and CSS2 report different values for these items. 5.CSS1 and CSS2: ( a )  CSS1 sends decommitment σ 1 , j x 1 [ j ] ⊕ b 1 [ j ], σ1,2m+jλ1[j]⊕b1[2m+j], σ2,jx1[j]⊕b2[j] and σ2,2m+jλ1[j]⊕b2[2m+j] to CCS ( b )  CSS2 sends decommitment σ1,m+jx2[j]⊕b1[m+j], σ1,3m+jλ2[j]⊕b1[3m+j], σ2,m+jx2[j]⊕b2[m+j] and σ2,3m+jλ2[j]⊕b2[3m+j] to CCS. 6. CCS:(a) For j∈[4m], compute Xj=ChkcrsC1,joj,σ1,joj, X′j=ChkcrsC2,joj,σ2,joj, for the appropriate o[j]. If any call to C h k returns ⊥, then abort. Similarly, CCS knows the values b12m+1⋯4m and b22m+1⋯4m, and aborts if CSS1 or CSS2 can not open the corresponding commitments of λ1 and λ2: C1,2m+jλ1j⊕b12m+j, C1,3m+jλ2j⊕b13m+j, C2,2m+jλ1j⊕b22m+j and C2,3m+jλ2j⊕b23m+j. ( b ) Run Y←Ev(F,X) and Y′←Ev(F,X′), then broadcasts Y and Y′ to CSS1 and CSS2. 7.CSS1 and CSS2: Compute x1+x2/a1+a2=De(d,Y)/De(d,Y′).For simplicity, we assume that|xi|=|y|=m. All communication between parties is via private point-to-point channels. Next, we assume that CSS1 and CSS2 can learn the same output y, while CCS can get the garbled values for the portion of the output wires corresponding to its own outputs only. CCS cannot get the output y with these garbled values. This protocol uses a garbling scheme, a four-tuple algorithm δ=(Gb,En,De,Ev), as the underlying algorithm. Gb is a randomized garbling algorithm that transforms a function of a triple. En and De are encoding and decoding algorithms, respectively. Ev is an algorithm that produces a garbled output for a garbled input and garbled circuit. Further, Chk is an algorithm that can verify commitments.


## 3. Outsourcing Privacy-Preserving ID3 Decision Tree Algorithm in Malicious Model

In this section, we present our secure outsourcing ID3 decision tree in cloud computing using the homomorphic encryption scheme and subprotocols proposed in Section2 as building blocks.


### 3.1. Main Concept

The aim is to privately compute ID3 over encrypted databases, and the key is to find privately the attributeA for which Gain is maximum. From the above description, the key value which needs to be calculated with other parties is EntropySai.Since all the data was encrypted and sent to the cloud, the cloud server can count the number of|S(ck)|t, |S|it using theSET protocol described in Section 2. Now, (3) can be executed as (x1+x2)/(a1+a2)log2(x1+x2)/(a1+a2), and the calculation of the logarithmic operation can be performed in CSS. The value to be calculated is the value of c1=(x1+x2)/(a1+a2), which can be easily determined using ourSCP protocol as explained in Section 2. Then, all the parties can calculate the value of Entropy(S) independently.


### 3.2. System Model

The system model is shown in Figure1, which includes two data owners and cloud servers (cloud storage server {CSS1, CSS2}, and cloud computing server CCS). Each data owner owns a private data set that is encrypted and outsourced to cloud server storage. Data owners can request cloud server to process ID3 data on encrypted data. At the same time, CSS and CCS servers participate in supporting the outsourcing privacy protection ID3 data mining algorithm steps; after the implementation of the algorithm, the final results are sent to the data owner. Assuming that the data owner and the CSS server are semihonest participants, CCS is a malicious participant.Figure 1
System model under consideration.


### 3.3. Details of the Proposed Algorithm

Our securely outsourcing ID3 decision tree (SOID3) algorithm is detailed as follows:( 1 )  P1 and P2 run KeyGen(λ) to generate the secret key SKi,i=1,2 and a public parameter p of Li’s homomorphic encryption scheme. Further, each party shares p with the other party and the cloud but shares SKi only with itself.( 2 ) Each party uses its key SKi to encrypt every attribute value of its database, and then outsources the encrypted database to the CSS (CSS1 and CSS2).( 3 ) The CSS1 and CSS2 use theSET protocol to calculate the value of Saji and Sajcki for each attribute with each party Pi.( 4 ) Each party generates its Paillier public and private keys (pki,ski), i=1,2, and sends the public keys to the CSS1 and CSS2.( 5 ) CCS, CSS1, and CSS2 jointly use theSCP protocol to compute x1+x2/a1+a2. Here, CSS1 has (x1,a1), and CSS2 has (x2,a2).( 6 ) Each party decrypts the received information, calculates it with the logarithmic operation of (x1+x2/a1+a2)log2(x1+x2/a1+a2), and then encrypts it with its public key. Then, it sends it back to the cloud.( 7 ) After getting the result, CSS1 and CSS2 use theSMIN2 protocol to select the ciphertext data with the minimum value and then further select the attribute label with the maximum information gain and return it to each participant.( 8 ) The participants divide the data sets and build tree nodes. Then, go to Step (3) until termination.


## 3.1. Main Concept

The aim is to privately compute ID3 over encrypted databases, and the key is to find privately the attributeA for which Gain is maximum. From the above description, the key value which needs to be calculated with other parties is EntropySai.Since all the data was encrypted and sent to the cloud, the cloud server can count the number of|S(ck)|t, |S|it using theSET protocol described in Section 2. Now, (3) can be executed as (x1+x2)/(a1+a2)log2(x1+x2)/(a1+a2), and the calculation of the logarithmic operation can be performed in CSS. The value to be calculated is the value of c1=(x1+x2)/(a1+a2), which can be easily determined using ourSCP protocol as explained in Section 2. Then, all the parties can calculate the value of Entropy(S) independently.


## 3.2. System Model

The system model is shown in Figure1, which includes two data owners and cloud servers (cloud storage server {CSS1, CSS2}, and cloud computing server CCS). Each data owner owns a private data set that is encrypted and outsourced to cloud server storage. Data owners can request cloud server to process ID3 data on encrypted data. At the same time, CSS and CCS servers participate in supporting the outsourcing privacy protection ID3 data mining algorithm steps; after the implementation of the algorithm, the final results are sent to the data owner. Assuming that the data owner and the CSS server are semihonest participants, CCS is a malicious participant.Figure 1
System model under consideration.


## 3.3. Details of the Proposed Algorithm

Our securely outsourcing ID3 decision tree (SOID3) algorithm is detailed as follows:( 1 )  P1 and P2 run KeyGen(λ) to generate the secret key SKi,i=1,2 and a public parameter p of Li’s homomorphic encryption scheme. Further, each party shares p with the other party and the cloud but shares SKi only with itself.( 2 ) Each party uses its key SKi to encrypt every attribute value of its database, and then outsources the encrypted database to the CSS (CSS1 and CSS2).( 3 ) The CSS1 and CSS2 use theSET protocol to calculate the value of Saji and Sajcki for each attribute with each party Pi.( 4 ) Each party generates its Paillier public and private keys (pki,ski), i=1,2, and sends the public keys to the CSS1 and CSS2.( 5 ) CCS, CSS1, and CSS2 jointly use theSCP protocol to compute x1+x2/a1+a2. Here, CSS1 has (x1,a1), and CSS2 has (x2,a2).( 6 ) Each party decrypts the received information, calculates it with the logarithmic operation of (x1+x2/a1+a2)log2(x1+x2/a1+a2), and then encrypts it with its public key. Then, it sends it back to the cloud.( 7 ) After getting the result, CSS1 and CSS2 use theSMIN2 protocol to select the ciphertext data with the minimum value and then further select the attribute label with the maximum information gain and return it to each participant.( 8 ) The participants divide the data sets and build tree nodes. Then, go to Step (3) until termination.


## 4. Security Analysis

In this section, we prove that the secure outsourcing ID3 decision tree (SOID3) algorithm can offer protection against the malicious cloud server.Theorem 1.
The SOID3 algorithm can achieve privacy for each party and the semihonest cloud storage server.Proof.
We mainly consider the security model under the noncollusive semihonest model and the semihonest cloud server. Suppose there are two parties,P1 and P2, and cloud storage server CSS.
LetP=(P1,P2,CSS) be the participants of all protocols. Consider three types of attackers ( AP1, AP2, and ACSS) that can invade P1, P2, and CSS. In the real model, P1 and P2 have data sets Dx and Dy, respectively, and CSS has encrypted data sets Enc(Dx) and Enc(Dy). Make H⊂P a collection of honest participants. For all PiϵH, outPi indicates the output of Pi. If Pi is invaded, outPi represents all views of participant Pi in running protocol Π.
For eachP∗∈P, the attacker A=(AP1, AP2,ACSS) view in the runtime protocol Π can be defined as(10)REALΠ,A,HP∗Dx,Dy=outPi:PiϵH∪outP∗
In the ideal model, there exists an ideal modelF for function f, and all participants can interact with the model F. That is, Challenger DPa and participant Pi can send data x and y to F. If Dx or Dy is ⊥, F returns ⊥. Finally, F can return fDx,Dy to challenger DPa. As mentioned earlier, H⊂P is a collection of honest participants. For each participant PiϵH in the collection, return the outPi as F output to Pi. If Pi is intruded on by a semihonest attacker, outPi is still consistent with the output of Pi in previous realistic models.
For allP∗∈P, in the ideal model, in the presence of independent simulators Sim=(SimP1, SimP2,SimCSS), the P∗ view is (11)IDEALF,Sim,HP∗Dx,Dy=outPi:PiϵH∪outP∗
Therefore, it is considered that the protocolΠ is secure in the presence of noncolluded semitruthful attackers.
Definition  2. Let f be a deterministic functionality among parties in P. Let H⊂P be the subset of honest parties in P. We say that Π securely realizes f if there exists a set Sim={SimP1,SimP2,SimS} of PPT transformations (where SimDa=SimP1(AP1) and so on) such that for all semihonest PPT adversaries A={AP1,AP2,AS}, for all inputs Dx,Dy and auxiliary inputs z, and for all parties P∈P the following holds:(12)REALΠ,A,H,zP∗λ,x,yλ∈N≡~IDEALF,Sim,H,zP∗λ,x,yλ∈N,
where≡~ denotes computational indistinguishability.Theorem 2.
The SOID3 algorithm is secure with the semihonest cloud storage server and the malicious cloud computing server.Proof.
First consider the case whereCSS1 or CSS2 is corrupted. It is necessary to prove that, in theSCP protocol, the ideal model and the realistic model are not distinguishable. That is, in the following interactions, it is impossible to distinguish between the various types of interaction information and outputs of the participants in the ideal model and the real model.
( 1 ) In the real model, assume that there is an emulator that can simulate various behaviors of a semihonest participant CSS1 (or CSS2), and receive inputs (x1,a2) and (x2,a2) from the execution environment of the protocol. At the same time, the simulator can simulate the function Ff, which sends all inputs (x1,a1) and (x2,a2) to the simulated Ff. Since the simulator does not do anything computed by Ff, there is no difference between the real Ff and the simulated Ff from the execution environment point of view.
( 2 ) Because in Step 2, CSS1 and CSS2 uniformly select the seed r of Pseudo-Random Function (PRF), the PRF security shows that the real model in Step 2 is indistinguishable from the ideal model.
( 3 ) In Step 3, we modify the simulator, which knows in advance what promises will be opened when the simulator generates commitment C. First, the simulator selects the random numbers o1, o2 that can be marked which promises to be opened and calculates the values of b1=o1⊕x1∥x2, b2=o2⊕a1∥a2. At this point, the simulator has obtained the values of x1, x2, and a1, a2. Then, the simulator can submit the markings that promise not to be opened. In this process, due to the concealment of commitment, the realistic model and the ideal model are equally indistinguishable.
( 4 ) In Step 6a, the simulated CSS1 and CSS2 stop executing when De(D,Y~)  =  ⊥. Change the emulator to make Y~≠Ev(F,X). By obfuscating the authenticity of the circuit, CCS has only negligible probability to obtain Y~≠Ev(F,X) in Ded,Y~  =  ⊥. Therefore, in this step, the realistic model and the ideal model are equally indistinguishable.
( 5 ) In Step 6b, the correctness of the obfuscation circuit guarantees that both CSS1 and CSS2 of the analog can be output. Therefore, if there is no pause in 6a, we can modify the simulator to an analog obfuscation circuit that generates (F,X,d). We can simulate the output of CSS1 and CSS2 by simulating the instructions of Ff. According to the security of the confusing circuit, the real model is also indistinguishable from the ideal model in this step.
Therefore, in this protocol, the execution environment can not distinguish between the realistic model and the ideal model. And the protocol is secure whenCCS is a malicious participant.


## 5. Performance Analysis

In this paper, we consider that CSS has a strong calculation ability and we ignore its computation time. Each data owner does not need to store the ciphertext but can just use the public key to encrypt the message and the private key to decrypt the ciphertext.In each iteration, first, each data owner will execute theSBD protocol andSMIN2 protocol with the cloud. There are two interactions in theSBD protocol and 2k interactions in theSMIN2 protocol. Then, CSS1, CSS2, and CCS will execute 6 interactions in theSCP protocol. Finally, each data owner will execute 1 interaction when it goes to the new iteration. We assume that t is the iteration time, so the communication traffic is at most O(k∗t).In this paper, a secure average computing protocol based onSCP is implemented. The server selected in the experimental environment is CPU: Intel (R) Xeon (R) CPU E5-2620 v3@2.40GHz∗2, memory: 32G, operating system Ubuntu 16.04.4 LTS version. In the experiment, AES-128 is chosen as the basic encryption method of the confusion circuit, and the open source code of JustGarble is changed, and the commitment protocol is implemented based on SHA-256. Finally, the average values obtained from experiments are as follows.In our secure outsourcing ID3 decision tree (SOID3) algorithm experiment, two participants were tested with different numbers of records. The experimental results are shown in Figure2.Figure 2
Performance measurements for our SOID3 with 2 participants.From Figure2, since the client is only responsible for encrypting uploaded data, the time consumption is very low. In the cloud, CCS and CSS servers need to runSCP protocol, resulting in a lot of time consumption (Table 1). The main reason is that a large number of bit commitment processing is needed in the obfuscation circuit, and the performance improvement will be focused on this issue in the follow-up work.Table 1
Time cost of the SCP protocol.
AND XOR OR Input size(bits) Output size(bits) C S S 1 / C S S 2 (ms) C C S (ms) 5090 4034 2016 129 65 26 47


## 6. Conclusion

In this paper, we proposed a secure outsourcing ID3 decision tree algorithm for two parties of the malicious model. Our algorithm can preserve the privacy of the users’ data as well as that of the data mining scheme for the cloud servers. The parties can get only the result trees and have no knowledge about the data mining scheme. Moreover, the cloud servers cannot get any private information about the parties. In summary, our protocol offers protection against malicious cloud servers.In the future, we intend to extend our algorithm to vertical and arbitrary partitioning in the malicious model. In addition, we plan to extend our algorithm to a general multiparty privacy-preserving framework suitable for other useful schemes, such as random decision tree, Bayes, SVM, and other data mining methods, and can be extended for use in the wireless sensor-networks [36, 37].



---

*Source: 2385150-2018-10-04.xml*