A Novel Matrix-Encoding Method for Privacy-Preserving Neural Networks (Inference)
Authors: Li-Yue Sun
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Homomorphic Encryption
Matrix Encoding
Matrix Multiplication
Privacy Preserving
Neural Networks

Abstract: In this work, we present a novel matrix-encoding method that is particularly convenient for neural networks to make predictions in a privacy-preserving manner using homomorphic encryption. Based on this encoding method, we implement a  convolutional neural network for handwritten image classification over encryption.  For two matrices A and B to perform homomorphic multiplication, the main idea behind it, in a simple version, is to encrypt matrix A and the transpose of matrix B into two ciphertexts respectively. With additional operations, the homomorphic matrix multiplication can be calculated over encrypted matrices efficiently. For the convolution operation,  we in advance span each convolution kernel to a matrix space of the same size as the input image so as to generate several ciphertexts, each of which is later used together with the ciphertext encrypting input images for calculating some of the final convolution results. We accumulate all these intermediate results and thus complete the convolution operation. 
In a public cloud with 40 vCPUs, our convolutional neural network implementation on the MNIST testing dataset takes ~287 seconds to compute ten likelihoods of 32  encrypted images of size 28 x 28 simultaneously.   The data owner only needs to upload one ciphertext (~19.8 MB) encrypting these 32 images to the public cloud. 

Volley Revolver: A Novel Matrix-Encoding Method for Privacy-Preserving Neural Networks (Inference)
Anonymous Author(s) Affiliation Address
email
Abstract
this work, we present novel matrix-encoding method that particularly convenient for neural networks to make predictions in privacy-preserving manner using homomorphic encryption. Based on this encoding method, we implement a convolutional neural network for handwritten image classification For two matrices A and to perform homomorphic multiplication, the main idea behind it, in simple version, is to encrypt matrix A and the transpose of matrix into two ciphertexts respectively. With additional operations, the homomorphic matrix multiplication can be calculated the convolution operation, we in advance span each convolution kernel to a matrix space of the same size the input image so generate several ciphertexts, each of which is later used together with the ciphertext encrypting input images for caleulating some of the final convolution results. We accumulate all these intermediate results and thus complete the convolution operation.
3
encryption.
5
encrypted matrices efficiently. For
10
11
13
14
In a public cloud with 40 vCPUs, our convolutional neural network implementation on the MNIST testing dataset takes ~ 287 seconds to compute ten likelihoods of encrypted images of size x simultaneously. The data owner only needs to upload one ciphertext (~ 19.8 MB) encrypting these 32 images to the public cloud.
15
16
Introduction
18
Machine learning applied in some specific domains such as health and finance should preserve privacy 20 while processing private confidential data to make accurate predictions. In this study, we focus on sewacy-preserving neural network inference, which aims outsource well-trained inference model 22 to cloud service in order to make predictions on private data. For this purpose. the data should
19
21
23 be encrypted first and then sent the cloud service that should not be capable of having access to
24 the raw data. Compared to other cryptology technologies such as Secure Multi-Party Computation, Homomorphic Encryption (HE) provides the most stringent security for this task.
25
28 Combining HE with Convolutional Neural Networks (CNN) inference has been receiving more and more attention in recent years since Gilad-Bachrace et al. (6) proposed framework called Cryptontss Cryptonets applies neural networks to make accurate inferences on encrypted data with high throughput. Chanranne al. 2 extended this work deeper CNN using different underlying software library called HElib and leveraged batch normalization and training process develop better quality polynomial approximations of the ReLU function for stability and accuracy. Chou et al. [4] developed a pruning and quantization approach with other deep-learning optimization techniques and presented method for encrypted neural networks inference, Faster Cryptolets..
27
28
29
30
31
32
33
34
Brutzkus et al. []] developed new encoding methods other than the one used in Cryptonets for representing data and presented the Low-Latency CryptoNets (LoLa) solution. Jiang et al.
35
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

