CrypTen: Secure Multi-Party Computation Meets Machine Learning

Introduction

Secure multi-party computation (MPC; ) allows parties to collaboratively perform computations on their combined data sets without revealing the data they possess to each other. This capability of secure MPC has the potential to unlock a variety of machine-learning applications that are currently infeasible because of data privacy concerns. For example, secure MPC can allow medical research institutions to jointly train better diagnostic models without having to share their sensitive patient data or allow social scientists to analyze gender wage gap statistics without companies having to share sensitive salary data . The prospect of such applications of machine learning with rigorous privacy and security guarantees has spurred a number of studies on machine learning via secure MPC . However, at present, adoption of secure MPC in machine learning is still relatively limited considering its wide-ranging potential. One of the main obstacles to widespread adoption is that the complexity of secure MPC techniques puts them out of reach for most machine-learning researchers, who frequently lack in-depth knowledge of cryptographic techniques.

To foster the adoption of secure MPC techniques in machine learning, we present CrypTen: a flexible software framework that aims to make modern secure MPC techniques accessible to machine-learning researchers and developers without a background in cryptography. Specifically, CrypTen provides a comprehensive tensor-computation library in which all computations are performed via secure MPC. CrypTen’s API closely follows the API of the popular PyTorch framework for machine learning , which makes it easy to use for machine-learning practitioners. For example, it provides automatic differentiation and a modular neural-network package. CrypTen assumes an semi-honest threat model [31, §2.3.2] and works for an arbitrary number of parties. To make private training and inference efficient, CrypTen off-loads computations to the GPU and uses high-performance communication libraries to implement interactions between parties.

The paper presents: (1) an overview of CrypTen’s design principles; (2) a description of the design of CrypTen and of the secure MPC protocols implemented; (3) a collection of benchmark experiments using CrypTen to run private versions of state-of-the-art models for text classification, speech recognition, and image classification; and (4) a discussion of open problems and a roadmap for the further development of CrypTen. Altogether, the paper demonstrates that CrypTen’s flexible, PyTorch-like API makes private inference and training of modern machine-learning models easy to implement and efficient. For example, CrypTen allows two parties to privately classify an image in $2$-$3$ seconds, or to securely make phoneme predictions for 16kHz speech recordings faster than real-time. We hope that CrypTen’s promising performance and ease-of-use will foster the adoption of secure MPC by the machine-learning community, and pave the way for a new generation of secure and private machine-learning systems.

Related Work

CrypTen is part of a large body of work that develops secure MPC protocols for machine learning; see Appendix D. Most closely related to our work is CryptGPU , which implements an 2-out-of-3 replicated secret sharing protocol on top of CrypTen. Like CrypTen, CryptGPU provides security against semi-honest corruption, but it is limited to the three-party setting. CryptGPU is one of several protocols optimized for the three-party setting. For example, Falcon implements a maliciously secure three-party MPC protocol, combining techniques from SecureNN and ABY3 . Falcon allows evaluation and training of convolutional networks such as AlexNet and VGG . Other systems that work in this setting include Astra , Blaze , and CrypTFlow .

There also exists a family of two-party systems that, like CrypTen, assume a semi-honest threat model. These systems include Gazelle , Chameleon , EzPC , MiniONN , SecureML , PySyft , and Delphi . XONN also works in the two-party setting but provides malicious security. Compared to these systems, CrypTen provides a more flexible machine-learning focused APICrypTFlow also provides such an API by integrating deeply with TensorFlow , but unlike CrypTen, it does not support PyTorch’s eager execution model or GPU support. that supports reverse-mode automatic differentiation, implements a rich set of functions, and natively runs on GPUs. Moreover, CrypTen supports a wider range of use cases by working with an arbitrary number of parties, and make communication between parties efficient via communication primitives that were optimized for high-performance distributed computing.

Design Principles

In the development of CrypTen, we adopted the following two main design principles:

Machine-learning first API. CrypTen has a general purpose, machine-learning first API design. Most other secure MPC frameworks adopt an API that stays close to the underlying MPC protocols. This hampers adoption of these frameworks in machine learning, for example, because they do not natively support tensor operations (but only scalar operations) and because they lack features that machine-learning researchers have come to expect, such as automatic differentiation. Instead, CrypTen implements the tensor-computation API of the popular PyTorch machine-learning framework , implements reverse-mode automatic differentiation, provides a modular neural-network package with corresponding learning routines, and supports GPU computations. We aim to allow developers to transition code from PyTorch to CrypTen by changing a single Python import.

Eager execution. CrypTen adopts an imperative programming model. This is different from existing MPC frameworks, which generally implement compilers for their own domain-specific languages . While compiler approaches have potential performance benefits, they slow down the development cycle, make debugging harder, and prevent users from using arbitrary host-language constructs . Instead, CrypTen follows the recent trend in machine learning away from graph compilers to frameworks that eagerly execute computations , providing a better developer experience. Yet, CrypTen is performant because it implements state-of-the-art secure MPC protocols (for settings with arbitrary number of parties), because it uses PyTorch’s highly optimized tensor library for most computations, because computations can be off-loaded to the GPU, and because it uses communication libraries that were optimized for high-performance distributed computing.

Design Overview

Figure 1 gives an overview of CrypTen’s design. Parties perform computations using efficient PyTorch tensor operations. Because secure MPC computations are integer computations that are not natively supported on GPUs, CrypTen maps between integer and floating-point computations on GPUs; see Section 5.3. The multi-party computations are implemented on arithmetic and binary secret shares ; see Section 5.1. Whereas many computations can be performed directly on arithmetic secret shares, others require conversion between arithmetic and binary secret shares (A2B) and back (B2A); see Section 5.2. Some multi-party computations require interaction between parties via a communicator that employs the high-performance communication primitives in Gloo and NCCL . Some multi-party computations require Beaver triples , which are supplied by a trusted third party (TTP).CrypTen adopts a trusted third party for generating Beaver triples for efficiency reasons, but we are planning to add TTP-free solutions based on additive homomorphic encryption or oblivious transfer .

