an algorithm to enable such privacy. Originally DP was studied in the centralized context, where the privacy from queries to a trusted server holding the data was the objective [16]. However, in distributed applications, such as federated learning [30], two significant aspects need to be accommodated: (i) data is held locally at clients and needs to be used for computation with an untrusted server; and (ii) to build good learning models, one might need repeated interactions (e.g., through distributed gradient descent).

To accommodate privacy of locally held data, a more appropriate notion is that of local differential privacy (LDP) [15,34]. In the LDP framework, each (distributed) client holding local data, individually randomizes its interactions with the (untrusted) server. 1Recently, such LDP mechanisms have been deployed by companies such as Google [23], Apple [29], and Microsoft [14]. However, LDP mechanisms suffer from poor performance in comparison with the centralized DP mechanisms, making their applicability limited [15,31,34]. To address this, a new privacy framework using anonymization has been proposed in the so-called shuffle model [7,13,22], where each client sends her (randomized) interaction message to a secure shuffler that randomly permutes all the received messages before forwarding them to the server. Such a shuffling can be enabled through anonymization techniques [10,20,22]. This model enables significantly better privacy-utility performance by amplifying LDP through this mechanism.

For the second aspect, where there are repeated interactions (e.g., through distributed gradient descent), one needs privacy composition [9]. In other words, we want to compute the overall privacy budget under the composition of multiple iterations. Clearly, from an optimization viewpoint, we might need to run these interactions longer for better models, but these also result in privacy leakage. Though the privacy leakage can be quantified using advanced composition theorems for DP (e.g., [19,33]), these might be loose. To address this, Abadi et al. [1] developed a "moments accountant" framework, which enabled a much tighter composition. This is enabled by providing the composition privacy guarantee in terms of Rényi Differential Privacy [36], and then mapping it back to the DP guarantee [37]. It is known [1] that the moments accountant provides a significant saving in the total privacy budget in comparison with using the strong composition theorems [19,33]. Therefore, developing the RDP privacy guarantee can enable stronger composition privacy results. Analyzing the RDP of the shuffle model could have several applications such as private statistics using interactive schemes for heavy hitters, mean estimation, federated learning, and distributed differentially private stochastic gradient descent (DPSGD). This leads us to the central question addressed in this paper:

Can we develop strong RDP privacy guarantees for general local mechanisms in the shuffle privacy model? The principal result in this paper is the first direct RDP guarantee for general discrete local randomization mechanisms in the shuffle privacy model. In particular, given an arbitrary discrete local mechanism with 0 -LDP guarantee, we provide an RDP guarantee for the shuffle model, as a function of 0 and the number of users ; see Theorem 3.1. This can be seen as an amplification by shuffling result for amplifying pure LDP guarantee to RDP guarantee via shuffling. In contrast, the existing amplification by shuffling results [7,22,24] amplify pure LDP guarantee to approximate DP guarantee.

When numerically evaluating our bound, we save a factor of 8× compared to the state-of-the-art approximate DP guarantee for shuffle models in [24] foot_1 combined with strong composition, with the number of iterations = 10 5 , LDP parameter 0 = 0.5, and number of clients = 10 6 ; see Figure 4a in Section 4 for such example regimes. Furthermore, characterizing the RDP of the shuffle model enables us to compute the RDP of shuffling with Poisson sub-sampling by using the results in [43]. We numerically show that this approach can lead to at least 10× improvement in privacy guarantee. This is for = 10 4 , 0 = 3, and = 10 6 . The comparison is with applying the strong composition theorem [33] after getting the state-of-the-art approximate DP of the shuffle model given in [24] with Poisson sub-sampling [35] (see Figure 5a in Section 4 for more such regimes). This in turn implies that we can accommodate at least 10× more interactions for the same privacy budget in these cases. Moreover, our upper bounds also give several orders of magnitude improvement over the simple RDP bound stated in [21, Remark 1] (also stated in (9)) in several regimes (see, for example, Figure 2e in Section 4). We also develop a lower bound for the RDP for the shuffle model and numerically demonstrate that the gap is small for many parameter regimes of interest.

In order to obtain our upper bound result, we develop new analysis techniques which could be of independent interest. In particular, we develop a novel RDP analysis for neighboring datasets with a special structure (see Theorem 3.7), in which one of the datasets has all the data points to be the same (see the definition in (12)). A key technical result is then to relate the RDP of general neighboring datasets to those with special structure (see Theorem 3.6).

• For the RDP analysis of neighboring datasets with the abovementioned special structure, we first observe that the output distribution of the shuffling mechanism is the multinomial distribution. Using this observation, then we show that the ratio of the distributions of the mechanism on special structure neighboring datasets is a sub-Gaussian random variable (r.v.), and we can write the Rényi divergence of the shuffle mechanism in terms of the moments of this r.v. Bounding the moments of this r.v. then gives an upper bound on the RDP for the special neighboring datasets. See the proof-sketch of Theorem 3.7 in Section 3.3.2 and its complete proof in Section 6. • We next connect the above analysis to the RDP computation for general neighboring datasets D = ( 1 , . . . , ) and

To do so, a crucial observation is to write the output distribution of the local randomizer R on the 'th client's data point (for any ∈ [ -1]) as a mixture distribution = -0 ′ + (1 --0 ) ˜ for some ˜ . 3 So, the number of clients that sample according to ′ is concentrated around -0 . Therefore, if we restrict the dataset to these clients only, the resulting datasets will have the special structure, and the size of that dataset will be concentrated around -0 . Finally, in order to be able to reduce the problem to the special case, we remove the effect of the clients that do not sample according to ′ without affecting the Rényi divergence. See the proof-sketch of Theorem 3.6 in Section 3.3.1 and its complete proof in Section 5.

