PRIVATE INFERENCE IN DEEP NEURAL NETWORK

Abstract

A secure inference over Deep Neural Networks (DNNs) using secure two-party computation to perform privacy-preserving machine learning. The secure inference uses a particular type of comparison that can be used as a building block for various layers in the DNN including, for example, ReLU activations and divisions. The comparison securely computes a Boolean share of a bit representing whether input value x is less than input value y, where x is held by a user of the DNN, and where y is held by a provider of the DNN. Each party computing system parses their input into leaf strings of multiple bits. This is much more efficient than if the leaf strings were individual bits. Accordingly, the secure inference described herein is more readily adapted for using in complex DNNs.

Claims

1. A method for performing secure inference over Deep Neural Networks (DNNs) using secure two-party computation to perform privacy-preserving machine learning such that the provider of the deep neural network does not learn anything about inputs to the deep neural network, and such that the provider of inputs to the deep neural network does not learn anything about weights of the deep neural network beyond that which can be inferred from the output of the deep neural network and the inputs to the deep neural network, the method comprising: performing a comparison that securely computes a Boolean share of a bit representing whether input value x is less than input value y, where x is held by a user of the DNN, and where y is held by a provider of the DNN, the comparison performed by: parsing x into q leaf strings x.sub.q−1 . . . x.sub.0, where each of the q leaf strings is more than one bit, and where x is equal to the concatenation x.sub.q−1∥ . . . ∥x.sub.0; compute shares of inequality 1{x.sub.n<y.sub.n} for each of at least some n from q−1 down to 1, where y is equal to the concatenation y.sub.q−1∥ . . . ∥y.sub.0, by in each case using oblivious transfer; compute shares of equality 1{x.sub.n=y.sub.n} for each of at least some n from q−1 down to 1 also in each case by using oblivious transfer; and recursively calculating shares of inequality of internal nodes according to the following equation: 1{x.sub.C<y.sub.C}=1{x.sub.B<y.sub.B}⊕(1{x.sub.B=y.sub.B}∧1{x.sub.A<y.sub.A} (where x.sub.C=x.sub.B∥x.sub.A, and y.sub.C=y.sub.B∥y.sub.A), and shares of equality of internal nodes until the Boolean share of 1{x<y} is determined; and repeatedly performing the comparison for different inputs to traverse a garbled binary circuit that represents the DNN to thereby obtain a result of the garbled circuit.

2. The method in accordance with claim 1, wherein inputs x and y are each of size bits, and each leaf string is of size m bits, where m divides .

3. The method in accordance with claim 1, wherein inputs x and y are each of size bits, and each leaf string is has a maximum size of m bits, where m does not divide .

4. The method in accordance with claim 1, the parsing comprising parsing so that at least one of the leaf strings of each of the inputs has less than m bits.

5. The method in accordance with claim 1, wherein /m is not a power of 2.

6. The method in accordance with claim 5, the recursively calculating shares comprising first constructing a binary tree with a power of two leaves.

7. The method in accordance with claim 1, the computing shares of inequality 1{x.sub.n<y.sub.n} occurring for each of all n from q−1 down to 1, and the computing shares of equality 1{x.sub.n=y.sub.n} occurring for each of all n from q−1 down to 1.

8. The method in accordance with claim 1, wherein for at least one of the comparisons, the comparison is performed as part of a ReLU activation on a value a∈.sub.L using arithmetic shares of a.

9. The method in accordance with claim 8, where shares of the ReLU activation are obtained by: performing the comparison on the input shares by performing the comparison on all but the most significant bit of a.

10. The method in accordance with claim 1, wherein for at least one of the comparisons, the comparison is performed as part of a division operation.

11. A method for performing secure inference over Deep Neural Networks (DNNs) using secure two-party computation to perform privacy-preserving machine learning such that the provider of the deep neural network does not learn anything about inputs to the deep neural network, and such that the provider of inputs to the deep neural network does not learn anything about weights of the deep neural network beyond that which can be inferred from the output of the deep neural network and the inputs to the deep neural network, the method comprising: performing a comparison that securely computes a Boolean share of a bit representing whether input value x is less than input value y, where x is held by a user of the DNN, and where y is held by a provider of the DNN, the comparison performed by: parsing y into q leaf strings y.sub.q−1 . . . y.sub.0, where each of the q leaf strings is more than one bit, and where y is equal to the concatenation y.sub.q−1∥ . . . ∥y.sub.0; compute shares of inequality 1{x.sub.n<y.sub.n} for each of at least some n from q−1 down to 1, where x is equal to the concatenation x.sub.q−1∥ . . . ∥x.sub.0, by in each case using oblivious transfer; compute shares of equality 1{x.sub.n=y.sub.n} for each of at least some n from q−1 down to 1 also in each case by using oblivious transfer; and recursively calculating shares of inequality of internal nodes according to the following equation: 1{x.sub.C<y.sub.C}=1{x.sub.B<y.sub.B}⊕(1{x.sub.B=y.sub.B}∧1{x.sub.A<y.sub.A} (where x.sub.C=x.sub.B∥x.sub.A, and y.sub.C=y.sub.B∥y.sub.A), and shares of equality of internal nodes until the Boolean share of 1{x<y} is determined; and repeatedly performing the comparison for different inputs to traverse a garbled binary circuit that represents the DNN to thereby obtain a result of the garbled circuit.

12. The method in accordance with claim 11, wherein inputs x and y are each of size bits, and each of multiple leaf string is of size m bits, the computation of shares of inequality 1{x.sub.n<y.sub.n} for each of at least one of the multiple leaf strings of size m bits is performed using $\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$ oblivious transfer.

13. The method in accordance with claim 12, wherein multiple performances of the $\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$ oblivious transfer are performed using a single call.

14. The method in accordance with claim 11, wherein inputs x and y are each of size bits, and each of multiple leaf string is of size m bits, the computation of shares of equality 1{x.sub.n=y.sub.n} for each of at least one of the multiple leaf strings of size m bits is performed using $\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$ oblivious transfer.

15. The method in accordance with claim 14, wherein multiple performances of the $\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$ oblivious transfer are performed using a single call.

16. A computing system for performing secure inference over Deep Neural Networks (DNNs) using secure two-party computation to perform privacy-preserving machine learning such that the provider of the deep neural network does not learn anything about inputs to the deep neural network, and such that the provider of inputs to the deep neural network does not learn anything about weights of the deep neural network beyond that which can be inferred from the output of the deep neural network and the inputs to the deep neural network, the computing system comprising: one or more processing units; computer-readable storage media having thereon computer-executable instructions that are structured such that, if executed by the one or more processing units, the computing system is configured to perform a comparison that securely computes a Boolean share of a bit representing whether input value x is less than input value y, where x is held by a user of the DNN, and where y is held by a provider of the DNN, the comparison performed by: parsing y into q leaf strings y.sub.q−1 . . . y.sub.0, where each of the q leaf strings is more than one bit, and where y is equal to the concatenation y.sub.q−1∥ . . . ∥y.sub.0; compute shares of inequality 1{x.sub.n<y.sub.n} for each of at least some n from q−1 down to 1, where x is equal to the concatenation x.sub.q−1∥ . . . ∥x.sub.0, by in each case using oblivious transfer; compute shares of equality 1{x.sub.n=y.sub.n} for each of at least some n from q−1 down to 1 also in each case by using oblivious transfer; and recursively calculating shares of inequality of internal nodes according to the following equation: 1{x.sub.C<y.sub.C}=1{x.sub.B<y.sub.B}⊕(1{x.sub.B=y.sub.B}∧1{x.sub.A<y.sub.A} (where x.sub.C=x.sub.B∥x.sub.A, and y.sub.C=y.sub.B∥y.sub.A), and shares of equality of internal nodes until the Boolean share of 1{x<y} is determined; and repeatedly performing the comparison for different inputs to traverse a garbled binary circuit that represents the DNN to thereby obtain a result of the garbled circuit.

17. The computing system in accordance with claim 16, wherein inputs x and y are each of size bits, and each of multiple leaf string is of size m bits, the computation of shares of inequality 1{x.sub.n<y.sub.n} for each of at least one of the multiple leaf strings of size m bits is performed using $\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$ oblivious transfer.

18. The computing system in accordance with claim 17, wherein multiple performances of the $\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$ oblivious transfer are performed using a single call.

19. The computing system in accordance with claim 16, wherein inputs x and y are each of size bits, and each of multiple leaf string is of size m bits, the computation of shares of equality 1{x.sub.n=y.sub.n} for each of at least one of the multiple leaf strings of size m bits is performed using $\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$ oblivious transfer.

20. The computing system in accordance with claim 19, wherein multiple performances of the $\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$ oblivious transfer are performed using a single call.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0013] In order to describe the manner in which the above-recited and other advantages and features can be obtained, a more particular description of the subject matter briefly described above will be rendered by reference to specific embodiments which are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments and are not therefore to be considered to be limiting in scope, embodiments will be described and explained with additional specificity and details through the use of the accompanying drawings in which:

[0014] FIG. 1 illustrates an environment in which the principles described herein in which a first party computing system and a second party computing system perform secure two-party computation over a Deep Neural Network (DNN);

[0015] FIG. 2A illustrates a process performed by the first party computing system to compute its share of 1{x.sub.B<y.sub.B};

[0016] FIG. 2B illustrates a process performed by the second party computing system to compute its share of 1{x.sub.B<y.sub.B};

[0017] FIG. 3 shows the improvement of our ReLU the protocols described herein over garbles circuits in both LAN and WAN settings; and

[0018] FIG. 4 illustrates an example computing system that may represent an example of the first party computing system and the second party computing system of FIG. 1.

DETAILED DESCRIPTION

1. Introduction

[0019] Embodiments disclosed herein relate to secure inference over Deep Neural Networks (DNNs) using secure two-party computation to perform privacy-preserving machine learning. This privacy means that the provider of the deep neural network does not learn anything about inputs to the deep neural network, and the provider of inputs to the deep neural network does not learn anything about weights of the deep neural network beyond that which can be inferred from the output of the deep neural network and the inputs to the deep neural network.

[0020] The secure inference uses a particular type of comparison that can be used as a building block for various layers in the DNN including, for example, ReLU activations and divisions. The comparison securely computes a Boolean share of a bit representing whether input value x is less than input value y, where x is held by a user of the DNN, and where y is held by a provider of the DNN.

[0021] A computing system of one party to the comparison parses x into q leaf strings x.sub.q−1 . . . x.sub.0, where each of the q leaf strings is more than one bit, and where x is equal to the concatenation x.sub.q−1∥ . . . ∥x.sub.0. Meanwhile the computing system of the second party parses y into q leaf strings y.sub.q−1 . . . y.sub.0, where each of the q leaf strings is more than one bit, and where x is equal to the concatenation y.sub.q−1∥ . . . ∥y.sub.0. Note that each leaf string constitutes multiple bits. This is much more efficient than if the leaf strings were individual bits. Accordingly, the secure inference described herein is more readily adapted for using in complex DNNs.

[0022] Each party computing system then computes shares of inequality 1{x.sub.n<y.sub.n} for each of at least some n from q−1 down to 1, where y is equal to the concatenation y.sub.q−1∥ . . . ∥y.sub.0, by in each case using oblivious transfer. In addition, the systems computes their respective shares of equality 1{x.sub.n=y.sub.n} for each of at least some n from q−1 down to 1 also in each case by using oblivious transfer. The systems recursively calculates their respective shares of inequality of internal nodes according to the following equation: 1{x.sub.C<y.sub.C}=1{x.sub.B<y.sub.B}⊕(1{x.sub.B=y.sub.B}∧1{x.sub.A<y.sub.A} (where x.sub.C=x.sub.B∥x.sub.A, and y.sub.C=y.sub.B∥y.sub.A), and their respective shares of equality of internal nodes until their respective Boolean share of 1{x<y} is determined.

[0023] This comparison can be performed at many layers in the DNN to thereby traverse the garbled binary circuit that represents the DNN. Furthermore, each party computing system has access to only their respective share of the information at each internal node in the garbled circuit. Accordingly, the computing systems mutually perform the DNN layers in a manner that their respective data input into the process (e.g., the training data or the evaluation data for the first party computing system, and the weights for the second party computing system) are kept from being disclosed to the opposite party. Thus, privacy is preserved.

[0024] A solution for secure inference such as the one described herein that scales to practical machine learning (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 offer their services with no fear of breaches of client data (they never observe private client data in the clear).

[0025] Secure inference is an instance of secure 2-party computation (2PC) and cryptographically secure general protocols for 2PC have been known for decades [31, 62]. However, secure inference for practical ML tasks, e.g., ImageNet scale prediction [25], is challenging for two reasons: a) realistic DNNs use ReLU activations (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. Conventional implementations [6, 30, 42, 47, 48, 50] of ReLUs can include replacing the activation with approximations that are more tractable for 2PC [23, 30, 48], which his approach results in significant accuracy losses that can degrade user experience. The only approaches known to the inventors to evaluate ReLUs efficiently require sacrificing security by making the untenable assumption that a non-colluding third party takes part in the protocol [7, 44, 49, 55, 60] or by leaking activations [13]. Moreover, some prior works [44, 48-50, 60] 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.

[0026] 1.1 Our Contribution

[0027] 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:

[0028] First, we give a new comparison protocol that enables us to securely and efficiently evaluate the non-linear layers of DNNs such as ReLU, Maxpool and Argmax.

[0029] Second, we provide new protocols for division. Together with new theorems that we prove on fixed-point arithmetic overshares, we show how to evaluate linear layers, such as convolutions, average pool and fully connected layers, faithfully.

[0030] Finally, by providing protocols that can work on a variety of input domains, we build a system PIE that supports two different types of secure inference protocols where linear layers can be evaluated using either homomorphic encryption (PIE.sub.HE) or through oblivious transfer (PIE.sub.OT).

[0031] We now provide more details of our main contributions.

[0032] New millionaires' protocol. Our first main technical contribution is a novel protocol for the well-known millionaires' problem [62], where parties P.sub.0 and P.sub.1 hold -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 ≈3× better than the most communication efficient prior millionaire's protocol [22, 28, 31, 61, 62]. In terms of round complexity, our protocol executes in log rounds (e.g. 5 rounds for =32 bits); this is much better than prior works except for those based on Yao's garbled circuits that require optimal 2 rounds, but have prohibitively high communication complexity (see Table 1 for a detailed comparison).

TABLE-US-00001 TABLE 1 Comparison of communication with prior work for millionaire's problem. For our protocol, m is a parameter. For concrete bits of communication we use λ = 128. Layer Protocol Comm. (bits) Rounds Millionaire's GC [61, 62] 4λ  2 on {0, 1}  GMW.sup.3/GSV [28, 31] ≈6λ  log   + 3 SC3.sup.4[22] >3λ  ≈4 log* λ This work (m = 4) <λ   + 14  log  Millionaire's GC [61, 62] 16384 2 example GMW/GSV [28, 31] 23140 8  = 32 SC3 [22] 13016 15  This work (m = 7) 2930 5 This work (m = 4) 3844 5

[0033] Under GMW.sup.3, we state the communication numbers for GWM [31] for a depth-optimized circuit. The circuit that would give the best communication would still have a complexity of >2λ and would additionally pay an inordinate cost in terms of rounds, namely . Further, under SC3.sup.4, Couteau [22] presented multiple protocols; we compare against the one that has the best communication complexity.

[0034] Using our protocol for millionaire's problem, we build new and efficient protocols for computing non-linear activations such as ReLU and Maxpool for both -bit integers (i.e., Z.sub.L, L=) and general rings Z.sub.n. Providing support for -bit integers Z.sub.L, as well as arbitrary rings Z.sub.n, allow us to securely evaluate the linear layers (such as matrix multiplication and convolutions) using the approaches of Oblivious Transfer (OT) [8, 50] as well as Homomorphic Encryption (HE) [29, 42, 48], respectively. This provides our protocols great flexibility when executing over different network configurations. Since all prior work [42, 47, 48, 50] known to the inventors for securely computing these activations rely on Yao's garbled circuits [62], our protocols are much more efficient in both settings. Asymptotically, our ReLU protocol over Z.sub.L, and Z.sub.n communicate 8× and 12× less bits than prior works [42, 47, 48, 50, 61, 62] (see Table 2 for a detailed comparison). Experimentally, our protocols are at least an order of magnitude more performant than prior protocols when computing ReLU activations at the scale of ML applications.

TABLE-US-00002 TABLE 2 Comparision of communication with Garbled Circuits for ReLU. We define η = ┌log n┐. For concrete bits of communication we use λ = 128. Layer Protocol Comm. (bits) Rounds ReLU GC [61, 62] 8λ  − 4λ 2 This work <λ  + 18  log   + 4 ReLU for GC [61, 62] 18λη − 6λ 2 general .sub.n This work [00001]$<\frac{3}{2}\lambda \left(\eta +1\right)+31\eta$ log η + 4 ReLU for GC [61, 62] 32256 2 ,  = 32 This work 3298 7 ReLU for GC [61, 62] 72960 2 .sub.n, η = 32 This work 5288 9

[0035] Fixed-point arithmetic. The ML models used by all prior works known to the inventors on secure inference are expressed using fixed-point arithmetic; such models can be obtained from [38, 41, 44, 51]. A faithful implementation of fixed-point arithmetic is quintessential to ensure that the secure computation is correct, i.e., it is equivalent to the cleartext computation for all possible inputs. Given a secure inference task F (x,w), some prior works [44, 48-50, 60] 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 [48] has shown that even in practice the approximations can lead to significant losses in classification accuracy.

[0036] 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 -bit integers Z.sub.L as well as Z.sub.n, for arbitrary n. The only known approach to compute division correctly is via garbled circuits which we compare with in Table 3. While garbled circuits based protocols require communication which is quadratic in or log n, our protocols are asymptotically better and incur only linear communication. Concretely, for average pool with 7×7 filters and 32-bit integers, our protocols have 54× less communication.

TABLE-US-00003 TABLE 3 Comparision of communication with Garbled Circuits for Avgpool.sub.d. We define η = ┌log n┐ and δ = ┌log(6 .Math. d)┐. For concrete bits of communication we use λ = 128. Choice of d = 49 corresponds to average pool filter of size 7 × 7. Layer Protocol Comm. (bits) Rounds Avgpool.sub.d GC [61, 62] 2λ( .sup.2 + 5   − 3)  2 This work <(λ + 21) .Math. (  + 3δ) log( δ) + 4 Avgpool.sub.d GC [61, 62] 2λ(η.sup.2 + 9η − 3)  2 .sub.n This work [00002]$<\frac{3}{2}\lambda \left(\eta +34\right).Math.\left(\eta +2\delta \right)$ log(ηδ) + 6 Avgpool.sub.49 GC [61, 62] 302336  2 ,  = 32 This work 5570 10 Avgpool.sub.49 GC [61, 62] 335104  2 .sub.n, η = 32 This work 7796 14

[0037] Scaling to practical DNNs. These efficient protocols, help us securely evaluate practical DNNs like SqueezeNet on ImageNet scale classification tasks in under a minute. In sharp contrast, all prior works on secure 2-party inference ([4, 6, 14, 18, 20, 23, 30, 42, 47, 48, 50, 54, 56]) 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×28 images into the classes 0 to 9, ImageNet tasks are much more complex: typically 224×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 convolutional neural networks (CNNs) like ResNet50 and DenseNet121; 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 [44, 64]. Thus, our work provides the first implementations of practical ML inference tasks running securely. Even on the smaller MNIST/CIFAR scale DNNs, our protocols require an order of magnitude less communication and significantly outperform the state-of-the-art [42, 48] in both LAN and WAN settings (see Table 5 in Section 7.2).

[0038] OT vs HE. Through our evaluation, we also resolve the OT vs HE conundrum: although the initial works on secure inference [47, 50] used OT-based protocols for evaluating convolutions, the state-of-the-art protocols [42, 48], which currently provide the best published inference latency, use HE-based convolutions. HE-based secure inference has much less communication than OT but HE's computation increases with the sizes of convolutions. Since practical DNNs have large Gigabyte-sized convolutions, at the onset of this work, it was not clear to us whether HE-based convolutions would provide us the best latency in practice.

[0039] To resolve this empirical question, we implement a cryptographic library PIE that provides two classes of protocols, PIE.sub.OT and PIE.sub.HE. In PIE.sub.OT, inputs are in Z.sub.L (L=, for a suitable choice of ). Linear layers such as matrix multiplication and convolution are performed using OT-based techniques [8, 50], while the activations such as ReLU, Maxpool and Avgpool are implemented using our new protocols over Z.sub.L. In PIE.sub.HE, inputs are encoded in an appropriate prime field Z.sub.n. Here, we compute linear layers using homomorphic encryption and the activations using our protocols over Z.sub.n. In both PIE.sub.OT and PIE.sub.HE faithful divisions after linear layers are performed using our new protocols over corresponding rings. Next, we evaluate ImageNet-scale inference tasks with both PIE.sub.OT and PIE.sub.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.

[0040] 1.2 Our Techniques

[0041] Millionaires'. Our protocol for securely computing the millionaire's problem (the bit x<y) uses the following observation (previously made in [28]). Let x=x.sub.1∥x.sub.0 and y=y.sub.1∥y.sub.0 (where ∥ denotes concatenation and x.sub.1,y.sub.1 are strings of the same length). Then, x<y is the same as checking if either x.sub.1<y.sub.1 or x.sub.1=y.sub.1 and x.sub.0<y.sub.0. Now, the original problem is reduced to computing two millionaires' instances over smaller length strings (x.sub.1<y.sub.1 and x.sub.0<y.sub.0) and one equality test (x.sub.1=y.sub.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.

[0042] We make several important modifications to this approach. First, we modify the tree so that the recursion is done log(/m) times to obtain leaves with strings of size m, for a parameter m. We then use 1-out-of-2.sup.m OT to compute the comparison/equality at the leaves. 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 AND functionality that uses Beaver bit triples [8] (This functionality takes as input shares of bits x, y from the two parties and outputs shares of x AND y to both parties). Here, the AND function takes as input shares of bits x, y from the two parties and output shares of x AND y to both parties. To the best of our knowledge, prior work required a cost of 2λ bits per triple [5, 24] (where λ is the security parameter and typically 128). Now, since the same secret shared value is used in 2 AND instances, we construct correlated pairs of bit triples using 1-out-of-8 OT protocols [43] to reduce this cost to λ+8 bits (amortized) per triple. Finally, by picking m appropriately, we obtain a protocol for millionaires' whose concrete communication (in bits) is nearly 5 times better than prior work.

[0043] ReLU activation. The function ReLU(a) is defined as a.Math.ReLU′(a), where ReLU′(a)=1 if a>0 and 0 otherwise. Hence, computing ReLU reduces to computing ReLU′(a). Let a be additively secret shared as a.sub.0, a.sub.1 over the appropriate ring. Note that a>0 is defined differently for -bit integers (i.e., Z.sub.L) and general rings Z.sub.n. Over Z.sub.L, ReLU′(a)=1⊕MSB(a), where MSB(a) is the most significant bit of a. Moreover, MSB(a)=MSB(a.sub.0)⊕MSB(a.sub.1)⊕carry. Here, carry=1 if a.sub.0′+a.sub.1′≥, where a.sub.0′, a.sub.1′ denotes the integer represented by the lower −1 bits of a.sub.0, a.sub.1. We compute this carry bit using a call to our millionaires' protocol. Over Z.sub.n, ReLU′(a)=1 if a∈[0, ┌n/2┐). Given the secret shares a.sub.0, a.sub.1, this is equivalent to (a.sub.0+a.sub.1)∈[0, ┌n/2┐)∪[n, ┌3n/2┐) over integers. While this can be naï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.

[0044] Division and Truncation. As a technical result, we provide a correct decomposition of division of a secret ring element in Z.sub.L or Z.sub.n by a public integer into division of secret shares by the same public integer and correction terms (Theorem 4.1). 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 truncation, i.e., dividing -bit integers by a power-of-2 (Corollary 4.2). 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 Avgpool, Table 3) 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.

[0045] 1.3 Organization

[0046] We begin with the details on security and cryptographic primitives used in Section 2 on preliminaries. In Section 3 we provide our protocols for millionaires' (Section 3.1) and ReLU′ (Section 3.2, 3.3), over both Z.sub.L, and general ring Z.sub.n. In Section 4, we present our protocols for general division, as well as the special case of division by power-of-2. We describe the various components that go into a neural network inference algorithm in Section 5 and show how to construct secure protocols for all these components given our protocols from Sections 3 and 4. We present our implementation details in Section 6 and our experiments in Section 7. We conclude discussion of these general principles in Section 8. Section 9 describes a computing system that may employ the principles described herein. Section 10 is an appendix. Section 11 is a bibliography.

2. Preliminaries

[0047] Notation. Let λ be the computational security parameter and negl(λ) denote a negligible function in λ. For a set W,

[00003]$w\stackrel{\$}{\leftarrow }{W}^{\prime }$

denotes sampling an element w, uniformly at random from W. [] denotes the set of integers {1, . . . , }. Let 1{b} denote the indicator function that is 1 when b is true and 0 when b is false.

[0048] 2.1 Threat Model and Security

[0049] We provide security in the simulation paradigm [19, 31, 46] against a static semi-honest probabilistic polynomial time (PPT) adversary . That is, a computationally bounded adversary corrupts either P.sub.0 or P.sub.1 at the beginning of the protocol and follows the protocol specification honestly. Security is modeled by defining two interactions: a real interaction where P.sub.0 and P.sub.1 execute the protocol in the presence of and the environment 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 in the real interaction, there is an adversary (called the simulator) in the ideal interaction, such that no environment can distinguish between real and ideal interactions. Many of our protocols invoke multiple sub-protocols and we describe these using the 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 is said to be in “-hybrid model.”

[0050] 2.2 Cryptographic Primitives

[0051] 2.2.1 Secret Sharing Schemes. Throughout this work, we use 2-out-of-2 additive secret sharing schemes over different rings [12, 58]. The 3 specific rings that we consider are the field .sub.2, the ring .sub.L, where L= (=32, typically), and the ring .sub.n, for a positive integer n (this last ring includes the special case of prime fields used in the works of [42, 48]). We let Share.sup.L (x) denote the algorithm that takes as input an element x in .sub.L, and outputs shares over .sub.L, denoted by x.sub.0.sup.L and x.sub.1.sup.L. Shares are generated by sampling random ring elements x.sub.0.sup.L and x.sub.1.sup.L, with the only constraint that x).sub.0.sup.L+x.sub.1.sup.L=x (where + denotes addition in .sub.L). Additive secret sharing schemes are perfectly hiding, i.e., given a share x.sub.0.sup.L or x.sub.1.sup.L, the value x is completely hidden. The reconstruction algorithm Reconst.sup.L (x.sub.0.sup.L, x.sub.1.sup.L) takes as input the two shares and outputs x=x.sub.0.sup.L+x.sub.1.sup.L. Shares (along with their corresponding Share( ) and Reconst( ) algorithms) are defined in a similar manner for .sub.2 and .sub.n with superscripts B and n, respectively. We sometimes refer to shares over .sub.L and .sub.n as arithmetic shares and shares over .sub.2 as boolean shares.

[0052] 2.2.2 Oblivious Transfer. Let

[00004]$\left(\begin{array}{c}k\\ 1\end{array}\right)-O{T}_{\ell }$

denote the 1-out-of-k Oblivious Transfer (OT) functionality [17] (which generalizes 1-out-of-2 OT [26, 53]). The sender's inputs to the functionality are the k strings m.sub.1, . . . , m.sub.k, each of length and the receiver's input is a value i∈[k]. The receiver obtains m.sub.i from the functionality and the sender receives no output. We use the protocols from [43], which are an optimized and generalized version of the OT extension framework proposed in [9, 40]. This framework allows the sender and receiver, to “reduce” λ.sup.c number of oblivious transfers to λ “base” OTs in the random oracle model [11] (for any constant c>1). We also use the notion of correlated 1-out-of-2 OT [5], denoted by

[00005]$\left(\begin{array}{c}k\\ 1\end{array}\right)-{\mathrm{COT}}_{\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

[00006]$\begin{array}{cc}\left(\begin{array}{c}k\\ 1\end{array}\right)-{\mathrm{OT}}_{\ell }& \left[43\right]\end{array}$$\mathrm{and}$$\begin{array}{cc}\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{COT}}_{\ell }& \left[5\right]\end{array}$

execute in 2 rounds and have total communication of 2λ+k and λ+, respectively. Moreover, simpler

[00007]$\left(\begin{array}{c}2\\ 1\end{array}\right)-O{T}_{\ell }$

has a communication of λ+2 bits [5, 40] (The protocol of

[00008]$\begin{array}{cc}\left(\begin{array}{c}k\\ 1\end{array}\right)-O{T}_{\ell }& \left[43\right]\end{array}$

incurs a communication cost of λ+k. However, to achieve the same level of security, their security parameter needs to be twice that of

[00009]$\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{COT}}_{\ell }.$

In concrete terms, therefore, we write the cost as 2λ+k).

[0053] 2.2.3 Multiplexer and B2A conversion. The functionality .sub.MUX.sup.n takes as input arithmetic shares of a over n and boolean shares of choice bit c from P.sub.0, P.sub.1, and returns shares of a if c=1, else returns shares of 0 over the same ring. A protocol for .sub.MUX.sup.n can easily be implemented by 2 simultaneous calls to

[00010]$\left(\begin{array}{c}2\\ 1\end{array}\right)-O{T}_{\eta }$

and communication complexity is 2(λ+2η), where η=┌log n┐.

[0054] The functionality .sub.B2A.sup.n (for boolean to arithmetic conversion) takes boolean (i.e., over .sub.2) shares as input and gives out arithmetic (i.e., over .sub.n) shares of the same value as output. It can be realized via one call to

[00011]$\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{COT}}_{\eta }$

