César Sabater

Aurélien Bellet

Jan Ramon

Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties

Learning from data owned by several parties, as in federated learning, raises challenges regarding the privacy guarantees provided to participants and the correctness of the computation in the presence of malicious parties. We tackle these challenges in the context of distributed averaging, an essential building block of distributed and federated learning. Our first contribution is a novel distributed differentially private protocol which naturally scales with the number of parties. The key idea underlying our protocol is to exchange correlated Gaussian noise along the edges of a network graph, complemented by independent noise added by each party. We analyze the differential privacy guarantees of our protocol and the impact of the graph topology, showing that we can match the accuracy of the trusted curator model even when each party communicates with only a logarithmic number of other parties chosen at random. This is in contrast with protocols in the local model of privacy (with lower accuracy) or based on secure aggregation (where all pairs of users need to exchange messages). Our second contribution is to enable users to prove the correctness of their computations without compromising the efficiency and privacy guarantees of the protocol. Our construction relies on standard cryptographic primitives like commitment schemes and zero knowledge proofs.

Introduction

Individuals are producing ever growing amounts of personal data, which in turn fuel innovative services based on machine learning (ML). The classic centralized paradigm consists in collecting, storing and analyzing this data on a (supposedly trusted) central server or in the cloud. which poses well documented privacy risks for the users. With the increase of public awareness and regulations, we are witnessing a shift towards a more decentralized paradigm where personal data remains on each user's device, see the recent trend of federated learning [START_REF] Peter Kairouz | Advances and Open Problems in Federated Learning[END_REF]. In this setting, users do not trust the central server (if any), or each other, which introduces new issues regarding privacy and security. First, the information shared by the participants during the decentralized training protocol can reveal a lot about their private data (see [START_REF] Melis | Exploiting unintended feature leakage in collaborative learning[END_REF][START_REF] Nasr | Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning[END_REF] for inference attacks on federated learning). Formal guarantees such as differential privacy (DP) [START_REF] Dwork | Differential Privacy[END_REF] are needed to provably mitigate this and convince privacy-aware users to participate in the protocol. Second, malicious users may send incorrect results to bias the learned model in arbitrary ways [START_REF] Hayes | Contamination attacks and mitigation in multi-party machine learning[END_REF][START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF][START_REF] Bagdasaryan | How to backdoor federated learning[END_REF]. Robustness to such adversaries is crucial to persuade service providers to move to a more decentralized and privacy-friendly setting.

In this work, we tackle these challenges in the context of private distributed averaging. In this canonical problem, the objective is to privately compute an estimate of the average of values owned by many users who do not want to disclose them. Beyond simple data analytics, distributed averaging is of high relevance to modern ML. Indeed, it is the essential primitive used to aggregate user updates in gradient-based distributed and federated learning algorithms [START_REF] Lin | Don't Use Large Minibatches, Use Local SGD[END_REF][START_REF] Stich | Local SGD Converges Fast and Communicates Little[END_REF][START_REF] Zheng | Communication-efficient learning of deep networks from decentralized data[END_REF][START_REF] Jayaraman | Distributed learning without distress: Privacy-preserving empirical risk minimization[END_REF][START_REF] Agarwal | cpSGD: Communication-efficient and differentially-private distributed SGD[END_REF]. It also allows to train ML models whose sufficient statistics are averages (e.g., linear models and decision Preprint. Under review. trees). Distributed averaging with differential privacy guarantees has thus attracted a lot of interest in recent years. In the strong model of local differential privacy (LDP) [START_REF] Prasad Kasiviswanathan | What Can We Learn Privately?[END_REF][START_REF] John C Duchi | Local privacy and statistical minimax rates[END_REF][START_REF] Kairouz | Secure multi-party differential privacy[END_REF][START_REF] Kairouz | Extremal Mechanisms for Local Differential Privacy[END_REF][START_REF] Kairouz | Discrete distribution estimation under local privacy[END_REF], each user randomizes its input locally before sending it to an untrusted aggregator. Unfortunately, the best possible error for the estimated average with n users is a factor of O( √ n) larger than in the centralized model of DP where a trusted curator aggregates data in the clear and perturbs the output [START_REF] Hubert Chan | Optimal Lower Bound for Differentially Private Multi-party Aggregation[END_REF]. To fill this gap, some work has explored relaxations of LDP that make it possible to match the accuracy of the trusted curator model. This is achieved through the use of cryptographic primitives such as secret sharing [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF], secure aggregation [START_REF] Hubert Chan | Privacy-preserving stream aggregation with fault tolerance[END_REF][START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF][START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF][START_REF] Jayaraman | Distributed learning without distress: Privacy-preserving empirical risk minimization[END_REF] and secure shuffling [START_REF] Erlingsson | Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity[END_REF][START_REF] Cheu | Distributed Differential Privacy via Shuffling[END_REF][START_REF] Balle | The Privacy Blanket of the Shuffle Model[END_REF]. Many of these primitives however assume that all users truthfully follow the protocol (they are honest-but-curious), and they are generally intractable when the number of parties is large.

Our contribution is twofold. First, we propose a novel differentially private averaging protocol which can match the accuracy of the trusted curator setting while naturally scaling to a large number of users. Our approach, called GOPA (GOssip Noise for Private Averaging) by analogy with gossip protocols [START_REF] Boyd | Randomized gossip algorithms[END_REF], is simple and decentralized. The main idea is to have users exchange correlated Gaussian noise along the edges of a network (represented as a connected graph) so as to mask their private values without affecting the global average. This (ultimately canceling) noise is complemented by the addition of independent (non-canceling) Gaussian noise by each user. We analyze the privacy of GOPA by modeling the knowledge of the adversary (colluding malicious users) as a system of linear equations and show that the privacy guarantees depend on the branching factor of a spanning tree of the subgraph of honest-but-curious users. Remarkably, we establish that we can recover the privacy-utility trade-off of the trusted curator setting as long as the graph of honest-but-curious users is connected and the pairwise-correlated noise variance is large enough. We further show that if the graph is well-connected, this variance can be significantly reduced. Finally, to ensure scalability and robustness in practice, we propose an efficient randomized procedure to construct a graph in which each user needs to communicate with only a logarithmic number of other users while still matching the privacy-utility trade-off of the trusted curator model. We prove these guarantees by leveraging and adapting results from random graph theory on embedding spanning trees in random graphs.

Our second contribution is a procedure to make GOPA verifiable by untrusted external parties, i.e., to provide users with the means of proving the correctness of their computations without compromising the efficiency or the privacy guarantees of the protocol. Our construction relies on commitment schemes and zero knowledge proofs (ZKPs), which are very popular in auditable electronic payment systems as well as cryptocurrencies. These cryptographic primitives, originally formalized in [START_REF] Goldwasser | The Knowledge Complexity of Interactive Proof Systems[END_REF], scale well both in network communication and computational requirements and are perfectly suitable in our untrusted decentralized setting. We use classic and state-of-the-art ZKPs to design a procedure for the generation of noise with verifiable distribution, and ultimately to prove the integrity of the final computation (or detect malicious users who did not follow the protocol). Crucially, the privacy guarantees of the protocol are not compromised by this procedure (not even relaxed through a cryptographic hardness assumption), while the integrity of the computation relies on a standard discrete logarithm assumption. In the end, our protocol offers correctness guarantees that are essentially equivalent to the case where a service provider would itself hold the private data of users.

The paper is organized as follows. Section 2 introduces the problem setting as well as the adversary and privacy models. Section 3 presents the GOPA protocol, and we analyze its differential privacy guarantees in Section 4. We present our procedure to ensure correctness against malicious behavior in Section 5, and summarize computational and communication costs in Section 6. Finally, we discuss the related work in more details in Section 7, and conclude with future lines of research in Section 8.

Notations and Setting

We consider a set U = {1, . . . , n} of n ≥ 3 users (parties). Each user u ∈ U holds a private value X u , which can be thought of as being computed from the private dataset of user u. We assume that X u lies in a bounded interval of R (without loss of generality, we assume X u ∈ [0, 1]). The extension to the vector case is straightforward. We denote by X the column vector X = [X 1 , . . . , X n ] ∈ [0, 1] n of private values. Unless otherwise noted, all vectors are column vectors. The users communicate over a network represented by a connected undirected graph G = (U, E), where {u, v} ∈ E indicates that users u and v are neighbors in G and can exchange messages. For a given user u, we denote by N (u) = {v : {u, v} ∈ E} the set of its neighbors.

The users aim to collaboratively compute the average value X avg = 1 n n u=1 X u without revealing their individual private value. Such a protocol can be readily used to privately execute distributed ML algorithms that interact with data through averages over values computed locally by the participants, but do not actually need to see the individual values. We give two concrete examples below. Example 1 (Linear regression). Let λ ≥ 0 be a public parameter. Each user u holds a private feature vector φ u = [φ 1 u , . . . , φ d u ] ∈ R d and a private label y u ∈ R. The goal is to solve a ridge regression task, i.e. find θ * ∈ arg min θ 1 n u∈U (φ u θ -y u ) 2 + λ θ 2 . The solution θ * can be computed in closed form from the quantities 1 n u∈U φ i u y u and 1 n u∈U φ i u φ j u for all i, j ∈ {1, . . . , d}. Example 2 (Federated ML). In federated learning [START_REF] Peter Kairouz | Advances and Open Problems in Federated Learning[END_REF] and more generally distributed empirical risk minimization, each user u holds a private dataset D u and the goal is to find θ * such that θ * ∈ arg min θ 1 n u∈U f (θ; D u ) where f is some loss function. Popular algorithms [START_REF] Lin | Don't Use Large Minibatches, Use Local SGD[END_REF][START_REF] Stich | Local SGD Converges Fast and Communicates Little[END_REF][START_REF] Zheng | Communication-efficient learning of deep networks from decentralized data[END_REF][START_REF] Jayaraman | Distributed learning without distress: Privacy-preserving empirical risk minimization[END_REF][START_REF] Agarwal | cpSGD: Communication-efficient and differentially-private distributed SGD[END_REF] all follow the same high-level procedure: at round t, each user u computes a local update θ t u based on D u and the current global model θ t-1 , and the updated global model is computed as θ t = 1 n u θ t u . Threat model. We consider two commonly adopted adversary models, which were formalized by [START_REF] Goldreich | Secure multi-party computation[END_REF] and are used in the design of many secure protocols. An honest-but-curious (honest for short) user will follow the protocol specification, but may use all the information obtained during the execution to infer information about other users. In contrast, a malicious user may deviate from the protocol execution by sending incorrect values at any point (we assume that they follow the required communication policy; if not, this can be easily detected). Malicious users can collude, and thus will be seen as a single malicious party (the adversary) who has access to all information collected by malicious users (privacy with respect to a single honest user can be obtained as a special case). Our privacy guarantees will hold under the assumption that honest users communicate through secure channels, while the correctness of our protocol will be guaranteed under some form of the Discrete Logarithm Assumption (DLA), a standard assumption in cryptography (see Appendix B for details).

Each user in the network is either honest or malicious. Honest users do not know whether other nodes are malicious. We denote by U H ⊆ U the set of honest users, by n H = |U H | the number of honest users and by ρ = n H /n their proportion in the network. We also denote by

G H = (U H , E H ) the subgraph of G induced by the set of honest users U H , i.e., E H = {{u, v} ∈ E : u, v ∈ U H }.
The properties of G and G H will play a key role in the efficiency and privacy guarantees of our protocol.

Privacy model. Our goal is to design a protocol which satisfies differential privacy [START_REF] Dwork | Differential Privacy[END_REF], which has become a gold standard notion in privacy-preserving information release. Definition 1 (Differential privacy). Let ε > 0, δ ≥ 0. A (randomized) protocol A is (ε, δ)differentially private if for all neighboring datasets X, X , i.e., datasets differing only in a single data point, and for all sets of possible outputs O, we have:

P r(A(X) ∈ O) ≤ e ε P r(A(X ) ∈ O) + δ.
(1)

GOPA: Gossip Noise for Private Averaging

In this section we describe our protocol, called GOPA (GOssip noise for Private Averaging). The high-level idea of GOPA is to have each user u mask its private value by adding two different types of noise. The first is a sum of pairwise-correlated noise terms ∆ u,v over the set of neighbors v ∈ N (u) such that each ∆ u,v cancels out with the ∆ v,u of user v in the final result. The second type of noise is an independent term η u which does not cancel out in the final result. At the end of the protocol, each user has generated a noisy version Xu of his private value X u , which takes the following form:

Xu = X u + v∈N (u) ∆ u,v + η u . (2)
Algorithm 1 presents the detailed steps. Neighboring nodes {u, v} ∈ E contact each other to draw a real number from the Gaussian distribution N (0, σ 2 ∆ ), that u adds to its private value and v subtracts. Each user thereby distributes noise masking his private value across several users, which will provide some robustness to malicious parties. The idea is reminiscent of one-time pads in secure aggregation (see [START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF], Section 3) but we use Gaussian noise rather than padding and restrict exchanges to the edges of the graph instead of considering all pairs. As in gossip algorithms [START_REF] Boyd | Randomized gossip algorithms[END_REF], the pairwise exchanges can be performed asynchronously and in parallel. Additionally, every user u ∈ U adds an independent noise term η u ∼ N (0, σ 2 η ) to its private value. This noise will ensure that the final estimate of the average satisfies differential privacy (see Section 4). σ 2 ∆ and σ 2 η are public parameters of the protocol.

Algorithm 1 GOPA protocol Input: graph G = (U, E), private values (X u ) u∈U , variances σ 2 ∆ , σ 2 η ∈ R + 1: for all neighbor pairs (u, v) ∈ E s.t. u < v do 2:
u and v draw a random x ∼ N (0, σ 2 ∆ ) and set ∆ u,v ← x, ∆ v,u ← -x 3: for all users u ∈ U do 4:

u draws a random η u ∼ N (0, σ 2 η ) and reveals noisy value

Xu ← X u + v∈N (u) ∆ u,v + η u
Utility of GOPA. The protocol generates a set of noisy values X = [ X1 , . . . , Xn ] which are then publicly released. They can be sent to an untrusted aggregator, or averaged in a decentralized way via gossiping [START_REF] Boyd | Randomized gossip algorithms[END_REF]. In any case, the estimated average is given by Xavg = 1 n u∈U Xu = X avg + 1 n u∈U η u , which has expected value X avg and variance σ 2 η /n. Ideally, we would like the total amount of independent noise to be of the same order as that needed to protect the average with the standard Gaussian mechanism in the trusted curator model of DP [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF], that is

η u = O(1/n).

Impact of σ 2

∆ . As we shall see in Section 4, the role of the pairwise noise terms is to compensate the independent noise that would be needed to protect individual values in the local model of differential privacy (where each user would release a locally perturbed input without communicating with other users). While the variance σ 2 ∆ must be sufficiently large to serve this purpose, it should be kept to a reasonable value. Indeed, a larger σ 2 ∆ induces a small (logarithmic) increase in communication costs as the representation space of the real values needs to be large enough to avoid overflows with high probability (we discuss these aspects in more details in further sections).

An important advantage of using centered Gaussian noise with bounded variance is to limit the impact of some users dropping out during the protocol. In particular, any residual noise term ∆ u,v (i.e., which does not cancel out due to either u or v dropping out) has expected value 0 and can be bounded with high probability. The smaller σ 2 ∆ , the smaller the impact on the accuracy of the final output in the event of drop outs. If the accuracy is deemed insufficient, it is however possible to "roll back" some of the faulty noise exchanges to regain precision at the expense of extra communication.