We give the most relevant work related to the paper and put our contributions in the context of these works.

shuffle privacy model: As mentioned, the shuffle model of privacy has been of significant recent interest [5-8, 13, 22, 25, 26]. However, all the existing works in literature [7,22,24] only characterize the approximate DP of the shuffle model -among these, [24] is the state-of-the-art, but as we show in our experiments, it yields weaker results when combined with composition. To the best of our knowledge, there is no bound on RDP of the shuffle model in the literature except for the one mentioned briefly in a remark in [22, Remark 1] (which is obtained by the standard conversion results from DP to RDP) and we state it in (9) for comparison. However, this bound is loose (e.g., see Figure 2e) and not useful for conversion to approximate DP (e.g., see Figures 3a,3c), as well as for composition (e.g., see Figure 4e). Thus, our work makes progress on this important open question of analyzing the RDP of the shuffle model. Both [20] and [27] used advanced composition to analyze privacy of shuffle models in federated learning; our results could be adapted to enhance their privacy guarantees.

Rényi differential privacy: The work of Abadi et al. [1] provided a methodology to get stronger composition results. Inherently, this used Rényi divergence, and was later formalized in [36] which defined Rényi differential privacy (RDP). RDP presents a unified definition for several kinds of privacy notions including pure differential privacy ( -DP), approximate differential privacy (( , )-DP), and concentrated differential privacy (CDP) [11,18]. As mentioned earlier, RDP enables a stronger result for composition, through the "moment accounting" idea. Similarly, several works [37,40,43] have shown that analyzing the RDP of subsampled mechanisms provides a tighter bound on the total privacy loss than the bound that can be obtained using the standard strong composition theorems. However, to the best of our knowledge, RDP analysis of the shuffle model and its use for composition in the shuffle model has not been studied. In this paper, we analyze the RDP of the shuffle model, where we can bound the approximate DP of a sequence of shuffle models using the transformation from RDP to approximate DP [1,2,12,40]. We show that our RDP analysis provides a better bound on the total privacy loss of composition than that can be obtained using the standard strong composition theorems (see Section 4).

Discrete mechanisms: Many of the works in DP use specific randomization mechanisms, adding noise using the Laplace or Gaussian distributions. However, in many situations the data is inherently discrete (e.g., see [12] and references therein) or compression causes it to be so (e.g., see [27,32] and references therein). It is therefore of interest to directly analyze privacy of discrete randomization mechanisms. Such discrete mechanisms have been studied extensively in shuffle models [5,25], but for approximate DP. To the best of our knowledge, RDP for general discrete mechanisms in the shuffle privacy framework is new to our work.

The paper is organized as follows. In Section 2, we give some preliminary definitions and results from the literature and also formulate our problem. In Section 3, we present our main results (two upper bounds and one lower bound on RDP), along with a proof sketch of the first upper bound. We also describe the two main ingredients in its proof -first is the reduction of computing RDP for the arbitrary pairs of neighboring datasets to computing RDP for the special pairs of neighboring datasets, and the second is computing RDP for the special pairs of neighboring datasets. In Section 4, we present several numerical results to demonstrate the advantages of our bounds compared to the state-of-the-art. The rest of the sections are devoted to the full proofs of our main results: Section 5 shows the reduction of our general problem to the special case; Section 6 proves the RDP for the special case; Section 7 proves both our upper bounds; and Section 8 proves our lower bound. In Section 9, we conclude with a short discussion. Omitted details from the proofs are provided in the appendices.

We give different privacy definitions that we use in Section 2.1, some existing results on RDP to DP conversion and RDP composition in Section 2.2, and give our problem formulation in Section 2.3.

In this subsection, we define different privacy notions that we will use in this paper: local differential privacy (LDP), central differential privacy (DP), and Rényi differential privacy (RDP). Definition 1 (Local Differential Privacy -LDP [34]). For 0 ≥ 0, a randomized mechanism R : X → Y is said to be 0 -local differentially private (in short, 0 -LDP), if for every pair of inputs , ′ ∈ X, we have

Let D = { 1 , . . . , } denote a dataset comprising points from X. We say that two datasets D = { 1 , . . . , } and D ′ = { ′ 1 , . . . , ′ } are neighboring (and denoted by D ∼ D ′ ) if they differ in one data point, i.e., there exists an ∈ [ ] such that ≠ ′ and for every ∈ [ ], ≠ , we have = ′ . Definition 2 (Central Differential Privacy -DP [16,17]). For , ≥ 0, a randomized mechanism M : X → Y is said to be ( , )differentially private (in short, ( , )-DP), if for all neighboring datasets D ∼ D ′ ∈ X and every subset S ⊆ Y, we have Pr [M (D) ∈ S] ≤ 0 Pr M (D ′ ) ∈ S + .

