Efficient Differentially Private Secure Aggregation for Federated Learning via Hardness of Learning with Errors

Introduction

Mobile phones and embedded devices are ubiquitous and allow massive quantities of data to be collected from users. The recent explosion in data collection for deep learning has led to significant new capabilities, from image recognition to natural language processing. But collection of private data from phones and devices remains a major and growing concern. Even if user data is not directly disclosed, recent results show that trained models themselves can leak information about user training data .

Private data for training deep learning models is typically collected from individual users at a central location, by a party we call the server. But this approach creates a significant computational burden on data centers, and requires complete trust in the server. Many data owners are rightfully skeptical of this arrangement, and this can impact model accuracy, since privacy-conscious individuals are likely to withhold some or even all of their data.

A significant amount of existing research aims to address these issues. Federated learning is a family of decentralized training algorithms for machine learning that allow individuals to collaboratively train a model without collecting the training data in a central location. This addresses computational burden in data centers by shifting training computation to the edge. However, federated learning does not necessarily protect the privacy of clients, since the updates received by the server may reveal information about the client’s training data .

Combining secure aggregation with differential privacy ensures end-to-end privacy in federated learning systems. In principle, secure aggregation allows user updates to be combined without viewing any single update in isolation. Methods based on differential privacy add noise to updates to ensure that trained models do not expose information about training data. However, secure aggregation protocols are expensive, in terms of both computation and communication. The state-of-the-art protocol for aggregating large vectors (as in federated deep learning) is due to Bonawitz et al. . This protocol has a communications expansion factor of more than 2x when aggregating 500 length-20,000 vectors (i.e. it doubles the communication required for each client), and requires several minutes of computation time for the server.

A novel malicious-secure aggregation protocol that outperforms previous approaches to gradient aggregation with differential privacy.

Analytic and empirical results that support our scalability claims, and that show our protocol achieves nearly the same accuracy as central-model approaches for differentially private deep learning on practical models for MNIST and CIFAR-10.

Overview

We study the problem of distributed differentially private deep learning without a trusted data curator. Our setting includes a set of clients (or data owners), each of whom holds some sensitive data, and a server that aggregates gradients generated by clients to obtain a model for the entire federation. The goal is to obtain a differentially private model, without revealing any private data to either the server or other clients.

Deep learning attempts to train a neural network architecture $\mathcal{F}(\theta,\cdot)$ by training its parameters (or weights) $\theta$ in order to minimize the value of a loss function $\mathcal{L}(\theta,\cdot)$ on the training data. Advances in deep learning have lead to significant gains in machine learning capabilities in recent years. Neural networks are typically trained via gradient descent: each iteration of training calculates the gradient of the loss on a subset of the training data called a batch, and the model parameters are updated based on the negation of the gradient.

Traditional deep learning techniques assume the training data is collected centrally; moreover, recent results suggest that trained models tend to memorize training data, and training examples can later be extracted from the trained model via membership inference attacks . When sensitive data is used to train the model, both factors represent significant privacy risks to data owners.

Federated learning is a family of techniques for training deep neural networks without collecting the training data centrally. In the simplest form of federated learning (also called distributed SGD), each client computes a gradient locally and sends the gradient (instead of the training data) to the server. The server averages the gradients and updates the model. More advanced approaches compute gradients in parallel to reduce communication costs; Kairouz et al. provide a survey.

Differential privacy is a rigorous privacy framework that provides a solution to the problem of privacy attacks on deep learning models. Achieving differential privacy typically involves adding noise to results to ensure privacy. Abadi et al. introduced DP-SGD, an algorithm for training deep neural networks with differential privacy. DP-SGD adds noise to gradients before each model update. Subsequent work has shown that this approach provides strong privacy protection, effectively preventing membership inference attacks .

DP-SGD works in the central model of differential privacy—it requires the training data to be collected centrally (i.e. on a single server). The participant that holds the data and runs the training algorithm is often called the data curator or server, and in the central model, the server must be trusted. Central-model algorithms offer the best accuracy of known approaches, at the expense of requiring a trusted server.

The classical method to eliminate a trusted server is local differential privacy , in which each client adds noise to their own data before sending it to the server. Local differential privacy algorithms for gradient descent have been proposed, but for deep neural networks, this approach introduces too much noise to train useful models . The major strength of local differential privacy is the threat model: privacy is assured for each client, even if every other client and the server act maliciously. The local model of differential privacy has also been relaxed to the shuffle model , which lies between the local and central models but which has seem limited use in distributed machine learning.