36
proposed an efficient evaluation strategy for secure outsourced matrix multiplication with the help of a novel -enooingn method.
37
38
Contributions In this study, our contributions are in three main parts:
39
1. We introduce a novel data-encoding method for matrix multiplications on encrypted matrices, Volley Revolver, which can be used to multiply matrices arbitrary shape efficiently.
40
41
2. We propose feasible evaluation strategy for convolution operation, by devising an efficient homomorphic algorithm sum some intermediate results of convolution operations.
43
3. We develop some simulated operations on the packed ciphertext encrypting an image dataset as if there were multiple virtual ciphertexts inhabiting it, which provides compelling new perspective of viewing the dataset as three-dimensional structure.
44
45
46
2
Preliminaries
47 Let "@" and "@" denote the component-wei -iis addition and multiplication respectively between
48 ciphertexts encrypting matrices and the ciphertext ct. the encryption of a matrix P. Let r(m)
49
represent the single pixel of the j-th element in the i-th row of the m-th image from the dataset.
50
Homomorphic Encryption Homomorphic Encryption is one kind of encryption but has its char- acteristic in that over HE system operations on encrypted data generate ciphertexts encrypting the right results of corresponding operations on plaintext without decrypting the data nor requiring access to the secret key. Since Gentry tackling the over three decades problem, much progress has been made on an efficient data encoding scheme for the application of machine learning to HE. Cheon et al. 3 constructed an HE scheme (CKKS) that can deal with this technique problem efficiently, coming up with a new procedure called rescaling ing for approximate arithmetic in order to manage the magnitude of plaintext. Their open- soeresouree library, HEAAN, like other HE libraries also supports the Single Instruction Multiple Data (aka SIMD) manner to encrypt multiple values into a single ciphertext.
51
52
53
S presented the first fully homomorphic encryption scheme,
54
55
57
59
60
Given the security parameter, HEAAN outputs secret key sk, public key pk, and other public keys used for operations such as rotation. For simplicity, we will ignore the rescale operation and deem the following operations to deal with the magnitude of plaintext automatedly. HEAAN has the following functions to support the HE scheme:
61
62
63
64
1. (mc) For the public key pk and a message vector m, HEAAN encrypts the message m into ciphertext ct.
65
66
2. (ct:: Using the secret key, this algorithm returns the message vector encrypted by the ciphertext ct.
67
3. Add(ctı, ct2): This operation returns new ciphertext that encrypts the message (ec,(cct)) @ (ct2).
69
70
4. Mul(ct1, ct2): This procedure returns a new ciphertext that encrypts the message (ec,(ctt)) & (et2))
71
72
5. Rot(ct, l):
This procedure generates a ciphertext encrypting a new plaintext vector obtained by rotating the the original message vector m encrypted by ct to the left by I positions.
73
74
Database Encoding Method For brevity, we assume that the training dataset has samples with features and that the number of slots in single ciphertext is at least f. A training dataset is usually organized into matrix Z each row of which represents an example. Kim et al. [10] propose
75
76
77 an efficient database encoding method to enerypt this matrix into single ciphertext in a row-by-row manner. They provide two basic but important shifting operations by shifting 1 and í positions 79 respectively: the incomplete column shifting and the row shifting. The matrix obtained from matrix Z by the incomplete column shifting operation is shown follows:

---