All secure computations are wrapped in a CrypTensor object that implements the PyTorch tensor API and that provides reverse-mode automatic differentiation (autograd) to enable gradient-based training of arbitrary (deep) learning models. Figure 2 illustrates CrypTensor creation, i.e., how tensors are secret-shared and revealed, as well as a simple computation (addition). Note that each party involved in the multi-party computation executes the same code. Whenever communication between the parties is required (e.g., as part of private multiplications), the communication acts as a synchronization point between the parties. The crypten.init() call is required once to establish the communication channel. In the example, the input tensor for the creation of the arithmetic secret share is provided party src=0, which indicates the rankCrypTen relies on MPI primitives for communication: each party knows their rank and the world size. of the party that supplies the data to be secret-shared (the other parties executing this code may provide None as input).

To enable deep-learning use cases, CrypTen allows implementing neural networks following PyTorch’s API. Figure 4 shows how to create and encrypt neural networks and how to use automatic differentiation in CrypTen. The example assumes that some training sample and the associated target label are provided by the party with rank 0 (note the value of src). As illustrated by the example, CrypTen’s API closely follows that of PyTorch. Indeed, it is possible to write a single training loop that can be used to train models using CrypTen or PyTorch without code changes. This makes it easy to adapt PyTorch code to use secure MPC for its computations, and it also makes debugging easier. The appendix presents a table listing all tensor functions that CrypTensor implements.

To enable interoperability with existing machine-learning platforms, neural networks can be imported into CrypTen via ONNX. Figure 4 shows how a PyTorch model is imported into CrypTen. The example illustrates how CrypTen makes private inference with a ResNet-18 easy. The example in the figure also demonstrates CrypTen’s GPU support. One caveat is that all parties must use the same type of device (i.e., CPU or GPU) for computations.

Secure Computations

To facilitate secure computations, CrypTen implements arithmetic secret sharing and binary secret sharing , as well as conversions between these two types of sharing . Arithmetic secret sharing is particularly well-suited for operations that are common in modern machine-learning models, such as matrix multiplications and convolutions. Binary secret sharing is required for evaluating certain other common functions, such as rectified linear units. We provide a high-level overview of CrypTen’s secure computation protocol here; a detailed description is presented in the appendix.

Conversion from $\boldsymbol{[x]}$ to $\boldsymbol{\langle x\rangle}$ is implemented by having the parties create a binary secret share of their $[x]_{p}$ shares, and summing the resulting binary shares. Specifically, the parties create a binary secret share, $\langle[x]_{p}\rangle$, of all the bits in $[x]_{p}$. Subsequently, the parties compute $\langle x\rangle=\sum_{p\in\mathcal{P}}\langle[x]_{p}\rangle$ using a carry-lookahead adder in $\log_{2}(|\mathcal{P}|)\log_{2}(Q)$ communication rounds .

Conversion from $\boldsymbol{\langle x\rangle}$ to $\boldsymbol{[x]}$ is achieved by computing $[x]=\sum_{b=1}^{B}2^{b}\left[\langle x\rangle^{(b)}\right]$, where $\langle x\rangle^{(b)}$ denotes the $b$-th bit of the binary share $\langle x\rangle$ and $B$ is the total number of bits in the shared secret, $\langle x\rangle$. To create an arithmetic share of a bit, the parties use secret shares, $\left([r^{(b)}],\langle r^{(b)}\rangle\right)$, of random bits $r^{(b)}$. The random bits are provided by the TTP, but we plan to add an implementation that generates them off-line via oblivious transfer . The parties use $\langle r^{(b)}\rangle$ to mask $\langle x\rangle^{(b)}$ and reveal the resulting masked bit $z^{(b)}$. Subsequently, they compute $\left[\langle x\rangle^{(b)}\right]=\left[r^{(b)}\right]+z^{(b)}-2\left[r^{(b)}\right]z^{(b)}$.

2 Secure Computation

Arithmetic and binary secret shares have homomorphic properties that can be used to implement secure computations. All computations in CrypTen are based on private addition and multiplication.

Private addition of two arithmetically secret shared values, $[z]=[x]+[y]$, is implemented by having each party $p$ sum their shares of $[x]$ and $[y]$: each party $p\in\mathcal{P}$ computes $[z]_{p}=[x]_{p}+[y]_{p}$.

Private multiplication is implemented using random Beaver triples , $([a],[b],[c])$ with $c\!=\!ab$, that are provided by the TTP. The parties compute $[\epsilon]=[x]-[a]$ and $[\delta]=[y]-[b]$, and decrypt $\epsilon$ and $\delta$ without information leakage due to the masking. They compute the result $[x][y]=[c]+\epsilon[b]+[a]\delta+\epsilon\delta$, using trivial implementations of addition and multiplication of secret shares with public values.

Linear functions are trivially implemented as combinations of private addition and multiplication. This allows CrypTen to compute dot products, outer products, matrix products, and convolutions.

Non-linear functions are implemented using standard approximations that only require private addition and multiplication. Specifically, CrypTen evaluates exponentials using a limit approximation, logarithms using Householder iterations , and reciprocals using Newton-Rhapson iterations. This allows CrypTen to implement functions that are commonly used in machine-learning models, including the sigmoid, softmax, and logistic-loss functions, as well as their gradients.