Privacy Guarantees of GOPA

In this section, we show that GOPA achieves ( , δ)-DP as long as G H (the subgraph of honest users) is connected and σ 2 η , σ 2 ∆ are large enough. More specifically, we will prove that (i) the variance σ 2 η of the independent (non-canceling) noise can be as small as in the trusted curator setting, and (ii) the required variance σ 2 ∆ for the pairwise (canceling) noise depends on the topology of G H .

Privacy Guarantees for Worst and Best Case Graphs

The knowledge acquired by the adversary (colluding malicious users) during the execution of the protocol consists of the following: (i) the noisy values X of all users, (ii) the full network graph G, (iii) the private value X u and the noise η u of the malicious users, and (iv) all ∆ u,v 's for which u or v is malicious. The only unknowns are the private value X u and independent noise η u of each honest user u ∈ U H , as well as the ∆ u,v 's exchanged between honest users {u, v} ∈ E H . From the knowledge above, the adversary can subtract the sum of noise exchanges v∈N (u

)\N H (u) ∆ u,v from Xu to obtain XH u = X u + u∈N H (u) ∆ u,v + η u for every honest u ∈ U H .
The view of the adversary can be summarized by the vector XH = ( XH u ) u∈U H and correlation between its elements. Our goal is to prove a differential privacy guarantee for GOPA. Adapting Definition 1 to our setting, for any input X and any possible outcome X ∈ R n , we need to compare the probability of the outcome being equal to X when a honest user v 1 ∈ U H participates in the computation with private value X A v1 to the probability of obtaining the same outcome when the value of v 1 is exchanged with an arbitrary value X B v1 ∈ [0, 1]. For notational simplicity, we denote by X A the vector of private values (X u ) u∈U H of honest users in which a user v 1 has value X A v1 , and by X B the vector where v 1 has value X B v1 . X A and X B differ in only in the v 1 -th coordinate, and their maximum difference is 1. Our first result gives a differential privacy guarantee for the worst-case topology.

Theorem 1 (Privacy guarantee for the worst-case graph). Let X A and X B be two databases (i.e., graphs with private values at the vertices) which differ only in the value of one user. Let ε, δ ∈ (0, 1) and θ =1

σ 2 η n H + n H 3σ 2 ∆
. If G H is connected and the following two inequalities hold:

ε ≥ θ/2 + θ 1/2 , (3)
(ε -θ/2) 2 ≥ 2 log(2/δ √ 2π)θ, (4)
then GOPA is (ε, δ)-differentially private, i.e., P ( X | X A ) ≤ e ε P ( X | X B ) + δ.

Crucially, Theorem 1 holds as soon as the subgraph G H of honest users is connected. 1 In order to get a constant ε, inspecting the term θ shows that the variance σ 2 η must be of order 1/n H regardless of the topology of G H . This is in fact optimal as it corresponds to the amount of noise required when averaging n H values in the trusted curator setting. It also matches the amount of noise required when using secure aggregation with differential privacy in the presence of colluding users, where honest users need to add n/n H more noise to compensate for collusion [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF]. In order to match the privacy-utility trade-off of the trusted curator setting, further inspection of the equations in Theorem 1 shows that the variance σ 2 ∆ of the pairwise noise must be large enough. How large it must be depends in fact on the structure of the graph G H . Theorem 1 describes the worst case, which is attained when every node has as few neighbors as possible while still being connected, i.e., when G H is a path. In this case, Theorem 1 shows that the variance σ 2 ∆ needs to be of order n H . Recall that this noise cancels out, so it does not impact the utility of the final output but only has a minor effect the communication cost and the robustness to drop out, as discussed in Section 3.

Intuitively, in graphs with higher connectivity, it should however be possible for σ 2 ∆ to be smaller than O(n H ). Before considering more practical topologies, we illustrate this on the complete graph case, which provides a best-case scenario in terms of connectivity. Theorem 2 shows that for a fully connected G H , σ 2 ∆ can be of order 1/n H , which is a quadratic reduction compared to the path case. Theorem 2 (Privacy guarantee for the complete graph). Let ε, δ ∈ (0, 1) and let G H be the complete graph. If ε, δ, σ η and σ ∆ satisfy the inequalities (3) and (4) in Theorem 1 with θ = 1

σ 2 η n H + 1 σ 2 ∆ n H then GOPA is (ε, δ)-differentially private.

Privacy Guarantees for Practical Random Graphs

Our results so far gives two options that are not fully satisfactory from the practical perspective when the number of users n is large. One option is to come up with a graph G such that G H is connected with high probability and use a large σ 2 ∆ of O(n H ) as specified by the worst-case of Theorem 1. Alternatively, we can work with the complete graph, which allows smaller O(1/n H ) variance (Theorem 2) but is intractable as all n 2 pairs of users need to exchange noise.

Instead, we propose a simple randomized procedure to construct a sparse network graph G such that G H will be well-connected with high probability, and prove a DP guarantee for the whole process (random graph generation followed by GOPA) under much less noise than the worst-case. The idea is to make each (honest) user select k other users uniformly at random among all users. Then, the edge {u, v} ∈ E is created if u selected v or v selected u (or both). This is known as a random k-out graph [START_REF] Bollobás | Random Graphs[END_REF] or random k-orientable graph [START_REF] Fenner | On the connectivity of random m-orientable graphs and digraphs[END_REF]. Such graphs are known for their very good connectivity properties [START_REF] Fenner | On the connectivity of random m-orientable graphs and digraphs[END_REF][START_REF] Yagan | On the Connectivity of Sensor Networks Under Random Pairwise Key Predistribution[END_REF] and are used for instance in creating secure communication channels in distributed sensor networks [START_REF] Chan | Random Key Predistribution Schemes for Sensor Networks[END_REF]. We note that GOPA can be conveniently executed while constructing the random k-out graph. We have the following privacy guarantees. Theorem 3 (Privacy guarantee for random k-out graphs). Let , δ ∈ (0, 1) and let G be obtained by letting all (honest) users randomly choose k ≤ n neighbors. Let k and ρ = n H /n be such that ρn ≥ 81, ρk ≥ 4 log(2ρn/3δ), ρk ≥ 6 log(ρn/3) and ρk ≥ 3 2 + 9 4 log(2e/δ). If , δ, σ η and σ ∆ satisfy the inequalities (3) and (4) in Theorem 1 with

θ = n -1 H σ -2 η + 1 (k -1)ρ/3 -1 + (12 + 6 log(n H ))/n H σ -2 ∆ ,
then GOPA is ( , 3δ)-differentially private.

Complete

Random k-out Worst-case ρ = 1 ρ = 0.5 ρ = 1 ρ = 0.5 ρ = 1 ρ = 0.5 This result has a similar form as Theorems 1-2 but requires k to be large enough (of order log(ρn)/ρ) so that G H is sufficiently connected. Importantly, it is sufficient to have σ 2 ∆ of order 1/kρ to ensure that we match the utility of the trusted curator model. Furthermore, each user needs to exchange with only 2k = O(log n) other users in expectation, which is much more practical than a complete graph.

Scaling the noise in practice. Using the above results, we can precisely quantify the amount of independent and pairwise noise needed to achieve a desired privacy guarantee depending on the topology, as illustrated by the following corollary. Corollary 1. Let ε, δ ∈ (0, 1), and

σ 2 η = c 2 /n H ε 2 , where c 2 > 2 log(1.25/δ ). Given some κ > 0, let σ 2 ∆ = κσ 2 η if G is complete, σ 2 ∆ = κσ 2 η n H ( 1 (k-1)ρ/3 -1 + (12 + 6 log(n H ))/n H ) if it is a random k-out graph, and σ 2 ∆ = κσ 2 η n 2 H /3 for an arbitrary connected G H . Then, GOPA is (ε, δ)-DP with δ ≥ a(δ /1.25) κ/κ+1
, where a = 3.75 for the random k-out graph and 1.25 otherwise.

In Corollary 1, σ 2

η is set such that after all noisy values are aggregated, the variance of the residual noise matches the one required by the standard Gaussian Mechanism [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF] to achieve (ε, δ )-DP for an average of n H values in the centralized setting. The privacy-utility trade-off achieved by GOPA is thus the same as in the trusted curator model up to a small constant in δ, as long as the pairwise variance σ 2 ∆ is large enough. As expected, we see that as σ 2 ∆ → +∞ (that is, as κ → +∞), we have δ → δ . Given the desired δ ≥ δ , we can use Corollary 1 to determine a value for σ 2 ∆ that is sufficient for GOPA to achieve ( , δ)-DP. Table 1 shows a numerical illustration with δ only a factor 10 larger than the δ of the trusted curator setting. For random k-out graphs, we report the values of σ ∆ and k given by Theorem 3, as well as smaller (yet admissible) values obtained by numerical simulation (see Appendix A.5). We see that although the conditions of Theorem 3 are a bit conservative (we are confident that constants in our analysis can be improved), they still lead to practical values. Clearly, random k-out graphs provide a useful trade-off in terms of scalability and robustness.

Proof techniques. At the technical level, our analysis decomposes into a generic (ε, δ)-differential privacy result, where we model the knowledge of the adversary as a system of linear equations, and a topology-specific part. In the latter part, the generic result is instantiated by identifying a spanning tree in G H with appropriate branching factor. While the optimal spanning tree is easy to construct for the worst-case and complete graphs, the case of random graphs is more involved and requires specific tools. We prove our result by leveraging and adapting results on embedding spanning trees in random graphs [START_REF] Krivelevich | Embedding spanning trees in random graphs[END_REF]. The full derivations and more detailed explanations can be found in Appendix A.

Ensuring Correctness Against Malicious Users

While the privacy guarantees of Section 4 hold no matter what the malicious users do, the utility guarantees of GOPA discussed in Section 3 are not valid if malicious users tamper with the protocol. In this section, we add to our protocol the capability of being audited to ensure the correctness of the computations while preserving privacy guarantees. While it is impossible to force a user to give the "right" input to the algorithm, this also holds in the centralized setting. Our goal is thus to guarantee that given the input vector X, GOPA will either generate a truthfully computed output Xavg or identify malicious behavior. Concretely, users will be able to prove the following properties:

Xu = X u + ∆ u + η u , ∀u ∈ U, (5)
∆ u,v = -∆ v,u , ∀{u, v} ∈ E, (6)
η u ∼ N (0, σ 2 η ), ∀u ∈ U, (7)
X u ∈ [0, 1], ∀u ∈ U. (8)
We also explain how to verify consistency over multiple runs of GOPA on the same/related data.

Tools for verifying computations. Our approach consists in publishing an encrypted log of the computation using cryptographic commitments and proving that it is performed correctly without revealing any additional information using zero knowledge proofs. Commitments and ZKPs are popular in a number of applications such as privacy-friendly auditable financial systems [68,38].

Commitments, first introduced in [START_REF] Blum | Coin flipping by telephone a protocol for solving impossible problems[END_REF], allow users to commit to chosen values while keeping them hidden from others. After the commitment is performed, the committer cannot change its value, but can later reveal it or prove properties of it. For our protocol we use an optimized version [START_REF] Franck | Efficient Implementation of Pedersen Commitments Using Twisted Edwards Curves[END_REF] of the Pedersen commitment scheme [START_REF] Pryds | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF]. A commitment is obtained by transforming the hidden statement using a hard-to-invert injective function Com, so that the recipient cannot know the original statement but can be sure that the committer cannot change the statement and still obtain the same commitment. Pedersen commitments additionally satisfy the homomorphic property, meaning that

Com(v 1 + v 2 ) = Com(v 1 ) + Com(v 2 ) for all values v 1 , v 2 .
This property facilitates verifying the correctness of summations without revealing them: in our case, verifying Properties ( 5) and ( 6).

To verify other properties than the additive ones, we use another family of cryptographic operations that are known as Zero Knowledge Proofs (ZKPs). Informally speaking, ZKPs allow a user (prover) to effectively prove a true statement (completeness), but also allow the other user (verifier) to discover with high probability if a cheating prover is trying to prove a statement which is not true (soundness), in such a way that by performing the proof no information other than the proven statement is revealed (zero knowledge). Here, we use classic [START_REF] Chaum | Wallet Databases with Observers[END_REF][START_REF] Mao | Guaranteed correct sharing of integer factorization with off-line shareholders[END_REF] and more recent [START_REF] Bünz | Bulletproofs: Short Proofs for Confidential Transactions and More[END_REF] proof techniques as building blocks. In particular, these building blocks support the verification of Properties ( 5) and ( 6), and constitute the bulk of the verification of ( 7) and ( 8).

Roughly speaking, the only assumption needed to ensure the validity of the commitments and ZKPs on which we rely is the Discrete Logarithm Assumption (DLA). We refer the interested reader to Appendices B.1-B.3, where we provide a step-by-step, bottom-up presentation of DLA, commitments, ZKPs, and of our own constructions over these existing building blocks.

Verification protocol. In a setup phase, users agree on a shared Pedersen commitment function Com. Then, while executing GOPA, users publish commitments of X u and η u for all u ∈ U and of ∆ u,v for all {u, v} ∈ E. Due to the homomorphic property of the Pedersen commitments, everyone can then verify the summation relations, i.e., Properties ( 5) and [START_REF] Balle | The Privacy Blanket of the Shuffle Model[END_REF]. In a second phase, ZKPs are performed to prove the remaining parts of the verification. To limit the number of ZKPs while convincing all involved users of the correctness of the computations, publicly randomly generated challenges can be used. We implement the publication of commitments using a public bulletin board so that any party can verify the validity of the protocol, avoiding the need for a trusted verification entity. Users sign their messages so they cannot deny them. More general purpose distributed ledger technology such as in Bitcoin [START_REF] Nakamoto | Bitcoin: A Peer-to-Peer Electronic Cash System[END_REF] could be used here, but we aim at an application-specific, light-weight and hence more scalable solution. Since the basic cryptographic operations are integer-based, we use a fixed precision scheme (see Appendix E for a discussion), which is efficient as our computations are mostly additive. More details on our verification protocol are provided in Appendix B.4.

It is easy to see that the correctness of the computation is guaranteed if Properties ( 5)-( 8) are satisfied. Note that, as long as they are self-canceling and not excessively large (avoiding overflows and additional costs if a user drops out, see Appendix B.4), we do not need to ensure that pairwise noise terms ∆ u,v have been drawn from the prescribed distribution, as these terms do not influence the final result and only those involving honest users affect the privacy guarantees of Section 4. In contrast, Properties ( 7) and ( 8) are necessary to prevent a malicious user from biasing the outcome of the computation. Indeed, [START_REF] Elaine | Recommendation for random number generation using deterministic random bit generators (revised)[END_REF] ensures that the independent noise is generated correctly, while [START_REF] Bell | Private Protocols for U-Statistics in the Local Model and Beyond[END_REF] ensures that input values are in the allowed range. The following result summarizes the security guarantees.

Theorem 4 (Security guarantees of GOPA). Under the DLA, a user u ∈ U that passes the verification procedure proves that Xu was computed correctly. Additionally, u does not reveal any additional information about X u by running the verification protocol, even if DLA does not hold.

Consistency across multiple runs. Many ML algorithms (see Examples 1 and 2), require computing several averages involving the same or related private values. Additional security can be obtained by (a) requiring users to commit once to a value and then use it during the complete run of one or several algorithms, and (b) using state-of-the-art ZKP techniques [START_REF] Bootle | Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting[END_REF][START_REF] Bünz | Bulletproofs: Short Proofs for Confidential Transactions and More[END_REF] to prove arithmetic relations.