The difference in accuracy between the central and local models raises the question: can cryptography help us obtain the benefits of both, simultaneously? Several secure aggregation protocols have been proposed in the context of federated learning to answer this question in the affirmative. These approaches yield the accuracy of the central model, but without a trusted server.

Secure aggregation protocols allow a group of clients—some of whom may be controlled by a malicious adversary—to compute the sum of the clients’ privately-held vectors (e.g. gradients, in federated learning), without revealing individual vectors. The state-of-the-art protocol is due to Bonawitz et al. . For $k$ clients and length-$m$ vectors, this protocol requires $O(k^{2}+mk)$ computation and $O(k+m)$ communication per client, and $O(mk^{2})$ computation and $O(m^{2}+mk)$ communication for the untrusted server. Bell et al. improve these to $O(\log^{2}k+m\log n)$ computation and $O(\log k+m)$ communication (client) and $O(k\log^{2}k+km\log k)$ computation and $O(k\log k+km)$ communication (server). These complexity classifications are summarized in Table 1.

2 Efficient Secure Aggregation in the Differential Privacy Setting

We present a new protocol for secure aggregation (detailed in Section 4) specifically for the setting of differentially private computations. Our protocol reduces client communications complexity to $O(m+k)$ and server communications complexity to $O(mk)$, where as above we have $k$ parties aggregating vectors of length $m$, and demonstrates excellent concrete performance in our empirical evaluation (Section 5). These analytic results are summarized in Table 1 for easy comparison with previous work.

Like previous work, we target both the semi-honest setting (in which all clients and the server correctly execute the protocol) and the malicious setting (in which the server and some fraction of the clients may act maliciously). These threat models are standard in the MPC literature , and match the ones targeted by Bonawitz et al. and Bell et al. . In the semi-honest version, we assume that the server is honest-but-curious, and that the clients have a corrupted honest-but-curious subset with an honest majority. In the malicious version, we assume that the server is malicious, and that the clients have a corrupted malicious subset with an honest majority. We present both versions in Section 4 (note that the results in Table 1 are for semi-honest protocol versions in all cases).

3 Paper Roadmap

The rest of the paper is organized as follows. In Section 3 we describe the ideal but insecure functionality of our main protocol that assumes a trusted server, along with our threat model. The trusted server assumption is removed in Section 4 where we present novel techniques for lightweight malicious-secure aggregation based on LWE. In that Section we also describe the threat model and state formal security results for the protocol, and analyze its algorithmic complexity. In Section 5 we discuss methods and results for two experiments-one that further evaluates scalability and other performance parameters, and another that evaluates the accuracy of the models using our protocol. We conclude with a summary and remarks on open related problems in Section 7.

Differentially Private Federated Learning

Abadi et al. describe a differentially private algorithm for stochastic gradient descent in the central model of differential privacy. The algorithm assumes that the training data is collected centrally by a trusted curator, and training takes place on a server controlled by the curator. For details of the algorithm the reader is referred to

The primary challenge in differentially private deep learning is in bounding the sensitivity of the gradient computation. Abadi et al. use the approach of computing per-example gradients—one for each example in the minibatch—then clipping each gradient to have $L_{2}$ norm bounded by the clipping parameter $C$ (line 6). The summation of the clipped gradients (line 7) has global $L_{2}$ sensitivity bounded by $C$.

Our privacy analysis of this algorithm uses Rényi differential privacy (RDP) (rather than the moments accountant) for convenience and leverages parallel composition over the minibatches in each epoch (rather than privacy amplification by subsampling). Otherwise, it is similar to that of Abadi et al. By the definition of the Gaussian mechanism for Rényi differential privacy , the Gaussian noise added in line 7 is sufficient to satisfy \Big{(}\alpha,\frac{C^{2}\alpha}{2\sigma^{2}}\Big{)}-RDP. By RDP’s sequential composition theorem, training for $E$ epochs satisfies \Big{(}\alpha,\frac{EC^{2}\alpha}{2\sigma^{2}}\Big{)}-RDP. Slightly tighter privacy analyses have been developed that also apply to our work. We present the RDP analysis for simplicity, since our focus is not on improving central-model accuracy.