and hence, its communication is λ+η. For completeness, we provide the protocols realizing .sub.MUX.sup.n as well as .sub.B2A.sup.n formally in Appendix A.3 and Appendix A.4, respectively.

[0055] 2.2.4 Homomorphic Encryption. A homomorphic encryption of x allows computing encryption of f (x) without the knowledge of the decryption key. In this work, we require an additively homomorphic encryption scheme that supports addition and scalar multiplication, i.e. multiplication of a ciphertext with a plaintext. We use the additively homomorphic scheme of BFV [16, 27] (the scheme used in the recent works of Gazelle [42] and Delphi [48]) and use the optimized algorithms of Gazelle for homomorphic matrix-vector products and homomorphic convolutions. The BFV scheme uses the batching optimization [45, 59] that enables operation on plaintext vectors over the field .sub.n, where n is a prime plaintext modulus of the form 2KN+1, K is some positive integer and N is scheme parameter that is a power-of-2.

3. Millionaire's and ReLU′ Protocols

[0056] In this section, we provide our protocols for millionaire's problem and ReLU′(a) (defined to be 1 if a>0 and 0 otherwise) when the inputs are bit signed integers as well as elements in general rings of the form .sub.n (including prime fields). Our protocol for Millionaire's problem invokes instances of .sub.AND that takes as input Boolean shares of values x,y∈{0, 1} and returns boolean shares of x∧y. We discuss efficient protocols for .sub.AND in Appendix A.1 and A.2

[0057] 3.1 Protocol for Millionaires'

[0058] In the Yao Millionaires' problem, party P.sub.0 holds x and party P.sub.1 holds y and they wish to learn boolean shares of 1{x<y}. FIG. 1 illustrates an environment 100 in which the learning occurs and includes first party computing system 101 owned by P.sub.0 and a second party computing system 102 owned by P.sub.1. The first party computing system 101 holds input x, whereas the second party computing system 102 holds input y. Each of the computing systems 101 and 102 may be structured as described below for the computing system 400 of FIG. 4.

[0059] As represented by arrow 121, the first party computing system 101 provides its input x to the two-party computation module 110. Also, as represented by arrow 122, the second party computing system 102 provides its input y to the two-party computing module 110. As represented by arrows 131 and 132, the two-party computation module 110 outputs a first share 111 of the value 1{x<y} to the first party computing system 101, and outputs a second share 112 of the value 1{x<y} to the second party computing system 102. At this point, the first and second party computing systems 101 and 102 could not independently reconstruct the value 140 (1{x<y}) unless they acquired the share they do not have from the other party. Thus, unless the two computing systems 101 and 102 were to share their shares (as represented by arrows 141 and 142), the result of the computation remains secure.

[0060] Here, x and y are -bit unsigned integers. We denote this functionality by . Our protocol for builds on the following observation (Equation 1) that was also used in [28].

1{x<y}=1{x.sub.1<y.sub.1}⊕(1{x.sub.1=y.sub.1}∧1{x.sub.0<y.sub.0}),  (1)

where, x=x.sub.1∥x.sub.0 and y=y.sub.1|y.sub.0.

[0061] Let m be a parameter and M=2.sup.m. First, for ease of exposition, we consider the special case when m divides and q=/m is a power of 2. FIG. 2 illustrates the an general process flow that each of the two computing systems would employ. We describe our protocol for millionaire's problem in this setting formally in Algorithm 1. We use Equation 1 above, recursively log q times to obtain q leaves of size m bits. For example, That is, let x=x.sub.q−1∥ . . . ∥x.sub.0 and y=y.sub.q−1∥ . . . ∥y.sub.0 (where every x.sub.1,y.sub.1∈{0, 1}.sup.m).

[0062] Now, we compute the shares of the inequalities and equalities of strings at the leaf level using

[00012]$\left(\begin{array}{c}M\\ 1\end{array}\right)-\mathrm{OT}1$

(steps 9 and 10, resp.). Next, we compute the shares of the inequalities (steps 14 & 15) and equalities (step 16) at each internal node upwards from the leaf using Equation 1. Value of inequality at the root gives the final output.

