\section{Introduction}
\label{sec:intro}
The problem of privacy preserving machine learning has become increasingly important. Recently, there have been many works that have made rapid strides towards realizing {\em secure inference}~\cite{cryptonets,chet,secureml,minionn,gazelle,delphi,nitin,xonn,ezpc,hycc,nhe1,deepsecure,ball}.
Consider a server that holds the weights $w$ of a publicly known deep neural network (DNN), $F$, that has been trained on private data. A client holds a private input $x$; in a standard machine learning (ML) inference task, the goal is for the client to learn the prediction $F(x,w)$ of the server's model on the input $x$. In secure inference, the inference is performed with the guarantee that the server learns {\em nothing} about $x$ and the client learns nothing about the server's model $w$ beyond what can be deduced from $F(x,w)$ and $x$. 

A solution for secure inference that scales to practical ML tasks would open a plethora of applications based on MLaaS (ML as a Service). Users can obtain value from ML services  without worrying about the loss of their private data, while model owners can effectively monetize their services with no fear of breaches of client data (they never observe private client data in the clear). Perhaps the most important emerging applications for secure inference  are in healthcare where
prior work~\cite{cryptflow,xonn,nitin} has explored secure inference services for privacy preserving medical diagnosis of chest diseases, diabetic retinopathy, malaria, and so on.

Secure inference is an instance of secure 2-party computation (2PC) and cryptographically secure general protocols for 2PC have been known for decades~\cite{Yao,gmw}. 
However, secure inference for practical ML tasks, e.g., ImageNet scale prediction~\cite{imagenet}, is challenging for two reasons: 
a) realistic DNNs use $\mathsf{ReLU}$ activations\footnote{$\mathsf{ReLU}(x)$ is defined as $\max(x,0)$.} that are expensive to compute securely; and b) preserving inference accuracy requires a faithful implementation of secure fixed-point arithmetic.
 All prior works~\cite{cryptonets,secureml,minionn,gazelle,delphi,ball} fail to provide efficient implementation of $\mathsf{ReLU}$s. Although $\mathsf{ReLU}$s can be replaced with approximations that are more tractable for 2PC~\cite{cryptonets,delphi,chet}, this approach results in significant accuracy losses that can degrade user experience. The only known approaches to evaluate $\mathsf{ReLU}$s efficiently require sacrificing security by making the untenable assumption that a non-colluding third party takes part in the protocol~\cite{chameleon,securenn,cryptflow,aby3,quantizednn} or by leaking activations~\cite{nhe2}.
Moreover, some prior works~\cite{secureml,delphi,securenn,aby3,cryptflow} even sacrifice correctness of their fixed-point implementations and the result of their secure execution can sometimes diverge from the expected result, i.e. cleartext execution, in random and unpredictable ways.
Thus, correct and efficient 2PC protocols for secure inference over realistic DNNs remain elusive.
\subsection{Our Contributions}

