Soteria: In search of efficient neural networks for private inference
Authors: Anshul Aggarwal
Trevor E Carlson
Reza Shokri
Shruti Tople
Venue: ICLR 2022 Submitted (2022)

Abstract: In the context of ML as a service, our objective is to protect the confidentiality of the users’ queries and the server's model parameters, with modest computation and communication overhead. Prior solutions primarily propose fine-tuning cryptographic methods to make them efficient for known fixed model architectures. The drawback with this line of approach is that the model itself is never designed to efficiently operate with existing cryptographic computations. We observe that the network architecture, internal functions, and parameters of a model, which are all chosen during training, significantly influence the computation and communication overhead of a cryptographic method, during inference.Thus, we propose SOTERIA — a training method to construct model architectures that are by-design efficient for private inference. We use neural architecture search algorithms with the dual objective of optimizing the accuracy of the model and the overhead of using cryptographic primitives for secure inference. Given the flexibility of modifying a model during training, we find accurate models that are also efficient for private computation. We select garbled circuits as our underlying cryptographic primitive, due to their expressiveness and efficiency. We empirically evaluate SOTERIA on MNIST and CIFAR10 datasets, to compare with the prior work on secure inference. Our results confirm that SOTERIA is indeed effective in balancing performance and accuracy.

Under review as a conference paper at ICLR 2022
SOTERIA: IN SEARCH OF EFFICIENT NEURAL NET- WORKS FOR PRIVATE INFERENCE
Anonymous authors Paper under double-blind review
ABSTRACT
Consider ML-as-a-service where cloud server hosts trained model and offers prediction (inference) service to users. In this setting, our objective is to protect the confidentiality of both the users' input queries as well as the model parame- ters at the server, with modest computation and communication overhead. Prior solutions primarily propose fine-tuning secure multi-arty computation protocols to make them efficient for known fixed model architectures. However, the model itself is not originally designed to operate efficiently with existing efficient cryp- tographic computations. We observe that the network architecture, internal fune- tions, and parameters of a model, which are all chosen during training, signifi- cantly influence the computation and communication overhead of cryptographic method, during inference. We propose SOTERIA - a training method to con- struct model architectures that are by-design efficient for private inference. We use neural architecture search algorithms with the dual objective of optimizing the accuracy of the model and the overhead of using cryptographic primitives for secure inference. We select garbled circuits as our underlying cryptographic prim- itive, and empirically evaluate SOTERIA to compare it with the prior work. Our results confirm that SOTERIA is effective in balancing performance and accuracy.
INTRODUCTION
Machine learning models are susceptible to several security and privacy attacks throughout their training and inference pipelines. Defending each of these threats require different types of security mechanisms. One important requirement is that the sensitive input data as well as the trained model parameters remains confidential during the inference time. In this paper, we focus on private compu- tation of inference over deep neural networks, which is the setting of machine learning-as-an as-eevie... Consider a server that provides machine learning service (e.g., classification), and a client who needs to use the service for inference on her data record. The server is not willing to share the proprietary machine learning model, underpinning the service, with any client. The clients are also unwilling to share their sensitive private data with the server. In addition, do not trust, nor include, any third entity in the protocol. In this setting, our first objective is to de- sign secure protocol that protects the confidentiality of client data well as the prediction results against the server who runs the computation. The second objective is to preserve the confidentiality of the model parameters with respect to the client. These can be achieved using secure multi-party computations. We consider an honest-but-curion threat model.
assume the two parties
A number of techniques provide data confidentiality while computing and thereby allow private computation. The techniques include computation on trusted processors such as Intel SGX Hunt al. (201 8a); Ohrimenko et al. (2016). and computation on encrypted data, using homomorphic encryption, garbled circuits, secret sharing, and hybrid cryptographic approaches that jointly opti- mize the efficiency of private inference on neural networks Yao (1986); Gentry (2009b); Yao (1982); Brakerski et al. (201 1); Beaver (1992). To provide private inference with minimal performance over- head and accuracy loss, the dominant line of research involves adapting cryptographic functions to (an approximation of) a given fixed model Liu et al. (2017); Mohassel & Zhang (2017); Mishra et al. (2020); Rouhani et al. (2018); Riazi et al. (2019); Chandran et al. (2019); Juvekar et al. (2018); Riazi et al. (2018). However, the alternative approach of searching or designing network architecture for a given set of efficient and known cryptographic primitives has not received much attention Ghodsi et al. (2020).

---

Under review as a conference paper at ICLR 2022
Note that secure multi-pant computations protect the confidentiality of the inputs to the protocol, and its intermediate computations, and cannot prevent inference attacks that exploit the output of the protocol to infer information about its inputs. We thus emphasize that the protection against the indirect inference attacks that aim at reconstructing model parameters Tramèr et al. (2016) or its training data Shokri et al. (2017), by exploiting model predictions, is not goal and out of scope for this work.
Our Contributions. We approach the problem of private inference from novel perspective where instead of modifying cryptographic schemes to support neural network computations, we advocate modification of the training algorithms for efficient cryptographie primitives. In a nutshell, we ad- vocate co-designing and co-optimizing models and cryptographic operations for efficient private inference. Research has shown that training algorithms for deep learning are inherently flexible with respect to their neural network architecture. This means that different network configurations can achieve similar level of prediction accuracy. We exploit this fact about deep learning algorithms and investigate the problem of optimizing deep learning algorithms ensure efficient private com- putation.
To this end, we present SOTERIA approach for constructing deep neural networks optimized for performance, accuracy and confidentiality. Although SOTERIA could leverage any of the avail- able cryptographic primitives or their combination, we select garbled circuits as its main building block to address the confidentiality concern. Garbled circuits (GC) are known to be efficient and al- low generation of constant depth circuits even for non-linear functions. We show that neural network algorithms can be optimized to efficiently execute garbled circuits while achieving high accuracy guarantees. We observe that the efficiency of evaluating an inference eircuit depends on two key factors: the model parameters and the network structure. With this observation, we design a regular- ized architecture search algorithm to construct neural networks. SOTERIA selects optimal parameter sparsity and network structure with the objective to guarantee balance between performance and model accuracy. We summarize our contributions below:
We propose a neural architecture search based approach called SOTERIA for designing models that guarantee balance between prediction utility and computation while maintaining confidentiality of the model parameters and the input during inference.
We build SOTERIA models using garbled circuits for both ternary neural networks as well the model architecture identified using network architecture search approach.
We evaluate SOTERIA the benchmark datasets used by all the prior work, and observe that our approach provides the flexibility to tune utility and efficiency parameters based on the requirement of the underlying scenario. Our complete anonymous source code is available on github.'
The two fields of research on neural architecture search Liu et al. (2019); Zoph & Le (2016); Elsken et al. (2018) and secure multi-party computation Yao (1986); Gentry (2009b); Yao (1982); Brakerski et al. (2011); Beaver (1992) are rapidly growing. SOTERIA enables take advantage of the advancements in these fields to systematically design more efficient algorithms for complex machine learning tasks.
SOTERIA
We design SOTERTA to automatically learn the model architecture and its connections so as to opti- mize the cost of private inference in addition optimizing accuracy. This approach is different than simply fine-tunning or compressing a model, as we aim to include the cost of private computation as part of the objective of architecture learning and parameter learning of the model. SOTERIA is built on top of two well-established classes of machine learning algorithms: neural architecture search algorithms, and ternary neural network algorithms.
Neural architecture search for efficient private inference. Architecture search algorithms for neural networks are designed replace the manual design of complex deep models. The objective is to learn a model structure that gives high accuracy when trained on the training set Elsken et al.
Source code of SOTERIA: https: //gi h/ggtttbbbb....o//////g/g...b..t com Coor//oteriii atnonymous//otterr.. /ttp://///ccccrrroooooooo/////e
2

---

