Tabula: Efficiently Computing Nonlinear Activation Functions for Secure Neural Network Inference
Authors: Max Lam
Michael Mitzenmacher
Vijay Janapa Reddi
Gu-Yeon Wei
David Brooks
Venue: Accepted by TMLR ()

Abstract: Multiparty computation approaches to secure neural network inference commonly rely on garbled circuits for securely executing nonlinear activation functions. However, garbled circuits require excessive communication between server and client, impose significant storage overheads, and incur large runtime penalties; for example, securely evaluating ResNet-32 using standard approaches requires more than 300MB of communication, over 10s of runtime, and around 5 GB of preprocessing storage. To reduce these costs, we propose an alternative to garbled circuits: Tabula, an algorithm based on secure lookup tables. Our approach precomputes lookup tables during an offline phase that contains the result of all possible nonlinear function calls.  Because these tables incur exponential storage costs in the number of operands and the precision of the input values, we use quantization to reduce these storage costs to make this approach practical. This enables an online phase where securely computing the result of a nonlinear function requires just a single round of communication, with communication cost equal to twice the number of bits of the input to the nonlinear function. In practice our approach costs 2 bytes of communication per nonlinear function call in the online phase. Compared to garbled circuits with quantized inputs, when computing individual nonlinear functions during the online phase, experiments show Tabula uses between $280$-$560 \times$ less communication, is over $100\times$ faster, and uses a comparable amount of storage; compared against other state-of-the-art protocols Tabula achieves greater than $40\times$ communication reduction. This leads to significant performance gains over garbled circuits with quantized inputs during the online phase of secure inference of neural networks: Tabula reduces end-to-end inference communication by up to $9 \times$ and achieves an end-to-end inference speedup of up to $50 \times$, while imposing comparable storage and offline preprocessing costs.

Published in Transactions on Machine Learning Research (06/2024)
Tabula: Efficiently Computing Nonlinear Activation Functions for Secure Neural Network Inference
Maximilian Lam Horvard University
corilam@@ghhrrrrde edu
Michael Mitzenmacher
micchallm@eccs.arrvooo
Horvard University
Vijay Janapa Reddi Horvard University
sjBeecs.harvord.com edu
Gu- Yeon Wei Horvard University
gugeon edu
David Brooks Horvard University
Aanooks@ghharvord.cdd edu
Reviewed on OpenReview: https: /// openreview. net/ forum? id= CXPb4tusry
Abstract
Multiparty computation approaches to secure neural network inference commonly rely garbled circuits for securely executing nonlinear activation functions. However, garbled circuits require excessive communication between server and client, impose significant storage overheads, and incur large runtime penalties; for example, securely evaluating ResNet-32 using standard approaches requires more than 300MB of communication, over 10s of runtime, and around 5 GB of preprocessing storage. To reduce these costs, we propose an alternative to garbled circuits: TABULA, an algorithm based on secure lookup tables. Our approach precomputes lookup tables during an offline phase that contains the result of all possible nonlinear function calls. Because these tables incur exponential storage costs in the number of operands and the prccision of the input values, we use quantization to reduce these storage costs to make this approach practical. This enables an online phase where securely computing the result of a nonlinear function requires just a single round communication, with communication cost equal to twice the number of bits of the input to the nonlinear function. In practice our approach costs bytes of communication per nonlinear function call in the online phase. Compared to garbled circuits with 8-bit quantized inputs, when computing individual nonlinear functions during the online phase, experiments show TABULA with bit activations uses between 280-560x less communication, is over 100x faster, and uses a comparable (within a factor of 2) amount of storage; compared against other state- of-the-art protocols TABULA achieves greater than 40x communication reduction. This leads to significant performance gains over garbled circuits with quantized inputs during the online phase of secure inference of neural networks: TABULA reduces end-to-end inference communication by up to 9x and achieves end-to-end inference speedup of up to 50x, while imposing comparable storage and offline preprocessing costs.
1 Introduction
Secure neural network inference seeks allow a server to perform neural network inference on a client's inputs while minimizing the data leakage between the two parties. Coneretely, the server holds a neural

---