Comparators are implemented using a function that evaluates $[z<0]$ by: (1) converting $[z]$ to a binary secret-share $\langle z\rangle$; (2) computing its sign bit, $\langle b\rangle=\langle z\rangle>\!>(L-1)$; and (3) converting the resulting bit to an arithmetic sharing $[b]$. This function allows CrypTen to implement arbitrary comparators. For example, it evaluates $[x<y]$ by computing $[z]=[x]-[y]$ and evaluating $[z<0]$. Similarly, CrypTen can evaluate: (1) the sign function via $\operatorname{sign}([x])=2[x>0]-1$; (2) the absolute value function via $|[x]|=[x]\operatorname{sign}([x])$; and (3) rectified linear units via $\operatorname{ReLU}([x])=[x][x>0]$. CrypTen also supports multiplexing; to do so, it evaluates $[c~{}?~{}x:y]=[c][x]+(1-[c])[y]$.

The CrypTen secure-computation protocol is secure against information leakage against any static passive adversary corrupting up to $|\mathcal{P}|-1$ of the $|\mathcal{P}|$ parties involved in the computation.

The proof of this lemma follows trivially from , and is given in the appendix. We adopt a protocol that provides security under a semi-honest threat model because it enables a wide range of use cases of secure machine learning, whilst being more efficient than maliciously secure protocols.

3 Off-loading Computations to the GPU

Hardware acceleration via GPUs is a critical component for training and inference in modern machine-learning models. Akin to frameworks such as PyTorch and TensorFlow , CrypTen can off-load computations to the GPU. On the GPU, it uses highly-optimized implementations for a range of functions that are provided by CUDA libraries such as cuBLAS and cuDNN .

Benchmarks

To measure the performance of CrypTen, we performed experiments on three tasks: (1) text classification using a linear model that learns word embeddings; (2) speech recognition using the Wav2Letter model ; and (3) image classification using residual networks and vision transformers . Because of space constraints, we focus on private inference using a secret-shared model on secret-shared data here, but our benchmark results with private training are very similar.

We performed benchmark experiments on a proprietary cluster, testing inference on both CPUs (Intel Skylake 18-core 1.6GHz) and GPUs (nVidia P100). We set the number of OpenMP threads to 1 in all benchmarks. All experiments were performed with the parties running in separate processes on a single machine. For GPU experiments, each party was assigned its own GPU. Although this setup is faster than a scenario in which each party operates its own machine,Communication between GPUs in two machines connected via InfiniBand has approximately $20\times$ lower throughput than communication between two GPUs in the same machine via NVLink (25GB/s versus 600GB/s). we believe our benchmark results provide a good sense of CrypTen’s performance. We average computation times over 30 batches, excluding the computation on the first batch as that computation may include CuDNN benchmarking. Code reproducing the results of our experiments is available on https://crypten.ai.

In our benchmarks, we focus on comparing (ciphertext) CrypTen computation with (plaintext) PyTorch computation. We refer the reader to for benchmarks that compare CrypTen to other secure MPC frameworks. Specifically, finds CrypTen is $11$-$18\times$ faster than PySyft and approximately $3\times$ faster than TF-Trusted in MNIST classification on CPU.

We performed text-sentiment classification experiments on the Yelp review dataset using a model that consists of a linear layer operating on word embeddings. The embedding layer contains $32$-dimensional embeddings of $519,820$ words, and the linear layer produces a binary output indicating the sentiment of the review. We evaluated the model on GPUs, varying the batch size and the number of parties participating. The normalized mean squared error ($\nicefrac{{\lVert\mathbf{x}-\mathbf{y}\rVert^{2}}}{{\lVert\mathbf{x}\rVert^{2}}}$) between the output of the CrypTen model and that of its PyTorch counterpart was smaller than $4\cdot 10^{-4}$ in all experiments.

Figure 5 presents the results of our experiments. The figure shows inference time per sample (in seconds) as a function of the number of parties involved in the computation for varying batch sizes (left); the amount of communication required per sample, per party (in GB); and the number of communication rounds required per sample. We include results in which the number of parties is $1$: herein, we run the CrypTen protocol but involve no other parties, which implies that the single party is running the protocol on unencrypted data. One-party results allow us to bisect different sources of computational overhead: specifically, they separate overhead due to communication from overhead due to fixed-point encoding, function approximations, and (lack of) sparse-matrix operations.

The results in Figure 5 show that CrypTen is about $2.5$–$3$ orders of magnitude slower than PyTorch in text-sentiment classification, depending on the number of parties involved. Most computational overhead is the word embedding layer: whereas PyTorch can evaluate this layer efficiently via a sparse matrix multiplication, CrypTen cannot do sparse lookups as they would reveal information on the encrypted input. Instead, CrypTen performs a full matrix multiplication between the word-count vector and the embedding matrix. Yet, text sentiment predictions are quite fast in CrypTen: inference takes only $0.03$ seconds per sample in the two-party setting with a batch size of $32$.

The results also show that increasing the batch size is an effective way to reduce inference time and communication per sample. The number of communication rounds is independent of the batch size, which means communication rounds can be amortized by using larger batch sizes. The number of bytes communicated is partly amortized as well because the size of weight tensors (e.g., in linear layers) does not depend on batch size. The results also show that whereas the number of communication rounds increases when moving from two-party to three-party computation, it remains constant afterwards. The larger number of communication rounds for three-party computation stems from the public division protocol, which requires additional communication rounds when more than two parties are involved to prevent wrap-around errors (see the appendix for details).

2 Speech Recognition

We performed speech-recognition experiments using Wav2Letter on the LibriSpeech dataset . The LibriSpeech dataset contains $16$ kHz audio clips represented as a waveform ($16,000$ samples per second). Because the audio clips vary in length, we clip all of them to $1$ second for the benchmark. Wav2Letter is a network with 13 convolutional layers using rectified linear unit (ReLU; ) activations.We used the reference implementation of Wav2Letter in torchaudio. The network operates directly on the waveform input, predicting one of 29 labels (26 letters plus 3 special characters). The first two layers use a filter size of $250$ (with stride $160$) and $48$ (stride $2$). The next seven layers use filter size $7$, followed by two layers with filter size $32$ and $1$ (all with stride $1$). All layers except the last two have $250$ channels. The last two layers have $2,000$ channels.

