Arnaud Grivet
email: arnaud.grivetsebert@cea.fr

Rafaël Pinot

Martin Zuber

Cédric Gouy-Pailler

Renaud Sirdey

Arnaud Grivet Sébert

SPEED: Secure, PrivatE, and Efficient Deep learning

Keywords: Data protection, Collaborative learning, Distributed differential privacy, Homomorphic encryption

We introduce a deep learning framework able to deal with strong privacy constraints. Based on collaborative learning, differential privacy and homomorphic encryption, the proposed approach advances state-of-the-art of private deep learning against a wider range of threats, in particular the honest-but-curious server assumption. We address threats from both the aggregation server, the global model and potentially colluding data holders. Building upon distributed differential privacy and a homomorphic argmax operator, our method is specifically designed to maintain low communication loads and efficiency. The proposed method is supported by carefully crafted theoretical results. We provide differential privacy guarantees from the point of view of any entity having access to the final model, including colluding data holders, as a function of the ratio of data holders who kept their noise secret. This makes our method practical to real-life scenarios where data holders do not trust any third party to process their datasets nor the other data holders. Crucially the computational burden of the approach is maintained reasonable, and, to the best of our knowledge, our framework is the first one to be efficient enough to investigate deep learning applications while addressing such a large scope of threats. To assess the practical usability of our framework, experiments have been carried out on image datasets in a classification context. We present numerical results that show that the learning procedure is both accurate and private.

Introduction

Application scenarios. We consider n hospitals, each of which owns a (personal) labelled database composed of medical records from its patients and a model (e.g. neural network) trained on this database to predict if a new patient is victim of a given disease, say cancer. The hospitals' goal is to collaborate in order to improve the early detection of cancer. Building a model from a larger dataset than the personal databases would lead to improved detection capabilities. Nevertheless, these medical databases are highly-sensitive and the information they contain about the patients cannot be disclosed [START_REF] Parliament | Regulation (eu) 2016/679 of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data[END_REF]. In such a setting, the hospitals wish to collaboratively train a global model while preserving confidentiality of their records. To do so, the idea is to rely on an aggregating institution (e.g. the World Health Organisation). This would amount to creating a three-party architecture: hospitals, aggregating institution, global model. Note that in our example, and in many real-world settings, all the training data providers may be recipients of the global model, or the global model may even be totally public. Hence, the global model may be exposed to attacks like membership inference attacks [START_REF] Shokri | Membership inference attacks against machine learning models[END_REF] that could indicate with high accuracy the probability that one patient was present in a database. Also, given a set of instances, the risk of a model inversion attack [START_REF] Wu | A methodology for formalizing modelinversion attacks[END_REF] which tries to infer sensitive attributes on the instances from a supposedly nonsensitive (often white-box) access to the model, is to be seriously taken into account as it would allow to infer for example that some of the hospital databases contain more ill patients than others. Besides, the aggregating institution might be the target of cyberattacks aimed at stealing data from it. For all these reasons, the three-party architecture we consider has to be resistant to threats coming from both the aggregation server and the global model recipients.

Another motivating example, from the field of cybersecurity, is when several actors each hold a database of cybersecurity incident signatures that have occurred on their customer networks. The actors would rely on a third-party server to train the global model. In this scenario, it is a great security issue if the global model suffers from an attack (e.g. if the model features can be inferred [START_REF] Tramèr | Stealing machine learning models via prediction apis[END_REF][START_REF] Wang | Stealing hyperparameters in machine learning[END_REF][START_REF] Yan | Cache telepathy: Leveraging shared resource attacks to learn DNN architectures[END_REF] with limited access to the model). In this case, this would clearly leak some information on the detection capabilities of the actors, giving a clear advantage to cyberattackers on the networks they supervise.