Published in Transactions on Machine Learning Research (06/2024)
Linear Functions
Preprocessing Phase
Online Phase
[z] = L[x]dd
[2]]
p-L(p-[x]/
Client
[T), [S]
dJ
Secure Table
Nonlinear
[2]++s}
[z]]+(s]
F Functions
z+s
(T],, [s]
Server
[F(2]]
[F(2)]
The TABULA approach to computing nonlinear functions for secure neural network inference. TABULA precomputes lookup tables [T]. [T]1 stored on client and server respectively, and also initializes shares of the secret s so that the client holds [s]o and the server holds [s]1. The lookup tables [T], contain the result of all possible nonlinear function calls an activation function and uses quantization to make storing all possible function calls in the table feasible. These lookup tables map secret shares of the quantized inputs to the nonlinear function to secret shares of the output of the activation function. During the online phase, these lookup tables enable extremely efficient nonlinear activation function exccution and procceds by 1) securely truncating the imputs, 2) reconstructing a blinded index and 3) looking up the blinded index in the lookup tables [T].. Our code is released at htcp:://ggttuu..cc//bbllliiaiii
Figure 1:
network model M while the client holds an input x. The objective of a secure inference protocol is for the client to compute (xx without revealing any additional information about the client's 's input x to the server, and without revealing any information about the server's model M to the client. protocol for secure neural network inference brings significant value both server and the clients. The clients' sensitive input data is kept secret from the server, shielding the user from malicious data collection. Additionally, the client does not learn anything about the server's model, which prevents the model from being stolen by competitors.
Current state-of-the-ard multiparty computation approaches to secure neural network inference require significant communication between client and server, lead to excessive runtime slowdowns, and incur large
storage penalties (Mishra et al. 2020a; Ghodsi et al. 2021 Jha et al. 2021 Rathee et al. 2020 Juvekar ct al. 2018 Cho et al.] 2021). The source of these expenses is computing nonlinear activation functions with garbled circuits (Yao] 1986). Garbled circuits are costly terms of computation, comnunication, and storage. Concretely, executing ReLU activation functions using garbled circuits requires over KB of communication per scalar element of the input (Mishra et al. 2020a) and imposes
17 KB of preprocessing storage per scalar element of the input (Mishra et al. 2020a Ghodsi et al. 2021 These costs make tiiee---f-hhh-arrt neural network models prohibitively expensive to deploy: ResNet-32, state-of-the-art multiparty computation approaches for single secure inference require more than 300 MB of data communication (Mishra et al. 2020a), take more than 10 seconds for an individual inference (Mishra et al. 2020a), and impose over 5 GB of preprocessing storage per inference (Ghodsi al. 202T). These communication, runtime, and storage costs pose a significant barrier deployment, as they degrade user experience, drain clients' batterios, induce high network expenses, and eliminate applications that require sustained real time inference.
To replace garbled circuits and other methods [Rathee al. 2020 Huang et al. 2022 for privately computing nonlinear functions, we propose TABULA, a two-party secure protocol to efficiently evaluate neural network nonlinear activation functions. During an oflline preprocessing phase, TABULA generales tables that contain the encrypted result of evaluating a nonlinear activation function over a range all possible quantized inputs. New tables are precomputed for each noulinear function performed during inference, and these tables are split across client and server. Then, at inference time, TABULA performs two steps to evaluate a nonlinear activation function: 1) securely quantize neural network activation inputs down to the precision of the range
2

---

Published in Transactions on Machine Learning Research (06/2024)
of the imputs to the precomputed tables and 2) securely lookup the result of the activation function using
two-party secure table lookup procedure (Tshai et al. Keller et al. 2017 Damgard & Zakarias 2016 6 By
heavily quantizing neural network activations and reducing the space of inputs to the nonlinear activation function, TABULA enables storing all possible results the activation function in a table without requiring an infeasibly large amount of memory. This allows the application of the subsequent two-parly secure table lookup protocol, which is efficient and has low storage, communication, and computation overhead.
TABULA achieves significant improvements over garbled circuits and other (Rathee et al. 2020 Huang
et al. 2022) approaches for securely computing nonlinear functions important system metrics such communicttio and runtime, while maintaining or even improving storage costs.
Runtime
TABULA offers significant. runtime improvements over garbled circuits with quantized in- puts due to the simplicity of the online phase of the secure table lookup protocol (Keller et al. 2017 Ishai et al. Damgård Zakarias, 2016). TABULA's runtime for an individual activation function is the cost of transferring single secretly shared value between parties, and performing single memory access the subsequent value. Our results show that when computing individual functions, TABULA is over 100x faster than garbled circuits with quantized impuls. This leads to significant overall runtime improvements when performing secure neural network inference. Our results show that across various standard networks (LeNet, ResNet-32, ResNet-34, VGG) TABULA achieves up to x0x runtime speedup compared to garbled circuits with quantized inputs. Additionally, during the online phase, the TABULA protocol requires just one table lookup; this significantly less computation compared to schemes that use function secret sharing (FSS), which require computing
PRGs like AES-125 128 (Wagh 2022 Gupta et al. 2022 Agarwal ct al. 2022 Boyle et al. 2019 2020
Ryffel et al. 2021
Communication
TABULA requires significantly less communication than garbled circuits with quantized inputs and also significantly less communication versus other state-of-the-art approaches like (Rathee et al. 2020 TAbula'S communication cost. for a single activation function is the cost of communicating a single secretly shared element between parties, and is independent the complexity of the nonlinear function. Our experiments show that, compared required for single nonlinear function call is reduced by factor of over 280 560x leading to an overall communication reduction of up to 9x various standard neural networks. Additionally, compared to other state-of-the-art protocols for computing nonlinear functions like (Rathee et al. 2020), we show TABULA reduces communication by up to 40x on a per-operation basis, leading to up to 10x reduction in communication when performing end-to-end private inference on various neural networks.
garbled circuits with quantized inputs, communication
Storage and Memory
TabuLa utilizes comparable storage and memory as garbled circuits with quantized inputs. TABULA'S 's table sizes are dictated by how heavily quantized the activations are and increase exponentially with the precision of the activations. Notably, TABULA'S table sizes affect the precision of the activation function and hence affect neural network accuracy. However, as neural network activations may be significantly quantized without significantly affecting neural network quality (Ni et al.] 2020 de Bruin et al. |220 Zhao et al.) 2020 McKinstry et al. (2019), the sizes of these individual tables may be reduced enough to allow a comparable or smaller amount of storage than garbled circuits with quantized inputs. Generally, across different models, TABULA uses between .25 2x as much memory as garbled circuits while maintaining similar model quality. Like garbled circuits, TABULA requires new table for each individual nonlinear operation to maintain security.
A comparison of our work against others across some of these axes is shown in Table 1
3

---

Published in Transactions on Machine Learning Research (06/2024)
Comnn. (per-op)
Runtime Cost (per-op)
Preproc. Storage Clst (per-op)
Supported Nonlinear Operations
Mode of Operation
Ouline Pluse Computation
Works
2B (Aryy functtion, jusst in lookup table)
Secure Lookop Table
Tabulaa
Ours
.35
16KB
Any
1 RAM lookup
Delpai Mashra m..
Garbled
Gozelle
Unvokar
Creentt
SocureNN
Mooineed X Aibea
2017
56215
70 1e
17.5KI
Any
Yao I986
DeepReeuuee
Circa Glods vt
MV1
Treo-Besed
Orypt Flow2
Rulhen
ReLU only
Oblivious Tronder
Comparator
Cheetah
Hiing et
1122
Lo. 1997
Function
2122
Sharing
Secvit
(PSS)
Idmaa
Armuin Byllor
Agaroal
Guiple vi A1
A022
Boyle
(8-hit compare.
Boyle al. 2019
512H
Any
Boyle nl. 2019
Boyle
FSS
AES-128)
PRG
Table 1: Comparison of our work against other approaches for securely computing nonlinear activation functions across selected axes. Unless specified costs refer the cost of the online phase. Compared to garbled circuits, the most widely used state-of-the-art protocol for securely computing nonlinear functions, our approach sees significant improvements in communication and runtime at comparable storage costs. We also compare our approach against. less generic protocols for non-linear function computation (tree- based comparator, limited to only ReLU) on the basis of communication where we again see considerable improvements. Finally, compared to function secret sharing (FSS) schemes, our approach is comparable in attaining low communication cost while being computationally more efficient.
2
Related Work
2.1
Multiparty Computation Approaches to Secure Neural Network Inference
Multiparty computation approaches to secure neural nelwork inference have been limited by the costs of
computing both the linear and nonlinear portions of the network (Mohassel & Zhang 2017 Rouhani et al,
2017
Rathee ct al. 2020 Keller
2020b. Recent works like Minionn, Gazelle and Delphi (Liu et al. 2017
Juvekar el al.; 2018: Mishra et al. 2020a Lehmkuhl al.) 202T Rathee et al., 2020 Tha et al.] 2021 Cho
et al. 2021 Ghodsi al.
2021) have optimized the linear operations of secure neural network inference via
techniques like preprocessing to the point they are no longer major system bottleneck (Mishra et al. 2020a h
Hence, current state-of-the-art approaches to secure inference like Minionn, Gazelle, Delphi, and CrypTFlowe are primarily bottlenecked by nonlinear operations. Specifically, these approaches rely on garbled eircuits, or a circuit- based protocol, to compute nonlinear activation functions (e.g: ReLU) (Liu et al., 2017 Juvekar eet al. 2018 Mishra et al. 2020aa Keller Sun 2021: Dalskov et al. 2020 resulting in notable drawbacks including high communication, runtime and storage costs.
Our approach addresses the problems posed by garbled circuits by climinating them altogether. Our method is centered around precomputing lookup tables containing the encrypled results of nonlinear activation functions, and using quantization to reduce the size of these tables to make them practical.
2.2 Lookup Tables for Secure Computation
Lookup tables have been used to speed up computation for applications in both secure multiparty computation
[Launchbury et al.) 2012 Damgārd et al. 2017 Keller et al.) 2017 Rass et al.) 2015 Dessouky et al. 2017
Crawford et al. 2018). These works have demonstrated that lookup tables may be used for garbled circuits computation Heath et al. (2024) or as an efficient alternative to garbled circuits, provided that the input space is small. Prior works have primarily locused on using lookup tables to speed up traditional applications like computing AES (Keller et al.) 2017 Damgard et al. 2017 Launchbury et al. [2012] Dessouky et al. (017]) and data aggregation (Rass et al.) 2015 Notable exceptions include (Crawford et al. 2018)) which focuses on linear regression, and (Rathee et al. 2021 which applies variants of lookup table as part of the protocol to secure machine learning inference. Lookup tables are
and homomorphic encryption (Li et al. 2019
4

---

Published in Transactions on Machine Learning Research (06/2024)
also widely used as cryptographic primitives in SNARKS (Stty et al. 2023 Arun et al. 2023 notably efficient primitives for non-arithmetic operations inside circuits (Arun et al. 2023
To the best of our knowledge, there exists little prior work which applies secure lookup tables to the private ofe-----rtt--ttttee secure inference systems like (Mishra et al. 2020a; Mohasssl & Zhang] 2017 Ghodsi et al.] 2021 Tha et al.] (021)) use garbled circuits. Two exceptions this include (Rathee et al. 2020; Huang et al.) 2022), which use a tree-based secure comparator.
execution of large neural networks. Most current
However, the tree-based secure comparator used in (Rathee et al. 2020 Huang et al., 2022 is significantly limited to only the ReLU activation function, and still requires significant computation and communicttion overhead. Another work, (Rathee et al. (021), does indeed use lookup tables as part of their protocol for evaluating activation functions, but crucially focuses on ensuring numerical precision, leading to lower system performance. We highlight that a key distinction in our use of lookup tables is that we store all possible results of the nonlinear function in these tables, which uses exponential storage. This storage is made managcable by heavily quantizing the neural network. This strategy of securely evaluating a function through lookup tables, although known theoretically (Ishai et. al. Damgard & Zakarias] 2016), to the best of our knowledge has not been applied practically until now, due to the exponential storage costs. The secure lookup table approach of "storing everything in a table' is remarkably well suited to securely and efficiently computing neural network nonlinear activation functions for two reasons: 1) neural network activations may be quantized to extremely low precision with little degradation to accuracy and 2) neural network activation functions are single operand. These two factors allow us to limit the size of the lookup table to be sufficiently small to be practical, and consequently we can achieve the significant performance benefits of secure lookup tables at runtime (i.e two orders of magnitude less communication). While work on quantization applied to secure inference cxists (Dalskov et al.) 2020 Keller & Sun 2021), these works do not combine this property with lookup tables for evaluating nonlinear functions. In summary, we emphasize that prior works that use secure lookup tables have either applied them towards non-ML applications (i.e: MPC for AES-128), or have not leveraged exponential-sized secure lookup tables in combination with neural network quantization to make them practical; although the exponential-sized secure lookup table approach for securely computing functions is known, the unique combination of this technique with neural network quantization has not been previously explored. In this work, we demonstrate that this unique combination of techniques can be applied to dramatically reduce the costs of secure neural network inference.
2.3 Function Secret Sharing
The secure lookup table approach (Ishai et al.) employed by TABULA is related to function secret sharing (FSS) approaches used in various private neural network inference approaches like Wagh [2022 ; Gupla et al. (2022); Agarwal et al. (2022). The secure lookup table approach of "storing all function /oputss in a secure lookup table" can be thcoretically categorized as a FSS approach. But there are several concrete differences between the secure table lookup approach TABULA uses compared to traditional FSS approaches. These distinctions lead to significant. runtime differences. Concretely, our secure lookup table approach incurs exponential storage costs which necessitates aggressive activation quantization to make storage costs practical. However, this approach also enables a highly efficient online phase which requires just one 8-bit memory access (in addition to the 2B communication between parties). FSS approaches, on the other hand, rely on using distributed point functions (DPFs) or distributed comparison functions (DCFs), (Boyle et al. 2019 2020) which in turn require evaluating PRGs (i.e: AES-128). Specifically, a table lookup using FSS requires at least log(N) PRG or AES-128 evaluations, where N is the number of entries in the table, leading to 8-16 AES-118 evaluations per activation function call. This cost increases for more complex nonlincar functions [Boyle et al. 2019 2020). Evaluating PRGs like AES-128 is comparatively more expensive than TABULA which requires just 1 8-b memory access, modern processor even with hardware acceleration computes only around 100M AES-128 operations (aes), whereas modern processor has memory bandwidth in the 100GB/s range. As such, TABULA is much more computationally efficient compared to FSS schemes, though as a drawback requires aggressive quantization to make practical. Another benefit to TABULA is that its communication cost is always 2B regardless of the nonlinear function being securely computed. This is not the case for function secret sharing where more complicated nonlincar functions may cost more than 2B |Boyle et al. (2019 2020). Furthermore, a third advantage is that TABULA exhibits information theoretic socurity in the online phase, while function secret. sharing schemes are only computationally secure up to a factor of the
5

---

Published in Transactions on Machine Learning Research (06/2024)
security parameter (Boyle et al. 2020 ; that is, the protocol leaks no information about the underlying data unlike FSS schemes, as FSS schemes rely on pseudorandom functions. A final and notable advantage is that TABULA is much simpler than FSS schemes that rely on computing distributed point functions or distributed comparison functions, which are complex cryptographic primitives. TABULA's main observation that neural network activations can be aggressively quantized to 8-bits and below with acceptable accuracy degradation and thus enable the use of exponential-sizee lookup tables, thereby avoiding the need for evaluating PRGs like AES-128 during online inference.
3 Tabula: Efficient Nonlinear Activation Functions for Secure Neural Network Inference
3.1 Background
Secure Inference Objectives, Threat Model
Secure neural network inference soeks to compute sequence of linear and nonlinear operations parameterized by the server's model over client's s input while revealing as little information to either party beyond the model's 's final prediction. Formally, given the server's model's weights W; E FM;xI and the client's 's private input 2, the goal of secure neural network inference is to compute a; 1() where nonlincar activation function, typically ReLU. W; E FM, L are the weights of the ncural network reprosented as fixed point number in the finite field of modulus p. The dimensions M; and L, correspond to the output and input dimensions the linear layer at i. Convolutions may be cast as a matrix multiply and fit within this framework.
x and A is a
State-of-the-arl secure neural network inference protocols like Delphi operate under two-parly semi-honest setting (Mishra. et al.) 2020a Lehmkuhl et al. 2021), where only one of the parties is corrupted and the corrupted party follows the protocol. Importantly, these secure inference protocols do not protect the architecture of the neural network being executed, only its weights, and furthermore do not secure any information leaked by the predictions themselves (Mishra et al. 2020ah. As we follow Delphi's protocol for the overall secure execution of the neural network these security assumptions are implicitly assumed.
Cryptographic Primitives, Notations, Definitions
TABULA utilizes standard tools in secure multiparty computation. Our protocols operate over additively shared secrets in finite fields. We denote F, p as finite field over n-bit prime p. We use [x]] to denote a two parly additive secret sharing of the scalar i E FF such that x = [x)o + [z]],, where party i holds additive share [x], but knows no information about the other share.
Delphi Secure Inference Protocol
The Delphi framework is set of protocols consisting of an oflline preprocessing phase and an online secure inference phase for securely evaluating neural networks over private client data without revealing to the client the weights of the neural network. The Delphi framework is concerned with the overall evaluation of the neural network (both linear and nonlinear layers). TABULA fits into the Delphi framework by replacing their use of garbled-circuits protocols for secure nonlinear function evaluation, which is the most computationally expensive part of their protocol Mishra et al. (2020a). To understand how TABULA fits into the Delphi framework (Mishra et al. 2020b). we outline how this protocol operates.
Per-Input Preprocessing Phase
This phase prepares for the secure exccution of a single input. The purpose of the preprocessing phase is to initialize the parties with correlated randomness that enables efficient online inference. This phase, as specified in the Delphi paper, requires the use of linearly homomorphic encryption (Mishra ct 2020a) to ensure that the parties do not reveal to each other their secret blinding factors which would compromisc the privacy of the entire protocol. For cach lincar layer W, F FM,LL, II, the client generates a random vector R. e EE,: where L; is the length of the inputs to the current linear layer, The client encrypts R, with their lincarly homomorphic public encryption key & to Snnc(R.). and sends this value to the server. The server, upon receiving Ency (Re), generates their own secret vector R, E PM, where M, is the length of the outputs of the current linear layer. The server then encrypts
6

---

Published in Transactions on Machine Learning Research (06/2024)
Secure Truncation
Secure Lookup (encret [c) table (T))
Client
(precision d)
X
[X d1
Blnch
X
[F(0]]
[F(O]]
Xi
[X = p-l(p-Xi//dl dl
X [T]-[Knectt]
Server
Figure 2: TABULA online protocol. Initially, the client and server hold secret shares of the input [a]. Both parties begin by executing the secure truncation protocol obtain shares of [atrune]- Then, the client and server perform the secure table lookup protocol, where they exchange blinded secrets [Itrunelk + s to compute Ptrune Finally, they use this value index into local lookup tables to compute Ti( which are secret shares of the result of the nonlinear function evaluation.
R2 with the client's 's public key k to obtain Ence (R,). The server then computes and returns to the client Ence (W; + R2). The client decrypts this value to obtain W.R, + R. which is then stored in preparation for the online inference phase.
Online Inference Phase
This phase performs inference the client's input. For linear layers, the client and server begin with additive secret shares of the linear layer's input That is the client and server hold [ı:]o and [z]] respectively, such that [ælo + [x]] = z. As the initial step, the client adds [æ]o with that layer's R. to obtain [xijo + R.- Then the client sends this vector to the server who adds their own share of the layer input [a]] to obtain x + Rr. The server, upon calculating x + Re; then computes Wi( Re) + R. = Wa + W,R, R, (recall that R, was the secret vector that the server generated for this particular layer). At this point, the client holds W,Rt + Rg from the preprocessing phase and the server has computed Wi + W.R. + Rg The difference between these two values is Wi.. Thus the two parties have obtained a secret sharing of W.r. Then, the two parties must compute a nonlinear activation function over these shares to obtain shares of the activations; in the Delphi framework, garbled circuits are employed to securely perform this operation Mishra et al. (2020a), and it is by replacing this part of the protocol that TABULA obtains considerable computational gains. After calculating shares of the activations, the secure inference phase repeats starting from the linear part of the protocol for the rest of the layers of the network.
As stated, after performing the protocol for the linear phase, the client and server hold secret shares of the input to the nonlinear activation function F. Hence we need to construct a secure protocol for performing nonlinear activation functions. This protocol must operate such that the client and server, each holding a secret share of x, can calculate secret shares of F(x) without lcaking any information about x itsclf. F, the nonlinear function for neural network activations, typically ReLU, but may also be include other nonlinear functions like sigmoid or tanh. As note, emphasize that details on the homomorphic preprocessing phase can be found in the Delphi paper (Mishra et al. 2020a)
3.2 Tabula for Securely and Efficiently Evaluating Neural Network Nonlinear Activation Functions
TABULA is divided into a preprocessing phase that initializes a lookup table for each individual nonlinear function call used in the neural network, and online phase which securely quantizes the activation inputs and looks up the result of the function in the previously initialized tables. An overall figure for protocol is shown in Figure I We emphasize that our paper primarily focuses on the online phase of exccution, which determines the system's 's real time response speed after knowing a client's input, rather than the preprocessing phase, which may done offline without knowing the client's s input data. We also develop a secure and reasonably efficient algorithm for the preprocessing phase of Tabula and conduct thorough experiments in the results section demonstrate its viability and effectiveness. We leave further innovations to the preprocessing algorithm to future research.
7

---

Published in Transactions on Machine Learning Research (06/2024)
Below we describe the core building blocks that TABULA utilizes, namely, the secure lookup table procedure
(Tshai et a Keller et al. 2017) and secure truncation protocol (Mohassel & Zhang 2017). We then describe
TABULA'S online and preprocessing execution phase, and detail its security, communication, and storage
properties.
Secure Lookup Table Procedure
We employ the concepts of (Ishai et al.) to enable the computation of a nonlinear function call through a table lookup. By using an exponential amount of preprocessing storage, we obtain secure protocol under the semi-honest threat model where communication complexity depends only the size of its input operands, regardless of the complexity of the function being computed. Concretely, we precompute all possible results of a nonlinear function and store them in a table, and utilize these secure tables during the online phase of secure inference. Computing nonlinear functions in the clear is extremely efficient computationally (i.e: cleartext comparison operations), and so the bulk of the pre-computation workload spent on MPC operations (i.e: Beaver triple multiplication). The lookup table approach similar to that described in (Keller et al. 2017 Ishai et al.). Like in garbled circuits, TABULA requires new circuits per operation to maintain security.
Given a table T[a] F(x), where F: F, + IF, is the target nonlinear function operating over scalars, we initialize a shared table [T' across the parties, so the client holds Tl E Ey and server holds [T] E Fy. A secret scalar 8 E IP unknown to both parties is generated and shared between the client and the server, with the client.
and server holding [s]o and [s] respectively. The shared table T is constructed such that [2][s + x] = [F(x)] for all values of x E F for some modulus p that determines the precision to compute the nonlinear function. Concretely, this means two tables are generated, [To and [7], such that [T]oss + x] + [T] + x] F(z); both client and server coordinate to initialize their local [T]; in an offline preprocessing phase. The online phase, given such shared table, is then straightforward. Initially, the client holds z and the server holds x1. The client sends to the server 2o + So while the server sends to the client In + $1. This allows both parties to obtain the true value of æ + s. Both parties then look up this value in their corresponding tables: client looks up [Tlo + s], server looks up [T] + s), the sum of which is F(x). Sccurity is maintained in the online phase as a new table [T] and secret 8 are used per function call, with s being unknown to either party, perfectly blinding the secret value x.
Securely initializing shared table [T] from T in the offiine preproccssing phase is based on the fact that given index into a table, a table lookup can be cast as a dot product between the entire lable with an indicator vector containing a one in the position of the table index (e.g: the one hot vector encoding of the index). Subsequently, a secure two party demux procedure {Keller et al. 2017) transforms secret shares of [s] into secret shared vectors [s'] which sum to an indicator vector with a one at the s s'th position. Finally, a dot product for each entry of the table can be performed to compute [T]: T(x) x [66++[(x [ +1] x + x [*<]] = [T|s + +x]]- We develop an efficient and secure protocol for initializing TABULA tables based on these concepts later in the text.
Secure Truncation
As the size of T increases lincarly with the size of the field Ep it becomes necessary to truncate or quantize [x] to prevent [T] from being impracticably large. Linear layers are required to use larger finite fields to ensure that their dot products are computed correctly without overflow. Thus, the input to TABULA is a value secret shared in a larger field, and a secure truncation method is required to switch to a smaller field so that the encoded value may be used to index into a feasibly sized table.
We use the secure truncation method in (Mohassel & Zhang, 2017] to achieve this. Given truncation factor d which specifics the precision of the activation inputs, the client and server perform the secure truncation protocol: the client computes [[z]o/d] and the server computes p 1(p - [x]1//d]. After the truncation protocol is performed, the resulting expressions the client and server hold sum to either [[[=]/d] + 1] or [[]=]/[]] with probability proportional to 1 - & where k is the maximum value r may take, and p is the maximum value of the finite field of the previous linear layer (Mohassel & Zhang 2017).
&
These small off by one errors, like quantization error, have little impact on model quality due to neural nelworks' resilience to noise. However, with probability proportional to & a large error occurs that is pessimistically assumed to ruin correctness. To reduce the probability of these catastrophic errors, is necessary to use large finite field modulus for lincar layers.
8

---

Published in Transactions on Machine Learning Research (06/2024)
In practice, use 64-bit finite field modulus to reduce the chance that secure truncation operation catastrophically fails to less than 1000. 2er. Hence, by configuring the modulus appropriately, with high probability, the secure truncation protocol computes the correctly truncated value with a small off by one error which may be tolerated by neural networks (Ni et al. 2020: Reagan et al. 2018).
Requiring 64 bits for the field increases the communication cost required by the linear portions of the protocol over other approaches that commonly use 32 bits, however, the reduction in communication cost by using TABULA tables more than makes up for this communication penalty, and this is shown in the results (note without TABULA use 32-bit precision for the linear layers).
In our experiments, using a 64-bit field size was essential to maintaining accuracy; using a 32-bit field size TABULA saw considerably worse accuracy due to catastrophic failures from the secure truncation protocol, as a single catastrophic failure anywhere in the computation propagates throughout the network and ruins the entire inference. We refer to (Mohasscl & Zhang 2017) for more details. Developing more effective secure truncation techniques is an important topie for further research.
We emphasize that there is a distinction between the field size used for the linear layers and the number of bits for the activations. Concretely, the 64-bit field sizes are used to represent the fixed-point values that are operands to the linear layers of the network, allowing for near full precision multiply--ccuumlltee during linear operations. This is opposed to quantized n-bit (generally n=8) inputs which are used as inputs to the lookup table, which determines the amount of memory used for the tables, as each table has 2n entries. Our method is functionally equivalent to performing the linear operation over 64-bit fixed point values, quantizing the result down to bits, computing the activation function over the truncated result, then scaling back up to 64-bit fixed point valuos for the next lincar operation.
Tabula Online Phase
Given these fundamental building blocks, we describe the TABULA protocol. In the preprocessing phase, TABULA generates multiple shared tables [T] as deseribed above for cach nonlinear function call that is performed when executing the neural network. How much to cruncate/quantize the network' activations is chosen offline to maximize network accuracy. In the online execution phase, TABULA quantizes the inputs to the activation function and uses this input to securely lookup up the result of the function. The full protocol is shown in Figure 2 The security of TABULA is ensured by the security of the secure truncation protocol
[Mohassel & Zhang 2017 and the secure table lookup protocol (Keller et al. 2017
Damgard & Zakarias
2016 Ishai et )..).
Tabula Online Phase Communication and Storage Cost
TABULA achieves significant communication benefits during the online phase at comparable storage costs. As shown in Figure [ TABULA requires just one round of communication to compute any arbitrary function, unlike garbled circuits, which may require multiple rounds for more complex functions. As an example, ReLU implemented using garbled circuits takes two rounds, whereas TABULA requires just one. Additionally, communication complexity is independent of the complexity of the nonlinear function being computed. Specifically, revealing 8a requires both parties to send their local shares, each nonlinear activation call incurs communication cost corresponding to the number of bits in Fp- Since we use 64-bit Fp, this results in 16 bytes of communication per activation function, the cost of transferring 8-byte field values back and forth. However, we can apply an optimization to reduce this down to twice the cost of transferring the size of the impul to the lable, rather than the field size. If the size of the table is 2 entries, and if finite field size p is also power of two, then we can have party i first mod their secret shares by 2 before exchanging them. Henco, the two parties hold [Etrancli mod 2 before adding their secret shares of the table secret [s]; to the value and exchanging it; this brings down the total cost of the protocol to 2 3xD b bits. Modding by 2 yields the correct answer as Ptrune mod p = [Ztrone]o + [Strune]] + pl for some I, and then (Itrune mod p) mod 2 = ([ætrunelo + [Itruno]1 + pl) mod 26 = ([roruneo + [Itrune]1) mod 2 ([ætrunclo mod 2²) + ([Itranel2 mod 2º). This equivalence shows that the two parties can first perform a modulus of their shares with 2b, and that their shares would stlll sum up to the original sum with the correct modulus. With this optimization, communication is now 2 x b bits per nonlincar function call; if we use 8-bit aclivations, then b = 8, and we use 2 byles of communication total per call during the ouline phase, an 8x improvement over the 16 bytes as previously stated.
9

---

Published in Transactions on Machine Learning Research (06/2024)
Generate Indicator
Beaver Triple Outer Product
Vector & Share
Client
[P]
[P]
To[x]=
[a]
[F(x+s)]
*
T(x0=
S Server
[Q] F(s.+s.+*)
Figure 3: TABULA preprocessing protocol. Client and server generate secrets Su, 81 and encode them in an indicator vector (i.e: construct veclor of length equal to the field size, then setting one to the position of the party's secret index). The parties then secret share this indicator vector with the other party. To obtain the entry for [xx,], the parties compute an outer product between the shared indicator vectors and a 2-dimensional table containing F(m + n + x) (where m, span the two dimensions of the table), which obtains [F(x + s)] where: = sn + $1. This works as the 2-D coordinates formed by where the indicator vectors are set privately select m, n through the dot-product; since this is done via private MPC operations, no information is leaked to either party about their corresponding secrets.
Storage and memory, as mentioned previously, grow exponentially with the precision that is used for activations and linearly with the number of activations in the neural network. Storage costs are thus x 2* x N, bits where n is the number of bits to use for the the output of the activation function, & is the number of bits to the imput of the activation function, and No is the total mumber of activations that are performed by the neural network. The majority of the storage cost comes from the 2 factor, the size of the individual tables, which grows exponentially with input space / precision of the activations. However, as neural network activations may be heavily quantized down without significantly affecting model quality (Ni et al., 2020
de Bruin et al. 2020 Zhao et al. 2020), we can reduce this factor enough to be practical; we also highlight. more advanced techniques like using variable number of bits per layer of the network can be employed for better performance (Dong el al. 2019). We verify that quantization has negligible impact on model quality in our results. We highlight that every bit of precision that is trimmed from the activation yields a factor of two roduction in storage and memory costs, and hence more advanced quantization tcchniques (Ni al. 2020 de Bruin el al. 2020: Zhao al. 2020 reduce precision yields significant benefits. As storage and memory varies with the precision of activations that is used, there is natural tradeoff between the accuracy of the model and the achieved wemory/storage requirement. We examine these tradeoffs in the results.
3.3 Tabula Preprocessing Phase
Similar to garbled cicuits, TABULA tables require a preprocessing phase that initializes the client and server with a single-use table that used once per activation function call during the inference phase. We develop a secure and efficient protocol for initializing TABULA tables, detailed below.
Preprocessing Phase Problem Statement
Given nonlinear function F Fp + Fp,, we wish to securely initialize the client and server with tables that map any possible input in Fp to secret shares of the result of the nonlincar function F. Specifically, we wish to initialize on the client a table [Too E p. and on the server a table [T], E Ey, such that
[T][s + æ] + [7][s + x) = F(x), where E F. is a secret unknown to both client and server. Additionally, at the end of the protocol, we want the client to hold $ E IF and server to hold 82 E, such that 8 + 82 = s.
Tabula Secure Preprocessing Protocol
To achieve this preprocessing step securely, the client and server first randomly generate so and 8 respectively, and is implicitly defined as so 5 (though, the parties do not know each others' secrets, they hence do not
1 x = 80
know what s is). Then, the client generates a random indicator vector P E Fg such that P[z]
0 x + 80
10

---

Published in Transactions on Machine Learning Research (06/2024)
the server similarly initializes Q F3 with $1- Client and server exchange shares of P and Q respectively, hence, both parties hold secret shares [P] and [Q] while leaking no information about
to either party. Finallyy client and server jointly initialize their table T[ = Σ m En Fmm + n n ([P) x [Q]m), where = for client and multiplication [Beaver 1991p. We depict the full preprocessing phase operation in Figure 3 and present the algorithmic details below.
for server, and secret shares [P] [Q] E Fp are multiplied using Beaver triple
Algorithm Tabula Preprocessing Phase
1:
client f- random secret Su E Fp
server <- random secret 81 E Fp
client, server locally initialize table F E E s.t. F[ F(i+
1 50
4: client computes P E FE s.t P
0 I +
31
5: server computes Q E pp 8.t Q
0 +
client, server exchange shares of P to obtain secret shares [P], [Q]
client, server compute [PQ] E Fpxx where [PQ][[]]] [P][]] x [Q]b] via Beaver triple multiplication
8: client, server compute [T] Dn m= Σ F' [[][][[ x [PQ] [m]]]] for all i E Fp
Preprocessing Phase Correctness In this protocol the client and server specify the coordinate through an outer product of their indicator vectors P, Q, which sets [T][>] = [F(s + x)}. This computes the correct answer as
P
P
[T|x] = Σ
F(m + n + ([P)m x [Q1x)
m=D n=0
F(m + n x) x Qul) (Beaver triple multiplication)
m=0 n=
P
[
m sg and n 81 otherwise
F(m + n + x)
00
mm
[F(s0 81 x)]
= [F(s + x)]
Preprocessing Phase Security
Security and privacy is preserved as each step of the protocol consists entirely of secure steps: secret sharing P and Q leaks no information about the vectors (hence leaks no information about either 8o, $1, and s), and Beaver triple multiplication is likewise secure (Beaver 1991). Concretely, we see that the only commuicatiin between client and server occurs when they exchange blinded secrets (i.e: [P). (Q) and when they perform Beaver triple multiplication. As these steps leak no information to either party about the underlying secrets, the client and server compule [T] without leaking any information about s0, 81 and hence leak information about
Preproccssing Phase Communication and Computation Cost
The bulk of the preprocessing phase lies in computing an outer product between P,Q. We perform this outer product just once and reuse across i in Txxx]. Hence, the protocol requires performing just a single outer product between vectors E Fp. This incurs O(p²) Beaver triple multiplication operations, and assuming that sufficient number of Beaver triples were generated before the preprocessing phase, communication cost is naively O(p log(p)) bits assuming that the values of the vectors each log(p) bits.
11

---

Published in Transactions on Machine Learning Research (06/2024)
This naive O(p² log(p)) communication cost can be significantly reduced to O(p²) by having P.Q be secret shared binary vectors, rather than be shared in Pp, then doing a conversion back to F. after the final inner product. This can be done as the true values of the vectors P. Q are either 0 or 1. Concretely, upon reception of the binary shares of P or Q the current party computes
[T(x))]
Σ Σ
F(m + n + 2)) [m,
===
Observe that [T(x))] [z](2 is either F(s + x) -F x) (in the case that the first party has the 1 and the second party has the O in the selected index, and the reverse). We perform an extra Beaver triple multiplication by the correction factor to eliminate this potential negation (by multiplying it by the parity of the sum of (PQT)), which costs an extra O(log()) bits of communication per inner-product. Since there are only p inner products, these correction factors cost a negligible O(p (og())))) communication. With this optimization, preprocessing communication cost is now O(p²) bits. As p, the quantized field size of the activation domain, is set to be extremely small (i.e.: less than equal to 256 for 8-bit. quantized activations), preprocessing communication costs 2(256)² 2 131072 bits = 16 KB per table (the factor of two at the front is because Beaver triple mulliplication requires both parlies exchange secret shared values, and we have 256² Beaver triple multiplication operations). This is comparable to the 17.5 KB cost that garbled circuits with full precision requires (Mishra et al. 2020a).
We emphasize that the prior analysis assumed that Beaver triples were obtained beforehand in a pre- preprocessing phase; we think this is reasonable that in practical scenario parties would obtain sufficient amounts of Beaver triples for any protocol due to their importance. However, accounting for Beaver triple preprocessing, communication cost is still an asymptotic O(p)) bits assuming that Beaver triples were generated using oblivious transfer e.g: Nielsen et al. (2012), which requires just 2 OT calls to generate 1-bit, Beaver triples. Using the OT procedure proposed in Huang et al. (2022) the concrete cost of a single OT is 3 bits for 1-bit values. Hence, pre-preprocessing costs for the Beaver triples would still be O(p') bits, with a higher constant factor burden. On a concrete example of S-bit activations, the cost for preprocessing the Beaver triples would amount to 2562 bits = 48 KB of communication. While this excceds the 17.5 KB cost of garbled cireuits, we believe that the online benefits of TABULA more than make up for this detriment.
In terms of computation, we see that for precomputing single table, we require summing across p² values (cach entry of the outer product) for every entry of the table. Since there are p entries in the table, computation costs scale as O(y²). However, these operations may be efficiently vectorized and parallelized as they are standard matrix operations. For b-tit tables, this is around 16 million field operations.
3.4 Note on Tabula Security
Although the TABULA protocol assumnes a honish threat model as inherited from the Delphi (Mishra ct al. 2020a) framework, more generally TABULA'S 's online phase which consists of utilizing a secure lookup procedure is information-thhereeiialll secure (Ishai et al.). This is intuitive as all communication between parties are randomly blinded by an additive factor. This another advantage that TABULA holds over garbled circuits implementations many of which are only computationally secure up to a security parameter in the semi-honest setting (mpch.
4 Results
We present results showing the benefits of TABULA over garbled circuits for secure neural network inference. We evaluate method neural networks including a large variant of LeNet for MNIST, ResNet-32 for Cifar10, and ResNet-34 / VGG-16 for Cifar-100, which are relatively large image recognition ncural networks that prior secure inference works benchmark (Ghodsi et al. 2021 Mishra et al. 2020a Tha et al. 2021 van der
Hagen& & Lucia 2021). ). Unless otherwise stated, we compare against an implementation of the Delphi protocol
Mishra et al.] 2020a) using garbled circuits for nonlincar activation functions, without neural architocture changes, during the online inference phase. As before, we use 64-bit fields for TABULA to reduce the impact
of the secure truncation protocol, however, for the baseline implementation that uses garbled circuits we use
12

---

Published in Transactions on Machine Learning Research (06/2024)
32-bit fields to reduce communiction cost. Experiments are run AWS c5.4x large machines (US-West1 (N. California) and U (Oregon)) which have 8 physical Intel Xeon Platinum @ 3 GHz CPUs and 32 GiB RAM; network bandwidth between these two machines achieves a maximum of 5-10 Gbit/sec, according to AWS. We use the same machine/ /rogion specs as detailed in (Mishra et al. 2020a), but with 2x more cores/ meeeoyy (c5.4xlarge va c5.2xlarge).
To ensure fair comparison, we compare TABULA against garbled circuits with quantized inputs, specifically garbled circuits with 32-bit, 16-bit, and 8-bit inputs, which are commonly used precisions, but we also show more detailed results on more gramular level by fixing accuracy / preciiionn and comparing systems costs between our methods. With the same activation precision, both TABULA and garbled circuits compute the same result. Like other works we benchmark using a batch size of 1 (Mishra et al. 2020a Rathee et al.) 2020: Huang et al. 2022 Ghodsi et al., 2021). TABULA is feasible only for precision up to 12-bits due to the exponential storage costs required for each extra bit of precision, hence, we show results up until this limit. Garbled circuits on the other hand can obtain 32/16-bit precision, however this is beyond the range of precision that TABULA may handle avoid large storage costs. Hence, we may show results for 16/32-bit garbled circuits as baseline reference, but the main comparison is between 8-bit garbled circuits and 8-bit TABULA, or between the two approaches when obtaining fixed accuracy.
4.1 Communication Reduction
ReLU Communication Reduction
We benchmark the amount of communication required to perform a single ReLU with TABULA vs garbled circuits. Table 2 shows the amount of communication required by both protocols during online inference. TABULA achieves siguificant (> 280x) communication reduction compared to garbled circuits. Note our implementation of garbled circuits on 32-bit imputs achieves the same communication cost as reported by Miishra et al. 2020a) (2KB communication for 32-bit integers).
Garbled Circuits
Garbled Circuits
Garbled
ComM. Reduction
Circuits
Tabula
(32-bit)
(16-bit)
(8-bit)
(vs 32/16/ 16//8 bit GC)
2.17KB
1.1KB
.562KB
2B
1112x
560x
280
Table 2: TABULA with 8-bit activations vs garbled circuits communication cost. for one ReLU.
We additionally compare ReLU communication of our protocol against. recent works like CrypTflow2 Rathee et al. (020) and Cheetah (Huang et al. 2022). CrypTflow2 and Cheetah similarly utilize tree- based secure comparison protocol dependent on oblivious transfer (Rathee et al.) 2020 Huang et al. 2022). However unlike CrypTflow2, Cheetah swaps out the underlying oblivious transfer inplementation for a more efficient version Huang et al. (2022). Our following analysis assumes that CrypTFlow2 uses a more efficient OT protocol based on preprocessing which reduces the online communication costs beyond what they present in their paper; broadly, the tree-based comparison method that CrypTflow2 utilizes requires at least 6 calls to 1-out-of-128 oblivious transfer for optimal communication complexity (Rathee et al. 2020), which, with preprocessing, takes at least 6 x 128- = 768 bits or 96 bytes, as oblivious transfer with preprocessing requires sending all n bits to the original sender at the end (Beaver 1995 Naor & Pinkas 1999). TABULA requires just 16 bits of communication regardless of the nonlinear function being computed, obtaining a 48x improvement in communication over the tree based comparison method of CrypTflow2 / Cheetah assuming the use of this preprocessing-basee based OT method. Cheetah's 's approach on the other hand uses the same tree-based comparison approach (Huang et al., 2022 but swaps out the underlying OT method for more efficient version; specifically, Cheetah's communication cost is 11 x L where L is the bitlength of the field element, which results in 88 bits of communication for 8-bit values and 352 bits for 32-bit values. TABULA requires just 16 bits of communication, which represents a 5.5x and 22x reduction respectively. SiRNN (Rathee et al., 2021), another paper which utilizes an OT based protocol, uses more communication than that of ReLU of CrypTflow (Rathee et al. (202)), hence our method would see > 48x communication improvement when compared their approach. We also compare communication cost against FSS approaches (Boyle et al. 2019
Gupta et al. 2022
Agarwal et al. 2022 Ryffel et al. 2021). Generally, for the ReL.U op TARULA obtains the
13

---

Published in Transactions on Machine Learning Research (06/2024)
same 2B communication cost FSS, however TABULA obtains several notable qualitative advantages over FSS, and table comparison is shown in Table 3 We summarize these communication cost comparisons in
Table | which compares the online communication cost of single ReLU operation for TABULA, CryptFlow2 and Cheetah.
Tabula
FSS
Computational Efficiency
8-bit memory access per op
1 PRG (i.e: AES-128)
operation per op
2B comin. cost for any nonlinear function (must fit in table)
Comm. cost increases for more complex nonlinear ops
Generality
Computational Security
Security
Information-Theorctcaally Secure
(up to security parameters X)
Complexity
Table lookup
DPF DCF (Boyle et al. 2020
Table 3: Qualitative comparison between TABULA and FSS schemes.
FSS
CrypTFlow2
Cheetah 32-bit
Cheetah 8-bit
Comm. Reduction
Tabula
(8-bit;
(OT preproc. method)
ReLU op)
2B
96B
44B
11B
2B
48
22 x
5.5
Table 4: TABULA (i- activations) vs CrypTFlow2 [Rathee et al., 2020) and Cheetah (Huang et al. 2022 and FSS [Boyle et al. 2019: 2020) online communicatio cost for performing a single ReLU operation during the online phase. For CryptFlow2 the communication based on an OT method that uses preprocessing which achieves better online communication cost than what is described in Rathee et al. (2020). Note FSS, Cheetah, Cryp'IFlow2 costs are specific to the ReLU op, while TABULA communication cost the same for any function provided they are quantized down to sufficiently small table size.
Total Online Communication Reduction
We benchmark the total amount of online communication required during the online phase of single private inference for various network architectures including LeNet, Resnet-32, ResNet-34 and VGG (batch size 1). Table 5 shows the number of ReLUs per network, as well as the communication costs of using garbled circuits (for 32/12 16/1 bit inputs) vs TABULA. TABULA roduces communcattion significantly (> 20x, > 10x, > 5x vs 32,16,8 bit garbled circuits) across various network architectures.
Garbled
Garbled Circuits
Garbled Circuits
Comm. Reduction (vs 32/16/8 bit GC)
Network
ReLUs
Circuits
Tabula
(32-bit)
(16-bit)
(8-bit)
LeNet
58K
124 MB
62 MB
31 MB
3.5 MB
35.4x
17.7x
8.8x
ResNet-32
303K
311 MB
155 MB
77 MB
14 MB
22.2x
11.1x
5.6x
VGG-16
276K
286 MB
143 MB
72 MB
12.1 MB
23.6x
11.8x
5.6x
ResNet-34
1.47M
1.5 GB
.75 GB
370 MB
59.5 MB
24.7x
12.4x
6.2x
Table 5: TABULA vs garbled circuits total online communication cost during secure inference for different. network architectures.
We additionally compare end-to-end communication costs against Rathee al. (2020), the current state-of- the-art for neural network inference, various networks Minionn and ResNet34 (Liu et al. 2017). shown in Table 0 TABULA'S compact tables enable much lower communication costs during the online phase of secure neural network inference, leading to an order of magnitude reduction in communication costs.
Finally, Figure shows the communication reduction TABULA achieves compared to garbled circuits with bit quantized inputs at a fixed accuracy threshold, and shows TABULA achieves over 8 9- communication reduction across networks to maintain close full precision accuracy. These values reflect total online
14

---

Published in Transactions on Machine Learning Research (06/2024)
Network
RcLUs
Tabula
CrypTFlow2
Comm. Reduction
MinioNN
176K
25MB
280MB
11.2 x
ResNet-34
1.47M
59.5 MB
590MB
9.9 x
Table 6: TABULA vs CrypTFlow2 [Rathee et al.
2020
end-to-end communication cost for performing secure
neural network inference on selected networks (Minionn (Liu et al. 2017) CIPAR10 architecture, and ResNeL34 C10)
communication costs, not just ReLU communication costs, and hence we find we are primarily bottlenecked by the communication for the linear layers rather than nonlinear layers. Also, do not make any architectural changes to the neural network (e.g: replace any ReLU operations with quadratic operations, retrain, etc).
As A
Ao AlsAn Asz
As Au A1
0.8
An A1a
0.990
0.986
0.988
0.7
0.8
Accuract
0.5
0.6
00.5
0.6
0.984
0.5
0.4
0.4
0.982
0.3
0.980
0.2
0.978
Baseline Acc
0.2
A6
Baseline Acc
0.1
Baseline Ace
0.1
4
Baseline Acc
0.976
9
Communi Reduction
Communication Reduction
Communication Reduction
Communication Reduction
(a) MNIST LeNet
(b) CIFARIO RcsNet32
(c) CIFAR100 VGG16
(d) CIFAR100 ResNet34
garbled circuits (x-axis) vs accuracy, when garbled circuits communication cost for An bits is compared against Tabula with 8-bit inputs. Tabula with 8-bit. inputs achieves accuracy equivalent to Ag. This plot shows Tabula with 8-bit. inputs obtains greater communication reduction over GCs with different precisions on various test architectures, while remaining withing 1% to 2% of the full precision bascline. Because both Tabula and GC see linear scaling of communication cost with the number of activation bits to the input of the nonlinear function, n-bit Tabula vs n-bit GC would yield a communication reduction factor of 6-8x for all n on these test architectures. Also the labels denoted An mark the accuracy achieved by both Tabula and GOs should they use bit activations, both compute the same result. Baseline precision shown the dashed blue line.
Figure 4: TABULA communication reduction improvement
4.2 Storage Costs
We compare the storage savings TABULA achieves against garbled circuits. Recall that TABULA requires storing a single lookup lable for each nonlinear activation call. This storage cost grows exponentially with the size of its tables, which dictates the precision of the activations. Using less storage means reducing the precision for the activations of the neural network and introduces some amount of error into the nonlinear function. This creates tradeoff between storage and network accuracy. Similar to garbled circuits, TABULA tables must be stored on both client and server, and likewise, storage costs are equivalent for both client and server; hence, in our results we show the storage cost for a single party. Below we show both the storage savings for a single ReLU operation disregarding the accuracy impact from the quantization, and additionally the storage vs accuracy tradeoffs for various networks (LeNet, ResNet32/34 VGG). Storage costs directly translate memory usage costs at inference time since the lookup tables or garbled circuits must be loaded into memory to be used to evaluate the nonlinear functions.
ReLU Storage Savings vs Precision
We compare the storage use between TABULA and garbled circuits for a single ReLU operation. TABULA'S storage use is the the size of its table multiplied by the number of bits of elements in the original field, which we default to 64-bit. numbers. Garbled circuits, on the other hand, uses 17KB, 8.5KB, and 4.25KB for each b2t 16-bit, and 8-bit ReLU operation respectively (Mishra et al. 2020a).
Figure 5 presents the storage usage of both TABULA and garbled circuits for a single ReLU operation, and shows that TABULA achieves comparable storage use to garbled eircuits at precisions 8-10, and lower storage
15

---

Published in Transactions on Machine Learning Research (06/2024)
use with precisions below 8. Specifically, with 8 bits of precision for activation TABULA achieves 8.25x, x.1x and 2x savings vs 32-bit, 16-bit and 8-bit garbled circuits; with ultra low precision TABULA achieves even more gains (4 bits yields around 136x storage reduction vs 32-bit garbled circuits and 17x reduction vs 8-bit garbled circuits). These results imply that standard techniques to quantize activations down below 8 bits and advanced techniques to quantize below 4 bits (Ni el al. 2020 de Bruin al. 2020 Zhao el al. 2020 can be applied with TABULA to achieve significant storage savings. Notably, TABULA achicves storage savings ultra low precision activations as 1-bit reduction in activation precision yields a 2x storage reduction, unlike for garbled circuits where storage is reduced linearly.
Storage Savings and Accuracy Tradcoff
We present TABULA's 's total storage usage versus accu- racy tradeoff in Figure [] In this experiment, we directly quantize the network's s activations during execution time uniformly across layers, recording the achieved accuracy and memory /storage requirements for a single inference. As shown in Figure 0 across various tasks and network architectures, activations may be quantized to 9 bits or be- low while maintaining within 1-3% accuracy. This allows TABULA to achieve comparable or even less storage use than garbled circuits at a fixed accuracy threshold. We em- phasize that future work may apply more advanced quan- tization techniques (Ni et al. 2020 de Bruin et al., 2020) to reduce activation precision below 8-bits and achieve even better storage savings. Our results here show that even with very basic quantization techniques, TABULA achieves comparable storage usage versus garbled circuits, and indicate that TABULA is more storage efficient as fewer bits of precision for the activations are used.
(Mem. (KB)
Tabula
Garbled Circuits
23
Stora 0
-1
2-2
2-
4
5
6
7
8
9
10 11 12
Precision for Activation
Figure TABULA and garbled circuits storage use for a single ReLU operation.
A12
Ar AsaA11
0.8
As AigAn
0.990
0.9
0.7
0.7
0.8
0.986
0.7
0.6
Accuracy
0.5
0.6
0.5
0.984
0.5
0.4
0.980
0.982
Baseline Acc
0.3
0.4
Baselinn Acc
Tabula
0.2
Baseline Acc
Tabula
0.2
0.3
Baseline Acc Tabila
Gartled
0.2
A;
4
Garbled Circuts
A
A
0.1
A. A
Craults
0.976
2/4
2/2
212
2
0.1
23
2
20
2
0.0
24
212
230
2
0.0
2
2
2 2 24 223 2 2
Storage (KB)
Storage (KB)
Storage (KB)
Storage (KB)
(a) MNIST LeNet
(b) CIFARIO ReaNet32
(c) CIFAR100 VGG16
(d) CIFAR100 ResNet34
Figure 6: TABULA overall storage usage for single inference versus accuracy for different tasks and neural networks. Each point is annotated with An, specifying the precision of activations for that run. With activation precisions above 10 TABULA uses more storage than garbled circuits due to the exponential increase in the size of its tables; however, below a precision of 8, TABULA achieves notable storage savings (> 2x) over garbled circuits. Baseline precision shown as the dashed blue line.
4.3 Runtime Speedup
We compare the runtime speedup TABULA achieves over garbled circuits. As noted in various secure neural network inference works (Mishra et al. 2020a Ghodsi et al., 2021 Cho et al., 2021j, executing nonlinear activation functions via garbled circuits takes up the majority of secure neural network execution time, hence, replacing garbled circuits with an efficient alternative has a major impact on runtime. Below we present the Tabula's 's runtime benefits when executing individual ReLU operations and when executing relatively large state-of-the-art neural networks.
ReLU Runtime Speedup
Table 7 shows the runtime speedup TABULA achieves over garbled circuits when executing single ReLU
16

---

Published in Transactions on Machine Learning Research (06/2024)
Garbled Circuits
Garbled Circuits
Garbled Circuits
Tabula Runtime (us)
32-bit
16-bit
8-bit
Tabula Speedup
Runtime
Runtime (us)
Runtime (us)
(vs 32/16/8 bit GC)
(us)
184
111
69
.55
334 x
202
105
Table 7: TABULA runtime speedup vs garbled circuits on a single ReLU operation. TABULA is orders of magnitude faster than garbled circuits.
operation. TABULA achieves over 100x runtime speedup due simplicity: the cost of transferring bytes of data and a single access to RAM is orders of magnitude faster than garbled circuits. Our implementation of garbled circuits on 32-bit inputs is slower than reported in Delphi (Mishra et al., 2020a). Our implementa atin of garbled circuits takes around 184 us per ReLU, whereas the reported is 84 us (Mishra et al., 2020a However, even if the implementation in Delphi achieves an optimal 4x speedup with 8-bit quantization, TABULA is still 38x faster.
Neural Network Runtime Speedup
We present TABULA'S overall speedup gains over garbled circuits across various neural networks including LeNet, ResNet32/23 and VGG16. Table g and Figure shows that TABULA reduces runtime by up 50x across different neural networks, bringing execution time below 1 second per inference for the majority of the networks. Bigger networks are increasingly bottlenecked by ReLU operations, and hence TABULA's runtime reduction increases in magnitude with the size of the neural network under consideration. Figure S shows breakdown of where execution time is being spent, for both TABULA and garbled circuits. As shown, TABULA reduces the runtime spent on computing activation functions by up to orders of magnitudes. With bigger networks, the impact of executing nonlinear activation functions is larger. Hence, TABULA sees greater runtime improvement on larger networks. Additionally, in the runtime breakdown chart, the linear layers for TABULA considerably slower than the linear layers when using garbled circuits cache effects caused this diffcrence in performance, as TABULA keeps all tables in memory, which may have overflowed to swap memory. Despile the slowdown in the linear layers, this has negligible impact runtime due to non- linear layers being the dominant cost, and TABULA sees considerably performance gains by being faster on the nonlincar layers.
believe that
Auz
Augi32
0.7275
Ar A2
A12
Asefez
0.9904
1/2
0.32
Garbled Chrcuts
0.76
Garbled Cirouts Tobub
Accuracy
0..9903
0.9902
Garbled Cicukt
Accuracy
0.91
0.7200
Garbidd Cirults Tabula
Accuracy
0.75
0.9901
0.7175
8.74
1
0.88
0.7150
Au
0.87
0.7100
An
0.72
Aa
Runtime (s)
Runtime (s)
Runtime
Runtime (s)
(a) MNIST LeNet
(b) CIFARIO ResNet32
(c) CIEAR100 VGG16
(d) CIFAR100 ResNet34
Figure 7: TABULA overall runtime for a single inference versus accuracy for different tasks and neural networks.
Each point is annotated with An, specifying the precision of activations for that run. At activation precisions 10-12 (achieving within 1-2% of baseline accuracy), TABULA achieves signifieant runtime speedup (> 10x) over garbled circuits.
4.4 Preprocessing Costs
We benchmark our proposed algorithm for preprocessing TABULA tables against garbled circuits preprocessing times to demonstrate that TABULA preprocessing costs are comparable to garbled circuits.
Preproccssing Runtime & Communication Costs
17

---

Published in Transactions on Machine Learning Research (06/2024)
32-bit
16-bit
8-bit
Garbled
Garbled
Garbled
Tabula Runtime (s)
Speedup
Network
ReLUs
Circuits
Circuits
Circuits
(vs 32/16/8 bit GC)
Runtime
Runtime
Runtime
(s)
(s)
(s)
LeNet
58K
11.1
6.3
3.9
.29
38.3x
21.7x
13.4x
ResNet-32
303K
69.7
43.4
30.6
.97
71.8x
44.7x
31.5x
VGG-16
284.7K
55.9
32.1
19.9
.67
83.4x
47.9x
29.7x
ResNett-34
1.47M
284.3
159.9
95.9
1.85
153.7x
86.4x
51.8x
Table 8: TABULA total online runtime speedup compared with garbled circuits. Compared to garbled circuits, TABULA achieves significant runtime speedup during neural nel work execution by reducing code complexity, communication costs, and memory/storage overheads.
10a
Linear Ops
Linear Ops
Linear Ops
Linear Ops
103
ReLU
Runtime (ms)
10
ReLU
10
ReLU
Runtime (ms)
ReLU
304
Runtime
Runtime
1.0
10a
100
10p
10k
(326.0
(16-b1))
(8-b4)
(32421)
(18-bit)
(8-61)
(32-10)
(16-2)
(8-51)
(3246)
(16-iit)
(8-210
(a) MNIST LeNet
(b) CIFARIO ResNNet32
(c) CIFARI00 VGG16
(d) CIFAR100 ResNet34
Figure 8: Runtime breakdown across linear and nonlinear (ReLU) layers comparing TABULA with 8-bit inputs and garbled circuits with and 8-bit inputs. TABULA achieves significant performance gains on nonlinear layers, leading to major runtime speedups.
We compare runtime and communication costs for initializing a single ReLU operation. Table 9 shows the cost of preprocessing a single ReLU operation for Tabula with 8-bit imputs, and garbled circuits. terms of communication costs, Tabula is comparable communication (han GC with 16/8 bit inputs. In terms of runtime, Tabula generally requires significantly more computation than garbled circuits, leading to higher runtime. The majority of Tabula preprocessing runtime is spent towards computing field operations for performing the mulliply-adddaccumallt operation between the outer product and the nonlinear function (recall that computation costs for an 8-bit input scales as ))256))). These computation costs can be significantly decreased through further parallelization and vectorization.
GC with 32-bit inputs; however, Tabula requires more
Tabula Preprocessing (8-bit)
Garbled Circuits
Garbled Circuits Preprocessing (16-bit)
Garbled Circuits Preprocessing (8-bit.)
Metric
Preprocessing (32-bit)
Runtime (ms)
.155
.092
.053
Communication (b)
16384
17920
8960
4480
Table 9: Tabula vs Garbled Circuits runtime and communication preprocessing costs for a single ReLU operation. Note: Tabula preprocessing costs, like runtime costs, stay constant regardless of activation function, unlike garbled circuits.
We further show the effect of number of bits used for the activation function on preprocessing communication costs. As each bit that is eliminated reduces the size the table by a factor 2, saving a single bit exponentially decreases runtime and communication costs. As seen Figure g at around bits TABULA preprocessing communicatin costs become lower than communication cost for garbled circuit at the same bitwidth.
18

---

Published in Transactions on Machine Learning Research (06/2024)
4.5 und-to-end Preprocessing Communication Costs
We additionally compare end-to-end preprocessing communication costs across various models (LetNet, ResNet, VGG) between TABULA and Garbled Circuits. Table [0 shows a comparison of the communi- cation costs between different models. Again, TABULA requires more communication than GC with 8/16-bit inputs but less than GC with 32-bit inputs, due to the need for computing outer products using Beaver triples that scale with the cardinality of the field. Although this is costly, results show that preprocessing can be feasibly per- formed at similar cost to GC with 32-bit inputs. Further research and algorithmic developments may drive down the preprocessing cost of initializing TABULA tables.
Communication (KB)
16
Tabula
Garbled Circuts
4.
2
6
Bits
Figure 9: Tabula preprocessing com- munication cost vs Garbled Circuits
Tabula Preprocessing
Garbled Circuits Preprocessing
Cerechits Caabhee Circuits
Network
ReLUs
Preprocessing (16-bit)
Preprocessing (8-bit)
(8-bit)
(32-bit)
LeNet
58K
906 MB
991 MB
496 MB
248 MB
ResNet-32
303K
4.6 GB
5.05 GB
2.53 GB
1.27 GB
VGG-16
284.7K
4.3 GB
4.75 GB
2.37 GB
1.19 GB
ResNet-34
1.47M
22.4 GB
24.5 GB
12.25 GB
6.13 GB
Table 10:
Preprocessing communication cost comparison between TABULA and garbled circuits for various neural network models. TABULA has comparable preprocessing costs compared to garbled circuits.
5
Conclusion
TABULA is a secure and efficient protocol for computing nonlinear activation functions in secure neural network inference. Our approach obtains considerable computational benefits over garbled circuits and other approaches to securely computing nonlinear functions. To conclude, we point out the following observation: quantization, as applied to improve standard neural network performance, typically obtains sublinear runtime improvements (as low bitwidth ops typically do not scale linearly in perf. with bits due to hardware inefficiencies), and linear memory improvements. Through our method, quantization as applied to secure neural network inference, obtains super-linear
improvements that scale with the complexily of the underlying nonlinear operation, and exponential memory improvements. We believe that, quantization, an already important performance improvement technique for neural networks, will be even more crucial for secure noural network inference, and that our method TABULA is a key approach towards realizing this fact. Additionally, TABULA will see improvement to both the online and offline phases with further advancements to neural network quantization. TABULA step towards sustained, low latency, low energy, low bandwidth real time secure inference applications.
Acknowledgements
Michael Mitzemmacher was supported in part by NSF grants CCF-2101140, CNS-2107078, and DMS-2023528.
References
AES performance.
Fundamental MPC protocols. http:///wee..rrooooo........oeaa
pdf AmirAli Abdolrashidi, Lisa Wang, Shivani Agrawal, Jonathan Malmaud, Oleg Rybakov, Chas Leichner, and Lukasz Lew. Pareto-optimal quantized resnet is mostly 4-bit. 2021 IEEE/CC /CVF Conference on Computer Vision and Pottern Recognation Workshops (CVPRW), pp. 1855-009,,4 2021.
19

---

Published in Transactions on Machine Learning Research (06/2024)
Amit Agarwal, Stanislav Peceny, Mariana Raykova, Phillipp Schoppmann, and Karn Seth. Communication-
efficient. secure logistic regression. Cryptology ePrint Archive, Paper 2022/866, 2022. URL https
//eprint.iacr wtt.a....../////////55/// https://eprint. www.rriinniia...i.ommmm wwwp:aaaarrrogg//2200 org/2022/866
Arasu Arun, Srinath Setty, and Justin Thaler. Jolt: Snarks for virtual machines via lookups. Cryptology https://eprint
ePrint Archive, Paper 2017/1217, 2023. URL http://pprrnn.iiaar.orr///222222
oaorrorg//0 0rg/2023/1217
Donald Beaver. Efficient multiparty protocols using circuit randomization. volume 576, pp. 420 432, 08 1991.
ISBN 978-3-540-55188-L doi: 14-007/3-540-46666 34.
Donald Beaver. Precomputing oblivious transfer. volume 963, pp. 97 109, 08 1995. ISBN 978-3-540-60221-7.
doi: 10.1007 11-0073-550 10-0773--40---0 140044450-4_8.
Elette Boyle, Niv Gilboa, and Yuval Ishai. Secure computation with preprocessing via function secret. sharing. Cryptology ePrint Archive, Paper 2019/1095, 2019. URL https::/ http:/pitt..i...oo////////////// org/2019/1099
https://eprint: iacr. org/2019/1095
Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, and Mayank Rathoe. Function secret sharing for mixed-mode and fixed-point secure computation. Cryptology ePrint Archive, Paper 2020/1399 1392, 2020. URL https://eprint: iacr. ortieo////2022012222 htttps///ppritt. iacr
org/2020/1392
Minsu Cho, Zahra Ghodsi, Brandon Reagen, Siddharth Garg, and Chinmay Hegde. Sphynx: Relu-efficient network design for private inference, 2021.
Jungwook Choi, Swagath Venkataramani, Vijayalakshmi Srinivasan, K. Gopalakrishnan, Zhuo Wang, and Pierce I-Jen Chuang, Accurate and efficient 2-bit quantized neural networks. In MLSys, 2019.
Jack L. H. Crawford, Craig Gentry, Shai Halevi, Daniel Platt, and Victor Shoup. Doing real work with fhe: The case of logistic regression. In Proceedings of the 6th Workshop Enerypted Computing; Applied Homomorphic Cryplogruphy, 2018.
Anders Dalskov, Daniel Escudero, and Marcel Keller. Secure evaluation of quantized neural networks. Proceedings on Privacy Enhancing Technologies, 2020.
Ivan Damgard, Jesper Buus Nielsen, Michael Nielsen, and Samuel Ranellucci. The tinytable protocol for 2- 2-party secure computation, or: hate-scrambling revisited. In CRYPTO, 2017.
Ivan Damgárd and Rasmus Zakarias. Fast oblivious aes a dedicated application of the minimac protocol.
In Proceedings of the 8th International Conference on Progress in Cryptology - AFRICACRYPT 2016 Volume 9646, pp. 245 264, Berlin, Heidelberg, 2016. Springer- Verlag. ISBN 9783319315164.
doi:
00.1007/978-3-33 319 31517-1 13. URL http::////0i..00111.10000/..////
319---31100011111111 319-31117-1111
Barry de Bruin, Zoran Zivkovic, and Henk Corporaal. Quantization of deep neural networks for accumulator- constrained processors. Microprocessors and Microsystems, 2020.
G. Dessouky, F. Koushanfar, A. Sadeghi, T. Schneider, Shaza Zeitouni, and Michael Zohner. Pushing the communication barrier in secure computation using lookup tables. IACR Cryptol. ePrint Arch., 2017.
Zhen Dong, Zhewei Yao, Amir Gholami, Michael Mahoney, and Kurt Keutzer. Hawq: Hessian aware 2019, doi:
quantization of neural networks with 03696
190......00..0666. URL
Karthik Garimella, Nandan Kumar Jha, and Brandon Reagen. Sisyphus: A cautionary tale of using lew-ee polynomial activations in pnivacy-preserving deep learning, 2021. URL https://arxiv. org/ abs 2217
12342
Zahra Ghodsi, Nandan Kumar Jha, Brandon Reagen, and Siddharth Garg. Circa: Stochastic relus for private deep learning. Tn Advances in Neural Information Processing Systems, 2021.
20

---

Published in Transactions on Machine Learning Research (06/2024)
Kanav Gupta, Deepak Kumaraswamy, Nishanth Chandran, and Divya Gupta. Llama: A low latency math library for secure inference. Cryptology ePrint. Archive, Paper 2022/793, 2022. URL https
//eprint. 2aarroor//022//93 https://eprint: iacr www.iiaa.r...o.... org/2022/793
David Heath, Vladimir Kolesnikov, and Lucien K. L. Ng. Garbled circuit lookup tables with logarithmic number ciphertexts. Cryptology ePrint Archive, Paper 2024/369, 2024. URL Inttps://eprinn iacr
org/2024/369 https://eprint. iacr 0rg/202/3669
Tuan Hoang, Thanh-Toan Do, Tam V. Nguyen, and Ngai-Man Cheung. Direct quantization for training highly accurate low bit-width deep neural networks. In Proceedings of the T Twenty-Nindh International Joint Conference on Artificial Intelligence, IJCAI-20. International Joint Conferences Artificial Intelligence Organization, 2020. URL http::////....rr/////222/22// 24963/1ja. 2020/2922
Zhicong Huang, Wen jie Lu, Cheng Hong, and Jiansheng Ding. Cheetah: Lean and fast secure Two- Party deep neural network inference. In 31st USENIX Security Symposium (USENIX Security 22), pp. 809 826, Boston, MA, August 2022. USENIX Association. ISBN 978-1-939133-31- URL https:
//www. wwww.uuemiz..rg//oofeeeeeeee http:///eeeeeaaaeaaaaaoaaoo/eeea
Yuval Ishai, Eyal Kushilevitz, and Sigurd Meldgaard. On the power of correlated randomness in secure computation. In In Proc. TCC 2013, pp. 600-620.
Nandan Kumar Jha, Zahra Ghodsi, Siddharth Garg, and Brandon Reagen. Deepreduce: Relu reduction for fast private inference. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. Gazelle: A low latency framework for secure neural network inference. In 27th USENIX Security Symposium (USENIX Security 18), 2018.
Marcel Keller. MP-SPDZ: A versatile framework for multi-party computation. In Proceedings of the 2020
ACM SIGSAC Conference on Computer and Communications Security, 2020.
Marcel Keller and Ke Sun. Secure quantized training for deep learning. CoRR, abs/ 22102 2021.
Marcel Keller, Emmanuela Orsini, Dragos Rotaru, Peter Scholl, Eduardo Soria-Vazquee and Srinivas Vivek. Faster secure multi-party computation of aes and des using lookup tables. In International Conference on Applied Cryptography and Network Security, 2017.
John Launchbury, Iavor S. Diatchki, Thomas DuBuisson, and Andy Adams-Moran. Efficient lookup-table protocol in secure multiparty computation. SIGPLAN Not., 2012.
Ryan Lehmkuhl, Pratyush Mishra, Akshayaram Srinivasan, and Raluca Ada Popa. Muse: Secure inference resilient to malicious clients. In 30th USENIX Security Symposium (USENIX Security 21), 2021.
Ruixiao Li, Yu Ishimaki, and Hayato Yamana. Fully homomorphic encryption with table lookup for privacy- preserving smart grid. In 2019 IEEE International Conference on Smart Computing (SMARTCOMP) 2019.
Jian Liu, Mika Juuti, Yao Lu, and Asokan N. Oblivious Neurol Network Predictions via MiniONN Transfor- mations. 2017.
Hoi-Kwong Lo. Insecurity of quantum secure computations. Phys. Rev. A, 1997.
Jeffrey L. McKinstry, Steven K. Esser, Rathinakumar Appuswamy, Deepika Bablani, John V. Arthur, Izzet B. Yildiz, and Dharmendra S. Modha. Discovering low-precision networks close to full-precision networks for efficient embodded inference, 2019.
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In 29th USENIX Security Symposium (USENIX Security 20), 2020a.
21

---

Published in Transactions on Machine Learning Research (06/2024)
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi codebase. httpp:///githbb http:///ommoooojpc////aaaaaa/aa 2020b.
Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable privacy-preserving machine learning. In 2017 IEEE Symposium on Security and Privacy (SP), 2017.
Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In Proceedings of the Thirty- First Annual ACM Symposium on Theory of Computing, STOC '99, pp. 245-254, New York, NY, USA, 1999. Association for Computing Machinery. ISBN 1581130678.
doi: 10.
URL
Renkun Ni, Hong min Chu, Oscar Castañeda, Ping yeh Chiang, Christoph Studer, and Tom Goldstein. Wrapnet: Neural net inference with ultra-low-rreooltion arithmetic, 2020.
Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. new approach to practical active-secure two-party computation. TACR Cryptol. ePrint Arch., 2011:91, 2012.
Stefan Rass, Peter Schartner, and Monika Brodbeck. Private function evaluation by local two-party computation. EURASIP Journal on Information Security, 2015.
Deevashwer Rathoe, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptslow2: Practical 2-party secure inference. Proceedings of the 2020 ACM SIGSAC Conference Compuler and Communications Security, 2020.
Deevashwer Rathee, Mayank Rathee, Rahul Kranti Kiran Goli, Divya Gupta, Rahul Sharma, Nishanth Chandran, and Aseem Rastogi. Sirnn: math library for secure rmn inference, 2021. URL https:
Srrxxv.org/abs/21000 04236
Brandon Reagan, Udit Gupta, Bob Adolf, Michael Mitzenmacher, Alexander Rush, Gu-Yeon Wei, and David Brooks. Weightless: Lossy weight encoding for deep neural network compression. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Bita Darvish Rouhani, M. Sadegh Riazi, and Farinaz Koushanfar. Deepsecure: Scalable provably-secure deep learning, 2017.
Théo Ryffel, Pierre Tholoniat, David Pointcheval, and Francis Bach. Ariann: Low-interaction privacy- preserving deep learning via function secret sharing, 2021.
Srinath Setty, Justin Thaler, and Riad Wahby. Unlocking the lookup singularity with lasso. Cryptology ePrint Archive, Paper 2023/1216, 2023. URL htttps://ppritt. iaci. www.:/aaarrrrrrgreee org/2023/1166 https://eprint
iacr. www.eorg/ggo 20/3//2222111
McKenzie van der Hagen and Brandon Lucia. Practical encrypted computing for iot clients, 2021.
Sameer Wagh. Pika: Secure computation using function secret sharing over rings. Cryptology ePrint Archive, Paper 2022/826, 2022. URL https://eprrnt. iacr org//22/22222 htttss:/ http:iitt.aarrrrrrr./..o waaaarrorg//000 org/2022/ 826
Andrew Chi-Chih Yao. How generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfes 1986), 1986.
Xiandong Zhao, Ying Wang, Xuyi Cai, Cheng Liu, and Lei Zhang. Linear symmetric quantization of neural networks for low-precision integer hardware. In International Conference on Learning Representations, 2020.
22

---

Published in Transactions on Machine Learning Research (06/2024)
A
Appendix
Polynomial approximation vs quantization
Ample research has been dedicated towards exploring how to make polynomial approximations more amenable to neural networks (as enabling polynomial activations eliminates system bottlenecks imposed by nonlinear functions). However a significant body of evidence demonstrates that polynomial activations face remarkable barriers to achieving high accuracy, especially for deep networks; on the other hand, research indicates that large and deep neural networks (including networks like VGG, ResNet, LSTMs and transformers on tasks like C0far100 and ImageNet) may be quantized to 8 bits and below (oftentimes to 4 even 2 or bit) with little loss of accuracy. Hence, rather than use polynomial activations, our work suggests that quantization is the more preferred approach. This is a significant observation driving our approach. Below, we show a comparison of the accuracy performance of quantization vs polynomial activation.
Method
Baseline
Polynomial
2-bit Activations
Accuracy
93.29%
71.81%
91.5%
Table 11: Comparison of polynomial activations vs quantization on ResNet32 Cifar10.
Method Bascline
Polynomial 65.17%
3-bit Activations
Accuracy 74.39%
73%
Table 12: Comparison of polynomial activations vs quantization on ResNet18 Cifar100.
Tables 11 and 12 compares the final test accuracy achieved by polynomial activations quantization for 32 Cifarl0 and ResNet18 Cifar100 respectively. These results were obtained from Gaaimella et al.] 2001 Choi et al. (2019); Hoang et al. (2020). As seen, polynomial approximations significantly harm accuracy, while activation quantization, even at very low precision (2-bit/ / 3-bit) results in near lossless accuracy. This phenomenon extends to large datasets such as ImageNet where 4-bit ResNet50 achieves lossless performance Abdolrashidi et al. (2021). whereas polynomial activations incur significant accuracy loss on tiny imagenet Garimella et al.] (2021p. In many of these quantization works, accuracy performance includes the quantization of the weights well the activations; as our approach requires only activation quantization, it may be inferred that even better accuracics may be attained than what those numbers indicate.
In the experiments shown in the main text, we do not do quantized retraining as in the results immediately above (and instead directly apply quantization to pretrained weights; this is known as post-training quantiza- tion), hence there is room for accuracy improvement over what was demonstrated in the main text. This reaffirms the potential of our approach in achieving efficient and accurate secure neural network inference.
Note on truncation errors
All accuracies reported in our paper are obtained by running the protocols in full and account for truncation error resulting from the secure truncation protocol. Notably, in our implementation, we maintain a single separate static scale parameter per layer that is known to both client and server (leaking negligible model information), ensuring that the underlying integer values of secretly shared activations are maintained between [o, 2'4] (this is a common technique when performing quantized inference with limited bitwidth datatypes for acceleration on hardware). As P(catastrophic truncation error) is proportional to the chance that the secret. blinding factor is less than the secret value, the probability of catastrophic error for one truncation is 214-64, This means, there is a 99.98% chance that. all 1,000,000 calls to net with 300,000 ReLUs succeeds. With just 80 bits, Pfcatastrophic error) is 204-80 leading to 99.99959% prob. that 1,000,000,000 calls to a 300,000 ReLU network all succeed. The common off by one errors, like quantization error, has negligible impact on model quality (a similar finding by Huang el al. (2022)). This is a key detail and difference from prior works (which do not maintain a separate scale, significantly inflating catastrophic truncation error probability). Detecting truncation error and retrying them is a topic for future work.
23


Reviews:
[{"review_id": "zLnAEJ5f0V", "reviewer": "Reviewer_iJ91", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n- The paper is well written - the motivation, problem formulation, algorithm and results are all explained well.\n- The paper employs a novel combination of lookup tables/function secret sharing/quantization to make the online phase efficient\n- Extensive experimentation is done (some is missing, see weakness) to indicate the advantages of TABULA in terms of cost savings - communication and runtime majorly.\n\n**Weaknesses**\n- Baseline methods: TABULA relies on quantization so it makes sense to compare with quantized versions of baseline. But results on comparing the accuracy with and without quantization should also be presented. Accuracy comparison is only presented for 8bit TABULA and garbled circuits. Since TABULA relies on quantization, the reader should know how much drop in accuracy to expect because of that.\n- Feasibility of the method for only up-to 12 bits is a major drawback. I think it should be mentioned in the abstract/introduction to set the readers expectations.\n- Regarding storage costs, the claim that TABULA uses comparable storage is not very apparent from the experiments. In a practical setting (say up-to 12 bits) TABULA uses way more storage than garbled circuits, in an 8 bit setting it uses 2x the storage.\n- Are there any networks other than image classification that can be explored for experimentation?\n- Some recent works have emerged using lookup tables as well, authors might like to compare/mention it in their work https://eprint.iacr.org/2024/369", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work introduces TABULA an algorithm for computing nonlinear activation functions efficiently for multiparty secure neural network inference. This paper claims that unlike traditional approaches that rely on garbled circuits for secure inference of non linear activations, TABULA is efficient in terms of communication, storage and runtime. It operates within the Delphi framework and focuses on improving the costs associated with non linear activations. The approach relies on secure lookup from precomputed tables and is done in two phases - offline phase where lookup tables are computed on both server and client side and online phase wherein the non linear activation is performed via table lookup. The lookup table is shared across two parties and contains output to every possible input to that non-linear function. Quantization is used throughout to avoid exponential growth in storage costs. During  online phase the inputs are securely truncated to match the quantized range in the lookup tables. The tables and inputs are secret shared between server and client to avoid either party being aware of the complete input/model weights.\n\nExperiments are presented to evaluate the algorithm and compared to the quantized version of garbled circuits. Results show that TABULA has reduced communication/storage/runtime costs without much degradation in accuracy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weakness", "broader_impact_concerns": "No Concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "RwOSkfWSTD", "reviewer": "Reviewer_BgbH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Based on the survey of prior work it seems that even though lookup tables have demonstrated speedup over garbled circuits in other applications this is the first work to successfully applying them to secure neural network inference by leveraging the fact that neural network activations can be quantized without much loss in accuracy, and this can save memory and make it feasible to construct a lookup table for the entire space.\n\n2. The paper demonstrates that their approach, Tabula, achieves significant improvements over garbled circuits and other state-of-the-art methods in terms of communication, runtime, and storage costs, while maintaining comparable accuracy and security.\n\nWeaknesses:\n\n1. The evaluation shows that there is a significant overhead in terms of both runtime and communication cost at the preprocessing stage for Tabula as compared to the garbled circuits approach. However, I appreciate the fact that the authors have acknowledged this and I believe it is okay to leave the optimization of this stage for future work.\n\n2. The description of the approach is hard to follow due to the long paragraphs and in-line equations in Section 3. I would strongly recommend revising the section, splitting the long paragraphs into multiple short paragraphs and avoiding the use of in-line equations as far as possible. It may also be worth including a description of garbled circuits in the appendix for interested readers who are unfamiliar with them.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes Tabula, a novel protocol for efficiently computing nonlinear activation functions for secure neural network inference, based on secure lookup tables and quantization. The authors describe a secure and practical algorithm for initializing Tabula tables in the offline preprocessing phase, and analyzes its security, communication, and storage properties. Empirical evaluation on various standard neural networks and datasets shows that Tabula achieves significant improvements at inference time over existing methods based on garbled circuits or function secret sharing in terms of communication, runtime, and storage costs, while maintaining comparable accuracy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to the writing changes suggested above, I had the following questions:\n\n1. At the beginning of Section-4 you mention that Tabula is feasible only for precision up to 12 bits but you also say that you use 64-bit fields for Tabula. Can you clarify the difference between precision and field size in this context?\n\n2. Why is the communication cost of Tabula fixed at 16 bytes regardless of the precision of activation inputs?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "baDcIRHB2e", "reviewer": "Reviewer_qKEu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Under given circumstances (with 8-bit quantized activations) Tabula achieves several cost benefits by preprocessing tables for computing the activation functions\n- The theoretical analysis and rationale behind Tabula is well-written \n- The evaluation comparison is comprehensive and the limitations are explicitly stated \n\nWeaknesses:\n- The approach is limited to 8-bit quantization or lower. 16/32-bit representation would require huge memory \n\nThe paper is well written and as an outsider to this topic, I could follow most of the algorithms. Except for the following part:\n- How are vectors P and Q shared between the client and server without revealing $s_0$ and $s_1$?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Tabula offers a new approach to enhancing the efficiency of secure neural network inference, presenting a secure lookup table algorithm as an alternative to garbled circuits. The algorithm is designed to address the communication, storage, and runtime challenges associated with traditional garbled circuits, aiming to provide a more practical solution. Through the use of precomputed lookup tables and quantization techniques, Tabula modestly achieves reductions in communication while offering improved end-to-end inference speed for neural networks compared to existing protocols.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, I think the paper is well-written, and introduces a new technique to solve an important problem. I see that in that the authors have already addressed some of the writing clarity issues in the previous iterations. Thus, I am happy with the paper as it is. (Please note that I'm not an expert on this topic.)", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work introduces an algorithm for computing nonlinear activation functions for multiparty secure neural network inference. The proposed method is well-motivated and the authors have conducted solid comparison to demonstrate the benefit of the method. Reviewers raised several questions about the experiments which are well addressed in the revision. Therefore all the reviewers and AC think the paper is ready to publish in TMLR.
Decision: Accept (poster)