The results in Figure 6 show that CrypTen is about $2.5$–$3$ orders of magnitude slower than PyTorch depending on the number of parties involved. For Wav2Letter, the overhead is largely due to the ReLU layers in the network: evaluating a ReLU function requires a comparison, which involves a conversion between arithmetic and binary secret sharing and back (see the appendix). The number of communication rounds increases when the number of parties grows beyond $4$: CrypTen uses a tree reduction for the summation in the comparator protocol, which implies that the number of communication rounds grows whenever the number of parties increases from $2^{k}$ to $2^{k+1}$.

Figure 8 also presents results comparing Wav2Letter inference time between CPUs and GPUs. The results in the figure show that CrypTen is $1$-$2$ orders of magnitude faster on GPUs than on CPUs. In real-world settings, this speedup can make the difference between a secure MPC use case being practical or not. Figure 8 shows how much wall-clock time is spent on communication and computation, respectively, when performing inference with Wav2Letter (using batch size 32). The results suggest that, whereas multi-party evaluation is compute-bound on CPU, it is communication-bound on GPU. On GPUs, $63$% of the time is spent on communication in eight-party computation.

3 Image Classification

We performed image-classification experiments on the ImageNet dataset using residual networks (ResNets; ) and vision transformers (ViT; ).We adopted the ResNet implementation from torchvision and the ViT implementation from https://github.com/rwightman/pytorch-image-models. ViT’s normalized mean squared error is larger than for other models because our Gaussian error function approximation converges slowly; see Section C.2.6. We experimented with a ResNet-18 with 18 convolutional layers and with a ViT-B/16 model that has 12 multi-head self-attention layers with 12 heads each, operating on image patches of $16\times 16$ pixels. Following common practice , we preprocess images by rescaling them to size $256\times 256$ and taking a center crop of size $224\times 224$.

Figure 9 presents the results of our image-classification benchmarks, which show that two parties can securely evaluate a ResNet-18 model in $2.49$ seconds and a ViT-B/16 model in $8.47$ seconds. A notable difference compared to the prior results is that the number of bytes communicated per sample is no longer reduced by increasing the batch size. The reason for this is that the vast majority of communication involves tensors that have the same size as intermediate activation functions: activation tensors are much larger than weight tensors in image-classification models. The amount of communication required to evaluate the ViT-B/16 model is particularly high due to the repeated evaluation of the softmax function in the attention layer of Transformers . We also observe that in ResNet-18, the number of communication rounds grows faster than expected for larger batch sizes. The reason for this is that the carry-lookahead adder used in the conversion from $[x]$ to $\langle x\rangle$ is very memory-intensive. When CrypTen runs out of GPU memory, it replaces the adder by an implementation that requires $O(|\mathcal{P}|)$ communication rounds (compared to $(\log_{2}|\mathcal{P}|)$ for the carry-lookahead adder) but that requires less memory.

Conclusion and Future Work

In this paper, we have introduced and benchmarked CrypTen. We hope that CrypTen’s flexible, machine-learning first API design and performance can help foster adoption of secure MPC in machine learning. We see the following directions for future research and development of CrypTen.

Numerical issues are substantially more common in CrypTen implementations of machine-learning algorithms than in their PyTorch counterparts. In particular, the fixed-point representation with $L$ bits of precision ($L\!=\!16$ by default) is more prone to numerical overflow or underflow than floating-point representations. Moreover, arithmetic secret shares are prone to wrap-around errors in which the sum of the shares $[x]_{p}$ exceeds the size of the ring, $Q\!=\!2^{64}$. Wrap-around errors can be difficult to debug because they may only arise in the multi-party setting, in which no individual party can detect them. We plan to implement tools in CrypTen that assist users in debugging such numerical issues.

End-to-end privacy requires seamless integration between data-processing frameworks, such as secure SQL implementations , and data-modeling frameworks like CrypTen. In “plaintext” software, such frameworks are developed independently and combined via “glue code” or platforms that facilitate the construction of processing and modeling pipelines. Real-world use cases of machine learning via secure MPC require the development of a platform that makes the integration of private data processing and modeling seamless, both from an implementation and a security point-of-view.

Differential privacy mechanisms may be required in real-world applications of CrypTen in order to provide rigorous guarantees on the information leakage that inevitably occurs when the results of a private computation are publicly revealed . CrypTen implements sampling algorithms for the Bernoulli, Laplace, and Gaussian distributions (see appendix), which allows for the implementation of randomized response , the Laplace mechanism , and the Gaussian mechanism (although care must be taken when implementing these mechanisms ). In future work, we aim to use these mechanisms, for example, to do a secure MPC implementation of DP-SGD .

Threat models may vary per use case. Specifically, some use cases may require malicious security or may not provide a TTP. Possible extensions may include support for malicious security via message authentication codes , as well as support for Beaver triple generation via additive homomorphic encryption , oblivious transfer , or more recent methods to eliminate the need for a TTP.

Model architecture design for secure MPC is another important direction for future research. Following prior work in this research area, this study has focused on implementing existing machine-learning models in a secure MPC framework. However, these models were designed based on computational considerations in “plaintext” implementations of the models on modern GPU or TPU hardware. The results of our benchmarks suggest that this may be suboptimal because those considerations are very different in a secure MPC environment. For example, the evaluation of softmax functions over large numbers of values requires a lot of communication in secure MPC, which makes attention layers very slow. This implies that multilayer perceptron models are likely much more efficient than vision transformers for image classification. We hope that CrypTen’s machine-learning API and ease of use will spur studies that design model architectures specifically optimized for a secure MPC environment, for example, via neural architecture search .

Broader Impact