In this work, we address the above two challenges and build new semi-honest secure 2-party cryptographic protocols for secure computation of DNN inference. 
Our new efficient protocols enable the first secure implementations of ImageNet scale inference that complete in under a minute!
We make three main  contributions:
\begin{tiret}
\item First, we give new protocols for millionaires' and $\mathsf{DReLU}$\footnote{$\mathsf{DReLU}$ is the derivative of $\mathsf{ReLU}$, i.e., $\mathsf{DReLU}(x)$ is $1$ if $x \geq 0$ and $0$ otherwise.} that enable us to securely and efficiently evaluate the non-linear layers of DNNs such as $\mathsf{ReLU}$, $\mathsf{Maxpool}$ and $\mathsf{Argmax}$. \item Second, we provide new protocols for division. Together with new theorems that we prove on fixed-point arithmetic over shares, we show how to evaluate linear layers, such as convolutions, average pool and fully connected layers, faithfully. 
\item Finally, by providing protocols that can work on a variety of input domains, we build a system\footnote{Implementation is available at \url{https://github.com/mpc-msri/EzPC}.}
    ${\textsc{CrypTFlow2}}\xspace$ that supports two different types of Secure and Correct Inference ({\textsc{SCI}}\xspace) protocols where linear layers can be evaluated using either homomorphic encryption ($\textsc{SCI}_{\mathsf{HE}}$) or through oblivious transfer ($\textsc{SCI}_{\mathsf{OT}}$).
\end{tiret}
We now provide more details of our main contributions. 
\\\\
\noindent{\textbf{New millionaires' and $\mathsf{DReLU}$ protocols.}} 
Our first main technical contribution is a novel protocol for the well-known {\em millionaires'} problem~\cite{Yao}, where parties \ensuremath{P_0}\xspace and \ensuremath{P_1}\xspace hold  $\ell-$bit integers $x$ and $y$, respectively, and want to securely compute $x < y$ (or, secret shares of $x<y$).
The theoretical communication complexity of our protocol is $\approx 3\times$ better than the most communication efficient prior millionaires' protocol~\cite{Cou18,Yao,gmw,emp-toolkit,GSV07}.
In terms of round complexity, our protocol executes in $\log \ell$ rounds (e.g. $5$ rounds for $\ell=32$ bits);
see \tableref{comp-mill} for a detailed comparison and \cite{Cou18} for a detailed overview of the costs of other comparison protocols.

Using our protocol for millionaires' problem, we build new and efficient protocols for computing $\mathsf{DReLU}$ for both $\ell-$bit integers (i.e., $\mathbb{Z}_L$, $L = {2^\ell}$) and general rings $\mathbb{Z}_n$.
Our protocol for $\mathsf{DReLU}$ serves as one of the main building blocks for non-linear activations such as $\mathsf{ReLU}$ and $\mathsf{Maxpool}$, as well as division over both input domains.
Providing support for  $\ell-$bit integers $\mathbb{Z}_{L}$ as well as arbitrary rings $\mathbb{Z}_{n}$, allows us to securely evaluate the linear layers (such as matrix multiplication and convolutions) using  the approaches of Oblivious Transfer (OT)~\cite{beaver,secureml} as well as Homomorphic Encryption (HE)~\cite{gentryfhe,gazelle,delphi}, respectively. 
This provides our protocols great flexibility when executing over different network configurations. 
Since all prior work~\cite{secureml,minionn,gazelle,delphi} for securely computing these activations rely on Yao's garbled circuits~\cite{Yao}, our protocols are much more efficient in both settings.
Asymptotically, our $\mathsf{ReLU}$ protocol over $\mathbb{Z}_L$ and $\mathbb{Z}_n$ communicate $\approx 8\times$ and $\approx 12\times$ less bits than prior works~\cite{Yao,secureml,minionn,gazelle,delphi,emp-toolkit} (see \tableref{comp-relu} for a detailed comparison).
Experimentally, our protocols are at least an order of magnitude more performant than prior protocols when computing $\mathsf{ReLU}$ activations at the scale of ML applications.
\\\\
\noindent{\textbf{Fixed-point arithmetic.}} 
The ML models used by all prior works on secure inference are expressed
using fixed-point arithmetic; such models can be obtained from~\cite{tflite,bnn,cryptflow,dfq}. A faithful implementation of fixed-point arithmetic is quintessential to ensure that the secure computation is {\em correct}, i.e., it is {\it equivalent} to the cleartext computation for all possible inputs.
Given a secure inference task $F(x,w)$, some prior works~\cite{secureml,delphi,securenn,aby3,cryptflow} give up on correctness
when implementing division operations and instead compute an approximation $F'(x,w)$. In fixed-point arithmetic, each multiplication requires a division by a power-of-2 and multiplications are used pervasively in linear-layers of DNNs. 
 Moreover, layers like average-pool require division for computing means.
Loss in correctness is worrisome as the errors can accumulate and $F'(x,w)$ can be arbitrarily far from $F(x,w)$.
 Recent work~\cite{delphi} has shown that even in practice the approximations can lead  to significant losses in classification accuracy.

As our next contribution, we provide novel protocols to compute division by power-of-2 as well as division by arbitrary integers that are both correct and efficient. The inputs to these protocols can be encoded over both $\ell-$bit integers $\mathbb{Z}_{L}$ as well as $\mathbb{Z}_{n}$, for arbitrary $n$. 
To the best of our knowledge, the only known approach to compute division correctly is via garbled circuits which we compare with in Table~\ref{tab:comp-avgpool}.
While garbled circuits based protocols require communication which is quadratic in $\ell$ or $\log n$, our protocols are asymptotically better and incur only linear communication. Concretely, for average pool with $7\times 7$ filters and 32-bit integers, our protocols have $\approx 54\times$ less communication.
\\\\
\noindent{\textbf{Scaling to practical DNNs.}} These efficient protocols, help us securely evaluate practical DNNs like \textsf{SqueezeNet}\xspace\   on ImageNet scale classification tasks in under a minute. In sharp contrast, all prior works on secure  2-party inference (\cite{cryptonets,chet,secureml,minionn,gazelle,delphi,nitin,xonn,ezpc,hycc,nhe1,deepsecure,ball}) has been limited to small DNNs on tiny datasets like MNIST and CIFAR.
While MNIST deals with the task of classifying black and white handwritten digits given as $28\times 28$ images into the classes 0 to 9, ImageNet tasks are much more complex: typically $224\times 224$ colored images need to be classified into thousand classes (e.g., agaric, gyromitra, ptarmigan, etc.) that even humans can find challenging .
 Additionally, our work is the first to securely evaluate practical {\em convolutional neural networks} (CNNs) like \textsf{ResNet50}\xspace\ and \textsf{DenseNet121}\xspace; these DNNs are at least an order of magnitude larger than the DNNs considered in prior work, provide over $90\%$ Top-5 accuracy on ImageNet, and have also been shown to predict lung diseases from chest X-ray images~\cite{cryptflow, chestxray2018}.
Thus, our work provides the first implementations of practical ML inference tasks running securely.  Even on the smaller CIFAR scale DNNs, our protocols require an order of magnitude less communication and $20\times$-$30\times$ less time than the state-of-the-art~\cite{delphi} (see  Section~\ref{sec:exp-comparison-prior-work}). 
\\\\
\noindent{\textbf{OT vs HE.}} Through our evaluation, we also resolve the OT vs HE conundrum: 
although the initial works on secure inference~\cite{secureml,minionn} used OT-based protocols for evaluating convolutions, the state-of-the-art protocols~\cite{gazelle,delphi}, which currently provide the best published inference latency, use HE-based convolutions. HE-based secure inference has much less communication than OT but HE requires more computation.
Hence, at the onset of this work, it was not clear to us whether HE-based convolutions would provide us the best latency for ImageNet-scale benchmarks. 

To resolve this empirical question, we implement two classes of protocols, $\textsc{SCI}_{\mathsf{OT}}$ and $\textsc{SCI}_{\mathsf{HE}}$, in {\textsc{CrypTFlow2}}\xspace.
In $\textsc{SCI}_{\mathsf{OT}}$, inputs are in $\mathbb{Z}_{L}$ ($L = 2^\ell$, for a suitable choice of $\ell$). Linear layers such as matrix multiplication and convolution are performed using OT-based techniques~\cite{beaver,secureml}, while the activations such as $\mathsf{ReLU}$, $\mathsf{Maxpool}$ and $\mathsf{Avgpool}$  are implemented using our new protocols over $\mathbb{Z}_{L}$. 
In $\textsc{SCI}_{\mathsf{HE}}$, inputs are encoded in an appropriate prime field $\mathbb{Z}_{n}$ (similar to~\cite{gazelle,delphi}). 
Here, we compute linear layers using homomorphic encryption and the activations  using our protocols over $\mathbb{Z}_{n}$.
In both $\textsc{SCI}_{\mathsf{OT}}$ and $\textsc{SCI}_{\mathsf{HE}}$ faithful divisions after linear layers are performed using our new protocols over corresponding rings. Next, we evaluate ImageNet-scale inference tasks with both $\textsc{SCI}_{\mathsf{OT}}$ and $\textsc{SCI}_{\mathsf{HE}}$ . We observe that in a WAN setting, where communication is a bottleneck, HE-based inference is always faster and in a LAN setting OT and HE are incomparable. 
\begin{table}
  \centering
      \begin{tabular}{|c|c|c|c|}
    \hline
				Layer & Protocol & Comm. (bits) & Rounds \\ \hline \hline
				\multirowcell{4}{Millionaires' \\ on $\{0,1\}^\ell$}
				& GC \cite{Yao, emp-toolkit} & $4\lambda\ell$ & 2 \\ \cline{2-4}
				& GMW$\footnotemark/$GSV~\cite{gmw,GSV07}& $\approx 6\lambda\ell$ & $\log \ell+3$ \\ \cline{2-4}
				& SC3\footnotemark\cite{Cou18} & $> 3\lambda\ell$ & $\approx 4\log^* \lambda$ \\ \cline{2-4}
				& This work ($m = 4$) & $< \lambda \ell + 14\ell $ & $\log {\ell}$\\ \hline \hline
				\multirowcell{5}{Millionaires' \\example \\$\ell = 32$}
				& GC \cite{Yao, emp-toolkit} & 16384 & 2 \\ \cline{2-4}
				& GMW$/$GSV \cite{gmw, GSV07} & 23140 & 8 \\ \cline{2-4}
				& SC3 \cite{Cou18} & 13016 & 15 \\ \cline{2-4}
				& This work ($m = 7$) & 2930 & 5 \\ \cline{2-4}
				& This work ($m = 4$) & 3844 & 5 \\ \hline
			\end{tabular}
 \caption{Comparison of communication with prior work for millionaires' problem. For our protocol, $m$ is a parameter. For concrete bits of communication we use $\lambda=128$. }
\label{tab:comp-mill}
\end{table}
\addtocounter{footnote}{-1}
\footnotetext{Here we state the communication numbers for GMW~\cite{gmw} for a depth-optimized circuit. The circuit that would give the best communication would still have a complexity of $> 2\lambda\ell$ and would additionally pay an inordinate cost in terms of rounds, namely $\ell$.}
\addtocounter{footnote}{1}
\footnotetext{Couteau~\cite{Cou18} presented multiple protocols; we pick the one that has the best communication complexity.}
 \begin{table}
  \centering
      \begin{tabular}{|c|c|c|c|}
    \hline
				Layer & Protocol & Comm. (bits) & Rounds \\ \hline \hline
				\multirowcell{2}{$\mathsf{ReLU}$ for \\$\mathbb{Z}_{2^\ell}$}

				& GC \cite{Yao, emp-toolkit} & $ 8\lambda\ell-4\lambda$ & 2 \\ \cline{2-4}
				& This work & \multirow{1}{*}{ $< \lambda\ell+18\ell$ } & $\log \ell + 2$\\
				 \hline

				\multirowcell{2}{$\mathsf{ReLU}$ for \\general $\mathbb{Z}_n$}

				& GC \cite{Yao, emp-toolkit} & $18\lambda\eta-6\lambda$ & 2 \\ \cline{2-4}
				& This work & $< \frac{3}{2}\lambda (\eta+1) + 31\eta$ & $\log \eta + 4$\\
				\hline \hline

				\multirowcell{2}{$\mathsf{ReLU}$ for \\ $\mathbb{Z}_{2^\ell}$, $\ell = 32$}
				
				& GC \cite{Yao, emp-toolkit} & 32256 & 2 \\ \cline{2-4}
				& This work  & 3298 & 7 \\ \cline{2-4}
				\hline
				
				\multirowcell{2}{$\mathsf{ReLU}$ for \\$\mathbb{Z}_n$, $ \eta = 32$}
				
				& GC \cite{Yao, emp-toolkit} & 72960 & 2 \\ \cline{2-4}
				& This work  & 5288 & 9 \\ \cline{2-4}
				\hline
			\end{tabular}
 \caption{Comparison of communication with garbled circuits for $\mathsf{ReLU}$. We define $\eta = \lceil \log n \rceil$. For concrete bits of communication we use $\lambda=128$. }
\label{tab:comp-relu}
\end{table}
 \begin{table}
  \centering
      \begin{tabular}{|c|c|c|c|}
    \hline
				Layer & Protocol & Comm. (bits) & Rounds \\ \hline \hline
				\multirowcell{2}{$\mathsf{Avgpool}_d$ \\$\mathbb{Z}_{2^\ell}$}

				& GC \cite{Yao, emp-toolkit} & $2\lambda(\ell^2 + 5\ell -3)$ & 2 \\ \cline{2-4}
				& This work &  $< (\lambda + 21) \cdot ( \ell + 3 \delta )$   & $\log (\ell\delta ) + 4$\\
              \hline

				\multirowcell{2}{$\mathsf{Avgpool}_d$  \\ $\mathbb{Z}_n$}

				& GC \cite{Yao, emp-toolkit} & $2\lambda(\eta^2 + 9\eta-3)$ & 2 \\ \cline{2-4}
				& This work & $< (\textstyle\frac{3}{2} \lambda + 34) \cdot (\eta + 2 \delta)$ & $\log (\eta\delta) + 6$\\
             \hline \hline

                \multirowcell{2}{$\mathsf{Avgpool}_{49}$ \\  $\mathbb{Z}_{2^\ell}, \ell = 32$}
				
				& GC \cite{Yao, emp-toolkit} & 302336 & 2 \\ \cline{2-4}
				& This work  & 5570 & 10 \\ \cline{2-4}
				\hline
				
                \multirowcell{2}{$\mathsf{Avgpool}_{49}$  \\ $\mathbb{Z}_n, \eta = 32$}
				
				& GC \cite{Yao, emp-toolkit} & 335104 & 2 \\ \cline{2-4}
				& This work & 7796 & 14 \\ \cline{2-4}
				\hline
			\end{tabular}
 \caption{Comparison of communication with garbled circuits for $\mathsf{Avgpool}_d$. We define $\eta = \lceil \log n \rceil$ and $\delta = \lceil \log (6 \cdot d) \rceil$. For concrete bits of communication we use $\lambda=128$. Choice of $d =49$ corresponds to average pool filter of size $7\times 7$. } \label{tab:comp-avgpool}
\end{table}
 \subsection{Our Techniques}

\noindent\textbf{Millionaires'.} Our protocol for securely computing the millionaires' problem (the bit $x<y$) is based on the following observation (first made in~\cite{GSV07}). 
Let $x = x_1||x_0$ and $y = y_1||y_0$ (where $||$ denotes concatenation and $x_1, y_1$ are strings of the same length). 
Then, $x<y$ is the same as checking if either $x_1<y_1$ or $x_1=y_1$ and $x_0<y_0$. 
Now, the original problem is reduced to computing two millionaires' instances over smaller length strings ($x_1<y_1$ and $x_0<y_0$) and one equality test ($x_1 = y_1$). 
By continuing recursively, one could build a tree all the way where the leaves are individual bits, at which point one could use 1-out-of-2 OT-based protocols to perform the comparison/equality. 
However, the communication complexity of this protocol is still quite large. 
We make several important modifications to this approach. 
First, we modify the tree so that the recursion is done $\log (\ell/m)$ times to obtain leaves with strings of size $m$, for a parameter $m$.
We then use 1-out-of-$2^m$ OT to compute the comparison/equality at the leaves, employing the lookup-table based approach of \cite{DKSSZZ17}.
Second, we observe that by carefully setting up the receiver's and sender's messages in the OT protocols for leaf comparisons and equality, multiple 1-out-of-$2^m$ OT instances can be combined to reduce communication. 
Next, recursing up from the leaves to the root, requires securely computing the $\mathsf{AND}$ functionality\footnote{This functionality takes as input shares of bits $x, y$ from the two parties and outputs shares of $x~\mathsf{AND}~y$ to both parties.}  that uses Beaver bit triples~\cite{beaver}. 
We observe that the same secret value is used in 2 $\mathsf{AND}$ instances.  
Hence, we construct correlated pairs of bit triples using 1-out-of-8 OT protocols~\cite{kkot} to reduce this cost to $\lambda+8$ bits (amortized) per triple, where $\lambda$ is the security parameter and typically $128$.
Some more work is needed for the above technique to work efficiently for the general case when $m$ does not divide $\ell$ or $\ell/m$ is not a power of $2$. 
Finally, by picking $m$ appropriately, we obtain a protocol for millionaires' whose concrete communication (in bits) is nearly $5$ times better than prior work. 
\\

\noindent\textbf{$\mathsf{DReLU}$.}
Let $a$ be additively secret shared as $a_0, a_1$ over the appropriate ring. 
$\mathsf{DReLU}(a)$ is $1$ if $a \geq 0$ and $0$ otherwise; note that $a\geq0$ is defined differently for $\ell-$bit integers and general rings.
Over $\mathbb{Z}_L$, where values are encoded using 2's complement notation, $\mathsf{DReLU}(a) = 1\oplus \mathsf{MSB}(a)$, where $\mathsf{MSB}(a)$ is the most significant bit of $a$.
Moreover,  $\mathsf{MSB}(a) = \mathsf{MSB}(a_0) \oplus \mathsf{MSB}(a_1) \oplus \mathsf{carry}$. 
Here, $\mathsf{carry} = 1$ if $a_0'+a_1' \geq 2^{\ell-1}$, where $a'_0, a'_1$ denotes the integer represented by the lower $\ell-1$ bits of $a_0, a_1$.
We compute this $\mathsf{carry}$ bit using a call to our millionaires' protocol.
Over $\mathbb{Z}_n$, $\mathsf{DReLU}(a) = 1$ if $a \in [0,\lceil n/2 \rceil)$. Given the secret shares $a_0, a_1$, this is equivalent to $(a_0+a_1) \in [0,\lceil n/2 \rceil) \cup [n, \lceil 3n/2 \rceil)$ over integers.
While this can be na\"{\i}vely computed by making 3 calls to the millionaires' protocol, we show that by carefully selecting the inputs to the millionaires' protocol, one can do this with only 2 calls.
Finally, we set things up so that the two calls to millionaires' have correlated inputs that reduces the overall cost to $\approx$ 1.5 instances of millionaires' over $\mathbb{Z}_n$.
\\

\noindent\textbf{Division and Truncation.} As a technical result, we  provide a {\em correct} decomposition of division of a secret ring element in $\mathbb{Z}_L$ or $\mathbb{Z}_n$ by a public integer into division of secret shares by the same public integer and  correction terms (\theoremref{general-division}). 
These correction terms consist of multiple inequalities on secret values. 
As a corollary, we also get a much simpler expression for the special case of {\em truncation}, i.e., dividing $\ell$-bit integers by a power-of-$2$ (\corolref{truncate-int}). 
We believe that the general theorem as well as the corollary can be of independent interest. 
Next, we give efficient protocols for both general division (used for $\mathsf{Avgpool}$, \tableref{comp-avgpool}) as well as division by a power-of-$2$ (used for multiplication in fixed-point arithmetic). The inequalities in the correction term are computed using our new protocol for millionaires' and the division of shares can be done locally by the respective parties. 
Our technical theorem is the key to obtaining secure implementation of DNN inference tasks that are bitwise equivalent to cleartext fixed-point execution.




\subsection{Other Related Work}

Perhaps the first work to consider the secure computation of machine learning inference algorithms was that of~\cite{bost}.
SecureML~\cite{secureml} was the first to consider secure neural network inference and training. Apart from the works mentioned earlier, other works include those that considered malicious adversaries~\cite{helen,mlspdz,leviosa} (for simpler ML models like linear models, regression, and polynomials) as well as specialized DNNs with 1 or 2 bit weights~\cite{xonn,deepsecure,nitin}.
Recently, \cite{edabits} gave protocols for faithful truncation (but not division) over $\ell$-bit integers and prime fields in various adversarial settings. For 2-party semi-honest setting, our protocols have up to $20\times$ less communication for the truncations required in our evaluation.
\cite{RSS19} proposed an HE-based triple generation protocol over $\mathbb{Z}_{2^{\ell}}$, which requires less communication than generating triples using OT.

\subsection{Organisation}
We begin with the details on security and cryptographic primitives used in Section~\ref{sec:prelims} on preliminaries. 
In Section~\ref{sec:comp-protocols} we provide our protocols for millionaires' (Section~\ref{sec:prot-mill}) and $\mathsf{DReLU}$ (Section~\ref{sec:prot-drelu-int},~\ref{sec:prot-drelu-ring}), over both $\mathbb{Z}_L$ and general ring $\mathbb{Z}_n$. In Section~\ref{sec:division}, we present our protocols for division and truncation. We describe the various components of DNN inference  in Section~\ref{sec:secureinference} and show how to construct secure protocols for all these components given our protocols from Sections~\ref{sec:comp-protocols} and ~\ref{sec:division}. We present our implementation details in Section~\ref{sec:impl} and our experiments in Section~\ref{sec:experiments}. Finally, we conclude and discuss future work in \sectionref{conclusion}.

 





















 \section{Preliminaries}
\label{sec:prelims}
\paragraph{Notation.}
For a set $\mathcal{W}$, $w \getsr \mathcal{W}$ denotes sampling an element $w$, uniformly at random from $\mathcal{W}$. $[\ell]$ denotes the set of integers $\{0, \cdots, \ell-1\}$. Let $\ind{b}$ denote the indicator function that is $1$ when $b$ is {\em true} and $0$ when $b$ is {\em false}. 


\subsection{Threat Model and Security}
We provide security in the simulation paradigm~\cite{gmw, canetti00, lindellsim} against a {\em static semi-honest} probabilistic polynomial time (PPT) adversary $\mathcal{A}$. That is, a computationally bounded adversary $\mathcal{A}$ corrupts either \ensuremath{P_0}\xspace or \ensuremath{P_1}\xspace at the beginning of the protocol and follows the protocol specification honestly. 
Security is modeled by defining two interactions: a real interaction where \ensuremath{P_0}\xspace and \ensuremath{P_1}\xspace execute the protocol in the presence of $\mathcal{A}$ and the environment $\mathcal{Z}$ and an ideal interaction where the parties send their inputs to a trusted functionality that performs the computation faithfully. 
Security requires that for every adversary $\mathcal{A}$ in the real interaction, there is an adversary
$\mathcal{S}$ (called the simulator) in the ideal interaction, such that no environment $\mathcal{Z}$ can distinguish between real and ideal interactions. Many of our protocols invoke multiple sub-protocols and we describe these using the \emph{hybrid model}. This is similar to a real interaction, except that sub-protocols are replaced by the invocations of  instances of  corresponding functionalities. A protocol invoking a functionality $\mathcal{F}$ is said to be in ``$\mathcal{F}$-hybrid model.''










\subsection{Cryptographic Primitives}

\subsubsection{Secret Sharing Schemes}
\label{sec:ss}

Throughout this work, we use 2-out-of-2 additive secret sharing schemes over different rings~\cite{shamir,blakeley}. The 3 specific rings that we consider are the field $\mathbb{Z}_2$, the ring $\mathbb{Z}_L$, where $L = 2^\ell$ ($\ell = 32$, typically), and the ring $\mathbb{Z}_n$,  for a positive integer $n$ (this last ring includes the special case of prime fields used in the works of \cite{gazelle,delphi}). We let $\genshare{L}{x}$ denote the algorithm that takes as input an element $x$ in $\mathbb{Z}_L$ and outputs shares over $\mathbb{Z}_L$, denoted by $\share{x}{L}{0}$ and $\share{x}{L}{1}$. 
Shares are generated by sampling random ring elements $\share{x}{L}{0}$ and $\share{x}{L}{1}$, with the only constraint that $\share{x}{L}{0}+\share{x}{L}{1} = x$ (where $+$ denotes addition in $\mathbb{Z}_L$). Additive secret sharing schemes are perfectly hiding, i.e., given a share $\share{x}{L}{0}$ or $\share{x}{L}{1}$, the value $x$ is completely hidden. The reconstruction algorithm $\reconst{L}{\share{x}{L}{0}, \share{x}{L}{1}}$ takes as input the two shares and outputs $x = \share{x}{L}{0}+\share{x}{L}{1}$. Shares (along with their corresponding $\genshare{}{}$ and $\reconst{}{}$ algorithms) are defined in a similar manner for $\mathbb{Z}_2$ and $\mathbb{Z}_n$ with superscripts $B$ and $n$, respectively. We sometimes refer to shares over $\mathbb{Z}_L$ and $\mathbb{Z}_n$ as arithmetic shares and shares over $\mathbb{Z}_2$ as boolean shares.


\subsubsection{Oblivious Transfer}

Let $\kkot{k}{\ell}$ denote the 1-out-of-$k$ Oblivious Transfer (OT) functionality~\cite{bcr1outofnot} (which generalizes 1-out-of-2 OT~\cite{rabinot, eglot}). The sender's inputs to the functionality are the $k$ strings $m_0, \cdots, m_{k-1}$, each of length $\ell$ and the receiver's input is a value $i \in [k]$. 
The receiver obtains $m_i$ from the functionality and the sender receives no output.
 We use the protocols from~\cite{kkot}, which are an optimized and generalized version of the OT extension framework proposed in~\cite{beaverotextension,iknp}. 
This framework allows the sender and receiver,  to ``reduce''  $\lambda^c$ number of oblivious transfers to $\lambda$ ``base'' OTs. We also use the notion of correlated 1-out-of-2 OT~\cite{ALSZ13}, denoted by $\iknpcot{\ell}$. In our context, this is a functionality where the sender's input is a ring element $x$ and the receiver's input is a choice bit $b$. The sender receives a random ring element $r$ as output and the receiver obtains either $r$ or $x+r$ as output depending on $b$.
The protocols for $\kkot{k}{\ell}$ \cite{kkot} and $\iknpcot{\ell}$ \cite{ALSZ13} execute in $2$ rounds and have total communication\footnote{The protocol of $\kkot{k}{\ell}$ \cite{kkot} incurs a communication cost of $\lambda + k\ell$. However, to achieve the same level of security, their security parameter needs to be twice that of $\iknpcot{\ell}$. In concrete terms, therefore, we write the cost as $2\lambda+k\ell$.} of $2\lambda + k\ell$ and $\lambda + \ell$, respectively. Moreover, simpler $\kkot{2}{\ell}$ has a communication of $\lambda+2\ell$ bits \cite{iknp,ALSZ13}.



\subsubsection{Multiplexer and B2A conversion}
\label{sec:mux}

The functionality $\fmux{n}$ takes as input arithmetic shares of $a$ over $n$ and boolean shares of choice bit $c$ from $\party{0}, \party{1}$, and returns shares of $a$ if $c =1$, else returns shares of $0$ over the same ring. 
A protocol for $\fmux{n}$ can easily be implemented by 2 simultaneous calls to $\kkot{2}{\eta}$ and communication complexity is $2(\lambda + 2\eta)$, where $\eta = \lceil \log n \rceil$. 

The functionality $\fBtoA{n}$ (for boolean to arithmetic conversion) takes boolean (i.e., over $\mathbb{Z}_2$) shares as input and gives out arithmetic (i.e., over $\mathbb{Z}_{n}$) shares of the same value as output. It can be realized via one call to $\iknpcot{\eta}$ and hence, its communication is $\lambda+\eta$. For completeness, we provide the protocols realizing $\fmux{n}$ as well as $\fBtoA{n}$ formally in 