TABLE-US-00004 Algorithm 1 Millionaires′,  : Input: P.sub.0, P.sub.1 hold x ∈ {0, 1  and y ∈ {0, 1 , respectively. Output: P.sub.0, P.sub.1 learn   1{x < y}  .sub.0.sup.B and  1{x < y}  .sub.1.sup.B, respectively. 1: P.sub.0 parses its input as x = x.sub.q−1 || . . . || x.sub.0 and P.sub.1 parses its input as y = y.sub.q−1 || . . . ||y.sub.0, where x.sub.i, y.sub.i ∈ {0, 1}.sup.m, q =  /m. 2: Let M= 2.sup.m. 3: for j= {0,...,q -1} do 4:  [00013]$P_0\mathrm{samples}{.Math.{\mathrm{lt}}_{0,j}.Math.}_0^B,{.Math.{\mathrm{eq}}_{0,j}.Math.}_0^B\stackrel{\$}{\leftarrow }\left\{0,1\right\}.$ 5:  for k= {0, . . . , M-1} do 6:   P.sub.0 sets s.sub.j,k =  lt.sub.0,j  .sub.0.sup.B ⊕ {x.sub.j < k}. 7:   P.sub.0 sets t.sub.j,k =  eq.sub.0,j  .sub.0.sup.B ⊕ {x.sub.j = k}. 8:  end for 9:  P.sub.0 & P.sub.1 invoke an instance of [00014]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$  where P.sub.0 is the sender with inputs {s.sub.j,k}.sub.k and P.sub.1 is the receiver with input y.sub.j. P.sub.1 sets its output as  lt.sub.0,j  .sub.1.sup.B. 10:  P.sub.0 & P.sub.1 invoke an instance of [00015]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$  where P.sub.0 is the sender with inputs {t.sub.j,k}.sub.k and P.sub.1 is the receiver with input y.sub.j. P.sub.1 sets its output as  eq.sub.0,j  .sub.1.sup.B. 11: end for 12: for i= {1, . . . , log q} do 13:  for j = {0, . . . , (q/2.sup.i) − 1} do 14:    For b ∈ {0, 1}, P.sub.b invokes  .sub.AND with inputs   lt.sub.i−1,2j  .sub.b.sup.B and eq.sub.i−1,2j+1  .sub.b.sup.B to learn output  temp  .sub.b.sup.B. 15:    P.sub.b sets  lt.sub.i,j  .sub.b.sup.B =  lt.sub.i−1,2j+1  .sub.b.sup.B ⊕ temp  .sub.b.sup.B. 16:    For b ∈ {0, 1}, P.sub.b invokes  .sub.AND with inputs   eq.sub.i−1,2j  .sub.b.sup.B and eq.sub.i−1,2j+1  .sub.b.sup.B to learn output  eq.sub.i,2  .sub.b.sup.B. 17:   end for 18: end for 19: For b ∈ {0, 1}, P.sub.b outputs  lt.sub.log n,0  .sub.b.sup.B.

[0063] Let us take a concrete example to further clarify with respect to FIGS. 2A and 2B. FIG. 2A shows the processing associated with the first party computing system. FIG. 2B shows the processing associated with the second party computing system. Suppose that the length of the input f is 16, and that the length of each leaf string m will be 4. Here M will be 2.sup.4 or 16. Furthermore, q=/m, which equals 16/4 or 4. Equation 1 will be performed recursively log.sub.2 q times, or in other words log.sub.2 4 times, or in other words twice. This is the special cases since m divides l, and since q is a power of 2 (2.sup.2). Now let us discuss an example input x=1001010110000001, and an example input y=1001010110001000.

[0064] In line 1 of Algorithm 1, and referring to the arrow 201A of FIG. 2A, P.sub.0 parses x to obtain x.sub.3=1001, x.sub.2=0101, x.sub.1=1000, and x.sub.0=0001. Also in line 1 and referring to the arrow 201B of FIG. 2B, P.sub.1 parses y to obtain y.sub.3=1001, y.sub.2=0101, y.sub.1=1000, and y.sub.0=1000. Note that the value of 1{x<y} is binary 1 since x is indeed less than y, but neither party knows this at least at this stage, and neither party will ever know this if this is not the final output of the garbled circuit representing the DNN. Instead, each party will only learn their respective Boolean share of 1{x<y}.

[0065] In line 9, using

[00016]$\left(\begin{array}{c}16\\ 1\end{array}\right)-O{T}_1$

each party learns their Boolean share of 1{x.sub.3<y.sub.3}, 1{x.sub.2<y.sub.2}, 1{x.sub.1<y.sub.1}, and 1{x.sub.0<y.sub.0}, or in other words, their respective Boolean share of 0, 0, 0, and 1 since only 1{x.sub.0<y.sub.0} is equal to one. As represented by arrow 211A of FIG. 2A, the first party computing system learns its shares 221A of 1{x.sub.3<y.sub.3}, 1{x.sub.2<y.sub.2}, 1{x.sub.1<y.sub.1}, and 1{x.sub.0<y.sub.0}. As represented by arrow 211B of FIG. 2B, the second party computing system also learns its shares 221B of 1{x.sub.3<y.sub.3}, 1{x.sub.2<y.sub.2}, 1{x.sub.1<y.sub.1}, and 1{x.sub.0<y.sub.0}. Again, each party only knows Boolean shares of these values, and thus continues to be obvious as to the truth of each of these inequalities.

[0066] In line 10, each party uses

[00017]$\left(\begin{array}{c}16\\ 1\end{array}\right)-O{T}_{1\mathrm{to}}$

to learn their Boolean share of 1{x.sub.3=y.sub.3}, 1{x.sub.2=y.sub.2}, 1{x.sub.1=y.sub.1} and 1{x.sub.0=y.sub.0}, or in other words their Boolean share of 1, 1, 1, 0, since only x.sub.0=y.sub.0 is false, and since the leaf strings x.sub.3, x.sub.2 and x.sub.1 are each equal to the respective leaf strings y.sub.3, y.sub.2 and y.sub.1. As represented by arrow 212A of FIG. 2A, the first party computing system learns its shares 222A of 1{x.sub.3=y.sub.3}, 1{x.sub.2=y.sub.2}, 1{x.sub.1=y.sub.1} and 1{x.sub.0=y.sub.0}. As represented by arrows 212B of FIG. 2B, the second party computing system learns its shares 222B of 1{x.sub.3=y.sub.3}, 1{x.sub.2=y.sub.2}, 1{x.sub.1=y.sub.1} and 1{x.sub.0=y.sub.0}. Again, each party only knows Boolean shares of these values, and thus continues to be obvious as to the truth of each of these inequalities.

[0067] In the first recursion 230 (when i is equal to 1), there is an inequality and equality to be learned for x.sub.32 and y.sub.32 (when j is equal to 0, and where x.sub.32=x.sub.3∥x.sub.2 and y.sub.32=y.sub.3∥y.sub.2), and an equality and inequality to be learned for x.sub.10 and y.sub.1- (when j is equal to 1, and where x.sub.10=x.sub.1∥x.sub.1 and y.sub.10=y.sub.1∥y.sub.1).

[0068] The first iteration will now be described with respect to the example. In this example x.sub.32 is 10010101, and y.sub.32 is also 10010101. Thus, we expect 1{x.sub.32<y.sub.32} to be 0. Applying Equation 1 to inputs y.sub.3. y.sub.2, x.sub.3, and x.sub.2, each party learns their respective Boolean shares 231A and 231B of 1{x.sub.32<y.sub.32}, which is 0⊕(1∧0), or 0⊕0, or 0. Applying .sub.AND to these same inputs, each party learns their respective shares 233A and 233B of 1{x.sub.32=y.sub.32}, which is 1. Also in this example x.sub.10 is 10000001, and y.sub.10 is also 10001000. Thus, we expect 1{x.sub.10<y.sub.10} to be 1. Applying Equation 1 to inputs y.sub.1. y.sub.0, x.sub.1, and x.sub.1, each party learns their respective Boolean shares 232A and 232B of 1{x.sub.10<y.sub.10}, which is 0⊕(1∧1), or 0⊕1, or 1. Applying .sub.AND to these same inputs, each party learns their respective shares 234A and 234B of 1{x.sub.10=y.sub.10}, which is 0. In the second iteration, the value 1{x<y} should be 1 since x is less than y. Applying Equation 1 to inputs y.sub.32. y.sub.10, x.sub.32, and x.sub.10, each party learns their respective Boolean shares 241A and 241B of 1{x<y}, which is 0⊕(1∧1), or 0⊕1, or 1.

[0069] Correctness and security. Correctness is shown by induction on the depth of the tree starting at the leaves. First, by correctness of

[00018]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$

in step 9, lt.sub.0,j.sub.1.sup.B=lt.sub.0,j.sub.0.sup.B⊕1{x.sub.j<y.sub.j}. Similarly, eq.sub.0,i.sub.1.sup.B=eq.sub.0,i.sub.0.sup.B⊕1{x.sub.j=y.sub.j}. This proves the base case. Let q.sub.i=q/2.sup.i. Also, for level i of the tree, parse x=x.sup.(i)=x.sub.q.sub.i.sub.−1.sup.(i)∥ . . . x.sub.0.sup.(i) and y=y.sup.(i)=y.sub.q.sub.i.sub.−1.sup.(i)∥ . . . y.sub.0.sup.(i). Assume that for i it holds that lt.sub.i,j=lt.sub.i,j .sub.0.sup.B⊕lt.sub.i,j.sub.1.sup.B=1{x.sub.j.sup.(i)<y.sub.j.sup.(i)} and eq.sub.i,j .sub.0.sup.B ⊕eq.sub.i,j.sub.1.sup.B=1{x.sub.j.sup.(i)=y.sub.j.sup.(i)} for all j∈{0, . . . , q.sub.i−1}. Then, we prove the same for i+1 as follows: By correctness of .sub.AND, for j∈{0, . . . , q.sub.i+1−1}, lt.sub.i+1,j.sub.0.sup.B⊕lt.sub.i+1,j.sub.1.sup.B=lt.sub.i,2j+1⊕(lt.sub.i,2j∧eq.sub.i,2j+1)=1{x.sub.2j+1.sup.(i)<y.sub.2j+1.sup.(i)}⊕(1{x.sub.2j.sup.(i)<y.sub.2j.sup.(i) }∧1{x.sub.2j+1.sup.(i)=y.sub.2j+1.sup.(i)})=1{x.sub.j.sup.(i+1)≤y.sub.j.sup.(i+1)} (using Equation 1). The induction step for eq.sub.i+1,j holds in a similar manner, thus proving correctness. Given uniformity of lt.sub.0,j.sub.0.sup.B, eq.sub.0,j.sub.0.sup.B for all j∈{0, . . . , q−1}, security follows easily in the

[00019]$(\left(\begin{array}{c}M\\ 1\end{array}\right)-{\mathrm{OT}}_1,$

.sub.AND)-hybrid.

[0070] General case. When m does not divide and q=┌/m┐ is not a power of 2, we make the following modifications to the protocol. Since m does not divide , x.sub.q−1∈{0, 1}.sup.r, where r= mod m (Note that r=m when m|). When doing the compute for x.sub.q−1 and y.sub.q−1, we perform a small optimization and use

[00020]$\left(\begin{array}{c}R\\ 1\end{array}\right)-\mathrm{OT}1$

in steps 9 and 10, where R=2.sup.r. Second, since q is not a power of 2, we do not have a perfect binary tree of recursion and we need to slightly change our recursion/tree traversal. In the general case, we construct maximal possible perfect binary trees and connect the roots of the same using the relation in Equation 1. Let α be such that 2.sup.α<q≤2.sup.α+1. Now, our tree has a perfect binary sub-tree with 2α leaves and we have remaining q′=q−2.sup.α leaves. We recurse on q′. In the last step, we obtain our tree with q leaves by combining the roots of perfect binary tree with 2.sup.α leaves and tree with q′ leaves using Equation 1. Note that value at the root is computed using ┌log q┐ sequential steps starting from the leaves.

[0071] Again, let us take a concrete example to further clarify. Suppose that the length of the input is 11, and that the length of each leaf string m will be 4. As an example suppose that input x=10110000001, and input y=10110001000. Here, m does not divide . Accordingly, x.sub.q−1∈{0, 1}.sup.r, where r= mod m (Note that r=m when m). Accordingly, x.sub.2 is equal to 101, and y.sub.2 is equal to 101. q is equal to 3, and thus there is no x.sub.3 and y.sub.3. x.sub.1, x.sub.0, y.sub.1 and y.sub.2 are the same as in the previous example. Here, when doing the compute for x.sub.2 and y.sub.2, the Boolean shares of the inequality and equality are each learned using uses

[00021]$\left(\begin{array}{c}8\\ 1\end{array}\right)-O{T}_1$

instead of uses

[00022]$\left(\begin{array}{c}16\\ 1\end{array}\right)-O{T}_1.$

In the first iteration, the Boolean shares the equalities and inequalities of x.sub.2 and y.sub.2 are calculated However, the equalities and inequalities for x.sub.10 and y.sub.10 are still calculated. Then, in the second recursion, the Boolean shares of the inequality for x and y is calculated using inputs, x.sub.2 and x.sub.10, and y.sub.2 and y.sub.10.

[0072] 3.1.1 Optimizations. We reduce the concrete communication complexity of our protocol using the following optimizations that are applicable to both the special and the general case.

[0073] Combining two

[00023]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$

calls into one

[00024]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_2:$

Since the input of P.sub.1 (OT receiver) to

[00025]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1$

in steps 9 and 10 is the same, i.e. y.sub.j, we can collapse these steps into a single call to

[00026]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_2$

where P.sub.0 and P.sub.1 input {(s.sub.j,k∥t.sub.j,k)}.sub.k and y.sub.j, respectively. P.sub.1 sets its output as (lt.sub.0, .sub.1.sup.B∥eq.sub.0,j.sub.1.sup.B). This reduces the cost from 2(2λ+M) to (2λ+2M).

[0074] Realizing .sub.AND efficiently: It is known that .sub.AND can be realized using Beaver bit triples [8]. In prior works [5, 24], generating a bit triple costs 2λ bits. For our protocol, we observe that the 2 calls to .sub.AND in steps 14 and 16 have a common input, eq.sub.i−1,2j+1.sub.b.sup.B. Hence, we optimize communication of these steps by generating correlated bit triples (d.sub.b.sup.B, e.sub.b.sup.B, f.sub.b.sup.B) and (d′.sub.b.sup.B, e.sub.b.sup.B, f′.sub.b.sup.B) for b∈{0, 1}, such that d∧e=f and d′∧e=f′. Next, we use

[00027]$\left(\begin{array}{c}8\\ 1\end{array}\right)-O{T}_2$

to generate one such correlated bit triple (Appendix A.2) with communication 2λ+16 bits, giving the amortized cost of λ+8 bits per triple. Given correlated bit triples, we need 6 additional bits to compute both .sub.AND calls.

[0075] Removing unnecessary equality computations: As observed in [28], the equalities computed on lowest significant bits are never used. Concretely, we can skip computing the values eq.sub.i,0 for i∈{0, . . . , log q}. Once we do this optimization, we only need a single call to .sub.AND instead of 2 correlated calls for the leftmost branch of the tree. We use the

[00028]$\left(\begin{array}{c}16\\ 1\end{array}\right)-O{T}_2.fwdarw.2\times \left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_1$

reduction to generate 2 regular bit triples (Appendix A.1) with communication of 2λ+32 bits. This gives us amortized communication of λ+16 bits per triple. This is ≈2× improvement over 2λ bits required in prior works [5, 24]. Given a bit triple, we need 4 bits to realize .sub.AND. This reduces the total communication by M (for the leaf) plus (λ+2).Math.┌log q┐ (for leftmost branch) bits.

[0076] 3.1.2 Communication Complexity. In our protocol, we communicate in protocols for OT (steps 9&10) and .sub.AND (steps 14&16). With above optimizations, we need 1 call to

[00029]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_1,$

(q−2) calls to

[00030]$\left(\begin{array}{c}M\\ 1\end{array}\right)-O{T}_2$

and 1 call to

[00031]$\left(\begin{array}{c}R\\ 1\end{array}\right)-O{T}_2$

which cost (2λ+M), ((q−2).Math.(2λ+2M)(and (2λ+2R) bits, respectively. In addition, we have ┌log q┐ invocations of .sub.AND and (q−1−┌log q┐) invocations of correlated .sub.AND. These require communication of (λ+20).Math.┌log q┐ and (2λ+22).Math.(q−1−┌log q┐) bits. This gives us total communication of λ(4q−┌log q┐−2)+M(2q−3)+2R+22(q−1)−2┌log q┐ bits. Using this expression for =32 we get the least communication for m=7 (Table 1). We note that there is a trade-off between communication and computational cost of OTs used and we discuss our choice of m for our experiments in Section 6.

[0077] 3.2 Protocol for ReLU′ for -Bit Integers

[0078] Here, we describe our protocol for that takes as input arithmetic shares of a and returns boolean shares of ReLU′(a) (DReLU stands for derivative of ReLU, i.e., ReLU′). Note that ReLU′(a)=(1⊕MSB(a)), where MSB(a) is the most significant bit of a. Let arithmetic shares of a∈.sub.L be a.sub.0.sup.L=msb.sub.0∥x.sub.0 and a=msb.sub.1∥x.sub.1 such that msb.sub.0, msb.sub.1∈{0, 1}. We compute the boolean shares of MSB(a) as follows: Let carry=1{(x.sub.0+x.sub.1)>−1}. Then, MSB(a)=msb.sub.0⊕msb.sub.1⊕carry. We compute boolean shares of carry by invoking an instance of .

TABLE-US-00005 Algorithm 2   -bit integer ReLU′   : Input: P.sub.0, P.sub.1 hold   a   .sub.0.sup.L and   a   .sub.1.sup.L, respectively. Output: P.sub.0, P.sub.1 get   ReLU′(a)   .sub.0.sup.B and   ReLU′(a)   .sub.1.sup.B. 1: P.sub.0 parses its input as   a   .sub.0.sup.L = msb.sub.0∥x.sub.0 and P.sub.1 parses its input as   a   .sub.1.sup.L = msb.sub.1∥x.sub.1, s.t. b ϵ  {0, 1}, msb.sub.b ϵ {0, 1}, x.sub.b ϵ {0, 1}   . 2: P.sub.0 & P.sub.1 invoke an instance of   , where P.sub.0's input is   −  1 − x.sub.0 and P.sub.1's input is x.sub.1. For b ϵ {0, 1}, P.sub.b learns   carry   .sub.b.sup.B. 3: For b ϵ {0, 1}, P.sub.b sets   ReLU′   .sub.b.sup.B = msb.sub.b ⊕   carry   .sub.b.sup.B ⊕ b.

[0079] Correctness and security. By correctness of , Reconst.sup.B (carry).sub.0.sup.B, (carry.sub.1.sup.B)=1{−1−x.sub.0)<x.sub.1}=1{(x.sub.0+x.sub.1)>−1}. Also, Reconst.sup.B (ReLU′).sub.0.sup.B, ReLU′.sub.1.sup.B)=msb.sub.0⊕msb.sub.1 ⊕carry⊕1=MSB(a)⊕1. Security follows trivially in the hybrid.

[0080] Communication complexity In Algorithm 2, we communicate the same as in ; that is <λ+14)(−1) by using m=4.

[0081] 3.3 Protocol for ReLU′ for General .sub.n

[0082] We describe a protocol for that takes arithmetic shares of a over .sub.n as input and returns boolean shares of ReLU′(a). For integer rings .sub.n, ReLU′(a)=1 if a<┌n/2┐ and 0 otherwise. Note that this includes the case of prime fields considered in the works of [42, 48]. We first describe a (simplified) protocol for ReLU′ in .sub.n, in Algorithm 3 with protocol logic as follows: Let arithmetic shares of a∈.sub.n be a.sub.0.sup.n, and a.sub.1.sup.n. Define wrap=1{a.sub.0.sup.n+a.sub.n.sup.1>n−1}, lt=1{a.sub.0.sup.n+a.sub.1.sup.n>(n−1)/2} and rt=1{a.sub.0.sup.n+a.sub.1.sup.n>n+(n−1)/2}. Then, ReLU′(a) is (1⊕lt) if wrap=0, else it is (1⊕rt). In Algorithm 3, steps 1, 2, 3, compute these three comparisons using .sub.MILL. Final output can be computed using an invocation of .sub.MUX.sup.2.

TABLE-US-00006 Algorithm 3 Simple Integer ring ReLU′ Π.sub.DReLU.sub.simple.sup.ring, n : Input: P.sub.0, P.sub.1, hold   a   .sub.0.sup.n and   a   .sub.1.sup.n , respectively, where a ϵ   .sub.n. Output: P.sub.0, P.sub.1 get   ReLU′(a)   .sub.0.sup.B and   ReLU′(a)   .sub.1.sup.B. 1: P.sub.0 & P.sub.1 invoke an instance of   .sub.MILL.sup.η with η = ┌log n┐, where P.sub.0's input is (n − 1 −   a   .sub.0.sup.n)  and P.sub.1's input is   a   .sub.1.sup.n .Math. For b ϵ {0, 1}, P.sub.b learns   wrap   .sub.b.sup.B as output. 2: P.sub.0 & P.sub.1 invoke an instance of   .sub.MILL.sup.η+1, where P.sub.0's input is (n − 1 −   a   .sub.0.sup.n) and P.sub.1's input  is ((n − 1)/2 +   a   .sub.1.sup.n). For b ϵ {0, 1}, P.sub.b learns   lt   .sub.b.sup.B as output. 3: P.sub.0 & P.sub.1 invoke an instance of   .sub.MILL.sup.η+1, where P.sub.0's input is (n + (n − 1)/2 −   a   .sub.0.sup.n) and  P.sub.1's input is   a   .sub.1.sup.n .Math. For b ϵ {0, 1}, P.sub.b learns   rt   .sub.b.sup.B as output. 4: For b ϵ {0, 1}, P.sub.b invokes   .sub.MUX.sup.2 with input (   lt   .sub.b.sup.B ⊕   rt   .sub.b.sup.B) and choice   wrap   .sub.b.sup.B to learn    z   .sub.b.sup.B. 5: For b ϵ {0,1}, P.sub.b outputs   z   .sub.b.sup.B ⊕   lt   .sub.b.sup.B ⊕ b.

[0083] Optimizations We describe an optimized protocol for .sub.DReLU.sup.ring,n in Algorithm 4 that reduces the number of calls to .sub.MILL to 2. First, we observe that if the input of P.sub.1 is identical in all three invocations, then the invocation of OT in Algorithm 1 (steps 9&10) can be done together for the three comparisons. This reduces the communication for each leaf OT invocation in steps 9&10 by an additive factor of 4λ. To enable this, P.sub.0, P.sub.1 add (n−1)/2 to their inputs to .sub.MILL.sup.η+1 in steps 1, 3 (η=┌log n┐). Hence, P.sub.1's input to .sub.MILL.sup.η+1 is (n−1)/2+a.sub.1.sup.n in all invocations and P.sub.0's inputs are (3(n−1)/2−n.sub.0.sup.n) (n−1−a.sub.0.sup.n), (2n−1−a.sub.0.sup.n) in steps 1, 2, 3, respectively.

TABLE-US-00007 Algorithm 4 Optimized Integer ring ReLU′, Π.sub.DReLU.sup.ring,n: Input: P.sub.0, P.sub.1 hold   a  .sub.0.sup.n and  a  .sub.1.sup.n, respectively, where a ∈ .sub.n. Let η = ┌logn┐. Output: P.sub.0, P.sub.1 get  ReLU′(a)  .sub.0.sup.B and   ReLU′(a)  .sub.1.sup.B. 1: P.sub.0 & P.sub.1 invoke an instance of  .sub.MILL.sup.η+1, where P.sub.0′s input is (3(n − 1)/2 −   a  .sub.0.sup.n) and P.sub.1′s input is (n − 1)/2 +  a  .sub.1.sup.n. For b ∈ {0, 1}, P.sub.b learns   wrap  .sub.b.sup.B as output. 2: P.sub.0 sets x =(2n − 1 −  a  .sub.0.sup.n) if   a  .sub.0.sup.n > (n − 1)/2, else x =(n − 1 −   a  .sub.0.sup.n). 3: P.sub.0 & P.sub.1 invoke an instance of  .sub.MILL.sup.η+1, where P.sub.0′s input is x and P.sub.1′s input is ((n − 1)/2 +   a  .sub.1.sup.n). For b ∈ {0, 1}, P.sub.b learns   xt  .sub.b.sup.B as output. 4: [00032]$P_0\mathrm{samples}{.Math.z.Math.}_0^B\stackrel{\$}{\leftarrow }\left\{0,1\right\}.$ 5: for j = {00, 01, 10, 11} do 6:   P.sub.0 parses j as j.sub.0||j.sub.1 and sets t.sub.j = 1 ⊕   xt  .sub.0.sup.B ⊕ j.sub.0. 7:   if   a  .sub.0.sup.n > (n − 1)/2 then 8:    P.sub.0 sets s.sub.j′ = t.sub.j ∧ (  wrap  .sub.0.sup.B ⊕ j.sub.1). 9:   else 10:    P.sub.0 sets s.sub.j′ = t.sub.j ⊕ ((1 ⊕ t.sub.j) ∧ (  wrap  .sub.0.sup.B ⊕ j.sub.1)). 11:   end if 12:   P.sub.0 sets s.sub.j = s.sub.j′ ⊕   z  .sub.0.sup.B 13: end for 14: [00033]$P_0\&P_1\mathrm{invoke}\mathrm{an}\mathrm{instance}\mathrm{of}\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_1\mathrm{where}{P}_0\mathrm{is}\mathrm{the}\mathrm{sender}\mathrm{with}\mathrm{inputs}{\left\{s_j\right\}}_j\mathrm{and}{P}_1$ is the receiver with input  xt  .sub.1.sup.B||  wrap  .sub.1.sup.B. P.sub.1 sets its output as  z  .sub.1.sup.B. 15: For b ∈ {0, 1}, P.sub.b outputs  z  .sub.b.sup.B.

[0084] Next, we observe that one of the comparisons in step 2 or step 3 is redundant. For instance, if a.sub.0.sup.n>(n−1)/2, then the result of the comparison lt=a.sub.0.sup.n+a.sub.1.sup.n>(n−1)/2 done in step 2 is always 1. Similarly, if a.sub.0.sup.n≤(n−1)/2, then the result of the comparison rt=1{a.sub.0.sup.n+a.sub.1.sup.n>n+(n−1)/2} done in step 3 is always 0. Moreover, P.sub.0 knows based on her input a.sub.0.sup.n which of the two comparisons is redundant. Hence, in the optimized protocol, P.sub.0 and P.sub.1 always run the comparison to compute shares of wrap and one of the other two comparisons. Note that the choice of which comparison is omitted by P.sub.0 need not be communicated to P.sub.1, since P.sub.1's input is same in all invocations of .sub.MILL. Moreover, this omission does not reveal any additional information to P.sub.1 by security of .sub.MILL. Finally, P.sub.0 and P.sub.1 can run a

[00034]$\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_1$

to learn the shares of ReLU′(a). Here, P.sub.1 is the receiver and her choice bits are the shares learnt in the two comparisons. P.sub.0 is the sender who sets the 4 OT messages based on her input share, and two shares learnt from the comparison protocol. We elaborate on this in the correctness proof below.

[0085] Correctness and Security. First, by correctness of .sub.MILL.sup.η+1 (step 1), wrap=Reconst.sup.B (wrap.sub.0.sup.B, wrap.sub.1.sup.B)=1{a.sub.0.sup.L+a.sub.1.sup.L>n−1}. Let j*=xt.sub.1.sup.B∥wrap.sub.1.sup.B. Then t.sub.j*=1⊕xt. We will show that s.sup.t.sub.j*=ReLU′(a), and hence, by correctness of

[00035]$\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_1,$

z=ReconstB (z.sub.0.sup.B, z.sub.1.sup.B)=ReLU′(a). We have the following two cases.

[0086] When a.sub.0.sup.L>(n−1)/2, lt=1, and ReLU′(a)=wrap∧(1⊕rt). Here, by correctness of .sub.MILL.sup.η+1 (step 3), xt=Reconst.sup.B (xt.sub.0.sup.B, xt.sub.1.sup.B)=rt. Hence, s′.sub.j*=t.sub.j*∧(wrap.sub.0.sup.B⊕j*.sub.1)=(1⊕rt)∧wrap.

[0087] When a.sub.0.sup.L≤(n−1)/2, rt=0, ReLU′(a) is 1⊕lt if wrap=0, else 1. It can be written as (1⊕lt)⊕(lt∧wrap). In this case, by correctness of .sub.MILL.sup.η+1 (step 3), xt=Reconst.sup.B (x.sub.0.sup.B, xt.sub.1.sup.B)=lt. Hence, s′.sub.j*=t.sub.j*⊕((1⊕t.sub.j*)∧(wrap.sub.0.sup.B⊕j*.sub.1))=(1⊕lt)⊕(lt∧wrap). Since z.sub.0.sup.B is uniform, security follows in the

[00036]$\left({ℱ}_{\mathrm{MILL}}^{\eta +1},\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_1\right)-\mathrm{hybrid}.$

[0088] Communication complexity. With the above optimization, the overall communication complexities of our protocol for ReLU′ in .sub.n is equivalent to 2 calls to Π.sub.MILL.sup.η+1 where P.sub.1 has same input plus 2λ+4 (for protocol for

[00037]$\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_1).$

Two calls to Π.sub.MILL.sup.η+1 in this case (using m=4) cost<3/2λ(η+1)+28(η+1) bits. Hence, total communication is <3/2λ(η+1)+28(η+1)+2λ+4. We note that the communication complexity of simplified protocol in Algorithm 3 is approximately 3 independent calls to Π.sub.MILL.sup.η, which cost 3(λη+14η) bits, plus 2λ+4 bits for .sub.MUX.sup.2. Thus, our optimization gives almost 2× improvement.

4 Division and Truncation

[0089] We present our results on secure implementations of division in the ring by a positive integer and truncation (division by power-of-2) that are bitwise equivalent to the corresponding cleartext computation. We begin with closed form expressions for each of these followed by secure protocols that use them.

[0090] 4.1 Expressing General Division and Truncation Using Arithmetic Over Secret Shares

[0091] Let idiv: ×.fwdarw. denote signed integer division, where the quotient is rounded towards −∞ and the sign of the remainder is the same as that of divisor. We denote division of a ring element by a positive integer using rdiv: .sub.n×.fwdarw..sub.n defined as

rdiv(a,d)idiv(a.sub.u−1{a.sub.u≥┌n/2┐}.Math.n,d)mod n,

where the integer a.sub.u∈{0, 1, . . . , n−1} is the unsigned representation of a∈.sub.n lifted to integers and 0<d<n. For brevity, we use x=.sub.n y to denote x mod n=y mod n.

[0092] THEOREM 4.1. (Division of ring element by positive integer). Let the shares of a∈n be a.sub.0.sup.n, a.sub.1.sup.n∈.sub.n, for some n=n.sup.1.Math.d+n.sup.0∈, where n.sup.0, n.sup.1, d∈ and 0≤n.sup.0<d<n. Let the unsigned representation of a, a.sub.0.sup.n, a.sub.1.sup.n in .sub.n lifted to integers be a.sub.u, a.sub.0, a.sub.1∈{0, 1, . . . , n−1}, respectively, such that a.sub.0=a.sub.0.sup.1.Math.d+a.sub.0.sup.0 and a.sub.1=a.sub.1.sup.1.Math.d+a.sub.1.sup.0, where a.sub.0.sup.1, a.sub.0.sup.0, a.sub.1.sup.1, a.sub.1.sup.0∈ and 0≤a.sub.0.sup.0, a.sub.1.sup.0<d. Let n′=┌n/2┐∈. Define corr, A, B, C∈ as follows:

[00038]$\mathrm{corr}=\{\begin{array}{c}-1\left(a_u\ge n^{\prime }\right)\wedge \left(a_0<n^{\prime }\right)\wedge \left(a_1<n^{\prime }\right)\\ 1a_u<n^{\prime }\wedge a_0\ge n^{\prime }\wedge a_1\ge n^{\prime }\\ 0\mathrm{otherwise}\end{array}$$A=a_0^0+a_1^0-\left(1\left\{a_0\ge n^{\prime }\right\}+1\left\{a_1\ge n^{\prime }\right\}-\mathrm{corr}\right).Math.n^0.$$B=\mathrm{idiv}\left(a_0^0-1\left\{a_0\ge n^{\prime }\right\}.Math.n^0,d\right)+\mathrm{idiv}\left(a_1^0-1\left\{a_1\ge n^{\prime }\right\}.Math.n^0,d\right)$$C=1\left\{A<d\right\}+1\left\{A<0\right\}+1\left\{A<-d\right\}$

Then, we have:

rdiv(a.sub.0.sup.n,d)+rdiv(a.sub.1.sup.n,d)+(corr.Math.n.sup.1+1−C−B)mod n=.sub.nrdiv(a,d).

The proof of the above theorem is presented in Appendix C.

[0093] 4.1.1 Special Case of truncation for bit integers. The expression above can be simplified for the special case of division by 2.sup.s of -bit integers, i.e., arithmetic right shift with s (>>s), as follows:

[0094] COROLLARY 4.2. (Truncation for -bit integers). Let the shares of a∈.sub.L be a.sub.0.sup.L, a.sub.1.sup.L∈.sub.L. Let the unsigned representation of a, a.sub.0.sup.L, a.sub.1.sup.L in .sub.L lifted to integers be a.sub.u, a.sub.0, a.sub.1∈{0, 1, . . . , −1}, respectively, such that a.sub.0=a.sub.0.sup.1.Math.2.sup.s+a.sub.0.sup.0 and a.sub.1=a.sub.1.sup.1.Math.2.sup.s+a.sub.1.sup.0, where a.sub.0.sup.1, a.sub.0.sup.0, a.sub.1.sup.1, a.sub.1.sup.0∈ and 0≤a.sub.0.sup.0, a.sub.1.sup.0<2.sup.s. Let corr∈ be defined as in Theorem 4.1. Then, we have:

(a.sub.0>>s)+(a.sub.1>>s)+corr.Math.+1{a.sub.0.sup.0+a.sub.1.sup.0≥2.sup.s}=L(a>>s).

PROOF. The corollary follows directly from Theorem 4.1 as follows: First, (a>>s)=rdiv(a, 2.sup.s). Next, n=, n.sup.1=2.sup.−.sup.s, and n.sup.0=0. Using these, we get A=a.sub.0.sup.0+a.sub.1.sup.0, B=0 and C=1{A<2s}=1{a.sub.0.sup.0+a.sub.1.sup.0<2.sup.s}.

[0095] 4.2 Protocols for Division

[0096] In this section, we describe our protocols for division in different settings. We first describe a protocol for the simplest case of truncation for f-bit integers followed by a protocol for general division in .sub.n by a positive integer (Section 4.2.2). Finally, we discuss another simpler case of truncation, which allows us to do better than general division for rings with a special structure (Section 4.2.3).

TABLE-US-00008 Algorithm 5 Truncation, : Input: For b ∈ {0, 1}, P.sub.b holds  a  .sub.b.sup.L, where a ∈ .sub.L. Output: For b ∈ {0, 1}, P.sub.b learns   z  .sub.b.sup.L s.t. z = a >> s. 1: For b ∈ {0, 1}, let a.sub.b, a.sub.b.sup.1 ∈  be as defined in Corollary 4.2. 2: For b ∈ {0, 1}, P.sub.b invokes  .sub.DReLU.sup.int, .sup., with input   a  .sub.b.sup.L to learn output   α  .sub.b.sup.B. Party P.sub.b sets m  .sub.b.sup.B=   α  .sub.b.sup.B ⊕ b. 3: For b ∈ {0, 1}, P.sub.b sets x.sub.b = MSB(  a  .sub.b.sup.L). 4: [00039]$P_0\mathrm{samples}{.Math.\mathrm{corr}.Math.}_0^L\stackrel{\$}{\leftarrow }{Z}_2^t.$ 5: for j = {00, 01, 10, 11} do 6:  P.sub.0 computes t.sub.j = (  m  .sub.0.sup.B ⊕ j.sub.0 ⊕ x.sub.0) ∧ (  m  .sub.0.sup.B ⊕ j.sub.0 ⊕ j.sub.1) s.t.j = ( j.sub.0||j.sub.1). 7:  if t.sub.j ∧ 1 {x.sub.0 = 0} then 8:   P.sub.0 sets s.sub.j = L −  corr  .sub.0.sup.L− 1. 9:  else if t.sub.j ∧ 1 {x.sub.0 = 1} then 10:   P.sub.0 sets s.sub.j = L −  corr  .sub.0.sup.L + 1. 11:  else 12:   P.sub.0 sets s.sub.j = L −  corr  .sub.0.sup.L. 13:  end if 14: end for 15: [00040]$P_0\&P_1\mathrm{invoke}\mathrm{an}\mathrm{instance}\mathrm{of}\left(\begin{array}{c}4\\ 1\end{array}\right)-\mathrm{OT}\ell ,\mathrm{where}{P}_0\mathrm{is}\mathrm{the}\mathrm{sender}\mathrm{with}\mathrm{inputs}{\left\{s_j\right\}}_j\mathrm{and}$ P.sub.1 is the receiver with input  m  .sub.1.sup.B||x.sub.1 and learns   corr  .sub.1.sup.L. 16: P.sub.0 & P.sub.1 invoke an instance of  .sub.MILL.sup.s with P.sub.0′s input as 2.sup.s−1−a.sub.0.sup.0 and P.sub.1′s input as a.sub.1.sup.0. For b ∈ {0, 1}, P.sub.b learns   c  .sub.b.sup.B. 17: For b ∈ {0, 1}, P.sub.b invokes an instance of  .sub.B2A.sup.L (L = 2 ) with input   c  .sub.b.sup.B and learns d  .sub.b.sup.L. 18: P.sub.b outputs   z  .sub.b.sup.L = (  a  .sub.b.sup.L>> s) +  corr  .sub.b.sup.L. 2  .sup.−s +   d  .sub.b.sup.L, b ∈ {0, 1}.

[0097] 4.2.1 Protocol for truncation of -bit integer. Let be the functionality that takes arithmetic shares of a as input and returns arithmetic shares of a>>s as output. In this work, we give a protocol Algorithm 5 that realizes the functionality correctly building on Corollary 4.2.

[0098] Parties P.sub.0 & P.sub.1 first invoke an instance of (where one party locally flips its share of ReLU′(a)) to get boolean shares m.sub.b.sup.B of MSB(a). Using these shares, they use a

[00041]$\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_1$

for calculating corr.sub.b.sup.L, i.e., arithmetic shares of corr term in Corollary 4.2. Next, they use an instance of .sub.MILL.sup.s to compute boolean shares of c=1{a.sub.0.sup.0+a.sub.1.sup.0≥2.sup.s}. Finally, they compute arithmetic shares of c using a call to .sub.B2A.sup.L (Algorithm 7).

[0099] Correctness and Security. For any z∈.sub.L, MSB(z)=1{z.sub.u≥}, where z.sub.u is unsigned representation of z lifted to integers. First, note that Reconst.sup.B(m.sub.0.sup.B, m.sub.1.sup.B)=1⊕Reconst.sup.B(a.sub.0.sup.B, a.sub.1.sup.B)=MSB(a) by correctness of . Next, we show that Reconst.sup.L(corr.sub.0.sup.L, corr.sub.1.sup.L)=corr, as defined in Corollary 4.2. Let x.sub.b=MSB(a.sub.b.sup.L) for b∈{0, 1}, and let j*=(m.sub.1.sup.B∥x.sub.1). Then, t.sub.j*=(m.sub.0.sup.B⊕m.sub.1.sup.B ⊕x.sub.0)∧(m.sub.0.sup.B⊕m.sub.1.sup.B⊕x.sub.1)=(MSB(a)⊕x.sub.0)∧(MSB(a)⊕x.sub.1). Now, t.sub.j*=1 implies that we are in one of the first two cases of expression for corr—which case we are in can be checked using x.sub.0 (steps 7 & 9). Now we can see that s.sub.j*=−corr.sub.0.sup.L+corr=corr.sub.1.sup.L. Next, by correctness of .sub.MILL.sup.s, c=Reconst.sup.B c.sub.0.sup.B, c.sub.1.sup.B)=1{a.sub.0.sup.0+a.sub.1.sup.0≥2.sup.s}. That is, c=c.sub.0 .sup.B⊕c.sub.1.sup.B. Given boolean shares of c, step 17, creates arithmetic shares of the same using an instance of .sub.B2A.sup.L. Since corr.sub.0.sup.L is uniformly random, security of our protocol is easy to see in

[00042]$\left({ℱ}_{\mathrm{DReLU}}^{\mathrm{int},\ell },\left(\begin{array}{c}4\\ 1\end{array}\right)-{\mathrm{OT}}_{\ell },{ℱ}_{\mathrm{MILL}}^s,{ℱ}_{B2A}^L\right)-\mathrm{hybrid}.$

[0100] Communication complexity. involves a single call each to

[00043]${ℱ}_{\mathrm{DReLU}}^{\mathrm{int},\ell },\left(\begin{array}{c}4\\ 1\end{array}\right)-{\mathrm{OT}}_{\ell },{ℱ}_{B2A}^L\mathrm{and}{ℱ}_{\mathrm{MILL}}^s.$

Hence, communication required is <λ+2λ+19+communication for .sub.MILL.sup.s that depends on parameters. For =32 and s=12, our concrete communication is 4310 bits (using m=7 for Π.sub.MILL.sup.12 as well as Π.sub.MILL.sup.31 inside Π.sub.DReLU.sup.int,32) as opposed to 24064 bits for garbled circuits.

[0101] 4.2.2 Protocol for division in ring. Let .sub.Div.sup.ring,n,d be the functionality for division that takes arithmetic shares of a as input and returns arithmetic shares of rdiv(a, d) as output. Our protocol builds on our closed form expression from Theorem 4.1. We note that -bit integers is a special case of .sub.n and we use the same protocol for division of an element in .sub.L by a positive integer.

[0102] This protocol is similar to the previous protocol for truncation and uses the same logic to compute shares of corr term. The most non-trivial term to compute is C that involves three signed comparisons over . We emulate these comparisons using calls to .sub.DReLU.sup.int,δ where δ is large enough to ensure that there are no overflows or underflows. We can see that −2d+2≤A≤2d−2 and hence, −3d+2≤A−d,A,A+d≤3d−2. Hence, we set δ=┌ log δd┐. Now, with this value of δ, the term C can we re-written as (ReLU′(A−d)⊕1)+(ReLU′(A)⊕1)+(ReLU′(A+d)⊕1), which can be computed using three calls to .sub.DReLU.sup.int,δ (Step 19) and .sub.B2A.sup.n (Step 20) each. Finally, note that to compute C we need arithmetic shares of A over the ring .sub.Δ, Δ=2.sup.δ. And this requires shares of corr over the same ring. Hence, we compute shares of corr over both .sub.n and .sub.Δ (Step 15). Due to space constraints, we describe the protocol formally in Appendix D. Table 3 provides theoretical and concrete communication numbers for division in both .sub.L and .sub.n, as well as a comparison with garbled circuits.

[0103] 4.2.3 Truncation in rings with special structure. Truncation by s in general rings can be done by performing a division by d=2.sup.s. However, we can omit a call to .sub.DReLU.sup.int,δ and .sub.B2A.sup.n when the underlying ring and d satisfy a relation. Specifically, if we have 2.Math.n.sup.0≤d=2.sup.s, then A is always greater than equal to −d, where n.sup.0, A∈Z are as defined in Theorem 4.1. Thus, the third comparison (A≤−d) in the expression of C from Theorem 4.1 can be omitted. Moreover, this reduces the value of δ needed and δ=┌log 4d┐ suffices since −2d≤A−d, A≤2d−2.

[0104] Our homomorphic encryption scheme requires n to be a prime of the form 2KN+1 (Section 2.2.4), where K is a positive integer and N≥8192 is a power-of-2. Thus, we have n.sup.0=n mod 2.sup.s=1 for 1≤s≤14. For all our benchmarks, s≤12 and we use this optimization for truncation in PIE.sub.HE.

5 Secure Inference

[0105] We give an overview of all the layers that are computed securely to realize the task of secure neural network inference. Layers can be broken into two categories—linear and non-linear. An inference algorithm simply consists of a sequence of layers of appropriate dimension connected to each other. Examples of linear layers include matrix multiplication, convolutions, Avgpool and batch normalization, while non-linear layers include ReLU, Maxpool, and Argmax.

[0106] We are in the setting of secure inference where the model owner, say P.sub.0, holds the weights. When securely realizing each of these layers, we maintain the following invariant: Parties P.sub.0 and P.sub.1 begin with arithmetic shares of the input to the layer and after the protocol, end with arithmetic shares (over the same ring) of the output of the layer. This allows us to stitch protocols for arbitrary layers sequentially to obtain a secure computation protocol for any neural network comprising of these layers. For protocols in PIE.sub.OT, this arithmetic secret sharing is over .sub.L; in PIE.sub.HE, the sharing is over .sub.n, prime n.

[0107] 5.1 Linear Layers

[0108] 5.1.1 Fully connected layers and convolutions. A fully connected layer in a neural network is simply a product of two matrices—the matrix of weights and the matrix of activations of that layer—of appropriate dimension. At a very high level, a convolutional layer applies a filter (usually of dimension f×f for small integer f) to the input matrix by sliding across it and computing the sum of elementwise products of the filter with the input. Various parameters are associated with convolutions—e.g. stride (a stride of 1 denotes that the filter slides across the larger input matrix beginning at every row and every column) and zero-padding (which indicates whether the matrix is padded with 0s to increase its dimension before applying the filter). When performing matrix multiplication or convolutions over fixed-point values, the values of the final matrix are scaled down appropriately so that it has the same scale as the inputs to the computation. We note that our values are in fixed-point with an associated scale s and have been encoded into appropriate size rings .sub.L or .sub.n as follows: a Real r is encoded as [r2.sup.s] mod k where k=L or n. Hence, to do faithful fixed-point arithmetic, we first compute the matrix multiplication or convolution over the ring (.sub.L or .sub.n) followed by truncation, i.e., division-by-2s of all the values. In PIE.sub.OT, multiplication and convolutions over the ring .sub.L are done using oblivious transfer techniques and in PIE.sub.HE these are done over .sub.n using homomorphic encryption techniques that we describe next followed by our truncation method.

[0109] OT based computation. We note that OT-based techniques for multiplication are known [8, 24, 50] and we describe them briefly for completeness. First consider the simple case of secure multiplication of 2 elements a and b in .sub.L where P.sub.0 knows a and P.sub.0 and P.sub.1 hold arithmetic shares of b. This can be done with instances of

[00044]$\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{COT}}_{\frac{\ell +1}{2}}.$