Although we believe that the adoption of secure MPC in machine learning can lead to the development of AI systems that are substantially more private and secure, we note that there are also potential downsides to such adoption. In particular, because the computations in secure MPC are performed on encrypted data, it can be harder to do quality control of AI systems implemented in CrypTen. For example, it is impossible to inspect the values of intermediate activations (or even model outputs) unless all parties agree to reveal those values. This may make it harder to explain why a model makes a certain decision or to detect data-poisoning attacks . Indeed, there exist fundamental trade-offs between privacy and utility and those trade-offs apply to CrypTen users, too.

It is also worth noting that, although the protocols implemented in CrypTen come with rigorous cryptographic guarantees, practical implementations of these protocols may be broken by other means. For example, we have no reason to assume that CrypTen would not be susceptible to side-channel attacks . Hence, good data stewardship remains essential even when using secure computation.

Acknowledgments. We thank Joe Spisak, Sijun Tan, Gregory Chanan, Igor Fedan, and the PyTorch team for their support. We thank Mark Tygert, Anderson Nascimento, Amrita Roy Chowdhury, and anonymous reviewers for helpful discussions and feedback on early versions of this paper.

References

Appendix A Overview of Functions Implemented in CrypTen

Table 2 gives an overview of all functions currently implemented in CrypTen, together with a short description of the approach used to implement the function. Random samplers are not listed in the table. For full details on the CrypTen secure-computation protocol, we refer to Appendix C.

Appendix B Security of CrypTen Functions

CrypTen provides MPC implementations of a large number of functions. However, these functions are all composed from a small set of primitives, which are listed in Table 1. CrypTen provides the security guarantee in Lemma 1. The proof for this security guarantee follows trivially from the following observations and results from prior work:

Operations in binary secret sharing are performed using the GMW protocol . AND operations in this protocol are proven to be secure in .

Conversion from arithmetic to binary (A2B) secret shares is performed using the protocol that is proven to be secure in .

Tensor indexing operations like concatenation, selection, reshaping, etc. are non-interactive, which implies an adversary cannot gain any information.

Security proofs for custom MPC protocols are provided in Appendix C (see Table 1 for details).

All other operations are compositions of secure functions (see Appendix C for details). This implies they are secure because security is closed under composition .

Appendix C Detailed Description of Secure MPC Protocols

CrypTen uses two different types of secret sharing: (1) arithmetic secret sharing and (2) binary secret sharing . Below, we describe the secret sharing methods for single values $x$ but they can trivially be extended to real-valued vectors $\mathbf{x}$.

Addition. The addition of two secret-shared values, $[z]=[x]+[y]$, can be trivially implemented by having each party $p$ sum their shares of $[x]$ and $[y]$: each party $p\in\mathcal{P}$ computes $[z]_{p}\leftarrow[x]_{p}+[y]_{p}$.

Because this result holds for any linear function, $f(\cdot)$, of two variables for which the triple $(a,b,c)$ satisfies $c=f(a,b)$, we use the same procedure to perform matrix multiplication and convolution.

Square. To compute the square $[x^{2}]$, the parties use a Beaver pair $([a],[b])$ such that $b\!=\!a^{2}$. The parties compute $[\epsilon]=[x]-[a]$, decrypt $\epsilon$, and obtain the result via $[x^{2}]=[b]+2\epsilon[a]+\epsilon^{2}$.

Therefore, the simple division method fails when $\theta_{x}\neq 0$, which happens with probability $\nicefrac{{x}}{{Q}}$ in the two-party case. Many MPC implementations specialize to the $|\mathcal{P}|=2$-party case and assume this probability is negligible . However, when $|\mathcal{P}|>2$ the probability of failure grows rapidly and we must account for the number of wraps, $\theta_{x}$.

We do so by privately computing a secret share of the number of wraps in $x$, $[\theta_{x}]$. To this end, we define three auxiliary variables:

$\theta_{x}$ represents the number of wraps produced by the shares of a secret shared variable $[x]$, such that $x=\sum_{p}[x]_{p}-\theta_{x}Q$, where $Q$ is the ring size.

$\beta_{xr}$ represents the differential wraps produced between each party’s shares of two secret shared variables, $[x]$ and $[r]$, such that $[x]_{i}+[r]_{i}\mod Q=[x]_{i}+[r]_{i}-[\beta_{xr}]_{i}Q$.

$\eta_{xr}$ represents the wraps produced by two plaintext variables, $x$ and $r$, such that $x+r\mod Q=x+r-\eta_{xr}Q$.

We use these variable in Algorithm 1 to compute $[\theta_{x}]$. This approach is inspired by Algorithm 4 of , but extends to an arbitrary number of parties. The correctness of this algorithm can be shown through the following reduction:

In practice, it can be difficult to compute $[\eta_{xr}]$ in Algorithm 1. However, we note that $\eta_{xr}$ has a fixed probability of being non-zero, irrespective of the number of parties. Indeed, regardless of the number of parties, we have $P(\eta_{xr}\neq 0)=\nicefrac{{x}}{{Q}}$. In practice, we can therefore skip the computation of $[\eta_{xr}]$ and simply set $\eta_{xr}=0$. This implies that incorrect results can be produced by our algorithm with small probability. For example, when we encode a real value $\hat{x}$ using a fixed-point encoding $x=\lfloor B\hat{x}\rceil$, truncation will produce an error with probability $P(\eta_{xr}\neq 0)=\nicefrac{{\lfloor B\hat{x}\rceil}}{{Q}}$. This probability can be reduced by increasing $Q$ or reducing the precision parameter, $B$.

Security proof. One can show the security of Algorithm 1 by noting that the only information gained by an adversary is the revealed shares of $[z]$, which are indistinguishable from white uniform random noise because shares of $[r]$ are chosen to be uniformly random.

C.1.2 Binary Secret Sharing

Note that XOR and AND operations form a basis for the set of Turing-complete operations (via circuits). However each sequential AND gate requires a round of communication, which makes all but very simple circuits very inefficient to evaluate via binary secret sharing. In CrypTen, we only use binary secret sharing to implement comparators.