We now extend the central-model approach to the distributed setting. The following describes a macro-level protocol for realizing differentially private distributed SGD when a trusted third party is present. Functionality 2 (NoisyBatchGradient) assumes the existence of a trusted third party to aggregate the noisy gradients associated with a single batch. Section 4 will describe our MPC protocol that implements Functionality 2 without a trusted third party.

Together, Protocol 1 and Functionality 2 define a differentially private distributed SGD algorithm suitable for the trusted server setting.The distributed computation follows the framework of McMahon et al. , in which each client computes a gradient locally (Functionality 2, line 2). To satisfy differential privacy, our adaptation clips each gradient and adds noise (lines 3-4).

Under the assumption that a trusted third party is available to compute Functionality 2, Protocol 1 satisfies differential privacy. Each execution of Functionality 2 calculates a sum of noisy gradients, each with Gaussian noise of scale $\frac{\sigma}{b}$. The final sum is:

which is exactly the same as the central model algorithm . The last step of the derivation follows by the sum of Gaussian random variables. Note that the noise added by each client is not sufficient for a meaningful privacy guarantee (it is only $\frac{1}{b}$ of the noise required). The privacy guarantee relies on the noise samples being correctly summed along with the gradients. This is a major difference between Functionality 2 and approaches based on local differential privacy , in which each client adds sufficient noise for privacy.

The privacy analysis for Functionality 2 and Protocol 1 are standard, based on the conclusion of Equation (1). The $L_{2}$ sensitivity of \Big{(}\sum_{i=1}^{b}\bar{g}_{i}\Big{)} is $C$, since at most one element of the summation may change, and it may change by at most $C$. By the definition of the Gaussian mechanism for Rényi differential privacy, the noisy gradient sum satisfies \Big{(}\alpha,\frac{C^{2}\alpha}{2\sigma^{2}}\Big{)}-RDP. The batches are disjoint, so over $E$ epochs of training, each individual in the dataset incurs a total privacy loss of \Big{(}\alpha,\frac{EC^{2}\alpha}{2\sigma^{2}}\Big{)}-RDP.

Protocol 1 satisfies differential privacy when a trusted third party is available to execute Functionality 2. The server may be untrusted, since the server only receives differentially private gradients.

Functionality 2 is secure against semi-honest clients (in part 1), since each client only sees their own data and the (differentially private) model $\theta$. However, actively malicious clients may break privacy for other clients. Each client is required to add noise to their own gradient (line 4); malicious clients may add no noise at all.

If 50% of the clients add no noise, then the variance of the noise in the aggregated gradient $\hat{G}$ (line 6) will be $\frac{\sigma^{2}}{2}$ instead of $\sigma^{2}$, yielding \Big{(}\alpha,\frac{EC^{2}\alpha}{\sigma^{2}}\Big{)}-RDP (a weaker guarantee than given above). As the fraction of malicious clients grows, the privacy guarantee gets weaker. As discussed earlier, we assume an honest majority of clients and relax our privacy guarantee to this weaker form.

The larger problem is with the requirement for a trusted third party to compute Part 2 of Functionality 2. Even an honest-but-curious server breaks the privacy guarantee for this part: the server receives each individual gradient separately, and each one has only a small amount of noise added. This small amount of noise is insufficient for a meaningful privacy guarantee. Section 4 describes an MPC protocol that securely implements Functionality 2 in the presence of an actively malicious server and an honest majority of clients.

The protocols we describe in Section 4 work for finite field elements, so the floating-point numbers making up noisy gradients will need to be converted to field elements. Our privacy analysis of Protocol 1 relies on a property of the sum of Gaussian random variables; as Kairouz et al. describe, this property does not hold for discrete Gaussians. We amend the privacy analysis to address this issue in Section 4.8.

LWE-Based Secure Aggregation

In this Section we address the security problem described in the last Section, i.e., that state-of-the-art federated learning with differential privacy requires a trusted third-party server for aggregating gradients. Instead, we propose to use secure aggregation between the clients of the protocol, eliminating the need for a trusted third-party server. This allows us to keep both client inputs and gradients confidential for the calculation of a differentially private aggregate gradient. Our solution is an secure aggregation protocol that securely realizes Functionality 2 as part of Protocol 1.