Under review as a conference paper at ICLR 2022
(2018); Zoph & Le (2016); Pham et al. (2018); Liu et al. (2019). They automatically construct the model architecture by stacking a number of cells. Each cell is a directed acyelic graph, where each node is neural operation (c.g., convolution with different dimensions, maxpool, identity). During the search algorithm, we use stochastic gradient descent to continuously update the scores associated with different candidate operations for each connection in the internal graph of cell, to maximize the accuracy of the model on some validation dataset.
In SOTERIA, regularize the computation of the connection scores over candidate operations, with factor A. We penalize each operation proportional to its computation and communication overhead when garbled. Larger values of À result in models that prefer efficiency of private inference over accuracy. As we balance the trade-off between accuracy and performance, SOTERIA can construct models which by design satisfy the requirements of our system.
Ternary (Sparse Binary) Neural Network. To build system that enables efficient private in- ference, we aim to reduce the number of parameters contained in the model. One approach to accomplish this is to first train the model, and then compress it afterwards. However, this method might not result in the highest accuracy that could be achieved if we were to construct the model for this purpose from the beginning. To better align with our approach of constructing model ar- chitectures, we aim to learn model structures which are accurate, sparse, and are efficient when implemented garbled circuits. More specifically, in SOTERIA,
train models with ternary pa- rameters (-1, 0. +1 Li et al. (2016) and binary activation functions. This allows us to leverage the benefits for BNNs, discussed in Section B, with the benefit of a potentially smaller cireuit (due to the model's sparsity). We incorporate Ternary Neural Networks, or TNNs, into our regularized ar- chitecture search algorithm find cells containing only ternary convolution and max-pooling layers that operate on binary inputs and ternary parameters.
3 EMPIRICAL EVALUATION
In this section, we evaluate the efficiency of our method in two main ways. First, we show how using ternary neural networks on fixed model architectures, as used in the prior work Riazi et al. (2019); Mohassel & Zhang (2017); Rouhani et al. (2018); Juvekar et al. (2018), can reduce the overhead of secure inference on sparse neural networks. Second, we present the performance of SOTERTA architectures, in which model complexity is optimized along with the model accuracy.
Implementation. We first build a representation of the model and parameters in SystemVeriloo and then convert the model into digital circuit supported by TinyGarble Songhori et al. (2015), and implementation of the Garbled Circuit (GC) protocol. We synthesize and optimize our circuit (using Synopsys Design Compiler) to use circuit elements supported by TinyGarble. In the first step, we design a collection of parameterized components (notably dot product, and maxpool) to use as building blocks in our architecture search algorithm. Each component is flexible and can efficiently accept arbitrary size input and output, and is composed to form the complete model. In a general setting, hardware-level code is typically straight-forward with SOTERIA, we have to dynamically define the sparsity of the modules depending on the result of model training and architecture search. Along with the parameter data, we define the sparsity information which is used during generate phases in SystemVerilopp to build the sparse network in hardware (taking advantage of the O-valued parameters). Altogether, this allows us to build and evaluate SOTERIA models.
generate. However, enable TNNs
3.1 EXPERIMENTAL SETUP
We need to evaluate SOTERIA on datasets which are used in the prior work to be able to perform a comprehensive comparison between the methods (see Table 3 for all the configurations). We evalu- ate our work on MNIST and CIFARIO image classification datasets, as they are the only benchmark datasets which are extensively used in the literature to evaluate the performance of cryptographically secure neural network schemes. We run our experiments on an AWS c5.2xlarge instance, running Ubuntu 18.04 LTS on an Intel Xeon 8124M at 3.0 GHz. We use Py PyTorch 1.3 Pyt, deep learning framework to implement our architecture search algorithm and train the ternary models. We use Synopsys Design Compiler Syn, version L-2016.03-SPP to synthesize System Verilog code into
3

---

Under review as a conference paper at ICLR 2022
the gate-level netlist. Our synthesis runs the TinyGarble gate library infrastructure". We compute the number of non-XOR gates in the generated boolean circuit netlist as a measure of its complexity. We measure the exact performance of SOTERIA as its runtime during the offline and online phases of the protocol, and its communication cost. We present the experimental setup of prior work and SOTERIA, including their CPU specification and link to available software codes, in Table 7. We also present the details of all neural network architectures which we evaluate in this paper in Table 6.
3.2 RESULTS FOR GC ON TERNARY NEURAL NETWORKS
In this subsection, we illustrate the benefits of taking advantage of the inherent sparsity (fraction of parameters with weight 0) found in ternary models, and analyze the effect of the scale of the network in the tradeoff between model accuracy and performance of private inference.
Sparsity. The sparsity of the trained model allows for the reduction in the amount of computation needed in the resulting preseerigg Garbled Circuit implementation. To demonstrate this, Figure la lists the number of non-XOR gates needed when building a collection of ternary neural networks with a 4-kemel 3 3 convolution operation, an input of size 32 32 x 3, and a padding of size 1. We randomly set fraction of the parameters to zero to manually control the sparsity of the model. BNN model is equivalent to the case where the sparsity is O. With increasing sparsity, we direct benefit in the reduction of non-XOR gates (reducing those gates that require expensive computation a GC implementation) in the resulting computation. This can result in reducing both the communication overhead and the inference runtime, which see as we train large models used in SOTERIA throughout the rest of this section.
-103
Number of nonnnOOO -I-OXOR gates
260
Accuracy Runtime
240
0.98
80
Inference runtime (ms)
220
Test accurucy
0.96
200
180
0.94
60
160
0.92
140
40
120
0.9
100
0.05 0.1 0.15 0.2 0.25 0.3
0.88
20
0.5
1.5
2
2.5
3
Sparsity (fraction of O-weight parameters)
Scaling Factor
(a) Sparsity of model versus its circuit complexity.
(b) Test accuracy versus inference runtime.
Figure 1: (a) We measure sparsity as the fraction of model parameters with 0 weight. We quantify circuit complexity as the number of non-XOR gates. The numbers are computed on a ternary neural network with a 3 x 3 convolution operation with kernels and a 32 x 32 x 3 input. For this experiment, assign weights to random set of parameters, to get different levels of sparsity and corresponding number of non-Xt MOR gates. (b) Test accuracy versus inference runtime for a ternary neural network trained on fixed MNIST (ml) architecture, in various scale.
Note that while training a TNN, we cannot control the sparsity of the network, In Table 1, we show the result of training both binary and ternary models on MNIST dataset, model architecture m3 (see Table 6 for the model details). The GC costs the components of the network for both BNNs and TNNs are listed, with the trained ternary model showing significant sparsity (almost 0.3). This level of sparsity results fewer circuits for the trained model, and a lower overall inference cost for the GC protocol when using these ternary neural networks. This is reflected in the smaller number of non-XOR gates in the ternary circuits needed for the convolution and fully connected operations. The costs for the maxpool operation will remain the same, as does not contain any learnable parameters.
We base our work on TinyGarble with gitid 21 htc.aa/hhh.hh333rr50077711151100 //gi www./eooogeeeecccccc /ri /tinarrrrr/innrarrrlo nyGarble.
from https:
4

---

Under review as a conference paper at ICLR 2022
Table 1: Performance inference on garbled circuit models with binary versus ternary parameters. We show the independent offline and online runtimes, communication costs and number of non- XOR gates for three different types of operations. The operations are taken from MNIST (m3) network, trained in both binary (BNN) and ternary (TNN) configurations using a scaling factor of 1.
Runtime (ms)
Communication (KB)
Number of non-XOR gates
TNN
Operation Type Size
Offline
Online
Total
SSpariity
BNN TNN
BNN TNN
BNN
TNN
BNN
TNN
BNN
TNN
Input: 12 x 12 x 16
Padding: 0
Convolation
Window: 5 5
39.16 28.27
52.87
38.17
92.03
66.43
2,572
1,876
589,824
425,558
0.27
Kernels: 16
Input: 8 x 8 x 16
Maxpool
Window: 2
0.35
0.57
0.92
34
768
N.A.
Fully
Input: 100
Connected
Nodes: 10
0.49
0.34
0.83
0.60
1.32
0.94
68
47
3150
2246
0.35
Table 2: Number of parameters and corresponding sparsity and trained model test accuracy for MNIST (ml) architecture with various levels of scaling factor. The table reports the statistics of the experiment in Figure lb.
Scaling Factor
Total no. of Parameters
No. of O-weights
Sparsity
Accuracy
0.25
26, 432
5, 946
0.22
0.9063
0.50
54, 912
13, 058
0.24
0.9413
0.75
85, 440
18, 703
0.22
0.9544
1.00
118, 116,016 016
25,317
0.21
0.9579
1.50
312 312
43, 43.
0.23
0.9618
2,00
268, 800
54,
0.22
0,9658
2.50
356, 480
83, 431
0.23
0.9676
3.00
452, 352
343
0.24
0.9712
Scale. As discussed in Section to obtain high accuracy for binary and ternary models, the network needs to be scaled to achieve a higher model capacity. Figure 1b shows the impact of the scale of the network on accuracy of the model and its GC runtime for private inference. Although inference time increases linearly with the scaling factor, accuracy improves up certain extent with scaling (scaling factor of 1) and then becomes almost constant. This allows the designer to select a scaling factor that optimizes for both accuracy and performance.
Table 2 shows how the scaling factor affects the number parameters the network. As the scaling factor in TNNs increases, the accuracy also tends increase well. However, this levels off with diminishing returns after a certain limit. In addition to improved accuracy, the inference cost of the circuit also increases, is evident from the growth of runtime with change in scaling factor. Note that the sparsity is 0.24 for scaling factor of 3 for the ternary neural network, which means that the effective size of the model (hence its performance cost) remains comparable binary neural network (without any scaling), albict with better accuracy. As reference, the test accuracy of BNN model with the same architecture 0.9514.
Comparison with prior work. We present the outcome of basic SOTERIA (without the use of architecture search) on model urchitectures which are used in the literature, thus only discussing the effect of sparsity of ternary neural networks the tradeoff between accuracy and performance costs (shown Table 3). We use three different architectures for each of the two datasets, which have been used in existing work. m1-3 the CIFARIO dataset. See Table for the descriptions of model architectures. We use the same scaling factors for our networks as used by Riazi et al. (2019), which is the only other comparable work with quantized (binary) weights and inputs, for a fair comparison.
used with the MNIST dataset, while m4-6 are used with
We observe that for MNIST datasets, the basic TNN SOTERIA models (ml-m3) provide improved runtime and communication performance on average than prior work with maximum drop in ac- curacy of only 0.0167 (for model m2). This shows that SOTERIA useful in designing custom
5

---

Under review as a conference paper at ICLR 2022
models that provide optimal performance guarantees while retaining high prediction accuracy. For CIFARIO datasets, we observe that for models used in prior work (m4 to m6), our basic TNN mod- els exhibit slightly higher drop in accuracy of 0.8, but provide computation and communication gain, on average, as compared to prior work. Overall, our results show that SOTERIA provides a flexible approach of training private models given the constraint on performance and accuracy of the model.
Table 3: Performance analysis of existing secure schemes for private neural network inference. We compare SOTERIA constructed on fixed model architectures with ternary parameters, as well as optimal architectures constructed by SOTERIA, with the prior work. We provide the descriptions of the model architectures in Table We use the same scaling factor for SOTERIA and XONN for fixed model architectures (1.75 for m1, 4.0 for m2, 2.0 for m3, 2.0 for m4, 3.0 for m5, 2.0 for m6), and use 3.0 for MNIST (SOTERia) and CIFARIO (SOTERIA) for the models constructed by our architecture search algorithm.
Model
Secure Scheme
Runtime
Communication (MB) Test Accuracy
Ofline
Online
Total
SecureML Mohassel Zhang (2017)
4.7
0.18
4.88
0,931
MiniONN Liu et al. (2017)
0.9
0.14
1.04
15.8
0.976
MNIST (ml)
ExPC Chandran et al. (2019)
0.7
76
0.976
Gazelle Juvekar et al. (2018)
0
0.03
0.03
0.5
0.976
XONN Riazi et al. (2019)
0
1.29
0.976'
(0.9591)
SOTERIA (TNN)
0.04
0.03
0.07
3.72
0,9642
DeepSecure Rouhani et al. (2018)
7.89
1.98
9.67
791
0,9895
MiniONN
0.88
0.1
1:28
17.6
0,9895
ExPC
0.6
70
0,990
MNIST (m2)
Gazelle
0.15
0.05
0.20
8.0
0.990
XONN
0
38. 28
0,98664
(0.9718)
SOTERIA (TNN)
0.08
0.06
0.14
30.68
0,9733
MiniONN
3.58
5.74
9.32
657.5
0,990
E2PC
5.1
501
0,990
MNIST (m3)
Gazelle
0.48
0.33
0.81
70
0,990
XONN
0.15
32.13
0,990
(0.9672)
SOTERIA (TNN)
0.08
0.07
0.15
26.01
0.9740
MNIST (SOTERIA)
SOTERIA (A
0.09
0.08
0.17
36.24
0,9883
SOTERIA (A 0)
0.016
0.018
0.034
95.18
0.9811
CIFAR 10 (m4)
XONN
15.07
4980
0.80
(0.7197)
SCIERIA (TNN)
8.58
14.70
936.1
0.7314
MiniONN
472
511
9272
0.8161
ExPC
205.6
40683
0.8161
CIFAR (m5)
Gazelle
Delphi
9.34
3.56
12.9
1236
200
0,8161
XONN
5.79*
2509
0,8185
(0. (0.7266)
SOTERIA (TNN)
461.3
0,7252
XONN
16.09
5320
0.83*
(0.7341)
CIFARIO (mm)
SOTERIA (TNN)
9.01
6.63
15.64
982.7
0.7396
SOTERIA
3.69
6.95
497.6
0.7384
CIFARIO (SOTERIA)
SOTERIA (A 0)
4.01
3.53
7.54
561.2
0.721
"We could not reproduce the test accuracies for XONN. We report results that we obtained on the same model architos-
tures with the on a high perfornance Intel processor, which faster than the one used by all other methods. "Breakdown of runlime cost into offline and online runtime is not reported by the authors. 'Comminication cost not reported by the authors. "The runtime. commonication cost and test accuracy are estimates from the graphs reported by the authors.
setting in the respective paper in parenthesis. "XONN's runtime reported by the authors measured
3.3 RESULTS WITH SOTERIA
We now discuss the details of our empirical analysis of SOTERIA. In particular, we will present the cost function we used in the architecture search algorithm, the effect of the performance regulariza- tion during the search, the effect of the model size on the tradeoff between accuracy and inference runtime, and compare SOTERIA with the prior work.
Cost function for regularized architecture search. Our algorithm searches for models that are not only accurate but are efficient with respect to the costs of using garbled circuits for computing the operations involved during inference time for a model. For this, we modify the score value generated by the generie architecture search algorithm Liu et al. (2019) gives each operation (e.g., maxpool, or convolution with different dimensions) with a regularized penalty factor proportional to the performance cost of the operation. Table 4a presents the communication and runtime cost of

---

Under review as a conference paper at ICLR 2022
(a) Runtime and communication cost per operation.
Runtime (ms)
Comm. (KB)
Pemalty factor
Operation
CONV5
55.40
7942
1.00
CONV3
23.10
3190
0.41
MAXPOOL2 x
3.23
145
0.04
IDENTITY
0.00
(b) Number of parameters, sparsity and test accuracy.
Total Parameters
No. 0-weights
Spansity
Accuracy
1.0
133, 032
41,
0.31
0.8892
729,
540
0.9721
0.6
2. 904, 168
1, 080, 217
0.37
0.9883
2. 999001,11 168
080, 217
0.9883
0.2
941,032
895, 033
0.30
0.9887
0.0
11, 466, 600
5, 116,,0000 030
0.45
0.9811
Table 4: (a) Runtime and communication cost each operation based on their garbled circuit infer- ence. We also calculate the performance penalty factor (which use in regularized architecture search algorithm) as the average of the relative costs for each unit w.r. the most expensive operation. (b) Number of parameters and corresponding sparsity and test accuracy with different levels of for SOTERIA architecture search over MNIST dataset with I cell architecture having sequential operations. The setting is the same the one illustrated in Figure 2(b). The scaling factor 3. For larger X, the algorithm penalizes large/complex models.
0.8
0.0
0.8g
0.2
0.4
accuracy
0.95
Text accuracy
0.1
0.8
0.9
1.0
0.85
0.2
0.3
0.4
3
5
Inference runtime (8)
Inference runtime (8)
MNIST
(b) CIFARIO
Figure 2: Inference runtime versus test accuracy of garbled ternary model, constructed with So- TERIA architecture search algorithm, for various values of circuit cost regularization We obtain the architecture for neural network with (a) cell for MNIST dataset, and (b) 3 cells for CIFARIO dataset. Scaling factor is 3.
each operation that we use in our algorithm. The penalty factor is computed the average of the relative communication cost and relative runtime cost of each operation, with respect to the most costly operation (CONV5 5). We this penalty factor the experiments.
Balancing accuracy and inference costs. For the architecture search in SOTERIA, we balance accuracy and inference cost over GC protocol, using regularization factor A. With À the importance of the penalty factor is maximum, and X = represents the case where we ignore the performance cost. We execute the search process with different values of À. Figure 2 presents trade- off between test accuracy of the optimal architectures and their inference runtime. Table 4b provides the statistics on the number of model parameters and the model sparsity for different values of À for the MNIST dataset. As À increases, cheaper operations, that have fewer trainable parameters chosen by the search process, which improves the inference runtime at the expense of the model accuracy. As observe, À 0.6 provides reasonable balance between both accuracy and the inference cost. The search algorithm identifies cheaper operations that collectively result in accuracy equivalent to using expensive operations. It is important to note that selecting À depends how

---

Under review as a conference paper at ICLR 2022
Accuracy Runtime
0.8
Inference ronkime (5)
0.6
Test
0.4
0.2
0
Model depth (number of
Figure 3: Impact of the model's depth (as the number of cells in the SOTERIA architecture search) on accuracy and inference runtime of garbled model on CIFARIO. Regularization term À is 0.6. Scaling factor is 3.
much cost accuracy drop tolerate for given setting. Thus, SOTERIA enables adapting private inference to the specific requirements and limitations a system.
Finding the optimal depth for the model (number of cells). The number of cells that the final architecture has is a manually-set hyperparameter and defines the depth of the model architecture. We perform an experiment on the CIFARIO dataset, using cells with operations in sequence and 0.6. We run the search process for 100 epochs, and train each resultant architecture for 200 epochs. Figure 3 presents the results of executing the search with different number of cells. illustrates the model accuracies along with their inference runtime. We observe that for single cell architecture, the accuracy levels are low, as the network could not process the features required to perform generalizable classification. The test accuracy peaks for 3-cell architecture, suggesting that it has enough operations to process the required features of the inputs. parallel, we can see that the number of cells increases, the runtime also increases.
Comparison with prior work. Table 3 shows all the evaluated configurations in the prior work. reports the results for SOTERIA trained models that are optimized for both accuracy and efficiency. For the MNIST dataset, we observe that our model with À = gives the best model as compared to prior work while balancing the runtime performance (0.034) and accuracy of 0.9811. Increasing = 0.6 increases the accuracy by small value. Similarly, for CIFAR10 10 datasets, we observe that a SOraRIA-trained model with À= 0.6 gives better accuracy than most of the prior work compared to the numbers reported in brackets. Our evaluation on MNIST and CIFAR 10 datasets confirm that SOTERIA is effective in training models that are customized perform well for performance and accuracy by providing a set of options that trades-off these metrics in a user-configurable way.
RELATED WORK
Several prior work targets the problem techniques for secure machine learning, or build up on exist- ing techniques by trying to optimize bottlenecks.
Homomorphic Encryption. In CryptoNets Dowlin et al. (2016)Xie et al. (2014), the authors mod- ify the neural network operation by using square function as an activation and average pool instead of maxpool to reduce the non-linear functions to low degree polynomial to control the noise. Similar approaches of using homomorphic encryption on data and optimizing the machine learning opera- tions to limit the noise have been explored extensively Bourse et al. (2017); Graepel et al. (2012); Bost et (2014). Hesamifard et al. Hesamifard et al. (2017b) explore using homomorphic en- crypted data for training the neural networks. CryptoDL Hesamifard et al. (2017a) explores various activation functions with low polynomial degree that can work well with homomorphic encrypted data and proposed activation using the derivative of ReLU function. However, using homomor- phic encryption adds to an additional computational overhead and most of the non-linear activations cannot be effectively computed which results in degradation of the deep learning systems.
Secure Multiparty Computation. Secure multiparty computation requires a very low computation overhead but requires extensive communication between the parties. It has been used for several
8

---

Under review as a conference paper at ICLR 2022
machine learning operations. DeepSecure Rouhani et al. (2018) only uses GC to compute all the op- erations in the neural network. They rely on pre-processing of the data by reducing the dimensions to improve the performance and is implemented on the TinyGarble Songhori et al. (2015) library. Chameleon Riazi et al. (2018) uses a combination of arithmetic sharing, garbled circuit and boolean sharing compute the neural networks for secure inference. They rely on third party server to perform computation in the offline phase resulting in better performance than the previous work. XONN Riazi et al. (2019) leverages Binary Neural Networks with GC. Binarization dramatically re- duces the inference latency for the network compared to other frameworks that utilize full- full-precision weights and inputs, as converts matrix multiplications into simple
They use TinyGarble library as well to implement the Boolean circuits for GC. Prio Corrigan-Gibbs. & Boneh (2017) uses a secret sharing Shamir (1979) based protocol to compute aggregate statistics over private data from multiple sources. They deploy secret-shared non-interactive zero-knowledge proof mechanism to verify whether data sent by clients is well-formed, and then decode summed encodings of clients' data to generate aggregate statistic. They extend the application of Prio to foundational machine learning techniques such as least squares regression.
Hybrid Schemes. A judicious combination of homomorphic encryption and multiparty computa- tion protocol have shown to give some additional benefits in terms of runtime and communication costs. Gazelle Juvekar et al. (2018) uses lattice based Packed Additive homomorphic encryption to compute dot product and convolution but relies on garbled circuits for implementing non-linear operations like Maxpool and ReLU. They reduce the overall bandwidth by packing ciphertexts and re-eneryption to refresh the noise budget. Delphi Mishra et al. (2020) builds upon this work and uses Architecture Search to select optimal replacement positions for expensive ReLU activation function with a quadratic approximation with minimal loss in accuracy. MiniONN Liu et al. (2017) pre-computes multiplication triplets using homomorphic encryption for GMW protocol followed by SPDZ Damgard et al. (2011; I; 2012) protocol. The multiplication triplets are exchanged securely using additive homomorphic encryption like Paillier or DGK. SecureML Mohassel & Zhang (2017) uses garbled circuits and additive homomorphic encryption to speed up some NN operations. How- ever, the conversion costs between of homomorphic encryption and Yao's garbled circuits is expen- sive and the performance of homomorphic encryption scales poorly with increasing security param- eter Demmler et al. (2015). Hence, we rely on only garbled circuit protocol to efficiently compute neural network operations during inference with low communication bandwidth, low computation complexity and low memory footprint using binary neural networks while maintaining the accuracy. Most of the previous work have relied heavily on optimizing the complex cryptographic operations to work well with the neural networks. We show that it is possible to optimize the neural network to get an efficient privacy preserving neural network architectures.
Trusted Computing, Some research uses trusted processors where they assume that the under- lying hardware is trustworthy and outsource all the machine learning computations to the trusted hardware. Chiron Hunt et al. (201 8a) is a training system for privacy-preserving machine learn- ing as a service which conceals the training data from the operator. It uses Intel Software Guard Extensions (SGX) and runs the standard ML training in an enclave and confines it in Ryoan sand- box Hunt et al. (2018b) to prevent it from leaking the training data outside the enclave. Ohrimenko et al. Ohrimenko et al. (2016) propose a solution for secure multiparty ML by using trusted Intel SGX-enabled processors and used oblivious protocols between client and server where the input and outputs are blinded. However, the memory of enclaves is limited and it is difficult process memory and computationally intensive operations like matrix multiplication in the enclaves with paralellism. To address this, Slalom Tramèr & Bonch (2018) provides a methodology to outsource the matrix multiplication to a faster untrusted processor and verify the computation.
5 CONCLUSIONS
We introduce SOTERIA, a system that takes advantage of the power of neural architecture search algorithms in order to design model architectures which jointly optimize accuracy and efficiency for private inference. We construct optimal architectures that enables balancing accuracy and inference efficiency on garbled circuits. As opposed to the prior work that build cryptographic schemes around given fixed models, SOTERIA provides a flexible solution that can be adapted to the accuracy and performance requirements of any given system, and enables trading off between requirements.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Pytorch 1.3. https:/ppytorch.org/
Synopsys design compiler, version L-2016.03-SPS--. hagigpofffit-yyymmeeii--ssdddd-s
http://www.yyypppy.cccc//mmmmmmn
Donald Beaver. Efficient multiparty protocols using circuit randomization. In Joan Feigenbaum (ed.), Advances in Cryptology CRYPTO '91, pp. 420-432, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg.
Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. Machine learning classification encrypted data. Cryptology ePrint Archive, Report 2014/331, 2014. fttps://epriigg iacr.
Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. Fast homomorphic evalu- ation of deep discretized neural networks. Cryptology ePrint Archive, Report 2017/1114 14, 2017.
iacr. ortp//17/////11
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. Fully homomorphic encryytooicceecryptioo without bootstrapping. Cryptology ePrint Archive, Report 1/277 2011. https: http://eppiitni........ oxg/2011/277.
Nishanth Chandran, Divya Gupta, Aseem Rastogi, Rahul Sharma, and Shardul Tripathi. EzPC: Programmable, efficient, and scalable secure two-party computation for machine learning. In IEEE European Symposium on Security and Privacy, February 2019.
Henry Corrigan-Gibbs and Dan Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX Symposium on Networked Systems Design and Im- plementation (NSDI 17), pp. 259-282, Boston, MA. March 2017. USENIX Association. ISBN 978-1-931971-37-9. URL. https: /ttp:://wwwwwwe. hwwp///www...x...///////../..xit wrg/ //////oofeeee//////ee feonneeeeee///nii11 iibs.
techn ca sesssssssssee sereallsssssssss/seeeeeeees httpa//si//seeeeeeettttoo//rrrre
I. Damgard, V. Pastro, N.P. Smart, and S. Zakarias. Multiparty computation from somewhat homo- morphic encryption. Cryptology ePrint Archive, Report 201 1/535, 2011. https: //eprint.
iacr.org/201. 0.ccoo2g/2011/535,
Ivan Damgard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart. Practical covertly secure mpc for dishonest majority or: Breaking the spdz limits. Cryptology ePrint Archive, Report 2012/642, 2012. https: eeprittnn..... iacr. wwtp/////22....../ 642.
Daniel Demmler, Thomas Schneider, and Michael Zohner. ABY A framework for efficient mixed-protocol secure two-party computation. In 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, Califormia, USA, February 8-11, 2015. The Internet Society, 2015. URL pestps:/wwaa wdwwwwndss-eee http://www.dddsyppssssssss www-ssssmsssssmmmammmmmssssssuut aby- framework www.eeewwro--ffiieeeeeee efficient monntt-mxxede
wwwpww-part--oooo peeerre-ttoopptttyy-oottttaaatt computation secure propiiooooooieeeeeprooooooool protocol
Nathan Dowlin, Ran Gilad- Bachrach, 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 International Conference Machine Learning Volume 48, ICML'16 16, pp. 201-210. JMLR.org, 2016.
Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In George Robert Blakley and David Chaum (eds.), Advances in Cryptology, pp. 10-18, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg. ISBN 978-3-540-39568-3.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: survey, 2018.
Craig Gentry. A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford, CA, USA, 2009a. AA13382729, Advisor: D. Bonch.
Craig Gentry. Fully homomorphic encryption using ideal lattices. Proceedings the Forty-First Annual ACM Symposium on Theory of Computing. STOC '09, pp. 169-178. New York. NY, USA, 2009b. Association for Computing Machinery. ISBN 1781605555062. doi: 10.1145/1536414
1536440. URL https::tp/..o.......m pettts::/doe
10

---

Under review as a conference paper at ICLR 2022
Zahra Ghodsi, Akshaj Veldanda, Brandon Reagen, and Siddharth Garg. Cryptonas: Private inference on a relu budget. arXiv preprint arXiv:2006.08733, 2020.
O. Goldreich, Micali, and A. Wigderson. How to Play ANY Mental Game. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pp. 218-229, New York, NY, USA, 1987. ACM. ISBN 0-89791-221-7. doi: 10.1145/28395.284200
Thore Graepel, Kristin Lauter, and Michael Naehrig. MI. Confidential: Machine learning en- crypted data. Cryptology ePrint Archive, Report 2012/323, 2012. https://eppr iacr.
org/2012/322
Ehsan Hesamifard, Hassan Takabi, and Mehdi Ghasemi. CryptoDL: Deep neural networks over encrypted data, 2017a.
Ehsan Hesamifard, Hassan Takabi, Mehdi Ghasemi, and Catherine Jones. Privacy-preserving machine learning in cloud. In Proceedings of the 2017 on Cloud Computing Security Work- shop, CCSW 17, pp. 39-48 43, New York, NY, USA, 2017b. Association for Computing Machin- ery. ISBN 9781 478145035,048, doi: 10.1145/3140649, 3140655. URL https: //doi.//oi... org/10.
1145/314 00155/31064335 9044440449........ 3140655.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Binarized neural networks. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 4107-4115. Curran Associates, Inc., 2016.
Tyler Hunt, Congzheng Song, Reza Shokri, Vitaly Shmatikov, and Emmett Witchel. Chiron: Privacy-presente machine learning as a service. arXiv preprint arXiv: arXiv:/803.0500 1803.5961, 2018a.
Tyler Hunt, Zhiting Zhu, Yuanzhong Xu, Simon Peter, and Emmett Witchel. Ryoan: A distributed sandbox for untrusted computation on secret data. ACM Trans. Comput. Syst., 35(4), Decem- ber 2018b. ISSN 0734-2071. doi: 10. 10.1145/3231594, URL httpp:://pc......... orr.//oooooooooooooooooooo 10 1145/ 3231594.
Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In Proceedings of the 27th USENIX Con- ference on Security Symposium, SEC' 18, pp. 1651-1668, Berkeley, CA, USA, 2018. USENIX Association. ISBN 978-1-931971-466
Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free xor gates and appli- cations. In International Colloquium on Automata, Languages, and Programming, pp. 486-498. Springer, 2008
Fengfu Li, Bo Zhang, and Bin Liu. Teraryy weight networks. arXiv preprint arXiv:1605.047/1 2016.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019. https:/ //pprr//eee//eeeeeeeee/eee/
net/ pot/ffor htt///ooumm/co iid
S1EXHoC5FX. -1e
Jian Liu, Mika Juuti, Yao Lu, and N. Asokan. Oblivious neural network predictions via MiniONN transformations. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Com- munications Security, CCS 177 pp. 619-631, New York, NY, USA, 2017. ACM. ISBN 978-1- 4503-4946-8, doi: 10.1145/53 (1155/11335565 33356333356630
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. Cryptology ePrint Archive, Report 2020/050, 2020. https: /tts:s//pprrttt//e iacr. org/ 2020/050.
P. Mohassel and Y. Zhang. SecureML: A system for scalable srivacy-preservin machine learning. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 19-38, May 2017. doi: 10.1 109/SP. 2017.12.
11

---

Under review as a conference paper at ICLR 2022
Olga Ohrimenko, Felix Schuster, Cédric Fournet, Aastha Mehta, Sebastian Nowozin, Kapil Vaswani, and Manuel Costa. Oblivious multi-party machine learning on trusted processors. In USENIX Security Symposium, 2016.
Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Jacques Stern (ed.), Advances in Cryptology EUROCRYPT '99, pp. 221-222--3 238, Berlin, Heidelherg, 1999.
Springer Berlin Heidelberg. ISBN 978-3-540-48910-3,
Hieu Pham, Melody Guan, Barret Zoph. Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4095-4104 Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Michael O. Rabin. How to exchange secrets with oblivious transfer. Technical Report TR-81, Aiken Computation Lab, Harvard University, 1981.
M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schnei- der, and Farinaz Koushanfar. Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications. In Proceedings of the 2018 on Asia Conference on Computer and Com- munications Security, ASIACCS 18. pp. 707-721, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5576-6 doi: 10.1145/319944443199622
M. Sadegh Riazi, Mohammad Samragh, Hao Chen, Kim Laine, Kristin Lauter, and Farinaz Koushanfar. XONN; XNOR-based oblivious deep neural network inference. In 28th USENIX Security Symposium (USENIX Security 19), pp. 1501-1518, Santa Clara, CA, August 2019.
USENIX Association. ISBN 978-1-939133-04-5
B. D. Rouhani, M. S. Riazi, and F. Koushanfar. DeepSecure: Scalable provably-secure deep learn- ing. In 2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC), June 2018. doi: 10.1109/DAC.201 84655994
Adi Shamir. How to share a secret. Commun. ACM, 22(11):61--633, Nov 1979, ISSN 0001-0782. doi: 10.1 24.115//59168.3597768
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. In Security and Privacy (SP), 2017 IEEE Symposium on, 2017.
E. M. Songhori, S. U. Hussain, A. Sadeghi, T. Schneider, and F. Koushanfar. TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits. In 2015 IEEE Symposium on Security and Privacy, pp. 41 4-428, May 2015. doi: 10. 10.10099P.2.15..2..
Florian Tramér, Fan Zhang, Ari Juels, Michael K Reiter, and Thomas Ristenpart. Stealing machine learning models via prediction APIs. In USENIX Security, 2016.
Florian Tramèr and Dan Boneh. Slalom: Fast, verifiable and private execution of neural networks in trusted hardware, 2018.
Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic en- cryption over the integers. In Henri Gilbert (ed.), Advances in Cryptology EUROCRYPT 2010, pp. 24 43, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. ISBN 978-9-642-13190-5.
Pengtao Xie, Misha Bilenko, Tom Finley, Ran Gilad-Bachrach, Kristin E. Lauter, and Michael Nachrig. Crypto-Nets: Neural networks over encrypted data. CORR, abs/1412.6181,
2014. URL http:// /dblp..p..o///// uni-trier de/ db/ abtjoornalss////ooocoo/caaaaalss corr/corr1412 html# XieBFGLN14.
Andrew C. Yao. Protocols for secure computations. In Proceedings of the 23rd Annual Sympo- sium on Foundations of Computer Science, SECS '82, pp. 160-164, USA, 1982. IEEE Computer Society.
Andrew C. Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (SCFS 1986), pp. 162-167, Oct 1986. doi: 10. F1109/FFCS.196..25
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. CoRR, 1.0/161 2016. URL http: org/ 01177..1.01158.
12

---

Under review as a conference paper at ICLR 2022
A SELECTING THE CRYPTOGRAPHIC PRIMITIVE
In designing SOTERIA, we make several design choices with the goal of achieving efficiency, The most important among them is the selection of the underlying cryptographic primitive ensure pri- vacy of data. Several cryptographic primitives such as partially homomorphic encryption schemes (PHE) and fully homomorphic encryption schemes (FHE), Goldreich-Mican -eieeli-iiigrsoonn protocol (GMW), arithmetic secret sharing (SS), and Yao's garbled circuit (GC) have been proposed to en- able two-party secure computation. Each of these primitives perform differently with respect to the factors such as efficiency, functionality, required resources and so on. Partially homomorphic encryption schemes allow either addition or multiplication operations but not both on encrypted data Paillier (1999); ElGamal (1985). In contrast, fully homomorphic encryption schemes schemes enable both addition and multiplication on encrypted data Gentry (2009b:a); van Dijk et al. (2010); Brakerski et al. (2011) 1) but ineur huge performance overhead. Secret sharing involves distributing the secret shares among non-trusting parties such that any operation can be computed on encrypted data without revealing the individual inputs of each party Beaver (1992). GMW Goldreich et al. (1987) and GC Yao (1982) allow designing boolean circuits and evaluating them between a client and a server. The differences between these schemes might make difficult decide which primitive is system for a particular application. Therefore, we first
the best fit for designing a outline the desirable properties specifically for private neural network inference and then compare these primitives with respect to these properties (see Table 5). We select a cryptographic scheme that satisfies all the following desired properties.
Expressiveness. This property ensures that the cryptographic primitive supports encrypted compu- tation for a variety of operations. With the goal to enable private computation for neural networks, examine the type of computations required in deep learning algorithms. Neural network algo- rithms are composed of linear and non- non-linear operations. Linear operations include computation required in the execution of culny-connected and convolution layers. Non-linear operations include activation functions such as Tanh, Sigmoid and ReLUU. The research in deep learning is at its peak with a plethora of new models being proposed by the community to improve the accuracy of vari- ous tasks. Hence, we desire that the underlying primitive should be expressive with respect to any new operations used in the future as well. PHE schemes offer limited operations (either addition or multiplication) on encrypted data. This limits their usage in applications that demand expressive functionalities such as neural network algorithms. Alternative approaches such as FHE, SS, GMW and GC protocols allow arbitrary operations.
Computation Efficiency. Efficiency is one of the key factors while designing client-server appli- cation such as a neural network inference service on the cloud. FHE techniques have shown to incur orders of magnitude overhead for computation of higher-degree polynmials or non-lineat functions. Existing approaches using FHE schemes have restricted its use to compute only linear functions. However, most of the neural network architectures such as CNNs have each linear layer followed by non-linear layer. To handle non- non-linear operations, previous solutions either approximate them to linear functions or switch to cryptographic primitives that support non-linearlity Dowlin et al. (2016); Mohassel & Zhang (2017); Juvekar et al. (2018); Mishra et al. (2020). Approximation of non-linear functions such as ReLU highly impacts the accuracy of the model. Switching between schemes introduces additional computation cost which is directly proportional to the network size. In comparison to FHE, research has shown that SS, GMW and GC schemes provide constructions with reasonable computation overhead for both linear and non-linear operations.
Communication Overhead. The communication costs incurred for private computation contribute to the decision of selecting our cryptographic primitive, as the network should not become bottle- neck in the execution of the private machine learning as a service. We expect the client and server to interact only once during the setup phase and at the end of the execution to receive the output. We aim to remain backward compatible to the existing cloud service setting where the client does not need to be online at all time between the request and response. In contradiction to this property, the GMW scheme requires communication rounds proportional to the depth of the circuit. To evaluate every layer with an AND gate, the client and server have to exchange secrets among them forcing the client to be online throughout the execution. Similarly, construction of non-linear bitwise functions with arithmetic secret shares require communication rounds logarithmic to the number of bits in the input. This makes the use of these schemes almost infeasible in the cloud setting that have a high-
13

---

Under review as a conference paper at ICLR 2022
PHE
FHE
SS
GMW
GC
Expressiveness
Efficiency
V
V
V
Communication
(One time setup)
X
X
Table 5: Properties of secure computation cryptographic primitives: Partially and fully homomor- phic encryption schemes (PHE, FHE), Goldreich-Micall Micali-Widgerson protocol (GMW), arithmetic secret sharing (SS), and Yao's garbled circuit (GC).
latency network. Unlike these primitives, Yao's garbled circuits combined with recent optimizations require an exchange data only once at the beginning of the protocol.
We select Garbled Circuits our underlying cryptographic primitive in SOTERIA as it satisfies all the desired properties for a designing private inference for cloud service applications.
B GARBLED CIRCUIT FOR EFFICIENT NEURAL-NETWORD
We investigate the problem of performing private inference on neural networks. Let W be the model parameters stored on the server, x be the client's input, y be the expected output and f the inference function to be computed. Given this, we want to compute (a; 0) -
Goals, We aim for the following main goals:
Confidentiality: The solution should preserve confidentiality of the model parameters from the users and that of and from the server. We assume an conest-but-curion threat model.
Accuracy:
The drop in accuracy the privately computed inference function should be negligible as compared to the accuracy of the model on plaintext data.
Performance: The private computation should demonstrate acceptable performance (run- time and communication) overhead.
Garbled circuits. GC protocol allows construction any function as a boolean circuit with a one time setup cost of data exchange Yao (1986). In our setting, the client is the garbler and the server is the evaluator. In the setup phase, the client first transforms the function into a boolean circuit with two-input gates. The function (model architecture) and the circuit are known to both the parties, but its parameters and input are private. The client then garbles the circuit. This process involves creating garbled computation table (GCT), which is encrypted version of the truth table for the boolean circuit. The entries for this table are randomly permuted, so that the order does not leak information. The client then shares the garbled circuit and its encrypted inputs the circuit (binary values representing x) with the server. In the next phase, the parties perform an oblivious transfer (OT) protocol Rabin (1981), values representing W), without leaking information about its parameters to the client. Then, the server evaluates the circuit, and obtains the output value which encrypted. The server transfers the output to the client which can match the encrypted values to their plaintext and obtain f(x; #).
the server obtains the encryption of its inputs to the circuit (binary
Performance. In GC, the communication and computation overhead is directly dependent on the number of AND, OR gates in the boolean circuit. Prior research has proposed several techniques that make free for the GC to execute XOR, XNOR and NOT gates Kolesnikov & Schneider (2008). Given this prior work, the communication overhead of the GC protocol for given circuit proportional to its security parameter and the number of non-XOR gates the circuit. The total runtime for evaluating circuit is the sum of the time required during the online (evaluation) and offline (garbling and oblivious transfer) computation.
Efficient neural networks. In SOTERIA, leverage the above-mentionel properties of GC to design an optimized neural network algorithm. Neural network algorithms are shown to be flexi- ble with respect to their architectures i.e., multiple models with different configuration achieve
14

---

Under review as a conference paper at ICLR 2022
similar level of accuracy. We take advantage of this observation and propose designing neural network architectures that help optimize the performance executing inference with garbled cir- cuits. The number of gates in circuit corresponding neural network depends its activation functions and the size of its parameter vector.
Neural networks have shown to exhibit relatively high accuracy for various tasks with low precision parameters. Binary neural networks Hubara et al. (2016) are designed with the lowest possible size for each parameter, i.e., one bit represent [-1,+1} values. Using BNNs naturally aligns with our selected cryptographic primitive because each wire in garbled circuits represents bit value (representing 1 in the model with in the circuit). Binarizing the model parameters further allows us to heavily use the free XOR, XNOR and NOT gates in garbled circuits, thus minimizing the computation and communication overhead of private inference. This has recently been shown in the performance evaluation of garbled circuits on binary neural networks Riazi et al. (2019).
In neural networks, linear functions such as those used in the convolutional fully connected layers form important part of the network. These functions involve dot product vector multiplica- tions. Instead of using multiplications, this can be computed very efficiently using XNOR poppoott: w = 2 x bitcount(xnor(' w)) N. where N = |x|. In binary neural networks, the output of activation functions is also binary. But, the output of ANOR-popcount is not binary number, thus, according to BNN algorithms one would need to compare it with 0; positive numbers will be converted to and negative numbers will be converted to O.
non-linear functions such maxpool very efficiently in BNNs. Max- pooling is a simple operation which returns the maximum value from vector, which in the case of neural networks is usually one-dimensional representation of 2D max-pooling window. In binary neural networks, maxpool need to simply return 1 if there is 1 in the vector. This is achieved by logical OR-operation over the elements of the vector.
We can compute
To achieve learning capacity for binary neural networks similar to full-precision models, we would need scale up the the number of model parameters. We can increase the number of kernels in convolution layer and the number of nodes in a fully connected layer, by given scaling factor. This technique has been used in the prior work Riazi al. (2019), and enables learning more accurate models, however at the cost of increasing the number of computations in the network.
15

---

Under review as a conference paper at ICLR 2022
C SPECIFICATIONS OF THE MODEL ARCHITECTURES
Table 6: Model architectures used in our experiments. Models ml-6 are used in the prior work on MNIST and CIFARIO datasets, and constructed the SOTERTA models using regularized architecture search algorithm.
Kernels/ Nodes
Kernels/ Nodes
Kernels/
Kernels
Type
Type
Type
Type
Nodes
Nodes
MNIST (m1)
CIFARIO (m5)
CIFARIO (SOTERIA)
CIFARIO (SOTERIa)
128
CONV
O,
of
2
FC
128
2
CONV 3 x 3
16
No. of operations oell
No. of operations per cell
FC
CONV 3 x
16
CONV
CONV 3 x
MAXPOOL 2 x
MAXPOOL x
CONV 3
16
MNIST (m2)
5
CONV 3 3
32
3
CONV 5 x
16
CONV 3 x
16
5
CONV 3
32
CONV
MAXPOOL
2
FC
100
7
CONV 3 3
32
5 CONV 5
32
CONV 3 3
32
8
MAXPOOL
MAXPOOL
CONV x
32
9 CONV 3 3
48
CONV 5 x
CONV 3
32
MNIST (m3)
CONV 3 x
48
8 CONV 5 x
32
MAXPOOL 2
CONV 5
16
CONV 3
64
CONV x
CONV 3
61
2
2AXPOOL.2X4 x
12 MAXPOOI. 2
10 MAXPOOL 2 x
10 CONV 3 x
64
CONV
10
CONV x
3
4 MAXPOOL x
12 CONV 5
61
12 MAXPOOL
FC
100
CIFARIO (m6)
13 FC
10
13
FC
10
FC
I
CONV 3 3
16
2
CONV 3 3
32
MNIST (SOTERIA)
MNIST (SOTERIa)
CIFARIO (m4)
3
32
0, of cells 1.
0.6, No. of cells
CONV3 x
64
4
MAXPOOL 2
No. of operations cell
No. of operations cell =4
CONV x
CONV 3 3
48
CONV5 x
MAXPOOL
6
CONV 3 3
64
2
CONV x
CONV x
16
4
CONV 3 3
64
7
CONV 3 3
80
3
CONV 5 x
16
MAXPOOL
MAXPOOI.
CONV
6
MAXPOOL
9 CONV 3 3
96
5 FC
100
FC
100
CONV 3 3
64
CONV 3 3
96
FC
FC
10
CONV x
CONV 3
128
9 CONV x
16
12 MAXPOOL
16

---

Under review as a conference paper at ICLR 2022
D DETAILS FOR EXPERIMENTAL EVALUATION FOR PRIOR WORK
Table 7: Overview of the existing private inference methods, including the cryptographic schemes used, precision of neural networks supported, number of parties involved, evaluation setup configu- ration and availability of code.
Prior Work
Cryptographic Scheme
Model Precision
Parties
Performance Evaluation Setup
Code
CPU Mark (Siggle Threadj'
Relative CPU
Serven: Entel Core i5
MisiONN Liu al. (2017)
Additively HE GC
Pull
4 3.30 GHz cores Client: Intel 3.20 GHz cores
1,686-2,300
0.61-0.83
Available'
ExPC Chandran al. (2019)
GC, Addisive SS
Full
2 Innel Xeon 2673 v3 2,40GHz
1,723
0.62
Available"
DeepSecure Rouhani al. (2018)
fixedppoint
2
Intel Care 17-26000 3.400GH2
1,737
0.63
SecureML. Zhang (2017)
Lincar
AWS ct. Balarge ES-2666
2.90 (H+))
Additivel HE,
AWS o4 c4.xtange (litel Xeon ES-2066 vi
Cazelle Juvekar (2018)
Pull
Addirively HE, GC
AWS c5 55.2xlarge
Delphi Mishra al. (2020)
Full
(Intel Xoon 8000 series 3.0 GHz)
2,082
0.75
Available'
AWS 2slagee (Intel Xeon 8 124 3.0 GiIk
SOTERIA
GC
Temary
2
2,082
0.35
Available
Chameleon Riazi et (2018)
GMW, Additive SS
Full
3*
Intel Cure 17-4790
3.80GHz
2,266
0.82
17-7700K
(2019)
Binary
MiniONN: Ettpss/
conn/ wtwm/Sackaaoo/mnn..ooo
PxPC: he pa //gi hhub. con
mart /FaPC
Delphi: aat / /htbb.. githab.coo//ne con/mo2 2oo222-roojeee projeet//dee /delpp
SOTERIA: bctps:/ /ithub. con/ Sct.erssnnnnnnyoo
Chameloon only uses the third party pre processing stage.
listed with their the singl-threased CPU Mark processors variety from (loating point operations, string surting and diia compression (bttps:/ //t//////w /www. :pubencimark net cppu. test innfo-hmm)) to provide an estimate of the cipabilitiss of procesoor As microurchieecturl optinizations vary from processor processne, frequency alone cannor he used performance metric The absolute sooess and relative (compared the highest scoring CPU the table) for CPUs used evalutton reluted work repoited.
CPU mark: The con figuraations
reported by
epubenchnark
17


Reviews:
[{"review_id": "VW4rPLFVWpD", "reviewer": "Reviewer_TcBF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 main strength of the paper is its novelty, increasing the efficiency of cryptographic computations by neural architecture design is an interesting approach. \n\nThe main weakness is that the technical contribution is limited. It leverages the already existing techniques of neural architecture search and ternary networks to reduce the computation and communication overhead. There are also several points that could be clarified. For instance, it is not clear what is the cost of the architecture search process itself, in terms of the runtime. Is this included in the offline runtime in Table 3? Is the search repeated for different values of the regularization factor to find the best one (in terms of the trade-off between test accuracy and inference runtime), or is there a principled way for choosing the regularization factor to avoid this? If it is the former, this could be very costly, since the search should be repeated for various values assigned to the regularization parameter. \n", "summary_of_the_paper": "The paper aims at developing an efficient neural network architecture with reduced computational cost under a cryptographic primitive where data on the client side and model on the server side are kept confidential. The motivation is that the existing works have focused on developing cryptographic techniques in a fixed network architecture and have not considered the neural network optimization perspective to enhance the efficiency of existing cryptographic computations. The paper then leverages the flexibility of the network structure while ensuring comparable accuracy and tries to find an architecture that provides a significant reduction in runtime while incurring negligible impact on prediction accuracy. Garbled circuits are chosen as the cryptographic primitive due to its compatibility with a wide range of computations, including non-linear functions. The paper then investigates how to reduce the private inference cost by incorporating two protocols: first one is neural architecture search for efficient private inference where a neural operation is penalized based on its computation and communication overhead, and the second one is to train models with ternary parameters which allows reducing the number of model parameters by introducing sparsity. Sparsity leads to a reduction in computation and communication overhead. However, to maintain a certain level of accuracy, the network needs to be scaled which incurs an increase in the runtime. Accordingly, a trade-off between efficiency and accuracy has been demonstrated with experiments on the CIFAR and MNIST datasets for varying regularization parameter and scaling factor.", "summary_of_the_review": "Using neural architecture search to increase the efficiency of neural network architectures for private computing is a very interesting direction. Providing more insights on the cost of the search process and the optimization of the key parameters such as the regularization factor would help the reader better assess the benefits of neural architecture search in this context. ", "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": "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": "8Gm4fDhXGdR", "reviewer": "Reviewer_zXdE", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\nThe strength of the paper is the seemingly careful design that combines three elements (1) secure MPC protocol choice that reduces communication rounds, (2) restriction of weights to binary/ternary alphabet, and (2) compatabile neural architecture search to enable efficient private inference.  \n\nThe main drawback of the paper is the lack of clarity in the exposition that makes the paper overall difficult to evaluate. The costs and drawbacks of the restricted architectures/weights compared to - say, a baseline with no privacy - is also not reported.\n Specifically:\n- The neural architecture search is not explained rigorously via mathematics, only via words. This leaves the reader guessing as to what the authors are actually performing. Among many aspects where I am unclear, I am unable to understand how the cost functions change given that the architecture is now restricted to discrete set of weights and biases, as the overall training becomes a discrete optimization problem - so I expect the complexity of finding these neural networks and the weights to be enormous \n- How is the factor lambda used in the cost function for the architecture search. The precise specification of the role of this factor is missing.\n- It seems that the data set is utilized for both training the architecture, and then training the model. Intuitively, this must translate to more data being required as compared to training the model itself. The paper must describe this, and perhaps demonstrate any such effects through empirical results.\n- The restriction to ternary weights and binary activation seems to be a significant drawback, and one expects that these restrictions must lead to weaker accuracy for some settings (data sets, or predictions). The paper misses a detailed discussion and experimental comparison in this regard. \n\nIn addition, it appears that the technical contribution builds on prior works, and so the novelty is relatively limited\n", "summary_of_the_paper": "The paper develops a method for private neural-network-inference via utilization of Yao's garbled circuits (GC) protocol. In order to keep the computation complexity manageable - the main practical hurdle for  GC - the paper proposes utilization of a neural network architecture search, coupled with restricting weights to ternary alphabet and binary activation. The neural architecture search is conducted via a variation of the \"DARTS\" approach of Liu et. al (ICLR 2019), that accounts for model complexity in the cost function. The paper performs extensive experiments against comparable protocols in their evaluation for MNIST and CIFAR10, and show improvements along some factors.  ", "summary_of_the_review": "Overall, even if the idea behind the paper is promising, given the unconventional approach to technical description (only words, not a single equation), and the associated lack of clarity and rigor, I recommend rejecting the paper in the current form. \n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6A2bJwxPYBN", "reviewer": "Reviewer_rwM8", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros:\n1. The problem addressed in this paper is of practical importance for many real-world applications.\n2. The challenges and the proposed solutions are well motivated.\n3. The paper is also very well-written and has a nice flow.\n\nCons:\n\n1.\tThe experiment section reads: “Although SOTERIA could leverage any of the available cryptographic primitives or their combination, we select garbled circuits as its main building block to address the confidentiality concern. Garbled circuits (GC) are known to be efficient and allow the generation of constant depth circuits even for non-linear functions. We show that neural network algorithms can be optimized to efficiently execute garbled circuits while achieving high accuracy guarantees.” It is not clear why faster GC+HE (homomorphic encryption) protocol than the pure-GC protocol that is proved by Gazelle [Chiraag Juvekar+, USENIX Security 2018] is not used.\n2.\tMultiple typos: For example, in the abstract, “multi-arty” should be “multi-party”.\n3.\tThe main contribution of the paper is proposing a neural architecture search to automatically search for an optimal ternary neural network architecture. As such, the paper has a limited novelty from the ML perspective.\n4.\tThe proposed method has shown improved performance over a few recent algorithms. The paper, however, fails to compare with CrypoNAS [Zahra Ghodsi+, NeurIPS 2020], which I think is the SOTA for cryptographic secure inference. It is better to compare more related works. \n", "summary_of_the_paper": "This paper studies neural network designs for cryptographically secure inference. The paper uses the existing DARTS neural network architecture search algorithm to automatically a ternary neural network for secure inference based on garbled circuits. ", "summary_of_the_review": "--", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a new way of addressing the ML as a service problem through using garbled circuits. As the reviewers point out the novelty is limited and comparison to existing work is not complete. The authors have also not responded to the reviews.
Decision: Reject