Bitwise XOR. Similar to addition in arithmetic secret sharing, a binary XOR of two binary secret-shared values, $\langle z\rangle=\langle x\rangle+\langle y\rangle$ can be trivially implemented by having each party XOR their shares of $\langle x\rangle$ and $\langle y\rangle$. That is, each party $p\in\mathcal{P}$ computes $\langle z\rangle_{p}\leftarrow\langle x\rangle_{p}\oplus\langle y\rangle_{p}$.

Bitwise AND. Since the bitwise AND operation is equivalent multiplication mod 2, we can utilize the same method we use to multiply arithmetic secret shared values. To facilitate bitwise AND of two binary secret-shared values, the parties use random triples generated in an offline preprocessing phase. The generated triple $(\langle a\rangle,\langle b\rangle,\langle c\rangle)$ satisfies the property $c\!=\!a\otimes b$. The parties then compute $\langle\epsilon\rangle=\langle x\rangle\oplus\langle a\rangle$ and $\langle\delta\rangle=\langle y\rangle\oplus\langle b\rangle$ and decrypt $\epsilon$ and $\delta$. This does not leak information since $a$ and $b$ contain bits drawn uniformly at random. $\langle x\rangle\otimes\langle y\rangle$ can now be evaluated by computing $\langle c\rangle\oplus(\epsilon\otimes\langle b\rangle)\oplus(\langle a\rangle\otimes\delta)\oplus(\epsilon\otimes\delta)$. Correctness follows from the same logic as multiplication in arithmetic secret sharing. We note that revealing $\epsilon$ and $\delta$ requires a round of communication among all parties in this protocol.

Logical shifts. Because each bit of a binary secret-shared value is an independent secret-shared bit, logical shifts can be performed trivially. To shift the bits of a binary secret-shared value $\langle x\rangle$ by a constant $k$, each party can compute the shift locally on its share, $\langle y\rangle_{p}=\langle x\rangle_{p}>\!>k$.

C.1.3 Converting Between Secret-Sharing Types

Many machine-learning models require both functions that are easier to compute on arithmetic secret shares (e.g., matrix multiplication) and functions that are easier to implement via circuits on binary secret shares (e.g., argmax). Therefore, CrypTen uses both types of secret sharing and converts between the two types as needed using the techniques proposed in .

From $[x]$ to $\langle x\rangle$: To convert from an arithmetic share $[x]$ to a binary share $\langle x\rangle$, each party first secretly shares its arithmetic share with the other parties and then performs addition of the resulting shares. The parties construct binary secret shared values $\langle y_{p}\rangle$ where each $y_{p}$ represents one of the arithmetic secret shares $y_{p}=[x]_{p}$. This process is repeated for each party $p\in\mathcal{P}$ to create binary secret shares of all $|\mathcal{P}|$ arithmetic shares $[x]_{p}$. Subsequently, the parties compute $\langle x\rangle=\sum_{p\in\mathcal{P}}\langle y_{p}\rangle$. To compute the sum, a carry-lookahead adder circuit can be evaluated in $\log_{2}(|\mathcal{P}|)\log_{2}(Q)$ rounds . In practice, the carry-lookahead adder circuit is quite memory-intensive. When CrypTen runs out of GPU memory, we adopt an alternative adder circuit that requires substantially less memory but performs $|\mathcal{P}|\log_{2}(L)$ communication rounds to perform the summation.

From $\langle x\rangle$ to $[x]$: To convert from a binary share $\langle x\rangle$ to an arithmetic share $[x]$, the parties compute $[x]=\sum_{b=1}^{B}2^{b}\left[\langle x\rangle^{(b)}\right]$, where $\langle x\rangle^{(b)}$ denotes the $b$-th bit of the binary share $\langle x\rangle$ and $B$ is the total number of bits in the shared secret. To create the arithmetic share of a bit, the parties use $b$ pairs of secret-shared bits $([r],\langle r\rangle)$ generated offline. Herein, $[r]$ and $\langle r\rangle$ represent arithmetic and binary secret-shares of the same bit value $r$. Parties then use Algorithm 2 to generate $\left[\langle x\rangle^{(b)}\right]$ from $\langle x\rangle^{(b)}$. This process can be performed for each bit in parallel, reducing the number of communication rounds required for the conversion process to one.

Security proof. One can show the security of Algorithm 2 by noting that the only information gained by an adversary is the revealed shares of $\langle z\rangle$, which are indistinguishable from white Bernoulli random noise because shares of $\langle r\rangle$ are chosen to be uniformly random.

C.1.4 Logic-based Operations

Many applications require implementations of logic-based operators to make branching decisions and compute piece-wise functions.

Comparisons. To compare two secret-shared values $[x]$ and $[y]$, we can produce $[x<y]$ by computing their difference $[z]=[x]-[y]$ and comparing the result to zero: $[z<0]$. We compute $[z<0]$ by first converting $[z]$ to a binary secret-share $\langle z\rangle$, computing its sign bit using a right shift $\langle b\rangle=\langle z\rangle>\!>(L-1)$, and converting the resulting bit to an arithmetic sharing $[b]$. Because we are using an integer encoding, the most significant bit of $z$ represents its sign. It is possible to compare $[x<y]$ directly using a less-than circuit, but this requires converting an extra value to binary secret sharing and incurring another $\log_{2}L$ rounds of communication to compute the less-than circuit.

We can use the ability to compute $[x<y]$ to compute all other comparators on $[x]$ and $[y]$:

We optimize evaluation of the is-equal operator by computing $[x\leq y]$ and $[x<y]$ in parallel.

Multiplexing. Multiplexing is a very valuable tool for computing conditional and piece-wise functions. To multiplex between two values $[x]$ and $[y]$ based on a condition $c$, we must first evaluate $c$ to a a binary value $[c]\in\{,\}$. We can then compute $[c~{}?~{}x:y]=[c][x]+(1-[c])[y]$. This allows us to evaluate if-statements using CrypTen, where $[x]$ is the result when the if-statement is executed, and $[y]$ is the result otherwise. However, unlike if-statements, both results must be evaluated, meaning we cannot use tree-based or dynamic programming techniques to optimize algorithm runtimes.