Our approach is to build a LWE-based masking protocol that substantially reduces the communication complexity required to add large vectors. Rather than applying traditional secure multiparty computation (MPC) protocols to the entire vector, we generate masks that obscure the secret vectors based on the learning with errors problem. The masked vectors are safe to publish to the central server for aggregation in the clear. The sum of all vector masks can be obtained through MPC among the clients in the federation. Since the individual vector masks cannot be perfectly reconstructed from the sum of all of the masks, the security of the learning with errors problem safeguards the encryption of the masked vectors.

Due to the nature of the learning with errors problem, the individual vector masks cannot be perfectly reconstructed with the sum of all the masks. The "errors" remain in the aggregated vector sum, and are sufficient to satisfy $(\epsilon,\delta)$-differential privacy.

2 Background: Multiparty Computation

Secure Multiparty Computation, abbreviated MPC, refers to distributed protocols where independent data owners use cryptography to compute a shared function output without revealing their private inputs to each other or a third party . In our setting, the ideal functionality computed by these clients is gradient aggregation, which as discussed in Section 3 is differentially private with regard to user inputs. Thus MPC serves to replace a trusted third party in secure function evaluation.

A $(t,k)$ threshold secret sharing scheme will break a secret value into $k$ shares, and require at least $t$ shares to recover the secret. Our secure vector aggregation protocol additionally requires that the scheme have an additive homomorphic property. That is to say if [a] and [b] are secret shares of values $a$ and $b$, and $c$ is a constant. Using [a], [b], and $c$, a party must be able to calculate [a + b], [ac], and [a + c] without communication among the other clients.

3 LWE-Based Masking of Input Vectors

We now describe our novel masking protocol, which allows us to reduce client communication. A high-level summary of the protocol is the following:

Each client generates a one-time-pad that is the same size as their gradient, masks their gradient, and sends the encrypted gradient to the server.

Clients add their masks together using MPC and send the aggregate mask to the server.

Through this protocol the server can recover the true sum of the gradients by adding the masked gradients and subtracting the aggregate mask. Moreover, the aggregate mask reveals nothing about any individual gradients or their masks.

where here $h$ is used to denote the encrypted $v$. Note that according to Regev , there is no loss in security in having all clients share the same matrix $A$ to perform this part of the protocol.

Now suppose that $h_{i}$, $v_{i}$, $b_{i}$, $s_{i}$, and $e_{i}$ are the $h$, $v$, $b$, $s$, and $e$ vectors of client $i$. Additionally, suppose $h_{sum}$, $v_{sum}$, $b_{sum}$, $s_{sum}$ and $e_{sum}$ are the sum of all $b_{i}$, $s_{i}$, and $e_{i}$ for clients $0,\ldots,k-1$ where $k$ is the number of clients.

By the definition of one-time pads, each client can send $h_{i}$ to the server without revealing anything about $v_{i}$. The server can obtain $h_{sum}$ through simple vector addition. By the definition of each $h_{i}$, we further know that:

and by the definition of each $b_{i}$ and the distributive property, we obtain:

where $As_{sum}$ denotes the usual matrix-vector multiplication. To obtain $s_{sum}$ we assume the federation has access to a secure aggregation protocol that realizes functionality $\texttt{Sagg}(x_{0},\dots x_{k},t)$. Sagg returns the sum of vectors $x_{0},\dots,x_{k}$, while not revealing any information about any inputs to any subset of parties of size smaller than $t$. Because they utilize Sagg, this reveals nothing about their individual $s_{i}$ values. In the case of dropouts, Sagg also returns the subset of parties that participated in the aggregation. Using $s_{sum}$, the server can compute the following value:

Of course, the clients do not share their individual error vector $e_{i}$ values because this would invalidate the LWE assumption that ensures $b_{i}$ is a one-time pad. Therefore, we realize the ideal functionality of calculating $v_{sum}$ by returning a noisy answer. Fortunately, each entry in $e_{sum}$ is the sum of at most $k$ discretized Gaussians. Therefore we can use the noise added by $e_{sum}$ to satisfy $(\epsilon,\delta)$-DP.

Protocol 3 reduces the client communication complexity from $O(\log(q)mk)$ to $O(\log(q)(m+n+k))$ by requiring clients to securely aggregate only a small vector of size $n$. The addition of $n$ and $k$ can be attributed to the possible use of packed secret sharing. Each client shares their length-$m$ vector once with the server, and then uses a packed secret sharing scheme on their length-$n$ vector. The total number of shares required in the packed scheme is $O(n+k)$

