With the advent of artificial intelligence, machine learning has been well explored and extensively applied into numerous fields, such as pattern recognition, image processing and cloud computing. Very recently, machine learning hosted in a cloud service has gained more attentions due to the benefits from the outsourcing paradigm. Based on cloud-aided computation techniques, the heavy computation tasks involved in machine learning process can be off-loaded into the cloud server in a pay-per-use manner, whereas outsourcing large-scale collection of sensitive data risks privacy leakage since the cloud server is semi-honest. Therefore, privacy preservation for the client and verification for the returned results become two challenges to be dealt with. In this paper, we focus on designing a novel privacy-preserving single-layer perceptron training scheme which supports batch patterns training and verification for the training results on the client side. In addition, adopting classical secure two-party computation method, we design a novel lightweight privacy-preserving predictive algorithm. Both two participants learns nothing about other’s inputs, and the calculation result is only known by one party. Detailed security analysis shows that the proposed scheme can achieve the desired security properties. We also demonstrate the efficiency of our scheme by providing the experimental evaluation on two different real datasets.
Hinweise
Communicated by B. B. Gupta.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
According to the report that the quantity of available data generated will be exceed 15 zettabytes by 2020 compared with 0.9 zettabytes in 2013 Adshead (2014). With the increasing amount of data generated by various equipments, machine learning techniques have been drawing more attentions. As we all known, machine learning is used to process abundant data and produce predictive models. Very recently, machine learning has been extensively applied in plenty of research fields (Chang et al. 2017a, b; Chang and Yang 2017; Chang et al. 2017), such as spam classification Yu and Xu (2008), disease diagnosis Fakoor et al. (2013), credit-risk assessment Yu et al. (2008). Generally speaking, machine learning techniques consist of two stages, i.e., training and prediction. Given a set of training data records and desired outputs, a predictive model can be finally derived after a series of iteration. In prediction paradigm, taking some new data as inputs the trained model can predict the classification or a certain continuous value. Especially, among numerous machine learning frameworks, neural network has gained much popularity due to its nice performance in many research goals. As one of the most simplest neural network tools, single-layer perceptron (SLP) Shynk (1990) has been successfully used to predict classification.
Due to the limited local storage and computing resources, cloud-based machine learning paradigm is becoming a newly developing research area. Cloud computing makes it possible to view computing as a kind of resource (Chen and Zhong 2009; Chen et al. 2016, 2015a, b, 2014a, b). In addition, the client can off-load their heavy computational tasks to the cloud server in a pay-per-use manner (Gao et al. 2018; Jiang et al. 2017, 2016, 2018; Li et al. 2015a, b, 2017a, b, 2016; Wang et al. 2015; Wen et al. 2014). Although there exist many benefits in cloud computing, this outsourcing paradigm may result in privacy leakage issue (Zhang et al. 2017a, b). In most cases, the inputs of the clients may contain some sensitive information and the cloud server is honest but curious. Therefore, considering the privacy protection into SLP training process in cloud computing is a significant challenge to deal with. Moreover, for some reasons such as hardware failures, software bugs or even malicious attacks, the cloud server may return a computationally indistinguishable result. In this case, the client should have the ability to check the validity of the returned result, which is a necessity in cloud-based SLP training process. Otherwise, outsourcing the complexity training task will become an impossible and meaningless issue.
Anzeige
Considering privacy protection in SLP training, traditional cryptographic primitives such as fully homomorphic encryption (FHE) can make it possible. However, the existing FHE schemes are not practical and efficient Wang et al. (2015). Recently, Zhang et al. (2018) proposed an efficient and privacy-preserving disease prediction scheme using SLP learning algorithm, named PPDP. In training stage, each medical sample is encrypted before uploading to the cloud server, which costs \(O(n^{3})\) on the hospital (client) side. It implies that if the number of iterative round is exactly equals to the number of training samples, it will make no sense to resort to the cloud server. The reason is that the most complicated calculation involved in SLP training stage costs \(O(n^{3})\) in Zhang et al. (2018). Besides, the verification mechanism is not considered in Zhang et al. (2018), and then the cloud server can deceive the hospital (client) by sending back an invalid result. Apart from that, the predictive model trained by the client, to some extent, should be regarded as the client’s own asset and well protected during predictive stage. Moreover, since a new record is submitted by the requester, the predictive result should be protected and only be known by itself. Therefore, it is urgent and necessary to design an efficient and secure SLP training scheme which satisfies the aforementioned requirements.
1.1 Contributions
In order to address the issues mentioned above, we propose a verifiable privacy-preserving SLP training scheme (VPSPT) with the aid of the cloud server. Our contributions are summarized as follows.
We propose a novel SLP training scheme, which can derive s predictive models for s different patterns simultaneously. Furthermore, based on the technique of mini-batch Mohassel and Zhang (2017), the trained model \(\mathbf w \) can smoothly and rapidly converge to the optimum value. Compared with the scheme in Zhang et al. (2018), the computational complexity can be dramatically reduced from \(O(n^3)\) to \(O(n^{2})\).
We first introduce the verification mechanism into SLP training scheme. If the cloud server cheats the client by returning an incorrect value, the dishonest behavior will be detected by the client definitely.
We design a lightweight privacy-preserving predictive algorithm based on secure two-party computation Malek and Miri (2006). With this method, both the predictive model \(\mathbf w \) and the new data record can be well protected. Moreover, the final classification result is only privately hold by the requester.
The rest of this paper is organized as follows: Sect. 2 presents some basic notations and concepts involved in our scheme. The system and security models are given in Sect. 3. In the following, we propose a concrete scheme containing training and predictive stages in Sect. 4, followed by security and efficiency analysis in Sect. 5. Experimental evaluation is given in Sect. 6. Finally, conclusions will be made in Sect. 7.
1.2 Related work
Differing from traditional machine learning methods, cloud-aided privacy-preserving machine learning has been well explored and drawn more attentions. Clifton et al. (2002) presented a survey on some basic tools for privacy-preserving distributed data mining. As a toolkit, these techniques can be used to solve some privacy-preserving machine learning problems. Graepel et al. (2012) proposed a new class of machine learning algorithms where the predictions can be expressed as polynomials of bounded degree. Nikolaenko et al. (2013) designed a privacy-preserving ridge regression on hundreds of data records, which can be regard as a building block for many machine learning operations. Raymond et al. Tai et al. (2017) studied privacy-preserving decision trees evaluation via linear functions, and more. Generally speaking, privacy-preserving machine learning can be roughly divided into two research goals, data perturbation and cryptographic tools. The first method can be represented by differential privacy, which has been successfully applied into protecting the privacy of statistical database (Li et al. 2016; Zhang and Zhu 2017; Abadi et al. 2016). What we have to emphasize is that the first method is orthogonal to our work, and the readers can refer to related papers for further study.
The second research area is supported by cryptographic methods. Gupta et al. (2016) identified emergent research and techniques being utilized in the field of cryptology and cyber threat prevention. Zheng et al. (2017) proposed a lightweight authenticated encryption scheme based on chaotic SCML for railway cloud service. Ibtihal and Naanani (2017) focused on secure outsourcing of images by using homomorphic encryption in mobile cloud computing environment. Bhushan and Gupta (2018) proposed a flow confidence-based discrimination algorithm to distinguish between flash crowd event and DDoS attack. By incorporating Shamir’s secret sharing and quantum byzantine agreement, AlZain et al. (2015) presented a practical data management model in a public and private multi-cloud environment. Lin et al. (2018) constructed a new ID-based linear homomorphic signature scheme, which avoided the shortcomings of the use of public-key certificates. Gao et al. (2018) proposed a privacy-preserving Naive Bayes classifier that is resistant to an easy-to-perform, but difficult-to-detect attack. Li et al. (2018) proposed a novel privacy-preserving Naive Bayes learning scheme with multiple data sources.
Anzeige
Based on the computational ability of participants, the second research field, cryptographic methods, can be split into two categories. The first scenario is training without the cloud server. That implies that all the participants are equal to each other in computational ability aspect. So far, plenty of works focus on this setting. Chen and Zhong (2009) proposed privacy-preserving backpropagation neural network learning scheme which allowed two parties jointly to train model over vertically partitioned data. In the following, based on their aforementioned work, Bansal et al. (2001) proposed a training scheme over arbitrarily partitioned data, which can be applied into more common scenes. In both two schemes (Bansal et al. 2001; Chen and Zhong 2009), the privacy of client can be guaranteed by using ElGamal scheme. Combined with several data-oblivious algorithms, Ohrimenko et al. (2016) designed a method to enable multiple parities to cooperatively conduct training program while each parties’ privacy can be well protected. Very recently, based on the two servers model, Mohassel and Zhang (2017) proposed a system for scalable privacy-preserving machine learning. In this model, the data owners randomly distribute data to two non-conclude servers to train several models. Among them, they focused on training neural networks by using secure two-party or multiparty computation theory.
Obviously, the second scenario is where the training process involves in the cloud server. This implies that the resource-constrained client relies on the powerful cloud server to train models. Li et al. (2017) proposed multi-key privacy-preserving deep learning schemes. Liu et al. (2017) only explored the privacy-preserving predictive process, which requires no change to how models are trained. After prediction, the server learns nothing about client’s inputs while the client learns nothing about the model. Very recently, considering the privacy protection of training stage, Wang et al. (2015) proposed a SLP learning scheme for e-healthcare. However, this scheme adopted Paillier homomorphic cryptosystem, which is time-consuming. In Zhang et al. (2018), a privacy-preserving disease prediction scheme in cloud-based e-healthcare system are proposed. Although this scheme provided the hospital (client) privacy protection in predictive stage, the privacy of patients (potential patients) was not considered, whereas in some specific scenarios it is necessary to design privacy-preserving algorithm in predictive stage. Besides, random matrices in Zhang et al. (2018) are utilized to encrypt training samples as we mentioned before, it is not efficient and practical.
2 Preliminaries
In this section, we will present some basic notations, machine learning and mathematical tools. Firstly, we briefly revisit the classical SLP learning algorithm which can be referred to in many standard machine learning textbooks Michalski et al. (2013). Furthermore, based on the basic idea in Mohassel and Zhang (2017), we propose a mini-batch SLP training scheme. In the following, we will introduce the privacy-preserving method for large-scale matrix multiplication in cloud computing Lei et al. (2014). Finally, we will give a secure dot-secure technique by using trace functions Malek and Miri (2006).
2.1 Mini-batch SLP training algorithm
In this section, we will recall the principles and some main properties of SLP. As one of the most important and simplest neural network architectures, SLP can be used as a powerful classifier whose output belongs to one class or another. Given a set of training data samples \(\mathbf X =\left\{ \mathbf x _{1}, \mathbf x _{2},\ldots ,\mathbf x _{n} \right\} \) with associated desired output \(\left\{ o_{1}, o_{2},\ldots , o_{n}\right\} \) (\(o_{i}\in \left\{ 1, -1\right\} \)), the goal of the SLP training algorithm is to obtain a prediction model. In most cases, when a new data record is submitted to this prediction model, it can give an accurate classification result t. The basic framework of SLP is depicted in Fig. 1. And in the following, let’s look the SLP training algorithm in detail.
Fig. 1
Model of single-layer perceptron
×
As we can see from Fig. 1, the SLP consists of two layer neuron cells, input nodes and output node. Among these nodes, the input nodes are denoted as \(\left\{ x_{i,1}, x_{i,2},\ldots ,x_{i,n}\right\} \) which means each piece of sample \(\mathbf x _{i}\) has n features. The output layer is a linear combination of input nodes and weight vector \(\mathbf w =\left\{ w_{1}, w_{2},\ldots , w_{n}\right\} \). After that, a specific activation function is acted on the output node, and then it outputs the classification result \(t_{i}\in \left\{ 1,-1 \right\} \). In this paper, we select the sign function as the activation function since its simplicity and popularity.
$$\begin{aligned} t_{i}=sign(\mathbf w ^{T}{} \mathbf x _{i}) \end{aligned}$$
If \(o_{i}\ne t_{i}\), the weight parameter w will be updated according to the following equation:
$$\begin{aligned} \mathbf w =\mathbf w + \eta \mathbf x _{i}o_{i} \end{aligned}$$
Different from traditional SLP training algorithm, based on the intuition presented in Mohassel and Zhang (2017) we randomly select a small batch m of samples instead of a piece of sample per iteration, because the overwhelming advantage of mini-batch method is that it can be used to speed up the computation. Besides, with this method, the weight vector \(\mathbf w \) can converge faster to the minimum value. Therefore, the weight vector \(\mathbf w \) can be updated by averaging the partial derivatives of m samples on the current \(\mathbf w \). For some \(t_{i}\ne o_{i}\), the updating formula for weight \(\mathbf w \) can be adapted as:
$$\begin{aligned} \mathbf w =\mathbf w + \frac{\eta }{m}{\textstyle \sum \limits _{t_{i}\ne o_{i}}}{} \mathbf x _{i}o_{i} \end{aligned}$$
If it meets one of the two requirements, the number of iterations more than the preset threshold or the prediction model converges to a constant, the SLP training algorithm will be terminated. Furthermore, the elaborate mini-batch SLP training algorithm is described in Algorithm 1.
×
Fig. 2
Model of our VPSPT scheme
×
2.2 Privacy-preserving method for outsourcing matrix multiplication
Securely outsourcing large-scale matrix multiplication has been researched for many years (Atallah et al. 2002; Lei et al. 2014), which is commonly used as the building block in scientific and engineering fields. Next, we will introduce a completed protocol for securely outsourcing matrix multiplication which consists of five algorithms \((\mathbf{KeyGen }\), \(\mathbf{MMEnc }\), \(\mathbf{Compute }\), \(\mathbf{MMDec }\), \(\mathbf{Verify })\) as follows.
KeyGen: On input the security parameter \(\lambda \), the client randomly chooses three sets \(\left\{ \alpha _{1}, \alpha _{2},\ldots ,\alpha _{n}\right\} \), \(\{\beta _{1}, \beta _{2},\ldots , \beta _{n}\}\) and \(\left\{ \gamma _{1}, \gamma _{2},\ldots , \gamma _{n}\right\} \) from specific key space. By using the same method in Lei et al. (2014), the client generates three random permutations, \(\pi _{1}, \pi _{2}, \pi _{3}\). Similarly, the client generates three sparse matrices, \(\mathbf F _{1}(i,j)=\alpha _{i}\delta _{\pi _{1}(i),j}, \mathbf F _{2}(i,j)=\beta _{i}\delta _{\pi _{2}(i),j}, \mathbf F _{3}(i,j)=\gamma _{i}\delta _{\pi _{3}(i),j} \), where the formula of the Kronecker delta function \(\delta _{x,y}\) is as follows. \(\delta _{x,y}=\left\{ \begin{aligned} 1,\quad x=y\\ 0,\quad x\ne y\\ \end{aligned} \right. \)
MMEnc: Given two large-scale matrices \(\mathbf X , \mathbf Y \), the resource-constrained client needs to calculate matrix multiplication. In order to protect his own private information, the client will encrypt his inputs before uploading them to the cloud server to compute with. Therefore, by using the matrix blinding technique the client computes \(\hat{\mathbf{X }}=\mathbf F _{1}{} \mathbf X {} \mathbf F _{2}^{-1}\) and \(\hat{\mathbf{Y }}=\mathbf F _{2}{} \mathbf X {} \mathbf F _{3}\) locally and sends the blinding inputs \(\hat{\mathbf{X }}, \hat{\mathbf{Y }}\) to the cloud server.
Compute: After receiving two matrices \(\hat{\mathbf{X }}, \hat{\mathbf{Y }}\) from the client, the cloud server conducts this algorithm to compute \(\hat{\mathbf{T }}=\hat{\mathbf{X }}\hat{\mathbf{Y }}\). Subsequently, the cloud server sends the blinding result \(\hat{\mathbf{T }}\) to the client.
MMDec: On input the returned result \(\hat{\mathbf{T }}\), the client will decrypt it, \(\mathbf T =\mathbf F _{1}^{-1}\hat{\mathbf{T }}{} \mathbf F _{3}^{-1}=\mathbf X {} \mathbf Y \). Therefore, the client will obtain the final result.
Verify: Considering the cloud server is honest but curious, after decrypting the result the client should check the correctness of the calculation result \(\mathbf T \). The client firstly selects a vector \(\mathbf r =\left\{ r_{1}, r_{2},\ldots , r_{n}\right\} \) and checks the equation \(\mathbf T {} \mathbf r \overset{?}{=}{} \mathbf X {} \mathbf Y {} \mathbf r \). If yes, the result \(\mathbf T \) will pass verification; otherwise, this algorithm will output \(\bot \).
2.3 Secure dot-product protocol
Definition 1
A trace function is a linear mapping from \(\mathbb {F}_{p^{n}}\) over \(\mathbb {F}_{p^{q}}\), where q can divide n. Let’s denote that \(\alpha \in \mathbb {F}_{p^n}=F\) and \(\alpha \in \mathbb {F}_{p^q}=K\), then the trace of element \(\alpha \) over K is:
For \(\alpha , \in \mathbb {F}_{p^{n}}\), \(T(\alpha ^{p})=T(\alpha )\).
Suppose that \(\left\{ \alpha _{1}, \alpha _{2},\ldots , \alpha _{n}\right\} \) is a basis of \(\mathbb {F}_{p^{n}}\) over \(\mathbb {F}_{p}\), and \(\left\{ \beta _{1}, \beta _{2},\ldots , \beta _{n}\right\} \) is its dual basis that satisfies the following equation.
Most important of all, we have the following equation holds.
$$\begin{aligned} T(\mathbf X {} \mathbf Y )=\mathbf x \cdot \mathbf y \end{aligned}$$
3 System and security models
In this section, we focus on formalizing the system model and security model.
3.1 System model
In this paper, we propose an efficient and secure VPSPT scheme, which consists of three entities, the client, the cloud server and the requester. Furthermore, the system model of VPSPT scheme is described as Fig. 2.
The client The main task of the client is to train s prediction models for s different patterns. The client takes the training cases \(\left\{ x_{i,j}\right\} \)\((1\le i\le n, 1\le j\le m)\), random weight \(\left\{ w_{j,k}\right\} \)\((1\le j\le m, 1\le k\le s)\), learning rate \(\eta \), the size of mini-batch n and the predetermined iteration round p as inputs. And the client takes a final weight matrix \(\mathbf W \) for s different patterns as its output.
The cloud server A cloud server possesses substantial computation and storage resources. With the help of the cloud server, the client can outsource the heavy computational operations in order to save the local resources by pay-per-use manner. Generally speaking, the cloud server is curious but honest. That is, the cloud server can follow the protocol honestly, but he will try his best to dig up some sensitive information beyond what he has known.
The requester A requester who owns a new data record wants to know the classification result under a specific prediction model. On the one hand, the new data record is privately held by the requester. On the other hand, the specific prediction model belongs to the client’s own asset which costs the client substantial resources to obtain. Therefore, the requester should learn nothing about the prediction model other than the final result.
3.2 Security model
In training stage, we consider that the adversary is an untrusted server in honest but curious model Goldreich et al. (1987) (also called “semi-honest"). That is, the cloud server will faithfully follow the protocol, but he may try to learn additional information by analyzing the messages that he receives during the execution. In predictive process, we assume that both the client and the requester are honest but curious. On the one hand, the query record submitted by the requester may contain some private information and should not be leaked to others. On the other hand, the malicious requester may want to know the training model which is the client’s own asset. Therefore, in our threat model, it must be ensured that each party learns nothing beyond what they should know.
In this paper, our aim is to propose an efficient and verifiable SLP training scheme which can produce s prediction models for different patterns. In the meanwhile, we aim at guaranteeing the privacy protection both in training and predictive stages. Besides, the following properties should be satisfied.
Privacy In training stage, we require that the client’s data are secure against the cloud server. Given the encrypted sample cases, the cloud server cannot get the client’s original data. Furthermore, the result is also hidden from the server. In predictive stage, both the new query record and prediction model should be well protected. That is, the two participants cannot learn nothing beyond what they have known.
Verifiability Since the cloud server is semi-honest, the client should have the ability to detect errors. That is to say, any error result from a cheating cloud server cannot pass the verification.
Efficiency In training process, for the client, the computation cost for preparing outsourcing calculation task to the cloud server and extracting the results from the returned values should be less than that of computing the computation task by its own.
4 The proposed VPSPT scheme
4.1 High description
In this section, we will outline the training process for s different models from a set of training sample cases. On the one hand, we adopt the main idea in Mohassel and Zhang (2017) to choose mini-batch cases instead of a piece of case per iteration. That is to say, using the stochastic gradient descent method we expand the sample vector \(\mathbf x =\left\{ x_{1}, x_{2},{\ldots } x_{n} \right\} \) into the matrix \(\mathbf X =\left\{ x_{i,j}\right\} \) (\(1\le i\le n, 1\le j\le m\)) to improve the iteration speed. On the other hand, since the same batch of cases can be used to train for different models, then we can train s different models \(\mathbf W =\left\{ w_{j,k}\right\} \)\((1\le j\le m, 1\le k\le s)\) simultaneously. In the training process, the client off-loads the heavy computation task to the cloud server with the help of the cloud computing architectures. Since the cloud servers are semi-honest, the client should conduct some blinding operations to encrypt input matrices \(\mathbf X \) and \(\mathbf W \) before uploading them. By using the random permutations and sparse matrix techniques which were firstly proposed by Atallah et al. (2002), we can achieve the aim of protecting privacy of the client.
Due to some financial reasons or hardware failures in cloud computing, the client must have the ability to detect errors in each iteration process. Compared to the existing works, we propose an efficient and verifiable SLP training algorithm. After decrypting the results returned by the cloud server \(\mathbf Y \), the client randomly selects a vector \(\mathbf r \) and checks whether the equation \(\mathbf X {} \mathbf W {} \mathbf r =\mathbf Y {} \mathbf r \) holds. If yes, the calculation result \(\mathbf Y \) will pass the verification.
Next, for some misclassification cases, the client will update the weight parameter \(\mathbf w _{k}\) following to the updating formula we mentioned before. If the training algorithm achieves the iteration termination condition, this algorithm will output s different models for s different patterns. Otherwise, the client will continue to conduct the training scheme for next round.
For a new coming case, based on trace function Malek and Miri (2006), we propose a lightweight privacy-preserving predictive algorithm. At the end of this algorithm, only will the requester know the prediction result. Besides, considering that the inputs of the requester contain some sensitive personal information, and the trained model \(\mathbf w _{k}\) is owned by the client, it is essential to design a privacy-preserving predictive algorithm. By this way, the client learns nothing about the inputs of the requester, and vice versa.
4.2 Verifiable privacy-preserving SLP training scheme
In this section, we propose the VPSPT scheme, which is composed of three stages, initialization, training stage and predictive stage. Moreover, the elaborate training process and predictive stage are described in Algorithm 2 and Algorithm 3, respectively.
Initialization Firstly, in order to protect the client’s sensitive information, it is necessary to encrypt the input information before uploading them to the cloud server. Therefore, the client conducts KeyGen algorithm to generate three secret sparse matrices \(\mathbf F _{1}\in \mathbb {R}^{n\times n}, \mathbf F _{2}\in \mathbb {R}^{m\times m}\) and \(\mathbf F _{3}\in \mathbb {R}^{s\times s}\), which are used to blind input matrices. Secondly, the client randomly selects a weight matrix \(\mathbf W \in \mathbb {R}^{m\times s}\) where all elements are equal to small random numbers.
Training stage In the following, the completed protocol will be depicted. The privacy-preserving and verifiable SLP training scheme is described by Algorithm 2.
Step 1 Based on the mini-batch idea in Mohassel and Zhang (2017), the client randomly selects a small batch of samples instead of a piece of data per iteration. The client chooses n pieces of training data \(\left\{ \mathbf x _{1}, \mathbf x _{2},\ldots \mathbf x _{n} \right\} \) with associated desired outputs \(\left\{ \mathbf o _{1}, \mathbf o _{2},\ldots \mathbf o _{n} \right\} \), and each piece of training data has m feature values. Hence, we denote these training data as matrix \(\mathbf X \in \mathbb {R}^{n\times m}\). In order to protect the sensitive information of the client \(\mathbf X \) and the training models \(\mathbf W \), the client needs to conduct the MMEnc algorithm to obtain \(\hat{\mathbf{X }}=\mathbf F _{1}{} \mathbf X {} \mathbf F _{2}\) and \(\hat{\mathbf{W }}=\mathbf F _{2}^{-1}{} \mathbf W {} \mathbf F _{3}\), and then uploads the ciphertext tuple \(\left\langle \hat{\mathbf{X }}, \hat{\mathbf{W }} \right\rangle \) to the cloud server.
Step 2 Upon receiving the ciphertext tuple \(\left\langle \hat{\mathbf{X }},\hat{\mathbf{W }} \right\rangle \) from the client, the cloud server executes the matrix multiplication function, i.e., \(\hat{\mathbf{Y }}=\hat{\mathbf{X }}\times \hat{\mathbf{W }}\). In the following, the cloud server sends the blinding training result \(\hat{\mathbf{Y }}\) to the client.
Step 3 In this step, the client conducts the decryption operation as \(\mathbf Y =\mathbf F _{1}^{-1} \hat{\mathbf{Y }} \mathbf F _{3}^{-1} \) and derives the final result matrix \(\mathbf Y \). Furthermore, in order to build confidence of the outsourcer, the client will check the correctness of the computation result \(\mathbf Y \) which is returned by the cloud server. Firstly, the client randomly selects a vector \(\mathbf r =\left\{ r_{1}, r_{2},{\ldots } r_{s} \right\} \) where not all elements are equal to zero. Secondly, the client locally calculates \(\mathbf Y {} \mathbf r \) and \(\mathbf X {} \mathbf W {} \mathbf r \), respectively, and checks whether they are equal to each other. If yes, the computation result \(\mathbf Y \) will pass the verification. Otherwise, the client will terminate this algorithm.
Step 4 To simplify the representation, we select one column of matrix \(\mathbf Y \) and denoted by \(\mathbf y _{k}\). It implies that we just elaborately discuss the training process of a specific model and other models are trained by the same method. Later, for each element of the vector \(\mathbf y _{k}\), the client executes the sign function as
and then the client compares each element of the \(\left\{ t_{i,k} \right\} \) with the desired classification results \(\left\{ o_{i,k} \right\} \) detailedly. For some \(t_{i,k}\ne o_{i,k}\) (for \(1\le i\le n\)), the client updates the weight vector \(\mathbf w _{k}\) as
$$\begin{aligned} \mathbf w _{k}=\mathbf w _{k}+\frac{\eta }{n}{\textstyle \sum \limits _{t_{i,k}\ne o_{i,k}}}{} \mathbf x _{i}o_{i,k} \end{aligned}$$
If the weight vector \(\mathbf w _{k}\) satisfies one of the two terminating conditions, i.e., the number of iteration round exceeds the preset value or all classification results for this model are correct, the SLP training algorithm will be terminated and go to step 5. Otherwise, the client will repeat the steps from step 1 with the help of the cloud server.
Step 5 In this paper, we assume that these s models synchronously achieve the convergence condition or they have the same preset threshold. After several iterations by conducting above training process, finally, the client obtains s prediction models from a set of samples for s different patterns.
Predictive stage To predict a new data record for the requester, based on the main idea in Malek and Miri (2006) we design a lightweight privacy-preserving predictive algorithm to obtain the classification result. The requester who owns the new data tuple \( \mathbf x =\left\{ x_{1}, x_{2},{\ldots } x_{n} \right\} \) will cooperate with the client owned the predictive model \( \mathbf w =\left\{ w_{1}, w_{2},{\ldots }w_{n} \right\} \) to conduct the predictive algorithm. Finally, only will the requester know the final classification result. What’s more, the client learns nothing about the requester’s input and the requester learns nothing about the model within the whole process. Especially, the predictive algorithm consists of the following three steps.
Step 1 Assume that \(\left\{ \alpha _{1}, \alpha _{2},\ldots \alpha _{n} \right\} \) is a basis of \(\mathbb {F}_{{p}^{n}}\) over \(\mathbb {F_{p}}\), and \(\left\{ \beta _{1}, \beta _{2},\ldots \beta _{n} \right\} \) is its dual basis. Therefore, the two vectors \(\mathbf X \) and \(\mathbf W \) can be presented over \(\mathbb {F}_{{p}^{n}}\) as
The requester randomly chooses \(\mathbf Z \in \mathbb {F}_{{p}^{n}}\), and \(a,b,c,d\in \mathbb {F}_{p}\), s.t. \((ad-bc)\ne 0\). Next, the requester locally computes the two following messages
$$\begin{aligned} \mathbf M= & {} a\mathbf X +b\mathbf Z \\ \mathbf N= & {} c\mathbf X +d\mathbf Z . \end{aligned}$$
Then, the requester sends the ciphertext tuple \(\left\langle \mathbf M , \mathbf N \right\rangle \) to the client for prediction.
Step 2 On receiving the ciphertext tuple \(\left\langle \mathbf M , \mathbf N \right\rangle \) from the requester, the client who owns the model \(\mathbf w \) will compute
$$\begin{aligned} \mathbf W {} \mathbf M =\mathbf W (a\mathbf X +b\mathbf Z )\\ \mathbf W {} \mathbf N =\mathbf W (c\mathbf X +d\mathbf Z ). \end{aligned}$$
In the meanwhile, the client computes the trace function \(T(\mathbf W {} \mathbf M )\), \(T(\mathbf W {} \mathbf N )\) and sends them to the requester.
Step 3 After receiving the trace functions from the client, the requester who owns the random numbers a, b, c, d will compute the message
$$\begin{aligned} o=(ad-bc)^{-1}(d\ T(\mathbf W {} \mathbf M )-b\ T(\mathbf W {} \mathbf N )). \end{aligned}$$
Subsequently, the requester conducts the activation function, i.e., \(t=sign(o)\). Therefore, the requester can obtain the final classification result t in secure manner without privacy information leakage. The detailed predictive algorithm is depicted in Algorithm 3.
×
×
4.3 Correctness
In this section, we will present the correctness of VPSPT scheme both in training stage and predictive stage, respectively.
Training stage In step 2 and step 3, on receiving the blinding result \(\hat{\mathbf{Y }}\), the client who possesses the secret keys \(\mathbf F _{1}^{-1}\) and \(\mathbf F _{3}^{-1}\) will conduct the following decryption operations.
$$\begin{aligned} \mathbf F _{1}^{-1}\hat{\mathbf{Y }}{} \mathbf F _{3}^{-1}&= \mathbf F _{1}^{-1}\hat{\mathbf{X }}\hat{\mathbf{W }}{} \mathbf F _{3}^{-1} \\&=\mathbf F _{1}^{-1}{} \mathbf F _{1}{} \mathbf X {} \mathbf F _{2}{} \mathbf F _{2}^{-1}{} \mathbf W {} \mathbf F _{3}{} \mathbf F _{3}^{-1}\\&= \mathbf X {} \mathbf W =\mathbf Y \end{aligned}$$
By selecting a random vector \(\mathbf r \), the client checks \(\mathbf Y {} \mathbf r \overset{?}{=}{} \mathbf X {} \mathbf W {} \mathbf r \). If the result passes verification, that means the client can derive a series of correct computational results. In addition, the rest of training tasks per round are conducted by the client locally.
Predictive stage Next, we will illustrate the correctness of the predictive algorithm. After receiving two trace functions \(T(\mathbf WM )\) and \(T(\mathbf WN )\) from the client, the requester privately computes
$$\begin{aligned} o&= (ad-bc)^{-1}(d\ T(\mathbf W {} \mathbf M )-b\ T(\mathbf W {} \mathbf N ))\\&=(ad-bc)^{-1}(d\ T(\mathbf W (a\mathbf X +b\mathbf Z ))\\&\quad -b\ T(\mathbf W (c\mathbf X +d\mathbf Z )))\\&=(ad-bc)^{-1}(ad-bc)T(\mathbf XW )\\&= T(\mathbf X {} \mathbf W ) \ mod\ p\\&= \mathbf x \cdot \mathbf w \end{aligned}$$
Later, the requester carries out the sign function to achieve the final classification result \(t=sign(o)\).
5 Security and efficiency analysis
In this section, we will present the security and efficiency analysis for our proposed VPSPT scheme.
5.1 Security analysis
In training and predictive stages, the training sample cases contain some private information. And the training process of the prediction models also requires substantial resources. In other words, these trained models are valuable assets owned by the client. In addition, the query record submitted by the requester contains some personal private information. Therefore, the training sample cases, prediction models and the query record should be well protected. That is, the cloud server, the client and the requester cannot learn anything other than what they have known.
In fact, in VPSPT scheme, most of the training process are carried out on the client side only apart from the process of outsourcing complicated computation. Therefore, we will elaborately present the security analysis for the whole process of outsourcing computation.
Theorem 1
The proposed training algorithm can ensure the input and output privacy of the client.
Proof
Considering that the client encrypts two input matrices \(\mathbf X \) and \(\mathbf W \), the semi-honest cloud server cannot recover the original matrices. Concretely, the client’s samples matrix \(\mathbf X \) is multiplied by two sparse matrices \(\mathbf F _{1}\) and \(\mathbf F _{2}\). In other words, each element in matrix \(\mathbf X \) is rearranged under both the row and column permutations. In addition, each element is further blinded by multiplying a factor, i.e., \((\alpha _{i}/\beta _{k})\). These entries both in matrices \(\mathbf F _{1}\) and \(\mathbf F _{2}\) are all not zero, and there exists exactly one nonzero value in each row or column. That implies that if an attacker launches a brute-force attack to obtain the two secret key sets \(\left\{ \alpha _{1}, \alpha _{2},\ldots , \alpha _{n}\right\} \) and \(\left\{ \beta _{1}, \beta _{2},\ldots , \beta _{n}\right\} \), the success probability is \( \frac{1}{|K_{\alpha }|^{n}|K_{\beta }|^{n}}\). And furthermore, the success probability of recovering the original position in matrix \(\mathbf X \) is \(((n!)^{2})\). Obviously, the security level for input privacy depends on the size of key space. A choice of enough large key spaces \(|K_{\alpha }|\) and \(|K_{\beta }|\) can threat this attack effectively. Likewise, the input privacy of weight matrix \(\mathbf W \) can be guaranteed in the same way. Similarly, the semi-honest cloud server cannot recover the final result \(\mathbf Y \) from the blinded result \(\hat{\mathbf{Y }}\). In this paper, we will omit the security analysis for output privacy since it can be analyzed in the same way with that of input privacy. Supposed that even the cloud server know the final result \(\mathbf Y \) for some other reasons, it does not make any sense for the cloud server. Because the desired output for training sets is privately held by the client, and the iterative process of weight matrix \(\mathbf W \) is also conducted on the client side. \(\square \)
Theorem 2
The privacy of requester can be guaranteed in the proposed predictive algorithm.
Proof
Given the ciphertext tuple \(\left\langle \mathbf M , \mathbf N \right\rangle \), for some random number a, b, c, d and suitable choice of \(\mathbf Z \), there exist many \(\mathbf X \in \mathbb {F}_{p^{n}}\) that can ensure the following matrix equation holds.
$$\begin{aligned} \left( \begin{array}{cc} a &{} b \\ c &{} d \\ \end{array} \right) \left( \begin{array}{c} \mathbf X \\ \mathbf Z \\ \end{array} \right) = \left( \begin{array}{c} \mathbf M \\ \mathbf N \\ \end{array} \right) \end{aligned}$$
The process of guessing the true value for \(\mathbf X \) can be considered as solving the above equations. We use the symbol S for marking the set of all \(\mathbf X \)’s when given the same \(\left\langle \mathbf M , \mathbf N \right\rangle \). Therefore, the success probability of the client (adversary) is \(\frac{1}{|S|}\). In order to make the right guess for \(\mathbf X \), the client has to have the ability to find all invertible matrices of two multiplied by two over \(\mathbb {F}_{p}\). The number of invertible 2-by-2 matrices over \(\mathbb {F}_{p}\) is \((p^{2}-1)(p^{2}-1)=\mathbf O (p^{4})\). Without any doubt, the number of invertible 2-by-2 matrices represents the size of S. This implies that we can reduce the success probability of the adversary by increasing the size of S. For the convenience of understanding, we assume that the requester’s inputs are selected from \(\mathbb {F}_{p^{m}}\) instead of \(\mathbb {F}_{p}\). Similar to above analysis, the size of S is changed into \((p^{2m}-1)(p^{2m}-p^{m})=\mathbf O (p^{4m})\). Therefore, we have
In practice, \(2^{80}\) can be considered to resist brute-force attack. At least, we choose \(p=2\) and \(m_{0}=20\) in this paper. The requester’s choice is evenly distributed over \(S\subset \mathbb {F}_{p^n}\). So far, we have presented the security analysis for the requester. \(\square \)
In the following, we will present the security analysis for the client. The reason is that the predictive model is the client’s own asset. The predictive model \(\mathbf w \) should be privately held by the client, and the requester learns nothing about \(\mathbf w \) in the execution of the predictive algorithm.
Theorem 3
The privacy of client can be guaranteed in the proposed predictive algorithm.
Proof
On receiving the trace functions \(T(\mathbf WM )\) and \(T(\mathbf WN )\), the aim of malicious requester is to find the predictive model \(\mathbf w \). As mentioned earlier, the trace function is a linear mapping from \(\mathbb {F}_{p^{n}}\) onto \(\mathbb {F}_{p}\). Then there are \(\frac{|\mathbb {F}_{p^{n}}|}{p}=p^{n-1}\) elements in \(\mathbb {F}_{p^{n}}\) which have the same trace function values as \(T(\mathbf WM )\), where we denote the size of field \(\mathbb {F}_{p^{n}}\) by \(|\mathbb {F}_{p^{n}}|\). And then the malicious requester can further increase the probability of guessing the correct \(\mathbf w \) by using the second message \(T(\mathbf WN )\). More specifically, there are \(p^{n-2}\) elements in \(\mathbb {F}_{p^{n}}\) that meet the both requirements.
$$\begin{aligned} \left\{ \begin{aligned} T(\mathbf W ^{*}{} \mathbf M )=T(\mathbf WM )\\ T(\mathbf W ^{*}{} \mathbf N )=T(\mathbf WN )\\ \end{aligned} \right. \end{aligned}$$
It’s obvious that the advantage of a malicious requester successfully guessing the predictive model can be made arbitrarily small by increasing n. Furthermore, we let \(n=km\), we can achieve the desired security by increasing m. The security parameter m satisfies the following:
$$\begin{aligned} \mathrm{Adv}_{\mathrm{requester}}=\frac{1}{p^{\mathrm{km}-2}}< \frac{1}{\mathrm{poly}(\mathrm{m})} \ (for \ m > m_{0}). \end{aligned}$$
In this section, we will present the computation overhead and communication costs of the VPSPT scheme in one round as well as the process of the predictive stage. Before terminating, the VPSPT scheme will be conducted one round by one round. In this paper, we only consider the scenario where the amount of predetermined iterative rounds for s different models are identical to each other. In other words, we preset a constant threshold for s different models before conducting the VPSPT scheme.
Computation overhead We will illustrate the computation cost containing three phases, initialization, training and prediction in Table 1. In the following, we will present the detailed efficiency analysis. In addition, we denoted by G an operation of generating a random number, M an operation of multiplication, E an operation of exponentiation, I an operation of inversion over finite field. In initialization phase, we call the KeyGen algorithm to generate three secret sparse matrices \(\mathbf F _{1}\in \mathbb {R}^{n\times n}\), \(\mathbf F _{2}\in \mathbb {R}^{m\times m}\) and \(\mathbf F _{3}\in \mathbb {R}^{s\times s}\), which cost \((n+m+s)\)G in total. In Step 1, in order to protect the sensitive information in training samples \(\mathbf X \) and s training models \(\mathbf W \), the client conducts encryption operations, which costs \((nm+ms)\)M. In step 2, after receiving the blinding inputs, the cloud server conducts the computation task according to the protocol. In fact, the cloud server multiplies \(\hat{\mathbf{X }}\) with \(\hat{\mathbf{W }}\) and achieves the blinding result \(\hat{\mathbf{Y }}\), which costs (nms)M. In Step 3, the client extracts the final result \(\mathbf Y \) from the blinding result \(\hat{\mathbf{Y }}\) by computing \(\mathbf F _{1}^{-1}\hat{\mathbf{Y }}{} \mathbf F _{3}^{-1}\), which costs (2ns)M. Since the cloud server is always semi-honest, it is necessary for the client to build the verification mechanism and check whether the returned result is correct or not. Therefore, the client conducts verification algorithm which costs (3ns)M to verify the result of decryption \(\mathbf Y \). In Step 4, the client conducts sign function to achieve the classification result \(t_{i,k}\) for training model k. For some incorrect classification results, the client updates the values of current model k. Especially, the computational overhead in this step is ranging from 0 to nM corresponding to the number of incorrect classification result ranging from 0 to n. So far, we have presented the detailed efficiency analysis for training process in each round. Besides, the rest of training process before arriving at the terminating condition is identical to the mentioned process. Next, we will introduce the efficiency analysis for our privacy-preserving predictive algorithm. Before submitting the data record to the client, the requester need to deal with some encryption operations, which costs (4n)M computational complexity. In the following, the client multiplies his own predictive model \(\mathbf W \) with the coming data record \(\left\langle \mathbf M , \mathbf N \right\rangle \), which costs (2n)M. In addition, in order to assist the requester with computing the classification result, the client needs to spend (2n)E to compute two trace functions \(T(\mathbf WM )\) and \(T(\mathbf WN )\). Finally, the requester computes the final result locally, which costs (5M+1I).
Communication overhead The communication overhead in three stages is also described in Table 1. As we can see from this table, both in training stage and predictive stage are only involved in one interaction by come-and-go manner. In training process, the client off-loads the complicated computation task to the cloud server by uploading the blinding inputs matrices \(\hat{\mathbf{X }}\) and \(\hat{\mathbf{W }}\), which costs \((nm+ms)\). The cloud server calculates the matrix multiplication and sends back the blinding result \(\hat{\mathbf{Y }}\) to the client, costing (ns). In predictive stage, the requester submits his data to predict the result with the cost of (2n). Subsequently, the client returns the two messages \(T(\mathbf WM )\) and \(T(\mathbf WN )\) to the requester with the cost of 2. Firstly, compared to the scheme in Zhang et al. (2018), our VPSPT scheme has plenty of advantages in computational cost among three phases. In Table 2, we will present the computation comparison between two schemes. We have analyzed the entire computational overhead in our scheme above, and the readers can refer to Zhang et al. (2018) for more details. We remark that the dimension of the training sample vector in Zhang et al. (2018) is also denoted by n. Secondly, in VPSPT scheme, the result returned by the cloud server can be checked by the client in order to avoid cheating by the malicious attacker. Finally, in predictive stage, both two participants’ privacy protection are considered in our scheme.
6 Performance evaluation
In this section, we provide an experimental evaluation of the proposed VPSPT scheme by using Java language. We run the cloud server side on a computer with Intel Xeon(R) E5-1620 CPU processor running at 3.50GHZ, 16GB RAM memory. And the client side is operated on a laptop with Intel(R) Core(TM) i7-4770 CPU processor running at 3.40GHz, 16GB RAM memory. In our experiment, two real datasets are conducted to training several models simultaneously. We set the iteration threshold as 100, 200, 300, 400 and 500, respectively. These two real datasets are utilized from the hospital repository.
Fig. 3
Time cost for dataset A varying with the number of sample cases
Table 3
Running time of training algorithm for two datasets
Time cost for training stage (ms)
Number of attributes
3
4
5
6
7
8
9
10
11
12
13
Dataset A
200 rounds
180
214
238
265
302
307
336
352
379
407
435
500 rounds
454
535
594
732
709
803
826
892
977
1026
1060
Number of attributes
4
10
16
22
28
34
40
46
52
58
64
Dataset B
200 rounds
314
476
643
800
974
1166
1317
1495
1617
1860
2046
500 rounds
804
1210
1593
1996
2419
2939
3327
3716
4187
4697
5190
×
The first real dataset A includes 300 instances with each instance containing 13 attributes: AST, ALT, \(\nu -\)GT TG, TC, HDL, LDL, VLDL, FFA, FBG, BUN, UA, IL-6. In this experiment, 7 disease prediction models can be trained, i.e., we let \(n=300, m=13, s=7\). The running time of our VPSPT training scheme with different numbers of sample cases is depicted in Fig. 3. As we can seen from this, the running time of VPSPT time of 100 rounds is ranging from 20 to 239 ms with the amount of sample cases varying from 25 to 300. The running time of VPSPT time of 500 rounds is ranging from 52 to 1055 ms with the amount of sample cases varying from 25 to 300. Moreover, we also give the running time in training stage varies with the number of symptom attributes, where \(3\le N_{a}\le 13\). As we can see from Table 3, for 300 sample cases in our VPSPT scheme, the time cost of 200 training rounds ranges from 180 to 435 ms and the time cost of 500 training rounds ranges from 454 to 1060 ms. The experiment results are elaborately sketched in Fig. 4.
The second real dataset B includes 300 instances with each instance containing 64 attributes. In this experiment, 26 disease prediction models can be trained synchronously, i.e., we let \(n=300, m=64, s=26\). The running time of our VPSPT training scheme is also depicted in Fig. 5. The running time of VPSPT time of 100 rounds is ranging from 81 to 1880 ms and the running time of VPSPT time of 500 rounds is ranging from 205 to 9537 ms with the amount of sample cases varying from 25 to 300. Moreover, we also give the running time in training stage varies with the number of symptom attributes, where \(4\le N_{b}\le 64\). As we can see from Table 3, for 300 sample cases in our VPSPT scheme, the time cost of 200 training rounds ranges from 314ms to 2046ms and the time cost of 500 training rounds ranges from 804ms to 5190ms with the amount of symptom attributes varying from 4 to 64. The experiment results are elaborately sketched in Fig. 6.
Fig. 4
Time cost for dataset A varying with the number of symptom attributes
Fig. 5
Time cost for dataset B varying with the number of sample cases
Fig. 6
Time cost for dataset B varying with the number of symptom attributes
×
×
×
7 Conclusion
In this paper, we propose a verifiable privacy-preserving single-layer perceptron training scheme. For a set of training samples, we can obtain s different models. Meanwhile, with the help of the cloud-aided computing technique, most of heavy computation tasks are transferred from the client to the cloud server. Therefore, the overhead of computation has been dramatically reduced. In predictive stage, both two participants can protect their inputs without privacy leakage. Moreover, only will the requester obtain the predictive result which is also private. In the future, we will focus on devoting ourselves to design more efficient and flexible machine learning schemes.
Acknowledgements
This work is supported by National Natural Science Foundation of China (Grant Nos. 61572382, 61702401), Key Project of Natural Science Basic Research Plan in Shannxi Province of China (No. 2016JZ021) and China 111 Project (Grant No. B16037).
Compliance with ethical standards
Conflict of interest
All authors declare that there is no conflict of interest.
Ethical standard
This article does not contain any studies with human participants or animals performed by any of the authors.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
In practice, \(2^{80}\) can be considered to resist brute-force attack. At least, we choose \(p=2\) and \(m_{0}=20\) in this paper. The requester’s choice is evenly distributed over \(S\subset \mathbb {F}_{p^n}\). So far, we have presented the security analysis for the requester. \(\square \)