(

Definition 3 (Rényi Differential Privacy -RDP [36]). A randomized mechanism M : X → Y is said to have ( )-Rényi differential privacy of order ∈ (1, ∞) (in short, ( , ( ))-RDP), if for any neighboring datasets D ∼ D ′ ∈ X , the Rényi divergence between M (D) and M (D ′ ) is upper-bounded by ( ), i.e.,

where M (D)( ) denotes the probability that M on input D generates the output . For convenience, instead of ( ) being an upper bound, we define it as

Our objective in this paper is to characterize the Rényi differential privacy of a shuffling mechanism M (see Section 2.3 for details) for different values of order .

In this subsection, we state some preliminary results from the literature that we will use. Though our main objective in this paper is to derive RDP guarantees of a shuffling mechanism, we also give the central privacy guarantees of that mechanism. For that purpose, we use the following result for converting the RDP guarantees of a mechanism to its DP guarantees. To the best of our knowledge, this result gives the best conversion. 4L 2.1 (F RDP DP [4,12]). Suppose for any > 1, a mechanism M is ( , ( ))-RDP. Then, the mechanism M is ( , )-DP, where , are define below: For a given ∈ (0, 1) :

As mentioned in Section 1, the main strength of RDP in comparison to other privacy notions comes from composition. The following result states that if we adaptively compose two RDP mechanisms with the same order, their privacy parameters add up in the resulting mechanism. A set of all possible histograms with bins and elements (see (4))

The shuffle mechanism M on the dataset D ∈ X ; M (D) is a distribution over A (see ( 3)) (P)

Distribution over A when client maps its data point according to the distribution (see ( 17)) Table 1: Notation used throughout the paper using convexity of the function ( -1) ( ) as follows. From [39, Corollary 2], the function ( -1) (P||Q) is convex in for any given two distributions P and Q. Thus, for any real order > 1, we can bound the RDP of the shuffle model by

where = ⌈ ⌉ -, since = ⌊ ⌋ + (1 -) ⌈ ⌉ for any real . Here, ⌊ ⌋ and ⌈ ⌉ respectively denote the largest integer smaller than or equal to and the smallest integer bigger than or equal to .

In the following theorem, we also present another bound on RDP that readily holds for all ≥ 1.

. For any ∈ N, 0 ≥ 0, and any ≥ 1 (including the non-integral ), the RDP of the shuffle model is upper-bounded by

where = ⌊ -1 2 0 ⌋ + 1. We prove Theorem 3.3 in Section 7.2.

Remark 3 (Improved Upper Bounds -Saving a Factor of 2). The exponential term 0 --1 8 0 in both the upper bounds stated in ( 5) and ( 8) comes from the Chernoff bound, where we naively choose the factor = 1/2 instead of optimizing it; see the proof of Theorem 3.1 in Section 7.1. If we instead had optimized and chosen it to be, for example, = 2 0 0 √ log( ) (which goes to 0 when, say, 0 ≤ 1 4 log( )), we would have asymptotically saved a multiplicative factor of 2 in the leading term in both upper bounds, because in this case we have

We chose to evaluate our bound with = 1/2 because of two reasons: first, it gives a simpler expression to compute; and second, the evaluated bound does not give good results (as compared to the ones with = 1/2) for the parameter ranges of interest.

Remark 4 (Difference in Upper Bounds). Since the quadratic term in inside the log in (8) has an extra multiplicative factor of 0 in comparison with the corresponding term in (5), our first upper bound presented in Theorem 3.1 is better than our second upper bound presented in Theorem 3.3 for all parameter ranges of interest; see also Figure 2 in Section 4. However, the expression in ( 8) is much cleaner to state as well as to compute as compared to that in (5). As we will see later, the techniques required to prove both upper bounds are different.

Remark 5 (Potentially Better Upper Bounds for Specific Mechanisms). Since both our upper bounds are worse-case bounds that hold for all 0 -LDP mechanisms, it is possible that for specific mechanisms, we may be able to exploit their structure for potentially better bounds. See Remark 8 on this just after (32).

The upper bounds on the RDP of the shuffle model presented in (5) and ( 8) are general and hold for any discrete 0 -LDP mechanism. Furthermore, these bounds are in closed form expressions that can be easily implemented. To the best of our knowledge, there is no bound on RDP of the shuffle model in literature except for the one given in [21, Remark 1], which we provide belowfoot_4 in (9). For the LDP parameter 0 and number of clients , they showed that for any > 1, the shuffle mechanism M is ( , ( ))-RDP, where

In Section 4, we evaluate numerically the performance of both our bounds (from Theorems 3.1 and 3.3) against the above bound in (9). We demonstrate that both our bounds outperform the above bound in all cases; and in particular, the gap is significant when 0 > 1 -note that the bound in [22] is worse than our simplified bound given in Corollary 3.2 by a multiplicative factor of 4 0 .

In this subsection, we provide a lower bound on the RDP for any integer order satisfying ≥ 2.

). For any ∈ N, 0 ≥ 0, and any integer ≥ 2, the RDP of the shuffle model is lower-bounded by:

where expectation is taken w.r.t. the binomial random variable ∼ Bin ( , ) with parameter = 1 0 +1 . We give a proof-sketch of Theorem 3.4 in Section 8 and provide its complete proof in Appendix E.

When is an even integer, then the expectation term in ( 10) is positive. When ≥ 3 is an odd integer, then using the convexity of function ( ) = , it follows from the Jensen's inequality (i.e., E ( ) ≥ (E )) and

Using these observations, we can safely ignore the summation term from (10) and obtain the following simplified lower bound.

). For any ∈ N, 0 ≥ 0, and integer ≥ 2, the RDP of the shuffle model is lowerbounded by:

Remark 6 (Upper and Lower Bound Proofs). Both our upper bounds stated in Theorems 3.1 and 3.3 hold for any 0 -LDP mechanism. In other words, they are the worst case privacy bounds, in the sense that there is no 0 -LDP mechanism for which the associated shuffle model gives a higher RDP parameter than those stated in ( 5) and (8). Therefore, the lower bound that we derive should serve as the lower bound on the RDP privacy parameter of the mechanism that achieves the largest privacy bound (i.e., worst privacy). We prove our lower bound result (stated in Theorem 3.4) by showing that a specific mechanism (in particular, the binary Randomized response (RR)) on a specific pair of neighboring datasets yields the RDP privacy parameter stated in the right hand side (RHS) of (10). This implies that RDP privacy bound (which is the supremum over all neighboring datasets) of binary RR for the shuffle model is at least the bound stated in (10), which in turn implies that the lower bound (which is the tightest bound for any 0 -LDP mechanism) is also at least that.