4 Vector Aggregation

To add the secret vectors $s_{0}\dots s_{k-1}$, we can use any secure aggregation protocol. In our use cases, each $s_{i}$ is typically of small dimension $(m\leq 800)$, so we use a packed Shamir secret sharing protocol outlined in Protocol 4.

Protocol 4 is secure against semi-honest adversaries based on the security packed secret sharing. A malicious adversary could broadcast an incorrect sum in Round 2 of the protocol, and the final result would be calculated incorrectly by the other clients. Traditionally, the reconstruct function has no ability to catch this kind of cheating; in many cases all of the shares are needed to reach the threshold during reconstruction, so corruption of a single one will change the result.

5 Malicious-Secure Vector Aggregation

We now extend Protocol 4 to be secure against malicious clients by applying a variation of Benaloh’s verifiable secret scheme . The key insight behind this modification comes from the observation that in our protocol each client receives $k$ shares from the other clients in Round 3, but only $t$ shares are actually required for reconstruction. Our modified reconstruction procedure uses the remaining shares to catch cheating clients.

We propose the following reconstruction method for verifying that clients have behaved honestly. Requiring that each client has at least $t+1$ shares, we have each honest client take two subsets of the shares, one of size $t$ and one of size $t+1$. The clients perform the traditional reconstruction technique on both subsets. If the values returned by both reconstructions are equivalent, they accept the result as correct. Otherwise, they abort. The modified reconstruction procedure appears in Algorithm 5. Replacing the call to reconstruct in Protocol 4 with a call to this modified reconstruction procedure yields a malicious-secure protocol.

Note that Algorithm 5 does not require communication with other clients. General-purpose malicious-secure protocols based on the same principle require interaction between the clients to check for cheating (e.g., the protocol of Chida et al. ) because they use the “extra” shares to perform multiplication. Since our application does not require multiplication, we can use these shares to catch cheating instead.

Algorithm 5 can be extended to the packed Shamir variant by requiring that each client has access to $t+k+1$ shares. The number of shares to which access is required must be increased because the reconstruction threshold is increased in the packed variant. Protocol 4 and Algorithm 5 realize the ideal functionality Sagg in the malicious adversary threat model.

6 Security Analysis

Here we analyze the security of Protocol 3, which we will denote as $\pi$.

Suppose the ideal functionality of noisy vector addition as $F$, an adversary $A$. Let $v_{i}$ and $x_{i}$ be input and view of client $i$ respectively. Let $x_{s}$ be the view of the server. $n$ is the LWE security parameter. Suppose a maliciously secure aggregation protocol $\texttt{Sagg}(X,t)$. Let $V$ be the output of $\pi$.

Let $U$ be the set of clients, and $C\subset U\cup\{S\}$ be the set of corrupt parties.

In the malicious model, we consider dropping out an adversarial behavior without loss of generality.

Suppose the simulator has access to an oracle $\texttt{IDEAL}(t,v_{u})_{u\in U\setminus C}$ where:

Let $\texttt{REAL}_{\pi,C}^{U}=\{x_{i}|i\in C\},V$.

There exists a PPT simulator SIM such that for all $t$, $U$, $C$

The proof full proof of this theorem can be found in Appendix A.

The security of an LWE instance is parameterized by the tuple $(n,q,\beta)$ where $n$ is the width of the matrix $A$ (or equivalently the dimension of the secret $s$), $q$ is the field size, and $\beta$ is such that $\beta q$ is the width of the error distribution $\chi$ (so that the standard deviation is $\sigma=\frac{\beta q}{\sqrt{2\pi}}$; this quantity is denoted $\alpha$ in the LWE literature, but we choose $\beta$ here so as to not conflict with the notation for Rényi divergence). We used the LWE estimator to calculate the security of each parameter tuple. Table 2 displays a series of LWE parameters for different potential aggregation scenarios, each with at least 128 bits of security.

The different parameter settings are driven by different sizes of $q$, which would enable more precision in the aggregate values. A larger field size also allows more clients to be involved in the aggregation. Field sizes picked here may also utilize fast Fourier transform secret sharing. For this reason we consider $q$ fixed by the application of the protocol. Since we also use a fixed valued of $\beta=\frac{3.2}{q}$, the security offered by the LWE problem depends on the variable $n$ (the length of the secret $s$), which we call the security parameter.