We conclude by claiming that, with the above guarantees, we provide a similar control over the correctness of computations as in the centralized setting. We further discuss this in Appendix B.4.

Computation and Communication Costs

Our cost analysis, detailed in Appendix D, considers user-centered costs, which is natural as most operations can be performed asynchronously and in parallel. The following summarizes our results. Theorem 5 (Complexity of GOPA). Let B > 0 be the desired precision of the fixed precision representation, e.g., the number 1 would be represented as the closest integer to 1/B. Then, in the private averaging phase, every user u performs O(|N (u)| + log(1/B)) computations and communications. In the verification phase, the protocol proves that all computations were performed correctly, where the η u are drawn from a Gaussian distribution approximated with 1/B equiprobable bins and proved with precision B, with a cost of O(|N (u)| + log(1/B) log(log(1/B))) per user.

Unlike other frameworks such as fully homomorphic encryption and secure multiparty computation, the cost of computing Pedersen commitments and ZKPs is tractable, even in massive amounts, as seen from production environment benchmarks [START_REF] Franck | Efficient Implementation of Pedersen Commitments Using Twisted Edwards Curves[END_REF][START_REF] Bünz | Bulletproofs: Short Proofs for Confidential Transactions and More[END_REF]. The above theorem assumes all users complete their participation in the protocol. If a user u drops out (gets off-line), we can roll back all computations where that user was involved (costing a broadcast and O(1) per neighbor), or accept a potential bias or additional error in the result (corresponding to the ∆ u,v random variables).

Related Work

Local differential privacy (LDP) [START_REF] Prasad Kasiviswanathan | What Can We Learn Privately?[END_REF][START_REF] John C Duchi | Local privacy and statistical minimax rates[END_REF][START_REF] Kairouz | Secure multi-party differential privacy[END_REF][START_REF] Kairouz | Extremal Mechanisms for Local Differential Privacy[END_REF][START_REF] Kairouz | Discrete distribution estimation under local privacy[END_REF] require users to locally randomize their input before they send it to an untrusted aggregator. This very strong model of privacy comes at a significant cost in terms of the accuracy of the resulting estimates, see [START_REF] Zheng | Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible[END_REF][START_REF] Wang | Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited[END_REF] for the limits of machine learning in the local model. For the problem of averaging, the best possible error is of

O(1/n) in the trusted curator model while it is O(1/ √ n)
in the local differential privacy model [START_REF] Hubert Chan | Optimal Lower Bound for Differentially Private Multi-party Aggregation[END_REF]. This makes the local model useful only in large-scale industrial settings where the number of participants is huge [START_REF] Erlingsson | Rappor: Randomized aggregatable privacy-preserving ordinal response[END_REF][START_REF] Bolin Ding | Collecting telemetry data privately[END_REF].

Our approach belongs to the recent line of work which attempts to relax the LDP model so as to improve utility without relying on a trusted curator. Several papers have leveraged secret sharing and/or secure aggregation schemes to recover the utility of the trusted curator model, see [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF][START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF][START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF][START_REF] Hubert Chan | Privacy-preserving stream aggregation with fault tolerance[END_REF] for protocols and [START_REF] Jayaraman | Distributed learning without distress: Privacy-preserving empirical risk minimization[END_REF] for a concrete application to distributed machine learning. These approaches can be made robust to malicious parties, using for instance verifiable secret sharing [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF]. However, they require O(n) communication per party, which is not feasible beyond a few hundred or thousand participants. In contrast, our protocol requires only logarithmic communication. Recently, the shuffle model of privacy [START_REF] Cheu | Distributed Differential Privacy via Shuffling[END_REF][START_REF] Erlingsson | Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity[END_REF][START_REF] Balle | The Privacy Blanket of the Shuffle Model[END_REF][START_REF] Hartmann | Privacy-Preserving Distributed Learning with Secret Gradient Descent[END_REF][START_REF] Balle | Differentially Private Summation with Multi-Message Shuffling[END_REF][START_REF] Ghazi | Pure Differentially Private Summation from Anonymous Messages[END_REF], where inputs are passed to a secure shuffler that obfuscates the source of the messages, has been studied theoretically as an intermediate point between the local and trusted curator models. For differentially private averaging, the shuffle model allows to match the utility of the trusted curator setting. However, practical implementations of secure shuffling are not discussed in these works. Existing solutions typically rely on multiple layers of routing servers [START_REF] Dingledine | Tor: The second-generation onion router[END_REF] with high communication overhead and non-collusion assumptions. Anonymous communication is also potentially at odds with the identification of malicious parties. To the best of our knowledge, all protocols for averaging in the shuffle model assume honest-but-curious parties. Finally, the recent work by [START_REF] Hafiz Imtiaz | Distributed Differentially Private Computation of Functions with Correlated Noise[END_REF] uses correlated Gaussian noise to achieve trusted curator accuracy for averaging. A key difference with our work is that the noise terms in their protocol are correlated at the global level (i.e., sums to zero once averaged over all users), requiring a call to a secure aggregation primitive that does not scale well, as discussed above. In contrast, our pairwise-canceling noise can be easily generated in a decentralized fashion. [START_REF] Hafiz Imtiaz | Distributed Differentially Private Computation of Functions with Correlated Noise[END_REF] also assume that all parties are honest-but-curious.

In summary, our protocol provides a unique combination of three important features: (a) accuracy of trusted curator setting, (b) logarithmic communication per user, and (c) robustness to malicious users.

Conclusion

We proposed GOPA, a protocol to privately compute averages over the values of many users. GOPA satisfies differential privacy, can match the utility of the trusted curator setting, and is robust to malicious parties. It can be readily used in distributed and federated ML [START_REF] Jayaraman | Distributed learning without distress: Privacy-preserving empirical risk minimization[END_REF][START_REF] Peter Kairouz | Advances and Open Problems in Federated Learning[END_REF] as an alternative to more costly secure aggregation schemes. In future work, we would like to extend the scope of our approach beyond averaging, e.g. to robust aggregation rules for distributed SGD [START_REF] Blanchard | Machine learning with adversaries: Byzantine tolerant gradient descent[END_REF] and to U -statistics [START_REF] Bell | Private Protocols for U-Statistics in the Local Model and Beyond[END_REF]. A promising direction is to combine GOPA with the functional mechanism [START_REF] Zhang | Functional mechanism: Regression analysis under differential privacy[END_REF].

Broader Impact

Our work promotes increased privacy and security in distributed and federated ML. The potential longer-term benefits of our work in this respect are a wider adoption of privacy-preserving ML solutions by service providers (thanks to the improved utility and the correctness guarantees), as well as better confidence of users and the general public in the ability of decentralized ML systems to avoid catastrophic data leaks. With this in mind, we plan to implement an efficient prototype to demonstrate the practicality of our approach.

Conversely, there are potential risks of accidental or deliberate misuse of our work in the sense that it could give a false sense of privacy to users if weak privacy parameters are used in deployment. This applies to all work on differential privacy. More applied research is needed towards developing a methodology to choose appropriate privacy parameters in a data-driven manner and to reliably assess the provided protection in practical use-cases. A good example of such work is a recent study by the US Census to prepare their adoption of differential privacy [START_REF] Abowd | The U.S. Census Bureau Adopts Differential Privacy[END_REF].

As ML penetrates into many areas of society, manipulations of algorithms by malicious parties could have (and have already had) serious societal and political consequences in the real world. A contribution of our work is to guarantee the correctness of the computation to prevent such manipulations. In contrast to the active and complementary research direction which aims to mitigate adversarial attacks with more robust algorithms, ensuring correctness by proving that the computation was done truthfully (without revealing the data) is not much studied in the ML community. This is likely because it requires technical tools from other fields (in particular cryptography and formal verification). We think our work, among others [START_REF] Hickey | Cheap Checking for Cloud Computing: Statistical Analysis via Annotated Data Streams[END_REF], could trigger more efforts in this direction.

SUPPLEMENTARY MATERIAL Appendix A Proofs of Differential Privacy Guarantees

Recall that each user u has a private value X u , and generates Xu by adding pairwise noise terms ∆u = v∈N (u) ∆ u,v (with ∆ u,v + ∆ v,u = 0) as well as independent noise η u . All random variables ∆ u,v (with u < v) and η u are independent. We have the system of linear equations

X = X + ∆ + η,
where ∆ = ( ∆u ) u∈U and η = (η u ) u∈U . An adversary may be able to determine all X u , ∆ u,v and η u for every non-honest user u. Such an adversary can hence fill part of the variables in the system of linear equations. Let X H = (X u ) u∈U H be the vector of private values restricted to the honest users.

Let ∆H u = v∈N H (u) ∆ u,v and let XH u = Xu -v∈N (u)\N H (u) ∆ u,v .
In this way, the adversary should now solve a new system of linear equations:

XH = X H + ∆H + η H ,
where ∆H = ( ∆H u ) u∈U H and η H = (η u ) u∈U H . The expectation and covariance matrix of XH are respectively given by:

E XH = X H and Σ = Σ XH = σ 2 η I U H + σ 2 ∆ Λ -σ 2 ∆ A = σ 2 η I U H + σ 2 ∆ L,
where Let

I U H ∈ R n H ×n H is the identity matrix, A ∈ R n H ×n
Σ (g) = σ 2 η I U H 0 0 σ 2 ∆ I E H .
We then have a joint probability distribution of independent Gaussians:

P ((η, ∆)) = C 1 exp - 1 2 (η, ∆) (Σ (g) ) -1 (η, ∆) ,
where

C 1 = (2π) -(n H +|E H |)/2 |Σ (g) | -1/2 .
Consider the following subspaces of Z:

Z A = {(η, ∆) ∈ Z | η + K∆ = XH -X A }, Z B = {(η, ∆) ∈ Z | η + K∆ = XH -X B }.
Assume that the (only) vertex for which X A and X B differ is v 1 . We can assume without loss of generality that private values are in the interval

[0, 1], hence X A v1 -X B v1 = 1. Now choose any t = (t η , t ∆ ) ∈ Z such that t η + Kt ∆ = X A -X B . It follows that Z A = Z B + t, i.e., Y ∈ Z A if and only if Y + t ∈ Z B .
We split the rest of our derivations into four parts. In Section A.1, we first prove a generic intermediate result (Lemma 1) which gives differential privacy guarantees for GOPA that depend on the particular choice of t. Then, in Section A.2, we study the best and worst-case topologies and show how the choice of t can be made intelligently depending on the graph structure, leading to Theorem 1 and Theorem 2. Section A.3.4 presents the derivations for random k-out graphs leading to Theorem 3. Finally, Section A.4 shows how these results can be instantiated to match the accuracy of the centralized Gaussian mechanism (Corollary 1).

A.1 Generic Differential Privacy Result

Let t = (t η , t ∆ ) ∈ Z such that t η + Kt ∆ = X A -X B as defined above. We start by proving differential privacy guarantees which depend on the particular choice of t. Lemma 1. Let ε, δ ∈ (0, 1). Under the setting introduced above, if

ε ≥ (t Σ (-g) t) 1/2 + t Σ (-g) t/2, (9)
and

ε -t Σ (-g) t/2 2 t Σ (-g) t ≥ 2 log 2 δ √ 2π , (10)
where

Σ (-g) = Σ (g) -1 , then GOPA is (ε, δ)-differentially private, i.e., P ( X | X A ) ≤ e ε P ( X | X B ) + δ. Proof. It is sufficient to prove that log P ((η, ∆)) P ((η, ∆) + t) ≤ ε (11)
with probability 1 -δ over (η, ∆). Denoting γ = (η, ∆) for convenience, we need to prove that with probability 1 -δ it holds that | log(P (γ)/P (γ + t))| ≥ e ε . We have

log P (γ) P (γ + t) = - 1 2 γ Σ (-g) γ + 1 2 (γ + t) Σ (-g) (γ + t) = 1 2 (2γ + t) Σ (-g) t .
To ensure Equation [START_REF] Blanchard | Machine learning with adversaries: Byzantine tolerant gradient descent[END_REF] hold with probability 1 -δ, since we are interested in the absolute value, we will show that

P 1 2 (2γ + t) Σ (-g) t ≥ ε ≤ δ/2,
which is equivalent to

P (γΣ (-g) t ≥ ε -t Σ (-g) t/2) ≤ δ/2. ( 12
)
The variance of γΣ (-g) t is var(γΣ

(-g) t) = v var η v σ -2 η t v + e var ∆ e σ -2 ∆ t e = v var (η v ) σ -4 η t 2 v + e var (∆ e ) σ -4 ∆ t 2 e = v σ 2 η σ -4 η t 2 v + e σ 2 ∆ σ -4 ∆ t 2 e = v σ -2 η t 2 v + e σ -2 ∆ t 2 e = t Σ (-g) t.
For any centered Gaussian random variable Y with variance σ 2 Y , we have that

P (Y ≥ λ) ≤ σ Y λ √ 2π exp -λ 2 /2σ 2 Y . ( 13
) Let Y = γΣ (-g) t, σ 2 Y = t Σ (-g) t and λ = ε -t Σ (-g) t/2 so satisfying σ Y λ √ 2π exp -λ 2 /2σ 2 Y ≤ δ/2 (14)
implies [START_REF] Blum | Coin flipping by telephone a protocol for solving impossible problems[END_REF]. Equation ( 14) is equivalent to

λ σ Y exp λ 2 /2σ 2 Y ≥ 2/δ √ 2π,
and taking logarithms we need

log λ σ Y + 1 2 λ σ Y 2 ≥ log 2 δ √ 2π .
To make this inequality hold, we require

log λ σ Y ≥ 0 (15)
and

1 2 λ σ Y 2 ≥ log 2 δ √ 2π . (16)
Equation ( 15) is equivalent to λ ≥ σ Y .

Substituting λ and σ Y we get

ε -t Σ (-g) t/2 ≥ (t Σ (-g) t) 1/2 ,
which is equivalent to [START_REF] Bertoni | Sponge-based pseudorandom number generators[END_REF]. Substituting λ and σ Y in Equation ( 16) gives [START_REF] Arjun | Analyzing federated learning through an adversarial lens[END_REF].

Essentially, given some ε, Equation ( 9) provides a lower bound for the noise (the diagonal of Σ (g) ) to be added. Equation ( 9) also implies that the lefthandside of Equation ( 10) is larger than 1. Equation ( 10) may then require the noise or ε to be even higher if 2 log(2/δ √ 2π) ≥ 1, i.e., δ ≤ 0.48394.

A.2 Worst and Best Case Topologies

Lemma 1 holds for all vectors t = (t η , t ∆ ). There exist multiple vectors t such that t η + Kt ∆ = X A -X B , so we will select the vector t which allows us most easily to prove differential privacy using the above.

Let us first consider the worst case, which corresponds to Theorem 1.

Proof of Theorem 1. Let T be a spanning tree of the (connected) communication graph G H . Let E T be the set of edges in T . Let t ∈ R n H +|E H | be a vector such that:

• For vertices u ∈ U H , t u = 1/n H .
• For edges e ∈ E H \ E T , t e = 0.

• Finally, for edges e ∈ E T , we choose t e in the unique way such that

t η + Kt ∆ = (X A - X B ).
In this way, t η + Kt ∆ is a vector with a 1 on the v 1 position and 0 everywhere else. We can find a unique vector t using this procedure for any communication graph.

It holds that