Remark 7 (Gap in Upper and Lower Bounds). When comparing our simplified upper and lower bounds from Corollaries 3.2 and 3.5, respectively, we observe that when 4 5 0 < 9 , our upper and lower bounds differ by a multiplicative factor of 4 0 . In our generic upper bound (5), note that when is large, only the term corresponding to 2 matters, and with our improved upper bound (which saves a factor of 2 in that term asymptotically -see Remark 3), the upper and lower bounds are away by the factor of 0 , which tends to 1 as 0 → 0. Thus, in the regime of large and small 0 , our upper and lower bounds coincide. Without any constraints on , 0 , we believe that our lower bound is tight. Closing this gap by showing a tighter upper bound is an interesting and important open problem.

The proof has two main steps. In the first step, we reduce the problem of deriving RDP for arbitrary neighboring datasets to the problem of deriving RDP for specific neighboring datasets, D, D ′ , where all elements in D are the same and D ′ differs from D in one entry. In the second step, we derive RDP for the special neighboring datasets. Details follow:

The specific neighboring datasets to which we reduce our general problem have the following form: and ∼ Bin ( -1, ) be a binomial random variable. We have:

We give a proof-sketch of Theorem 3.6 in Section 3.3.1 and provide its complete proof in Section 5.

We know (by Chernoff bound) that the binomial random variable is concentrated around its mean, which implies that the terms in the RHS of (13) that correspond to < (1 -) ( -1) (we will take = 1/2) will contribute in a negligible amount. Then we show in Lemma D.1 (on page 20) that

is a non-increasing function of . These observations together imply that the RHS in ( 13) is approximately upper bounded by

Since is precisely what is required to bound the RDP for the specific neighboring datasets, we have reduced the problem of computing RDP for arbitrary neighboring datasets to the problem of computing RDP for specific neighboring datasets. The second step of the proof bounds (1-) ( -1) , which follows from the result below that holds for any ∈ N. T 3.7 (RDP S C ). Let ∈ N be arbitrary. For any integer ≥ 2, we have

We give a proof-sketch of Theorem 3.7 in Section 3.3.2 and provide its complete proof in Section 6.

Substituting = (1 -) ( -1) + 1 in ( 14) yields the bound in Theorem 3.1.

Proof Sketch of Theorem 3.6. For ∈ [ ], let denote the distribution of the 0 -LDP mechanism R when the input data point is , and ′ denote the distribution of R when the input data point is ′ . The main idea of the proof is the observation that each distribution can be written as the following mixture distribution:

, where ˜ is a certain distribution associated with . So, instead of client ∈ [ -1] mapping its data point according to , we can view it as the client maps according to ′ with probability 1 0 and according to ˜ with probability (1 -1 0 ). Thus the number of clients that sample from the distribution ′ follows a binomial distribution Bin( -1, ) with parameter = 1 0 . This allows us to write the distribution of M when clients map their data points according to 1 , . . . , , ′ as a convex combination of the distribution of M when clients map their data points according to ˜ 1 , . . . , ˜ -1 , , ′ ; see Lemma 5.1. Then using a joint convexity argument (see Lemma 5.2), we write the Rényi divergence between the original pair of distributions of M in terms of the same convex combination of the Rényi divergence between the resulting pairs of distributions of M as in Lemma 5.1. Using a monotonicity argument (see Lemma 5.3), we can remove the effect of clients that do not sample from the distribution ′ without decreasing the Rényi divergence. By this chain of arguments, we have reduced the problem to the one involving the computation of Rényi divergence only for the special form of neighboring datasets, which proves Theorem 3.6. Details can be found in Section 5.

Let : A → R denote a random variable (r.v.) associated with the distribution M (D ), and for every ∈ A , is defined as

With this, we can rewrite (15) in terms of the moments of . Then we show that is a sub-Gaussian r.v. that has zero-mean and bounded variance. Using the sub-Gaussianity of , we bound its higher moments (see Lemma 6.1). Substituting these bounds in (15) proves Theorem 3.7. Details can be found in Section 6.

In this section, we present numerical experiments to show the performance of our bounds on the RDP of the shuffle model and its usage for getting approximate DP and composition results.

RDP of the shuffle model: In Figure 2, we plot several bounds on the RDP of the shuffle model in different regimes. In particular, we compare between the first upper bound on the RDP given in Theorem 3.1, the second upper bound on the RDP given in Theorem 3.3, the lower bound on the RDP given in Theorem 3.4, and the upper bound on the RDP given in [22, Remark 1] and stated in (9). 6 It is clear that our first upper bound (5) gives a tighter bound on the RDP in comparison with the second bound (8) and the upper bound given in [22]. Furthermore, the first upper bound is close to the lower bound for small values of the LDP parameter 0 and for high orders . In addition, the gap between our proposed bound in Theorem 3.1 and the bound given in [22] increases as the LDP parameter 0 increases. We also observe that the curves of the lower and upper bounds on the RDP of the shuffle model saturate close to 0 when the order approaches to infinity. This indicates that the pure DP of the shuffle model is bounded below by 0 , an observation made in literature [3,22]. As can be seen in Figures 2d and2e, the RDP obtained by standard approximate DP to RDP conversion in [22, Remark 1], can be several orders of magnitude loose in comparison to our analysis.