7 Encoding and Decoding Gradients

In order to manipulate gradients with MPC, we require that they can be encoded as a vector of finite field elements. First we flatten the tensors that compose each gradient into a vector of floating point numbers. The aggregation operation of gradients is element wise. Therefore, we simplify the encoding problem to encoding a floating point number as a finite field element. Gradient elements are clipped, and encoded as fixed point numbers. We chose 16 bit numbers with 4 digits of precision after the decimal. This precision was sufficient for model conversion on the MNIST and CFAR-10 problems.

The integers are converted to unsigned integers using an offset, and the unsigned integer result can be encoded into any field larger than $2^{16}$. The fields used in our experiment are outlined in Table 2.

The privacy analysis of Protocol 1 relies on the fact that the sum of Gaussian random variables is itself a Gaussian random variable. However, as Kairouz et al. point out, this property does not hold for discrete Gaussians—and since EncodeGradient uses a fixed-point representation for noisy gradients, we cannot rely on the summation property. Instead, our privacy analysis proceeds based on Proposition 14 of Kairouz et al. :

where $\tau:=10\cdot\sum_{k=1}^{n-1}e^{-2\pi^{2}\sigma^{2}\frac{k}{k+1}}$.

Proposition 1 provides a bound on Rényi divergence, $D_{\alpha}$, for noise generated as the sum of discrete Gaussians, which directly implies Rényi differential privacy. In our setting, Proposition 1 yields almost identical results to the privacy analysis of Protocol 1 (which assumes continuous Gaussians). Note that the first term of the bound from Proposition 1 is identical to the bound given in our earlier privacy analysis, when $n$ is equal to the batch size $b$ and $\lVert\Delta\rVert_{2}^{2}$ is equal to $C^{2}$ (where $C$ is the $L_{2}$ clipping parameter).

As the fixed-point representation of noisy gradients becomes more precise, the second term of the bound ($\tau d$) becomes extremely small. The EncodeGradient function uses 4 places of precision past the decimal point, meaning that the effective values of $\sigma^{2}$ and $\lVert\Delta\rVert_{2}^{2}$ are 10,000 times their “original” values. Each additional place of precision adds another factor of 10 to both values. This has the effect of reducing the value of $\tau$ to extremely close to zero.

We have implemented both the original analysis (which incorrectly assumes continuous Gaussians) and Proposition 1. The results reported in Section 5 use Proposition 1, but the two methods yield values of $\epsilon$ so close together that the resulting graphs are indistinguishable.

9 Algorithmic Complexity

In order to assume the difficulty of the LWE decision problem, we require that $q$ be polynomial in $n$. Though the field size does affect the precision of the values to be aggregated and the possible number of parties to the aggregation scheme, it is customary to think of $q$ as a constant, and therefore $n$ is constant here too in our complexity analysis. However, in practice it is possible to choose $n$ quite small relative to $q$.

Server complexity consists of adding $k$ masked vectors, reconstructing the packed secret sharing, and multiplying an $m\times n$ matrix by a length $n$ vector. The vector addition and matrix multiplication have complexity $O(mk+m\log(k))$. Reconstructing the packed secret shares takes time $O(k\log(k))$ in the semi-honest case with no dropouts using the Fast Fourier Transform method. In the case of malicious security and dropouts, we use Lagrange interpolation to obtain a runtime of $O(k^{2})$. The number of dropouts does not affect runtime complexity as long as there are more than 0 dropouts. In total, the server runtime complexity is $O(mk+mn+k\log(k))$ in the no dropout scenario, and $O(mk+mn+k^{2})$ in case of dropouts or malicious adversaries.

Evaluation

Our empirical evaluation aims to answer two research questions:

This experimental setup is necessary for the implementation of local experiments with batch sizes of $128$. Reading each gradient from file sidesteps the need for each client to have their own TensorFlow instance, substantially reducing our memory consumption footprint.

The memory consumption issue described here is created by simulating many clients on the same machine. In a true federated learning instance, each client would have their own independent resources, and therefore would not run into this same issue.

1 Experiment 1: Masking Scalability