t η t η = n H 1 n H 2 = 1 n H . (17)
In both Equations ( 9) and ( 10) of Lemma 1, a higher t Σ (-g) t is 'worse' in the sense that a higher ε or δ is needed. Conversely, for a given ε and δ, t Σ (-g) t must be sufficiently low to satisfy both inequalities. We can see t ∆ σ -2 ∆ t ∆ is maximized (thus producing the worst case) if the spanning tree T is a path

(v 1 v 2 . . . v n H ), in which case t {vi,vi+1} = (n H -i)/n H . Therefore, t ∆ t ∆ ≤ n H -1 i=1 n H -i n H 2 = n H (n H -1)(2n H -1)/6 n 2 H = (n H -1)(2n H -1) 6n H . ( 18
)
We now plug in the specific values of t in our general results of Lemma 1. Consider a given δ, σ η and σ ∆ . Substituting Equation ( 17) and ( 18) into Equation ( 9) yields

ε ≥ 1 2 σ -2 η 1 n H + σ -2 ∆ (n H -1)(2n H -1) 6n H + σ -2 η 1 n H + σ -2 ∆ (n H -1)(2n H -1) 6n H 1/2 , which is satisfied if ε ≥ 1 2σ 2 η n H + n H 6σ 2 ∆ + 1 σ 2 η n H + n H 3σ 2 ∆ 1/2 . ( 19
)
Substituting Equation ( 17) and ( 18) into Equation ( 10) yields

ε -σ -2 η 1 n H + σ -2 ∆ (n H -1)(2n H -1) 6n H /2 2 σ -2 η 1 n H + σ -2 ∆ (n H -1)(2n H -1) 6n H ≥ 2 log 2 δ √ 2π , which is satisfied if ε - 1 2σ 2 η n H - n H 6σ 2 ∆ 2 ≥ 2 log 2 δ √ 2π 1 σ 2 η n H + n H 3σ 2 ∆ . (20)
We can observe that in the worst case σ 2 ∆ should be large (linear in n H ) to keep ε small, which has no direct negative effect on the accuracy of the resulting X. On the other hand, σ 2 η can be small (of the order 1/n H ), which means that independent of the number of participants or the way they communicate a small amount of independent noise is sufficient to achieve differential privacy.

However, the necessary value of σ 2 ∆ depends strongly on the network structure. This becomes clear in Theorem 2, which covers the case of the complete graph.

Proof of Theorem 2. If the communication graph is fully connected, we can use the following values for the vector t:

• As earlier, for v ∈ U H , let t v = -1/n H .
• For edges {u, v} with v 1 ∈ {u, v}, let t {u,v} = 0.

• For u ∈ U H \ {v 1 }, let t {u,v1} = 1/n H .
Again, one can verify that t η + Kt ∆ = X A -X B is a vector with a 1 on the v 1 position and 0 everywhere else. In this way, again

t η t η = 1/n H but now t ∆ t ∆ = (n H -1)/n 2
H is much smaller. With this network structure, substituting into Equation (9) yields

ε ≥ 1 2 σ -2 η 1 n H + σ -2 ∆ (n H -1) n 2 H + σ -2 η 1 n H + σ -2 ∆ n H -1 n 2 H 1/2 , which is satisfied if ε ≥ σ -2 η + σ -2 ∆ 2n H + σ -2 η + σ -2 ∆ n H 1/2 . ( 21
)
Substituting into Equation (10) yields

ε -σ -2 η 1 n H + σ -2 ∆ n H -1 n 2 H /2 2 σ -2 η 1 n H + σ -2 ∆ n H -1 n 2 H ≥ 2 log 2 δ √ 2π , which is satisfied if ε -σ -2 η + σ -2 ∆ /2n H 2 ≥ 2 log 2 δ √ 2π σ -2 η + σ -2 ∆ n H . (22)
A practical communication graph will be between the two extremes of the path and the complete graph, as shown by the case of random k-out graphs (see Appendix A.3).

A.3 Random k-out Graphs

In this section, we will study the differential privacy properties for the case where all users select k neighbors randomly, leading to a proof of Theorem 3. We will start by analyzing the properties of G H (Section A.3.1). Section A.3.2 consists of preparations for embedding a suitable spanning tree in G H . Next, in Section A.3.3 we will prove a number of lemmas showing that such suitable spanning tree can be embedded almost surely in G H . Finally, we will apply these results to proving differential privacy guarantees for GOPA when communicating over such a random k-out graph G in Section A.3.4, proving Theorem 3.

In this section, all newly introduced notations and definitions are local and will not be used elsewhere.

At the same time, to follow more closely existing conventions in random graph theory, we may reuse in this section some variable names used elsewhere and give them a different meaning.

A.3.1 The Random Graph G H

Recall that the communication graph G H is generated as follows:

• We start with n = |U | vertices where U is the set of agents.

• All (honest) agents randomly select k neighbors to obtain a k-out graph G.

A.3.2 The Shape of the Spanning Tree

Remember that our general strategy to prove differential privacy results is to find a spanning tree in G H and then to compute the norm of the vector t ∆ that will "spread" the difference between X A and X B over all vertices (so as to get a σ η of the same order as in the trusted curator setting). Here, we will first define the shape of a rooted tree and then prove that with high probability this tree is isomorphic to a spanning tree of G H . Of course, we make a crude approximation here, as in the (unlikely) case that our predefined tree cannot be embedded in G H it is still possible that other trees could be embedded in G H and would yield similarly good differentially privacy guarantees. While our bound on the risk that our privacy guarantee does not hold will not be tight, we will focus on proving our result for reasonably-sized U and k, and on obtaining interesting bounds on the norm of t ∆ .

Let G H = ([n H ], E H ) be a random graph where between every pair of vertices there is an edge with probability 2k H /n H . The average degree of G H is 2k H .

Let k H ≥ 4. Let q ≥ 3 be an integer. Let ∆ 1 , ∆ 2 . . . ∆ q be a sequence of positive integers such that

  q i=1 i j=1 ∆ j   -(∆ q + 1) q-2 j=1 ∆ j < n H ≤ q i=1 i j=1 ∆ j . (23)
Let T = ([n H ], E T ) be a balanced rooted tree with n H vertices, constructed as follows. First, we define for each level l a variable z l representing the number of vertices at that level, and a variable Z l representing the total number of vertices in that and previous levels. In particular: at the root

Z -1 = 0, Z 0 = z 0 = 1 and for l ∈ [q -2] by induction z l = z l-1 ∆ l and Z l = Z l-1 + z l . Then, z q-1 = (n H -Z q-2 )/(∆ q + 1) , Z q-1 = Z q-2 + z q-1 , z q = n H -Z q-1 and Z q = n H . Next,
we define the set of edges of T :

E T = {{Z l-2 + i, Z l-1 + z l-1 j + i} | l ∈ [q] ∧ i ∈ [z l-1 ] ∧ z l-1 j + i ∈ [z l ]}.
So the tree consists of three parts: in the first q -2 levels, every vertex has a fixed, level-dependent number of children, the last level is organized such that a maximum of parents has ∆ q children, and in level q -1 parent nodes have in general ∆ q-1 -1 or ∆ q-1 children. Moreover, for 0 ≤ l ≤ q -2, the difference between the number of vertices in the subtrees rooted by two vertices in level l is at most ∆ q + 2. We also define the set of children of a vertex, i.e., for l ∈ [q] and i

∈ [z i-1 ], ch(Z l-2 + i) = {Z l-1 + z l-1 j + i | z l-1 j + i ∈ [z l ]}.
In Section A.3.3, we will show conditions on n H , ∆, k H and δ such that for a random graph G H on n H vertices and a vertex v 1 of G H , with high probability (at least 1 -δ) G H contains a subgraph isomorphic to T whose root is at v 1 .

A.3.3 Random Graphs Almost Surely Embed a Balanced Spanning Tree

The results below are inspired by [START_REF] Krivelevich | Embedding spanning trees in random graphs[END_REF]. We specialize this result to our specific problem, obtaining proofs which are also valid for graphs smaller than 10 10 vertices, even if the bounds get slightly weaker when we drop terms of order O(log(log(n H ))) for the simplicity of our derivation.

Let F be the subgraph of T induced by all its non-leafs, i.e., F = ([

n H /∆ ], E F ) with E F = {{i, j} ∈ E T | i, j ≤ Z q-1 }.
Lemma 2. Let G H and F be defined as above. Let v 1 be a vertex of

G H . Let n H ≥ k H ≥ ∆ ≥ 3. Let γ = max q-1 l=1 ∆ l /k H and let γ + 4(∆ + 2) -1 + 2n -1 H ≤ 1. Let k H ≥ 4 log(2n H /δ F (∆ q + 2)
). Then, with probability at least 1 -δ F , there is an isomorphism φ from F to a subgraph of G H , mapping the root 1 of F on v 1 .

Proof. We will construct φ by selecting images for the children of vertices of F in increasing order, i.e., we first select φ(1) = v 1 , then map children {2 . . . ∆ 1 + 1} of 1 to vertices adjacent to v 1 , then map all children of 2 to vertices adjacent to φ(2), etc. Suppose we are processing level l ∈ [q -1] and have selected φ(j) for all j ∈ ch(i ) for all i < i for some Z l-1 < i ≤ Z l . We now need to select images for the ∆ l children j ∈ ch(i) of vertex i (or in case l = q -1 possibly only ∆ l -1 children). This means we need to find ∆ l neighbors of i not already assigned as image to another vertex (i.e., not belonging to ∪ 0≤i <i φ(ch(i ))). We compute the probability that this fails. For any vertex j ∈ [n H ] with i = j, the probability that there is an edge between i and j in G H is 2k H /n H . Therefore, the probability that we fail to find ∆ l free neighbors of i can be upper bounded as

P r [FAIL F (i)] = P r Bin n H -Z l , 2k H n H < ∆ l ≤ exp    -(n H -Z l ) 2k H n H -∆ l 2 2(n H -Z l ) 2k H n H    . ( 24
)
We know that n H -Z l ≥ z q . Moreover, (z q + ∆ q -1)/∆ q ≥ z q-1 and Z q-2 + 1 ≤ z q-1 , hence 2(z q + ∆ q -1)/∆ q ≥ Z q-2 + Z q-1 + 1 = Z q-1 + 1 and 2(z q + ∆ q -1)/∆ q + z q ≥ n H + 1.

There follows

z q (2 + ∆ q ) ≥ n H + 1 -2(∆ q -1)/∆ q ≥ n H -1.
Therefore,

n H -Z l ≥ z q ≥ n H (1 -2(∆ q + 2) -1 -n -1 H ). (25)
Substituting this and ∆ l ≥ γk H in Equation ( 24), we get

P r [FAIL F (i)] ≤ exp    -n H (1 -2(∆ q + 2) -1 -n -1 H ) 2k H n H -k H γ 2 2n H (1 -2(∆ q + 2) -1 -n -1 H ) 2k H n H    ≤ exp -k 2 H 2(1 -2(∆ q + 2) -1 -n -1 H ) -γ 2 4k H ≤ exp -k 2 H 4k H = exp -k H 4 ,
where the latter inequality holds as γ + 4(∆ + 2)

-1 + 2n -1 H ≤ 1. As k H ≥ 4 log(2n H /δ F (∆ q + 2)) we can conclude that P r [FAIL F (i)] ≤ δ(∆ q + 2) 2n H .
The total probability of failure to embed F in G H is therefore given by

Zq-1 i=2 FAIL F (i) ≤ (Z q-1 -1) δ F (∆ q + 2) 2n H ≤ n H (2(∆ q + 2) -1 + n -1 H ) -1 δ F (∆ q + 2) 2n H = 2n H ∆ q + 2 δ F (∆ q + 2) 2n H = δ F ,
where we again applied [START_REF] Cheu | Distributed Differential Privacy via Shuffling[END_REF]. Now that we can embed F in G H , we still need to embed the leaves of T . Before doing so, we review a result on matchings in random graphs. The next lemma mostly follows [13, Theorem 7.11], we mainly adapt to our notation, introduce a confidence parameter and make a few less crude approximations. 2Lemma 3. Let m ≥ 27 (in our construction, m = z q ) and ζ ≥ 4. Consider a random bipartite graph with vertex partitions A = {a 1 . . . a m } and B = {b 1 . . . b m }, where for every i, j ∈ [m] the probability of an edge {a i , b j } is p = ζ(log(m))/m. Then, the probability of a complete matching between A and B is higher then

1 - em -2(ζ-1)/3 1 -m -(ζ-1)/3 .
Proof. For a set X of vertices, let Γ(X) be the set of all vertices adjacent to at least one member of X. Then, if there is no complete matching between A and B, there is some set X, with either X ⊂ A or X ⊂ B, which violates Hall's condition, i.e., |Γ(X)| < |X|. Let X be the smallest set satisfying this property (so the subgraph induced by X ∪ Γ(X) is connected). The probability that such sets X and Γ(X) of respective sizes i and j = |Γ(X)| exist is upper bounded by appropriately combining:

• the number of choices for X, i.e., 2 (for selecting A or B) times m i ,

• the number of choices for Γ(X), i.e., m i -1 ,

• an upper bound for the probability that under these choices of X and Γ(X) there are at least 2i -2 edges (as the subgraph induced by X ∪ Γ(X) is connected), i.e., ij i + j -1 possible choices of the vertex pairs and p i+j-1 the probability that these vertex pairs all form edges, and

• the probability that there is no edge between any of X ∪ Γ(X) and the other vertices, i.e., (1 -p) i(m-j)+j(m-i) = (1 -p) m(i+j)-2ij .

Thus, we upper bound the probability of observing such sets X and Γ(X) of sizes i and j as follows:

FAIL B (i, j) ≤ m i m j ij i + j -1 p i+j-1 (1 -p) m(i+j)-2ij ≤ me i i me j j ije i + j -1 i+j-1 p i+j-1 (1 -p) m(i+j)-2ij .
Here, in the second line the classic upper bound for combinations is used:

m i < me i i . As 2j ≤ i + j -1, we get FAIL B (i, j) ≤ me i i me j j ie 2 i+j-1 p i+j-1 (1 -p) m(i+j)-2ij ≤ m i+j e 2i+2j-1 i j-1 j j 2 i+j-1 p i+j-1 (1 -p) m(i+j)-2ij . (26)
As 0 < p < 1, there also holds (1 -p) 1/p < 1/e, and therefore

(1 -p) m(i+j)-2ij = (1 -p) 1 p p(m(i+j)-2ij) < (1/e) p(m(i+j)-2ij) .
We can substitute p = ζ(log(m))/m to obtain

(1 -p) m(i+j)-2ij < (1/e) (ζ(log(m))/m)(m(i+j)-2ij) = 1 m ζ(m(i+j)-2ij)/m
. Substituting this and p < ζ log(m)/m into Equation ( 26), we get

FAIL B (i, j) ≤ m i+j e 2i+2j-1 i j-1 j j 2 i+j-1 log(m)ζ m i+j-1 1 m ζ(m(i+j)-2ij)/m = mei j-1 j j log(m)ζe 2 2 i+j-1 1 m ζ((i+j)-2ij/m) . As j < i < m/2, 2 ≤ i < (i + j) -2ij/m < i + j, there follows FAIL B (i, j) ≤ mei j-1 j j log(m)ζe 2 2 i+j-1 1 m ζ((i+j)-2ij/m)
.

Given that m ζ/3 ≥ ζ log(m)e 2 /2 holds for m ≥ 27 and ζ ≥ 4, we get