201[ [|2[1]
2[1][]]
2[1[[]]
210]2]]
2[][[3]
2[2[11]
2|2
incomplete column shifting,
2/21/21
P[2[[s]
2[S
Z =
[(v[[2]
F[n][3]
-[1[[1]
81 Han et al. [8] summarize another two procedures, SumRowVec and SumColVec, to compute the 82 summation of each row and column respectively. The results of two procedures Z are as follows:
[[1][2]
[[1]12]
P[alls]
SumRowVec (2)
Σ
1=
P(100
E 2(112)
Σ
c
Σ
2[1[]]
Σ P106
2(1]
Σ 3-1 P121b
Σ j-1 2|2|[>]
SumColVec (2)
Σ
Σ PMiL
Σ/ Pioli
Plolls
88 We propose a new useful procedure called SumForConv v to facilitate convolution operation for every
84 image. Below we illustrate the result SumForConv on taking the example that n and f are both
4 and the kernel size is 3 x 3:
200
2[][2]]
2[1[3]]
2[1][4]
8
07
Z
[[2][1]
2[2
[[2[3]]
[|2][4]
SunF ozr Conrr (-3,3)
1
222
213](1]
2[3]a]]
[[3[3]
[[3][4]
P(A](1)
2[4][2]
F[4[[3]
[[4][4]]
0
86 where {[]]>]] =
Σグ E P[p][o] for i < 2. In the convolutional layer, SumForConv can help
87
to compute some partial results of convolution operation for an image simultaneously.
Technical details
88
We introduce novel matrix-encodinn method called Volley Revolver, which is particularly suitable for secure matrix multiplication. The basic idea is to place each semanticall- information (such 92 this matrix into a single ciphertext. When applying it to private neural networks, Volley Revolver puts the whole weights of every neural node into the corresponding row of matrix, organizes all the nodes from the same layer into this matrix, and encrypts this matrix into a single ciphertext.
90
example in dataset) into the corresponding row of matrix and encrypt
g4
95 3.1 Encoding Method for Matrix Multiplication
Suppose that we given C' of size m x p, which is the matrix product B with the element Cjajs] = Σi_ [[a[ X bpep
matrix A and a x matrix B and suppose to compute the matrix
97
[[]][2]
[[][[]]
lalell
A
B
[|m][]]]
[[d[[]]
Q[m][m]]
[[]][2]
b
98
For simplicity, we assume that each of the three matrices A, B and C could be encrypted into single ciphertext. We also make the assumption that m is greater than p. m > p. We will not illustrate the other cases where m < p. which is similar to this one. When comes to the homomorphic matrix multiplication, Volley devolver encodes matrix A directly but encodes padding form of the transpose of matrix B, by using two row-ordering encoding maps. For matrix A, we adopt the same encoding method that [ did by the encoding map A - A )osk<mx For matrix B, we design a very different encoding method from 9 for Volley Revolver: we transpose the matrix B first and then extend the resulting matrix in
99
100
102
104

---

106
the vertical direction to the size m n. Therefore Volley Revolver adopts the encoding map 0okkmmnn obtaining the matrix from mapping Tb on B:
107 Tb
B + B
b
[x]]
b(1l b
b1])2 1mmp))
+ (mm-1)9p))
[1 ++ (mn-1)%pp)_
108
Homomorphic Matrix Multiplication We report an efficient evaluation algorithm for homomorphic 109 matrix multiplication. This algorithm uses ciphertext ct.R encrypting zeros or given value such accumulator and an operation RowShifter to
as the weight bias of fully-comnected layer perform a specific kind of row shifting on the encrypted matrix B. RowShifter pops up the first row of B and appends another corresponding already existing row of B:
111
brarpe
bellel
boolle [mil
RouShifter (B)
b(2]lr)
b biil
b(all1)
:
bp]ld] b1((()+))))
bpo]ir]
(11((+1)))pp)
11s For two ciphertexts At.A and Bt the algorithm for homomorphic matrix multiplication has iterations. For the k-th iteration where 0 < k y there are the following four steps:
115
Step 1. This step uses RowShifter on ct. to generate new ciphertext ct. and then com- putes the homomorphic multiplication between ciphertexts ct.A and ct.B, to get the resulting product ct AB, When & in this case RowShifter just return a copy of the ciphertext ct Bt.
116
117
118
S Step 2. In this step, the public cloud applies SumColVed on ct. At.,BB; to collect the summation of the data in each row of AB, for some intermediate results, and obtain the ciphertext ct.
120
S Step 3. This step designs a special matrix to generate a ciphertext ct. for filtering out the redundancy element in D by one multiplication Mul(ct.F, ct. resulting the ciphertext ct.
122
Step 4. The ciphertext ct. Rt.R is then used to accumulate the intermediate ciphertext ct.
123
The algorithm will repeat Steps to for times and finally aggregates all the intermediate cipher- texts, returning the ciphertext C. Algorithm shows how to perform homomorphic matrix multiplication. Figure describes simple case for Algorithm where m = 2, n = 4 and 2.
125
126
The calculation process of this method, especially for the simple case where m p. is intuitively similar to a special kind revolver that can fire multiple bullets at once (The first matrix A is settled still while the second matrix B is revolved). That is why we term our encoding method "Volley Revolver".
127
129
real-world cases where m mod p = 0. the operation RowShifter can be reduced only need one rotation RowShifter Rot ct, n2). which is much more efficient and should thus be adopted whenever possible. Corresponding to the neural networks, we can set the number of neural nodes for each fully-connected layer to be power of two to achieve this goal.
131
133
3.2
Homomorphic Convolution Operation
134
In this subsection, we first introduce a novel but impractical algorithm to calculate the convolution operation for single grayscale image of size h x w based on the assumption that this single image can happen to encrypted into single ciphertext without vacant slots left, meaning the number N of slots in packed ciphertext chance to be N = h x w. We then illustrate how to use this method to compute the convolution operation of several images of any size the same time for a convolutional layer after these images have been encrypted into ciphertext and been viewed several virtual
135
196
198

---

Algorithm
Homomorphic matrix multiplicatiin
Input: ct.A and ct.B for A E Rmx", B E Ruxp and B Volley Revolver Encoding, B RRxxx
Output: The encrypted resulting matrixs ct.C for C E Ruxp of the matrix product A B b C: To accumulate intermediate matrices
Set C
2: ct.C' t (C)
The outer loop (could computed in parallel)
3: for idæ == 0 to
do
4: ct..7 <- RowShifter(ct. (ttifftrrrrrt..P..... idz)
5:
ct.7 <- Mul(ct.A,ct.7)
6:
ct.7' -- SumColVec(ct.7))
Build specifically-ddsigneed matrix to clean up the redundant values
7:
Set F +-
D
P E mx
8:
for i : to m do
9:
F[o]((i + W t
10:
end for
11:
ct. +- MMnc (F), ct.T)
To accumulate the intermediate results ct.C < +dd+-ddtt Add(ct.C,ct.7))
12:
13:
end for
14:
return ct.C
Eacoding
66
07
Ap
by
Enerygt
166
0
0
br
60
61
02
93
An
8c
9unColMeoo())
0o
Clean up
Oa
A
redundant
by
Gg bg +
Bg dg bb
BuaColVoc())
Claan the
04
45
06
d7
An
C2
62
62
redundent vaa tsea.
C2
0
dg bp + 0g by 0o dy 4 by
b2
%o
Decrypt 6g Decoding
Figure 1: Our matrix multiplication algorithm with m = 2, n = and p = 2
ciphertexts inhabiting this real ciphertext. For simplicity, we assume that the image is grayscale and that the image dataset can be encrypted into single ciphertext.
141
An impractical algorithm Given grayscale image I of size h and kernel K of size l x k with its bias kn such that and w are both greater than k, based on the assumption that this image can happen to be encrypted into ciphertext ct. with more or less vacant slots, present an efficient algorithm to compute the convolution operation. We set the stride size to the usual default value (1, 1) and adopt no padding technique in this algorithm.
143
145
147
Before the algorithm starts, the kernel K should called by an operation that we term Kernelspanner to in advance generate k² ciphertexts for most cases where h > 2 k - and
149 " 2 k 1, each which encrypts a matrix P: for S S 2.2 using map to span the k kemel to a h x matrix space, For simple example that h 4, w and & Kernelepanner