Approximate DP of the shuffle model: Analyzing RDP of the shuffle model provides a bound on the approximate DP of the shuffle model from the relation between the RDP and approximate DP as shown in Lemma 2.1. In Figure 3, we plot several bounds on the approximate ( , )-DP of the shuffle model for fixed = 10 -6 . In Figures 3d and3b, we do not plot the results given in [22], since their bounds are quite loose and are far from the plotted range when 0 > 1. We can see that our analysis of the RDP of the shuffle model provides a tighter bound on the approximate DP of the shuffle model in comparison with the bound given in [7] in some regimes. However, our RDP analysis performs worse than the best known bound given in [24], when used without composition. This might be due to the gap between our upper and lower bound on the RDP of the shuffle model as the lower bound provides better performance than the bound given in [24] for all values of LDP parameter 0 . Note that the main use case for converting our RDP analysis to approximate DP is after composition rather than in the single-shot conversion illustrated in Figure 3.

Composition of a sequence of shuffle models: We now numerically evaluate the privacy parameters of the approximate ( , )-DP for a composition of mechanisms (M 1 , . . . , M ), where M is a shuffle mechanism for all ∈ [ ]. In Figure 4, we plot three different bounds on the overall privacy parameter for fixed = 10 -8 for a composition of identical shuffle models. The first bound on Now, using Lemma 5.1, in the following lemma we show that the Rényi divergence between (P) and (P ′ ) can be upper-bounded by a convex combination of the Rényi divergence between (P C ) and

). For any > 1, the function

is jointly convex in ( (P), (P ′ )), i.e.,

We prove Lemma 5.2 in Appendix B.2. For any

same , if we remove the effect of distributions in P [ -1]\C in the RHS of ( 24), we would be able to bound the RHS of (24) using the RDP for the special neighboring datasets in

same . This is precisely what we will do in the following lemma and the subsequent corollary, where we will eliminate the distributions in P [ -1]\C in the RHS (24).

The following lemma holds for arbitrary pairs (P, P ′ ) of neighboring distributions P = { 1 , . . . , } and P ′ = { 1 , . . . , -1 , ′ }, where we show that E ∼ ( P ′ ) ( P) ( ) ( P ′ ) ( ) does not decrease when we eliminate a distribution (i.e., remove the data point from the datasets) for any ∈ [ -1]. We need this general statement as it will be required in the proof of Theorem 3.1 later.

For any ∈ [ -1], we have

where, for ∈ [ -1], P -= P \ { } and P ′ -= P ′ \ { }. Note that in the left hand side (LHS) of (25), (P), (P ′ ) are distributions over A , whereas, in the RHS, (P -), (P ′ -) for any ∈ [ -1] are distributions over A -1 .

We prove Lemma 5.3 in Appendix B.3. Note that Lemma 5.3 is a general statement that holds for arbitrary pairs (P, P ′ ) of neighboring distributions. For our purpose, we apply Lemma 5.3 with (P C , P ′ C ) for any C ⊆ [ -1] and then eliminate the distributions in P [ -1]\C one by one. The result is stated in the following corollary.

We prove Corollary 5.4 in Appendix B.4. Substituting from ( 26) into (24) and noting that for every ∈ A , (P)( ) and (P ′ )( ) are distributionally equal to M (D)( ) and M (D ′ )( ), respectively, we get

The inequality (a) is the same as (24), just writing it differently. In (b) we used (26) and in (c) we used the fact that number of -sized subsets of [ -1] is equal to -1 . This completes the proof of Theorem 3.6.

Fix an arbitrary ∈ N and consider any pair of neighboring datasets (D , D ′ ) ∈ D same . Let D = ( , . . . , ) ∈ X and D ′ = ( , . . . , , ′ ) ∈ X . Let = ( 1 , . . . , ) and ′ = ( ′ 1 , . . . , ′ ) be the probability distributions of the discrete 0 -LDP mechanism R : X → Y = [ ] when its inputs are and ′ , respectively, where

Since M is a shuffle mechanism, it induces a distribution on A for any input dataset. So, for any ∈ A , M (D )( ) and M (D ′ )( ) are equal to the probabilities of seeing when the inputs to M are D and D ′ , respectively. Thus, for a given histogram = (ℎ 1 , . . . , ℎ ) ∈ A with elements and bins, we have

where MN ( , , ) denotes the Multinomial distribution with

Note that (28) can be obtained as a special case of the general distribution in ( 17) by putting = for each client . For M (D ′ ), note that the last client (independent of the other clients) maps its input data point ′ to the 'th bin with probability ′ , and the remaining ( -1) clients' mappings induce a distribution on A -1 . Thus, M (D ′ )( ) for any ∈ A can be written as

where = ℎ 1 , . . . , ℎ -1 , ℎ -1, ℎ +1 , . . . , ℎ ∈ A -1 . We implicitly assume that if ℎ = 0 for some ∈ [ ], then MN -1, , = 0 as one of the elements is negative. Note that similar to ( 28), (29) can also be obtained from (17) as a special case. Using the polynomial expansion (1 + ) = =0

(with = M ( D ′ ) ( ) M ( D ) ( ) -1 in the following), we have:

Let : A → R be a random variable associated with the distribution M (D ) on A , and for any ∈ A , define ( ) :=

Substituting this in (30) gives:

The RHS of ( 31) is in terms of the moments of , which we bound in the following lemma. Before that, first we simplify the expression for ( ) by computing the ratio

Thus, we get ( )