Using this, multiplying two matrices A∈.sub.L.sup.M,N and B∈.sub.L.sup.N,K such that P.sub.0 knows A and B is arithmetically secret shared requires MNK instances of

[00045]$\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{COT}}_{\frac{\ell +1}{2}}.$

This can be optimized by using the structured multiplications inside a matrix multiplication by combining all the COT sender messages when multiplying with the same element, reducing the complexity to NK instances of

[00046]$\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{COT}}_{\frac{M\left(\ell +1\right)}{2}}.$

Finally, we reduce the task of secure convolutions to secure matrix multiplication similar to [44, 49, 60].

[0110] HE based computation. PIE.sub.HE, uses techniques from Gazelle [42] and Delphi [48] to compute matrix multiplications and convolutions over a field .sub.L (prime n), of appropriate size. At a high level, first, P.sub.1 sends an encryption of its arithmetic share to P.sub.0. Then, P.sub.0 homomorphically computes on this ciphertext using weights of the model (known to P.sub.0) to compute an encryption of the arithmetic share of the result and sends this back to P.sub.1. Hence, the communication only depends on the input and output size of the linear layer and is independent of the number of multiplications being performed. Homomorphic operations can have significantly high computational cost—to mitigate this, we build upon the output rotations method from [42] for performing convolutions, and reduce its number of homomorphic rotations. At a very high level, after performing convolutions homomorphically, ciphertexts are grouped, rotated in order to be correctly aligned, and then packed using addition. In our work, we divide the groups further into subgroups that are misaligned by the same offset. Hence the ciphertexts within a subgroup can first be added and the resulting ciphertext can then be aligned using a single rotation as opposed to ≈c.sub.i/c.sub.n in [42] (where c.sub.i denotes the number of input channels and c.sub.n is the number of channels that fit in a single ciphertext). We refer the reader to Appendix E for details.