Deployment scenario and threat model. To perform the aggregation in a private way, we work in the tripartite setting summarised in Figure 1 and formally detailed in Section 4. The student (who holds the global model, a.k.a. the student model ) is the owner of the homomorphic encryption scheme under which encrypted-domain computations will be performed by the aggregation server. This means that the student generates and knows both the encryption and decryption keys pk and sk. Then, when being submitted an unlabelled input, the data holders (a.k.a. the teachers) noise the predictions from their personal models, encrypt them under pk and send these encryptions to the server. The server has the responsibility to homomorphically perform the aggregation in order to produce an encryption of the output (e.g. a label) which will be sent back to the student and used by the latter for learning, after due decryption. Homomorphic encryption thus provides a countermeasure to confidentiality threats on the teachers' predictions from the aggregation server, while the noise introduced by the actor addresses, via differential privacy, the issue of attacks against the student model. In this setting, we assume that the student model is public or at least available to all the actors of the protocol, namely the teachers, the aggregation server and, of course, the student. Our mechanism is differentially private in this context, and our guarantees still hold against a malicious teacher, who has the information of the noise she generated, or even against colluding teachers (see Section 5). On the contrary, we do not address threats whereby the student and the aggregation server collude in the sense that the student does not share sk with the server (in which case they would both get access to the teachers' predictions). We do not consider either threats where the aggregation server behaves maliciously, e.g. to prevent the student model from effectively learning from the teachers, leading to more or less stealthy forms of denial-of-service, or to perform a chosen ciphertext attack via selected queries to the student model. This is the typical scenario in which homomorphic encryption intervenes and our setting thus covers the threat model whereby the aggregation server is assumed to operate properly but may perform computations on observed data to retrieve information. This threat model is commonly known as the honestbut-curious model [7,[START_REF] Graepel | Ml confidential: Machine learning on encrypted data[END_REF][START_REF] Ishai | Extending oblivious transfers efficiently[END_REF]. Our contribution. In this paper, we present a complete collaborative learning protocol which is secure along the whole workflow regarding a large scope of threats. We ensure protection of the data against any malicious actor of the protocol during the learning phase and prevent indirect information leakage from the final model using both homomorphic encryption and differential privacy. While our framework is agnostic to the kind of models used by both the teachers and the student, to the best of our knowledge this is the first work with this level of protection to be efficient enough to apply to deep learning, therefore allowing very good accuracy on difficult tasks such as image classification, as shown by the experiments we ran. Our framework is also bandwidth-efficient and does not require more interactions than required by the baseline protocol.

Outline of the paper. Section 2 relates our work to the literature. In Section 3, we give some technical background on differential privacy and homomorphic encryp-tion. We describe our SPEED framework in Section 4 and analyse its differential privacy guarantees in Section 5. Section 6 presents our experimental results -SPEED achieves state-or-the-art accuracy and privacy with a mild computational overhead w.r.t previous works. Section 7 concludes the paper and states some open questions for further works.

Related work

Differential privacy (DP). Recent works considered to use differential privacy in collaborative settings close to the one we consider [5,6,[START_REF] Chase | Private collaborative neural network learning[END_REF][START_REF] Geyer | Differentially private federated learning: A client level perspective[END_REF][START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF][START_REF] Papernot | Scalable private learning with pate[END_REF]. Among them, the most efficient technique in terms of accuracy and privacy guarantees is Private Aggregation of Teacher Ensembles (PATE) first presented in [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF] and refined in [START_REF] Papernot | Scalable private learning with pate[END_REF]. PATE uses semi-supervised learning to transfer to the student model the knowledge of the ensemble of teachers by using a differentially private aggregation method. This approach considers a setting very close to ours with the notable difference that the aggregation server is trusted. Hence, applying PATE in our scenario makes the teacher models vulnerable. To tackle this issue, our work builds upon PATE idea with two key differences: we let the responsibility of generating the noise to the teachers and we add a layer of homomorphic encryption in order for the overall learning to be kept private. Another difference can also be noted. To derive privacy guarantees, PATE assumes that two databases d and d are adjacent if only one sample of the personal database d i of one teacher i changes, with the hypothesis that the personal databases d i are disjoint. We do not need this hypothesis and we only consider the teacher models, not the personal databases they use to train them. This leads us to a more powerful definition of adjacency: two databases d and d are adjacent if they differ by one teacher.

Homomorphic Encryption (HE). HE allows to perform computations over encrypted data. In particular, this can be used so that the model can perform both training and prediction without handling cleartext data. In terms of learning, the naive approach would be to have the training sets homomorphically encrypted, sent to a server for training to be done in the encrypted domain and the resulting (encrypted) model sent back to the participants for decryption. However, putting aside many subtleties, even by deploying all the arsenal available in the HE practitioner toolbox (batching, transciphering, etc.) this would be impractical as "classical" learning is both computation and know-how intensive and HE operations are intrinsically costly. As a consequence, there are only very few works that capitalise on HE for private training [START_REF] Graepel | Ml confidential: Machine learning on encrypted data[END_REF][START_REF] Hesamifard | Cryptodl: Deep neural networks over encrypted data[END_REF][START_REF] Lou | Glyph: Fast and accurately training deep neural networks on encrypted data[END_REF] and inference [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF][START_REF] Juvekar | {GAZELLE}: A low latency framework for secure neural network inference[END_REF] of machine learning tasks. Moreover, since some attacks can be performed in a black-box setting, the system is still vulnerable to attacks from the end user who has access to the decryption key. In our framework, we do not use HE directly to build the model, we use it as a mean for the aggregation to be kept private. That way, we are protected against potential threats from the aggregation server, which does not have the decryption key, and we keep a manageable computational overhead. Federated learning. Federated learning approaches gather several users who own data and make them collaborate in an iterative workflow in order to train a global model. The most famous federated learning algorithm is federated averaging [START_REF] Mcmahan | Federated learning of deep networks using model averaging[END_REF] which is a parallelised stochastic gradient descent. In a context of sensitive user data, several works proposed privacy-preserving federated learning or closely related distributed learning that make use of differential privacy [START_REF] Geyer | Differentially private federated learning: A client level perspective[END_REF][START_REF] Shokri | Privacy-preserving deep learning[END_REF], cryptographic primitives [7,8,[START_REF] Ryffel | Ariann: Low-interaction privacy-preserving deep learning via function secret sharing[END_REF] or both [START_REF] Chase | Private collaborative neural network learning[END_REF][START_REF] Ryffel | A generic framework for privacy preserving deep learning[END_REF][START_REF] Sabater | Distributed differentially private averaging with improved utility and robustness to malicious parties[END_REF]. These methods require online communication between the parties whereas our solution takes advantage of homomorphic encryption and the existence of personal trained models to avoid online communication and drastically limit the interactions, that are both bandwidthconsuming and vulnerable to attacks.

Private aggregation. Several approaches have been considered to limit the need for a trusted server when applying differential privacy, for example by considering local differential privacy [START_REF] Duchi | Local privacy and statistical minimax rates[END_REF][START_REF] Kairouz | Extremal mechanisms for local differential privacy[END_REF][START_REF] Kasiviswanathan | What can we learn privately[END_REF]. In practice it often results in applying too much noise, and maintaining utility can be difficult [START_REF] Kasiviswanathan | What can we learn privately[END_REF][START_REF] Ullman | Tight lower bounds for locally differentially private selection[END_REF] especially for deep learning applications. In order to recover more accuracy while keeping privacy, some works combined decentralised noise distribution (a.k.a. distributed differential privacy [START_REF] Shi | Privacy-preserving aggregation of time-series data[END_REF]) and encryption schemes [2,[START_REF] Goryczka | A comprehensive comparison of multiparty secure additions with differential privacy[END_REF][START_REF] Rastogi | Differentially private aggregation of distributed time-series with transformation and encryption[END_REF][START_REF] Shi | Privacy-preserving aggregation of time-series data[END_REF] in the context of aggregation of distributed time-series. Our work contributes to this line of research. However, our framework is the first one to be efficient enough to investigate deep learning applications while combining distributed DP and HE. Another advantage of our solution concerns fault tolerance regarding the added noise. Some works addressed the problem of fault tolerance by making the server generate the noise that some users did not generate [4] while other works assume that the users themselves adapt the noise they generate to the possible failures [START_REF] Chan | Privacy-preserving stream aggregation with fault tolerance[END_REF]. In our setting, because of the encryption and the absence of communication between the teachers, we cannot suppose that any honest entity knows if some failures occurred. Moreover, the addition of noise to compensate a failure does not solve the problem of colluding teachers who may still send noise but do not keep it secret. In our protocol, the task of an honest actor (teacher or server) does not depend on the number of failures and we provide privacy guarantees as a function of the number of failures (see Section 5) -it then suffices to assume an upper bound on this number to ensure a privacy guarantee.

Secure Multi-Party Computation (SMPC). Secure Multi-Party Computation is a general approach that enables several parties to collaboratively perform a given computation without revealing to the other parties any more information than the result of this computation. In particular, secure aggregation regroups approaches which use SMPC techniques as one-time pads masking [7,8] or secret-sharing [START_REF] Danezis | Smart meter aggregation via secret-sharing[END_REF] to perform aggregation over sensitive data. Although these approaches are very close in intent to FHE-based ones, as the present one, they achieve different tradeoffs. In a nutshell, when FHE is computation-intensive and non-interactive, SMPC puts more stress on protocol interactions. SMPC requires a lot of communication (garbled circuit generation and evaluation, oblivious input key retrieval, secret key sharing), both time-consuming and vulnerable to attacks, and needs in general that all teachers play their role in the protocol for it to terminate -or fixing the fault tolerance issue implies additional rounds of communication [7,8]. On the contrary, the FHE approach is more versatile, requires no interaction among the teachers and is robust to temporary teacher unavailability. Still, at the time of writing, it is the authors' opinion that both approaches are worth investigating in their own right (and this paper obviously belongs to the FHE thread of research).

Preliminaries

Differential privacy

Differential privacy [START_REF] Dwork | Our data, ourselves: Privacy via distributed noise generation[END_REF] is a gold standard concept in privacy preserving data analysis. It provides a guarantee that under a reasonable privacy budget ( , δ), two adjacent databases produce statistically indistinguishable results. In this section, two databases d and d are said adjacent if they differ by at most one example.

Definition 1 A randomised mechanism A with output range R satisfies ( , δ)differential privacy if for any two adjacent databases d, d and for any subset of outputs S ⊂ R one has

P [A(d) ∈ S] ≤ e P A(d ) ∈ S + δ.
Let us also present a famous and widely used differentially private mechanism, known as the report noisy max mechanism.

Definition 2 Let K ∈ N * , and let X be a set that can be partitioned into K subsets X 1 , . . . , X K . The mechanism that, given a database d of elements of X , reports argmax k∈

[K] [n k + Y k ]
, where [K] := {1, . . . , K}, n k := |d ∩ X k | and Y k is a Laplace noise with mean 0 and scale 1 γ , γ ∈ R * + , is called report noisy max.

Theorem 1 ( [17])

Let A be the report noisy max as above. Then A is (2γ, 0)differentially private.

We now define the notion of infinite divisibility that we will use to implement distributed differential privacy. Definition 3 A random variable Y is said to be infinitely divisible if, for any m ∈ N * , we can find a family (X m,i ) i∈[m] of independent and identically distributed (i.i.d.) random variables such that Y has the same distribution as m i=1 X m,i . The following proposition from [START_REF] Kotz | The laplace distribution and generalizations[END_REF] claims that the Laplace distribution is infinitely divisible 1 , enabling to distribute its generation among an arbitrary number of agents.

Proposition 1 ( [30]) Let m ∈ N and γ ∈ R * + . Let G (i) p , for (i, p) ∈ [m] × [2]
, be i.i.d. random variables following the Gamma distribution of shape 1 m and scale

1 γ . Then m i=1 G (i) 1 -G (i) 2
follows the Laplace distribution of mean 0 and scale 1 γ . The Laplace distribution is said to be infinitely divisible. Definition 4 Let A be a randomised mechanism with output range R and d, d a pair of adjacent databases. Let aux denote an auxiliary input. For any o ∈ R, the privacy loss at o is defined as

c(o; A, aux, d, d ) := log P[A(aux, d) = o] P[A(aux, d ) = o]
.

1 Another well-known example of infinitely divisible probability distribution is the Gaussian distribution which can be seen as the sum of Gaussian distributions of well chosen scale parameter. In a possible further work, we could indeed replace the (distributed) Laplace noise by a (distributed) Gaussian noise.

We define the privacy loss random variable C(A, aux, d, d ) as

C(A, aux, d, d ) := c(A(d); A, aux, d, d )
i.e. the random variable defined by evaluating the privacy loss at an outcome sampled from A(d).

In order to determine the privacy loss of our protocol, we use a traditional two-fold approach. First of all, we determine the privacy loss per query and, in a second step, we compose the privacy losses of each query to get the overall loss. The classical composition theorem (see e.g. [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]) states that the guarantees of sequential queries add up. Nevertheless, training a deep neural network, even with a collaborative framework as presented in this paper, requires a large amount of calls to the databases, precluding the use of this classical composition. Therefore, to obtain reasonable DP guarantees, we need to keep track of the privacy loss with a more refined tool, namely the moments accountant [1] that we introduce here, deferring the details of the method in Section A.1 of the appendix.

Definition 5 With the same notations as above, the moments accountant is defined for any l ∈ R * + as

α A (l) := max aux,d,d α A (l; aux, d, d )
where the maximum is taken over any auxiliary input aux and any pair of adjacent databases (d, d ) and α A (l; aux, d, d ) := log E exp(lC(A, aux, d, d )) is the moment generating function of the privacy loss random variable.

Homomorphic encryption

Let us consider Λ and Ω which respectively are the set of cleartexts (a.k.a. the clear domain) and the set of ciphertexts (a.k.a. the encrypted domain). A homomorphic encryption system first consists in two algorithms Enc pk : Λ -→ Ω and Dec sk : Ω -→ Λ where pk and sk are data structures which represent the public encryption key and the private decryption key of the cryptosystem. Homomorphic encryption systems are by necessity probabilistic, meaning that some randomness has to be involved in the Enc function and that the ciphertexts set Ω is significantly much bigger than the cleartexts set Λ. Any (decent) homomorphic encryption scheme possesses the semantic security property meaning that, given Enc(m) and polynomially many pairs (m i , Enc(m i )) it is hard2 to gain any information on m with a significant advantage over guessing. Most importantly, a homomorphic encryption scheme offers two other operators ⊕ and ⊗ where

-Enc(m 1 ) ⊕ Enc(m 2 ) = Enc(m 1 + m 2 ) ∈ Ω -Enc(m 1 ) ⊗ Enc(m 2 ) = Enc(m 1 m 2 ) ∈ Ω
When these two operators are supported without restriction by a homomorphic scheme, it is said to be a Fully Homomorphic Encryption (FHE) scheme. A FHE with Λ = Z 2 is Turing-complete and, as such, is in principle sufficient to perform any computation in the encrypted domain with a computational overhead depending on the security target 3 . In practice, though, the ⊕ and ⊗ are much more computationally costly than their clear domain counterparts which has led to the development of several approaches to HE schemes design each with their pros and cons.

Somewhat HE (SHE). Somewhat homomorphic encryption schemes, such as BGV [10] or BFV [START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF], provide both operators but with several constraints. Indeed, in these cryptosystems the ⊗ operator is much more costly than the ⊕ operator and the cost of the former strongly depends on the multiplicative depth of the calculation, that is the maximum number of multiplications that have to be chained (although this depth can be optimised [3]). Interestingly, most SHE schemes offer a batching capability by which multiple cleartexts can be packed in one ciphertext resulting in (quite massively) parallel homomorphic operations i.e.,

Enc(m 1 , ..., m κ ) ⊕ Enc(m 1 , ..., m κ ) = Enc(m 1 + m 1 , ..., m κ + m κ ) (1)
(and similarly so for ⊗). Typically, several hundreds such slots are available which often allows to significantly speed up encrypted-domain calculations.

Fully HE (FHE). Fully homomorphic encryption schemes offer both the ⊕ and ⊗ operators without restrictions on multiplicative depth. At the time of writing, only the FHE-over-the-torus approach, instantiated in the TFHE cryptosystem [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], offers practical performances. In this cryptosystem, ⊕ and ⊗ have the same constant cost. On the downside, TFHE offers no batching capabilities. To get the best of all worlds, the TFHE scheme is often hybridised with SHE by means of operators allowing to homomorphically switch among several ciphertext formats [9,[START_REF] Lou | Glyph: Fast and accurately training deep neural networks on encrypted data[END_REF] to perform each part of calculation with the most appropriate scheme (see e.g. [START_REF] Zuber | Towards real-time hidden speaker recognition by means of fully homomorphic encryption[END_REF]). Let us consider a set of n owners (a.k.a. teachers) each holding a personal sensitive model f i . We assume that we also have an unlabelled public database D. The goal is to label D using the knowledge of the private (teacher) models to train a collaborative model (a.k.a. student model ) mapping an input space X to an output space [K] = {1, . . . , K}. To do so while keeping the process private, we follow the setting illustrated by Figure 1 relying on a (distrusted) aggregation server:

1. For every sample x of the public database D, the student sends x to the aggregator requesting it to output label for x. The aggregator forwards this request to the n teachers.

2. Each teacher i labels x using its own private model f i . Then each teacher adds noise to the label (see Section 4.2) and encrypts the noisy label before sending it to the aggregation server. 3. The aggregator performs a homomorphic aggregation of the noisy labels and returns the result to the student model, namely the most common answered label (see Section 4.3). 4. The student, who owns the decryption key, decrypts the aggregated label and is then able to use the labelled sample to train its model.

Our framework addresses two kinds of threats using two complementary tools. On one hand, differential privacy protects the sensitive data from attacks against the student model. Indeed, some model inversion attacks [START_REF] Wu | A methodology for formalizing modelinversion attacks[END_REF] might disclose the training data of the student model, and especially the labels of database D. But differential privacy ensures that the noise applied to the teachers' answers prevents the aggregated labels from leaking information about the sensitive models f i4 . On the other hand, the homomorphic encryption of the teachers' answers prevents the aggregator to learn anything about the sensitive data while enabling it to blindly compute the aggregation.

Noise generation and threat models

When requested to label a sample x, each owner i uses its model f i to infer the label of x. In order for the aggregator to compute the most common label in the secret domain, the owner must send a one-hot encoding of the label. That is, rather than sending f i (x), the i-th teacher sends a K-dimensional vector, say z (i) , whose f i (x)-th coordinate is an encryption of 1 while all the other coordinates are encryptions of 0. To guarantee differential privacy (see Section 5 for the formal analysis), the owner adds to this one-hot encoding a noise drawn from

G (i) 1 -G (i) 2
where the G (i) 1 and G (i) 2 are 2n i.i.d. K-dimensional random variables following the Gamma distribution of shape 1 n and scale 1 γ , where γ ∈ R * + . Then, i sends the (encrypted) noisy one-hot encoded vector whose k-th coordinate corresponds to z

(i) k + G (i) k,1 -G (i) k,2 .
Assuming that the aggregator has access to the student model, distributing the responsibility of adding the noise among all the teachers instead of delegating this task to the aggregator (see paragraph on centralised noise below) is necessary to protect the data against an honest-but-curious aggregator. Indeed, such an aggregator could use the information of the noise it generated to break the differential privacy guarantees and, potentially, recover the sensitive data by model inversion on the student model. Note that such an attack does not break the honest-butcurious assumption since the aggregator still performs its task correctly.

Beyond the honest-but-curious model In a model that would go beyond the honestbut-curious aggregator hypothesis, the capability for the aggregator to add it own noise is even more harmful for the privacy (and of course, the accuracy) than not using noise at all. Indeed it gives the aggregator much more freedom to attack. As an example, think about a malicious aggregator that wants to know a characteristic χ on a particular teacher, called its victim. Given a query, for all k ∈ [K], we write n k := |{i : f i (x) = k}| and call it the number of votes for class k. Let us suppose that, for a given query, changing the value of the victim's characteristic χ from χ 0 to χ 1 also changes the victim's vote from a class k 0 to a class k 1 . Hence, by denoting n k 0 = ν 0 and n

k 1 = ν 1 if χ = χ 0 we get n k 0 = ν 0 -1 and n k 1 = ν 1 + 1 if χ = χ 1 .
Then, if the aggregator knows all the n k for k ∈ [K] \ {k 0 , k 1 } and knows ν 0 and ν 1 (which are the classical hypotheses in differential privacy), it can add just as much noise as needed for the class k 0 to be the argmax if and only if χ = χ 0 5 . The result from the homomorphic argmax would then leak the information about the value of the victim's characteristic χ.

Centralised noise generation In a context in which the student model is kept private and, especially, not available to the aggregator, we can consider a centralised way of generating the noise. If we do not trust the teachers to generate the noise, we can charge the aggregator to do it, since it will not be able to use the knowledge of the noise to attack the sensitive data via the student model. The aggregator only needs to generate a Laplace noise (in the clear domain), and homomorphically add it to the unnoisy encryption of n k it receives from the teachers. The infinite divisibility of the Laplace distribution (Proposition 1) shows that the resulting noise is the same as in the case presented above in which each teacher generates an individual noise drawn from the difference of two Gamma distributions. The privacy cost of one request is simply the privacy cost of the report noisy max, namely 2γ (Theorem 1).

In a nutshell, we can consider the following different threat models:

honest (H) : the aggregation server performs its tasks properly and do not try to retrieve information from the data it has access to honest-but-curious (HBC) : the aggregation server performs its tasks properly but it may compute the available data to get sensitive information beyond honest-but-curious (BHBC) : the aggregation server performs the aggregation correctly but cannot be trusted to properly generate the noise necessary to the DP guarantees Table 1 summarises against which kind of server our protocol is protected, depending on the access the server has to the student model and on the way the noise is generated. As already emphasised, we focus on the case where the student model is public and the noise is distributively generated by the teachers because it is the most general model among the realistic threat models and thus gives the better tradeoff between flexibility and security.

Technical details on the homomorphic aggregation

Summing the noisy counts The aggregation server receives the n encrypted noisy labels and sums them up in the secret domain. Due to the infinite divisibility of the Laplace distribution, the server obtains a K-dimensional vector whose k-th

(k ∈ [K]) coordinate is an encryption of: n i=1 z (i) k + G (i) k,1 -G (i) k,2 = n k + Y k
where n k := |{i : f i (x) = k}| and Y k is a Laplace noise with mean 0 and scale 1 γ . So far, we have only needed homomorphic addition which is a good start. Then an argmax operator must be performed after the summation. However, efficiently handling the highly nonlinear argmax function by means of FHE is much more challenging.

Computing the argmax. Most prior work on secure argmax computations use some kind of interaction between a party that holds a sensitive vector of values and a party that wants to obtain the argmax over those values. The non-linearity of the argmax operator presents unique challenges that have mostly been handled by allowing the two interested parties to exchange information. This means increased communication costs and, in some cases, information leakage. This is with the exception of [START_REF] Zuber | Towards real-time hidden speaker recognition by means of fully homomorphic encryption[END_REF]. They provide a fully non-interactive homomorphic argmax computation scheme based on the TFHE encryption. We implemented and parametrised their scheme to fit the specific training problems presented in Section 6. We present here the main idea behind this novel FHE argmax scheme. For more details, see the original paper. The TFHE encryption scheme provides a bootstrap operation that can be applied on any scalar ciphertext. Its purpose is threefold: switch the encryption key; reduce the noise; apply a non-linear operation on the underlying plaintext value. This underlying operation can be seen as a function

g t,a,b (x) = a if x > t b if x < t.
One notable application is that of a "sign" bootstrap: we can extract the sign of the input with the underlying function g 0,1,0 (x). The argmax computation in the ciphertext space is made as follows. For every k, k , k = k , we compare the values

n k + Y k and n k + Y k with a subtraction (n k + Y k -n k -Y k )
and application of a sign bootstrap operation. This yields θ k,k , a variable with value 1 if n k + Y k > n k + Y k and 0 otherwise. Therefore the complexity will be quadratic in the number of classes. For a given k we can then obtain a boolean truth value (0 or 1) for whether n k + Y k is the maximum value. To this end, we compute

Θ k = i =k θ k,i .
n k is the max if and only if, for all i one has θ k,i = 1 i.e. Θ k = K -1. We can therefore apply another bootstrap operation with g K-3 2 ,1,0 . If Θ k = K -1, the boostrap will return an encryption of 1, and return an encryption of 0 otherwise.

Once decrypted, the position of the only non-zero value is the argmax. Because the underlying function g t,a,b is applied homomorphically, its output is inherently probabilistic. In the FHE scheme used, an error is inserted in all the ciphertexts at encryption time to ensure an appropriate level of security. This means that if two values are too close, then the sign bootstrap operation might return the wrong result over their difference. The exact impact of this approximation on the accuracy is evaluated in Section 6.

Remark. Another solution would be to send the noisy histogram n k + Y k of the counts for each class k to the student and let her process the argmax in the clear domain. This could indeed be performed with a plain-old additively-homomorphic cryptosystem such as Paillier or (additive-flavored) ElGamal, avoiding the machinery of the homomorphic argmax. Nevertheless, this approach was put aside because sending the whole histogram instead of the argmax would provide much worse DP guarantees.

Differential privacy analysis

In this section, we will give privacy guarantees considering that two databases d and d are adjacent if they differ by one teacher i.e. there exists

i 0 ∈ [n] such that f i 0 = f i 0 and, for all i ∈ [n] \ {i 0 }, f i = f i .
This definition of adjacency is quite conservative and is strictly larger than the definition of adjacency from [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF] (indeed, in the assumption whereby the personal teacher databases d i are disjoint, changing one sample from a personal database changes at most one teacher).

Robustness against colluding teachers. As we have decided not to trust the aggregation server to generate the noise necessary to the privacy guarantees, we may also assume that a subset of teachers might be malicious and collude by communicating their generated noise, which gives the same DP guarantees from the point of view of a colluding teacher as if they would have not generated any noise and, to this extent, our protocol, which addresses this issue, is fault tolerant. The following theorem quantifies the privacy cost of such failures.

In the following, we call A the aggregation mechanism that outputs the argmax of the noisy counts. A(d, Q) is the output of A for the database d and the query Q. Let γ ∈ R * + be the inverse scale parameter of the distributed noise. Considering the DP guarantees from the point of view of an entity E, let τ ∈ (0, 1) be the ratio of the teachers whose noise is ignored by E.

Theorem 2 Let us define

I : v ∈ R * + → +∞ 0 (t + v) τ -1 t τ -1 e -2t dt and g : t ∈ R → +∞ γt e -v I(v)dv +∞ γ(t+2) e -v I(v)dv . Then, from E's point of view, A is ( , 0)-differentially private, with = log 1 + 2 γ 0 e -v I(v)dv +∞ 2γ e -v I(v)dv . Moreover, if τ > 1 2 , g is differentiable in 0 and A is ( , 0)-differentially private, with = min , log g(0) -g (0)
where

g (0) = γ Γ (τ ) 2 2 e -2γ I(2γ)-I(0) +∞ 2γ e -v I(v)dv ( +∞ 2γ e -v I(v)dv) 2 .
Sketch of proof. Adapting the proof of the privacy cost of the report noisy max from [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF], we first show that, if we can find a function M of γ and τ such that, for any t ∈ R, g(t) ≤ M , then A is (log(M ), 0)-differentially private. This motivates us to find an upper bound of g.

To do so, we prove that g has a maximum on R and that this maximum is reached on the interval [-1; 0]. On one hand, we show that, for all t ∈ [-1; 0],

g(t) ≤ 1 + 2 γ 0 e -v I(v)dv +∞ 2γ
e -v I(v)dv . On the other hand, we prove that, if besides τ > 1 2 , then g is concave on [argmax(g); 0] and thus, for all t ∈ [-1; 0], g(t) ≤ g(0) -g (0) (note that g is not differentiable in 0 if τ ≤ 1 2 ). Denoting S the subset of teachers who are honest (i.e. do not collude), this theorem allows us to control the privacy cost by the ratio τ of the teachers who kept their noise secret, from the point of view of both:

a colluding teacher, taking τ = |S| n an honest teacher, taking τ = n-1 n any entity who has access to the student model but is not a teacher, taking τ = 1

Note that we can also use Theorem 2 in the hypothesis whereby the colluding teachers publish their noise (to the whole world), adapting τ in consequence 6 . For τ = 1, the privacy guarantee is given by lim τ →1 which, as shown by Proposition 2, is the classical bound of the report noisy max with a centralised Laplace noise.

Proposition 2 For all γ ∈ R * + , lim τ →1 log(g(0) -g (0)) = 2γ.
Furthermore, Proposition 3 shows that, naturally, the privacy cost tends to be null when the noise becomes infinitely large (γ approaches 0).

Proposition 3 For all τ ∈ (0, 1), lim

γ→0 log 1 + 2 γ 2 0 e -v I(v)dv +∞ γ e -v I(v)dv = 0.
Let us also give an upper bound of the probability that the noisy argmax is different from the true argmax.

Proposition 4 Let k * be the class corresponding to the true argmax.

If τ ∈ ( 1 2 ; 1),

P[A(d; Q) = k * ] ≤ k =k * e -γ∆ k 1 2 + (γ∆ k ) 2τ -1 τ 2 4τ -2 Γ (τ ) 2 where ∆ k := n k * -n k for any k ∈ [K] and Γ : β ∈ R * + → +∞ 0
t β-1 e -t dt is the gamma function. If τ ∈ (0; 1 2 ],

P[A(d; Q) = k * ] ≤ k =k * e -γ∆ k 1 2 + (γ∆ k ) τ 2 τ 2 5 2 τ -1 Γ (τ ) 2 × 3 2 τ 3 2 τ 2 τ -3 1-3 2 τ
.

Sketch of proof. The event (A(d; Q) = k * ) is the union of the events (n k + Y k ≥ n k * + Y k * ), for k ∈ [K] \ {k * }, and thus P[A(d; Q) = k * ] ≤ k =k * P(n k + Y k ≥ n k * + Y k * ).
We remark that, for any k ∈ [K] \ {k * },

P(n k + Y k ≥ n k * + Y k * ) = P(Y k * ≤ Y k -∆ k ) = 0 -∞ f (t)F (t -∆ k )dt + ∆ k 0 f (t)F (t -∆ k )dt + +∞ ∆ k f (t)F (t -∆ k )dt where f : u ∈ R * → γ Γ (τ ) 2 e -γ|u| I(γ|u|) and F : t ∈ R → t -∞ f (u)du. We show that +∞ ∆ k f (t)F (t -∆ k )dt ≤ 3 8 e -γ∆ k and 0 -∞ f (t)F (t -∆ k )dt ≤ 1 8
e -γ∆ k . Moreover, using Hölder's inequality, we show that, for all q ∈ ( 1 1-τ ; +∞),

calling p := 1 1-1 q , ∆ k 0 f (t)F (t-∆ k )dt ≤ e -γ∆ k τ 2 4τ -2+ 1 q Γ (τ ) 2 × (γ∆ k ) 2τ -1+ 1 q p 1 p [q(1-τ )-1] 1 q
. For τ > 1 2 , we take the particular (and classic) case of the limit of the previous bound when q tends to +∞. For τ ≤ 1 2 , we take q = 1 1-3 2 τ . Theorem 2 and Proposition 4 serve as building blocks to which we apply the following theorem from [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF].

Theorem 3 ( [35]) Let , l ∈ R * + .
Let A be a ( , 0)-differentially private mechanism and q ≥ P[A(d) = k * ] for some outcome k * . If q < e -1 e 2 -1 , then for any additional information aux and any pair (d, d ) of adjacent databases, A satisfies

α A (l; aux, d, d ) ≤ min l, 2 l(l + 1) 2 , log (1 -q) 1 -q 1 -e q l + qe l .
As in [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF], Theorem 3 coupled with some properties of the moments accountant (composability and tail bound) allows one to devise the overall privacy budget ( , δ) for the learning procedure (see Section 6 for numerical results). We refer the interested reader to Section A of the appendix for more details and for the extended proofs of our claims.

Influence of the cryptographic layer. One must be aware that the cryptographic layer perturbates the noisy votes because the computation of the homomorphic argmax has a small probability of error. Although this topic deserves further investigations, we make the assumption that these perturbations are negligible and that they do not change the privacy guarantees as they basically constitute an additional noise on the votes. We further discuss this point in Appendix A.3.

Experimental results

The experiments presented below enable us to validate the accuracy of our framework on well-known image classification tasks and illustrate the practicality of our method in terms of performance, since the computational overhead due to the homomorphic layer remains reasonable. The source codes necessary to run the following experiments are available on https://github.com/Arnaud-GS/SPEED. HE time overhead. We implemented the homomorphic argmax computation presented in Section 4.3. Without parallelizing, a single argmax query requires just under 4 seconds to compute on an Intel Core i7-6600U CPU. Importantly, this does not depend on the input data. The costliest operation is the computation of θ. Any other part of the scheme is negligible in comparison. Therefore, once the parameters are set, the time performance depends solely on the number of classes (the number of bootstrap comparisons is quadratic in the number of classes). As such, 100 queries require 6.5 minutes and 1000 queries 65 minutes. Of course, the queries can be performed in parallel to decrease the latency allowing for much more challenging applications.

Homomorphic argmax accuracy. As we mention in Section 4.3, the homomorphic computation of the argmax is inherently probabilistic. This is due both to the noise added to any ciphertext at encryption time, and to limitations of the bootstrapping operation in terms of accuracy. On MNIST dataset [31], we evaluate the method with τ = 1/0.9/0.7 and compare the cleartext argmax to our homomorphic argmax. Our implementation of the HE argmax has an average accuracy of 99.4%, meaning that it retrieves the cleartext argmax 99.4% of the time. To obtain a more general and conservative measure of the inherent accuracy of the HE argmax (which can be applied on any dataset), we make the teachers give uniformly random answers to the queries. In this setting, most counts n k are likely to be close to one another, which makes even a classical argmax useless. This kind of scenario can be seen as worst-case, since the teacher voting is adversarial to argmax computation. Even in this scenario, and with the same parameters as for MNIST, our implementation of the HE argmax algorithm still produces an average accuracy of 90%. Hence, an accuracy of 90% can be considered a lower bound for any adaptation of this argmax technique to other datasets. Yet in practice a tweaking of the parameters can yield a better accuracy even for this worst-case scenario, at the cost of time efficiency.

Learning setup. To evaluate the performances of our framework, we test our method on MNIST [31] and SVHN [START_REF] Netzer | Reading digits in natural images with unsupervised feature learning[END_REF] datasets. To represent the data holders, we divide the training set in 250 equally distributed and disjoint subsets, keeping the test set for learning and evaluation of the student model. Then we apply the following procedures. We refer the interested reader to Section C of the appendix for more details on the hyper-parameters and learning procedure.

-Teacher models. For MNIST, given a dataset, a data holder builds a local model by stacking two convolutional layers with max pooling and a fully connected layer with ReLu activations. Two additional layers have been added for SVHN. -Student model. Following the idea from [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF], we train the student in a semisupervised fashion. Unlabelled inputs are used to estimate a good prior distribution using a GAN-based technique first introduced in [START_REF] Salimans | Improved techniques for training gans[END_REF]. Then we use a limited amount of queries (100 for MNIST, 500 for SVHN) to obtain labelled examples which we use to fine tune the model.

For MNIST experiments, as the student model can substantially vary based on the selected subset of labelled examples, the out-of-sample accuracy has been evaluated 15 times, with 100 labelled examples sampled from a set of 9000 ones.

For each experiment, the remaining 1000 examples have been used to evaluate the student model accuracy. For SVHN, the computations being much more heavy, the out-of-sample accuracy has been evaluated 3 times, with 500 examples sampled from a set of 10000 ones. We used 16032 examples to test the student model accuracy.

Performances on MNIST. Table 2 displays our experimental results for SPEED with MNIST and compares them to a non-private baseline (without DP or HE) and to the framework that we call Trusted which assumes that the server is trusted and thus only involves DP and not HE. Trusted can be considered as PATE framework from [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF] with some subtle differences: the noise is generated in a distributed way in Trusted and the notion of adjacency is larger. Even if the inverse noise scale γ we use is greater than the one in [START_REF] Papernot | Semi-supervised knowledge transfer for deep learning from private training data[END_REF] (0.1 instead of 0.05), which should lead to a worse DP guarantee, an argmax-specific analysis of the privacy cost per query allowed us to provide a better DP guarantee ( = 1.41 instead of = 2.04 with δ = 10 -5 and 100 queries). To be more conservative in terms of accuracy, the experiments were run considering that the colluding teachers did not generate any noise, which does not change anything in terms of DP. That is why, in spite of the variability of the accuracy, we observe a tradeoff between accuracy and DP. Indeed, even if the reported average accuracy does not vary much across conditions, consistent rankings of the methods have been observed, confirming the expected average rank of the method based on the amount of added noise. As expected, the best DP guarantee ( = 1.41) is obtained when all the teachers generated noise (τ = 1), but this is the case where the accuracy is the lowest. On the contrary, when some teachers failed to generate noise (τ = 0.9 and τ = 0.7), the counts are more precise, leading to a slightly better accuracy but worse DP guarantees. It should also be noted that the variance is high in each condition. It masks the fact that the distribution is highly skewed, with a majority of results in the 97.5% -98.5% range, and a few samplings yielding an out-of-sample accuracy around 90%.

Table 2 Results for MNIST dataset with 250 teachers and 100 student queries. We used an inverse noise scale γ = 0.1. The DP guarantees, computed by composability with the moments accountant method over the 100 queries, are given for δ = 10 -5 .

Framework

Acc Figure 2 shows the evolution of our DP guarantee as a function of γ, with τ = 0.9 fixed. Note that the privacy cost decreases for γ ≥ 2 which may seem counterintuitive but the reason is thoroughly explained in Section A.4 of the appendix. Anyway, we observed empirically that the privacy cost has a finite limit in +∞ (approximately 2.87) and remains greater than this limit for any γ ≥ 2. The asymptote is shown by a dashed line on Figure 2. Figure 3 shows the evolution of the DP guarantee as a function of τ , with γ = 0.1 fixed. As explained before, the greater τ , the better the DP guarantee.

Performances on SVHN. Table 3 presents our experimental results on SVHN dataset 7 . The variance on the accuracy is much smaller than for MNIST dataset because the test set is constituted of 16032 samples. Similarly to the MNIST experiment, the accuracy and the privacy cost increase when less noise is applied because less teachers noised their votes (i.e. when τ is small). The DP guarantees are not as good as for MNIST, this is due to the high amount of queries (500) necessary to obtain a good accuracy because the learning task is more complex.

Conclusion and open questions for further works

Our framework allows a group of agents to collaborate and put together their sensitive knowledge while protecting it via two complementary technologies -differential privacy and homomorphic encryption -against any entity contributing to the learning or having access to the final model. Crucially, our experiments showed that our method is practical for deep learning applications, combining high accuracy, mild computational overhead and privacy guarantees adapting to the number of malicious teachers.

An interesting further work could investigate the fault tolerance of the privacy guarantees with other noises (e.g. Gaussian noise) or other infinite divisions (Laplace distribution can also be infinitely divided using individual Gaussian noises or individual Laplace noises [START_REF] Goryczka | Secure multiparty aggregation with differential privacy: A comparative study[END_REF]). A more ambitious direction towards collaborative deep learning with privacy would be to design new aggregation operators, more suitable to FHE performances yet still providing good DP bounds. In particular, a linear or quadratic aggregation operator would be amenable to almost negligible homomorphic computations overhead. This lighter homomorphic layer would enable to extend the applicability of our framework to more complex datasets. Such aggregation operators would also allow to associate homomorphic calculations with verifiable computing techniques (e.g. [START_REF] Fiore | Efficiently verifiable computation on encrypted data[END_REF]) whereby the server would provide an encrypted aggregation result along with a formal proof that aggregation was indeed done correctly. These perspectives would then allow to address threats beyond the honest-but-curious model.

Declarations

Funding

The experiments were performed using HPC resources of FactoryIA partially funded by Ile-de-France French region -project SESAME 2017.

Conflicts of interest/Competing interests

Not applicable.

Availability of data and material

The MNIST [31] and SVHN [START_REF] Netzer | Reading digits in natural images with unsupervised feature learning[END_REF] datasets can be found respectively at http:// yann.lecun.com/exdb/mnist/ and http://ufldl.stanford.edu/housenumbers/.

Code availability

The source codes used to run the experiments and compute the DP guarantees can be accessed on https://github.com/Arnaud-GS/SPEED.

where the maximum is taken over any auxiliary input aux and any pair of adjacent databases d, d and α M (l; aux, d, d ) := log E exp(lC(M, aux, d, d )) is the moment generating function of the privacy loss random variable.

Theorem 3 ([8]) Let , l ∈ R * + .
Let M be a ( , 0)-differentially private mechanism and q ≥ P[M(d) = k * ] for some outcome k * . If q < e -1 e 2 -1 , then for any aux and any pair d, d of adjacent databases, M satisfies α M (l; aux, d, d ) ≤ min l, 2 l(l + 1)

2

, log (1 -q) 1 -q 1 -e q l + qe l .

3

Using the moments accountant per query, we evaluate the overall moments accountant by composability, applying the following theorem from [1].

Theorem 4 ([1]) Let p ∈ N * .
Let us consider a mechanism M defined on a set D that consists of a sequence of adaptive mechanisms M 1 , . . . , M p where, for any

i ∈ [p], M i : i-1 j=1 R j × D → R i . Then, for any l ∈ R * + , α M (l) ≤ p i=1 α M i (l).
Finally, parameter δ being chosen, the privacy guarantee is derived from the overall moments accountant applying the tail bound property, stated in Theorem 5 from [1].

Theorem 5 ([1]) For any ∈ R * + , the mechanism M is ( , δ)-differentially pri- vate for δ = min l∈N * exp(α M (l) -l ).
Algorithm 1: Algorithm to determine the overall privacy guarantee of the learning procedure Input : number of teachers n, number of classes K, ratio τ of teachers with secret noise, set of queries Q, unnoisy teachers' counts n k , inverse noise scale γ, l max a , δ Output: for l in [l max ] do α(l) ← 0 for query Q in Q do Compute the privacy cost of Q and an upperbound of

P[A(d; Q) = k * ]; Derive the moments accountant α Q (l) with Theorem 3; α(l) ← α(l) + α Q (l); end (l) ← α(l)-δ l ; end ← min l∈[l max ] (l);
a To determine the DP guarantees presented in the paper, we took lmax = 25 because it seems empirically that it captures the best moments accountant in every case.

A.2 DP guarantee per query in the BHBC framework

Preliminaries on the generalised Laplace distribution. For every teacher j who did send noise and whose noise is secret, the noise sent by j is distributed as G

(j) 1 -G (j) 2
where G (j) 1 and G (j) 2 are two i.i.d. random variables with gamma density u →

1 1 γ 1 n Γ ( 1 n ) u 1 n -1 e -γu and characteristic function t → 1 1-i t γ 1 n
(see [6]). Hence, the characteristic function of

G (j) 1 -G (j) 2 is ψ : t → 1 1+ t γ 2 1 n
. By summing over all the teachers who did send a secret noise, we get a total noise whose characteristic

function is ψ τ n : t → 1 1+ t γ 2 τ
. The corresponding moment generating function

is t → 1 1-t γ 2 τ
. According to [7], this is the moment generating function of a generalised Laplace distribution whose density is

f γ,τ : u ∈ R * →      1 1 γ 2τ Γ (τ ) 2 e γu +∞ u t τ -1 (t -u) τ -1 e -2γt dt if u > 0 1 1 γ 2τ Γ (τ ) 2 e γu +∞ 0 t τ -1 (t -u) τ -1 e -2γt dt if u < 0 which is actually u ∈ R * → 1 1 γ 2τ Γ (τ ) 2 e γ|u| +∞ |u| t τ -1 (t -|u|) τ -1 e -2γt dt = γ 2τ -1 Γ (τ ) 2 e γ|u| +∞ 0 v γ + |u| τ -1 v γ τ -1 e -2(v+γ|u|) dv (by the substitution v = γ(t -|u|)) = L γ,τ e -γ|u| I τ (γ|u|)
where

I τ : v ∈ R * + → +∞ 0 (x + v) τ -1 x τ -1 e -2x dx and L γ,τ = γ Γ (τ ) 2 .
Let us remark that, since τ -1 ≤ 0, I τ is decreasing on R * + . As a density function, f γ,τ is integrable on R (it can also be proved using Lemma 4). We call F γ,τ the associated cumulative distribution function:

F γ,τ : t ∈ R → t -∞ f γ,τ (u)du Note that, lim +∞ F γ,τ = 1 and, since f γ,τ is pair, F γ,τ (0) = 1 2 and ∀t ∈ R, F γ,τ (t) + F γ,τ (-t) = 1. ( 1
)
If there is no ambiguity on the parameters γ and τ , we will only write f , F , I and L.

Lemma 1 Let r be a random variable following the generalised Laplace distribution as defined above. Suppose that we can find a function M of γ and τ such that, for any t ∈ R, P[r≥t] P[r≥t+2] ≤ M . Then A is (log(M ), 0)-differentially private.

Proof We will mimic the proof of the privacy guarantee of the report noisy max from [5] (Claim 3.9), but with two key adaptations.

First of all, let us warn that our definition of the adjacence of two databases is different from the one of [5]. Changing one teacher is analogous to changing one individual in the counting queries context. This is why the hypotheses must be adapted. Indeed, d and d being two adjacent databases (in our sense), since at most one teacher will change its vote between d and d , we have the property |n k -n k | ≤ 1 for any k ∈ [K] but we do not have the property of monotonicity of the counts used in [5] 2 .

The second difference is that, r being a random variable following the generalised Laplace distribution, we have to substitute the classical upperbound e 2γ (valid for the Laplace distribution) of P[r≥t] P[r≥t+2] by M . We consider a query

Q. Let k 0 ∈ [K].
For any event E, we write P[E|r -k 0 ] the probability of E under the condition that the draw from the (K -1)-dimensional generalised Laplace distribution, used for all the noisy counts except the k 0 -th count, is equal to r -k 0 . We now suppose this draw r -k 0 fixed.

We define r * = min{r

k 0 |∀k ∈ [K] \ {k 0 }, n k 0 + r k 0 ≥ n k + r k }.
Note that, whatever is the tie-breaking policy, r -k 0 being fixed, k 0 is the output of A for database

d if r k 0 > r * and k 0 is not the output of A if r k 0 < r * . Since P[r k 0 = r * ] = 0, we have P[A(d, Q) = k 0 |r -k 0 ] = P[r k 0 > r * ] = P[r k 0 ≥ r * ]. Moreover, for all k ∈ [K] \ {k 0 }, n k 0 + r * + 2 ≥ n k 0 + r * + 1 (because |n k 0 -n k 0 | ≤ 1) ≥ n k + r k + 1 (by definition of r * ) ≥ n k + r k (because |n k 0 -n k 0 | ≤ 1)
We deduce that, if r k 0 > r * + 2, then k 0 is the output of A for database d . Therefore,

P[A(d , Q) = k 0 |r -k 0 ] ≥ P[r k 0 > r * + 2] = P[r k 0 ≥ r * + 2]. Since P[r k 0 ≥ r * ] ≤ M P[r k 0 ≥ r * + 2]
by assumption, we can deduce that

P[A(d, Q) = k 0 |r -k 0 ] ≤ M P[A(d , Q) = k 0 |r -k 0 ]
. This being true for any draw r -k 0 , the law of total probability gives us

P[A(d, Q) = k 0 ] ≤ M P[A(d , Q) = k 0 ].
As d and d play perfectly symmetric roles (unlike in the proof of the report noisy max guarantee from [5]), we also have

P[A(d , Q) = k 0 ] ≤ M P[A(d, Q) = k 0 ]
. Since this is true for any query Q, we can conclude that A is (log(M ), 0)differentially private.

By definition of F , r being a random variable following the generalised Laplace distribution, for all t ∈ R, P[r ≥ t] = 1 -F (t). 2 We could have consider a database d such that d is adjacent to d and d is adjacent to d with Dwork's definition. Then we could have applied twice the result of [5] (using M instead of e γ as upper bound of for (d, d) and( d, d )). Nevertheless, we performed numerical experimentations that make us believe that it would have given worse privacy guarantees than the present result.

P[r≥t] P[r≥t+2]
Let a ∈ R * + . In the following, we exhibit upper bounds of g : t ∈ R → 1-F (t) 1-F (t+a) (Propositions 5 and 6) to derive privacy guarantees for A (Theorem 2) taking a = 2. Let us first state some useful lemmas.

Lemma 2 Let β ∈ R + . The application h : v ∈ R * + → I(v) I(v+β) is decreasing.
Proof We will prove that h is differentiable and that its derivative is non-positive.

Let φ : (v, t) ∈ (R * + ) 2 → (t + v) τ -1 t τ -1 e -2γt
. φ has a partial derivative in the first variable and, for all (v, t)

∈ (R * + ) 2 , ∂φ ∂v (v, t) = (τ -1) (t + v) τ -2 t τ -1 e -2γt
. φ and ∂φ ∂v are continuous in both variables.

Let b ∈ R * + . For all (v, t) ∈ [b, +∞) × R * + , | ∂φ ∂v (v, t)| ≤ ψ(t) where ψ : t ∈ R * + → (1 -τ ) (t + b) τ -2 t τ -1 e -2γt
. ψ is continuous and integrable on [b, +∞). Applying Leibniz's theorem, we deduce that I is differentiable on [b, +∞) and that, for all v ∈ [b, +∞),

I (v) = +∞ 0 (τ -1) (t + v) τ -2 t τ -1 e -2γt dt. Since this is true for all b ∈ R * + , we know that I is differentiable on R * + and that, for all v ∈ R * + , I (v) = +∞ 0 (τ -1) (t + v) τ -2 t τ -1 e -2γt dt. As a consequence, h is differentiable on R * + and, for all v ∈ R * + , h (v) = I(v+β)I (v)-I(v)I (v+β) I(v+β) 2 . Let v ∈ R * + . I(v + β)I (v) -I(v)I (v + β) = +∞ 0 (x + v + β) τ -1 x τ -1 e -2x dx × +∞ 0 (τ -1) (y + v) τ -2 y τ -1 e -2y dy - +∞ 0 (y + v) τ -1 y τ -1 e -2y dy × +∞ 0 (τ -1) (x + v + β) τ -2 x τ -1 e -2x dx = (τ -1) +∞ 0 (x + v + β) τ -1 x τ -1 e -2x +∞ 0 (y + v) τ -2 y τ -1 e -2y dydx - +∞ 0 (x + v + β) τ -2 x τ -1 e -2x +∞ 0 (y + v) τ -1 y τ -1 e -2y dydx = (τ -1) +∞ 0 +∞ 0 (x + v + β) τ -1 (y + v) τ -2 (xy) τ -1 e -2(x+y) dydx - +∞ 0 +∞ 0 (x + v + β) τ -2 (y + v) τ -1 (xy) τ -1 e -2(x+y) dydx = (τ -1) +∞ 0 +∞ 0 (xy) τ -1 e -2(x+y) × (x + v + β) τ -1 (y + v) τ -2 -(x + v + β) τ -2 (y + v) τ -1 dydx = (τ -1) +∞ 0 +∞ 0 (x + v + β) τ -2 (y + v) τ -2 (xy) τ -1 e -2(x+y) × [(x + v + β) -(y + v)] dydx = (τ -1) +∞ 0 +∞ 0 (x + v + β) τ -2 (y + v) τ -2 (xy) τ -1 e -2(x+y) × (x + β -y) dydx ≤ (τ -1) +∞ 0 +∞ 0 (x + v + β) τ -2 (y + v) τ -2 (xy) τ -1 e -2(x+y) (x -y)dydx (2)
(because τ -1 ≤ 0 and β ≥ 0)

Similarly, we show that

I(v + β)I (v) -I(v)I (v + β) = +∞ 0 (y + v + β) τ -1 y τ -1 e -2y dy × +∞ 0 (τ -1) (x + v) τ -2 x τ -1 e -2x dx - +∞ 0 (x + v) τ -1 x τ -1 e -2x dx × +∞ 0 (τ -1) (y + v + β) τ -2 y τ -1 e -2y dy = (τ -1) +∞ 0 (x + v) τ -2 x τ -1 e -2x +∞ 0 (y + v + β) τ -1 y τ -1 e -2y dydx - +∞ 0 (x + v) τ -1 x τ -1 e -2x +∞ 0 (y + v + β) τ -2 y τ -1 e -2y dydx = (τ -1) +∞ 0 +∞ 0 (xy) τ -1 e -2(x+y) × (x + v) τ -2 (y + v + β) τ -1 -(x + v) τ -1 (y + v + β) τ -2 dydx = (τ -1) +∞ 0 +∞ 0 (x + v) τ -2 (y + v + β) τ -2 (xy) τ -1 e -2(x+y) × (y + β -x)dydx ≤ (τ -1) +∞ 0 +∞ 0 (x + v) τ -2 (y + v + β) τ -2 (xy) τ -1 e -2(x+y) (y -x)dydx (3)
Alternatively, we can use 2 to deduce 3 directly using Fubini's theorem and exchanging the roles of x and y.

From 2 and 3, we get:

2 × I(v + β)I (v) -I(v)I (v + β) ≤ (τ -1) +∞ 0 +∞ 0 (x + v + β) τ -2 (y + v) τ -2 (x -y) (xy) τ -1 e -2(x+y) dydx + (τ -1) +∞ 0 +∞ 0 (x + v) τ -2 (y + v + β) τ -2 (y -x) (xy) τ -1 e -2(x+y) dydx = (τ -1) +∞ 0 +∞ 0 (x -y) (xy) τ -1 e -2(x+y) × (x + v + β) τ -2 (y + v) τ -2 -(x + v) τ -2 (y + v + β) τ -2 dydx Let (x, y) ∈ (R * + ) 2 . Note that (x + v + β) (y + v) -(x + v) (y + v + β) = β(y -x) and then (x + v + β) τ -2 (y + v) τ -2 ≥ (x + v) τ -2 (y + v + β) τ -2 ⇔ (x + v + β) (y + v) ≤ (x + v) (y + v + β) (because τ -2 < 0) ⇔ x ≥ y.
We deduce that

(x + v + β) τ -2 (y + v) τ -2 -(x + v) τ -2 (y + v + β) τ -2 (x -y) ≥ 0.
This inequality being true for all (x, y) ∈ (R * + ) 2 and, since τ -1 ≤ 0, we have:

(τ -1) +∞ 0 +∞ 0 (x + v + β) τ -2 (y + v) τ -2 -(x + v) τ -2 (y + v + β) τ -2 × (x -y) (xy) τ -1 e -2(x+y) dydx ≤ 0 Finally, I(v + β)I (v) -I(v)I (v + β) ≤ 0 and h (v) ≤ 0.
Since this is true for any v ∈ R * + , we can conclude that h is decreasing on R * + .

Lemma 3

The function g has a maximum on R, and this maximum is reached in the interval [-a 2 ; 0].

Proof Since f is defined on R * , F is differentiable on R * . Thus g is differentiable on R * \ {-a} and, for all t ∈ R * \ {-a}, g (t) = (1 -F (t))f (t + a) -(1 -F (t + a))f (t) (1 -F (t + a)) 2 .
First of all, let us prove that g is increasing on (-∞; -a 2 ). For all t ∈ (-∞; -a), |t| = -t ≥ -t -a = |t + a| and, for all t ∈ (-a;

-a 2 ), |t| = -t ≥ t + a = |t + a|. Let t ∈ (-∞; -a) ∪ (-a; -a 2 )
. Then, since x → e -γx I(γx) is decreasing on R * + , e -γ|t| I(γ|t|) ≤ e -γ|t+a| I(γ|t + a|) which means f (t) ≤ f (t + a). Besides, F is increasing then, since a ≥ 0, 1 -F (t + a) ≤ 1 -F (t). Since f (t), f (t + a), 1 -F (t) and 1 -F (t) are all positive quantities, we deduce that g (t) ≥ 0. Then, g is increasing on (-∞; -a) and on (-a; -a 2 ) and since g is defined and continuous in -a, g is increasing on (-∞; -a 2 ). Let us now prove that g is decreasing on R + . Let t ∈ R * + .

( ] du ≤ 0 and finally g (t) ≤ 0. This being valid for all t ∈ R * + and g being continuous in 0, we deduce that g is decreasing on R + .

-F (t + a)) 2 L 2 g (t) = 1 L 2 [(1 -F (t))f (t + a) -(1 -F (t + a))f 1
From the two previous discussions and from the fact that g is continuous on [-a 2 ; 0], we conclude that g has a maximum on R and that this maximum is reached in [-a 2 ; 0].

Proposition 5 For all t ∈ [-a 2 ; 0],

g(t) ≤ 1 + 2 γa 2 0 e -v I(v)dv +∞ γa e -v I(v)dv .
Proof For all t ∈ [-a 2 ; 0],

g(t) = 1 + F (t + a) -F (t) 1 -F (t + a) . Calling φ : t ∈ [-a 2 ; 0] → F (t + a) -F (t), we know that φ is differentiable on [-a 2 ; 0) and that φ : t ∈ [-a 2 ; 0) → f (t + a) -f (t). Since x ∈ R * + → e -x I(x)
is decreasing, we have, for all t ∈ [-a 2 ; 0), φ (t) ≥ 0 ⇔ e -γ|t+a| I(γ|t + a|) ≥ e -γ|t| I(γ|t|)

⇔ |t + a| ≤ |t| ⇔ t + a ≤ -t (because t + a ≥ 0 and t ≤ 0) ⇔ t ≤ - a 2
Since φ is continuous in 0, we deduce that φ is decreasing on [-a 2 ; 0] and then, for all t ∈ [-a 2 ; 0], F (t+a)-F (t) ≤ F ( a 2 )-F (-a 2 ). Moreover, since F is increasing, for all t ∈ [-a 2 ; 0], 1 -F (t + a) ≥ 1 -F (a). Finally, for all t ∈ [-a 2 ; 0], . For all t ∈ [-a 2 ; 0],

g(t) ≤ 1 + F ( a 2 ) -F (-a 2 ) 1 -F (a) = 1 + L a 2 -a 2 e -γ|u| I(γ|u|)du L +∞ a e -γ|u| I(γ|u|)du = 1 + L γ γa 2 -γa
g(t) ≤ g(0) - a 2 g (0). with g (0) = γ Γ (τ ) 2 2 e -γa I(γa) -I(0) +∞ γa e -v I(v)dv +∞ γa e -v I(v)dv 2 .
Proof The result basically comes from the fact that g is concave on [argmax(g); 0] which we prove hereafter.

From the proof of Lemma 3 we know that g is differentiable on [-a 2 ; 0) and

g : t → (1-F (t))f (t+a)-(1-F (t+a))f (t) (1-F (t+a)) 2 = g(t)f (t+a)-f (t) 1-F (t+a)
. In the proof of Lemma 2, we saw that I is differentiable on R * + and thus f is differentiable on R * + . Finally, we get that g is differentiable on (-a; 0) and, for all t ∈ (-a; 0),

g (t) = 1 (1 -F (t + a)) 2 (1 -F (t + a))[g (t)f (t + a) + g(t)f (t + a) -f (t)] +f (t + a)[g(t)f (t + a) -f (t)]] = 1 (1 -F (t + a)) 2 (1 -F (t + a))[g (t)f (t + a) + g(t)f (t + a) -f (t)] +(1 -F (t + a))f (t + a)g (t) = 2g (t) f (t + a) 1 -F (t + a) + (1 -F (t + a))[g(t)f (t + a) -f (t)] (1 -F (t + a)) 2 = 2g (t) f (t + a) 1 -F (t + a) + (1 -F (t))f (t + a) -(1 -F (t + a))f (t) (1 -F (t + a)) 2 .
Since I is strictly negative on R * + , for all u < 0, f (u) = Lγ[e γu I(-γu)e γu I (-γu)] > 0 and, for all u > 0, f (u) = Lγ[-e -γu I(γu) + e -γu I (γu)] < 0. Then, for all t ∈ (-a; 0), f (t) > 0 and f (t + a) < 0 and, since 1 -F (t) > 0 and 1 -F (t + a) > 0, (1 -F (t))f (t + a) < 0 and (1 -F (t + a))f (t) > 0. We deduce that, for all t ∈ (-a; 0),

g (t) < 2g (t) f (t + a) 1 -F (t + a) + (1 -F (t))f (t + a) (1 -F (t + a)) 2 (4)
where 2 f (t+a) 1-F (t+a) > 0 and (1-F (t))f (t+a)

(1-F (t+a)) 2 < 0. According to Lemma 3, g has a maximum, which is reached on [-a 2 ; 0]. Let t max = argmax(g). If t max = 0, we can argue that g (t max ) = 0 and then, from Inequation 4, g is strictly negative on a neighbourhood of t max . This implies that g is decreasing on a neighbourhood of (t max ) + and then strictly negative on a neighbourhood of (t max ) + .

Removing the assumption that t max = 0, we need to be slightly more subtle since g is not differentiable in 0 (because I is not differentiable in 0).

Since τ > 1 2 , v → v 2τ -2 e -2v is integrable on R * + and we can extend the definition of I to R + . This implies in particular that F and then g are differentiable on the whole interval (-a; +∞) (with

g (0) = (1-F (0))f (a)-(1-F (a))f (0) (1-F (a)) 2
). Then g (t max ) = 0 and, from Inequation 4, lim (t max ) + g < (1-F (t max ))f (t max +a)

(1-F (t max +a)) 2 < 0. Thus g (not defined in 0) is strictly negative on a neighbourhood of (t max ) + . Then g is strictly decreasing on a neighbourhood of (t max ) + and, by continuity in t max , strictly negative on a neighbourhood of (t max ) + . Let us suppose that g (t) ≥ 0 for a t in [t max ; 0) (trivially false if t max = 0 since [t max ; 0) is empty in this case). We fix such a t and call it t 0 . Then, from Inequation 4, g (t 0 ) > 0 and we can fix t 1 = inf{t ∈ [t max ; t 0 ]|g (t) ≥ 0}. g is non-negative on a neighbourhood of (t 1 ) + thus t 1 > t max . We also know that g is non-positive on [t max ; t 1 ) by definition of t 1 . This implies g (t 1 ) = 0. Since g (t 1 ) = 0, from Inequation 4, we know that g (t 1 ) < 0 and then g is strictly negative on a neighbourhood of (t 1 ) + . We get a contradiction so g (t) < 0 for all t ∈ [t max ; 0). We deduce that g is decreasing on [t max ; 0).

Thus, for all t ∈ [t max ; 0), g (t) ≥ g (0). As a consequence, since t max ≤ 0, g(t max ) ≤ g(0) + t max g (0). Besides, t max ≥ -a 2 and g (0) ≤ g (t max ) = 0, thus g(t max ) ≤ g(0) -a 2 g (0). Finally, by definition of t max , for all t ∈ R,

g(t) ≤ g(0) - a 2 g (0)
with Moreover, if τ > 1 2 , g is differentiable in 0 and A is ( , 0)-differentially private, with = min , log g(0) -g (0) .

g (0) = (1 -F (0))f (a) -(1 -F (a))f (0) (1 -F (a)) 2
Proof Thanks to Lemma 3, we can use Propositions 5 and 6 to upper bound g, for a = 2. We then just have to apply Lemma 1 to conclude.

Lemma 4 For all v ∈ R * + , I(v) ≤ v τ -1 Γ (τ ) 2 τ . Proof Let v ∈ R * + . I(v) = +∞ 0 (t + v) τ -1 t τ -1 e -2t dt ≤ v τ -1 +∞ 0 t τ -1 e -2t dt (because τ -1 ≤ 0) = v τ -1 +∞ 0 u 2 τ -1 e -u du 2 (by the substitution u = 2t) = v τ -1 Γ (τ ) 2 τ
Proposition 3 For all τ ∈ (0, 1), lim Applying Lemma 4, we get

γ 0 e -v I(v)dv ≤ Γ (τ ) 2 τ γ 0 e -v v τ -1 dv ≤ Γ (τ ) 2 τ γ 0 v τ -1 dv = Γ (τ ) 2 τ γ τ τ which gives lim γ→0 γ 0 e -v I(v)dv = 0.
Proposition 2 For all γ ∈ R * + , lim τ →1 log g(0) -g (0) = 2γ.

Proof We use the dominated convergence theorem to determine the limit of f and F when τ approaches 1. Let us suppose in the following that τ ∈ ( 3 4 ; 1). First of all, we determine the limit of I and deduce the one of f . Let v ∈ R + . For all x ∈ (0; 1], (x + v) τ -1 x τ -1 e -2x ≤ x 2τ -2 e -2x ≤ x -1 2 e -2x . As x → x -1 2 e -2x is integrable on (0; 1], and, for all x ∈ (0; 1], lim τ →1 (x + v) τ -1 x τ -1 e -2x = e -2x , by the dominated convergence theorem we get that lim

τ →1 1 0 (x + v) τ -1 x τ -1 e -2x dx = 1 0 e -2x dx.
Similarly, as, for all x ∈ [1; +∞), (x + v) τ -1 x τ -1 e -2x ≤ e -2x and lim

τ →1 (x + v) τ -1 x τ -1 e -2x = e -2x
, by the dominated convergence theorem,

lim τ →1 +∞ 1 (x + v) τ -1 x τ -1 e -2x dx = +∞ 1 e -2x dx.
From the two points above, we deduce that lim From what precedes we can conclude that, with a = 2,

τ →1 I(v) = lim τ →1 1 0 (x + v) τ -1 x τ -1 e -2x dx + +∞ 1 (x + v) τ -1 x τ -1 e -2x dx
lim τ →1 g(0) -g (0) = lim τ →1 1 -F (0) 1 -F (2) - (1 -F (0))f (2) -(1 -F (2))f (0) (1 -F (2)) 2 = 1 2 1 2 e -2γ - 1 2 1 2 × 1 2 γe -2γ -1 2 e -2γ × 1 2 γ ( 1 2 e -2γ ) 2 = e 2γ A.

Influence of the HE layer on the DP guarantee per query

The computation of the homomorphic argmax induces some perturbations on the noisy counts and, as such, could harm the DP guarantees that we just gave. The three kinds of perturbations due to the HE layer are:

the addition of (Gaussian) noise at the time of TFHE encryption which is inherently probabilistic the addition of a constant value A on the noisy counts to ensure that all the noisy counts are positive (with high probability) (see Section B) a possible mistake on the argmax if two noisy counts are too close (see Section 6 of the main paper)

While these perturbations can be seen as some postprocessing applied on the clear noisy histogram, they cannot be seen as a postprocessing on the clear noisy argmax on which we showed DP guarantees in Section A.2. Nevertheless, if we can prove that these perturbations consist of an addition of noise on the clear histogram, the upper bound on P [r≥t] P[r≥t+2] , r being the total noise (generalised Laplace noise and HE perturbations) applied to the histogram of the n k 's, would still hold, leading to the same DP guarantees. The additions of Gaussian noise and constant A at encryption have, by commutativity, the same effect as the addition of a sum of Gaussian noises and nA after summation and they will anyway change the output of the homomorphic argmax with very low probability. However, some further work needs to be done in order to check whether the third kind of perturbation can be simulated as a noise addition on the histogram.

A.4 Upper bound of the probability of a report noisy max mistake

In this subsection, we give an upper bound of the probability that A outputs a wrong argmax because of the added noise following the generalised Laplace distribution.

Lemma 5 Let u 0 ∈ R + . Let q ∈ 1 1-τ ; +∞ and p := 1 1-1 q . We have +∞ u 0 e -γu I(γu)du ≤ Γ (τ ) 2 τ γ e -γu 0 p 1 p (γu 0 ) τ -1+ 1 q [q(1 -τ ) -1] 1 q . Proof Let u 0 ∈ R + . Let (p, q) ∈ (R * + ) 2 such that 1 p + 1 q = 1 and q > 1 1-τ . +∞ u 0 e -γu I(γu)du ≤ Γ (τ ) 2 τ +∞ u 0 e -γu (γu) τ -1 du (according to Lemma 4) = Γ (τ ) 2 τ γ +∞ γu 0 e -v v τ -1 dv (by the substitution v = γu)
By assumption, q > 1 1-τ so, since τ < 1, q(τ -1) < -1 and then v ∈ R * + → v q(τ -1) is integrable in the neighbourhood of +∞. Then we can apply Hölder's inequality in the following manner:

+∞ u 0 e -γu I(γu)du ≤ Γ (τ ) 2 τ γ +∞ γu 0 e -pv dv 1 p +∞ γu 0 v q(τ -1) dv 1 q = Γ (τ ) 2 τ γ × e -pγu 0 p 1 p
× -(γu 0 ) q(τ -1)+1 (q(τ -1) + 1)

1 q = Γ (τ ) 2 τ γ × e -γu 0 p 1 p × (γu 0 ) τ -1+ 1 q [q(1 -τ ) -1] 1 q Lemma 6 Let us consider a query Q. Let k * ∈ [K] be the unnoisy argmax (for all k ∈ [K], n k * ≥ n k ). For all k ∈ [K], we define ∆ k := n k * -n k ≥ 0. Then, for all q ∈ ( 1 1-τ ; +∞), calling p := 1 1-1 q , P[A(d, Q) = k * ] ≤ k =k * e -γ∆ k 1 2 + 1 τ 2 4τ -2+ 1 q Γ (τ ) 2 × (γ∆ k ) 2τ -1+ 1 q p 1 p [q(1 -τ ) -1] 1 q
.

Proof In the following, we will assume that ∆ k > 0 and the upper bound for ∆ k = 0 is obtained by continuity. For any k ∈ [K], let us denote Y k the random variable following the generalised Laplace distribution generated by the sum of the τ n individual noises.

Let k ∈ [K].

P(n k + Y k ≥ n k * + Y k * ) = P(Y k * ≤ Y k -∆ k ) = +∞ -∞ f (t)F (t -∆ k )dt = 0 -∞ f (t)F (t -∆ k )dt + ∆ k 0 f (t)F (t -∆ k )dt + +∞ ∆ k f (t)F (t -∆ k )dt (5)
We will now upper bound each one of the three above integrals separately. The two extreme integrals can be nicely bounded by decreasing exponentials in ∆ k :

+∞ ∆ k f (t)F (t -∆ k )dt = +∞ 0 f (v + ∆ k )F (v)dv (by the substitution v = t -∆ k ) = L +∞ 0 e -γ|v+∆ k | I(γ|v + ∆ k |)F (v)dv = L +∞ 0 e -γ(v+∆ k ) I(γ(v + ∆ k ))F (v)dv = Le -γ∆ k +∞ 0 e -γv I(γ(v + ∆ k ))F (v)dv ≤ Le -γ∆ k +∞ 0 e -γv I(γv)F (v)dv (because I is decreasing) = Le -γ∆ k +∞ 0 e -γ|v| I(γ|v|)F (v)dv = e -γ∆ k +∞ 0 f (v)F (v)dv = e -γ∆ k × lim +∞ F 2 -F (0) 2 2 = e -γ∆ k × 1 -1 4 2 = 3 8 e -γ∆ k (6)
and

0 -∞ f (t)F (t -∆ k )dt = L 0 -∞ f (t) t-∆ k -∞ e -γ|u| I(γ|u|)dudt = L 0 -∞ f (t) t-∆ k -∞ e γu I(-γu)dudt = L 0 -∞ f (t) t -∞ e γ(v-∆ k ) I(γ(∆ k -v))dudt (by the substitution v = u + ∆ k ) = Le -γ∆ k 0 -∞ f (t) t -∞ e γv I(γ(∆ k -v))dudt ≤ Le -γ∆ k 0 -∞ f (t) t -∞ e γv I(-γv)dudt (because I is decreasing) = Le -γ∆ k 0 -∞ f (t) t -∞ e -γ|v| I(γ|v|)dudt = e -γ∆ k 0 -∞ f (t)F (t)dt = e -γ∆ k × F (0) 2 -lim -∞ F 2 2 = 1 8 e -γ∆ k . (7)
As for the middle integral, we have

∆ k 0 f (t)F (t -∆ k )dt = L ∆ k 0 f (t) t-∆ k -∞ e -γ|u| I(γ|u|)dudt = L ∆ k 0 f (t) +∞ ∆ k -t e -γ|v| I(γ|v|)dvdt (by the substitution v = -u) = L ∆ k 0 f (t) +∞ ∆ k -t e -γv I(γv)dvdt
Since, for all t ∈ [0; ∆ k ], 0 ≤ ∆ k -t, we can apply Lemma 5. Let q ∈ 1 1-τ ; +∞ and p = 1 1-1 q . We have, for all t ∈ (0; ∆ k ),

+∞ ∆ k -t e -γv I(γv)dv ≤ Γ (τ ) 2 τ γ × 1 p 1 p [q(1-τ )-1] 1 q × e -γ(∆ k -t) [γ(∆ k -t)] τ -1+ 1 q . Since τ -1 + 1 q > -1, t → [γ(∆ k -t)] τ -1+ 1 q is integrable on a neighbourhood of (∆ k ) -and then, since t → f (t)e -γ(∆ k -t) is bounded on a neighbourhood of ∆ k , t → f (t)e -γ(∆ k -t) [γ(∆ k - t)] τ -1+ 1
q is integrable on a neighbourhood of (∆ k ) -. Thus, we can write

∆ k 0 f (t)F (t -∆ k )dt ≤ L Γ (τ ) 2 τ γ × 1 p 1 p [q(1 -τ ) -1] 1 q × ∆ k 0 f (t)e -γ(∆ k -t) [γ(∆ k -t)] τ -1+ 1 q dt = L 2 Γ (τ ) 2 τ γ × 1 p 1 p [q(1 -τ ) -1] 1 q × ∆ k 0 e -γ|t| I(γ|t|)e -γ(∆ k -t) [γ(∆ k -t)] τ -1+ 1 q dt = γ 2 τ Γ (τ ) 3 × 1 p 1 p [q(1 -τ ) -1] 1 q × ∆ k 0 e -γt I(γt)e -γ(∆ k -t) [γ(∆ k -t)] τ -1+ 1 q dt = e -γ∆ k 2 τ Γ (τ ) 3 × γ p 1 p [q(1 -τ ) -1] 1 q × ∆ k 0 I(γt)[γ(∆ k -t)]
τ -1+ 1 q dt t → (γt) τ -1 is integrable on a neighbourhood of 0 + because τ -1 > -1. Therefore, t → (γt) τ -1 Γ (τ ) 2 τ [γ(∆ k -t)]

τ -1+ 1 q is integrable on (0; ∆ k ) so we can apply Lemma 4:

∆ k 0 f (t)F (t -∆ k )dt ≤ e -γ∆ k 2 τ Γ (τ ) 3 × γ p 1 p [q(1 -τ ) -1] 1 q × ∆ k 0 (γt) τ -1 Γ (τ ) 2 τ [γ(∆ k -t)] τ -1+ 1 q dt = e -γ∆ k 2 2τ Γ (τ ) 2 × γ∆ k p 1 p [q(1 -τ ) -1] 1 q × 1 0 (γ∆ k u) τ -1 [γ(∆ k -∆ k u)] τ -1+ 1 q du (by the substitution u = t ∆ k ) = e -γ∆ k 2 2τ Γ (τ ) 2 × (γ∆ k ) 2τ -1+ 1 q p 1 p [q(1 -τ ) -1] 1 q × 1 0 u τ -1 (1 -u) τ -1+ 1 q du Note that 1 0 u τ -1 (1 -u) τ -1+ 1 q du = 1 2 0 u τ -1 (1 -u) τ -1+ 1 q du + 1 1 2 u τ -1 (1 -u) τ -1+ 1 q du ≤ 1 2 0 u τ -1 1 2 τ -1+ 1 q du + 1 1 2 1 2 τ -1 (1 -u) τ -1+ 1 q du (because τ -1 + 1 q < 0 and τ -1 < 0) = 1 2 τ -1+ 1 q 1 2 0 u τ -1 du + 1 2 τ -1 1 2 0 v τ -1+ 1 q dv (by the substitution v = 1 -u) = 1 2 τ -1+ 1 q × 1 τ 2 τ + 1 2 τ -1 × 1 (τ + 1 q )2 τ + 1 q = 1 2 2τ -1+ 1 q 1 τ + 1 τ + 1 q ≤ 1 τ 2 2τ -2+ 1 q Therefore ∆ k 0 f (t)F (t -∆ k )dt ≤ e -γ∆ k τ 2 4τ -2+ 1 q Γ (τ ) 2 × (γ∆ k ) 2τ -1+ 1 q p 1 p [q(1 -τ ) -1] 1 q . ( 8
)
Using 5, 6, 7 and 8, we get Proposition 4 If τ ∈ ( 1 2 ; 1),

P(n k + Y k ≥ n k * + Y k * ) ≤ e -γ∆ k 1 2 + 1 τ 2 4τ -2+ 1 q Γ (τ ) 2 × (γ∆ k ) 2τ -1+ 1 q p 1 p [q(1 -τ ) -1]
P[A(d; Q) = k * ] ≤ k =k * e -γ∆ k 1 2 + (γ∆ k ) 2τ -1 τ 2 4τ -2 Γ (τ ) 2 .
If τ ∈ (0; .

Proof Let us distinct two cases according to the value of τ . First case: τ > 1 2

Taking the limit when q approaches +∞ in 8 (which actually amounts to substitute v τ -1 by its upper bound (γu 0 ) τ -1 in the integral +∞ γu 0 e -v v τ -1 dv of the proof of Lemma 5, without needing Hölder's inequality), we get

P[A(d; Q) = k * ] ≤ k =k * e -γ∆ k 1 2 + (γ∆ k ) 2τ -1 τ 2 4τ -2 Γ (τ ) 2
Second case: τ ≤ 1 2 By convention, if τ = 1 2 , we have 1 1-2τ = +∞. We take q < 1 1-2τ (it is possible since 1 1-2τ > 1 1-τ ) and write q = 1 1-2τ + , with 0 < < τ . Then, 1 p = 1 -1 q = 2τ -and we get

P[A(d; Q) = k * ] ≤ k =k * e -γ∆ k 1 2 + (2τ -) 2τ - τ 2 2τ -1+ Γ (τ ) 2 × 1 -2τ + τ - 1-2τ + × (γ∆ k )
For example, with = τ 2 (i.e. q = 1 1-3 2 τ ), we have

P[A(d; Q) = k * ] ≤ k =k * e -γ∆ k 1 2 + 1 τ 2 5 2 τ -1 Γ (τ ) 2 × 3 2 τ 3 2 τ 2 τ -3 1-3 2 τ × (γ∆ k ) τ 2
Note that, whatever is the value of τ ∈ (0; 1), our upper bound of P(n k + Y k ≥ n k * + Y k * ) tends to 0 when ∆ k approaches +∞ which follows the intuition that P(n k +Y k ≥ n k * +Y k * ) tends to 0 when the true argmax k * has a much higher count than k. The upper bound tends to 1 2 when ∆ k approaches 0, which is consistent with the actual value of the probability P(n k + Y k ≥ n k * + Y k * ) when the counts n k * and n k are equal.

Similarly, the upper bound tends to 0 when γ tends to +∞ and to 1 2 when γ approaches 0. These are the expected values of the probability P(n k + Y k ≥ n k * + Y k * ) when there is no noise or an infinitely wide noise respectively.

Finally, let us remark that we recover the upper bound

P[A(d; Q) = k * ] ≤ k =k * 2+γ∆ k
4e γ∆ k from [8] (obtained with a centralised Laplace noise) when we consider the limit when τ tends to 1.

Remark. The data-dependent bound α A (l; aux, d, d ) ≤ log (1-q) 1-q 1-e q l +qe l from Theorem 3 is non-monotonic in γ. This may appear counter-intuitive since a smaller noise (greater γ) usually gives worse privacy guarantees and, as one would expect, a bigger moments accountant. Nevertheless, a smaller noise means that the probability of outputting the true (unnoisy) argmax is closer to 1, which may lower the moments accountant. Indeed, two adjacent databases will both output the true argmax with high probability, giving less chance to an adversary to distinguish them. This non-monotonicity of the data-dependent bound induces the non-monotonicity of the overall privacy cost . This is illustrated in Figure 2 of the paper on which we can see, however, that choosing a small γ still gives better guarantees.

B FHE argmax implementation details

We implemented the FHE argmax algorithm using the C++ TFHE library [4]. Table 1 presents all of the parameters needed to reproduce our results and build a fully homomorphic argmax scheme using the TFHE library. The first two lines present our values for the standard TFHE parameters: the first line for initial ciphertext encryption; the second line for the two bootstrapping keys we use. Given the parameters that we use here, we achieve a security parameter of 110. We base the security of our scheme on the lwe-estimator 3 script. The estimator is based on the work presented in [2] and is consistently kept up to date.

The third line presents parameters that are specific to our implementation. Because of the use of Gamma distributions, the values sent by the teachers can C.1 Experimental settings for MNIST Following PATE experimental conditions, we built our framework based on the code repositories 4 accompanying [8]. The teacher models are based on two convolutional layers with max-pooling and one fully connected layer with ReLUs. Code modifications have been performed on the initial repository, and are available on https://github.com/Arnaud-GS/SPEED. The execution environment consists in Python 3 and Tensorflow 1.15.0. The batch size, learning rate and max steps parameters have been respectively set to 128, 0.01 and 5000. As stated in [8], this yields an aggregate test-error rate of 93%. A semi-supervised technique proposed in [9] has been used 5 , in an execution environment consisting of Python 3 and Theano 0.7. Besides modifications available on https://github.com/Arnaud-GS/ SPEED, the learning rate and number of epochs have been set to 0.001 and 500 respectively.

C.2 Experimental settings for SVHN

For SVHN, two additional layers have been added to the teacher models which were learned using a node with 8 NVIDIA v100. The batch size, learning rate and max steps parameters have been respectively set to 64, 0.08 and 2000. The student model also uses the improved GAN semi-supervised model, relying on Python 3 and Theano 0.8.2. The learning rate and number of epochs have been set to 0.0003 and 600 respectively.

Fig. 1

 1 Fig. 1 SPEED -Teacher models send to the aggregation server their encrypted noisy answers to the student's queries. The server homomorphically performs the aggregation in the encrypted domain and sends the result to the student model which decrypts it and uses it for training

4

  SPEED: Secure, Private, and Efficient Deep Learning 4.1 A distributed learning architecture

6

  e.g. the privacy guarantee for an honest teacher would be computed with τ = |S|-1 n .

Fig. 2 Fig. 3

 23 Fig.2Differential privacy guarantees for MNIST as a function of γ, with τ = 0.9

  ] = e -γ|t+a| I(γ|t + a|) +∞ t e -γ|u| I(γ|u|)du -e -γ|t| I(γ|t|) +∞ t+a e -γ|u| I(γ|u|)du = e -γ(t+a) I(γ(t + a)) +∞ t e -γu I(γu)du -e -γt I(γt) +∞ t+a e -γu I(γu)du = e -γ(t+a) I(γ(t + a)) +∞ t e -γu I(γu)du -e -γt I(γt) +∞ t e -γ(v+a) I(γ(v + a))dv (by the substitution v = u -a) = e -γ(t+a) +∞ t e -γu [I(γ(t + a))I(γu) -I(γt)I(γ(u + a))] du For any u ∈ [t; +∞), Lemma 2 with β = γa tells us that I(γu) I(γ(u+a)) ≤ I(γt) I(γ(t+a)) which means I(γ(t + a))I(γu) -I(γt)I(γ(u + a)) ≤ 0. Therefore, +∞ t e -γu [I(γ(t + a))I(γu) -I(γt)I(γ(u + a))

2 e 2 e 2 0 1 + γa 2 0 2 0 2 0= 1 + 2 γa 2 0Proposition 6

 2221222126 -|v| I(|v|)dv L γ +∞ γa e -|v| I(|v|)dv (by the substitutions v = γu) -|v| I(|v|)dv + γa e -|v| I(|v|)dv +∞ γa e -|v| I(|v|)dv = e -|v | I(|v |)dv + γa e -|v| I(|v|)dv +∞ γa e -|v| I(|v|)dv (by the substitution v = -v) e -|v| I(|v|)dv +∞ γa e -|v| I(|v|)dv e -v I(v)dv +∞ γa e -v I(v)dv Let us suppose that τ > 1 2

= 1 2 2 = 1 2L 2 =Γ (τ ) 2 2γ 2 (Γ (τ ) 2 2 2 . 2

 121222222 Le -γa I(γa) -L 2 I(0) +∞ a e -γu I(γu)du L +∞ a e -γu I(γu)du e -γa I(γa) -I(0) +∞ a e -γu I(γu)du +∞ a e -γu I(γu)du e -γa I(γa) -1 γ I(0) +∞ γa e -v I(v)dv 1 γ +∞ γa e -v I(v)dv by the substitutions v = γu) = γ e -γa I(γa) -I(0) +∞ γa e -v I(v)dv +∞ γa e -v I(v)dv Theorem The aggregation mechanism A is ( , 0)-differentially private, with = log 1 + 2 γ 0 e -v I(v)dv +∞ 2γ e -v I(v)dv .

Proof 2 e

 2 For all v ∈ R * + , e -v I(v) > 0 thus, supposing γ ∈ (0, 1],+∞ 2γ e -v I(v)dv ≥ +∞ -v I(v)dv > 0. Therefore, it suffices to prove that lim γ→0 γ 0 e -v I(v)dv = 0 to deduce the announced result.

Γ 1 u→1 u 1 u→1 u 1 u 1 u 1 u 0 e γu 2 1 u 1 2 e γz if z < 0 1 -1 2 e

 111112112 (τ ) 2 e -γ|u| I(γ|u|) = 1 2 γe -γ|u| . Let us now determine the limit of F . Let u 0 ∈ [0; 1 γ ] and u 1 ∈ [0; 1 γ ] such that u 0 < u 1 . According to Lemma 4, for all u ∈ (u 0 ; u 1 ], e -γu I(γu) ≤ e -γu (γu) τ -1 Γ (τ ) 2 τ ≤ e -γu (γu) -and Γ is decreasing on (0; 1]. Since u → e -γu (γu) -0 ; u 1 ] and, for all u ∈ (u 0 ; u 1 ], lim τ →1 e -γu I(γu) = e -γu 2 , by the dominated convergence theorem, limτ →1 u 0 e -γu I(γu)du = u 1 u 0 e -γu 2 du. Let u 0 ∈ [ 1 γ ; +∞) and u 1 ∈ [ 1 γ ; +∞) ∪ {+∞} such that u 0 < u 1 .Similarly, as, for all u ∈ [u 0 ; u 1 ), e -γu I(γu) ≤ e -γu (γu) τ -1 Γ (τ ) 2 τ ≤ e -γu Γ ( is integrable on [u 0 ; u 1 ) and, for all u ∈ [u 0 ; u 1 ), lim τ →1 e -γu I(γu) = e -γu 2 , by the dominated convergence theorem, lim τ 0 e -γu I(γu)du = We deduce that, whatever are the bounds u 0 ∈ [0; +∞) and u 1 ∈ [0; +∞) ∪ {+∞} with u 0 < u 1 , lim τ 0 e -γu I(γu)du = 0 e γu I(-γu)du = u du for any u 0 ∈ (-∞; 0] ∪ {-∞} and u 1 ∈ (-∞; 0] with u 0 < u 1 .Finally, for any u 0 ∈ (-∞; 0] ∪ {-∞} and u 1 ∈ [0; +∞) ∪ {+∞} such that u 0 < u 1 , we have lim τ →1 u 0 e -γ|u| I(γ|u|)du = -γz if z ≥ 0 which is actually the expression of the Laplace cumulative distribution function.

.

  The overall upper bound forP[A(d; Q) = k * ] is obtained using the fact that the event (A(d; Q) = k * ) is the union of the events (n k + Y k ≥ n k * + Y k * ), for k ∈ [K] \ {k * }, and then P[A(d; Q) = k * ] ≤ k =k * P(n k + Y k ≥ n k * + Y k * ).

Table 1

 1 Robustness of our framework depending on the availability of the student model and the noise generation

		Private model Public model
	Centralised noise	HBC	H
	Distributed noise	BHBC	BHBC

Table 3

 3 SVHN experimental results for 500 queries, with noise inverse scale γ = 0.1, δ = 10 -5

	Framework		Acc. [%] HE overhead
	Non-private	-	84.7	-
	Trusted	4.73	83.7	-
	τ = 1	4.73	83.5
	τ = 0.9 τ = 0.7	5.59 8.16	83.8 84.6	32.5 min

"Hard" means that it requires solving a reference (conjectured) computationally hard problem on which the security of the cryptosystem hence depends. From a practical viewpoint, given a security target λ, the concrete parameters of a homomorphic scheme are chosen such that the best known (exponential-time) algorithms for solving the underlying reference problem require an order of magnitude of 2 λ nontrivial operations.

Polynomial in λ.

Thanks to the DP guarantees, the labels of D could actually be published as well.

For example, add ν 0 -1 2 -n k to all the classes except k 0 and k 1 , ν 0 -1 -ν 1 to the class k 1 and nothing to the class k 0 .

Note that our DP guarantee for Trusted cannot be directly compared with PATE's one since we do not use the same δ.

Note that only the third value over which the minimum is taken in Theorem 3 is datadependent and, as such, requires this upperbound of P[A(d; Q) = k * ].

https://bitbucket.org/malb/lwe-estimator/raw/HEAD/estimator.py

Appendix

Arnaud Grivet Sébert • Rafaël Pinot • Martin Zuber • Cédric Gouy-Pailler • Renaud Sirdey

Received: date / Accepted: date A DP analysis of the learning procedure

In this section, we describe the procedure that computes the overall DP guarantees of the student model learning stage. We summarise this procedure in Section A.1, and demonstrate the theorems we use in Sections A.2 and A. 4.

We call A the aggregation mechanism that outputs the argmax of the noisy counts. A(d, Q) is the output of A for the database d and the query Q.

Let γ ∈ R * + be the inverse scale parameter of the distributed noise. Considering the DP guarantees from the point of view of an entity E, let τ ∈ (0, 1) be the ratio of the teachers whose noise is ignored by E. Typically, from the point of view of a colluding teacher, τ is the ratio of the teachers who do not collude.

A.1 Analysis algorithm

Let us suppose that for every query Q from the student model, we have a privacy guarantee using Theorem 2 and that we can upperbound the probability P[A(d; Q) = k * ] that A outputs some specific output k * (in practice we choose k * to be the unnoisy argmax). Then, Theorem 3 gives us an upperbound on the moments accountant per query 1 . The computation of these building blocks is detailed in Sections A.2 and A.4, and the procedure is summarised in Algorithm 1.

Let us recall the definition of the moments accountant.

Definition 5

The moments accountant of a mechanism M is defined for any Evidence. On a theoretical point of view, we formally proved the upper bound of the privacy cost, as a function of the ratio of teachers who do not collude, and detailed the algorithm used to compute it. To support our theoretical guarantees, we performed experiments on MNIST and SVHN datasets to determine the accuracy and the privacy cost of our framework. Most related contributions. As mentioned in the paper, our work was inspired by PATE framework from Semi-supervised knowledge transfer for deep learning from private training data, Papernot et al. [5] and Scalable private learning with PATE, Papernot et al. [6]. Nevertheless, while PATE needs to trust the aggregation server, SPEED addresses the issue of threats from an honest but curious aggregation server -or even beyond -thanks to the HE computation of the aggregation and the argmax and to the use of distributed differential privacy. Our notion of adjacence is also larger and leads to more general differential privacy guarantees.

In Practical secure aggregation for privacy-preserving machine learning [1], Bonawitz et al. consider the problem of privacy-preserving secure aggregation to apply it to federated learning frameworks. The secure aggregation is performed using one-time pads masking, which, contrary to homomorphic encryption, requires communication and is vulnerable to agents' failures. Fault tolerance is nevertheless achieved, at the price of heavy additional communication and computation. The possibility of using differential privacy is mentioned in the appendix of [1] but the problem of a server which has access to the final model is not treated.

Arnaud Grivet Sébert, Rafaël Pinot, Martin Zuber, Cédric Gouy-Pailler, Renaud Sirdey Université Paris-Saclay, CEA, List, F-91120 Palaiseau, France Rafaël Pinot Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE, Paris, France

Information sheet

Private collaborative neural network learning, Chase et al. [2], makes use of both differential privacy and secure aggregation to perform collaborative gradient descent which requires much more computation and communication than our voteaggregation framework which takes advantage of the existence of personal models. The employed cryptographic techniques (secret sharing), which do not include homomorphic encryption, increase the communication load between the agents. Moreover, the problem of colluding agents is not addressed. Appropriate reviewers. We believe that relevant reviewers for our paper would be Slawomir Goryczka, Nicolas Papernot, Keith Bonawitz and Théo Ryffel. As the first author of two comparative studies on secure aggregation using distributed differential privacy [3,4], Slawomir Goryczka would give very interesting reviews on our work. Since SPEED's architecture is close to PATE's one and our differential privacy analysis was inspired from the one from [5], Nicolas Papernot would review our paper with a deep understanding of the problems we tackled. Due to his attention to the fault tolerance problem in secure aggregation and his interest on the differential privacy answer to distrusted servers, we believe that Keith Bonawitz [1] would also be a very appropriate reviewer. Specialised in privacypreserving machine learning and cryptography, Théo Ryffel [7,8] would give more cryptography-oriented and complementary insights on our work.