Remark 8. As mentioned in Remark 5, we could tighten our upper bounds for specific mechanisms. As shown in (31) above, the Rényi divergence of a mechanism between two neighboring datasets can be written in terms of the moments of a r.v. , which is defined as the ratio of distributions of the mechanism on these two neighboring datasets. However, since our goal is to bound RDP for all 0 -LDP mechanisms, we prove the worse-case bound on the moments of that holds for all mechanisms; see (34) in Lemma 6.1 for bound on the ≥ 3'rd moments of and (38) in Lemma 6.2 for bound on the variance of . L 6.1. The random variable has the following properties:

(1) has zero mean, i.e., E ∼M ( D ) [ ( )] = 0.

(2) The variance of is equal to

(3) For ≥ 3, the 'th moment of is bounded by

is the Gamma function.

A proof of Lemma 6.1 is presented in Appendix C.1. Substituting the bounds from Lemma 6.1 into (31), we get

Note that 1 , . . . , , ′ 1 , . . . , ′ are defined for the fixed pair of datasets (D , D ′ ) ∈ D same that we started with. So, the term con-

and that is the only term in (35) that depends on (D , D ′ ). Since Theorem 3.7 requires us to bound (35) for any pair of neighboring datasets (D , D ′ ) ∈ D same , so, in order to prove Theorem 3.7, we need to compute sup ( D ,D ′ ) ∈D same =1 ′2 -1 . We bound this in the following.

Define a set T 0 consisting of all pairs of -dimensional probability vectors satisfying the 0 -LDP constraints as follows:

Note that T 0 contains all pairs of the output probability distributions ( , ′ ) of all 0 -LDP mechanisms R on all neighboring data points , ′ ∈ X. Since any (D , D ′ ) ∈ D same generates a pair of probability distributions ( , ′ ) ∈ T 0 (because D = ( , . . . , ) and D ′ = ( , . . . , , ′ ) together contain only two distinct data points , ′ ), we have sup

In the following lemma, we bounds the RHS of (37). L 6.2. We have the following bound:

We prove Lemma 6.2 in Appendix C.2. Taking supremum over (D , D ′ ) ∈ D same in (35) and then using (37) and (38), we get the bound in Theorem 3.7.

In this section, we will prove our upper bounds stated in Theorems 3.1 and 3.3 in Sections 7.1 and 7.2, respectively. same . Recall from Theorem 3.6, we have

where := -1 (1 -) --1 . For simplicity of notation, for any ∈ {0, 1, . . . , -1}, define

We show in Appendix D.1 that is a non-increasing function of . Using this and concentration properties of the Binomial r.v., we get (details are in Appendix D.1):

where > 0 is arbitrary, and expectation is taken w.r.t. ∼ M (D ′ ).

Note that we have already bounded for all in Theorem 3.7. By setting = 1 2 and = ⌊(1 -) ( -1)⌋ + 1 = ⌊ -1 2 0 ⌋ + 1, we get from Theorem 3.7, that:

Since the above bound holds for arbitrary pairs of neighboring datasets D and D ′ , this completes the proof of Theorem 3.1.

The proof of Theorem 3.3 follows the same steps as that of the proof of Theorem 3.1 that we outlined in Section 3.3 and also gave formally in Section 7.1, except for the following change. Instead of using Theorem 3.7 for bounding the RDP for specific neighboring datasets, we will use the following theorem.

We prove Theorem 7.1 in Appendix D.2. Note that Theorem 7.1 implies that -1 ≤ exp 2 ( 0 -1) 2 holds for every integer ≥ 2.

Substituting this in (41) (by putting = = ⌊ -1 2 0 ⌋ + 1), we get

This proves Theorem 3.3.

Consider the binary case, where each data point can take a value from X = {0, 1}. Let the local randomizer R be the binary randomized response (2RR) mechanism, where Pr

for ∈ X. It is easy to verify that R is an 0 -LDP mechanism.

For simplicity, let = 1 0 +1 . Consider two neighboring datasets D, D ′ ∈ {0, 1} , where D = (0, . . . , 0, 0) and D ′ = (0, . . . , 0, 1). Let ∈ {0, . . . , } denote the number of ones in the output of the shuffler. As argued in Section 2.3 on page 4, since the output of the shuffle mechanism M can be thought of as the distribution of the number of ones in the output, we have that ∼ M (D) is distributed as a Binomial random variable Bin( , ). The proof uses some properties of the Binomial r.v., which are provided in Appendix E.

The analysis of the RDP for the shuffle model presented in this paper was based on some new analysis techniques that may be of independent interest. The utility of these bounds were also demonstrated numerically, where we saw that in important regimes of interest, we get 8× improvement over the state-of-the-art without sampling and at least 10× improvement with sampling (see Section 4 for more details).

A simple extension of the results would be to work with local approximate DP guarantees instead of pure LDP. This can be seen by using the tight conversion between approximate DP and pure DP given in [24]. However, there are several open problems of interest. Our upper bounds hold for general discrete local mechanisms. The extension to continuous distributions requires careful technical analysis as the histogram used for RDP analysis would need to approximate continuous distributions via discretization. We leave the analysis of continuous distributions as a future work. Perhaps the most important one is mentioned in Remark 7. There is a multiplicative gap of the order 0 in our upper and lower bounds, and closing this gap is an important open problem. We believe that our lower bound is tight (at least for the first order term) and the upper bound is loose. Showing this or getting a tighter upper bound may require new proof techniques. A second question could be how to get an overall RDP guarantee if we are given local RDP guarantees instead of local LDP guarantees.

For the LHS and the RHS, we respectively have