[0111] Faithful truncation. To correctly emulate fixed-point arithmetic, the value encoded in the shares obtained from the above methods are divided-by-2s, where s is the scale used. For this we invoke in PIE.sub.OT and .sub.Div.sup.ring,n,2.sup.s in PIE.sub.HE for each value of the resulting matrix. With this, result of secure implementation of fixed-point multiplication and convolutions is bitwise equal to the corresponding cleartext execution. In contrast, many prior works on 2PC [48, 50] and 3PC [44, 49, 60] used a local truncation method for approximate truncation based on a result from [50]. Here, the result can be arbitrarily wrong with a (small) probability p and with probability 1−p the result can be wrong in the last bit. Since p grows with the number of truncations, these probabilistic errors are problematic for large DNNs. Moreover, even if p is small, 1-bit errors can accumulate and the results of cleartext execution and secure execution can diverge; this is undesirable as it breaks correctness of 2PC.

[0112] 5.1.2 Avgpool.sub.d. The function Avgpool.sub.d (a.sub.1, . . . , a.sub.d) over a pool of d elements a1, . . . , ad is defined to be the arithmetic mean of these d values. The protocol to compute this function works as follows: P.sub.0 and P.sub.1 begin with arithmetic shares (e.g. over .sub.L in PIE.sub.OT) of a.sub.i, for all i∈[d]. They perform local addition to obtain shares of w=Σ.sub.i=1d a.sub.i (i.e., P.sub.b computes w.sub.b.sup.L=Σ.sub.i=1.sup.da.sub.i.sub.b.sup.L). Then, parties invoke .sub.Div.sup.ring,L,d on inputs w.sub.b.sup.L to obtain the desired output. Correctness and security follow in therein .sub.Div.sup.ring,L,d-hybrid model. Here too, unlike prior works, our secure execution is bitwise equal to the cleartext version.

[0113] 5.1.3 Batch Normalization. This layer takes as input vectors c, x, d of the same length, and outputs c⊙x+d, where c⊙x refers to the element-wise product of the vectors c and x. Moreover, c and d are a function of the mean and the variance of the training data set, and some parameters learnt during training. Hence, c and d are known to model owner, i.e., P.sub.0. This layer can be computed using techniques of secure multiplication.

[0114] 5.2 Nonlinear Layers

[0115] 5.2.1 ReLU. Note that ReLU(a)=a if a≥0, and 0 otherwise. Equivalently, ReLU(a)=ReLU′(a).Math.a. Once we compute the boolean shares of ReLU′(a) using a call to we compute shares of ReLU(a) using a call to multiplexer functionality .sub.MUX.sup.L (Section 2.2.3). We describe the protocol for ReLU(a) over .sub.L formally in Algorithm 8, Appendix B (the case of Z.sub.n follows in a similar manner). For communication complexity, refer to Table 2 for comparison with garbled circuits and Appendix B for detailed discussion.

[0116] 5.2.2 Maxpool.sub.d and Argmax.sub.d. The function Maxpool.sub.d (a.sub.1, . . . , a.sub.d) over d elements a.sub.1, . . . , a.sub.d is defined in the following way. Define gt(x,y)=z, where w=x−y and z=x, if w>0 and z=y, if w≤0. Define z.sub.1=a.sub.1 and z.sub.i=gt(a.sub.i, z.sub.i−1), recursively for all 2≤i≤d. Now, Maxpool.sub.d (a.sub.1, . . . , a.sub.d)=z.sub.d.

[0117] We now describe a protocol such that parties begin with arithmetic shares (over .sub.L) of a.sub.i, for all i∈[d] and end the protocol with arithmetic shares (over .sub.L) of Maxpool.sub.d (a.sub.1, . . . , a.sub.d). For simplicity, we describe how P.sub.0 and P.sub.1 can compute shares of z=gt(x,y) (beginning with the shares of x and y). It is easy to see then how they can compute Maxpool.sub.d. First, parties locally compute shares of w=x−y (i.e., P.sub.b computes w.sub.b.sup.L=x.sub.b.sup.L−y.sub.b.sup.L, for b∈{0, 1}). Next, they invoke with input w.sub.b.sup.L to learn output v.sub.b.sup.B. Now, they invoke .sub.MUX.sup.L with input w.sub.b.sup.L and v.sub.b.sup.B to learn output t.sub.b.sup.L. Finally, parties' output z.sub.b.sup.L=y.sub.b.sup.L+t.sub.b.sup.L. The correctness and security of the protocol follows in a straightforward manner. Computing Maxpool d is done using d−1 invocations of the above sub-protocol in d−1 sequential steps.

[0118] Argmax.sub.d (a.sub.1, . . . , a.sub.d) is defined similar to Maxpool.sub.d (a.sub.1, . . . , a.sub.d), except that its output is an index i*s.t. a.sub.i*=Maxpool.sub.d (a.sub.1, . . . , a.sub.d). Argmax.sub.d can be computed securely similar to Maxpool.sub.d (a.sub.1, . . . , a.sub.d).

6 Implementation

[0119] We implement our cryptographic protocols in a library PIE and integrate them into the CrypTFlow framework [1, 44] as a new cryptographic backend. CrypTFlow compiles high-level Tensor-Flow [3] inference code to secure computation protocols, that are then executed by its cryptographic backends. We modify the truncation behavior of CrypTFlow's float-to-fixed compiler, Athos, in support of faithful fixed-point arithmetic. We start by describing the implementation of our cryptographic library, followed by the modifications that we made to Athos.

[0120] 6.1 Cryptographic Backend

[0121] To implement our protocols, we build upon the

[00047]$\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{COT}}_{\ell }$

implementation from EMP [61] and extend it to

[00048]$\left(\begin{array}{c}k\\ 1\end{array}\right)-{\mathrm{COT}}_{\ell }$

using the protocol from [43]. Our linear-layer implementation using PIE.sub.HE is based on SEAL/Delphi [2, 57] and PIE.sub.OT is based on EMP. All our protocol implementations are multi-threaded.

[0122] Oblivious Transfer.

[00049]$\left(\begin{array}{c}k\\ 1\end{array}\right)-{\mathrm{COT}}_{\ell }$

uses AES.sub.256.sup.IC as a hash function in the random oracle model to mask the sender's messages in the OT extension protocol of [43] (There are two types of AES in MPC applications—fixed key (FK) and ideal cipher (IC) [10, 34]. While the former runs key schedule only once and is more efficient, the latter generates a new key schedule for every invocation and is required in this application. It is parameterized by the key size, which is 256 in this case). We incorporated the optimizations from [32, 33] for AES key expansion and pipelining these AES.sub.256.sup.IC calls. This leads to roughly 6× improvement in the performance of AES.sub.256.sup.IC calls, considerably improving the overall execution time of

[00050]$\left(\begin{array}{c}k\\ 1\end{array}\right)-{\mathrm{COT}}_{\ell }$

(e.g. 2.7× over LAN for

[00051]$\left(\begin{array}{c}16\\ 1\end{array}\right)-{\mathrm{COT}}_8.$

[0123] Millionaires' protocol. Recall that m is a parameter in our protocol . While we discussed the dependence of communication complexity on m in Section 3.1.2, here we discuss its influence on the computational cost. Our protocol makes calls to

[00052]$\left(\begin{array}{c}M\\ 1\end{array}\right)-{\mathrm{OT}}_2$

(after merging steps 9&10), where M=2.sup.m. Using OT extension techniques, generating an instance of

[00053]$\left(\begin{array}{c}M\\ 1\end{array}\right)-{\mathrm{OT}}_2$

requires 6 AES.sub.256.sup.IC and (M+1) AES.sub.256.sup.IC evaluations. Thus, the computational cost grows super-polynomial with m. We note that for =32, even though communication is minimized for m=7, empirically we observe that m=4 gives us the best performance under both LAN and WAN settings (communication in this case is about 30% more than when m=7 but computation is 3× lower).

[0124] Implementing linear layers in PIE.sub.HE. To implement the linear layers in PIE.sub.HE, we build upon the Delphi implementation [2, 48], that is in turn based on the SEAL library [57]. We implement the fully connected layers as in [48]. For convolution layers, we parallelize the code, employ modulus-switching [57] to reduce the ciphertext modulus (and hence ciphertext size), and implement the strided convolutions proposed in Gazelle [42] These optimizations resulted in significant performance improvement of convolution layers. E.g. for the first convolution layer of ResNet50, the runtime decreased from 306s to 18s in the LAN setting and communication decreased from 204 MiB to 76 MiB (Layer parameters: image size 230×230, filter size 7×7, input channels 3, output channels 64, and stride size 2×2).

[0125] 6.2 CrypTFlow Integration

[0126] We integrate our protocols into the CrypTFlow framework [1, 44] as a new cryptographic backend. CrypTFlow's float-to-fixed compiler, Athos, outputs fixed-point DNNs that use 64-bit integers and sets an optimal scale using a validation set. CrypTFlow required 64-bits to ensure that the probability of local truncation errors in its protocols is small (Section 5.1.1). Since our protocols are correct and have no such errors, we extend Athos to set both the bitwidth and the scale optimally using the validation set. The bitwidth and scale leak information about the weights and this leakage is similar to the prior works on secure inference [42, 44, 47-50, 60].

[0127] Implementing faithful truncations using requires the parties to communicate. We implement the following peephole optimizations in Athos to reduce the cost of these truncation calls. Consider a DNN having a convolution layer followed by a ReLU layer. While truncation can be done immediately after the convolution, moving the truncation call to after the ReLU layer can reduce the cost of our protocol . Since the values after ReLU are guaranteed to be all positive, the call to within it (step 2 in Algorithm 5) now becomes redundant and can be omitted. Our optimization further accounts for operations that may occur between the convolutions and ReLU, say a matrix addition. Moving the truncation call from immediately after convolution to after ReLU means the activations flowing into the addition operation are now scaled by 2s, instead of the usual s. For the addition operation to then work correctly, we scale the other argument of addition by s as well. These optimizations are fully automatic and need no manual intervention.

7 Experiments

[0128] We empirically validate the following claims: [0129] In Section 7.1, we show that our protocols for computing ReLU activations are more efficient than state-of-the-art garbled circuits-based implementations (Table 4). Additionally, our division protocols outperforms garbled circuits when computing average pool layers (Table 7). [0130] On the DNNs considered by prior work on secure inference, our protocols can evaluate the non-linear layers much more efficiently (Section 7.2). [0131] We show the first empirical evaluation of 2-party secure inference on ImageNet-scale benchmarks (Section 7.3). These results show the tradeoffs between OT and HE-based secure DNN inference (Table 6).

[0132] We start with a description of our experimental setup and benchmarks, followed by the results.

[0133] Experimental Setup. We ran our benchmarks in two network settings, namely, a LAN setting with both machines situated in West Europe, and transatlantic WAN setting with one of the machines in East US. The bandwidth between the machines is 377 MBps and 40 MBps in the LAN and the WAN setting respectively and the echo latency is 0.3 ms and 80 ms respectively. Each machine has commodity class hardware: 3.7 GHz Intel Xeon processor with 4 cores and 16 GBs of RAM.

[0134] Our Benchmarks. We evaluate on the ImageNet-scale benchmarks considered by [44]: SqueezeNet [39], ResNet50 [36], and DenseNet121 [37]. To match the reported accuracies, we need 37-bit fixed-point numbers for ResNet50, whereas 32 bits suffice for DenseNet121 and SqueezeNet. Recall that our division protocols lead to correct secure executions and there is no accuracy loss in going from cleartext inference to secure inference. A brief summary of the complexity of these benchmarks is given in Appendix F.

[0135] 7.1 Comparison with Garbled Circuits

[0136] We compare with EMP-toolkit [61], the state-of-the-art library for Garbled Circuits (GC). FIG. 4 shows the improvement of our ReLU protocols over GC in both LAN and WAN settings.

[0137] On the x-axis, which is in log-scale, the number of ReLUs range from 2.sup.0 to 2.sup.20. The histogram shows, using the right y-axis, the cumulative number of layers in our benchmarks (SqueezeNet, ResNet50, DenseNet121) which require the number of ReLU activations given on the x-axis. We observe that these DNNs have layers that compute between 2.sup.13 and 2.sup.20 ReLUs. For such layers, we observe (on the left y-axis) that our protocols are 2×-25× faster than GC—the larger the layers the higher the speedups, and gains are larger in the WAN settings. Specifically, for WAN and >2.sup.17 ReLUs, the speedups are much higher than the LAN setting. Here, the cost of rounds is amortized over large layers and the communication cost is a large fraction of the total runtime. Note that our implementations perform load-balancing to leverage full-duplex TCP.

[0138] Next, we compare the time taken by GC and our protocols in computing the ReLU activations of our benchmarks in Table 4.

TABLE-US-00009 TABLE 4 Performance comparison of Garbled Circuits with our protocols for computing ReLU layers. Runtimes are in seconds and communication numbers are in GiB. Garbled Circuits Our Protocols Benchmark LAN WAN Comm LAN WAN Comm (a) over SqueezeNet 26.4 265.6 7.63 3.5 33.3 1.15 ResNet50 136.5 1285.2 39.19 16.4 69.4 5.23 DenseNet121 199.6 1849.3 56.57 24.8 118.7 8.21 (b) over  .sub.n SqueezeNet 51.7 525.8 16.06 5.6 50.4 1.77 ResNet50 267.5 2589.7 84.02 28.0 124.0 8.55 DenseNet121 383.5 3686.2 118.98 41.9 256.0 12.64

[0139] Our protocol over .sub.L is up to 8× and 18× faster than GC in the LAN and WAN settings respectively, while it is ≈7× more communication efficient. As expected, our protocol over .sub.n has even better gains over GC. Specifically, it is up to 9× and 21× faster in the LAN and WAN settings respectively, and has 9× less communication.

[0140] We also performed a similar comparison of our protocols with GC for the Avgpool layers of our benchmarks, and saw up to 51× reduction in runtime and 41× reduction in communication. We report the concrete performance numbers and discuss the results in more detail in Appendix G.

[0141] 7.2 Comparison with State-of-the-Art

[0142] In this section, we compare with Gazelle [42] and Delphi [48], which are the current state-of-the-art for 2-party secure DNN inference that outperform [13, 14, 18, 20, 23, 30, 47, 55]. They use garbled circuits for implementing their non-linear layers, and we show that with our protocols, the time taken to evaluate the non-linear layers of their benchmarks can be decreased significantly.

[0143] For a fair evaluation, we demonstrate these improvements on the benchmarks of Delphi [48], i.e., the MiniONN (CIFAR-10) [47] and ResNet32 (CIFAR-100) DNNs (as opposed to the ImageNet-scale benchmarks for which their systems have not been optimized). For these benchmarks, Gazelle and Delphi have the same total time and communication; we refer to them as GD. Since Gazelle's choice of parameters was insecure, which was later fixed in Delphi, we use Delphi's implementation for comparing with them.)

[0144] In Table 5, we report the performance of GD for evaluating the linear and non linear components of MiniONN and ResNet32 separately, along with the performance of our protocols for the same non-linear computation (Our non-linear time includes the cost of truncation).

TABLE-US-00010 TABLE 5 Performance comparison of our protocols for non-linear layers with Gazelle/Delphi (GD). Runtimes are in seconds and communication numbers are in GiB. Benchmark Computation LAN WAN Comm MiniONN GD linear 10.7 11.4 0.02 GD Non-Linear 30.2 124.0 3.15 Our Non-Linear 1.0 14.5 0.28 ResNet32 GD Linear 15.9 22.7 0.07 GD Non-Linear 52.9 211.3 5.51 Our Non-Linear 2.4 45.3 0.59