FAIL B (i, j) ≤ mei j-1 j j log(m)ζe 2 2m 1/3 i+j-1 m -ζ((i+j)-2ij/m)+ζ(i+j-1)/3 ≤ ei j-1 j j m -ζ( 2 3 (i+j)+1/3-2ij/m)+1 ≤ ei j-1 j j m -ζ( 1 3 i+ 1 3 )+1 . 20 As ζ ≥ 4, this implies FAIL B (i, j) ≤ e i i j j m -ζi 3 -1 3 (27)
There holds:

i-1 j=1 i j j = i/3 j=1 i j j + i j= i/3 +1 i j j ≤ i/3 j=1 i j j + i j= i/3 +1 3 j = i/3 j=1 i j j + 3 i/3 +1 3 i-i/3 -1 3 -1 < i/3 j=1 i j j + 3 i+1 2 < i/3 j=1 i i/3 + 3 i+1 2 ≤ i 3 i i/3 + 3 i+1 2 .
Substituting in Equation [START_REF] Cramer | Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[END_REF] gives

FAIL B = m/2 i=2 i-1 j=1 FAIL B (i, j) < m/2 i=2 i-1 j=1 e i i j j m -ζi 3 -1 3 < m/2 i=2 i i/3+1 3 + 3 i+1 2 e i m -ζi 3 -1 3 < m/2 i=2 i i/3 + 3 i+1 e 2 m -ζi 3 -1 3 < m/2 i=2 i i/3 m -ζi 3 -1 3 + 3 i+1 e 2 m -ζi 3 -1 3 .
As m ≥ 27 = 3 3 we can now write

FAIL B < e 2 m/2 i=2 m -(ζ-1)i 3 -1 3 + m (i+1)/3 m -ζi 3 -1 3 < e 2 m/2 i=2 m -(ζ-1)i 3 -1 3 + m -(ζ-1)i 3 < e m/2 i=2 m -(ζ-1)i 3 = em -2(ζ-1) 3 m/2-2 i=0 m -ζ-1 3 i = em -2(ζ-1) 3 1 -m -ζ-1 3 m/2-1 1 -m -ζ-1 3 < em -2(ζ-1) 3 1 1 -m -ζ-1 3 .
This concludes the proof. Consider a random bipartite graph as described in Lemma 3 above. Then, with probability at least 1 -δ B there is a complete matching between A and B.

Proof. From the given ζ, we can infer that

ζ -1 ≥ 3 log(2e/δ B ) 2 log(m) ζ -1 ≥ -3 log(δ B /2e) 2 log(m) -2 3 (ζ -1) log(m) ≤ log (δ B /2e) m -2(ζ-1)/3 ≤ δ B /2e
We also know that ζ ≥ 4 and m ≥ 27, hence (ζ -1)/3 ≥ 1 and 1 -m -(ζ-1)/3 ≥ 26/27 ≥ 1/2. We know from Lemma 3 that the probability of having a complete matching is at least

1 - em -2(ζ-1)/3 1 -m -(ζ-1)/3 ≥ 1 - e(δ B /2e) 1/2 = 1 -δ B .
Lemma 5. Let δ B > 0, ∆ ≥ 1 (in our construction, ∆ = ∆ q ) and m ≥ 27. Let d 1 . . . d l be positive numbers, with

d i = ∆ for i ∈ [l -1], d l ∈ [∆] and l i=1 d i = m. Let A = {a 1 .
. . a l } and B = {b 1 . . . b m } be disjoint sets of vertices in a random graph G H where the probability to have an edge {a i , b j } is 2k H /n H for any i and j. Let

p ≥ 1 -1 -max 4, 1 + 3 log(2e/δ B ) 2 log(m) log(m) m ∆ . ( 28
)
Then with probability at least 1 -δ B , G H contains a collection of disjoint d i -stars centers a i and leaves in B.

