Privacy preserving multivariate classification based on tree-vector product protocol

JOURNAL OF SCIENCE OF HNUE FIT., 2011, Vol. 56, pp. 72-80 PRIVACY PRESERVING MULTIVARIATE CLASSIFICATION BASED ON TREE-VECTOR PRODUCT PROTOCOL Luong The Dung(∗) VietNam Information Security Commission Tran Duc Su Academy of Cryptographic Technique (∗)E-mail: thedungluong@gmail.com 1. Introduction Data mining has emerged as a significant technology for gaining knowledge from vast quantities of data [1]. Data mining technology allows us to analyze a personal data, or a organizational data. However, that creates threats to privacy, this reason might cause an obstruction to data mining collaboration projects. For example, two companies have a huge data set of records of their customers. These companies want to cooperatively conduct mining on their joint data set for their mutual benefit since this collaboration brings them results of mining which are more accurate than results of local data mining. However, each company does not want to, or does not have permission to disclose private information of other company’s customers. The challenge then is whether the two companies above obtain results of mining while still preserving their data secrecy. Recently, there has been growing focus on finding solutions to this problem [4, 5, 11]. In this paper, we firstly state the secure three-vector product computation problem and develop protocols called tree-vector products to solve this problem. Our protocols are developed based on some basic protocols [3, 4, 7, 8] and their security properties is validated base on the composition theorem for the semi-honest model [9]. We then use the proposed protocols to address a focus problem of privacy preserving multivariate classification. 2. Content 2.1. Background and problem statement 2.1.1. Problem statement Problem. Consider a data set D that has m observations, n attributes X1, X2, . . . , Xn and a class attribute Y . Where each Xi, (i = 1, . . . , n) takes values as real numbers, Y takes values as category data. The data set D is vertically 72 Privacy preserving multivariate classification based on tree-vector product protocol partitioned over K parties where each party Pi (i = 1, 2, . . . , K) corresponds to a subset Di with some attributes of D. In other words, each Pi can only observe the values of some attributes of D for the same set of m observations, only one or the subset of the parties has attribute Y . We use the notation D = (D1 : D2 : . . . : DK : Y ) to present the union of these K subsets. The target of this work is to find solutions to build a Multivariate Classification model according to the above described circumstance, without disclosing the private data of any parties to the others. Previous works. Privacy preserving Multivariate Classification approach for the vertically partitioned model proposed in [2, 12]. This approach is based on secure matrix product computation techniques, it was showed efficient in cost communica- tion. However, this approach has a limitation that it requires all parties participating in the protocol knowing class attribute Y . We address the problem that only the subset of the parties knows the class attribute and the class attribute is sensitive and it needs be protected. 2.1.2. Cryptography tools Secure scalar product computation protocol. For example there are two parties Alice and Bob, Alice has a vector X = (x1, .., xn) and Bob has a vector Y = (y1, . . . , yn). The scalar product, or inner product, of two vectors Y and Y is defined as 〈X, Y 〉 = n∑ i=1 xiyi. The goal of secure scalar product protocol is to compute the scalar product of two vectors X and Y with no party disclose its private data (vector) to other parties. Secure scalar product protocols are an important primitive for privacy- preserving data mining. Several such protocols have been proposed (e.g. [3], [4], [5], etc.) with varying degrees of security and cost communication. A nice overview of the problem and the security properties of some solutions appears in [6]. Oblivious polynomial evaluation. The problem of “oblivious polynomial evalu- ation” was first considered in [7]. As with oblivious transfer, this problem involves a sender and a receiver. The sender’s input is a polynomial Q of degree k over some finite field F and the receiver’s input is an element z ∈ F (the degree k of Q is public). The protocol is such that the receiver obtains Q(z) without learning anything else about the polynomial Q, and the sender learns nothing. An efficient solution to this problem was presented in [7]. The overhead of that protocol is O(k) exponentiations (using the method suggested in [8] for doing a 1-out-of-N oblivious transfer with O(1) exponentiations). The semi-honest model. In the semi-honest model, each party participating in the protocol have to follow the rules using its correct input, and it can’t use what it sees during execution of the protocol to compromise security. This model is 73 Luong The Dung and Tran Duc Su reasonable for many real situations because parties who want to mine data for their mutual benefit will follow the protocol to get correct results. The definition of secure two-party computation in the semi-honest model is stated in [9]. Basically the definition states that a computation is secure if the view of each party during the execution of the protocol can be effectively simulated by the input and the output of the party. This is not quite the same as saying that private information is protected because it is possible to have privacy breaches by inferring from the final result and local information. In this paper, we also use the Composition Theorem for the semi-honest model. The detail of its discussion and the proof can be seen in [9]. Theorem 2.1. (The Composition Theorem) Suppose that g is privately reducible to f and that there exists a protocol for privately computing f . Then there exists a protocol for privately computing g. 2.2. Tree-vector Product For next works, in this section we state a secure three-vector product compu- tation problem and propose protocols to address this problem. Support that three parties Pa, Pb and Pc have three vectors X = (x1, . . . , xn), Y = (y1, . . . , yn) and Z = (z1, . . . , zn) respectively. We call the three-vectors scalar product of X, Y and Z as 〈X, Y, Z〉 = n∑ i=1 x − iyizi. Our goal is to design a protocol for secure three- vectors product computation with no party disclose its private data to other party, all parties are not able to learn anything other than the final result. 2.2.1. Protocol 1 To address the above problem, we built three-vector product protocols from the two basic protocols: secure scalar product and secure polynomial comes evalu- ation. In actual implementation, these basic protocols have proved be secure and efficient, hence some authors have used these protocols as an important prim- itive to design their protocols. Let R = (r1, . . . , rm) be a random vector. Let (Q1(z), Q2(z), . . . , Qm(z)) = (x1z + x2z + . . . + xmz + rm) be n degree 1 poly- nomials, we call it be a linear polynomial vector. we design the secure three-vector product protocol as below: Input. Three parties Pa, Pb, Pc have three vectors X, Y, Z respectively. Output. 〈X, Y, Z〉. 1. Pa generates a random vector and then defines a linear polynomial vector where be a linear polynomial. Each element of vector R follows a uniform distribution over a user-defined field. 2. Pa and Pb engage in a private evaluation of each Qi(yi), (i = 1, . . . , m)), in which Pb obtains Q = (Q1(y1), Q2(y2), , . . . , Qm(ym)) where Qi(yi) = xiyi + ri 74 Privacy preserving multivariate classification based on tree-vector product protocol 3. Pa and Pc execute the secure product protocol with Pa inputting R and in- putting Z, in which Pc obtains 4. Pb and Pc execute the secure product protocol with Pb inputting and Pc in- putting Z, in which Pb obtains 5. Pb computes 〈X, Y, Z〉 = 〈Q,Z〉 − 〈R,Z〉. 6. Pb sends to Pa and Pc Theorem 2.2. Protocol 1 privately computes the shares of the three-vectors Product value Proof. In this section, we show that Protocol 1 allows us to obtain the three-vectors Scalar Product values and privacy-preserving. We have Q = (Q1(y1), Q2(y2), , . . . , Qm(ym)) = (x1y1 + r1, . . . , xmym + rm), so 〈Q,Z〉 = m∑ i=1 (xiyizi + rizi) and 〈R,Z〉 = ∑ 6mi=1rizi, therefor, 〈X, Y, Z〉 = 〈Q,Z〉 − 〈R,Z〉 = m∑ i=1 xiyizi, this is the three-vectors product value. In order to show that a protocol is secure in the semi-honest model, we simply need to apply the composition theorem, so we need to show that each step in Protocol 1 is secure. We note that Protocol 1 requires the secure scalar product and secure poly- nomial evaluation operation, where there already exists many protocols that are correct and secure ([3,4,5]). During these execution of this protocols, the parties participating in the protocols are not able to learn anything other than the final result. In the protocol 1, the only communication taking place is at steps 2, 3 and 4. In Step 2, parties Pa and Pb engage in a private evaluation of each Qi(yi), (i = 1, . . . , m), neither party share their private, only Pb obtains the vector Q that each Qi(yi) = xiyi + ri is a random number from a uniform distribution over a defined field. In step 3, Pa and Pc execute the secure product protocol, each party only ob- tains 〈R,Z〉 without any other useful information. The results of the scalar product protocol are randomly shared, which can be simulated by both Pa and Pc as shown in (Lemma 4.1 [11]) In step 4, similarly, Pb and Pc only obtain the value 〈Q,Z〉 without knowing other useful information from the other party. Protocol 1 can also be proved by using a simulation method [10]. The basic idea is to show the view of each party during the execution of the protocol that can 75 Luong The Dung and Tran Duc Su be effectively simulated by giving the input and output of that party. Here, we show that both parties are not able to learn anything but the final result. Remark. We should note that using the same random vector R in many iter- ations of Protocol 1 will cause privacy breaches. For example, assume that Pa has a vector X, Pb has two vectors Y and Y ′, and Pc has a vector Z. The parties need to execute two iterations of Protocol 1 to compute 〈X, Y ′, Z〉 and 〈X, Y, Z〉. If we use the same vector R in two above iterations then each xi of Pa, Pb can establish an equation system including two equations: xiyi + ri = qi and xiyi′ + ri = qi′ (qi and qi′ were determined), so Pb can get xi. Thus, to prevent privacy breaches we need to generate a different vector R in each iteration of Protocol 1. Cost Communication. Let pi(m) be an expression for the communication cost of some secure scalar product protocols where is the number of elements of the vectors participating in the protocol. Let pi′(m) be an expression for the communication cost of the private polynomial evaluation protocol in a private evaluation of the linear polynomial vector. In Protocol 1, the communication primarily occurs at steps 2, 3 and 4, so the communication cost of Protocol 1 is 2pi(m) + pi′(m) 2.2.2. Protocol 2 The protocol 1 is secure and it also protects each party’s private information against collusion of other dishonest parties. However, in some determined conditions, we can support that there are no collusions among parties. Thus we propose a secure three- vectors scalar product protocol that can have lower communication cost other than that of Protocol 1. The idea is that, because Pa shares the vector R with Pc, we can ignore the step of computing 〈R,Z〉 to reduce communication costs. However, the drawback of this protocol is that it does not protect private data of Pa against collusion between Pb and Pc. Input. Three parties Pa, Pb and Pc have three vectors X, Y, Z respectively. Output. 〈X, Y, Z〉. 1. Pa and Pc jointly generate a random vector R = (r1, . . . , rm). Each element of vector R follows a uniform distribution over a user-defined field. 2. Pa generates a random vector a linear polynomial vector Q = (Q1(z1), Q2(z2), , . . . , Qm(zm)) where Qi(z) = xiz + ri be a linear polyno- mial. 3. Pa and Pb engage in a private evaluation of each Qi(z), in which Pb obtains Q = (Q1(y1), Q2(y2), , . . . , Qm(ym)) where Qi(z) = xiyi + ri. 4. Pb and Pc execute the secure scalar product protocol with Pb inputting Q and Pc inputting Z, in which they obtain 〈Q,Z〉. 5. Pc computes 〈R,Z〉 and then computes 〈X, Y, Z〉 = 〈Q,Z〉 − 〈R,Z〉. 76 Privacy preserving multivariate classification based on tree-vector product protocol 6. Pc sends 〈X, Y, Z〉 to Pa and Pb Theorem 2.3. Protocol 2 privately computes the shares of the three-vector product value assuming non-collusion. Proof. Similar to the proof of Protocol 1, we can also show that Protocol 2 is privacy-preserving if there is no collusion. Because in Protocol 2, the only com- munication taking place is at steps 3, 4. In step 3, the secure polynomial evaluation protocol executed that only Pb obtains a value random from the defined field. The communication occurs at step 4 with the invocation of the scalar product protocol. The results of the scalar product protocol are random shares, which can be simu- lated as shown in (Lemma 4.1 [11]). Thus, Protocol 1 can be simulated, with the composition theorem being applied to the scalar product protocol and the polyno- mial evaluation protocol. However, Protocol 2 can cause privacy breaches when Pb enters into collusion with Pc, then Pc can share the vector R with Pb, so Pb can get vector X of Pa. Communication cost. In Protocol 2, the communication primarily occurs at steps 3 and 4, so the communication cost of Protocol 1 is pi(m) + pi′(m). Thus, the communication cost of Protocol 2 is lower than that of Protocol 1. The reason for that is because of Pa sharing R with Pc, Pa and Pc do not have to use a scalar product protocol for computation 〈R,Z〉. 2.2.3. Protocol 3 In this section, we consider a case that three vectors X, Y, Z belong to only two parties. For example, X and Y belong to Pa, and Z belongs to Pb. To compute 〈X, Y, Z〉, Pa generates R = (x1y1, . . . , xmym), then Pa and Pb execute the secure product protocol with Pa inputting R and Pb inputting Z, in which they obtain 〈R,Z〉. It should be noted that 〈X, Y, Z〉 = 〈R,Z〉. Security properties of this protocol derive from the secure scalar product protocol. 2.3. Privacy Preserving Multivariate Classification 2.3.1. Multivariate Classification In this section, we introduce the Multivariate Classification method and ana- lyze this method to find the target formula that need be securely computed. Classification is one of the most important technologies of data mining that has wide applications in the various areas. The goal of classification is to build a model which can predict the value of one variable, based on the known values of the other variables. There are various classification methods, such as Statistical methods, Support vector machine, and Decision tree [1]. In this paper we consider a method based on a statistical analysis presented in [2]. An observation is said belonging a class k if the attributes vector of that observation is the closest to the centroid of class k. The Mahalanobis distance of an 77 Luong The Dung and Tran Duc Su observation in a class indicates how far the observation is from the centroid of all observations in that class. Let Sk represents the data set consisting of the vectors of all the observations in class k. Let Sk be the vector of means of observations in class k. Let Sk(j) represents the jth row of matrix Sk, and Ŝk be a matrix where Ŝk(j) = Sk(j) − Sk. The Mahalanobis distance dk between an observation V (its attributes vector is V ) and the centroid of class k can be computed as the following: d2k = (V − Sk)TC−1k (V − Sk) + ln |Ck| where Ck is the covariance matrix in class k: Ck = 1 m− 1〈Sˆk, Sˆk〉 Assume class attribute Y takes values in a discrete domain including *********** values. After computing d1, . . . , dL, we can conclude that the observation V belongs to class i if di = min{d1, d2, ..., dL}. Therefore, in order to determine a class for a new observation, we need to compute Ck and Sk. 2.3.2. Privacy Preserving Multivariate Classification Now we address the privacy preserving classification problem, assume the data set D is vertically partitioned onK parties. We need to design a protocol that allows each party to predict a class label for a new observation based on the joint data set of parties with no party disclosing its private data to other parties. To predict class for a new observation, the parties need to know d1, . . . , dL. So they need to securely compute the covariance matrix Ck and the mean vector Sk for each class k. In this section, we analyze steps to compute Ck and Sk. So finally, we propose a protocol through analysis steps. Xi = (x1, x2, ..., xm) be the column vector ith of the data set D (i = 1, . . . , n). We denote Yk = (y1, y2, ..., ym) be a vector that yi = 1 mk if the row ith of the data set belongs to the class k else yi = 0, where mk be the number of rows of the data set belong to class k. Let Xki be the mean of the vector Xi in the class k, then: X k i = ∑m j=1 xjyj = 〈Xi, Yk〉 It should be noted that Sk = (X k 1, X k 2, .., X k n). Therefor, to compute Sk, we have to address the computation of a scalar product of two vector Xi and Yk. if Xi and Yk belong to the same party, then this work is locally completed without disclosing private data of any parties. If Xi and Yk belong to two different parties, then we use the secure scalar product protocol. To continue, we have to address the computation of Ck. Let Xˆi = (xˆ1, xˆ2, ..., xˆm) be a vector that each element xˆi = xi − Xki . we denote Yk′ = (y1′ , y′2, ..., y′m) be a vector that each yi′ = 1 mk − 1 if the row i th of the data set belongs to class k else yi′ = 0. Each the element (I, j)th of Ck is determined by 78 Privacy preserving multivariate classification based on tree-vector product protocol Ck(i, j) = m∑ t=1 xˆ (i) t xˆ (j) t y ′ k = 〈Xˆi, Xˆj , Yk′〉 We assume without loss of generality that only one party Pc (c ∈ {1, 2, . . . , K}) has the class attribute Y . We can divide this into three possibilities: - Three vectors Xi, Xj and Yk belong to the same party, then C(I, j) is locally computed without disclosing any private information. - Three vectors Xi, Xj and Yk belong to two parties. We can use Protocol 3 to address this case. - Xi, Xj and Yk belong to three different party. We address this problem by Protocol 1 or Protocol 2. The above analysis has showed that we can securely compute the mean vector and the covariance matrix by proposed protocols in section 3. Based on the compo- sition theorem and derivation of proposed protocols, our computations can privately make the shares of the mean vector and the covariance matrix for each class k. 3. Conclusion The major contributions of this paper are a privacy preserving multivariate classification for vertically partitioned data, in which only subsets of parties know class attribute. To address the above problem, three- vector product protocol was proposed in this paper. There is another direction for our future works that devel- oping multiple-vectors products protocol is a non-trivial extension, especially if we consider collusion between parties as well. This goal is to develop other efficient pri- vacy preserving data mining methods such as Association Rules, Network Bayesian, etc. REFERENCES [1] J. Han and M. Kamber. Data Mining Concepts and Techniques. Morgan Kauf- mann Publishers, 2001. [2] W.L. Du, Yunghsiang S. Han and S. Chen. Privacy-preserving multivariate sta-