[0145] The table shows that the time to evaluate non-linear layers is the bulk of the total time and our protocols are 4×-30× faster in evaluating the non-linear layers. Also note that we reduce the communication by 11× on MiniONN, and require around 9× less communication on ResNet32.

[0146] 7.3 Evaluation on Practical DNNs

[0147] With all our protocols and implementation optimizations in place, we demonstrate the scalability of PIE by efficiently running ImageNet-scale secure inference. Table 6 shows that both our backends, PIE.sub.OT and PIE.sub.HE, are efficient enough to evaluate SqueezeNet in under a minute and scale to ResNet50 and DenseNet121.

TABLE-US-00011 TABLE 6 Performance of PIE on ImageNet-scale benchmarks. Runtimes are in seconds and communication in GiB. Benchmark Protocol LAN WAN Comm SqueezeNet PIE.sub.OT 44.3 293.6 26.07 PIE.sub.HE 59.2 156.6 5.27 ResNet50 PIE.sub.OT 619.4 3611.6 370.84 PIE.sub.HE 545.8 936.0 32.43 DenseNet121 PIE.sub.OT 371.4 2257.7 217.19 PIE.sub.HE 463.2 1124.7 35.56

[0148] In the LAN setting, for both SqueezeNet and DenseNet121, PIE.sub.OT performs better than PIE.sub.HE by at least 20% owing to the higher compute in the latter. However, the quadratic growth of communication with bitlength in the linear-layers of PIE.sub.OT can easily drown this difference if we go to higher bitlengths. Because ResNet50, requires 37-bits (compared to 32 in SqueezeNet and DenseNet121) to preserve accuracy, PIE.sub.HE outperforms PIE.sub.OT in both LAN and WAN settings. In general for WAN settings where communication becomes the major performance bottleneck, PIE.sub.HE performs better than PIE.sub.OT: 2× for SqueezeNet and DenseNet121 and 4× for ResNet50. Overall, with PIE, we could evaluate all the 3 benchmarks within 10 minutes on LAN and 20 minutes on WAN. Since PIE supports both PIE.sub.OT and PIE.sub.HE, one can choose a specific backend depending on the network statistics [18, 52] to get the best secure inference latency. To the best of our knowledge, no prior system provides this support for OT and HE-based secure DNN inference.

8 Conclusion

[0149] We have presented secure, efficient, and correct implementations of practical 2-party DNN inference that outperform prior work in both latency and scale. Like all prior work on 2PC for secure DNN inference, PIE only considers semi-honest adversaries.

9. Computing System

[0150] Because the principles described herein are performed in the context of a computing system, some introductory discussion of a computing system will be described with respect to FIG. 4. Computing systems are now increasingly taking a wide variety of forms. Computing systems may, for example, be handheld devices, appliances, laptop computers, desktop computers, mainframes, distributed computing systems, data centers, or even devices that have not conventionally been considered a computing system, such as wearables (e.g., glasses). In this description and in the claims, the term “computing system” is defined broadly as including any device or system (or a combination thereof) that includes at least one physical and tangible processor, and a physical and tangible memory capable of having thereon computer-executable instructions that may be executed by a processor. The memory may take any form and may depend on the nature and form of the computing system. A computing system may be distributed over a network environment and may include multiple constituent computing systems.

[0151] As illustrated in FIG. 4, in its most basic configuration, a computing system 400 includes at least one hardware processing unit 402 and memory 404. The processing unit 402 includes a general-purpose processor. Although not required, the processing unit 402 may also include a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), or any other specialized circuit. In one embodiment, the memory 404 includes a physical system memory. That physical system memory may be volatile, non-volatile, or some combination of the two. In a second embodiment, the memory is non-volatile mass storage such as physical storage media. If the computing system is distributed, the processing, memory and/or storage capability may be distributed as well.

[0152] The computing system 400 also has thereon multiple structures often referred to as an “executable component”. For instance, the memory 404 of the computing system 400 is illustrated as including executable component 406. The term “executable component” is the name for a structure that is well understood to one of ordinary skill in the art in the field of computing as being a structure that can be software, hardware, or a combination thereof. For instance, when implemented in software, one of ordinary skill in the art would understand that the structure of an executable component may include software objects, routines, methods (and so forth) that may be executed on the computing system. Such an executable component exists in the heap of a computing system, in computer-readable storage media, or a combination.

[0153] One of ordinary skill in the art will recognize that the structure of the executable component exists on a computer-readable medium such that, when interpreted by one or more processors of a computing system (e.g., by a processor thread), the computing system is caused to perform a function. Such structure may be computer readable directly by the processors (as is the case if the executable component were binary). Alternatively, the structure may be structured to be interpretable and/or compiled (whether in a single stage or in multiple stages) so as to generate such binary that is directly interpretable by the processors. Such an understanding of example structures of an executable component is well within the understanding of one of ordinary skill in the art of computing when using the term “executable component”.

[0154] The term “executable component” is also well understood by one of ordinary skill as including structures, such as hard coded or hard wired logic gates, that are implemented exclusively or near-exclusively in hardware, such as within a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), or any other specialized circuit. Accordingly, the term “executable component” is a term for a structure that is well understood by those of ordinary skill in the art of computing, whether implemented in software, hardware, or a combination. In this description, the terms “component”, “agent”, “manager”, “service”, “engine”, “module”, “virtual machine” or the like may also be used. As used in this description and in the case, these terms (whether expressed with or without a modifying clause) are also intended to be synonymous with the term “executable component”, and thus also have a structure that is well understood by those of ordinary skill in the art of computing.

[0155] In the description that follows, embodiments are described with reference to acts that are performed by one or more computing systems. If such acts are implemented in software, one or more processors (of the associated computing system that performs the act) direct the operation of the computing system in response to having executed computer-executable instructions that constitute an executable component. For example, such computer-executable instructions may be embodied on one or more computer-readable media that form a computer program product. An example of such an operation involves the manipulation of data. If such acts are implemented exclusively or near-exclusively in hardware, such as within a FPGA or an ASIC, the computer-executable instructions may be hard-coded or hard-wired logic gates. The computer-executable instructions (and the manipulated data) may be stored in the memory 404 of the computing system 400. Computing system 400 may also contain communication channels 408 that allow the computing system 400 to communicate with other computing systems over, for example, network 410.

[0156] While not all computing systems require a user interface, in some embodiments, the computing system 400 includes a user interface system 412 for use in interfacing with a user. The user interface system 412 may include output mechanisms 412A as well as input mechanisms 412B. The principles described herein are not limited to the precise output mechanisms 412A or input mechanisms 412B as such will depend on the nature of the device. However, output mechanisms 412A might include, for instance, speakers, displays, tactile output, virtual or augmented reality, holograms and so forth. Examples of input mechanisms 412B might include, for instance, microphones, touchscreens, virtual or augmented reality, holograms, cameras, keyboards, mouse or other pointer input, sensors of any type, and so forth.

[0157] Embodiments described herein may comprise or utilize a special-purpose or general-purpose computing system including computer hardware, such as, for example, one or more processors and system memory, as discussed in greater detail below. Embodiments described herein also include physical and other computer-readable media for carrying or storing computer-executable instructions and/or data structures. Such computer-readable media can be any available media that can be accessed by a general-purpose or special-purpose computing system. Computer-readable media that store computer-executable instructions are physical storage media. Computer-readable media that carry computer-executable instructions are transmission media. Thus, by way of example, and not limitation, embodiments of the invention can comprise at least two distinctly different kinds of computer-readable media: storage media and transmission media.

[0158] Computer-readable storage media includes RAM, ROM, EEPROM, CD-ROM, or other optical disk storage, magnetic disk storage, or other magnetic storage devices, or any other physical and tangible storage medium which can be used to store desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general-purpose or special-purpose computing system.

[0159] A “network” is defined as one or more data links that enable the transport of electronic data between computing systems and/or modules and/or other electronic devices. When information is transferred or provided over a network or another communications connection (either hardwired, wireless, or a combination of hardwired or wireless) to a computing system, the computing system properly views the connection as a transmission medium. Transmission media can include a network and/or data links which can be used to carry desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general-purpose or special-purpose computing system. Combinations of the above should also be included within the scope of computer-readable media.

[0160] Further, upon reaching various computing system components, program code means in the form of computer-executable instructions or data structures can be transferred automatically from transmission media to storage media (or vice versa). For example, computer-executable instructions or data structures received over a network or data link can be buffered in RANI within a network interface module (e.g., a “NIC”), and then be eventually transferred to computing system RANI and/or to less volatile storage media at a computing system. Thus, it should be understood that storage media can be included in computing system components that also (or even primarily) utilize transmission media.

[0161] Computer-executable instructions comprise, for example, instructions and data which, when executed at a processor, cause a general-purpose computing system, special-purpose computing system, or special-purpose processing device to perform a certain function or group of functions. Alternatively, or in addition, the computer-executable instructions may configure the computing system to perform a certain function or group of functions. The computer executable instructions may be, for example, binaries or even instructions that undergo some translation (such as compilation) before direct execution by the processors, such as intermediate format instructions such as assembly language, or even source code.

[0162] Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the described features or acts described above. Rather, the described features and acts are disclosed as example forms of implementing the claims.

[0163] Those skilled in the art will appreciate that the invention may be practiced in network computing environments with many types of computing system configurations, including, personal computers, desktop computers, laptop computers, message processors, hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, mobile telephones, PDAs, pagers, routers, switches, datacenters, wearables (such as glasses) and the like. The invention may also be practiced in distributed system environments where local and remote computing system, which are linked (either by hardwired data links, wireless data links, or by a combination of hardwired and wireless data links) through a network, both perform tasks. In a distributed system environment, program modules may be located in both local and remote memory storage devices.

[0164] Those skilled in the art will also appreciate that the invention may be practiced in a cloud computing environment. Cloud computing environments may be distributed, although this is not required. When distributed, cloud computing environments may be distributed internationally within an organization and/or have components possessed across multiple organizations. In this description and the following claims, “cloud computing” is defined as a model for enabling on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services). The definition of “cloud computing” is not limited to any of the other numerous advantages that can be obtained from such a model when properly deployed.

[0165] For the processes and methods disclosed herein, the operations performed in the processes and methods may be implemented in differing order. Furthermore, the outlined operations are only provided as examples, and some of the operations may be optional, combined into fewer steps and operations, supplemented with further operations, or expanded into additional operations without detracting from the essence of the disclosed embodiments.

10. Appendix

A. Supporting Protocols

[0166] Here, we describe supporting protocols that our main protocols rely on.

[0167] A.1 Protocol for Regular .sub.and

[0168] Regular .sub.AND can be realized using bit-triples [8], which are of the form (d).sub.b.sup.B, e.sub.b.sup.B, f.sub.b.sup.B), where b∈{0, 1} and d∧e=f. Using an instance of

[00054]$\left(\begin{array}{c}16\\ 1\end{array}\right)-{\mathrm{OT}}_2,$

the parties can generate two bit-triples. We describe this protocol for generating the first triple, and from there, it will be easy to see how to also generate the second one. The parties start by sampling random shares

[00055]${.Math.d.Math.}_b^B,{.Math.e.Math.}_b^B\stackrel{\$}{\leftarrow }\left\{0,1\right\}\mathrm{for}b\in \left\{0,1\right\}.$

P.sub.1 sets the first two bits of its input to

[00056]$\left(\begin{array}{c}16\\ 1\end{array}\right)-O{T}_2,$

as d.sub.1.sup.B∥e.sub.1.sup.B, while the other two bits are used for the second triple. P.sub.0 samples a random bit r and sets its input messages to

[00057]$\left(\begin{array}{c}16\\ 1\end{array}\right)-{\mathrm{OT}}_2$

as follows: for the i-th message, where i∈{0, 1}.sup.4, P.sub.0 uses the first two bits i.sub.1∥i.sub.2 of i to compute r⊕((i.sub.1⊕d.sub.0.sup.B∧(i.sub.2⊕e.sub.0.sup.B)), and sets it as the first bit of the message, while reserving the second bit for the other triple. Finally, P.sub.0 sets f.sub.0.sup.B=r, and P.sub.1 sets the first bit of the output of

[00058]$\left(\begin{array}{c}16\\ 1\end{array}\right)-O{T}_2\mathrm{as}{.Math.f.Math.}_1^B.$

Correctness can be seen by noting that f.sub.1.sup.B=f.sub.0.sup.B⊕(d∧e), and since f.sub.0.sup.B is uniformly random, security follows directly in the

[00059]$\left(\begin{array}{c}16\\ 1\end{array}\right)-{\mathrm{OT}}_2-\mathrm{hybrid}.$

[0169] The communication of this protocol is the same as that of

[00060]$\left(\begin{array}{c}16\\ 1\end{array}\right)-O{T}_2,$

which is 2λ+16.Math.2 bits. Since we generate two bit-triples using this protocol, the amortized cost per triple is λ+16 bits, which is 144 for λ=128.

[0170] A.2 Protocol for Correlated .sub.AND

[0171] Correlated triples are two sets of bit triples (d.sub.b.sup.B, e.sub.b.sup.B, f.sub.b.sup.B) and (d′.sub.b.sup.B), e′.sub.b.sup.B, f′.sub.b.sup.B), for b∈{0, 1}, such that e=e′, d∧e=f, and d′∧e′=f′. The protocol from Appendix A.1 used a

[00061]$\left(\begin{array}{c}16\\ 1\end{array}\right)-O{T}_2$

invocation to generate two regular triples, where the 4 bits of P.sub.1's input were its shares of d, e, d′, and e′. However, when generating correlated triples, we can instead use an instance of

[00062]$\left(\begin{array}{c}8\\ 1\end{array}\right)-O{T}_2$

because e=e′, and thus, 3 bits suffice to represent P.sub.1's input. Correctness and security follow in a similar way as in the case of regular .sub.AND (see Appendix A.1).

[0172] The communication of this protocol is equal to that of

[00063]$\left(\begin{array}{c}8\\ 1\end{array}\right)-O{T}_2,$

which costs 2λ+8.Math.2 bits. Thus, we get an amortized communication of λ+8 bits per correlated triple.

[0173] A.3 Protocol for Multiplexer

[0174] We describe our protocol for realizing .sub.MUX.sup.2 in Algorithm 6. First we argue correctness. Let c=Reconst.sup.B(c.sub.0.sup.B, c.sub.1.sup.B)=c.sub.0.sup.B⊕c.sub.1.sup.B. By correctness of

[00064]$\left(\begin{array}{c}2\\ 1\end{array}\right)-O{T}_{\eta },$

x.sub.1=−r.sub.0+c.Math.a.sub.0.sup.n. Similarly, x.sub.0=−r.sub.1+c.Math.a.sub.1.sup.n. Hence, Reconst.sup.n (z.sub.0.sup.n, a.sub.1.sup.n)=z.sub.0+z.sub.1=c.Math.a. Security trivially follows in

[00065]$\left(\begin{array}{c}2\\ 1\end{array}\right)-O{T}_{\eta }-\mathrm{hybrid}.$

Communication complexity is 2(λ+λη).

TABLE-US-00012 Algorithm 6 Multiplexer, Π.sub.MUX.sup.n: Input: For b ∈ {0, 1}, P.sub.b holds   a  .sub.b.sup.n and   c  .sub.b.sup.B. Output: For b ∈ {0, 1}, P.sub.b learns  z  .sub.b.sup.n s.t. z = a if c = 1, else z = 0. 1: [00066]$\mathrm{For}b\in \left\{0,1\right\},P_b\mathrm{picks}{r}_b\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n.$ 2: P.sub.0 sets s.sub.0, s.sub.1 as follows: If   c  .sub.0.sup.B= 0, (s.sub.0, s.sub.1) = (−r.sub.0, −r.sub.0 +   a  .sub.0.sup.n ). Else, (s.sub.0, s.sub.1) = (−r.sub.0+  a  .sub.0.sup.n, −r.sub.0). 3: P.sub.0 & P.sub.1 invoke an instance of [00067]$\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{OT}}_{\eta }$  where P.sub.0 is the sender with inputs (s.sub.0, s.sub.1) and P.sub.1 is the receiver with input  c  .sub.1.sup.B. Let P.sub.1′s output be x.sub.1. 4: P.sub.1 sets t.sub.0, t.sub.1 as follows: If   c  .sub.1.sup.B = 0, (t.sub.0, t.sub.1) = (−r.sub.1, −r.sub.1 +   a  .sub.1.sup.n ).Else, (t.sub.0, t.sub.1) =(−r.sub.1 + a  .sub.1.sup.n, −r.sub.1). 5: P.sub.0 & P.sub.1 invoke an instance of [00068]$\left(\begin{array}{c}2\\ 1\end{array}\right)-{\mathrm{OT}}_{\eta }$  where P.sub.1 is the sender with inputs (t.sub.0, t.sub.1) and P.sub.0 is the receiver with input  c  .sub.0.sup.B. Let P.sub.0′s output be x.sub.0. 6: For b ∈ {0, 1}, P.sub.b outputs   z  .sub.b.sup.n = r.sub.b + x.sub.b.

[0175] A.4 Protocol for B2A

[0176] We describe our protocol for realizing .sub.B2A.sup.n formally in Algorithm 7. For correctness, we need to show that d=Reconst.sup.L (d.sub.0.sup.n, d.sub.1.sup.n)=c.sub.0.sup.B+c.sub.1.sup.B−2c.sub.0.sup.B c.sub.1.sup.B. By correctness of

[00069]$\left(\begin{array}{c}2\\ 1\end{array}\right)-CO{T}_{\eta },y1=x+{.Math.c.Math.}_0^B{.Math.c.Math.}_1^B.$

Using this, d.sub.0.sup.n=c.sub.0.sup.B+2x and d.sub.1.sup.n=c.sub.1.sup.B−2x−2c.sub.0.sup.Bc.sub.1.sup.B. Security follows from the security of

[00070]$\left(\begin{array}{c}2\\ 1\end{array}\right)-CO{T}_{\eta }$

and communication required is λ+η bits.

TABLE-US-00013 Algorithm 7 Boolean to Arithmetic, Π.sub.B2A.sup.n: Input: P.sub.0, P.sub.1 hold  c  .sub.0.sup.B and   c  .sub.1.sup.B, respectively, where c ∈ {0, 1}. Output: P.sub.0, P.sub.1 learn   d  .sub.0.sup.n and   d  .sub.1.sup.n, respectively, s.t. d = c. 1: [00071]$P_0\&P_1\mathrm{invoke}\mathrm{an}\mathrm{instance}\mathrm{of}\left(\begin{array}{c}2\\ 1\end{array}\right)-C{\mathrm{OT}}_{\eta }\mathrm{where}{P}_0\mathrm{is}\mathrm{the}\mathrm{sender}\mathrm{with}\mathrm{correlation}$ function f (x) = x +   c  .sub.0.sup.B and P.sub.1 is the receiver with input   c  .sub.1.sup.B. Party P.sub.0 learns x and sets y.sub.0 = n − x and P.sub.1 learns y.sub.1. 2: For b ∈ {0, 1}, P.sub.b computes   d  .sub.b.sup.n =   c  .sub.b.sup.B− 2.Math.y.sub.b.

B Protocol for ReLU

[0177] We describe our ReLU protocol for the case where the input and output shares are over .sub.L in Algorithm 8, and note that the case of .sub.n follows similarly. It is easy to see that the correctness and security of the protocol follow in the (, .sub.MUX.sup.L)-hybrid.

