  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. 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
8-bit quantized inputs, when computing individual nonlinear functions during
the online phase, experiments show Tabula with 8-bit activations uses between
$280$-$560 \times$ less communication, is over $100\times$ 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 $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.