Proof. Define an auxiliary random bipartite graph G with sides A = {a 1 . . . a m and B = {b 1 . . . b m . For every i, j ∈ [m], the probability of having an edge between a i and b j in

G is p = 1 -(1 -p) 1/∆ .
We relate the distributions on the edges of G H and G by requiring there is an edge between a i and b j if and only if there is an edge between a ∆(i-1)+i and b j for all i ∈ [∆].

From Equation ( 28) we can derive

p ≥ max 4, 1 + 3 log(2e/δ B ) 2 log(m) log(m) m . (29)
Setting

ζ = max 4, 1 + 3 log(2e/δ B ) 2 log(m) ,
this ensures p satisfies the constraints of Lemma 4:

p = ζ log(m)/m.
As a result, there is a complete matching in G with probability at least 1 -δ B , and hence the required stars can be found in G H with probability at least 1 -δ B .

Lemma 6. Let δ F > 0 and δ B > 0. Let G H and T and their associated variables be as defined above. Assume that the following conditions are satisfied:

(a) n H ≥ 27(∆ q + 2)/∆ q , (b) γ + 2(∆ q + 2) -1 + n -1 H ≤ 1, (c) k H ≥ 4 log(2n H /δ F (∆ q + 2)), (d) k H ≥ max 4, 1 + 3 log(2e/δ B ) 2 log(n H ∆ q /(∆ q + 2)) ∆ q + 2 2 log n H ∆ q ∆ q + 2 , (e) γ = max q-1 l=1 ∆ l /k H .
Let G H be a random graph where there is an edge between any two vertices with probability p. Let v 1 be a vertex of G H . Then, with probability at least 1 -δ F -δ B , there is a subgraph isomorphism between the tree T defined above and G H such that the root of T is mapped on v 1 .

Proof. The conditions of Lemma 2 are clearly satisfied, so with probability 1 -δ F there is a tree isomorphic to F in G H . Then, from condition (d) above and knowing that the edge probability is p = 2k H /n H , we obtain

p ≥ max 4, 1 + 3 log(2e/δ B ) 2 log(n H ∆ q /(∆ q + 2)) 1 n H ∆ q /(∆ q + 2) log n H ∆ q ∆ q + 2 ∆ q .
Taking into account that m = n H ∆ q /(∆ q + 2), we get

p ≥ max 4, 1 + 3 log(2e/δ B ) 2 log(m) 1 m log (m) ∆ q ,
which implies the condition on p in Lemma 4. The other conditions of that lemma can be easily verified. As a result, with probability at least 1 -δ B there is a set of stars in G H linking the leaves of F to the leaves of T , so we can embed T completely in G H .

A.3.4 Running GOPA on Random Graphs

Assume we run GOPA on a random graph satisfying the properties above, what can we say about the differential privacy guarantees? According to Lemma 1, it is sufficient that there exists a spanning tree and vectors t η and t ∆ such that t η + Kt ∆ = X A -X B . We fix t η in the same way as for the other discussed topologies (see Section A.2) in order to achieve the desired σ η and focus our attention on t ∆ . According to Lemma 6, with high probability there exists in G H a spanning tree rooted at the vertex where X A and X B differ and a branching factor ∆ l specified per level. So given a random graph on n H vertices with edge density 2k H /n H , if the conditions of Lemma 6 are satisfied we can find such a tree isomorphic to T in the communication graph between honest users G H . In many cases (reasonably large n H and k H ), this means that the lemma guarantees a spanning tree with branching factor as high as O(k H ), even though it may be desirable to select a small value for the branching factor of the last level in order to more easily satisfy condition (d) of Lemma 6, e.g., ∆ q = 2 or even ∆ q = 1.

Lemma 7. Under the conditions described above,

t ∆ t ∆ ≤ 1 ∆ 1 1 + 1 ∆ 2 1 + | ∆ 3 . . . 1 ∆ q + (∆ q + 2)(∆ q + 2 + 2q) n H (30)
≤ 1 ∆ 1 1 + 2 ∆ 2 + O(n -1 H ).
Proof. Let q be the depth of the tree T . The tree is balanced, so in every node the number of vertices in the subtrees of its children differs at most ∆ q + 2. For edges e incident with the root (a level 0 node), |t e -∆ -1 1 | ≤ n -1 H (∆ q +2). In general, for a node at level l (except leaves or parents of leaves), there are l i=1 ∆ i vertices, each of which have ∆ l+1 children, and for every edge e connecting such a node with a child,

t e - l+1 i=1 ∆ -1 i ≤ (∆ q + 2)/n H .
For a complete tree (of 1 + ∆ + . . . + ∆ q vertices), we would have

t ∆ t ∆ = q l=1 l i=1 ∆ i l i=1 ∆ -1 i 2 = q l=1 l i=1 ∆ i -1
, which corresponds to the first term in Equation [START_REF] John C Duchi | Local privacy and statistical minimax rates[END_REF]. As the tree may not be complete, i.e., there may be less than q i=1 ∆ i leaves, we analyze how much off the above estimate is. For an edge e connecting a vertex of level l with one of its children,

t e - l+1 i=1 ∆ i ≤ (∆ q + 2)/n H ,
and hence

t 2 e - l+1 i=1 ∆ i 2 ≤ t 2 e -t e l+1 i=1 ∆ i +   t e l+1 i=1 ∆ i - l+1 i=1 ∆ i 2   ≤ t e (∆ q + 2)/n H + l+1 i=1 ∆ i (∆ q + 2)/n H ≤ ( l+1 i=1 ∆ i + n -1 H )(∆ q + 2)n H + l+1 i=1 ∆ i (∆ q + 2)/n H = (∆ q + 2) 2 /n 2 H + 2 l+1 i=1 ∆ i (∆ q + 2)/n H .
Summing over all edges gives

t ∆ t ∆ - q l=1 l i=1 ∆ i -1 ≤ q l=1 z l   (∆ q + 2)/n 2 H + 2 l+1 i=1 ∆ i -1 (∆ q + 2)/n H   = (∆ q + 2) 2 /n H + q l=1 2z l l+1 i=1 ∆ i -1 (∆ q + 2)/n H ≤ (∆ q + 2) 2 /n H + q l=1 2(∆ q + 2)/n H = (∆ q + 2)(∆ q + 2 + 2q) n H .
So if we choose parameters ∆ for the tree T , the above lemmas provide a value δ such that T can be embedded in G H with probability at least 1 -δ and an upper bound for t ∆ t ∆ that can be obtained with the resulting spanning tree in G H .

Theorem 3 in the main text summarizes these results, simplifying the conditions by assuming that ∆ i = (k -1)ρ/2 for i ≤ q -1 and ∆ q = 2.

Proof of Theorem 3. Let us choose ∆ i = (k -1)ρ/3 for i ∈ [q -1] and ∆ q = 1 for some appropriate q such that Equation ( 23) is satisfied. We also set

δ = δ F = δ B .
Then, the conditions of Lemma 6 are satisfied. In particular, condition (a) holds as n H = ρn ≥ 81 = 27(∆ q + 2)/∆ q . Condition (e) implies that

γ = q-1 max i=1 ∆ i /k H = 1 k H (k -1)ρ 3 .
Condition (b) holds as

γ + 2(∆ q + 2) -1 + n -1 H = 1 k H (k -1)ρ 3 + 2 3 + n -1 H ≤ 1 k H (k -1)ρ 3 + 2 3 + n -1 H ≤ 1 3 - ρ 3k H + 2 3 + n -1 H = 1 3 - 1 3k + 2 3 + n -1 H ≤ 1 3 - 1 n H + 2 3 + n -1 H = 1.
Condition (d) holds because we know that ρk ≥ 6 log(ρn/3), which is equivalent to

k H ≥ 4 ∆ + 2 ∆ log n H ∆ q ∆ q + 2 ,
and we know that ρk ≥ 3 2 + 9 4 log(2e/δ), which is equivalent to

k H ≥ 1 + 3 log(2e/δ B ) 2 log(n H ∆ q /(∆ q + 2)) ∆ + 2 ∆ log n H ∆ q ∆ q + 2 .
Finally, condition (c) is satisfied as we know that ρk ≥ 4 log(ρn/3δ). Therefore, applying the lemma, we can with probability at least 1 -2δ find a spanning tree isomorphic to T . If we find one, Lemma 7 implies that

t ∆ t ∆ ≤ q l=1 l i=1 ∆ i -1 + (∆ q + 2)(∆ q + 2 + 2q) n H = q-1 l=1 ∆ -l 1 + ∆ 1-q 1 ∆ -1 q + 3(3 + 2q) n H = ∆ -1 1 1 -∆ 1-q 1 1 -∆ -1 1 + ∆ 1-q 1 ∆ -1 q + 9 + 6q n H ≤ 1 ∆ 1 -1 + 3 n H + 9 + 6q n H = 1 (k -1)ρ/3 -1 + 12 + 6q n H = 1 (k -1)ρ/3 -1 + 12 + 6 log(n H ) n H
This implies the conditions related to σ ∆ and t ∆ are satisfied. From Lemma 1, it follows that with probability 1 -2δ GOPA is ( , δ)-differentially private, or in short GOPA is ( , 3δ)-differentially private.

A.4 Matching the Utility of the Centralized Gaussian Mechanism

From the above theorems, we can now obtain a simple corollary which precisely quantifies the amount of independent and pairwise noise needed to achieve a desired privacy guarantee depending on the topology.

Proof of Corollary 1. In the centralized (trusted curator) setting, the standard centralized Gaussian mechanism [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF] (Theorem A.1 therein) states that in order for the noisy average ( 1 n u∈U X u ) + η to be (ε , δ )-DP for some ε , δ ∈ (0, 1), the variance of η needs to be:

σ 2 gm = c 2 (ε n) 2 . ( 31
)
where c 2 > 2 log(1.25/δ ).

Based on this, we let the independent noise η u added by each user in GOPA to have variance

σ 2 η = n 2 n H σ 2 gm = c 2 (ε ) 2 n H , (32)
which, for the approximate average Xavg , gives a total variance of:

V ar 1 n H u∈U H η u = 1 n 2 H n H σ 2 η = c 2 (ε n H ) 2 . ( 33
)
We can see that when n H = n (no malicious user), Equation ( 33) exactly corresponds to the variance required by the centralized Gaussian mechanism in Equation ( 31), hence GOPA will achieve the same utility. When there are malicious users, each honest user needs to add a factor n/n H more noise to compensate for the fact that malicious users can subtract their own inputs and independent noise terms from Xavg . This is consistent with previous work on distributed noise generation under malicious parties [START_REF] Shi | Privacy-Preserving Aggregation of Time-Series Data[END_REF].

Now, given some κ > 0, let σ 2 ∆ = κσ 2 η if G is the complete graph, σ 2 ∆ = 1 (k-1)ρ/3 -1 + (12 + 6 log(n H ))
/n H for the random k-out graph, and σ 2 ∆ = κn 2 H σ 2 η /3 for an arbitrary connected G H . In all cases, the value of θ in Theorems 1, 2 and 3 after plugging

σ 2 ∆ gives θ = ε 2 c 2 + ε 2 κc 2 = (κ + 1)ε 2 κc 2 . n = 100 ρ = 1 k = 3 σ ∆ =
ε ≥ (κ + 1)ε 2 2κc 2 + (κ + 1) κ ε c
For d 2 = κ κ+1 c 2 we can rewrite the above as

ε ≥ ε 2 2d 2 + ε d .
Since ≤ 1, this is satisfied if d -ε 2d ≥ 1 and in turn when d ≥ 3/2, or equivalently when c ≥ 3 2 κ+1 κ . Now analyzing the inequality in Equation ( 4) we have:

ε - (k + 1)ε 2 2κc 2 2 ≥ 2 log(2/δ √ 2π) ε 2 c 2 + ε 2 κc 2 ε 2 + (κ + 1) 2 ε 4 4κ 2 c 4 - (κ + 1)ε 3 κc 2 ≥ 2 log(2/δ √ 2π) (κ + 1)ε 2 κc 2 1 2 κc 2 κ + 1 + (κ + 1)ε 2 4κc 2 -ε ≥ log(2/δ √ 2π).
Again denoting d 2 = κ κ+1 c 2 we can rewrite the above as

1 2 d 2 + ε 2 4d 2 -ε ≥ log(2/δ √ 2π).
For d ≥ 3/2 and ε ≤ 1, the derivative of

d 2 + ε 2 4d 2 -ε is positive, so d 2 + ε 2 4d 2 -ε > d 2 -8/9
. Thus, we only require d 2 ≥ 2 log(1.25/δ). Therefore Equation ( 4) is satisfied when:

κ κ + 1 log(1.25/δ ) ≥ log(1.25/δ),
which is equivalent to

δ ≥ 1.25 δ 1.25 κ κ+1 .
The constant 3.75 instead of 1.25 for the random k-out graph case is because Theorem 3 guarantees ( , 3δ)-DP instead of ( , δ) in Theorems 1 and 2.

A.5 Smaller k and σ 2 ∆ via Numerical Simulation

For random k-out graphs, the conditions on k and σ 2 ∆ given by Theorem 3 are quite conservative. While we are confident that they can be refined by resorting to tighter approximations in our analysis in Section A.3, an alternative option to find smaller, yet admissible values for k and σ 2 ∆ is to resort to numerical simulation. and independently at random from G a pair of elements g and h which form the set of parameters Θ = (g, h) of the scheme. Additionally, M Θ = R Θ = Z q , and C Θ = G. We will refer to g and h as bases. The commitment function Com Θ is defined as

Com Θ : Z q × Z q → G Com Θ (x, r) = g x • h r , (34)
where (•) is the modular product of group G, x is the secret and r is the randomness. Pedersen commitments are homomorphic (in particular,

Com Θ (x + y, r + s) = Com Θ (x, r) • Com Θ (y, s)),
unconditionally hiding, and computationally binding under the Discrete Logarithm Assumption, which we informally describe below. Assumption 1 (Discrete Logarithm Assumption). Let G be a cyclic multiplicative group of large prime order q, and g and h two elements chosen independently and uniformly at random from G. Then, there exists no probabilistic polynomial time algorithm A that takes as input the tuple (G, q, g, h) and outputs a value b such that P (g b = h) is significant on the bit-size of q.

The DLA is a standard assumption widely used in production environments. A more detailed description can be found in Chapter 7 of [START_REF] Katz | Introduction to Modern Cryptography[END_REF].

The Pedersen commitment scheme can be efficiently implemented with elliptic curves, as described and benchmarked in [START_REF] Franck | Efficient Implementation of Pedersen Commitments Using Twisted Edwards Curves[END_REF]. To generate a common Pedersen scheme in our adversary model, the generation of the unbiased random input t for Setup can be done as described in Section 4.4 of [START_REF] Bünz | Bulletproofs: Short Proofs for Confidential Transactions and More[END_REF]. We provide a concrete method for this in Appendix C.

B.2 Zero Knowledge Proofs

On top of Pedersen commitments, we use a family of techniques called Zero Knowledge Proofs (ZKPs), first proposed by [START_REF] Goldwasser | The Knowledge Complexity of Interactive Proof Systems[END_REF]. In these proofs, a party P called the Prover, convinces another party V , the Verifier, about a statement. For our scope and informally speaking, ZKPs3

• allow every P to successfully prove true a statement (completeness),

• allow every V to discover with arbitrarily large probability any attempt to prove a false statement (soundness), • guarantee that by performing the proof, no information about the knowledge of P other than the proven statement is revealed (zero knowledge).

Importantly, the zero knowledge property of our proofs does not rely on any computational hardness assumption.

Honest-verifier interactive ZKPs. In the following sections, we describe how our ZKPs can be be performed as an interactive protocol between a Prover P and a honest Verifier V whose only task in the conversation is to generate unbiased random numbers, that we will call challenges, and which P must not be able to predict. In these proofs, the zero knowledge property holds only if V is honest and does not try to generate biased challenges in order to guess private values of P . Such model does not apply to our malicious adversary model. However, this can be easily overcome in most cases with a generic transformation of the proofs that makes them suitable in adversarial settings, called the Fiat-Shamir heuristic, which we describe at the end of Appendix B.3. Additionally, for a particular case of a proof in the beginning of Appendix B.3 which, as we will see, cannot be made non-interactive, we provide an efficient interactive method to generate unbiased challenges as an honest verifier would do in Appendix C.

B.2.1 Zero Knowledge Proofs: Building Blocks

We now briefly review a number of ZKP building blocks present in literature and necessary for our verification protocol. We illustrate the basic principles for a selection of relevant ZKPs, describing their protocol and complexity, and refer to the literature for others.

where P proves that x ∈ [0, 2 l -1] and that M -x ∈ [0, 2 l -1] (this involves another commitment for M -x and a linear proof of this relation) for l = log 2 M + 1. We denote the proof by

ZKPRange(c x , [0, M ]) (x, r) : c x = g x h r ∧ x ∈ [0, M ] .
It has a computational cost of O(log 2 M ) exponentiations for both P and V and a proof size of O(log 2 log 2 M ). With this proof, the verification of Property ( 8) can be done.

The verification of Property ( 7) is more elaborate as it involves proving that a value has been drawn from a prescribed statistical distribution. We describe this proof in Appendix B.3, but first introduce additional building blocks that will be needed for this proof.

Proof of product. In this proof, P wants to prove that for three secrets a, b, d committed in

c a = g a h r1 , c b = g b h r2 and c d = g d h r3
, it holds that ab = d (mod q). This proof can be done in a straightforward way based on ZKPEq. We use the fact that, by properties of cyclic groups, c a is not only a commitment but also a base of G, and that c d = (c a ) b h (r2-bra) , which is a valid commitment for b using bases (c a , h). Then we use ZKPEq(c b , c d ) with the pairs of bases (g, h) and (c a , h). If P does not know the commitment of a product of ab hidden in c d it would not pass the proof. We denote this proof as

ZKPProd(c a , c b , c d ) (a, r 1 , b, r 2 , d, r 3 ) : c a = g a h r1 ∧ c b = g b h r2 ∧ c d = g d h r3 ∧ ab = d (mod q) .
The proof, first proposed in [START_REF] Fujisaki | Statistical zero knowledge protocols to prove modular polynomial relations[END_REF], has the same complexity as ZKPEq plus the computation of an extra commitment (2 exponentiations).

Proof of OR-composition. This proof provides the possibility of constructing a ZKP on a statement that is the disjunction of statements of other (already constructed) ZKPs. Concretely, given the proofs

ZKP 1 {(v) : S 1 (v)}, and ZKP 2 {(v) : S 2 (v)}
where v is a vector of private values and S 1 and S 2 are the verifiable statements, one can construct the proof

ZKPOr (v) : S 1 (v) ∨ S 2 (v) .
The proof is described in [START_REF] Cramer | Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[END_REF] and [START_REF] De Santis | On monotone formula closure of SZK[END_REF]. The complexity of ZKPOr is the sum of the complexities of ZKP 1 and ZKP 2 . Not exclusively but often, we will use the construction to prove that a secret b is a bit, i.e. that b ∈ {0, 1}. The instantiation is described in [START_REF] Mao | Guaranteed correct sharing of integer factorization with off-line shareholders[END_REF](pages 66-67 therein) and requires O(1) computations for P and V and as well as O(1) proof size complexity.

Proof of modular sum. Here, P wants to prove that, for a public modulus M < q/2, a public value t ∈ [0, M -1] and two secrets x, z ∈ [0, M -1], the relation x = z + t mod M is satisfied. Let c x and c z be the commitments of x and z respectively. For the proof, we perform ZKPRange(c x , [0, M -1]), ZKPRange(c z , [0, M -1]), and we use an auxiliary commitment of a bit b which we prove to be in {0, 1}. Then, we prove the arithmetic relation x = z + t -bM (mod q) with ZKPLinear. Because of their range, we have that z + t < q, hence the modulus q does not interfere and the linear equality holds if and only if the modular sum is satisfied. We denote this proof as

ZKPMod(c x , c z , M, t) (x, r 1 , z, r 2 ) : c x = g x h r1 ∧ x ∈ [0, M -1] ∧ c z = g z h r2 ∧ z ∈ [0, M -1] ∧ x = z + t mod M .
This proof is inspired by the more general proof of modular sum proposed in [START_REF] Camenisch | Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes[END_REF]. Its complexity is given by the composition of the proofs mentioned above, where the dominant term is in the range proofs, and amounts to O(log 2 M ) exponentiations in the computation by both P and V , and O(log 2 log 2 M ) in the published proof size.

Non-interactive ZKPs.

There is a standard method to transform honest verifier interactive ZKPs into a non-interactive protocol through the widely used Fiat-Shamir heuristic [START_REF] Fiat | How To Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF]. Roughly speaking, the method replaces the interactive role of a verifier V by a cryptographic hash function (in theory, a random oracle) which generates our publicly verifiable challenges. Using this heuristic, P can compute the proof by itself without compromising the soundness property, and publish it in the bulletin board. The complexity of generating and verifying the proof is not changed by the transformation, and the proof is established by the fictional interactive conversation between P and V . Once P has published the proof in the bulletin board, any party can check its correctness.

B.3 Zero Knowledge Proofs for Uniform and Gaussian Random Variables

Given the building blocks in Appendix B.2, we can construct a proof that a random variable follows a uniform or a Gaussian distribution.

Proof of uniform distribution. We prove that a secret random variable y is uniformly distributed over the interval [0, M -1] for M < q/2. As we are not proving any statement for a particular fixed value but of a distribution, it is intuitive that we sample the value while the proof is generated. Essentially, we use ZKPMod(c y , c z , M, t), and provide a protocol such that t guarantees the distribution is not biased and z guarantees the secrecy of y. By the properties of modular sum, we can ensure that y is uniformly distributed. The secure proof goes as follows:

1. P draws z ← R [0, M -1], computes c z = g z h r for some r ← R Z q and sends c z to V . 2. V draws t ← R [0, M -1] (as described in Appendix C) and sends it to P .

3. P computes y ← z + t mod M and c y ← g y h r for some r ← R Z q , and sends c y to V .

After this, P and V perform ZKPMod as mentioned above. We denote this proof as

ZKPUniform(c y , [0, M -1]) (y, r ) : c y = g y h r ∧ y ∼ U([0, M -1]) .
The complexity of ZKPUniform remains of the same order as ZKPMod, i.e. O(log 2 M ) computation and O(log 2 log 2 M ) in the published proof size.

Note that this proof cannot be made non-interactive, as a malicious user can sample locally many random values and pick the one he likes, biasing the distribution. We need to make sure all users generate uniformly distributed numbers in the first attempt and do not have possibility to pick and reject numbers as they see fit. We provide in Appendix C a decentralized method to generate unbiased random challenges, which makes the proving user to "commit" to every generation of a random number. This approach only requires O(1) additional computations and communication cost per user, so the complexity of ZKPUniform remains of the same order.

Proof of Gaussian distribution. In our algorithm, every user u needs to generate a Gaussian distributed number η u , which he does not publish, but for which we need to verify that it is generated correctly, as otherwise a malicious user could bias the result of the algorithm.

Proving the generation of a Gaussian distributed random number is more involved. We will start from an integer y , which is only known to a party P , for which P has published a commitment Com Θ (y ) and for which the other agents know it has been generated uniformly randomly from an interval [0, M -1] (for large M ), as can be done with ZKPUniform. Then, P will compute x such that ((2y + 1)/M ) -1 = erf(x / √ 2). We know that x is normally distributed. The main task is then to provide a ZKP that y = erf(x) for y = ((2y + 1)/M ) -1 and x = x / √ 2.

The error function relates its input and output in a way that cannot be expressed with additive, multiplicative or exponential equations. We therefore approximate erf using a converging series. In particular, we will rely on the series

erf(x) = 2 √ π ∞ l=0 (-1) l x 2l+1 l!(2l + 1) . ( 35
)
As argued in [START_REF] Chevillard | Computation of the error function erf in arbitrary precision with correct rounding[END_REF], this series has two major advantages. First, it only involves additions and multiplications, while other known series converging to erf(x) often include factors such as exp(-x 2 /2) which would require additional evaluations and proofs. Second, it is an alternating series, which means we can determine more easily in advance how many terms we need to evaluate to achieve a given precision.

Nevertheless, Equation ( 35) converges slowly for large x. It is more efficient to prove either that y = erf(x) or 1 -y = erfc(x), as for erfc(x) = 1erf(x) there exist good approximations requiring only a few terms for large x.

An example is the asymptotic expansion

erfc(x) = e -x 2 x √ π S erfc (x) + R L (x), (36)
where

S erfc (x) = L-1 l=0 (-1) l (2l -1)!! (2x 2 ) l (37)
with l!! = 1 for l < 1 and (2l -1)!! = l i=1 (2i -1). This series diverges, but if x is sufficiently large then the remainder

R L (x) ≤ 2 √ π (2L -1)!! (2x 2 ) L (38)
after the first L terms is sufficiently small to be neglected. So the prover could prove either part of the disjunction with ZKPOr depending on whether the erf or erfc approximations achieve sufficient precision. In particular, for a fixed x, Equation ( 38) is minimal with L ≈ x 2 /2, so given x we can achieve an error of

E erfc (x) ≈ 2 √ π (2 x 2 /2 -1)!! (2x 2 ) x 2 /2 = 2 √ π (2 x 2 /2 )! x 2 /2 !2 x 2 /2 (2x 2 ) x 2 /2 ≈ 2 √ π (2 x 2 /2 /e) 2 x 2 /2 (2 x 2 /2 ) 1/2 ( x 2 /2 /e) x 2 /2 ( x 2 /2 ) 1/2 2 x 2 /2 (2x 2 ) x 2 /2 = 2 √ π ( x 2 /2 ) x 2 /2 2 1/2 e x 2 /2 (x 2 ) x 2 /2 ≤ √ 8 √ π(2e) x 2 /2 .
Approximating erfc(x) involves approximating exp(-x 2 ). The common series exp(z) = ∞ i=0 z i /i! is known to converge quickly. Even if its terms first go up until z < i, for larger z where this could slow down convergence one can simply divide z be a constant a (maybe conveniently a power of 2), approximate exp(z/a) and then compute (exp(z/a)) a , which can be done efficiently. We omit the details here and focus in the following on the more difficult erf function.

In absolute value, terms of the erf approximation never get larger than

(-1) l x 2l+1 l!(2l + 1) ≤ x 2 x 2 +1 x 2 !(2x 2 -1) ≈ x 2x 2 +1 √ 2πx 2 (x 2 /e) x 2 (2x 2 -1) = x √ 2πxe -x 2 (2x 2 -1) = e x 2 √ 2π(2x 2 -1) < e x 2 √ 8πx 2 (39)
Evaluating a term of one of the series (Equation [START_REF] Erlingsson | Rappor: Randomized aggregatable privacy-preserving ordinal response[END_REF] or Equation ( 37)) is possible by addition, multiplication and a division. We have described above building blocks for providing ZKPs of additions (ZKPLinear) and multiplications (ZKPProd). For the multiplication, please note that one can compute x l by x l = x l-1 x, reusing the result of earlier multiplications. For the division, proving that a/b = c, where a and c are private, is possible by proving that -|b|/2 ≤ a -bc ≤ |b|/2, which involves a range proof. The several range proofs for the several terms can be combined as indicated in the description of ZKPRange.

In the following, we will explicitly consider fixed precision representations. The implied rounding does not cause major problems for several reasons. First, the Gaussian distribution is symmetric, and hence the probability of rounding up and rounding down is exactly the same, making the rounding error a zero-mean random variable. Second, discrete approximations of the Gaussian mechanism such as binomial mechanisms have been studied and found to give similar guarantees as the Gaussian mechanism [START_REF] Agarwal | cpSGD: Communication-efficient and differentially-private distributed SGD[END_REF]. Third, we can require the cumulated rounding error to be an order of magnitude smaller than the standard deviation of the noise we are generating, so that any deviation due to rounding has negligible impact.

We will use a fixed precision for all numbers (except for small integer constants), and we will represent numbers as multiples of ψ. We assume 1/ψM to be an integer, so as the variable x is a multiple of 1/M , we can represent x and x 2 without rounding. Let

t i = x 2i+1 i! .
We can compute recursively

t i+1 = t i x 2 i + 1
, where t 0 = x. The multiplication with x 2 and the division by i increase the relative error by less than ψ. If we evaluate the first L terms of the series, the relative error due to rounding is thus at most Lψ. Combining this with Equation ( 39) implies that the maximal absolute error of a term is Lψe x 2 / √ 8πx 2 , and the total error after summing these terms is

E round erf = L 2 ψe x 2 √ 8πx 2 . (40)
Suppose we want to achieve an approximation where the error on y as a function of x is at most B. It is natural to set M ≈ 1/B. We require that the rounding error is at most B/2 and the approximation error is at most B/2. Then, if

B 2 ≥ √ 8 √ π(2e) x 2 /2 ≥ E erfc (x),
the prover will use the erfc series, else the erf series. As the erf series more strongly constrains our design choices, we will focus here on the erf case (the erfc case can be analyzed using the same principles). We hence assume that

√ 8 √ π(2e) x 2 /2 ≥ B 2 , which implies √ 32 B √ π ≥ (2e) x 2 /2 ,
The series in Equation ( 35) is an alternating series too, so to reach an error smaller than B/2, it is sufficient to truncate the series when terms get smaller than B/2 in absolute value. In particular, we need L terms with

2x 2L+1 √ πL!(2L + 1) ≤ B 2 .
Using Stirling's approximation, this means

2x 2L+1 √ π √ 2πL(L/e) L (2L + 1) ≤ B 2 .
Taking logarithms, we get:

log(2) + (2L + 1) log(x) -log(π √ 2) -(L + 1/2) log(l) -L + log(2L + 1) ≤ log(B) -log(2).
For L ≥ 1, it holds that l ≥ 2 log(2) + log(2L + 1) -log(π √ 2), so the above inequality is satisfied if

(2L + 1) log(x) -(L + 1/2) log(L) ≤ log(B),
which is equivalent to

(2L + 1) log(x/ √ L) ≤ log(B),
or, written differently:

(2L + 1) log 1 - √ L -x √ L ≤ log(B).
As log(1 + α) ≤ α, the above inequality is satisfied if

-(2L + 1) √ L -x √ L ≤ log(B).
Further approximating, this is satisfied if

2L √ L -x √ L + log(B) ≥ 0, or equivalently 2L -2 √ Lx + log(B) ≥ 0.
It follows that we need

√ L ≥ 2x + 4x 2 -8 log(B) 4 = x + x 2 -2 log(B) 2 .
Substituting the worst case value of x from Equation (41), we get

L ≥ 1
From Equation [START_REF] Fujisaki | Statistical zero knowledge protocols to prove modular polynomial relations[END_REF], we can now also determine what precision is needed. In particular:

E round erf = L 2 ψe x 2 √ 8πx 2 ≤ B 2 is satisfied if ψ ≤ √ 2πBx 2 L 2 e x 2 = O B 2 log(B)
.

Typically, one would like the total error (due to approximation and rounding) to be negligible with respect to the standard deviation σ η , so one could choose B = σ η /10 6 |U H |.

For any desired variance σ 2 , we denote the proof of Gaussian distribution by

ZKPNormal(c x , σ 2 ) (x, r) : c x = g x h r ∧ x ∼ N (0, σ 2 ) .
We • c Xu = Com Θ (X u , r Xu ) (before the execution of Algorithm 1)

3:

• c ∆u,v = Com Θ (∆ u,v , r ∆u,v ) (when exchanging with v ∈ N (u) during Algorithm 1)

4:

• c ηu = Com Θ (η u , r ηu ) (after generating η u ) 5:

• Xu (at the end of Algorithm 1)

6:

• ZKPLinear proofs for Properties ( 5) and (6)

7:

• ZKPNormal and ZKPRange proofs for Properties [START_REF] Elaine | Recommendation for random number generation using deterministic random bit generators (revised)[END_REF] and (8) 8: for all user u ∈ U do 9:

Verify that the value inside c Xu is in [0, 1] (if not, add u to the cheaters list) Verify that the value inside c ηu has distribution N (0, η u ) (if not, add u to cheaters list) 12: for all user v ∈ N (u) do Verify that values inside c ∆u,v and c ∆v,u sum to 0 (if not, add u and v to cheaters list) a term requires three multiplications, a division and a range proof. Evaluating a series hence requires O(log 2 (1/B)) multiplications, additions and range proofs. While the first two cost O(1), a range proof costs O(log 2 (2L + 1)) where 2L + 1 is the size of the range. In this case, L = O(log 2 (1/B)) so the cost is O(log 2 (log 2 (1/B))). In total, the cost of the ZKP for the correct computation of the series is therefore O(log 2 (1/B) log 2 (log 2 (1/B)). Depending on the value of x one of two series will be evaluated, and a disjunction of two relations proven with ZKPOr (which simply doubles the above cost). Regarding the proof size, the computation of erf or erfc (or the proof of its disjunction) has size O(log 2 (1/B) log 2 (log 2 (log 2 (1/B)))), as each of the range proofs performed has a size which is logarithmic in the complexity of its computation. The total proof size is therefore of O(log 2 (1/B) log 2 (log 2 (log 2 (1/B)))).

B.4 GOPA Verification Protocol

We design our verification protocol based on the ZKPs described in Appendices B.2 and B.3. Concretely, we rely on ZKPLinear to verify Properties ( 5) and ( 6), ZKPNormal to verify Property [START_REF] Elaine | Recommendation for random number generation using deterministic random bit generators (revised)[END_REF] and ZKPRange to verify Property [START_REF] Bell | Private Protocols for U-Statistics in the Local Model and Beyond[END_REF]. Note that Property (6) involves secrets of two different users u and v. However, this is not a problem as these pairwise noise terms are known by both involved users, so they can use negated randomnesses r ∆u,v = -r ∆v,u in their commitments of ∆ u,v and ∆ v,u such that everybody can verify that Com Θ (∆ u,v , r ∆u,v ) + Com Θ (∆ v,u , r ∆v,u ) = Com Θ (0, 0).

At the beginning of the protocol, all users jointly generate parameters Θ for a shared Pedersen commitment scheme (see Appendix C). Our verification protocol, described in Algorithm 2, requires users to publish in the bulletin board all commitments and involved ZKPs as soon as the private values involved are generated by the execution of the private averaging phase (Algorithm 1). The verification can then be performed by any party interested in verifying the integrity of the computation. By composition of ZKPs, every user prove the correctness of his/her computations, and thereby Theorem 4. Completeness, soundness and zero knowledge properties for Theorem 4 are guaranteed as they are preserved by the composition of ZKPs.

In the rest of this section, we give additional details regarding multiple executions and user drop out, and conclude with a discussion of how the correctness guarantees of GOPA compare to the centralized scenario.

B.4.1 Consistency over Multiple Executions

While the guarantees of Theorem 4 hold with respect to a single execution of GOPA, commitments to private values can be used when multiple executions of the algorithm are performed over the same or related data. In addition to linear relations, products and range proofs, a wide variety of arithmetic relations can be proven between committed secrets. As an illustration, consider ridge regression in Example 1. Every user u can publish commitments c yu = Com Θ (y u , r), c φ i u = Com Θ (φ i u , r i ) for i ∈ {1, . . . , d} (computed with the appropriately drawn randomness), and additionally commit to φ i u y u and φ i u φ j u , for i, j ∈ {1, . . . , d}. Then, by the use of ZKPProd, it can be verified that all these commitments are computed coherently, i.e, that the commitment of φ i u y u is the product of secrets committed in c yu and c φ i u for i ∈ {1, . . . , d}, and analogously for the commitment of φ i u φ j u in relation with c φ i u and c φ j u , for i, j ∈ {1, . . . d}. An efficient ZKP to check arbitrary arithmetic relations, i.e, inner products of vectors of commitments, is provided in [START_REF] Bootle | Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting[END_REF] and optimized in [START_REF] Bünz | Bulletproofs: Short Proofs for Confidential Transactions and More[END_REF]. Additionally, ZKPs can be composed such that AND and OR composition of the proven statements can be generated (see ZKPOr), and consequently any kind of logical monotone formula [START_REF] Cramer | Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[END_REF][START_REF] De Santis | On monotone formula closure of SZK[END_REF].

B.4.2 Dealing with User Drop Out

As we are in a decentralized setting, the successful execution of the protocol relies on users remaining active during the computation. In the context of a large number of users, the probability of a few of them to drop out in the middle of the execution must be taken into account. Here, we consider that a user drops out of the computation if he/she is off-line for a period which is too long for the community to wait until his/her return. Malicious users may also intentionally drop out to bias the outcome of the computation. Indeed, drop outs affect the outcome of the computation as we rely on the self-canceling noise terms {∆ u } u∈U for the correctness and accuracy of the computation.

We propose a three-step approach to handling user drop out. First, as a preventive measure, users should exchange pairwise noise with a few more neighbors than strictly needed to satisfy the privacy requirements, in order to have some margin in case a small number of neighbors drop out. Second, as long as there is time, users attempt to repair as much as possible the problems induced by drop outs. Finally, when circumstances require and allow it, 4 we can ignore the remaining problems and proceed with the algorithm, which will then output a slightly perturbed answer.

We now focus on the second of these three steps. Users can react to the drop-out of a neighbor (i.e., a user with whom they already exchanged pairwise noise) in several ways. First, a user u who did not publish Xu yet can just remove the corresponding pairwise noise (and exchange noise with another active user instead if needed). Second, a user u who did publish Xu already but has still some safety margin because he exchanged pairwise noise with more neighbors than strictly necessary can simply reveal the noise exchanged with the user who dropped out, and subtract it from his published Xu . The third case, in which a user u published Xu already but cannot afford to adjust it by removing the noise exchanged by the user who dropped out, is the most difficult one, and should therefore be avoided as much as possible by the preventive surplus of noise exchanges described above. If u is lucky, he/she can still exchange additional noise with other users who did not publish their noisy value yet. However, if u cannot trust that a sufficient fraction of these users are honest, the only choice may be that user u drops himself/herself out. Note that this could cause a cascade of drop-outs if other users also do not have sufficient margin, or a significant part of the pairwise noise exchange procedure needs to be repeated. To avoid such problems, in addition to preventively exchanging surplus pairwise noise, it is best to check which users went off-line just before publishing X, and to have penalties for users who (repeatedly) drop out at the most inconvenient times.

B.4.3 Comparison of Correctness Guarantees with the Centralized Setting

Consider the case of a centralized computation, where a central party is provided with the raw data to compute the model. In general, this central party does not know whether the values it received as input are truthful. However, it knows that all of its computations are performed correctly given the received input data. In this sense, our commitments offer the same guarantees.

In some critical cases where reliable data is needed, the central party could require that the data of users to be certified by a trusted third party. In such scenarios where credentials are required, solutions exist to provide private credentials to users, that have the same zero knowledge logic as our solution and also provide to the central party a certificate from a trusted third party that this data is valid [START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF][START_REF] Brands | Rethinking public key infrastructures and digital certificates: building in privacy[END_REF].

We can conclude that GOPA is an auditable protocol that, through existing efficient cryptographic primitives, can offer guarantees similar to the automated auditing which is possible for data shared with a central party.

For computation, we take into account regular operations such as floating point sum, product, division, exponentiation, etc., as well as products and exponentiations in the Pedersen multiplicative group G described in Appendix B, and cryptographic hash function evaluations. Often, the dominant terms in the computations are discrete exponentiations in G, which still remain lightweight in current implementations of Pedersen commitments [START_REF] Franck | Efficient Implementation of Pedersen Commitments Using Twisted Edwards Curves[END_REF]. For communication, three types of interactions in the network are taken into account: (1) sending a message to another user in the context of a pairwise exchange, (2) publishing a message or (3) querying the bulletin board for a set of publications. We also measure the size of these messages in the number of values that they contain, which in most cases are elements of Z q and G.

The costs break down as follows:

• The initialization of GOPA requires enrolling users for the computation and defining parameters of the Pedersen commitment scheme, which has a cost of O(1) per user. The computation and publication of commitments of the vector X of private values, as well as the verification that every one of its components is in the range [0, 1] (i.e. Property [START_REF] Bell | Private Protocols for U-Statistics in the Local Model and Beyond[END_REF]) with ZKPRange has a computational and communication cost that is logarithmic in the size of the range [0, 1]. As the range proof size is small and constant, this cost is dominated by other costs. Additionally, the complexity of verifying the publications of u is the same as the cost of u proving its computations mentioned above. Finally, the communication cost for the verification of u comes from querying the bulletin board for all of u's publications, i.e. the size of all commitments and ZKPs published, which is O(|N (u)| + log 2 (1/B) log 2 (log 2 (log 2 (1/B)))).

As discussed at the end of Appendix B.3, a reasonable value for B in practice is σ η /10 6 |U H |.

our work we use a partially homomorphic scheme with only addition. As a result, we can just represent our floating point numbers with as many bits (after the decimal dot) as our variables also have in computer memory. 3. If bandwidth would dictate that we can transfer only at lower precision compared to the internal representation, a conversion will be needed before encryption (e.g. from 10 digits to 5 digits after the decimal dot). Still, (a) rounding has been well described in numerical computing literature, (b) in our case it would not decrease privacy as all our operations are linear (no sharp differences in behavior if a value changes less than machine precision), and (c) we feel this would not gain much bandwidth: indeed, in practical applications with sums over millions of parties (plus some random encryption bits), one would already require more than 7 digits before the decimal dot, in comparison with which the number of less significant bits gained is relatively small.

Lemma 4 .

 4 Let m ≥ 27 and δ B > 0. Let ζ = max 4, 1 + 3 log(2e/δ B ) 2 log(m) .

60 . 8 k 3 ρ 1 ρ 7 ρ

 608317 = 5 σ ∆ = 41.= 0.5 k = 20 σ ∆ = 26.8 k = 30 σ ∆ = 17.2 n = 1000 ρ = 1 k = 5 σ ∆ = 63.4 k = 10 σ ∆ = 41.= 0.5 k = 20 σ ∆ = 45.4 k = 30 σ ∆ = 27.3 n = 10000 ρ = 1 k = 10 σ ∆ = 54.6 k = 20 σ ∆ = 34.= 0.5 k = 20 σ ∆ = 55.5 k = 40 σ ∆ = 28.4 Table 2: Examples of admissible values for k and σ ∆ , obtained by numerical simulation, to ensure ( , δ)-DP with trusted curator utility for ε = 0.1, δ = 1/n 2 H , δ = 10δ . By setting ε = ε , Equation (3) of Theorem 1 implies:

•

  Interacting with a neighbor to generate a noise term, and publishing a commitment of it requires O(1) computations and messages for a user. Performing the ZKPLinear proof to verify Property (6) require O(1) messages and computations (as the linear relation is composed of 2 terms) for a user and its verifier. As |N (u)| pairwise noise terms are generated by user u, this has a cost of O(|N (u)|) for communication and computation in total. • Generating the private Gaussian distribution variable η u and proving Property (7) is done by performing ZKPNormal. Given parameter B, this requires O(log 2 (1/B)) computations for the generation of η u in the private averaging phase, O(log 2 (1/B) log 2 (log 2 (1/B))) computations to generate and verify the ZKP, and O(1) messages of size O(log 2 (1/B) log 2 (log 2 (log 2 (1/B)))). • Finally, the computation and verification of the proof of Property (5) requires the computation of ZKPLinear over |N (u)| + 3 terms per user, which has a computational cost of O(|N (u)|) both for the prover and the verifier. The communication cost is of O(1) messages of size O(1) as the private values involved in the proof have already been committed for previous proofs. The overall computational cost of the private averaging phase for a user u ∈ U is therefore O(|N (u)| + log 2 (1/B)) and the cost of proving its computations in the verification phase is O(|N (u)| + log 2 (1/B) log 2 (log 2 (1/B))). The overall communication cost is composed of O(|N (u)|) messages of size O(1) and O(1) messages of size O(log 2 (1/B) log 2 (log 2 (log 2 (1/B)))).

Table 1 :

 1 Value of σ ∆ to ensure ( , δ)-DP with trusted curator utility for n = 10000, ε = 0.1, δ = 1/n 2 H , δ = 10δ depending on the topology, as obtained from Corollary 1.

	1.7	2.1	Theorem 3: 44.7 (k = 105) 34.4 (k = 203) 9655.0 6114.8 Simulation: 34.7 (k = 20) 28.4 (k = 40)

  To simplify our argument, in the sequel we will assume G H is such random graph as this does not affect the obtained result. In fact, the random k-out model concentrates the degree of vertices more narrowly around the expected value then Erdős-Rényi random graphs, so any tail bound our proofs will rely on that holds for Erdős-Rényi random graphs also holds for the graph G H we are considering. In particular, for v ∈ U H , the degree of v is a random variable which we will approximate for sufficiently large n H and k H by a binomial B(n H , 2k H /n H ) with expected value 2k H and variance 2k H (1 -2k H /n H ) ≈ 2k H .

• We consider the subgraph G H induced by the set U H of honest users. Recall that n H = |U H | and that a fraction ρ of the users is honest, hence n H = ρn. Let k H = ρk. The graph G H is a subsample of a k-out-graph, which for larger n H and k H follows a distribution very close to that of Erdős-Rényi random graphs G p (n H , 2k H /n H ).

  Verification phase computations of GOPA 1: Input: All users have jointly generated a commitment scheme with parameters Θ and each user u has published to the bulletin board:

now briefly analyze its complexity. Recall that given parameter M = 1/B, generating a uniformly distributed random number y has a cost of O(log 2 (1/B)) computations and a proof size of O(log 2 (log 2 (1/B))) as described in ZKPUniform. The dominant cost of the computation is in the computation of the erf or erfc series. We neglect lower order costs. The number of terms to evaluate is a constant L = O(log 2 (1/B)) that the community computes once in advance. Computing 34 Algorithm 2 2:

10 :

 10 Verify that values inside c Xu , (c ∆u,v ) v∈N (u) , c ηu sum to Xu (if not, add u to cheaters list)

	11:

Note that if G H is not connected, we obtain a similar but weaker result for each connected component separately (nH is replaced by the size of the connected component).

In particular, even though Bollobas's proof is asymptotically tight, its last line uses the fact that (e log n)

3a n 1-a+a 2 /n = o(1) for all a ≤ n/2. This expression is only lower than 1 for n ≥ 5.6 • 10 10 , and as the sum of this expression over all possible values of a needs to be smaller than δF , we do not expect this proof applies to graphs representing current real-life datasets.

Strictly speaking, the proofs we will use are called arguments, as the soundness property relies on the computational boundedness of the Prover P through the DLA described above, but as for general reference to the family of techniques we use the term proofs.

For instance, only a few drop outs have not yet been resolved, there is not much time available, and the corresponding pairwise terms ∆u,v are known to be not too large (e.g., by the use of range proofs).

Acknowledgments and Disclosure of Funding

The authors were supported by grants ANR-16-CE23-0016-01 and ANR-18-CE23-0018-03, by the European Union's Horizon 2020 Research and Innovation Program under Grant Agreement No.825081 COMPRISE and by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020. César Sabater is funded by an Inria Cordi-S scholarship.

The authors would like to thank James Bell, Pierre Dellenbach, Adrià Gascón and Alexandre Huat for fruitful discussions.

Given the number of users n, the proportion of honest nodes ρ and a value for k, we implemented a program that generates a random k-out graph, checks if the subgraph G H of honest users is connected, and if so finds a suitable spanning tree for G H and computes the corresponding value for t ∆ t ∆ needed by our differential privacy analysis (see for instance Appendix A.2). From this, we can in turn deduce a sufficient value for σ 2 ∆ using Corollary 1. Table 2 gives examples of values obtained by simulations for various values of n, ρ and several choices for k. In each case, the reported σ ∆ corresponds to the worst-case value required across 10 5 random runs, and the chosen value of k was large enough for G H to be connected in all runs. This was the case even for slightly smaller values of k. Therefore, the values reported in Table 2 can be considered safe to use in practice.

Appendix B Cryptographic Framework

In this appendix, we provide an extended overview of the cryptographic notions involved in Section 5, and give more details about our verification protocol. First, we give deeper intuitions on commitments and ZKPs in Appendices B.1 and B.2. Next, using these building blocks, we present ZKPs on the statistical distributions of uniform and Gaussian random variables in Appendix B.3. Finally, in Appendix B.4, we show how these tools can be used to obtain the verification protocol of GOPA. For simplicity, we sometimes abstract away some of the technical cryptographic details, but refer to the corresponding bibliography for a more advanced treatment.

Public bulletin board. We implement the publication of commitments and proofs using a public bulletin board so that any party can verify the validity of the protocol, avoiding the need for a trusted verification entity. Users sign their messages so they cannot deny them. More general purpose distributed ledger technology such as in Bitcoin transactions [START_REF] Nakamoto | Bitcoin: A Peer-to-Peer Electronic Cash System[END_REF] could be used here, but we aim at an application-specific, light-weight and hence more scalable solution.

B.1 Commitment Schemes

We start by defining formally a commitment and its properties. For clarity, we will use bold variables to denote commitments. Definition 2 (Commitment Scheme). A commitment scheme consists of a pair of (computationally efficient) algorithms (Setup, Com). The setup algorithm Setup is executed once, with randomness t as input, and outputs a tuple Θ ← Setup(t), which is called the set of parameters of the scheme. The algorithm Com with parameters Θ, denoted Com Θ , is a function Com Θ : M Θ × R Θ → C Θ , where M Θ is called the message space, R Θ the randomness space, and C Θ the commitment space. For a message m ∈ M Θ , the algorithm draws r ∈ R Θ uniformly at random and computes commitment c ← Com Θ (m, r).

The security of a commitment scheme typically depends on t not being biased, in particular, it must be hard to guess non-trivial information about t.

We now define some key properties of commitments. Property 1 (Hiding Property). A commitment scheme is hiding if, for all secrets x ∈ M Θ and given that r is chosen uniformly at random from R Θ , the commitment c x = Com Θ (x, r) does not reveal any information about x. Property 2 (Binding Property). A commitment is binding if there exists no computationally efficient algorithm A that can find

Property 3 (Homomorphic Property). A homomorphic commitment scheme is a commitment scheme such that M Θ , R Θ and C Θ are abelian groups, and for all

Please note that the three occurrences of the '+' sign in the above definition are operations in three difference spaces, and hence may have different definitions and do not necessarily correspond to normal addition of numbers.

Pedersen commitments. For our protocol we use the Pedersen commitment scheme, described in [START_REF] Pryds | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF]. For a given cyclic group G of large prime order q, Setup is a function that draws uniformly

We base our proofs in a Pedersen commitment with parameters (g, h) chosen from G as described above. For some building blocks, we use multiple pairs of bases as parameters, where bases belonging to the same pair Θ are always assumed to be chosen independently at random from G. We denote by r ← R S the operation of generating a random number r uniformly distributed over the set S, and by a = ? b the action of verifying the equality of a and b. Between elements of G, products and exponentiations are implicitly modulo q.

When discussing complexity, the dominating computations are always discrete exponentiations in G.

We will refer to them just as exponentiations. For a ZKP, we call the size of a proof the sum of all the values (numbers, commitments, challenges, etc.) exchanged between P and V .

Proof of equality. This first proof allows a prover P to prove that he committed to the same private value x in two different commitments

The pairs of bases (g 1 , h 1 ) and (g 2 , h 2 ) might be different. This proof is a standard generalization of the one described in [START_REF] Chaum | Wallet Databases with Observers[END_REF] for single bases.

The protocol goes as follows:

V draws a challenge t ← R Z q and sends it to P . 3. P computes d ← a + xt (mod q), e ← b + rt (mod q) and f ← c + r t (mod q) and sends (d, e, f ) to V .

At any time, to verify the proof (c ab , c ac , t, d, e, f ), V checks that

If the equality holds, P proves the statement. We denote this proof as

where we use the convention that values outside the curly braces are public, while values private to P and the proven statement are inside. The proof requires the computation of 4 exponentiations by P , 6 exponentiations by V , and its size is the sum of the sizes of the 6 values exchanged in the conversation between P and V .

Proof of linear relation. This is a key proof that will be used several times in our verification procedure. Let x = (x i ) k i=1 for some k > 0 be a vector of private values, c = (c i ) k i=1 a public vector of commitments such that c i is a commitment of x i , ā = (a i ) k i=1 a public vector of coefficients, and b a public scalar. The goal of P is to prove the equality x, ā = b (mod q), where •, • is the inner product. The proof is simple: first, note that, by the homomorphic property, c L = k i=1 (c i ) (ai) is a valid commitment of x, ā . Then, P and V just perform ZKPEq(c L , c b ) for c b = g b (the base h for c b is not necessary as we use randomness equal to 0). We denote the proof as

To perform the proof, the amount of computations done by P is dominated by 3k + 1 exponentiations to compute the vector c and the other commitments c L and c b . Both P and V perform one execution of ZKPEq. V also has to compute c L and c b by performing k+1 exponentiations. The computational complexity is then O(k) exponentiations for both parties. The proof size and therefore the load of the network is also O(k) values, which for P , can be split into several messages if components of c are committed in different moments. Note that, with this proof, users can already prove the correctness of Properties ( 5) and ( 6) for the verification of GOPA.

Proof that a secret lies in a given range (range proof ). Here, the statement to prove is that, for a positive integer M < q -1 and a commitment c x , P knows the secret x inside c x , and that it lies in the range [0, M ]. Among the various constructions that exist for range proofs, we use the result by [START_REF] Bünz | Bulletproofs: Short Proofs for Confidential Transactions and More[END_REF] for intervals of the form [0, 2 l -1]. Then, our proof can be performed with 2 of these proofs,

Appendix C Randomness for Setup and ZKPUniform

The generation of challenges in ZKPUniform cannot be made non-interactive as it provides an opportunity for malicious users to execute many generations and choose a particular sample, which would bias the distribution. Here, we provide a decentralized method to generate O(|U |) challenges with a computational effort of O(1) per user, and only O(1) messages in the network. Additionally, this algorithm can be used to generate the randomness to run the Setup algorithm and initialize the Pedersen commitment scheme shared by all users.

For this purpose, we make use of a cryptographic hash function

where M is defined as in the interval of ZKPUniform. Cryptographic hash functions are easy to evaluate, but their outcome is impossible to predict or to distinguish from random numbers. Practical instances of such functions can be found in HMAC and Sponge-based constructions for random number generators [START_REF] Elaine | Recommendation for random number generation using deterministic random bit generators (revised)[END_REF][START_REF] Bertoni | Sponge-based pseudorandom number generators[END_REF].

To describe our procedure, we enumerate users from 1 to n = |U |. The procedure goes as follows:

1. Every user u generates a random number s u ← R Z M , computes a commitment c u ← Com(s u ) for some randomness and publishes c u to the bulletin board.

2. When all commitments are published, every user reveals s u by publishing it such that all users can check that the commitment c u was computed correctly.

3. By setting s 1 ← s 1 and starting from user 2, user u + 1 queries the bulletin board to get s u , computes s u+1 ← s u+1 + s u mod M and publishes s u+1 in the bulletin board.

4. Users set t 0 ← s n as an unbiased seed for H and sequentially, each user u queries the bulletin board for t u-1 , computes its challenge t u ← H(t u-1 ) and publishes it to the bulletin board.

The "commit-then-reveal" protocol in Steps 1 and 2 is to avoid users from choosing the value s u depending on the choice of other users, which could bias the final seed s n . As it is computed from modular sums, this seed is uniformly distributed over [0, M -1] if at least one user is honest. As our seed is unpredictable and challenges are obtained by application of H, we make sure that the sequence of challenges t 1 , . . . , t n is also unpredictable. To obtain more randomness, the protocol above can be repeated.

If users have already initialized parameters Θ of the shared Pedersen scheme, the commitment function Com used is the Pedersen function Com Θ as defined in Appendix B. Otherwise, a commitment function which does not require the generation of common parameters (but is not suitable for other tasks such as the generation of our ZKPs) can be used, see for example [START_REF] Blum | Coin flipping by telephone a protocol for solving impossible problems[END_REF]. This happens if the above protocol is used to generate the randomness t as input of the Setup function of the shared Pedersen scheme. In this case, we obtain t by taking as many bits of the sequence t 1 , t 2 , . . . as needed.

Note that the request for a challenge t u is blocking for the user u until all users request a challenge. However, every user needs the same amount of random challenges to execute Setup or ZKPUniform. Hence, all these challenges can be requested and used at initialization for Setup, and in a moment of the computation fixed by all users for ZKPUniform. This prevents that users have to wait for a long time after a request, as would happen in a setting where the requests are imbalanced.

Finally, to verify that a user u participated correctly, one needs to check that (1) the commitment c u was properly computed from s u , (2) s u was correctly computed from s u-1 and s u , and (3) the challenge t u was correctly computed from t u-1 by the application of H. This can be added to the verification protocol with O(1) extra computations and messages for every random challenge generated and the execution of Setup, and does not have a significant impact in the overall complexity.

Appendix D Complexity of GOPA

The complexity of the protocol in terms of computation and communication was summarized in Theorem 5. This section presents a more detailed analysis of this complexity, relying in particular on the complexity of the zero knowledge proofs discussed in Appendix B.

Appendix E Further Discussion on the Impact of Finite Precision

In practice, we cannot work with real numbers but only with finite precision approximations. We provide here a brief discussion of the impact of this on the guarantees offered by the protocol. We emphasize that there is already a large body of work which addresses most of the potential problems which could arise because of finite precision. Here are the main points:

1. Finite precision can be an issue for differential privacy in general, see e.g. [START_REF] Balcer | Differential Privacy on Finite Computers[END_REF] for a study of the effect of floating point representations. Issues can be overcome with some care, and our additional encryption does not make the problem worse (in fact we can argue that encryption typically uses more bits and in our setting this may help). 2. The issue of finite precision has been studied in cryptography. While some operations such as multiplication can cause additional trouble in the context of homomorphic encryption, in