[0178] Communication complexity. We first look at the complexity of , which involves a call to , and .sub.MUX.sup.L. , has the same communication as , which requires λ(−1)+13½(−1)−2λ−22 bits if we assume m=4 and m|(−1), and exclude optimization (3.1.1) in the general expression from Section 3.1.2. .sub.MUX.sup.L incurs a cost of 2λ+4 bits, bringing the total cost to λ+17½−λ−35½ bits, which can be rewritten as <lt+18. We get our best communication for =32 (with all the optimizations) by taking m=7 for the Π.sub.MILL.sup.32, invocation inside Π.sub.DReLU.sup.int,32, which gives us a total communication of 3298 bits.

[0179] Now, we look at the complexity of Π.sub.ReLU.sup.ring,n, which makes calls to .sub.DReLU.sup.ring,n and .sub.MUX.sup.n). The cost of .sub.DReLU.sup.ring,n is 2λ+4 bits for

[00072]$\left(\begin{array}{c}4\\ 1\end{array}\right)-OT1,$

plus (3/2) λ(η+1)+27(η+1)−4λ−44 bits for 2 invocations of .sub.MILL.sup.n+1, where P.sub.1's input is the same in both invocations and the same assumptions are made as for the expression of above. The cost of .sub.MUX.sup.n is 2λ+4η bits, and thus, the total cost is (3/2) λ(η+1)+31η−13, which can be rewritten as <(3/2) λ(η+1)+31η. Concretely, we get the best communication for η=32 by taking m=7 for the millionaire invocations, getting a total communication of 5288 bits.

TABLE-US-00014  Algorithm 8   -bit integer ReLU,   : Input: P.sub.0, P.sub.1 hold   a   .sub.0.sup.L and   a   L.sub.1.sup.L , respectively. Output: P.sub.0, P.sub.1 get   ReLU(a)   .sub.0.sup.L and   ReLU(a)   .sub.1.sup.L. 1: For b ϵ {0, 1}, P.sub.b invokes   with input   a   .sub.b.sup.L to learn output   y   .sub.b.sup.B. 2: For b ϵ {0, 1}, PP.sub.b invokes   .sub.MUX.sup.L with inputs   a   .sub.b.sup.L and   y   .sub.b.sup.B to learn   z   .sub.b.sup.L and sets  ReLU(a)   .sub.b.sup.L =   z   .sub.b.sup.L.

C Proof of Division Theorem

[0180] Here, we prove Theorem 4.1.

[0181] From Equation 2, we can write rdiv(a.sub.i.sup.n, d) as:

[00073]$\begin{array}{cc}\begin{array}{c}\mathrm{rdiv}\left({.Math.a.Math.}_i^n,d\right){=}_n\mathrm{idiv}\left(a_i-1\left\{a_i\ge n^{\prime }\right\}.Math.n,d\right)\\ {=}_n\mathrm{idiv}\left(a_i^1.Math.d+a_i^0-1\left\{a_i\ge n^{\prime }\right\}.Math.\left(n^1.Math.d+n^0\right),d\right)\\ {=}_n{a}_i^1-1\left\{a_i\ge n^{\prime }\right\}.Math.n^1+\mathrm{idiv}\left(a_i^0-1\left\{a_i\ge n^{\prime }\right\}.Math.n^0,d\right)\end{array},& \left(3\right)\end{array}$

for i∈{0, 1}. a.sub.u can be expressed as a.sub.u=a.sub.0+a.sub.1−w.Math.n, where the wrap-bit w=1{a.sub.0+a.sub.1≥n}. We can rewrite this as:

[00074]$\begin{array}{cc}\begin{array}{c}{a}_u=a_0+a_1-w.Math.n\\ =\left(a_0^1+a_1^1-w.Math.n^1\right).Math.d+\left(a_0^0+a_1^0-w.Math.n^0\right)\\ =\left(a_0^1+a_1^1-w.Math.n^1+k\right).Math.d+\left(a_0^0+a_1^0-w.Math.n^0-k.Math.d\right)\end{array},& \left(4\right)\end{array}$

for some integer k such that 0≤a.sub.0.sup.0+a.sub.1.sup.0−w.Math.n.sup.0−k.Math.d<d. Similar to Equation 3 and from Equation 4, we can write rdiv(a, d) as:

[00075]$\begin{array}{cc}\begin{array}{c}\mathrm{rdiv}\left(a,d\right){=}_n{a}_0^1+a_1^1-w.Math.n^1+k-1\left\{a\ge n^{\prime }\right\}.Math.n^1+\\ \mathrm{idiv}\left(a_0^0+a_1^0-w.Math.n^0-k.Math.d-1\left\{a\ge n^{\prime }\right\}.Math.n^0,d\right)\\ {=}_n{a}_0^1+a_1^1-w.Math.n^1-1\left\{a\ge n^{\prime }\right\}.Math.n^1+\\ \mathrm{idiv}\left(a_0^0+a_1^0-w.Math.n^0-1\left\{a\ge n^{\prime }\right\}.Math.n^0,d\right)\end{array}.& \left(5\right)\end{array}$

From Equations 3 and 5, we have the following correction term:

[00076]$\begin{array}{cc}c{=}_n\mathrm{rdiv}\left(a,d\right)-\mathrm{rdiv}\left({.Math.a.Math.}_0^n,d\right)-\mathrm{rdiv}\left({.Math.a.Math.}_1^n,d\right){=}_n\left(1\left\{a_0\ge n^{\prime }\right\}+1\left\{a_1\ge n^{\prime }\right\}-w-1\left\{a\ge n^{\prime }\right\}\right).Math.n^1+\mathrm{idiv}\left(a_0^0+a_1^0-w.Math.n^0-1\left\{a\ge n^{\prime }\right\}.Math.n^0,d\right)-\left(\mathrm{idiv}\left(a_0^0-1\left\{a_0\ge n^{\prime }\right\}.Math.n^0,d\right)+\mathrm{idiv}\left(a_1^0-1\left\{a_1\ge n^{\prime }\right\}.Math.n^0,d\right)\right).& \left(6\right)\end{array}$$\begin{array}{cc}{=}_n{c}^1.Math.n^1+c^0-B& \left(7\right)\end{array}$

Let A′.sub.ii=idiv(a.sub.0.sup.0+a.sub.1.sup.0−i.Math.n.sup.0, d). Then the values of the correction terms c.sup.1 and c.sup.0 are as summarized in the following table:

TABLE-US-00015 # 1 (a.sub.0 ≥ n′) 1 (a.sub.1 ≥ n′) 1 (a.sub.u ≥ n′) w c.sup.1 c.sup.0 1 0 0 0 0 0 A′.sub.0 2 0 0 1 0 −1 A′.sub.1 3 0 1 0 1 0 A′.sub.1 4 0 1 1 0 0 A′.sub.1 5 1 0 0 1 0 A′.sub.1 6 1 0 1 0 0 A′.sub.1 7 1 1 0 1 1 A′.sub.1 8 1 1 1 1 0 A′.sub.2

[0182] From the table, we have c.sup.1=corr and can rewrite the correction term as c=.sub.n corr.Math.n.sup.1+c.sup.0−B. Thus, adding corr.Math.n.sup.1−B mod n to rdiv(a.sub.0.sup.n, d)+rdiv(a.sub.1.sup.n, d) accounts for all the correction terms except c.sub.0 mod n.

[0183] Now all that remains to be proven is that c.sup.0=1−C. Let C.sub.0=1{A<d}, C.sub.1=1{A<0}, and C.sub.2=1{A<−d}. Then, we have C=C.sub.0+C.sub.1+C.sub.2. Note from the theorem statement that A=a.sup.0.sub.0+a.sub.1.sup.0 and A=a.sub.0.sup.0+a.sub.1.sup.0−2.Math.n.sup.0 for the cases corresponding to rows 1 and 8 respectively from the table, while A=a.sub.0.sup.0+a.sub.1.sup.0−n.sup.0 for the rest of cases. Thus, it can be herein seen that c.sup.0=idiv(A, d). Also note that −2.Math.d+2≤A≤2.Math.d−2, implying that the range of c.sup.0 is {−2, −1, 0, 1}. Now we look at each value assumed by c.sup.0 separately as follows: [0184] c.sup.0=−2: In this case, we have (A<−d), implying C.sub.0=C.sub.1=C.sub.2=1, and 1−C=−2. [0185] c.sup.0=−1: In this case, we have (−d≤A<0), implying C.sub.0=C.sub.1=1, C.sub.2=0 and 1−C=−1. [0186] c.sup.0=0: In this case, we have (0≤A<d), implying C.sub.0=1, C.sub.1=C.sub.2=0 and 1−C=0. [0187] c.sup.0=1: In this case, we have (d≤A), implying C.sub.0=C.sub.1=C.sub.2=0 and 1−C=1.
Thus, c=.sub.n corr.Math.n.sup.1+(1−C)−B=.sub.n rdiv(a, d)−rdiv(a.sub.0.sup.n, d)−rdiv(a.sub.1.sup.n, d).

D Protocol for General Division

[0188] We describe our protocol for general division formally in Algorithm 9. As discussed in Section 4.2.2, our protocol builds on Theorem 4.1 and we compute the various sub-terms securely using our new protocols. Let δ=┌log δd┐. We compute the shares of corr over both .sub.n and .sub.Δ (Step 15). We write the term C as (ReLU′(A−d)⊕1)+(ReLU′(A)⊕1)+(ReLU′(A+d)⊕1), which can be computed using three calls to .sub.DReLU.sup.int,δ (Step 19) and .sub.B2A.sup.n (Step 20) each.

TABLE-US-00016 Algorithm 9 Integer ring division, Π.sub.DIV.sup.ring,n,d: Input: For b ∈ {0, 1}, P.sub.b holds   a  .sub.b.sup.n, where a ∈  n. Output: For b ∈ {0, 1}, P.sub.b learns  z  .sub.b.sup.n s.t. z = rdiv(a, d). 1: For b ∈ {0, 1}, let a.sub.b, a.sub.b.sup.0, a.sub.b.sup.1 ∈   and n.sup.0, n.sup.1, n′ ∈   be as defined in Theorem 4.1. Let  η = ┌log(n)┐, δ = ┌log 6d┐, and Δ = 2.sup.δ. 2: For b ∈ {0, 1}, P.sub.b invokes  .sub.DReLU.sup.ring,n with input   a  .sub.b.sup.n to learn output   a  .sub.b.sup.B. Party P.sub.b sets   m  .sub.b.sup.B =   α  .sub.b.sup.B ⊕ b. 3: For b ∈ {0, 1}, P.sub.b sets x.sub.b = 1{  α  .sub.b.sup.B ≥ n′}. 4: [00077]$P_0\mathrm{samples}{.Math.\mathrm{corr}.Math.}_0^n\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n\mathrm{and}{.Math.\mathrm{corr}.Math.}_0^{\Delta }\stackrel{\$}{\leftarrow }{\mathbb{Z}}_{\Delta }.$ 5: for j = {00, 01, 10, 11} do 6:   P.sub.0 computes t.sub.j = (  m  .sub.0.sup.B ⊕ j.sub.0 ⊕ x.sub.0) ∧ (  m  .sub.0.sup.B ⊕ j.sub.0 ⊕ j.sub.1) s.t.j = (j.sub.0||j.sub.1). 7:   if t.sub.j ∧ 1{x.sub.0 = 0} then 8:    P.sub.0 sets s.sub.j =.sub.n −  corr  .sub.0.sup.n − 1 and r.sub.j =.sub.Δ −  corr  .sub.0.sup.Δ − 1. 9:   else if t.sub.j ∧ 1{x.sub.0 = 1} then 10:    P.sub.0 sets s.sub.j =.sub.n −  corr  .sub.0.sup.n + 1 and r.sub.j =.sub.Δ −  corr  .sub.0.sup.Δ + 1. 11:   else 12:    P.sub.0 sets s.sub.j =.sub.n −  corr  .sub.0.sup.n and r.sub.j =.sub.Δ −  corr  .sub.0.sup.Δ. 13:   end if 14: end for 15: [00078]$P_0\&P_1\mathrm{invoke}\mathrm{an}\mathrm{instance}\mathrm{of}\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_{\eta +8}\mathrm{where}{P}_0\mathrm{is}\mathrm{the}\mathrm{sender}\mathrm{with}\mathrm{inputs}{\left\{s_j||r_j\right\}}_j$ and P.sub.1 is the receiver with input  m  .sub.1.sup.B||x.sub.1. P.sub.1 sets its output as  corr  .sub.′1.sup.n|| corr  .sub.1.sup.Δ. 16: For b ∈ {0, 1}, P.sub.b sets  A  .sub.b.sup.Δ =.sub.Δ a.sub.b.sup.0 − (x.sub.b −  corr  .sub.b.sup.Δ) .Math. n.sup.0. 17: For b ∈ {0, 1}, P.sub.b sets  A.sub.0  .sub.b.sup.Δ =.sub.Δ  A  .sub.b.sup.Δ− b .Math. d,  A.sub.1  .sub.b.sup.Δ =  A  .sub.b.sup.Δ ,and  A.sub.2  .sub.b.sup.Δ =.sub.Δ  A  .sub.b.sup.Δ+ b .Math. d. 18: for j = {0, 1, 2} do 19:  For b ∈ {0, 1}, P.sub.b invokes  .sub.DReLU.sup.int,δ with input  A.sub.j  .sub.b.sup.Δ to learn output  γ.sub.j  .sub.b.sup.Δ .Math. Party P.sub.b sets  C′j  B.sub.b =  γ.sub.j  .sub.b.sup.B ⊕ b. 20:  For b ∈ {0, 1}, P.sub.b invokes an instance of  .sub.B2A.sup.n with input  C′.sub.j  .sub.b.sup.B and learns  C.sub.j  .sub.b.sup.n. 21: end for 22: For b ∈ {0, 1}, P.sub.b sets  C  .sub.b.sup.n =  C.sub.0  .sub.b.sup.n+  C.sub.1  .sub.b.sup.n+  C.sub.2  .sub.b.sup.n. 23: For b ∈ {0, 1}, P.sub.b sets B.sub.b = idiv(a.sub.b.sup.0− x.sub.b .Math. n.sup.0, d). 24: P.sub.b sets  z  .sub.b.sup.n =.sub.n rdiv(  a  .sub.b.sup.n, d) +  corr  .sub.b.sup.n.Math. n.sup.1 +b −   C  .sub.b.sup.n− B.sub.b, for b ∈ {0, 1}.

[0189] Correctness and Security. First, m=Reconst.sup.B(m.sub.0.sup.B, m.sub.1.sup.B)=Reconst.sup.B(a.sub.0.sup.B, a.sub.1.sup.B)=1{a≥n′}. Next, similar to Algorithm 5, Reconst.sup.L(corr.sub.0.sup.L, corr.sub.1.sup.L)=corr=Reconst.sup.Δ(corr.sub.0.sup.Δ, corr.sub.1.sup.Δ), where corr is as defined in Theorem 4.1. Given the bounds on value of A (as discussed above), we can see that Steps 16 & 17 compute arithmetic shares of A, and A.sub.0=(A−d), A.sub.1=A, A.sub.2=(A+d), respectively. Now, invocation of .sub.DReLU.sup.int,δ on shares of A.sub.j (Step 19) returns boolean shares of γ=(1⊕MSB(A.sub.j)) over δ bit integers, which is same as 1⊕1{A.sub.j<0} over . Hence, C′.sub.j=Reconst.sup.B (C′.sub.j).sub.0.sup.B, C′.sub.1.sup.B)=1{A.sub.j<0}. By correctness of .sub.B2A.sup.n, step 22 computes arithmetic shares of C as defined in Theorem 4.1. In step 23, B.sub.0+B.sub.1=.sub.n B as defined. Hence, correctness holds and z.sub.b.sup.n are shares of rdiv(a, d).

[0190] Given that corr.sub.0.sup.n and corr.sub.0.sup.Δ are uniformly random, security of the protocol can be seen in

[00079]$\left(\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_{\eta +\delta },{ℱ}_{\mathrm{DReLU}}^{\mathrm{int},\delta },{ℱ}_{B2A}^n\right)-\mathrm{hybrid}.$

[0191] Communication complexity. Π.sub.DIV.sup.ring,n,d involves a single call to .sub.DReLU.sup.ring,n and

[00080]$\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_{\eta +\delta },$

and three calls each to .sub.DReLU.sup.int,δ, and .sub.B2A.sup.n. From Appendix B, we have the cost of .sub.DReLU.sup.ring,n as (3/2)λη+27η−λ/2−13 bits.

[00081]$\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_{\eta +\delta }$

and 3×.sub.B2A.sup.n cost 2λ+4.Math.(η+δ) and 3λ+3η bits respectively. Since the cost of is λ+13½−3λ−35½ bits (see Appendix B), 3×.sub.DReLU.sup.int,δ, requires 3λδ+40½δ−9λ−106½ bits of communication. Thus, the overall communication of Π.sub.DIV.sup.ring,n,d is (3/2)λη+34η+3λδ+44½δ−4½λ−119½, which can be rewritten as <(3/2λ+34).Math.(η+2δ). Concretely, we get the best communication for Π.sub.DIV.sup.ring,n,49 (η=32) setting m=7 in all our millionaire invocations, which results in a total communication of 7796 bits.

[0192] Note that for the case of -bit integers, our division protocol would use a call to and

[00082]$\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_{\ell +\delta },$

and three calls each to .sub.DReLU.sup.int,δ, and .sub.B2A.sup.L. The cost of , and 3×.sub.DReLU.sup.int,δ are as mentioned in the previous paragraph, and the cost of

[00083]$\left(\begin{array}{c}4\\ 1\end{array}\right)-O{T}_{\ell +\delta }$

and .sub.B2A.sup.L are 2λ+4.Math.(+δ) and 3λ+3 bits respectively. Thus, the overall communication is λ+3λδ+20½+44½δ−7λ−142 bits, which can be rewritten as <(λ+21).Math.(+3δ). By setting m=8 in all our millionaire invocations, we get the best communication of 5570 bits for Π.sub.DIV.sup.ring,32,49.

E Improvement to Gazelle's Algorithm

[0193] Gazelle [42] proposed two methods for computing convolutions, namely, the input rotations and the output rotations method. The only difference between the two methods is the number of (homomorphic) rotations required (the number of homomorphic additions also differ, but they are relatively very cheap). In this section, we describe an optimization to reduce the number of rotations required by the output rotations method.

[0194] Let c.sub.i and c.sub.o denote the number of input and output channels respectively, and c.sub.n denote the number of channels that can fit in a single ciphertext. At a high level, the output rotations method works as follows: after performing all the convolutions homomorphically, we have c.sub.i.Math.c.sub.o/c.sub.n intermediate ciphertexts that are to be accumulated to form tightly packed output ciphertexts. Since most of these ciphertexts are misaligned after the convolution, they must be rotated in order to align and pack them. The intermediate ciphertexts can be grouped into c.sub.o/c.sub.n groups of c.sub.i ciphertexts each, such that the ciphertexts within each group are added (after alignment) to form a single ciphertext. In [42], the ciphertexts within each group are rotated (aligned) individually, resulting in ≠c.sub.i.Math.c.sub.o/c.sub.n rotations. We observe that these groups can be further divided into c.sub.n subgroups of c.sub.i/c.sub.n ciphertexts each, such that ciphertexts within a subgroup are misaligned by the same offset. Doing this has the advantage that the c.sub.i/c.sub.n ciphertexts within each subgroup can first be added and then the resulting ciphertext can be aligned using a single rotation. This brings down the number of rotations by a factor of c.sub.i/c.sub.n to c.sub.n.Math.c.sub.o/c.sub.n.