This section strives to answer RQ1. We implemented the masking protocol in single threaded python and evaluated various federation configurations. Experiments were run on an AWS z1d2xlarge instance with a 4.0Ghz Intel Xeon processor and 64 Gb of RAM . Concrete timing and expansion results for protocol computation are included in Figures 1, 2, and Table 2. We assume semi-honest behavior from the adversary and consider the scenario with no dropouts as well as a $25\%$ dropout rate. In all experiments, $\beta$ is assumed to be $3.2/q$. We assume a single aggregation server, and we assume that clients broadcast the sum of shares to the server rather than performing Shamir reconstruction themselves.

Figures 1 and 2 presents our concrete performance results. We see a significant improvement in client and server computation time over the concrete performance results of Bonawitz et al. . Client computation takes less than half a second for all configurations tested, and is dictated by a linear relationship with the vector size.

Server computation time has a linear relationship with vector size and a quadratic relationship with the number of clients. In the case with no dropouts, server computation is quick, taking less than 5 seconds for all configurations tested. In the dropout scenario, server computation is significantly slower, but still much faster than the state of the art . It’s worth noting that this is an upper bound on server time in the dropout case. Performance can be improved with faster interpolation algorithms .

Recall the quantity $\beta$ from Section 4.6.1, which given $q$ the size of the field gives us the standard deviation of the noise. We observe that changing $\beta$ has no effect on the runtime. We note that changing $\beta$ can require different values for $n$ and $q$ to guarantee a certain amount of security, but this is only necessary if $\beta$ is decreased. For our timing experiments we chose $\beta=3.2/q$ to accommodate a wide variety of privacy budgets for relatively small fixed precision. Because our values are fixed precision with 4 decimal places, the chosen value of $\beta$ adds noise with standard deviation .0409 to our aggregated vectors assuming 128 clients. This is far less than the minimum amount of DP-noise we added in our accuracy experiments, which had a standard deviation of 1.

2 Experiment 2: Model Accuracy

For both the MNIST and CIFAR-10 models, we utilize categorical cross entropy for our loss function, stochastic gradient descent with a learning rate of $0.01$ and momentum of $0.9$ for our optimizer and a clipping parameter $C=5$ for all trials.

We run a series of trials for each dataset with each pair of batch size and $\sigma$ listed in Table 3. All accuracy results are the per epoch average of 4 trials with the given model configuration. $\epsilon$ is calculated post hoc as a function of $\sigma,C,\textit{batch\_size},epochs$. All $\epsilon$ values are calculated from the corresponding Rényi differential privacy guarantee by picking $\alpha$ to minimize the RDP $\epsilon$ parameter, then converting this guarantee into $(\epsilon,\delta)$-differential privacy with $\delta=10^{-5}$. We see selected accuracy results reported for differing values of $\epsilon$ in Figure 3.

The Modified National Institute of Standards and Technology database is an often used image recognition benchmark consisting of 60,000 training samples and 10,000 testing samples; each sample is a $28\times 28$ gray scale image of a handwritten digit. We train a classifier containing 2 ReLU-activated convolution layers, max pooling following each of them, and a ReLU activated dense layer with 32 nodes. Finally, classifications are done with a softmax layer. This model has about 26,000 trainable parameters in total.

After training for 275 epochs, our private MNIST models are able to attain a maximum $98.7\%$ mean validation accuracy over 4 trials. This is a slight decrease in accuracy from the no noise baseline accuracy of $99.2\%$, however the private model still generalizes very well. Figure 4 shows how different privacy budgets affect accuracy for our sample batch sizes. Models trained with all batch sizes see improved accuracy as $\epsilon$ increases, however larger batch sizes tend to produce more accurate models, especially for small values of $\epsilon$. Improved accuracy for larger batch sizes can be seen as an effect of the private average, where the sensitivity of the gradient average is inversely proportional to the batch size. Therefore, larger batches require less noise added for a given privacy budget, resulting in a more accurate model.

2.2 CIFAR-10

The Canadian Institute for Advanced Research 10 dataset consists of 60,000 colored images equally partitioned into 10 classes. Each image is $32\times 32$ with 3 channel RGB colored pixels. We separated the dataset into 50,000 training examples and 10,000 test samples for our experiment. Our trained model contains three pairs of ReLU-activated convolution layers with batch normalization after each layer, and max pooling after each pair. We also include one ReLU activated dense layer with 128 nodes, and a softmax activated output layer. This model contains 550,000 parameters.