Therefore, in order to show (49), it suffices to show 3foot_6 4 0 ≤ √ 3 0 , which is equivalent to 4 5 0 < 9 . Thus, we have shown that 4 5 0 < 9 implies (48). Now we show that when 4 5 0 < 9 , (46) and (47) are automatically satisfied:

(1) Proof of (46):

In the second inequality we used ≥ 1 and in the penultimate inequality we used 2 0 ≥ from (51). (2) Proof of (47): For this, first we upper-bound the LHS and lower-bound the RHS, and then note that the upper-bound is smaller than the lower-bound. For the upper-bound on exp( 0 --1 8 0 ), note that 0 ≤ 5 0 /4 = 5 0 4 1/4 <

foot_7/4 . Substituting these bounds in the exponent of exp( 0 --1 8 0 ), we get:

where ′ > 0 is a constant even for small values of . For example, for = 100, we get ′ ≥ 1 20 . For the lower-bound on

follows from 5 0 ≤ 4 5 0 < 9 . Now we show the lower bound:

Note that the upper-bound on exp( 0 --1 8 0 ) is exponentially small in 3/4 , whereas, the lower-bound on

is inverse-polynomial in . So, for sufficiently large , (47) will be satisfied. This completes the proof of Corollary 3.2 Claim 1 (An Inequality for the Gamma Function). For any ∈ N and ≥ 3, we have Γ( /2) ≤ .

. Note that for any ∈ N and ≤ , we have = ( -1) ( -2)...( -+1) ! . We show the claim separately for the cases when is an even integer or not.

(1) When is an even integer: Since for any integer ∈ N, Γ( ) = ( -1)!, so when is an even integer, we have

≤ .

(2) When is an odd integer: Note that for any integer ∈ N, we have Γ + 1 2 =

(2 )! 4 ! √ ; see [42]. Let = 2 + 1. Then

≤ where (a) follows because

. (P) and (P ′ ) can be written as the following convex combinations:

where P C , P ′ C are defined in (19)- (21).

. We only show (54); (55) can be shown similarly. For convenience, for any C ⊆ [ -1], define

With these notations, we can write

For any ∈ [ -1], define the following random variable :

For any subset C ⊆ [ -1], define an event

Consider an arbitrary ∈ A . Define a random variable (P) over A whose distribution is equal to (P).

where, P ′ | C |, and P [ -1]\C in the RHS of (e) are defined in the statement of the claim.

Since the above calculation holds for every ∈ A , we have proved (54).

B.2 Proof of Lemma 5.2

2). For any > 1, the function

is jointly convex in ( (P), (P ′ )), i.e.,

. For simplicity of notation, let = (P) and = (P ′ ).

, which is also called the Hellinger integral. In order to prove the lemma, it suffices to show that ∫ 1is jointly convex in ( , ), i.e., if

Proof of (58) is implicit in the proof of [39,Theorem 13]. However, for completeness, we prove (58) in Lemma B.1 below. Since = (P) and = (P ′ ) are convex combinations of C = (P C ) and C = (P ′ C ), respectively, with same coefficients, repeated application of (58) implies (57).

P . Let ( ) = . It is easy to show that for any ≥ 1, ( ) is a convex function when > 0. This implies that for any point ∈ Ω in the sample space, we have

where the last inequality follows from the convexity of ( ). By multiplying both sides with ( ) and substituting the definition of ( ) = , we get

By integrating this equality, we get (59).

B.3 Proof of Lemma 5.3

we have

, where, for ∈ [ -1], P -= P \ { } and P ′ -= P ′ \ { }. Note that in the LHS, (P), (P ′ ) are distributions over A , whereas, in the RHS, (P -), (P ′ -) for any ∈ [ -1] are distributions over A -1 .

. First we show that E ∼ ( P ′ )

Note that due to the independence of R on different data points, for any = (ℎ 1 , . . . , ℎ ) ∈ A , we can recursively write the distributions (P)( ) and (P ′ )( ) (which are defined in (17)) as follows:

where = (ℎ 1 , . . . , ℎ -1 , ℎ -1, ℎ +1 , . . . , ℎ ) for any ∈ [ ]. Here, (P -), (P ′ -) are distributions over A -1 . 8 Fix any ∈ [ -1] and also fix arbitrary 1 , . . . , -1 , +1 , . . . , , ′ . Take any ∈ [0, 1], and consider = 0 + (1 -) 1 .

Let P = ( 1 , . . . , , . . . , ), P 0 = ( 1 , . . . , 0 , . . . , ), and P 1 = ( 1 , . . . , 1 , . . . , ). Similarly, let P ′ = ( 1 , . . . , , . . . , ′ ), P ′ 0 = ( 1 , . . . , 0 , . . . , ′ ), and P ′ 1 = ( 1 , . . . , 1 , . . . , ′ ). With these definitions, we have P = P 0 + (1 -)P 1 . Note that (P ) -= (P 0 ) -= (P 1 ) -.

Then, from the recursive definitions of (P) and (P ′ ) (given in (60) and (61), respectively), for any ∈ A , we get (P )( ) = =1 ((P ) -) ( ) 8 We assume that ( P -) ( ) = 0 and ( P ′ -) ( ) = 0 if ℎ -1 < 0. Similarly, we can show that (P ′ )( ) = (P ′ 0 )( )+(1-) (P ′ 1 )( ). Thus we have shown that

From Lemma B.1, we have that E ∼ ( P ′ )

