Efficient representations for privacy-preserving inference
Authors: Han Xuanyuan
Francisco Vargas
Stephen Cummins
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep neural networks
Homomorphic encryption

Abstract: Deep neural networks have a wide range of applications across multiple domains such as computer vision and medicine. In many cases, the input of a model at inference time can consist of sensitive user data, which raises questions concerning the levels of privacy and trust guaranteed by such services. Much existing work has leveraged homomorphic encryption (HE) schemes that enable computation on encrypted data to achieve private inference for multi-layer perceptrons and CNNs. An early work along this direction was CryptoNets, which takes 250 seconds for one MNIST inference. The main limitation of such approaches is that of compute, which is due to the costly nature of the NTT (number theoretic transform) operations that constitute HE operations. Others have proposed the use of model pruning and efficient data representations to reduce the number of HE operations required. In this paper, we focus on improving upon existing work by proposing changes to the representations of intermediate tensors during CNN inference. We construct and evaluate private CNNs on the MNIST and CIFAR-10 datasets, and achieve over a two-fold reduction in the number of operations used for inferences of the CryptoNets architecture.

Under review as a conference paper at ICLR 2022
EFFICIENT REPRESENTATIONN FOR PRIVACY-PRESERVING INFERENCE
Anonymous authors Paper under double-blind review
ABSTRACT
Deep neural networks have a wide range of applications across multiple domains such as computer vision and medicine. many cases, the imput of model at in- ference time can consist of sensitive user data, which raises questions concerning the level of privacy and trust guaranteed by such services. Much existing work has leveraged homomorphic encryption (HE) schemes that enable computation on encrypted data to achieve private inference for multilayer perceptrons and CNNs. An early work along this direction was CryptoNets, which takes 250 seconds for one MNIST inference. The main limitation of such approaches is that of com- pute, which is due the costly nature of the NTT (number theoretic transform) operations that constitute HE operations. Others have proposed the use model pruning and efficient data representations reduce the number of HE operations required. In this paper, we focus on improving upon existing work by proposing changes the representations of intermediate tensors during CNN inference. We construct and evaluate private CNNs on the MNIST and CIFAR-IO datasets, and achieve over two-fold reduction in the number of operations used for inferences of the CryptoNets architecture.
INTRODUCTION
In recent years, deep neural networks have achieved state-of-the-art accuracy for tasks such image recognition. They have been deployed range of sectors, powering wide variety of applications such as recommendation systems, medical diagnosis, and content filtering. Machine Learning as Service (MLaaS)) is framework in which cloud services apply machine learning algorithms on user- supplied data to produce an inference result which is then returned to the user. Cloud systems are an attractive platform for deploying pretrained models due to the relatively low cost and the availability of remote servers. However, the data has to be decrypted before inference, which allows a server- side adversary to have access to the user's information. Homomorphic encryption (HE), can be applied to enable inference to be performed the user without risk of the server accessing the original data or the inference result. CRYPTONETS GachachBachrahh et al. 2016) was the first application of HE secure neural network inference, and leveraged the YASHE' scheme to perform MNIST classifications. CRYPTONETS suffers from high number of homomorphic operations (HOPs), with single MNIST inference requiring 290, 000 homomorphic multiplications and 250 seconds of inference latency. Subsequent works such as FASTER CRYPTONETS (Chou et al. 2018) used neural network surgery and faster encryption scheme to reduce the inference latency of CRYPTONETS.
encrypted data, enabling the result to be delivered to
Later works utilised ciphertext rotations as opposed the SIMD packing scheme, enabling convo- lutional and fully connected layers to be computed using much fewer HOPs (Juvekar et al.) 2018 Mishra et al. 2020p. This has been shown to reduce the inference latency of MNIST models by more than order of magnitude, bringing confidence that private inference be practical. LOLA (Brutzkus et al.] 2019) proposed novel representations for intermediate tensors and their MNIST model requires only 2.2 seconds for one inference. One drawback of their representations is poorly scalability to harder datasets such as CIFAR-10 10 due to the limited number of slots per ciphertext acting barrier the size of tensors that are practical.
The limitated set of operations supported by HE schemes prevents the secure computation of non- polynomial activation functions which impedes model training due to the problem of exploding

---

