Neural Network Training With Homomorphic Encryption

Deep learning has become successful mostly because of hardware improvements and cloud computing. Besides the huge quantity of data that can be processed, it remains many issues regarding safety such as privacy and anonymity related issues. Cloud computing in its essence leaks information since private information leaves physically or systematically secure environment such as server reside in the company or institution. In the realm of deep learning, two important kinds of information can be leaked: the parameters that define the model and the data used to to train the model. Privacy-preserving machine learning have been paid attention over the last decade in order to prevent such leakage.

Privacy-preserving machine learning methods can be categorized into two main classes: secure multiparty computation, and homomorphic encryption. A secure multiparty approach creates a generic training protocol that allows several parties to compute a function on their joint inputs without sharing secrets. Mohassel and Zhang [13] presented privacy-preserving neural network training protocol based on a system with two untrusted servers. Although they show the feasibility of their protocol, the latter is very expensive both computationally and in communication. A homomorphic approach does computations over encrypted data as well as the encrypted model, or just over encrypted data alone if there is no need to conceal the model parameters. Homomorphic operations require only one server in general to train the model while a multiparty computation based approach would require the simultaneous interactions of all the parties involved. Research on machine learning inferential applications using homomorphic encryption can be found for instance in [2, 3, 14, 18, 6, 8, 13, 15, 16]. Applications for deep machine learning are however not so frequent [10].

In this section, we shall recall the CKKS [5] scheme upon which our new application is based. Since our implementation uses the CKKS scheme backed with the Microsoft SEAL library [12], we also briefly summarize the latter’s functionalities. In addition, we review packing methods for that are crucial for machine learning applications that use homomorphic encryption. We review quickly the necessary material for training neural networks that motivated our work.

A CKKS scheme has its security based on the hardness of learning with errors (LWE) problem over a polynomial factor ring  [11]. It has a different encoding and batching scheme than the BFV scheme [9]. One of the major difference is that CKKS scheme allows us to encode real number into polynomial slot through canonical embedding whereas BFV scheme allows only integer for encoding, CKKS scheme is preferable for our implementation. It supports leveled homomorphic encryption with chained modulus and relinearization as with the BFV scheme. The main functionalities are: (1) KeyGen, (2) Encoding, (3) Decoding, (4) Encryption, (5) Decryption, (6) Addition, and (7) Multiplication and (8) Rotation.

Packing and rotation techniques are central to compute over ciphertexts because they can be used to speed up linear transformations significantly. Packing is used to encrypt a list of elements to one ciphertext instead of encrypting each element into distinct ciphertexts. This is done through encoding the plaintext information into the subfield of the factor ring [17]. Rotation is the Galois mapping of each element from the subfield, which in practice, is used to add elements from one subfield to another. In this way, linear transformation can be written as a sequence of sums, multiplications and rotations over packed ciphertext. Multiplications and rotations are computationally heavy operations, hence, the design of efficient ciphertext packing methods are critical. We will study the effect of different packing methods on the computation load.

We focus now on how to perform matrix-vector multiplications efficiently using two packing algorithms: (1) a row vector packing method, and (2) a diagonal packing method. These two packing methods are useful to perform linear transformations over encrypted vector. First, consider the multiplication of a matrix $W$ with a vector $x$ whose dimensions are $M\times N$ and $N$, respectively. Following procedure is summarized in algorithm 2. Here, we denote $\texttt{rot}(x,i)$ for packed vector $x$ rotated to right direction by $i$ slots. Similarly $\texttt{rot}(x,-i)$ is for packed vector $x$ rotated to left direction by $i$ slots. For instance, $\texttt{rot}([1,2,3,4,5],1)=[5,1,2,3,4]$, $\texttt{rot}([1,2,3,4,5],-1)=[2,3,4,5,1]$. As shown on figure 1 below, row vector packing method packs each row of $W$ respectively which results in $M$ packed ciphertexts for $W$ and one for $x$. After packing, multiplication is processed by multiplying each of the $M$ packed ciphertexts with the packed ciphertext $x$.

In order to obtain the final result, each intermediate results are rotated and summed by itself so that the slot contains the inner product value of row-packed vector and $x$. Once each inner products are obtained, multiplication with the vector with only one element 1 and the others 0 (we note this vector as unit vector) is applied to remove unnecessary elements. At the end, results are summed up to yield the output of linear transformation. In this case, this entire process consumes $2M$ multiplications and $MN$ rotations.

We describe now the diagonal packing method from gazelle [6]. Given a fixed matrix $W$ and and fixed input $x$, packing is done along the diagonal direction instead of row direction as shown on figure 1 (right). Input, on the other hand, packed into one ciphertext as before. In this case, we conduct iteration which multiplies each of packed diagonal component of the weight $W$ with rotated packed input vector. Packed $x$ is rotated by one at each iteration step. After this iteration, a summation of those intermediate results yields to linear transformation. Major difference from row packing method is that there are no need to multiply ciphertext with the unit vector. In addition, since rotation is only applied to the input vector, the number of rotation can be fewer. Hence, the total computation cost is composed of $N$ multiplications and $N$ rotations. Procedure is summarized in algorithm  2. Although the number of multiplication depends on the shape of given matrix and of the input vector, diagonal method is more efficient in most of the situations.

We briefly review neural network training procedures. For simplicity, we show a simple neural network model which consists of three layers: the input layer, the middle hidden layer and the output layer. A nonlinear layer called activation layer is placed after each linear transformation. The generic structure of a neural network is as on figure 2.