Sign, absolute value, and ReLU. Several important functions can be computed using the multiplexing technique. We can compute $\operatorname{sign}([x])=2[x>0]-1$. We can then use this to compute $|[x]|=[x]\operatorname{sign}([x])$. Similarly we can compute the ReLU function by noting $\operatorname{ReLU}([x])=[x][x>0]$.

Argmax and maximum. CrypTen supports two methods for computing maximums $[\max x]$. Both methods first compute a one-hot argmax mask that contains a one at the index containing a maximal element $[y]=\operatorname{argmax}([x])$. A maximum can then be obtained by taking the sum $[\max x]=\sum_{i}[y_{i}][x_{i}]$ where the sum is taken along the dimension over which the maximum is being computed. By default, the argmax is computed using a tree-reduction algorithm, though configurations are available to use pairwise comparisons depending on network bandwidth / latency.

The tree-reduction algorithm computes the argmax by partitioning the input into two halves, then comparing the elements of each half. This reduces the size of the input by half in each round, requiring $O(\log_{2}N)$ rounds to complete the argmax. This method requires order $O(\log_{2}N)$ communication rounds, $O(N^{2})$ communication bits, and $O(N)$ computation complexity.

The pairwise method generates a matrix $[A]$ whose rows are constructed by the pairwise differences of every pair of elements $\forall i\neq j:[A_{ij}]=[x_{i}-x_{j}]$. We then evaluate all comparisons simultaneously by computing $[A\geq 0]$. All maximal elements will correspond to columns whose elements are all greater than 0, so we can compute the argmax mask $[m]$ by taking the sum over all columns of $[A]$. However, if more than one maximal element exists, this will result in a mask $[m]$ that is not one-hot. To make this one-hot we take a cumulative sum $[c]$ of $[m]$ and return $[c<2][m]$ to return the index of the first maximal element. This method requires $O(1)$ communication rounds, $O(N^{2})$ communication bits, and $O(N^{2})$ computation complexity. In theory, because of constant-round communication, this method should be more efficient than the tree-reduction algorithm when the network latency is high.

Argmin and minimum. To compute minimums and argmins, we compute our argmax mask with a negated input: $[\operatorname{argmin}x]=[\operatorname{argmax}(-x)]$.

C.2 Mathematical Approximations

CrypTen also offers configurable parameters for protocol-specific optimizations, for example, custom initializations that improve convergence for iterative methods in a pre-specified input domain.

There are many well-known polynomial approximations for the exponential function, for example, the Taylor series, $e^{x}=\sum_{n=0}^{\infty}\frac{1}{n!}x^{n}$. However, because exponentials grow much faster than polynomials, the degree of the polynomial we would need to approximate the exponential function increases exponentially as the domain increases. Therefore, we instead use the limit approximation, which allows us to do repeated squaring very efficiently:

CrypTen can also use the repeated-squaring method to compute complex exponentials efficiently, which enables the computation of the sine and cosine functions:

C.2.2 Reciprocal

CrypTen uses Newton-Raphson iterations to compute the reciprocal function. This method uses an initial guess, $y_{0}$, for the reciprocal and repeats the following update:

This will converge to $\lim_{n\rightarrow\infty}y_{n}\!=\!\frac{1}{x}$ quadratically as long as the initial guess $y_{0}$ meets the Newton-Raphson convergence criterion, which is $0\!<\!y_{0}\!<\!\frac{2}{x}$ for the above. By default, CrypTen uses:

to initialize the approximation, which provides convergence on a large domain. This function was found by inspection and can be replaced by a user-defined value using CrypTen’s configuration API. Because this method only converges for positive values of $x$, we compute the reciprocal using the identity $\frac{1}{x}=\frac{\operatorname{sgn}x}{|x|}$. (Note that square matrix inverses and Moore-Penrose inverses can be found using similar techniques given input matrices with singular values that meet the convergence criterion.)

C.2.3 Square Root and Normalization

CrypTen uses Newton-Raphson iterations to compute square roots. However, the Newton-Raphson update formula for square roots, $y_{n+1}=\frac{1}{2}(y_{n}+\frac{x}{y_{n}})$ is quite inefficient to compute on secret shares. Instead, we use the much more efficient Newton-Raphson update formula for inverse square root:

We then multiply by the input $x$ to obtain the square root: $\sqrt{x}=(x^{-0.5})x$. We can also use the inverse square root function to efficiently normalize values via: $\frac{x}{\left\lVert x\right\rVert}=x\left(\sum_{i}x_{i}^{2}\right)^{-\nicefrac{{1}}{{2}}}$.

C.2.4 Logarithm and Exponents

To compute logarithms, CrypTen uses higher-order iterative methods to achieve better convergence. The following update formula can be found using high-order modified Householder methods on $\ln(x)$ or by manipulating the Taylor series expansion of $\ln(1-x)$:

Note that at each step $\ln x=y_{n}+\ln(1-h_{n})$, but we can only approximate $\ln(1-h_{n})$ using a truncated Taylor Series approximation. For this method, the order of the Householder method (i.e., the polynomial degree in the second equation) will determine the speed of convergence. Since the convergence rate per iteration increases proportionally to the degree of the polynomial, whereas an exponential must be computed for each iteration, it is more computationally efficient to use high-degree polynomials instead of doing many iterations. By default, CrypTen uses a polynomial of degree $8$, the initialization $y_{0}=\frac{x}{120}-20e^{-2x-1}+3$, and $3$ iterations. This provides effective convergence on the domain $[10^{-4},10^{2}]$.

Using the logarithm and exponential functions, we can also compute arbitrary public or private exponents on positive inputs $x$ using the equation $x^{y}=e^{y\ln(x)}$.