Under review as a conference paper at ICLR 2022
2018). To address this, others have proposed the use of secure multi-party computation to enable secure computation of non- pol-yooyomiial activations using multiple parties (Ju-) vekar et al. 2018 Mishra et al. 2020). Despite enabling use of popular nonpolynomial activations such as ReI.U, rel relying on multiparty computation incurs large amounts of data transfer between parties and the requirement for the parties involved be online and have feasibly fast data transfer rates. For example, GAZELLE (Juvekar et al., 2018)) requires ~- GB of data transfer per inference for their CIFAR-10 model, and DELPHI (Mishra al. 2020) requires ~ GB per inference with ResNet-32 model. Single-party approaches often choose to approximate the ReLU activation using a second-degree polynomial (Gilad-Bard Bachrach et al. 2016; Chou et al., 2018: Brutzkus et al. 2019).
gradients (Chou al.
In this work, we introduce a framework for secure inference on secure CNNs, designed to reduce the number of HOPs required per inference whilst preserving prediction accuracy. Our contributions can be summarised as follows:
We integrate the convolution- packing method from LoLA with the fast matrix- prod- uct method introduced by Halevi and Shoup (Halevi & Shoup, 2019) and utilised by [Ju-] vekar et al. (2018) in their multi-party computation framework. Intermediate convolutions are converted into fully-connected layers and computed as matrix-vector products. We show that utilising the Halevi-Shoup method allows the use of rotations and ciphertext packing to scale better compared with the representations in LOLA, when applicd to larger convolutional layers. We perform more detailed investigation methods used in LOLA to larger models and show that they are significantly outperformed by our proposed method.
the scalability of the
We compare our framework against LOLA by constructing models for MNIST and CIFAR- 10. Our main evaluation criteria is the number of HOPs required per inference for model. With the same layer parameters as LOLA, we are able to obtain over a two-fold reduction in the number of HOPs per inference. Our CIFAR-10 10 model achieves similar accuracy to that of LOLA'S 's but uses far fewer operations.
2 BACKGROUND AND PREREQUISITES
2.1 THREAT MODEL
Our threat model concerns that of the machine learning as service paradigm (MLaaS), in which the user first sends data to a server, which then performs machine learning inference on the received data using some model. The inference result is then delivered back to the user. For example, consider an online machine learning service which claims to detect the probability of a person having COVID-19 from an audio recording of their cough. Suppose that Alice decides send a recording of her cough to this service, in the hopes of receiving a diagnosis. There are two key threats in this scenario: (i) the risk of an adversary cavesdropping on the data transmission, and (ii) the risk of the MLaaS provider performing unauthorised access on the user's data - in this case, the recording produced by Alice. The first threat can be mitigated using standard cryptographic protocols. However, the second risk is harder to address, especially if the user data is decrypted before inference [ae et al. (2018). The use of HE mitigates both risks. The data is encrypted using HE, which sufficient to prevent an adversary from eavesdropping. In addition, the provider is only able to perform computations on the encrypted data and will output the inference result without being able to decrypt.
2.2 HOMOMORPHIC OPERATIONS
Several recent HE schemes such as BFV (Brakerski & Vaikuntanathan 2011 and CKKS (Cheon
al., 2017) are based on the RLWE problem and support SIMD ciphertext operations. On a high level, such schemes establish a mapping between real vectors and a plaintext space. The plaintext space is usually the polynomial ring R = /|X + 1). In particular, this a cyclotomic polynomial ring R [XX)/(0M(A)) where 4x((X) is the M-th cyclotomic polynomial and M = 2N is a power of two. The decoding operation maps an element in R to a vector that is either real complex, depending the scheme used. The encoding operation performs the reverse. Plaintext polynomials are encrypted into ciphertext polynomials using a public key. The operations of addition and multiplication can be performed over ciphertexts using an evaluation key.
2

---

Under review as a conference paper at ICLR 2022
Since each ciphertext corresponds vector of real (or complex) values, single homomorphic operation between two ciphertexts constitutes an element-wiss operation between two vectors. In addition, such schemes support rotations of the slots within ciphertext, with the use of Galois automorphisms.
2.3 FLATTENED CONVOLUTIONS
Consider the convolution of an image I with filter f. For simplicity, assume that both the image and filter are square, the vertical and horizontal strides of the filter are equal. Let I E IR dg Xd, X and f E Rx Denote the stride as and padding as p. Now, the output feature map such that J E Rdduxdd Xdur where
din - k + 2p
doat
+1. 1.
A full convolutional layer that outputs Cout feature maps will require a convolution of the input image with each of the Cout filters. Consider the vector v obtained by flattening each output feature map row-wise. This can be expressed as a matrix-vector product of the form v A. w E R C ewe where A E Rula Foo X d and w is the flattened representation of I.
2.4 FAST CONVOLUTION
The first convolutional layer in a CNN can be represented using convolution-packee (Brutzkus et al., 2019). The convolution of input image / with filter y of width w, height h and depth d is
w- ---1h-1-1 -
(f * [
glz, y. 2If i æ.J + y, 2].
y=0 ==0
Observe that the parallelism inherent in this computation enables to be vectorized as
08- A--ldd d-11
f*g= -0=Σ>> Σ
[0, y, 2] p(a.,)),
(2)
z= y= ==0
where ((....))) is matrix such that (2.0.=) + j,j+y, 2]. For an input image I Xd ij
feature maps and kernel of window size k, the input image is represented as k.2 Cn vectors vi,..., Vgg.cu where contains all elements convolved with the i-th value in the filter. Denote corresponding ciphertexts as ct,..... Claa.... ... The process of producing the j-th output feature map is now reduced to ciphertext-plainter multiplication of each ct, with the i-th value in the j-th filter. In total, the process requires 622 Gin ciphertext- multiplications per output feature map, leading to total of 62 Gn Cou multiplications.
2.5 MATRIX-VECTIN MULTIPI.ICATION
Multiplying a plaintext weight matrix of A R with a ciphertext vector can be achieved naively by first performing ciphertext multiplications of the vector with each row of A. Then for each product ciphertext, we can compute the sum of all elements within by applying a rotate- and-sum procedure (Halevi Shoup 2019): we first rotate the ciphertext by N/2 slots and add it to the original. Then the procedure is repeated for N/4 slots, N/8 and so on, until the sum of the ciphertext resides within all slots of the ciphertext. The resulting dot products can be summed together. This basic approach requires (m log r1) rotations.
Halevi Shoup 2019) introduced a more efficient method of computing the encrypted matrix- vector product A. V for square A. GAZELLE (Juvekar et al. (0188) extended the approach to support rectangular A E Rmxx The method works by decomposing A into its m diagonals, de- noted [d, d2, dm,) such that d, [A Ait1,1,... Aitn-Ix--)), Note that all row positions are modulo m. Then each d, rotated positions to align values belonging to the same row of A into the same column(s), and finally each rotated diagonal is multiplied with with corresponding rotations of v. The ciphertexts are summed, and the last stage is to apply a rotate-and taitte-ad--mm procedure to the resulting ciphertext. Overall, this procedure requires O(m) multiplications and O(m + log, n) rotations. We propose an improved variant of this approach for our framework described in section
3.1
3