With a batch size of 64, we achieve a maximum accuracy of $70.0\%$ mean validation accuracy over 4 trials on CIFAR-10. This is a sizeable drop in accuracy compared to the $77.4\%$ mean accuracy of our architecture trained without differential privacy, however it is in line with differentially private model performance in the central model .

2.3 Comparison With Centralized Differential Privacy

Related Work

Secure multiparty computation (MPC) is a family of techniques that enable mutually distrustful parties to collaboratively compute a function of their distributed inputs without revealing those inputs. MPC techniques include garbled circuits (which is most easily applied in the two-party case) and approaches based on secret sharing (which naturally apply in the $n$-party case). MPC approaches have seen rapid improvement over the past 20 years, but scalability remains a challenge for practical deployments. In particular, most MPC protocols work best when the number of parties is small (e.g., 2 or 3), and costs grow at least quadratically with the number of parties. State-of-the-art protocols support significantly more parties: Wang et al. reach 128 parties using a garbled circuits approach, and Chida et al. reach 110 parties using a secret sharing approach.

MPC techniques have been previously applied to the problem of differentially private deep learning, but these approaches require either a semi-honest data curator or two non-colluding data curators . Secure aggregation protocols (detailed in Section 2) are themselves MPC protocols, specifically designed for the many-client setting. Kairouz et al. present a general framework for differentially private federated learning that leverages existing secure aggregation protocols.

Outside of deep learning, several systems have been proposed for computing differentially private results from distributed data. Honeycrisp and Orchard are most related to our work, and use a distributed protocol similar to secure aggregation to compute the results of database-style queries. ShrinkWrap and Crypt$\epsilon$ leverage existing MPC frameworks to implement differentially private database queries.

While as far as we know there are no security reductions for small fixed $\beta q$, at the same time we do not currently know of an attack that takes advantage of a small constant standard deviation. Accordingly, our choice is similar to the choice made in the current FrodoKEM algorithm specifications (submission to Round 3 of the NIST PQC challenge) and consistent with the recommendation of .

Conclusion

References

Appendix A Proof of security

Suppose the ideal functionality of noisy vector addition as $F$, an adversary $A$. Let $v_{i}$ and $x_{i}$ be input and view of client $i$ respectively. Let $x_{s}$ be the view of the server. $n$ is the LWE security parameter. Suppose a maliciously secure aggregation protocol $\texttt{Sagg}(X,t)$. Let $V$ be the output of $\pi$.

Let $U$ be the set of clients, and $C\subset U\cup\{S\}$ be the set of corrupt parties.

In the malicious model, we consider dropping out an adversarial behavior without loss of generality.

Suppose the simulator has access to an oracle $\texttt{IDEAL}(t,v_{u})_{u\in U\setminus C}$ where:

Let $\texttt{REAL}_{\pi,C}^{U}=\{x_{i}|i\in C\},V$.

There exists a PPT simulator SIM such that for all $t$, $U$, $C$

In this hybrid SIM has access to $\{x_{i}|i\in U\}$. SIM runs the full protocol and outputs a view of the adversary from the previous hybrid.

In this hybrid, SIM has corrupt parties receive an ABORT if the server sends a $U_{1}$ such that $t>|U_{1}|$.

In this hybrid, SIM replaces $V$ with the output of $F$ from any $x_{C}$.

In this hybrid, SIM replaces $s$, the sum of secret vectors with a vector of random field elements distributed by $\chi*k$. Because $s$ is not used to reconstruct $G$, and is normally distributed by $\chi*k$, this hybrid is indistinguishable from the previous hybrid.

In this hybrid, SIM replaces $H$ with $V+As$.

In this hybrid, SIM replaces the run of protocol Sagg with the ideal simulation of Sagg. If Sagg returns ABORT, SIM returns ABORT. Because Sagg is secure, this hybrid is indistinguishable from the previous hybrid using each parties $s_{i}$ as input.

In this hybrid, SIM replaces the $s_{i}$ of each client with a vector of elements distributed by $\chi$. Because $s_{i}$ is typically distributed by $\chi$ and each $s_{i}$ is not used to compute $s$ anymore, this hybrid is indistinguishable from the previous hybrid.

After these steps, the simulator no longer needs any input from the honest clients to simulate Protocol 3, implying that it is secure in the malicious threat model.

Notably, our malicious threat model subsumes the semi-honest threat model. Therefore this proof proves security in that threat model as well. In the case of a semi-honest threat model, the security of Sagg can also eased to semi-honest.