C.2.5 Sigmoid and Hyperbolic Tangent

We have explored several methods for computing logistic functions in MPC, including direct computation, rational approximations, and Chebyshev polynomial approximations . We have found that direct computation is the most efficient when it is combined with some specific optimizations. Specifically, CrypTen uses the exponential and reciprocal functions to compute:

We optimize this computation by noting that the range of the sigmoid function is $$, and the range for the positive half of its domain is$[0.5,1]$. Therefore, when we compute the reciprocal using the method described in Section C.2.2, we compute$\sigma(|x|)$using an initialized value of$0.75$for the Newton-Raphson iterations to improve convergence. We extend the result to the full domain by noting$\sigma(-x)=1-\sigma(x)$. We compute the hyperbolic tangent function via$\tanh(x)=2\sigma(2x)-1$.

C.2.6 Gaussian Error Function

We use a Maclaurin series to approximate the Gaussian error function $\textrm{erf}(x)=\nicefrac{{2}}{{\sqrt{\pi}}}\int_{0}^{x}e^{-x^{2}}dx$. The resulting approximation is given by: $\textrm{erf}(x)\approx\frac{2}{\sqrt{\pi}}\sum_{k=0}^{K}\frac{(-1)^{k}x^{2k+1}}{k!(2k+1)}$, where $K$ is the number of terms in the approximation (we set $K=8$ by default). Although the approximation works reasonably well in practice, we note that it is known to have poor convergence when $x>1$ (see OEIS A007680).

C.3 Random Sampling

Several applications of privacy-preserving computations require secret-shared generation of random numbers such that no party can gain any information about the value of realizations. We use the following methods for generating secret shares of random samples from several popular distributions.

Due to quantization introduced by our encoding with scale $2^{L}$, we can only produce discrete uniform random variables with $2^{L}$ possible values. To do so, we produce samples $[u]\sim Uniform(0,1)$ by generating $L$ bits as Rademacher variates. To generate these bits, each party randomly generates its own binary secret-share with the same distribution locally. The XOR sum of independently distributed Rademacher variates, $u=\oplus_{p\in\mathcal{P}}\langle u\rangle_{p}$, is itself a Rademacher variate and is uncorrelated with any of the input bits.

Security proof. One can show the security of this sampler by noting that no adversary could gain any information about the sampled bit from its own binary share of the bit, because the XOR sum of independently distributed Rademacher variates is uncorrelated with any of the input bits. The bits are then converted to an arithmetic share $[u]$ using Algorithm 2, which is itself secure.

C.3.2 Bernoulli Sampling

To compute a Bernoulli random variable with arbitrary mean $[b]\sim Bern(p)$, we first generate a uniform random variable $[u]\sim Uniform(0,1)$ and compute $[b]=[u>p]$. Note that due to quantization in $[u]$, the true probability parameter of the Bernoulli random sample is quantized to the nearest multiple of $2^{-L}$, as would have happened if $p$ was encoded using the fixed-point encoder.

C.3.3 Gaussian Sampling

Gaussian random samples $[x]\sim\mathcal{N}(\mu,\sigma^{2})$ can be computed using the Box-Muller transform. Given a pair of independent uniformly distributed random variables $([u_{1}],[u_{2}])$, two independent Gaussian random variables $([x_{1}],[x_{2}])$ from $\mathcal{N}(0,1)$ can be generated by computing:

Since the range of the uniform inputs is $$, we optimize our numerical approximations for better performance on this domain. To obtain samples$[y]\sim\mathcal{N}(\mu,\sigma^{2})$, we compute$[y]=\sigma[x]+\mu$.

C.3.4 Exponential and Laplace sampling

Exponential random variables $[x]\sim Exp(\lambda)$ can be computed using the inverse CDF method. Given a uniform random sample $[u]\sim U$, an exponential random variable is generated via:

Again, we optimize the logarithm for the domain .

A Laplace distributed random sample $[y]\sim Lap(\mu,k)$ can be generated from an exponential random sample, $[x]\sim Exp(k^{-1})$, and a Rademacher variate, $[b]$, by evaluating $[y]=(2[b]-1)[x]$.

C.3.5 Weighted Random Sampling

To produce a weighted random sample of inputs $[x_{i}]$ with weights given by $[w_{i}]$, we first generate a uniform random sample in $\left([0,\sum_{i}[w_{i}]\right)$ by drawing a uniform sample, $[u]$, and evaluating $[r]=[u]\left[\sum_{i}w_{i}\right]$. Care should be taken to avoid precision issues caused by generating $[u]$ in fixed-point with finite precision. We then compute the cumulative sum values $[c_{i}]$ of the weights $[w_{i}]$, and compare those values to our random value $[m_{i}]=[c_{i}>r]$. This produces a mask vector whose entries are all zero below some index $j$ and all one above index $j$. To convert this mask vector into a one-hot vector, we append a zero in front of the $[m_{i}]$-values and compute $[o_{i}]=[m_{i}]-[m_{i+1}]$. Finally, we obtain the selected sample from the inputs $[x_{i}]$ by multiplying the samples with the one-hot vector and summing: $[y]=\sum_{i}[x_{i}][o_{i}]$.

Appendix D Comparison with Secure MPC Frameworks for Machine Learning

Table 3 presents a comparison of CrypTen with other secure MPC frameworks for machine learning. For each framework, the table shows whether the framework supports maliciously secure threat models, can generate Beaver triples (if needed) without requiring a trusted third party, supports GPU computations, supports model training, supports general purpose function evaluation, and implements automatic differentiation (autograd). We define a secure MPC framework for machine learning to be general-purpose if it supports at least the following functions: linear functions, convolutions, rectified linear units (ReLU), max-pooling, and batch normalization.CrypTen supports a variety of functions beyond these five functions, but we focus on these five in our comparison as they are the main building blocks of many deep network architectures.