---

Under review as a conference paper at ICLR 2022
3 METHOD
In this section, we present our method for achieving Srivacy-preservin CNN inference with low numbers of HOPs. In summary, we adopt the fast convolution method from LOLA but compute the intermediate convolutional layers network using the Halevi-Shoup (HS) matrix-vector product method instead. This enables large convolutions to be performed in far fewer ciphertext rotations than LOLA'S 's approach of computing a rotatc-and-sum procedure for each row in the weight matrix. In section 3.1 we explain the approach improvements made by our modifications compared with the approach from LoLA. In section 4, apply our approach to models for the MNIST and CIFAR- 10 datasets.
use. In section 3.2, we perform analysis to show the
3. PERFORMING INTERMEDIATE CONVOLUTIONS
In Section 2.3 we state that a convolution can be flattened and represented as a matrix-vector product A W E die where A E T Cau x and w is the flattened input.
This product be computed efficiently using the Halevi-Shoup method. However, neither the original method (Halevi & Shoup 2019) nor GAZELLE (Juvekar et al.] 2018) discuss the con- straints the ciphertext slot count imposes in this context. In Proposition we show that certain constraints must be applied on the sizes of the input and output of the convolution. In particular, we must have N 2 de Gin deut
Cout 1, unless doa and Cout are both powers 2f
Proposition 1. Let N denote the ciphertext slot count, and n = di, Cin be the size the the convolution impul, and m desr Cout be the size of the output. The basic Halevi-Shoup method, which takes 1 + [log2 m=+n-1)1 rotations, requires the condition that N 2 + n 1. If this does not hold, but is the case that 2¹, 0 $
logg N, then m + loga rotations are required.
Proof. Applying the Halevi-Shoup technique requires ciphertext diagonals d .d....dd' (m) of length n to be extracted, rotated and summed. Note that ( Ai+ii Now, if N 2 m+n-1 then N is sufficiently large for all rotations to be performed without wrapping around the ciphertext. If
N < m + n 1, then wrap-around will occur for at least one of the diagonal ciphertexts during ro- tation. For any slot a the rotation by positions will shift the slot to position A: i+J (mod N).
The slot (t is from the row of A with index i+ (mod m), and so must be shifted into an index that is equivalent to r modulo m, order for the rotatc-and-sum algorithm to be used. N is integer multiple of m, then will cause the diagonals to be misaligned when summed together. Since is a power of 2, the requirement that divides N is satisfied whenever drat and Coat also powers of such that 2 logg drm + log2 Cout < logg N.
see k = (mod m) indeed holds. Otherwise, wrap-around
Based on Proposition I we utilise procedure to ensure that the method can be applied for all choices of (din, douts Giny Cout) where de Cout S N: if the condition that N 2 + n 1 does hold, then we 'round' m to the closest power of not less than itself, and add corresponding rows filled with 0's the weight matrix. This procedure is illustrated below for the simple case where N = 4, m = and n 4. Notice that the padding allows the diagonals to align correctly after rotation.
Pad
Diagonalize
Align
Figure 1: An illustration of version of the Halevi-Shoup method that utilises a padding method.
4

---

Under review as a conference paper at ICLR 2022
3.2 COMPARISON WITH LoLA
Firstly, we follow the terminology used by BBrutzkus et al. (2019) and define dense, sparse, stacked and interleaved representations for vector E I
Sparse: is represented with n ciphertexts, where the i-th ciphertext contains the i-th
element of all its slots.
Dense: is represented a single ciphertext where the first n slots correspond to the values in v.
Stacked: v represented as a single ciphertext that contains as many copies of v as the ciphertext slot count permits.
Interleaved: is represented as single ciphertext similar to the dense representation however, the slots are shuffled by some permutation.
LOLA proposes cense-vector row-major matrix vector product method (which we call LoLA- dense) that maps the input vector in the dense representation to an output vector in the sparse rep- resentation. Let
Rmxn The dense-vector row-major method computes Av1 multiplication per row of A and summing the elements inside each product vector using the rotate- and-sum procedure. This the basic approach described in Section 2.5 except the dot products are not summed together.
V2 via
They also propose stacked-vector row-major method (which we call LOLA-stacked) that requires input vector in the stacked representation and provides the output in the interleaved representation. To obtain the stacked representation, they first pack & copies v into a single ciphertext where NN/((n) and 5(n) 2|ooR, x is the smallest power of greater than or equal to n. The stacked vector is then multiplied with corresponding stacked rows of A, before rotate-and-sum is applied. The main drawback of this method is its reliance on the ability to pack many copies of into a ciphertext, which requires N to be much larger than For large convolutions, this is hard to achieve. We derive the number operations this method takes.
HS
LoLaDense
LoLaS
100000
80000
rotatious 1018
40000
20000
8000
6000
4000
2000
4000
2000
GUUU
8000
Figure 2: Comparison of LOLA's matrix-vector product methods with the Halevi-Shoup approach. in terms of the number of rotations required for computing fully-connected layer from n inputs to m outputs.
Remark
The stacked-vector row-major method proposed by Brutzkus et al. 2019 requires (I: + [log, n
mm rotations and m multiplications.
Proof. The stacking in Brutzkus et al. (2019) done is using rotations and additions. Then the point-wise multiplication requires single SIMD multiplication between the ciphertext and

---

Under review as a conference paper at ICLR 2022
(stacked) rows of A. Finally, flog2 n rotations and additions performed compute the A elements of the product vector. Since N is not always sufficiently large to pack m copies of n, this procedure has to be performed + times. To produce all elements of the product vector, to multiplications are performed, before [ rotations I (A: + [log2 n - 1) rotations and x
performed to bring the ciphertexts into single one. Note that the produced ciphertex((S)
contain the product elements in an interleaved format, i.c. permutation.
Suppose we are passing 4096-length representation into a fully connected layer to map to a 64- length embedding, and let N 16384. LoLA-dense would require 64 log, 4096 768 rotations and 64 multiplications; LotA-stacked would require 1023 rotations and 64 multiplications. Now, the Halevi-Shoup product approach would require only 64 + log, 8192 77 rotations and 64 mul- tiplications. Since rotations are the most expensive operation, we compare the number of rotations required by each of the three methods in Figure 2
can be shown that for any n > 1, ..LLLL-ASS- LoL.A-ttceedd uses fewer rotations than LoLA-dense. However, LoLA-dense can be used compute two layers instead one. For large inputs and output layers (relative to N), however, both methods require significantly more rotations than HS. LoLA-stacked relies on m ((n) /N being small whereas LoLA-dens relies on log, n being small. With HS, even if n N, log2 n. is insignificant compared to m.
In general, we believe that having the number of rotations be linear to only m is beneficial since neural networks typically down-sample or pool the data to produce denser, higher-level represen- tations, and so can expect n 2 m generally. should noted that there are exceptions such as bottleneck layers.
4 EXPERIMENTS
We conduct experiments the MNIST and CIFAR-10 datasets. We first apply approach the CRYPTONETS architecture used in LOLA,, to create a model CRYPTONETS-HH The same architec- ture was shown achieve close 98.95% accuracy by GGilad-Bachaad similar performance using their training parameters. Training is conducted using TensorFlow (Abadi al. 2015). The architecture is then converted into sequence of homomorphic operations. We use the SEAL library (Chen el al. 2017) for this. For reference, the original CRYPTONETS architecture shown in Figure
et al.) (2016), and observe
50 x 5
50 5 x
100
30
sxx 13
x 13
8
10
Convolution
Pooling
Convolation 3,5=
Pooling 3,8
Deuse
Deuse
k 5,8
Figure 3: The architecture used in LoLa. k indicates the kernel size and indicates the stride of convolution and pooling. Note that the original 28 x 28 input is padded.
LOLA uses combination of their stacked and interleaved representations for their intermediate convolutions. We opt to use the efficient approach instead. To reduce consumption of instruction depth, linear layers without activations between them are composed together. For instance, each cnvollutionpooliing block CRYPTONETS HS is a single linear layer. This done to enable bascline to match the architecture in LOLA. It should be noted that omitting activations reduce representational power and made not be ideal in practice. The models are implemented using operations provided by the SEAL library, and inference is performed standard desktop

---

Under review as a conference paper at ICLR 2022
processor. We utilise only single thread. We measure the number of homomorphic operations required per single inference, as well as model test aceuracy.
Using the proposed improvements, 10, respectively. The proposed architectures have reduced memory requirements and layer parame- ters that better suited towards the HS method:
also construct models ME and CE. for MNIST and CIFAR-
Model ME has similar test accuracy CRYPTONETS-HS but is designed in consideration the way we are computing the layers. note that applying the HS method computing layer 6 of CRYPTONETS HS requires setting reduce the kernel size of the first convolution from x 5 to x 3, and the size the first dense layer from 100 32. To account for the reduced representational power of the first convolution, the stride reduced from 2 to 1. This notably does not add any homomorphic operations the computation. We are able achieve 98. 7% 100 epochs of training with the Adam optimiser.
100 and
845. Specifically,
accuracy using ME after
Model CE is larger, and requires more operations to compute. We initially construct model with a second convolutional layer with an output tensor of size 8 with 64 chan- nels, and then follow the approach from Lu et al. (202T) and use SVD to factorise this layer convolution which is efficient compute
into smaller cob-convolution followed by a using the ceayvolution-pcckknng method described in LOLA. The smaller sub-convolution is computed using the HS method. The final trained model a test accuracy 73.1%.
Layer
Description
Parameters
Input
Convolution
k ==
(1, 30, 30)
Square
(5, 28, 28)
Avg. Pool
k == 3,
(5, 28, 28)
3
Convolution
k k= =33
(50, 14, 14)
4
Avg. Pool
k= 3,
(50. 12, 12)
Flatten
(50, 12, 12)
Dense
m = 32
(1250)
Square
(32)
7
Dense
10
(32)
Softmax
(100)
(a) ME layer parameters.
Layer
Description
Parameters
Input
Convolution
3,
(I, 32, 32)
Square
(18, 30, 30)
Average Pooling
k = 2,
(18, 30, 30)
Sub-convolution
k = 3,
(18, 10, 10)
Sub-convolution
(13, 8, 8)
Square
(18, 30, 30)
Average Pooling
2,
(64,
Convolution
k = 3,
(64, 4,
Flatten
(256, 2)
Dense
m 512
(1024)
Square
(18, 30, 30)
Dense
m = 10
(256)
Softmax
(10)
(b) CE layer parameters.
Table 1: Layer parameters for ME (left) and CE (bottom). k and indicate the kernel width and stride respectively. m indicates the number of output nodes of fully-connected layer.
5 RESULTS AND DISCUSSION
Table shows breakdown of the operations for the models discussed far. In homomorphic encryption applied to neural networks, the most expensive homomorphic operation is rotation, with worst case time complexity of performing both number theoretic transform (NTT) and an inverse

---

Under review as a conference paper at ICLR 2022
NTT vectors of length N. We observe that CRYPTONETS-HE requires total of 122 rotations, as shown in Table 2a LOLA-MNIST requires a total of 380 rotations for the same architecture. We notice that at both the convolution-poollee implementation has fewer rotations than LOLA. The reduction in rotations is a direct result of applying the HS method to compute flattened convolutions, in which the number of rotations scales with the size of the output tensor, rather than the size of the input. LoLA uses the stacked-vector row-major method for the first convolution, and the dense-vector row-major method for the second convolution. In Section 3.2 we discussed that both of these scale poorly compared to the HS method.
blocks in the CRYPTONETS architecture, the HS
Now, the optimised ME architecture requires only 56 rotations per inference, but still achieves high test accuracy of 98.7%, which is close to the 98. 9 test accuracy achieved by LOLA-MNIST, suggesting that careful selection of layer sizes can lead great reductions inference latency. We do note that CRYPTONETS- -S requires more multiplications than LOLA-MNIST (245 vs. 148). This is due to the stacked-veet vector row-major approach reducing the number of multiplications needed. However, the reduction in rotations exceeds the increase in multiplications.
Layer
Total HOPs
Add PC
Add CC
Mul PC
Mul CC
Rot
M L' L
M
L'
L
M
I.
M
T L
M L
I
M
L'
L
Conv1
90 250 250
5
5
40
120 120
45 125 125
Flatl
4
Squarel
1 1
1
Conv2-Dent 1
110 308 492
38
103
246
32
100 13
39
104 246
Square2
1
1
Dense2
36 38 279
12
13
139
10
10
13
14 130
Total
246 606 1031
5
94
240
509
87
235
148
2
2
2
56
122
380
(a) Comparison of operations in three different LOLA-MNIST model, L' indicates the CRYPTONETS HS model, and M indicates the ME model. 'CC' indicates operation between two ciphertexis and 'PC' indicates operation between plaintext and ciphertext.
MNIST models. L indicates the original
Layer
HOPs
Add
Add
Mul
Mul
Rot
PC
CC
PC
CC
Conv1 Flatl
972
18
468
486
30
15
15
Squarel
3
3
Pool1-Conv2
7506
2504
2496
2505
Conv3
1677
768
832
13
Flat2
126
Square2
Pool2-Densel
778
260
256
261
Square
Dense2
40
14
10
15
Total
11134
85
4092
4080
2872
(b) Break-down of operations in CE.
Table Break-dowe of the types of operations performed by the low latency models. The notation 'layerl-layer'' denotes the layers between and including layerl and layer2.
In terms latency, the CRYPTONETS-FE model requires 2.7 seconds, whereas ME requires only 0.97 seconds. For For reference, LOLA-MNIST requires 2.2 seconds per inference; however, they utilise cores on a server CPU whereas our homomorphic operations are run on single core of a desktop processor.
For the CE model, we provide a model with sightly lower test accuracy (73.1% vs. 74.1%) but requiring less than 10% the number of rotations than LoLa's CIFAR- 10 model. This due to both ensuring that intermediate tensor sizes fit well into the number of available slots, and also the use of the HS method. The number of operations for each layer is shown in 2b It should be noted that sizeable portion of this reduction comes from using a smaller model. The exact model from LoLA
Note that this is deduced to the hest of ability using the descriptions supplied in their paper.
8

---

Under review as a conference paper at ICLR 2022
was not implemented due to its high memory requirements. However, expect that utilising approach for LOLA's 's CIFAR-10 architecture would still significantly reduce the inference latency.
The main takeaway from the results is that the application of the HS method to the framework proposed by LoLA can significantly reduce the number of rotations, which are the most computa- tionally expensive HE operation. In addition, our models ME and CE are more efficient than the ones proposed by LoLa whilst achieving similar accuracy.
CONCLUSION
prraccypreserving inference using homomorphic encryption largely constrained by the compu- tational requirements of the operations. We propose improvements over LoLA to achieve lower latencies computing intermediate convolutions, resulting in over two-fold reduction in the number of rotations for the same MNIST architecture. It clear that further improvements can made along this direction, especially in the topic of automatically selecting suitable layer parameters to set the trade-off between inference latency and model accuracy (Lou al. 2020).

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, llya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wat- tenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learn- ing on heterogencous systems, 2015. URL hitps: /wtp//wwwwww..mm www.wrtensorflo..o org/ Software available from tensorflow.org.
Ho Bae, Jachee Jang, Dahuin Jung, Hyemi Jang, Heonseok Ha, and Sungroh Yoon. Security and privacy issues in deep learning. urXiv:/807.11666 2018.
Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) lwe. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 97-106. IEEE Computer Society, 2011.
Alon Brutzkus, Ran Gilad-Bachrach, and Oren Elisha. Low latency privacy preserving inference. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 812-821. PMLR, 2019.
Hao Chen, Kim Laine, and Rachel Player. Simple encrypted arithmetic library seal v2.1. In Financial Cryptography and Data Security, pp. 3-18. Springer International Publishing, 2017. ISBN 978-3-319-70278-J
Jung Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic eneryption for arithmetic of approximate numbers. In Advances in Cryptology ASIACRYPT 2017, pp. 409-437. Springer, 2017.
Edward Chou, Josh Beal, Daniel Levy, Serena Yeung, Albert Haque, and L. Fei-Fei. Faster cryp- tonets: Leveraging sparsity for real-world encrypted inference. /rXiv:/8/1 18/109953 2018.
Ran Baaadd-,cchrch, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John Werns- ing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, pp. 201- 210. PMLR, 2016.
Shai Halevi and Victor Shoup. Algorithms in helib. In Advances in Cryptology, pp. 554-571. Springer, 2019.
Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. Gazelle: a low latency frame- work for secure neural network inference. In Proceedings of the 27th USENIX Conference on Security Symposium, pp. 1651-1668. USENIX, 2018.
Qian Lou, Song Bian, and Lei Jiang. Autoprivacy: Automated layer- wise parameter selection for secure neural network inference. In Advances in Neural Information Processing Systems, vol- ume 33, pp. 8638-8647, Curran Associates, Inc., 2020.
Yuxiao Lu, Jie Lin, Chao Jin, Zhe Wang. Khin Mi Mi Aung, and Xiaoli Li. Ffconv: Fast factorized neural network inference on encrypted data. arXiv:2102.03494 2021.
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In Proceedings of the 2020 Work- shop on Privacy-Preserving Machine Learning in Practice, pp. 27-30, ACM, 2020.
10


Reviews:
[{"review_id": "bzg4Xgj75QB", "reviewer": "Reviewer_7wWC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Strengths**\n\nThe experimental results demonstrate that the proposed method is much more efficient than previous works.\n\n\n**Weaknesses**\n\nDisclaimer: The reviewer is not familiar with the literature of HE schemes for privacy-preserving inference, and has not checked the relevant literature closely.\n\nOverall, the reviewer feels that the writing of this paper is not clear, and many details are missing or not easy to follow. For example, the main methods are supposed to be in Section 3.1, while this section only contains a primitive introduction to the convolution operation and its flattened version (which I would expect to reside in Section 2), and a remark which tells the number of operations for the proposed method. The two parts are a bit disconnected. Based on my understanding, the proposed method is to apply the HE operation (as in Section 2.4) on the flattened convolution operation, and this part should go before the remark part. But the corresponding description is completely missing from my point of view.\n\nIn section 3.2, the authors compared with two types of representations in LoLa: the sparse representation and the stacked representation. I roughly checked the LoLa paper (Brutzkus et al., 2019). Actually they have five types of representations, even including a \"Convolution representation\" which claims to \"make convolution operations efficient\". I didn't check the details of their \"Convolution representation\", but I would like to ask the authors what is the difference between their method and yours, and why you didn't involve a comparison in your paper? I would appreciate it if the authors can provide a clear explanation to this.\n\nIn experiments, the authors mentioned that \"linear layers without activations between them are composed together\". But activations are often quite important in all sorts of architectures. Is there any reason that impeded authors from using activations? Also, the last column of Table 1(a) (i.e., the \"Input\" column) look wrong to me. I would suggest that the authors carefully check the numbers.\n\nMinors:\n\n* Authors said \"We choose to use a variant of this method ... \". So is the variant proposed by the authors? What is the relationship of this variant and Halevi & Shoup (2019) and GAZELLE (Juvekar et al., 2018)?\n* In Section 3.1, $\\mathbf{v}$ should be $\\in \\mathbb{R}^{d_{\\mathrm out}^2\\cdot c_{\\mathrm{out}}}$\n* In Section 3.1, the \"Remark\" should be replaced by \"Proposition\".", "summary_of_the_paper": "This paper follows the line of work that leverages holomorphic encryption (HE) operations on encrypted data for privacy-preserving inference on MLPs and CNNs. Authors propose changes to the representations of intermediate layers during CNN inference, which requires much fewer number of operations than previous works.", "summary_of_the_review": "Several important details and comparisons are missing in the paper, which largely weakens the contribution of the paper. Also, there are flaws in the statement, and the writing is not professional enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "VZngbzVju2V", "reviewer": "Reviewer_gqrN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The technique is explained well and there is an-depth analysis of the resulting complexity with a comparison to prior work. The 2-3x improvement is considerable. Furthermore, the editorial quality is high.\n\nMinor:\n- p7: 56 rotation(s)\n", "summary_of_the_paper": "The paper applies the state-of-the-art technique for matrix-vector multiplication in homomorphic encryption to encrypted inference for convolutional neural networks.\n", "summary_of_the_review": "The paper provides a well-argued application of the state of the art in homomorphic encryption.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PFknTMObSzH", "reviewer": "Reviewer_uGUc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Overall, this paper addresses an important problem in privacy-preserving machine learning and the results show that the method is effective. However, the originality and the evaluation of the paper are not strong enough. The originality is incremental because the authors applied an existed approach, HS, to an existed structure, CRYPTONET. The evaluation is not sufficient because the experimental results are not well analyzed and interpreted. For example, only a limited part in table 2 is discussed in the text. More analysis about table 2 would improve the results section of the paper. In addition, the introduction to the HS method is a little short and the entire pipeline of the HS approach is not easy to follow. By focusing on the introduction to the HS method instead of the introduction of the baseline LOLA method, the authors can explain the HS method better.", "summary_of_the_paper": "To accelerate the privacy-preserving inference through convolution neural networks (CNNs) with homomorphic encryption (HE), the authors aim to reduce the number of homomorphic operations (HOPs) required for the algorithm to save the data needs to be transferred while preserving prediction accuracy.\n\nUsing a LOLA method as a baseline, the authors used Halevi-Shoup (HS) which requires much fewer rotations operations in general. In the experimental results, the HS method requires half of the operations in comparison to the LOLA method. By further simplifying the structure of the network, only about 20% of HOPs are required. These simplifications bring about 1% and 27% accuracy loss.\n", "summary_of_the_review": "The paper is marginal acceptable because the paper is addressing an important question and the method is effective. However, the improvement of the method is not impressing or suppressing. The entire is not well finished. Thus, this paper is regarded as a border line paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FS3kWN7c_zM", "reviewer": "Reviewer_9nHn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pros:\n\n1. The paper attempts to study a problem that is at the heart of privacy preserving machine learning, i.e., speeding up HE based inference on deep neural networks.\n2. The paper is well written.\n\nCons:\n\n1. The paper is rather straightforward rehashing of existing (which are themselves rather simplistic, in my opinion). For instance, they take a recent improvement by Halevi and Shoup for Matrix products and apply it to the previous work LoLa. \n\n2. The experimental section is quite weak and misleading. In the abstract it is claimed that the current work improves upon the existing work by two orders of magnitude. While this is true when compared by CryptoNets -- the more recent works already seem significantly better. \n\n", "summary_of_the_paper": "The paper considers the problem of privacy preserving inference on deep learning models using homomorphic encryption. HE is a special type of encryption that allows one to perform certain types of computations while the data is encrypted. However, the catch is HE based inferences can be significantly slower than the non-private counterparts. The paper claims to improve upon the existing state of the art HE based inference approaches significantly -- two orders of magnitude.", "summary_of_the_review": "I think this is an important problem and the paper is reasonably well written. Unfortunately, it is a rather weak attempt. Essentially, it is a rehashing of existing ideas -- which are already uninspiring from an ML point of view. Further, as described above, the experimental section is rather misleading. For instance, there is no clear comparison of inference time with LoLa (does it improve the inference time at all?). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper improves on the efficiency of prior work that uses homomorphic
encryption to perform privacy-preserving inference. There are two main
concerns raised by the reviewers. First, multiple reviewers (and I) found
this paper difficult to read. Multiple pieces of the problem are not
clearly presented especially with respect to the technical contributions.
This was fixed in part in the rebuttal but more could still be done here.
But more importantly, three reviewers raise concerns about the evaluation
methodology, especially with respect to comparisons to prior work. On top
of this, there are valid criticisms raised by the reviewers about if the
contribution here is that significant when compared to prior work. (This
is something that both more clear writing and more careful experiments
could hep address.) Taken together I do not believe this paper is yet ready
for publication.
Decision: Reject