Neural network training is decomposed into two main parts: feedforward and backpropagation. Feedforward is made by the composition of a linear transformation layer followed by a non-linear transformation layer, called activation layer. We initialize the entries of the weight matrix and the biases using a gaussian distribution. The dataset which consists of an input vector and a label that is fed to the first layer then linearly transformed using the weights and the biases. An output is transformed non-linearly using the activation layer. The output of the activation layer becomes the input for the second layer and this continues until we reach the last layer. The output from the last layer becomes the prediction result of that specific input vector. In order to improve the prediction, a the loss between the inferred results and the actual labels is calculated and passed to the backpropagation. Backpropagation is generally the reverse process of feedforward. For the backpropagation process, updates of the weights are calculated to optimize the model towards a better prediction. On figure 3 below, the input goes through two layers by feedforward and the loss is evaluated by taking the mean square error between the inferred result and the true label. Once the loss is calculated, backpropagation allows to compute partial derivatives of the loss with respect to parameters. For the update of the weight parameter, this partial derivative is used to minimize the loss function over the training. Along this backpropagation step, the transpose of packed encrypted weight matrix is required figure 3

Optimizations of the following primitive operations are thus crucial to perfect efficiently neural network training with homomorphic encryption: (1) matrix-vector operations to perform the feedforward phase, (2) computation of the transposition weight matrix for the backpropagation, (3) matrix-vector operations within the backpropagation step, and (4) method to computer the activation function. For (1) and (3), as proposed in gazelle [6] implementation, we pack along the diagonal. Square activation is used for (4) and also as a homomorphic friendly activation function as in cryptonets [7, 10]. We discuss (2) in the next section since the efficient transposition of packed matrix is not discussed in the previous literature.

We mentioned previously that the optimization of the computation of the linear transformation is important in order to keep the runtime and the memory size small enough to be practical. Optimization efforts for homomorphic operations on machine learning algorithms such as convolutional neural network are done by [18, 6, 4] which also make use of packing method for the inputs. However, the aforementioned articles focus on the inference part rather than training the model. Recently, [10] proposed an attempt to train a logistic regression model using packed information to allow end-to-end training. Nevertheless, to the best of our knowledge, only a few implementations of neural network training have been done. Our contribution is as follow:

1. 1.

   A novel packing method for the matrix of weights to achieve efficient overall training runtime. As a result, our design keeps the total number of heavy homomorphic operations significantly lower than other methods. In addition, the depth of circuit for multiplication is kept small which yields to faster and lighter implementation.

2. 2.

   A detailed implementation which was not done extensively in the industry before.

3. 3.

   A tested implementation of our method on well-known iris dataset using Microsoft SEAL.

To verify the advantage of our method, we implemented a neural network model with one hidden layer for the iris dataset classification. Iris dataset is a well-known tutorial dataset for machine learning, which contains $150$ datasets and $150$ labels of $3$ kinds of iris in total. Each element of the dataset consists four iris properties that are flagged for membership. We design our neural network to have one hidden layer as in [7, 10] and described as in table LABEL:table:impl1.

Figure 7 shows the execution flow of training. Repacking of the weight matrix is done in order to prevent the growth of noise per batch training.

The repacking is done by transferring encrypted data to a trusted environment temporarily to perform decryption and re-encrypt of the weight matrix that is sent back to the server. However, as we mentioned earlier, this communication is not necessary when bootstrapping is applied.

We use Microsoft SEAL library as a back end. Encryption parameters for the degree of modulus is $2^{15}$ and bit sequence of modulus chain is to be in the multiset $\{60,40,40,40,40,40,40,40,40,40,60\}$ ($9$ levels of modulus chains available. On the other hand, encryption parameters for the row method has $12$ levels, because of the extra multiplication with the unit vector. The machine specifications for this experiment are: Intel(R) Core(TM) i7-8700K CPU @ $3.70$GHz, $32$GB RAM and $6$ cores.

Table 4 summarizes the running time for each steps of training: (1) feedforward, (2) taking transpose, (3) backpropagation, (4) SGD update and (5) row repacking versus diagonal repacking. For simplicity, the batch size is set to one for this comparison. We observe that the entire process gets faster by $3$ times with our optimization.

To assert the correctness of our method, training is done entirely with our method. We use same model architecture and a batch size of $20$ instead. Batch process is parallelized by Open MP with $12$ threads, which gave us around twice computation performance. Total time for entire process was $107,520$ seconds which is about $29.8$ hours with $400$ epochs. In addition, we wrote a program of training this model with plaintext using same architecture. This code is used to compare the accuracy of a model trained over plaintext and a model trained over ciphertext through CKKS. The mean square loss function and the learning accuracy transition curve per epoch are plotted side by side on figures 8 and 9. After $400$ epochs, final loss function is $0.0249$ for plaintext-based model and $0.273$ for ciphertext-based model. On the other hand, final accuracy is $0.9805$ for plaintext-based model and $0.9847$ for ciphertext-based model. As can be seen, intrinsic approximation of real number of CKKS scheme did not affect the model accuracy.

The needs for privacy-preserving solutions in untrusted environments in which machine learning algorithms are executed are essential nowadays. To achieve such privacy-preserving algorithms, homomorphic encryption has gone out of academia to be now operational at an industrial scale. We proposed an efficient privacy-preserving neural network training architecture that relies on a packing method to optimize the transposition of matrices. As a consequence, training neural networks homomorphically yields to an improvement about $3$ times with respect to other architectures. We tested its advantages on the well-known iris dataset using the SEAL library. We are investigating how our method can be used to train more complex neural network. Homomorphic encryption based neural network training is still a big challenge in terms of computation, however, we believe that it can be a huge breakthrough for privacy preserving technology in coming years.