---

generates 4 ciphertexts and the kernel bias ky will be used to generate ciphertext:
k2
kj
h2
k
22
07
0
0
Ri ki
k2
spaaner
Kz
k:4
kg
k:
O
K3
k4
0
kj
k2
k1
k2
kis
k1
k2
ki
O
k1
h/
0
k3
k4
ki
kg
K3
kig
Rig
O
K3
R4
0_
0
0
Koo
kg
ko
07
0
0
0
ko
ko
ko
k2
[Ko] + Enc
ko
ko
ko
0
0
K3
K4
0
0
0
0
152
Our impractical homomorphic algorithm for convolution operation also needs a ciphertext ct.R to accumulate the intermediate ciphertexts, which should be initially encrypted by the kernel bias ko- This algorithm requires & X k iterations and the i-th iteration consists of the following four steps for
153
154
155
1 < i k²:
Step 1. For ciphertexts ct./ and ct.P, this step computes their multiplication and returns the ciphertext ct. = Mul(ct.7,ct.PP)
157
158
Step 2. To aggregate the values of some blocks of size l x k, this step applies the procedure SumFor ComForCon's Conv on the ciphertexi ct./P;, obtaining the ciphertext ct.
159
160
Step 3. The public cloud generates ciphertext encrypting specially-designe matrix in order to filter the garbage data in ct. by one multiplication, obtaining a ciphertext ct.
162
S Step 4. In this step. the homomorphic convolution operration algorithm updates the accumulator ciphertext ct R. by homomorphically adding ct.D to it, namely ct.R Add( (t. R., ct.D).
164
Note that Steps 1-3 in this algorithm can be computed parallel with A threads. We describe how to compute homomorphic convolution operation in Algorithm 2 in detail. Figure@describer
185
186
simple case for the algorithm where 3, w and
Input
Image
Kernel
Fix
$12
613
Az
ks
kn
Aq
0
0
Fax
Ega
124
h4
kG
As
Ao
0
0
0
0
Exc
Avr
Kxg
App
Korastepaonnn
8:g By + + Fax Ap
4ga
114
Aa
Ara
k
SunPorConv(
Esc
kx
lms
Pap
6ss
1s4
Ar
Xarso) spanaii
+
112
114
ArL
SunPorConv())
Bara
Sax
Est
Rg2
koy
As
Output
Figure 2: Our convolution operation algorithm with h = 3, w = and 3
187 Next, we will show how to make this impractical homomorphic algorithm work efficiently in real- world cases.

---