is jointly convex in (P) and (P ′ ). As a result, we get The LDP constraints put some restrictions on the set of values that the distribution can take; however, the maximum value that E ∼ ( P ′ ) ( P) ( ) ( P ′ ) ( ) takes can only increase when we remove those constraints. We instead maximize it w.r.t. over the simplex Δ := {( 1 , . . . ,

) : ≥ 0 for ∈ [ ] and =1 = 1}. This implies

Substituting from (60) and ( 61) into (63), we get

Since maximizing a convex function over a polyhedron attains its maximum value at one of its vertices, and there are vertices in the simplex Δ , which are of the form * = 1 for some * ∈ [ ] and = 0 for all ≠ * , we have max

Since the 'th data point deterministically maps to the * 'th output by the mechanism R, the expectation term in the RHS of (a) has no dependence on the 'th data point, so we can safely remove that, which gives (b). This proves Lemma 5.

In the last equality, we used that P ′ (1) has zero mean, i.e., E ∼M ( D ) [ ( )] = 0.

(2) The variance of is equal to

(3) For ≥ 3, the th moment of is bounded by

is the Gamma function.

. For simplicity of notation, let 0 , 1 denote the distributions M (D ), M (D ′ ), respectively. As shown in (32), for any ∈ A , we have

]. Now we show the three properties.

(1) The mean of the random variable is given by

(2) The variance of the random variable is given by

Here, step (b) uses properties of multinomial distribution:

, and (see [38,Lemma 1.8])), we have that is a sub-Gaussian r.v.

with parameter 2 =

It follows that (h) = =1 is also a sub-Gaussian random variable with parameter 2 . The remaining steps are similar to bound the moments of a sub-Gaussian random variable. We write them here for completeness. From Chernoff bound we get

where (b) follows by setting = 2 . Similarly, we can bound the term Pr [-≥ ]. Thus, we get

Hence, the 'th moment of the random variable can be bounded by

where step (b) follows by setting = 2 2 2 (change of variables). In the last step, Γ

denotes the Gamma function. Thus, we conclude that for every ≥ 3, we

.

This completes the proof of Lemma 6.1.

C.2 Proof of Lemma 6.2

2). We have the following bound:

Since the function ( , ) = 2 is convex in ( , ) for > 0, it implies that the objective function ( , ′ ) is also convex in ( , ′ ).

It is easy to verify that T 0 is a polytope. Since we maximize a convex function ( , ′ ) over a polytope T 0 , the optimal solution is one of the vertices of the polytope. Note that any vertex ( , ′ ) of the polytope in dimensions satisfies all the LDP constraints (i.e., -0 ≤ ′ ≤ 0 , = 1, . . . , ) with equality. Without loss of generality, assume that the optimal solution ( ˜ , ˜ ′ ) is a vertex such that ˜ ′ ˜ = 0 for = 1, . . . , and ˜ ′ ˜ = -0 for = + 1, . . . , , for some ∈ [ ]. Thus, we have

Rearranging the above gives =1 ˜ = 1 0 +1 . This implies =1 ˜ ′ = 0 0 +1 , which in turn implies = +1 ˜ ′ = 1 0 +1 . Now the result follows from the following set of equalities:

where the last equality uses the identity 3 + 1 = ( + 1)( 2 -+ 1). This completes the proof of Lemma 6.2.

D OMITTED DETAILS FROM SECTION 6 D.1 Omitted Details from Section 7.1

Before proving (40), first we show an important property of that we will use in the proof. Here, steps (a) and (d) follow from the fact that is a non-increasing function of (see Lemma D.1). Step (b) follows from the Chernoff bound. In step (c), we used that M ( ) = R ( ) and M ( ′ ) = R ( ′ ), which together imply that

where the inequality follows because R is an 0 -LDP mechanism. (67)

. Fix an arbitrary ∈ N. Let (D , D ′ ) ∈ D same and = ( 1 , . . . , ), ′ = ( ′ 1 , . . . , ′ ) be the same as defined in the proof of Theorem 3.7 in Section 6.

where the first equality uses (32) and the last inequality follows from 1 + ≤ . In (68), is distributed according to M (D ) = H (R ( ), . . . , R ( )), where H denotes the shuffling operation on elements and range of R is equal to [ ]. Since all the data points are identical, and all clients use independent randomness for computing R ( ), we can assume, w.l.o.g., that M (D ) is a collection of i.i.d. random variables 1 , . . . ,

, where Pr [ = ] = for ∈ [ ]. Thus, we have (in the following, note that = (ℎ 1 , . . . , ℎ ) is a r.v.)

where 1 {• } denotes the indicator r.v. Substituting from (69) into (68), we get

where = [ 1 , . . . , ]. From Taylor expansion of = 1+ ∞ =1 ! , we get

where the inequality follows from .

(since 1 --≤ )

This completes the proof of Theorem 7.1.

In this section, we provide a complete proof of Theorem 3.4. Consider the binary case, where each data point can take a value from X = {0, 1}. Let the local randomizer R be the binary randomized response (2RR) mechanism, where Pr [R ( ) = ] = 0 0 +1 for ∈ X. It is easy to verify that R is an 0 -LDP mechanism. For simplicity, let = 1 0 +1 . Consider two neighboring datasets D, D ′ ∈ {0, 1} , where D = (0, . . . , 0, 0) and D ′ = (0, . . . , 0, 1). Let ∈ {0, . . . , } denote the number of ones in the output of the shuffler. As argued in Section 2.3 on page 4, since the output of the shuffle mechanism M can be thought of as the distribution of the number of ones in the output, we have that ∼ M (D) is distributed as a Binomial random variable Bin( , ). Thus, we have

(1 -) --1 .

It will be useful to compute

Thus, we have that In view of Remark 6, this completes the proof of Theorem 3.4.