[0195] With our optimization, the output rotations method is better than the input rotations method when f.sup.2.Math.c.sub.i>c.sub.o, where f.sup.2 the filter size, which is usually the case.

F Complexity of Our Benchmarks

[0196] The complexity of the benchmarks we use in Section 7 is summarized as follows: [0197] SqueezeNet: There are 26 convolution layers of maximum filter size 3×3 and up to 1000 output channels. The activations after linear layers are ReLUs with size of up to 200,704 elements per layer. All ReLU layers combined have a size of 2,033,480. Additionally, there are 3 Maxpool layers and an Avgpool.sub.169 layer (Avgpool with pool size 169). [0198] ResNet50: There are 53 convolution layers of maximum filter size 7×7 and a peak output channel count of 2048. Convolution layers are followed by batch normalization and then ReLUs. There are 49 ReLU layers totaling 9,006,592 ReLUs, where the biggest one consists of 802,816 elements. Moreover, ResNet50 also has Maxpool layers and an Avgpool.sub.49. [0199] DenseNet121: There are 121 convolution layers with maximum filter dimension of 7×7 and up to 1000 output channels. Similar to ResNet50, between 2 convolution layers, there is batch normalization followed by ReLU. The biggest ReLU layer in DenseNet121 has 802,816 elements and the combined size of all ReLU layers is 15,065,344. In addition, DenseNet121 consists of a Maxpool, an Avgpool.sub.49 and 3 Avgpool.sub.4 layers.

G Garbled Circuits vs Our Protocols for Avgpool

[0200] In this section, we compare our protocols with garbled circuits for evaluating the Avgpool layers of our benchmarks, and the corresponding performance numbers are given in Table 7.

TABLE-US-00017 TABLE 7 Performance comparison of Garbled Circuits with our protocols for computing AVGpool layers. Runtimes are in seconds and communication numbers are in MiB. Garbled Circuits Our Protocol Benchmark LAN WAN Comm LAN WAN Comm (a) over  SqueezeNet 0.2 2.0 36.02 0.1 0.8 1.84 ResNet50 0.4 3.9 96.97 0.1 0.8 2.35 DenseNet121 17.2 179.4 6017.94 0.5 3.5 158.83 (b) over   .sub.n SqueezeNet 0.2 2.2 39.93 0.1 0.9 1.92 ResNet50 0.4 4.2 106.22 0.1 1.0 3.82 DenseNet121 19.2 198.2 6707.94 0.6 4.4 214.94

[0201] On DenseNet121, where a total of 176, 640 divisions are performed, we have improvements over GC of more than 32× and 45× in the LAN and the WAN setting, respectively, for both our protocols. However, on SqueezeNet and ResNet50, the improvements are smaller (2× to 7×) because these DNNs only require 1000 and 2048 divisions, respectively, which are not enough for the costs in our protocols to amortize well. On the other hand, the communication difference between our protocols and GC is huge for all three DNNs. Specifically, we have an improvement of more than 19×, 27×, and 31× on SqueezeNet, ResNet50, and DenseNet121 respectively, for both our protocols.

[0202] The present invention may be embodied in other specific forms without departing from its spirit or characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicate by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.

11. Bibliography

[0203] [1] 2020. CrypTFlow: An End-to-end System for Secure TensorFlow Inference. https://github.com/mpc-msri/EzPC. (2020). [0204] [2] 2020. Delphi: A Cryptographic Inference Service for Neural Networks. https://github.com/mc2-project/delphi. (2020). [0205] [3] Martin Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Gregory S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian J. Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Józefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Gordon Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul A. Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda B. Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2016. TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems. CoRR abs/1603.04467 (2016). https://arxiv.org/abs/1603.04467 [0206] [4] Nitin Agrawal, Ali Shahin Shamsabadi, Matt J. Kusner, and Adrià Gascón. 2019. QUOTIENT: Two-Party Secure Neural Network Training and Prediction. In Proceedings of the 2019 ACMSIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, Nov. 11-15, 2019. 1231-1247. [0207] [5] Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. 2013. More efficient oblivious transfer and extensions for faster secure computation. In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS' 13, Berlin, Germany, Nov. 4-8, 2013, Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung (Eds.). ACM, 535-548. https://doi.org/10.1145/2508859.2516738 [0208] [6] Marshall Ball, Brent Carmer, Tal Malkin, Mike Rosulek, and Nichole Schimanski. 2019. Garbled Neural Networks are Practical. IACR Cryptology ePrint Archive 2019 (2019), 338. https://eprint.iacr.org/2019/338 [0209] [7] Assi Barak, Daniel Escudero, Anders Dalskov, and Marcel Keller. 2019. Secure Evaluation of Quantized Neural Networks. Cryptology ePrint Archive, Report 2019/131. (2019). https://eprint.iacr.org/2019/131. [0210] [8] Donald Beaver. 1991. Efficient Multiparty Protocols Using Circuit Randomization. In Advances in Cryptology—CRYPTO '91, 11th Annual International Cryptology Conference, Santa Barbara, Calif., USA, Aug. 11-15, 1991, Proceedings. 420-432. [0211] [9] Donald Beaver. 1996. Correlated Pseudorandomness and the Complexity of Private Computations. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pa., USA, May 22-24, 1996, Gary L. Miller (Ed.). ACM, 479-488. https://doi.org/10.1145/237814.237996 [0212] [10] Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway. 2013. Efficient Garbling from a Fixed-Key Blockcipher. In 2013 IEEE Symposium on Security and Privacy, S P 2013, Berkeley, Calif., USA, May 19-22, 2013. IEEE Computer Society, 478-492. https://doi.org/10.1109/SP.2013.39 [0213] [11] Mihir Bellare and Phillip Rogaway. 1993. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In CCS '93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Va., USA, Nov. 3-5, 1993, Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby (Eds.). ACM, 62-73. https://doi.org/10.1145/168588.168596 [0214] [12] G. R Blakley. 1979. Safeguarding cryptographic keys. In Managing Requirements Knowledge, International Workshop on. IEEE Computer Society, Los Alamitos, Calif., USA, 313. https://doi.org/10.1109/AFIPS.1979.98 [0215] [13] Fabian Boemer, Anamaria Costache, Rosario Cammarota, and Casimir Wierzynski. 2019. nGraph-HE2: A High-Throughput Framework for Neural Network Inference on Encrypted Data. In Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC@CCS 2019, London, UK, Nov. 11-15, 2019, Michael Brenner, Tancrède Lepoint, and Kurt Rohloff (Eds.). ACM, 45-56. https://doi.org/10.1145/3338469.3358944 [0216] [14] Fabian Boemer, Yixing Lao, Rosario Cammarota, and Casimir Wierzynski. 2019. nGraph HE: A Graph Compiler for Deep Learning on Homomorphically Encrypted Data. In Proceedings of the 16th ACM International Conference on Computing Frontiers, C F 2019, Alghero, Italy, Apr. 30-May 2, 2019. 3-13. [0217] [15] Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. 2015. Machine Learning Classification over Encrypted Data. In 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, Calif., USA, Feb. 8-11, 2015. The Internet Society. https://www.ndss-symposium.org/ndss2015/machine-learning-classification-over-encrypted-data [0218] [16] Zvika Brakerski. 2012. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In Advances in Cryptology—CRYPTO 2012-32nd Annual Cryptology Conference, Santa Barbara, Calif., USA, Aug. 19-23, 2012. Proceedings (Lecture Notes in Computer Science), Reihaneh Safavi-Naini and Ran Canetti (Eds.), Vol. 7417. Springer, 868-886. https://doi.org/10.1007/978-3-642-32009-5_50 [0219] [17] Gilles Brassard, Claude Crépeau, and Jean-Marc Robert. 1986. All-or-Nothing Disclosure of Secrets. In Advances in Cryptology—CRYPTO '86, Santa Barbara, Calif., USA, 1986, Proceedings (Lecture Notes in Computer Science), Andrew M. Odlyzko (Ed.), Vol. 263. Springer, 234-238. https://doi.org/10.1007/3-540-47721-7_17 [0220] [18] Niklas Büscher, Daniel Demmler, Stefan Katzenbeisser, David Kretzmer, and Thomas Schneider. 2018. HyCC: Compilation of Hybrid Protocols for Practical Secure Computation. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, Oct. 15-19, 2018, David Lie, Mohammad Mannan, Michael Backes, and Xiao Feng Wang (Eds.). ACM, 847-861. https://doi.org/10.1145/3243734.3243786 [0221] [19] Ran Canetti. 2000. Security and Composition of Multiparty Cryptographic Protocols. J. Cryptology 13, 1 (2000), 143-202. [0222] [20] Nishanth Chandran, Divya Gupta, Aseem Rastogi, Rahul Sharma, and Shardul Tripathi. 2019. EzPC: Programmable and Efficient Secure Two-Party Computation for Machine Learning. In IEEE European Symposium on Security and Privacy, EuroS&P 2019, Stockholm, Sweden, Jun. 17-19, 2019. 496-511. [0223] [21] Valerie Chen, Valerio Pastro, and Mariana Raykova. 2019. Secure Computation for Machine Learning With SPDZ. CoRR abs/1901.00329 (2019). arXiv:1901.00329 http://arxiv.org/abs/1901.00329 [0224] [22] Geoffroy Couteau. 2018. New Protocols for Secure Equality Test and Comparison. In Applied Cryptography and Network Security—16th International Conference, ACNS 2018, Leuven, Belgium, Jul. 2-4, 2018, Proceedings (Lecture Notes in Computer Science), Bart Preneel and Frederik Vercauteren (Eds.), Vol. 10892. Springer, 303-320. https://doi.org/10.1007/978-3-319-93387-0_16 [0225] [23] Roshan Dathathri, Olli Saarikivi, Hao Chen, Kristin Lauter, Saeed Maleki, Madan Musuvathi, and Todd Mytkowicz. 2019. CHET: An Optimizing Compiler for Fully-Homomorphic Neural-Network Inferencing. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, Phoenix, Ariz., USA, Jun. 22-26, 2019. 142-156. [0226] [24] Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. ABY—A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, Calif., USA, Feb. 8-11, 2015. [0227] [25] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. 2009. ImageNet: A large-scale hierarchical image database. In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 Jun. 2009, Miami, Fla., USA. 248-255. [0228] [26] Shimon Even, Oded Goldreich, and Abraham Lempel. 1985. A Randomized Protocol for Signing Contracts. Commun. ACM 28, 6 (1985), 637-647. https://doi.org/10.1145/3812.3818 [0229] [27] Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144. (2012). http://eprint.iacr.org/2012/144. [0230] [28] Juan A. Garay, Berry Schoenmakers, and José Villegas. 2007. Practical and Secure Solutions for Integer Comparison. In Public Key Cryptography—PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China, Apr. 16-20, 2007, Proceedings (Lecture Notes in Computer Science), Tatsuaki Okamoto and Xiaoyun Wang (Eds.), Vol. 4450. Springer, 330-342. https://doi.org/10.1007/978-3-540-71677-8_22 [0231] [29] Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, Md., USA, May 31-Jun. 2, 2009, Michael Mitzenmacher (Ed.). ACM, 169 178. https://doi.org/10.1145/1536414.1536440 [0232] [30] Ran Gilad-Bachrach, Nathan Dowlin, Kim Lathe, Kristin E. Lauter, Michael Naehrig, and John Wernsing. 2016. CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, N.Y., USA, Jun. 19-24, 2016. 201-210. [0233] [31] Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, N.Y., USA. 218-229. [0234] [32] Shay Gueron. 2016. AES-GCM-SIV implementations (128 and 256 bit). https://github.com/Shay-Gueron/AES-GCM-SIV. (2016). [0235] [33] Shay Gueron, Yehuda Lindell, Ariel Nof, and Benny Pinkas. 2018. Fast Garbling of Circuits Under Standard Assumptions. J. Cryptol. 31, 3 (2018). https://doi.org/10.1007/s00145-017-9271-y [0236] [34] C. Guo, J. Katz, X. Wang, and Y. Yu. 2020. Efficient and Secure Multiparty Computation from Fixed-Key Block Ciphers. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, Los Alamitos, Calif., USA, 247-263. https://doi.org/10.1109/SP.2020. 00016 [0237] [35] Carmit Hazay, Yuval Ishai, Antonio Marcedone, and Muthuramakrishnan Venkitasubramaniam. 2019. LevioSA: Lightweight Secure Arithmetic Computation. In Proceedings of the 2019 ACM Conference on Computer and Communications Security, CCS 2019, London, UK, Nov. 11-15, 2019. 327-344. [0238] [36] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, Nev., USA, Jun. 27-30, 2016. 770-778. [0239] [37] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. 2017. Densely Connected Convolutional Networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, Hi., USA, Jul. 21-26, 2017. 2261-2269. [0240] [38] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. 2016. Binarized Neural Networks. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, Dec. 5-10, 2016, Barcelona, Spain, Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (Eds.). 4107-4115. [0241] [39] Forrest N. Iandola, Matthew W. Moskewicz, Khalid Ashraf, Song Han, William J. Dally, and Kurt Keutzer. 2016. SqueezeNet: AlexNet-level accuracy with 50× fewer parameters and <1 MB model size. CoRR abs/1602.07360 (2016).arXiv:1602.07360 http://arxiv.org/abs/1602.07360 [0242] [40] Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. 2003. Extending Oblivious Transfers Efficiently. In Advances in Cryptology—CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, Calif., USA, Aug. 17-21, 2003, Proceedings (Lecture Notes in Computer Science), Dan Boneh (Ed.), Vol. 2729. Springer, 145-161. https://doi.org/10.1007/978-3-540-45146-4_9 [0243] [41] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew G. Howard, Hartwig Adam, and Dmitry Kalenichenko. 2018. Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, Utah, USA, Jun. 18-22, 2018. 2704-2713. [0244] [42] Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. 2018. GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In 27th USENIX Security Symposium, USENIX Security 2018, Baltimore, Md., USA, Aug. 15-17, 2018. 1651-1669. [0245] [43] Vladimir Kolesnikov and Ranjit Kumaresan. 2013. Improved OT Extension for Transferring Short Secrets. In Advances in Cryptology—CRYPTO 2013-33rd Annual Cryptology Conference, Santa Barbara, Calif., USA, Aug. 18-22, 2013. Proceedings, Part II (Lecture Notes in Computer Science), Ran Canetti and Juan A. Garay (Eds.), Vol. 8043. Springer, 54-70. https://doi.org/10.1007/978-3-642-40084-1_4 [0246] [44] Nishant Kumar, Mayank Rathee, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. 2020. CrypTFlow: Secure TensorFlow Inference. In 2020 IEEE Symposium on Security and Privacy, S&P 2020, San Francisco, Calif., USA, May 18-20, 2020. 1521-1538. [0247] [45] Kim Lathe. 2017. Simple Encrypted Arithmetic Library 2.3.1. https://www.microsoft.com/en-us/research/uploads/prod/2017/11/sealmanual-2-3-1.pdf. [0248] [46] Yehuda Lindell. 2016. How To Simulate It—A Tutorial on the Simulation Proof Technique. Cryptology ePrint Archive, Report 2016/046. (2016). https://eprint.iacr.org/2016/046. [0249] [47] Jian Liu, Mika Juuti, Yao Lu, and N. Asokan. 2017. Oblivious Neural Network Predictions via MiniONN Transformations. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, Tex., USA, Oct. 30-Nov. 3, 2017. 619-631. [0250] [48] Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. 2020. Delphi: A Cryptographic Inference Service for Neural Networks. In 29th USENIX Security Symposium, USENIX Security 20. Boston, Mass. [0251] [49] Payman Mohassel and Peter Rindal. 2018. ABY3: A Mixed Protocol Framework for Machine Learning. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, Oct. 15-19, 2018. 35-52. [0252] [50] Payman Mohassel and Yupeng Zhang. 2017. SecureML: A System for Scalable Privacy-Preserving Machine Learning. In 2017 IEEE Symposium on Security and Privacy, S&P 2017, San Jose, Calif., USA, May 22-26, 2017. 19-38. [0253] [51] Markus Nagel, Mart van Baalen, Tijmen Blankevoort, and Max Welling. 2019. Data-Free Quantization Through Weight Equalization and Bias Correction. In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), Oct. 27-Nov. 2, 2019. IEEE, 1325-1334. [0254] [52] Erman Pattuk, Murat Kantarcioglu, Huseyin Ulusoy, and Bradley A. Malin. 2016. CheapSMC: A Framework to Minimize Secure Multiparty Computation Cost in the Cloud. In Data and Applications Security and Privacy XXX—30th Annual IFIP WG 11.3 Conference, DBSec 2016, Trento, Italy, Jul. 18-20, 2016. Proceedings (Lecture Notes in Computer Science), Silvio Ranise and Vipin Swarup (Eds.), Vol. 9766. Springer, 285 294. [0255] [53] Michael O. Rabin. 1981. How to exchange secrets with oblivious transfer. Technical Report TR-81, Aiken Computation Lab, Harvard University. (1981). https://eprint.iacr.org/2005/187.pdf. [0256] [54] M. Sadegh Riazi, Mohammad Samragh, Hao Chen, Kim Laine, Kristin E. Lauter, and Farinaz Koushanfar. 2019. XONN: XNOR-based Oblivious Deep Neural Network Inference. In 28th USENIX Security Symposium, USENIX Security 2019, Santa Clara, Calif., USA, Aug. 14-16, 2019. 1501-1518. [0257] [55] M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schneider, and Farinaz Koushanfar. 2018. Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications. In Proceedings of the 2018 on Asia Conference on Computer and Communications Security, AsiaCCS 2018, Incheon, Republic of Korea, Jun. 4-8, 2018. 707-721. https://doi.org/10.1145/3196494.3196522 [0258] [56] Bita Darvish Rouhani, M. Sadegh Riazi, and Farinaz Koushanfar. 2018. Deepsecure: scalable provably-secure deep learning. In Proceedings of the 55th Annual Design Automation Conference, D A C 2018, San Francisco, Calif., USA, Jun. 24-29, 2018. ACM, 2:1-2:6. [0259] [57] SEAL 2019. Microsoft SEAL (release 3.3). https://github.com/Microsoft/SEAL. (2019). Microsoft Research, Redmond, Wash. [0260] [58] Adi Shamir. 1979. How to Share a Secret. Commun. ACM 22, 11 (1979), 612-613. https://doi.org/10.1145/359168.359176 [0261] [59] N. P. Smart and F. Vercauteren. 2011. Fully Homomorphic SIMD Operations. Cryptology ePrint Archive, Report 2011/133. (2011). http://eprint.iacr.org/2011/133. [0262] [60] Sameer Wagh, Divya Gupta, and Nishanth Chandran. 2019. SecureNN: 3-Party Secure Computation for Neural Network Training. PoPETs 2019, 3 (2019), 26-49. [0263] [61] Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. 2016. EMP-toolkit: Efficient MultiParty computation toolkit. https://github.com/emp-toolkit. (2016). [0264] [62] Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets (Extended Abstract). In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 Oct. 1986. IEEE Computer Society, 162-167. https://doi.org/10.1109/SFCS.1986.25 [0265] [63] Wenting Zheng, Raluca Ada Popa, Joseph E. Gonzalez, and Ion Stoica. 2019. Helen: Maliciously Secure Coopetitive Learning for Linear Models. In 2019 IEEE Symposium on Security and Privacy, S&P 2019, San Francisco, Calif., USA, May 19-23, 2019. 724 738. [0266] [64] Xiaoyong Zhu, George Iordanescu, Ilia Karmanov, and Mazen Zawaideh. 2018. (March 2018). https://blogs.technet.microsoft.com/machinelearning/2018/03/07/using-microsoft-ai-to-build-a-lung-disease-prediction-model-using-chest-xray-images/