Algorithm/ 2 Homomorphic convolution operation
Input: An encrypted Image ct.l for I E 1 and a kernel K of size k x k with its bias ko Output: The encrypted resulting image ct.l, where I has the same size as I The Third Party performs sernesspanne and prepares the ciphertext encrypting kernel bias
1: ct.S + Kernel (K, h, w)
1 15 i S k2 > Le R
2: Set I, f-
3: for == 1 to - + do
4: for j := 1 to w k do
5:
[,]0[[]
6: end for
7: end for
8: ct.l, (t,)p((I)) [.)
D So begins the Cloud its work
9: for 0 k do
10:
for j = 0 to k do
ct.
12:
ct. SumForConv(ctt.))
> Design matrix to filter out the redundant values Set F 0
F E R
14:
for hth = to / do
for wit : 0
do
16:
if (wth - i) mod k = 0 and wih + k S w and
(hth j) mod & 0 and hth k < h then
18:
Fihth] wtth] t
end if end for end for
20:
22:
ct.7 Mul (Encpt (F), ct.T)
> To accumulate the intermediate results
23:
ct./, + Add ct.T)
24:
end for
25:
end for
26: return ct.l,
Encoding Method for Convolution Operation For simplicity, assume that the dataset X Rm can be encrypted into a single ciphertext ct.X, m is a power of two, all the images are grayscale and have the size h w. Volley Revolver encodes the dataset as matrix using the database encoding method [10] and deals with any CNN layer with a single formation. In most cases, h < f, if this happened, zero columns could be used for padding. Volley Revolver extends this database encoding method [00] with some additional operations to view the dataset matrix as cimee-dimeniionl structure.
170
172
174
Algorithm is a feasible and efficient way to calculate the secure convolution operation in an HE domain. However, its working-environment assumption that the size of an image is exactly the length of the plaintext, which rarely happens, is too strict to make a practical algorithm, leaving this algorithm directly useless. In addition, Algorithm 2 can only deal with one image at time due to the assumption that a single ciphertext only encrypts only one image, which is too inefficient for worldworld applications.
176
178
180
182
To solve these problems, Volley Revolver performs some simulated operations on the ciphertext ct.X to treat the two-dimensions dataset as faree-dimensiona structure. These simulated opera- tions together could simulate the first continual space of the same size as an image of each row the matrix encrypted in real ciphertext as a virtual ciphertext that can perform all the HE operations. Moreover, the number of plaintext slots usually set to large number and hence a single eiphertext could encrypt several images. For example, the ciphertext encrypting the dataset X e m could
183
184
186
7

---

188
be used to simulate m virtual ciphertexts vct; for 1 S i S m, as shown below:
(()
[[
[w]]
(1)
(1)
(1)
vEnc
0
[
(2)
(2)
0
[M]1]]
[A][
[[]]
Ene
[m)
(lm)
((m)
f(m)
0
[1][]]
[M][]]
vEnc
(m)
(mm)
[A]
189
Similar to an HE ciphertext, a virtual ciphertext has virtual HE operations: vEnc, vDec, vAdd, vMul, vRescale, vBootstrapp ing and vRot. Except for vRot, others can be all inherited from the corresponding HE operations. The HE operations, Add, Mul, Rescale and Bootstrapping in the same corresponding virtual operations: vÅdd, vMul, vReacale and vBootstrapping, The virtual rotation operation vRot is much different from other virtual operations: it needs two rotation the real ciphertext. We only need to simulate the rotation operation on these virtual ciphertexts to complete the simulation. The virtual rotation operation vRot(ct, r), to rotate all the
191
result
182
193
operations
195
198
virtual ciphertexts dwelling in the real ciphertext ct to the left by positions, has the following
197
simulation result:
vEnc
[
(() [-
(1) ()+t)// 11%%))
(()
[M][a]]
Enc
vEnc (r)m))
(mx)
[m][me]]
vRot(ct,r))
vEnc [1
(
Enc
vEnc (m))
(m) [[]]]]
(n) [/
198
To bring all the pieces together, we can use Algorithm 2 to perform convolution operations for several images in parallel based the simulation virtual ciphertexts. The most efficient part of these simulated operations is that sequence of operations on a real ciphertext results in the same corresponding operations on the multiple virtual ciphertexts, which would suffice the real-world
199
200
201
202
applications.
Privacy-preserving CNN Inference
203
Homomorphic Encryption cannot directly compute func- tions such as the ReLU activation function. We use Dctave to generate a degree-three polynomial by the least square method and just initialize all the activation layers with this polynomial, leaving the training process to determine the coefficients of polynomials for every activation layer. Other computation operations, such matrix multiplication in the fully-connected layer and convolution operation in the convolutional layer, can also be performed by the algorithms we proposed above.
Limitations applying CNN to HE
205
207
208
209
Neural Networks Architecture We adopt the same CNN architecture as [9] but with some different hyperparameters. Our encoding method Volley Revolver can be used to build convolutional neural networks deep it needs. However, in this case, the computation time will therefore increase and bootstrapping will have to be used to refresh the ciphertext, resulting in more time-consuming. Table [ gives description of our neural networks architecture on the MNIST dataset.
211
213
5
Experimental Results
216 We use C++ to implement our homomorphic CNN inference. Our complete source code is publicly available at attttps: atlttps:/annonyooo //t///nnnonous.a//////
ECA44/

---

Table 1: Description of our CNN on the MNIST dataset
Layer
Description
CONV
32 input images of size 28 28, 4 kernels of size 3 x 3, stride size of (1. 1)
ACT-1
I bー 0.00015120704 0.46101449
2.0225089 x² 1.4511951 x²
FC-1
Fully connecting with 26 x 26 x 4 = 2704 inputs and 64 outputs
ACT-2
+ 1.5650445 - 0.9943367 x + 1.6794522 x² + 0.5350255 x²
FC-2
Fully connecting with 64 inputs and 10 outputs
218
We evaluate our implementation of the homomorphic CNN model on the MNIST dataset each time calculate ten likelihoods for 32 encrypted images of handwritten digits. The MNIST database includes training dataset of 60 000 images and a testing dataset of 10 000, each image of which is of size 28 28. For such an image, each pixel is represented by 256-1evel grayscale and each image depicts digit from zero to nine and is labeled with it.
Database
219
220
221
222
223
Building a model in the clear In order to build homomorphic model, we follow the normal approach for the machine-learning training in the clear- except that we replace the normal ReLU function with polynomial approximation: we (1) train our CNN model described in Table [ with
224
225
the MNIST training dataset being normalized into domain [0. 1]. and then we (2) implement the well- resulting CNN model from step (1) using the HE library and HE programming.
226
227
For step (1) adopt the highly customizable library keras with Tensorflox. which provides us with simple framework for defining our own model layers such as the activation layer to enact the polynomial activation function. After many attempts obtain a decent CNN model, we finally get
229
230
231
CNN model that could reach a precision of 98. 36.66% on the testing dataset. We store the weights of
232
this model into CSV file for the future use. In step (2) we use the HE programming to implement
233
the CNN model, accessing its weights from the CSV file generated by step (1). We normalize the
234
MNIST training dataset by dividing each pixel by the floating-pont pointt constant 255.
235
Classifying encrypted inputs We implement our homomorphic CNN inference with the library
236
HEAAN by (3. Note that before encrypting the testing dataset of images, we also normalize the MNIST testing dataset by dividing each pixel by the floating noating-point constant 255, just like the normal procedure on the training dataset in the clear.
237
238
239 Parameters. We follow the notation of [10] and set the HE scheme parameters for implementment: A = 2 and A, 220; slots = 32768; logQ = 1200 and logN = 16 to achieve a security level for more details on these parameters).
240
241
of bits. (see
242
Result. We evaluate the performance of our implementation on the MNIST testing dataset of 10 000 images. Since in this case Volley Revolver encoding method can only deal with 32 MNIST images at one time, we thus partition the 10 000 MNIST testing images into 313 blocks with the last block being padded zeros to make it full. We then test the homomorphic CNN inference on these 313 ciphertexts and finally obtain a classification accuracy of 98.61% %. The processing of each ciphertext outputs 32 digits with the highest probability of each image, and it takes ~ 287 seconds on a cloud server with 40 vCPUs. There is a slight difference in the accuracy between the clear and the encryption, which is due to the fact that the accuracy under the ciphertext is not the same as that under the plaintext. In order to save the modulus. a TensorFlow Lite model could be used to reduce the accuracy the clear from float 32 float 16. The data owner only uploads 1 ciphertext (~ 19.8 MB) enerypting these 32 images to the public cloud while the model provider has to send 52 ciphertexts GB) encrypting the weights of the well-trained model the public cloud.
244
246
247
248
249
250
251
252
253
6
Conclusion
The encoding method we proposed in this work, Volley Revolver, is particularly tailored for 255
neural networks. There is good chance that it can be used to assist the private neural networks training, in which case for the backpropagation algorithm of the fully-connected layer the first matrix A is revolved while the second matrix B is settled to be still.
257

---

References
259
280
[1]
Alon Brutzkus, Ran Gilad-Bachradd and Oren Elisha. Low latency privacy preserving inference. In International Conference on Machine Learning, pages 812-821. PMLR, 2019.
[2] Hervé Chabanne, Amaury de Wargny, Jonathan Milgram, Constance Morel, and Emmanuel Prouff. Privacy-preserving classification on deep neural network. IACR Cryptol. ePrint Arch., 2017:35, 2017.
263
265
[3] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security, pages 409-437. Springer, 2017.
286
267
268
[4] Edward Chou, Josh Beal, Daniel Levy, Serena Yeung, Albert Haque, and Li Fei-Fei. Faster cryp- tonets: Leveraging sparsity for real-world encrypted inference. arXiv preprint arXiv: 1.09953, 2018.
270
271
[5] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 169-178, 2009.
[6] Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing, Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pages 201-210. PMLR, 2016
274
275
278
[7] Shai Halevi and Victor Shoup. Helib design principles. Tech. Rep., 2020. Sstps://githas com/homent http:/hoomc/HHH1111 /b
277
[8] Kyoohyung Han, Seungwan Hong, Jung Hee Cheon, and Daejun Park. Logistic regression on homomorphic encrypted data at scale. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9466-94715 2019.
279
99] Xiaoqian Jiang. Miran Kim, Kristin Lauter, and Yongsoo Song. Secure outsourced matrix computation and application to neural networks. In Proceedings of the 2018 ACM SIGSAC Conference Computer and Communications Security, pages 1209-1222, 2018.
282
283
284
[10] Andrey Kim, Yongsoo Song, Miran Kim, Keewoo Lee, and Jung Hee Cheon. Logistic regression model training based on the approximate homomorphic encryption. BMC medical genomics, 11(4):83, 2018.
285
206
287
[11] N.P. Smart and F. Vercauteren. Fully homomorphic simd operations. Cryptology ePrint Archive, 2011. /3//1/3//
288
Report
cr/2011/133
Checklist
289
1. For all authors...
291
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s
292
contributions and scope? [Yes]
293
(b) Did you describe the limitations of your work? [Yes]
294
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
295
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
296
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
301
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
302
303
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
10

---

305
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
306
307
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasng new assets...
310
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [Yes]
314
315
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
316
317
5.
If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
319
320
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
321
322
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
A
Appendix
325
Optionally include extra information (complete proofs, additional experiments and plots) in the appendix. This section will often be part of the supplemental material.


Reviews:
[{"review_id": "zOvaqO_U-LJ", "reviewer": "Reviewer_rzzf", "summary": "The paper presents methods for matrix multiplication and 2D convolution in lattice-based homomorphic encryption that allows parallel multiplication of a number of cleartext values. The authors have implemented in an open source framework and provide a benchmark for a simple MNIST network.\n", "questions": "How did you implement SumForConv in terms of rotations and element-wise operations?\n", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I'm missing a differentation to the prior work by Dathrati et al. [1]. They propose a matrix multiplication that only uses one ciphertext multiplication as opposed to $2p$ in this work for $p$ being the number of columns in the output, and they report on inference of three versions of a LeNet network with similar accuracy in 2.5 seconds where this work achieves an inference time of 287 seconds for a batch of 32. Even prior art cited by the paper (CryptoNets) achieves 250 seconds on a batch of 4096. The authors claim that memory usage is an issue with CryptoNets but they don't comment on the memory usage of their solution.\n\nI'm also missing the specification SumForConv in terms of basic operations. The underlying encryption scheme only allows element-wise operations and rotations so any other operations has to reduced to these.\n\nWhy do the authors encrypt $F$ (line 11 in Algorithm 1 and line 22 in Algorithm 2)? F only contains public information, so a public-private multiplication would be more efficient.\n\n[1] https://dl.acm.org/doi/10.1145/3314221.3314628\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LqA5Eqf37kb", "reviewer": "Reviewer_uaxy", "summary": "This paper proposes a new matrix multiplication method (called \"volly revolver\") suitable for homomorphic encryption. They present an efficient way of adding intermediate steps of the Convolution operation and simulate the operation on the packed ciphertext.", "questions": "The paper deals only with matrix multiplication, but it is unclear what advantages there are from multiplication alone. Recent works have already reported a faster computation run-time than reported in the paper. Therefore, a simulation comparison with the latest results is necessary to clarify the advantage of the proposed method in the paper, but there is currently none.\n\nCNN operation does not end with just one matrix operation, but it leads to another operation. In this process, the message size is reduced, and the message packed in the ciphertext needs to be reconstructed for efficient operations. Considering the whole network, convolution operation (and matrix multiplication) should be considered. Otherwise, it can be rather disadvantageous due to additional packing requirements and a corresponding new data rotation for the followed processes.\n\n(215-216 lines) said that \"Our method based on Volley Revolver can build convolutional neural networks as deep as it needs.\" However, they do not \n\nAlthough this paper targets gray images, other studies handle color images such as CIFAR-10/100 and ImageNet well. Obviously, the proposed method in this paper can also be used for color images, applying three channels independently. However, the amount of computation should be three times larger.\n\nAt 78-79 lines, the method in this paper is only applicable to datasets with a smaller number of pixels than the available slots of ciphertext, which is also a limitation of the proposed method. In the case of ImageNet, it is not possible to fit one image even in 2^15 slots, so another efficient method is needed.\n\nOn page 4, is the extended form of B included in the single ciphertext? Then, when the extended area is considered, the actually applicable sample size is likely to be further reduced.\n\nIt also does not consider how stride two or higher is applicable.", "limitations": "The social impact or limitations of the paper are not specifically described.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In applying homomorphic encryption to neural networks, it is necessary to perform matrix operations efficiently. In this process, homomorphic encryption requires an efficient method because the movement of the encrypted message is done through rotation, which has much computational cost. \nThis paper does not reflect the latest research results. See, for example, C. Juvekar, et al., “GAZELLE: a low latency framework for secure neural network inference,” Proceedings of the 27th USENIX Conference on Security Symposium, August 2018, pp. 1651–1668, which covers how to perform matrix operations for homomorphic operations efficiently.\n\nThis paper is not properly compared with homomorphic matrix multiplication results in other papers. There is a limit to directly applying to real CNNs considering only matrix operation without considering the flow of computation in the entire network. The tests conducted only in MNEST appear to be too outdated compared to the recent results of CIFAR-10/100 or ImageNet.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GTvm9knzZfV", "reviewer": "Reviewer_sp2h", "summary": "This work deals with the new matrix encoding method, called Volley Revolver, for efficient matrix multiplication on homomorphic encryption scheme. To efficiently use the data structure and the homomorphic operation in CKKS scheme for matrix multiplication, they adequately transpose and concatenate one of the input matrices and use RowShifter and SumColVec operation. The matrix multiplication and convolution operation are efficiently designed for CKKS scheme, and the simulation is conducted with HEAAN library and MNIST dataset.", "questions": "- Why Jiang et al.'s work is difficult to be applied in CNN with over two convolutional layers?\n- Please show the comparison with the state-of-the-art prior techniques.", "limitations": "They did not deal with the limitation of this work, and I think there is no potential negative societal impact.", "rating": 2, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The authors deal with matrix multiplication and convolution with the general dimensions of matrices.\n- The ideas are well conveyed with specific matrix formulas to ease the understanding.\n\nWeaknesses\n- No simulation comparison with state-of-the-art matrix multiplication or convolution with CKKS scheme. As far as I know, the matrix multiplication and convolution in CKKS scheme is well researched in homomorphic encryption academic area, and thus this proposed technique can be compared with many prior works regarding matrix multiplication. They only show the classification accuracy and the latency with their proposed model without any comparison, so I cannot be assured that the proposed technique is superior to the state-of-the-art techniques.\n- Reference is too weak. There are far more works regarding matrix multiplication and convolution in HE, but they only refer to only a small subset of these works.\n- They refers to the work of Jiang et al. [9] and they claimed that the technique in this work \"might\" be difficult to be applied in practical application for CNN with over two convolutional layers. However, the authors do not suggest why it is difficult. The authors should have dealt with the limitation of the prior works thoroughly before proposing their technique. I cannot be assured that the prior techniques are really inadequate for CNN with over two convolutional layers.\n- Overall, the authors failed to prove that their proposed technique is superior to the state-of-the-art techniques, and thus the authors should justify their contribution more strongly if they want to be accepted in the NeurIPS conference.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0ZlkDuOCWCy", "reviewer": "Reviewer_SjJL", "summary": "This work provides the method, named Volley Revolver, of encoding encrypted matrix to perform matrix multiplication efficiently in the HE scheme. Volley Revolver provides an encoding method that packs multiple encrypted data in a single ciphertext, which makes matrix multiplication efficient.", "questions": "Is the proposed method applicable for encrypted image data with multiple channels? Most of the colored image dataset such as CIFAR-10 are formed with three channels.", "limitations": "The limitation is mentioned in the introduction (lines 40--41).", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe authors described the details of the proposed method with proper figures which are easy to understand.\n\n---\n\nWeaknesses:\n\nThe authors use the word *efficient* a lot, but its meaning should be described more definitely. From my understanding, the meaning of \"efficient\" refers that multiple image data can be encoded in a single ciphertext. If this is the authors' main contribution, please emphasize this point in Abstract, Introduction, Related Works, and Conclusions. \n\nMoreover, there is no quantitative discussion about the efficiency of the proposed method. Previous works are mentioned, but I cannot find the exact improvement compared to the previous works. Are there any other previous works about matrix encoding for matrix multiplication or convolution operation? If so, the authors should refer those works. If not, please mention it. And please show the performance which indicates the improvement from the previous works (e.g., runtime, the number of multiplications). Without these discussions, I think the proposed method is hard to be considered as an efficient method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject