{'fraction_non_alphanumeric': 0.03499608252807521, 'fraction_numerical': 0.012601201358056934, 'mean_word_length': 4.491753316600932, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
LDP-FL: Practical Private Aggregation in Federated Learning with Local Differential Privacy

Train machine learning models on sensitive user data has raised increasing privacy concerns in many areas. Federated learning is a popular approach for privacy protection that collects the local gradient information instead of real data. One way to achieve a strict privacy guarantee is to apply local differential privacy into federated learning. However, previous works do not give a practical solution due to three issues. First, the noisy data is close to its original value with high probability, increasing the risk of information exposure. Second, a large variance is introduced to the estimated average, causing poor accuracy. Last, the privacy budget explodes due to the high dimensionality of weights in deep learning models. In this paper, we proposed a novel design of local differential privacy mechanism for federated learning to address the abovementioned issues. It is capable of making the data more distinct from its original value and introducing lower variance. Moreover, the proposed mechanism bypasses the curse of dimensionality by splitting and shuffling model updates. A series of empirical evaluations on three commonly used datasets, MNIST, Fashion-MNIST and CIFAR-10, demonstrate that our solution can not only achieve superior deep learning performance but also provide a strong privacy guarantee at the same time.

Training deep learning models on sensitive user data has raised increasing privacy concerns in many areas. Federated learning is a popular approach for privacy protection that collects the local gradient information instead of raw data. One way to achieve a strict privacy guarantee is to apply local differential privacy into federated learning. However, previous work does not give a practical solution due to two issues. First, the range difference of weights in different deep learning model layers has not been explicitly considered when applying local differential privacy mechanism. Second, the privacy budget explodes due to the high dimensionality of weights in deep learning models and many query iterations of federated learning. In this paper, we proposed a novel design of a local differential privacy mechanism for federated learning to address the abovementioned issues. It makes the local weights update differentially private by adapting to the varying ranges at different layers of a deep neural network, which introduces a smaller variance of the estimated model weights, especially for deeper models. Moreover, the proposed mechanism bypasses the curse of dimensionality by parameter shuffling aggregation. Empirical evaluations on three commonly used datasets in prior differential privacy work, MNIST, Fashion-MNIST and CIFAR-10, demonstrate that our solution can not only achieve superior deep learning performance but also provide a strong privacy guarantee at the same time.

Introduction
Many attractive applications involve training models on highly sensitive data, e.g., diagnosis of diseases with medical records, or genetic sequences [Xu et al., 2021;Che et al., 2021]. In order to protect the privacy of the training data, the federated learning framework is of particular interest since it can provide a well-trained model without touching any sensitive data directly [McMahan et al., 2016]. The original purpose of the federated learning (FL) framework is to share the weights of * Corresponding Author the model trained on sensitive data instead of data directly. However, some studies show that the weights also can leak privacy and the original sensitive data can be recovered [Papernot et al., 2017]. In order to solve the problem, recent works start to use differential privacy to protect the private data in federated learning [Nguyên et al., 2016;Lyu et al., 2020;Sun and Lyu, 2020], but most of them cannot give a practical solution for deep learning on complex datasets due to the trade-off between privacy budget and performance.
Notably, there are at least two remaining challenges in applying local differential privacy (LDP) in FL. First, existing approaches have assumed a fixed range of weights for simplicity. However, in complicated models such as those used in deep learning tasks, the range of model weights at different neural network layer varies significantly. Assuming weights in all layers to be in a fixed range will introduce a large variance of the estimated model weights, which leads to the poor model accuracy. Second, when client uploads the local model to the server, the server can explore the private connections of model weights, which causes the privacy budget explosion due to the high dimensionality of deep learning models.
In this paper, we proposed Locally Differential Private Federated Learning (LDP-FL), a new local differential privacy mechanism to solve the above issues, as shown in Fig. 1. Our main contributions are multifold. First, we propose a new data perturbation with adaptive range by considering that model weights at different deep neural network (DNN) layer could vary significantly. We derive a more general LDP mechanism to illustrate the impact of the range on the variance of the estimated model weights. We also further demonstrate how the proposed adaptive range settings can greatly improve the accuracy of aggregated model, especially in deeper models. To the best of our knowledge, this is the first work that has considered and studied the necessity and effectiveness of adapting to the different model weights' ranges when applying LDP in federated learning. Second, we propose a parameter shuffling mechanism to each clients' weights to mitigate the privacy degradation caused by the high data dimensionality of deep learning models and many query iterations. Last, we evaluate LDP-FL on three commonly used datasets in previous works, MNIST [LeCun et al., 2010], Fashion-MNIST [Xiao et al., 2017] and CIFAR-10 [Krizhevsky et al., 2009]. The proposed mechanism achieves a privacy budget of = 1 with 0.97% accuracy loss on MNIST, a privacy budget of = 4 with 1.32% . . Figure 1: The overview of LDP-FL. Each client has a private dataset. After training their model locally, clients perturb their model weights with differentially private noise, and locally split and shuffle the weights to make them less likely to be linked together by the cloud. Finally, they send the weights to the cloud for aggregation. accuracy loss on FMNIST, and a privacy budget of = 10 with 1.09% accuracy loss on CIFAR-10, respectively. Our work gives the first practical LDP solution for federated deep learning with a superior performance. Due to space limitation, all proofs are in the appendix.

Preliminary
Federated Learning. FL [McMahan et al., 2016;Konečnỳ et al., 2016] has been proposed and widely used in different approaches. The motivation is to share the model weights instead of the private data for better privacy protection. Each client, the owner of private training data, updates a model locally, and sends all gradients or weights information to the cloud. The cloud aggregates such information from clients, updates a new central model (e.g., averaging all clients' weights), and then distributes it back to a fraction of clients for another round of model update. Such process is continued iteratively until a satisfying performance is achieved. Note that, to minimize communication, each client might take several mini-batch gradient descent steps in local model computation. Local Differential Privacy To enhance the privacy protection, differential privacy (DP) has been applied to federated learning [Bhowmick et al., 2018;Geyer et al., 2017]. Traditional DP requires a central trusted party which is often not realistic. To remove that limitation, local differential privacy (LDP) has been proposed. The definition of -LDP is given as below: Definition 1. [Dwork, 2011] A randomized mechanism M satisfies -LDP, for any pair input x and x in D, and any output Y of M, The privacy guarantee of mechanism M is controlled by privacy budget [Dwork, 2011], denoted as . A smaller value of indicates a stronger privacy guarantee.

Overview of LDP-FL
In this section, we introduce LDP-FL, a federated learning framework with LDP as shown in Fig.1. It consists of two steps, as described by Algorithm 1. Cloud Update. First, the cloud initializes the weights randomly at the beginning. Let n be the total number of local clients. Then, in the r-th communication round, the cloud will randomly select k r ≤ n clients to update their weights for local-side optimization. Unlike the previous works [Bhowmick et al., 2018;Erlingsson et al., 2014;Seif et al., 2020], where they assume that the aggregator already knows the identities (e.g., IP addresses) of the users but not their private data, our approach assumes the client remains anonymous to the cloud. Local Update. For each client, it contains its own private dataset. In each communication, the selected local clients will update their local models by the weight from the cloud. Next, each local model uses Stochastic Gradient Descent (SGD) [Robbins and Monro, 1951] to optimize the distinct local models' weights in parallel. In order to provide a practical privacy protection approach, each local client applies a split and shuffle mechanism on the weights of local model and sends each weight through an anonymous mechanism to the cloud. For splitting, we separate all parameters of the trained model, and tag them with their location in the network structure. For shuffling, we randomly generate a time t in Algorithm 3 to prevent the cloud from tracking the client owner of each parameter. Detailed description and discussion on parameter shuffling mechanism are given in the later section.

Privacy-Preserving Mechanism
In this section, we describe in details the two major components in LDP-FL for privacy-preservation.

Data Perturbation with Adaptive Range
To better understand the necessity of adaptive range in data perturbation, we first generalize the LDP mechanism in  by considering model weights' range.
Given the weights W of a model, the algorithm returns a perturbed tuple W * by randomizing each dimension of W . Let M be our mechanism, for each weight/entry w ∈ W , assuming w ∈ [c − r, c + r] where c is the center of w's range and r is the radius of the range (c, r depend on how we clip the weight). Therefore, we design the following LDP mechanism to perturb w.
2r(e +1) where w * is the reported noisy weight by our proposed LDP, and "w.p." stands for "with probability". Algorithm 2 shows the pseudo-code of this mechanism.
Algorithm 1: LDP-FL Input: n is the number of local clients; B is the local mini-batch size, E the number of local epochs, γ is the learning rate. 1 CloudUpdate 2 Initialize weights W 0 = {w 0 id | ∀id}, where id indicates the position of each weight; 3 Initialize the range by (C 0 , R 0 ) for layers of W 0 ; 4 SendT oClient(W 0 , k 0 , C 0 , R 0 ); 5 for each round l = 1, 2, . . . do 6 randomly select k l (k l ≤ n) local clients; 7 collect all weights updates {(id, w id ) | ∀id} from selected clients with SendT oCloud; 8 %Now calculate and update model weights W l ; 9 for each element w ∈ W l do 10 determine the id for w; ParameterShuffling(W s l+1 ); From (2), we can see that, with a certain privacy budget , the larger range which indicates the larger r, the larger range of perturbed weights w * which intuitively indicates a noisier perturbed weight. In Section 4, we give a formal privacy and utility analysis which shows that the larger r, the larger variance of the estimated model weights. This observation motivates us to consider the range variation of model weights when applying LDP. Therefore, we propose the adaptive range settings. The proposed adaptive range setting in private federated learning consists of several steps: • All clients and the server agree to the same weight range, represented by (C 0 , R 0 ) based on prior knowledge at the beginning when initializing weights.
• In local update, based on the weight range (c l , r l ) of each layer where c l ∈ C and r l ∈ R, each local client can perturb its weights by the proposed LDP data perturbation given by (2).
• In cloud update, the cloud calculates and updates C and R from the local weights update received from clients. The updated C and R will be distributed to the clients when the cloud distributes the updated weights.
Algorithm 2: DataPertubation Input: Original local weights W s l+1 , range represented by C l and R l , privacy budget Output: Perturbed weights W s l+1 1 for each w ∈ W s l+1 and corresponding c ∈ C l and r ∈ R l do 2 Sample a Bernoulli variable u such that

Algorithm 3: ParameterShuffling
Input: Perturbed weights W s l+1 after Algorithm 2 1 label the position id of each element of W ; 2 for each element w s ∈ W do Note that range parameters C and R are calculated layer-wise, i.e., they are vectors with each element corresponding to one layer in the model. A pseudo-code of adaptive range settings is given in Algorithm 1. Our adaptive range setting gives a new feasible approach to set up the weight range and improves the utility for complex deep learning tasks.

Parameter Shuffling
As noted in [Dwork et al., 2014], a sophisticated privacypreserving system composites multiple locally differentiate algorithms that lead to a composition of privacy cost of such algorithms. That is, a combination of locally differentiate algorithm with privacy budget 1 and 2 consumes a privacy budget of 1 + 2 . Training a DNN using federated learning requires clients to upload gradient updates to the cloud in multiple iterations. If LDP is applied at each iteration along the iterative training process, the privacy budget will accumulate, which causes the explosion of the total privacy budget.
Previous efforts [Bittau et al., 2017;Erlingsson et al., 2019] have shown that when data reports are properly anonymized at each timestep and unlinkable over the time, the overall privacy guarantee can be greatly improved. That is, by adding anonymity onto the local model updates in LDP-FL, it can break the linkage from the received data at the cloud to a specific client and decouple the gradient updates sent from the same client in each iteration. This can be achieved by multiple existing mechanisms, depending on how the server tracks clients in the specific scenario. As a typically best practice for  Figure 2: Example of parameter shuffling in LDP-FL. π is a random shuffling mechanism. Note that, the parameter shuffling is composed of parameter shuffling mechanisms. The cloud will aggregate all kinds of information from clients. privacy, a certain level of anonymity of each client to the server is applied to disassociate clients' individually-identifiable information from their weight updates. For example, if the server tracks clients by IP address, each client can adopt an untraceable IP address by using a network proxy, a VPN service [Belesi, 2016], public WiFi access, and/or the Tor [Dingledine et al., 2004]. For another example, if the server tracks clients by software-generated metadata such as an ID, each client can randomize this metadata before sending it to the server.
However, we argue that client anonymity is not sufficient to prevent side-channel linkage attacks, e.g., the cloud can still link a large number of weight updates together if the client uploaded them at the same time in each iteration. Therefore, we design the local parameter shuffling mechanism to break the linkage among the model weight updates from the same clients and to mix them among updates from other clients, making it harder for the cloud to combine more than one piece of updates to infer more information about any client.  Fig. 2 (1). However, prior works doesn't consider the privacy issue due to the high dimensionality of the DNN weights. To solve the curse of the high dimensionality of DNN models, parameter shuffling is executed in two steps. In the first step, each client splits the weights of their local model, but labels each weight with an id to indicate its location of the weight in the network structure. In the second step, each client samples a small random latency t from a uniform distribution U (0, T ), where T > 0, for each weight and waits for t before sending the weight to the cloud. Note that T is agreed by all clients at the beginning of federated learning, e.g., by broadcasting their proposed T and computing the median of them (not computing average because average is vulnerable to a single dishonest client's influence). Since all uploads happen uniformly randomly during the same period of time, the cloud cannot distinguish them by upload time and cannot associate the weights updates from the same client. An approach is given in Algorithm 3.
In practical scenarios, the clients might spend different time in training (due to different hardwares) and in communications (due to different network conditions). The above design of the random delay for each client can accommodate such a heterogeneity with a minor adjustment. For client i, we denote the local computing time, the communication time, the proposed random delay for j-th model parameter by t i LC , t i C and t i j , respectively. Define T S = max i {t i LC + t i C }, which represents the response time of the slowest client without parameter shuffling. At the beginning of each iteration, T S can be estimated from clients' predictions of the corresponding t i LC and t i C based on their hardware specifications and communication settings. Instead of having t i j ∼ U (0, T ) as originally proposed in the paper, we set t That is, when sending any parameter, client i waits T i W before adding a random delay uniformly distributed from 0 to T . The resulting response time for j-th model parameter by client i, defined as t i LC + t i j + t i C , can be then rewritten as T S +t i j . This shows that adding T i W has no negative effect and the additional delay overhead is still controlled by T , as the delay of each iteration is decided by the slowest client (at least T S ). The response times of all parameter updates are still random and uniformly distributed. Therefore, the client anonymity is preserved, and the privacy budget won't accumulate. Besides, additional methods, such as not selecting the slower device (as the reviewer also mentioned), optimizing the local computing or applying asynchronous FL, can be applied regardlessly.
In theory, T can be as small as clients and cloud can support, to add enough randomness to the parameter shuffling. In practice, T might be given a safe margin by considering the imperfectness of time synchronization and the estimation of T S , and the unavoidable randomness in local computing (for example, device sluggish) and communications (for example, packet drop), so that the parameter updates reaches the cloud randomly. In any case, T is expected to be a small impact on the time cost of each FL iteration.
In this section, we analyze the privacy guarantee and utility cost of our approach, and compare it with other LDP mechanisms. Due to limited space, all proofs of lemmas and theorems are given in the appendix. Local Differential Privacy We prove the proposed random noise mechanism M satisfies LDP w.r.t. a bounding range. Theorem 1. Given any single number w ∈ [c − r, c + r], where c is the center of w's range and r is the radius of the range, the proposed mechanism M in Eq. 2 satisfies -LDP w.r.t. [c − r, c + r].
Both , r affect the privacy level. determines how well the data is hidden in a "crowd" and r determines the size of the "crowd". Suppose the true average weights in an iteration is w = 1 n u w u for each w ∈ W , the proposed LDP mechanism in Eq. 2 induces zero bias in calculating the average weight M(w) = 1 n u M(w u ). Lemma 1. Algorithm 2 introduces zero bias to estimating average weights, i.e., E[M(w)] =w.
The following lemmas show the variance of the data obtained by the cloud. First, the proposed mechanism leads to a variance to each reported weight M(w). Lemma 2. Let M be the proposed data perturbation mechanism. Given any number w, the variance of the mechanism is r 2 (e + 1) 2 n(e − 1) 2 − r 2 n ≤ V ar[M(w)] ≤ r 2 (e + 1) 2 n(e − 1) 2 . It can be seen from Lemma 3 that, with enough clients (a large n), we can achieve a low variance on the estimated average weight with a wide range of perturbed data (a large r) and a small privacy cost (a small ). With the above lemmas, we conclude the following theorem that shows the accuracy guarantee for calculating average weights on the cloud. Theorem 2. For any weight w ∈ W , with at least 1 − β Adaptive Range Setting If the weights' ranges are adaptive, clients may choose different c, r to bound their weights and a client may choose different c, r for each of its weights in each round. In such cases, LDP is still satisfied because the noise is applied to each weight separately. It is straightforward that the bias of the estimated average weight is still 0. For variance, we can derive a corollary from Lemma 3. Parameter Shuffling As we claimed before, LDP-FL uses parameter shuffling to bypass the curse of dimensionality. Since the weights are split and uploaded anonymously, the cloud is unable to link different weight values from the same client, so it cannot infer more information about a particular client. Therefore, it is sufficient to protect -LDP for each weight. Likewise, because of the client anonymity, the cloud is unable to link weights from the same client at different iterations. Without parameter shuffling, the privacy budget of LDP will grow to T d , where T is the iteration number and d is the number of weights in the model.  monyan and Zisserman, 2014] for the task. The training data and the testing data are fed into the network directly in each client, and for each client, the size of the training data is the total number of the training samples divided by the number of the clients. In this case, a larger number of clients indicates the small size of the training data of each client. For each weight, we clip them in a fixed range. In this work, we set (c, r) = (0, 0.075) and (0, 0.015) by default for MNIST and FMNIST, respectively. However, for CIFAR-10, instead of using a fixed range, due to the complexity of the model, we set c and r adaptively by the weight range of each layer. The learning rate γ is set as 0.03 for MNIST/FMNIST and 0.015 for CIFAR-10. Considering the randomness during perturbation, we run the test experiments ten times independently to obtain an averaged value. In order to evaluate the performance of different learning approaches, we use different metrics including accuracy for utility, for privacy cost and m, the number of communication rounds (CRs), for communication cost. Any approach with a high accuracy, a small and a small communication round indicates a good and practical solution. The proposed models are implemented using Pytorch, and all experiments are done with a single GPU NVIDIA Tesla V100 on the local server. Experiments on MNIST and FMNIST can be finished within an hour with 10 CRs, and experiments on CIFAR-10 need about 2 hours with 15 CRs. that when f r is too small, it does not affect the performance on MNIST, but affects significantly the performance on FM-NIST and CIFAR-10. When f r is close to 1, LDP-FL can achieve almost the same performance as the noise-free results on MNIST, FMNIST and CIFAR-10, as shown in Fig. 5(a-c). Another important parameter is the communication rounds between cloud and clients. It is not hard to see that with more communications, we can train a better model on all datasets through the proposed model. However, due to the complexity of data and tasks, CIFAR-10 needs more communication rounds for a better model. Fig. 3 shows that LDP-FL can achieve a high accuracy with a low privacy cost because of the new design of the communication and the new local data perturbation. While increasing the number of clients n in training, the LDP-FL can perform as close as the noise-free federated learning. Compared with MNIST (n = 100, = 1), FMNIST (n = 200, = 5), CIFAR-10 (n = 500, = 10) needs more clients, which indicates that for a more complex task with a larger neural network model, it requires more local data and more clients for a better performance against the data perturbation. The privacy budget also affects the performance of the central model, but more details will be discussed in the next section.

Analysis of Privacy Budget
To analyze the impact of privacy budgets on performance, we present the accuracy results with from 0.1 to 1 for MNIST, 1 to 10 FMNIST and 1 to 10 for CIFAR-10 in Fig. 5 (a-c). It shows that LDP-FL can maintain the accuracy at a high value for a wide range of privacy budgets on MNIST ( > 0.3), FMNIST ( > 2) and CIFAR-10 ( > 5). While < 0.3 for MNIST, < 2 for FMNIST and < 3 for CIFAR-10, the accuracy drops significantly. It is obvious that more complex data and tasks require more privacy cost. The main reason is that the complex task requires a sophisticated neural network, which contains a large number of model weights. Meanwhile, the range of each weight is also wider in the complex task, which causes a larger variance for the estimated weights.

Analysis of Adaptive Range Setting
To analyze the effectiveness of the adaptive weight range, we compare the accuracy with fixed range versus that with adaptive range for all three benchmark datasets in Table 1. We run the experiments for the privacy budget of = 5, and = 10, respectively. Clearly, for CIFAR-10, the adaptive range setting presents the greatest performance improvement over the fixed range setting. For example, in CIFAR-10 with = 10,  if (c, r) = (0, 1) is chosen for the fixed ranging setting, the adaptive range setting improves the accuracy by 45% over the fixed range setting. While on less complex datasets such as FMNIST and MNIST, we observe that the advantage of adaptive range setting gradually disappears. Specifically, on the MNIST dataset, there is no obvious difference in the accuracy achieved by the adaptive range setting and by the fixed range. This is because the model on CIFAR-10 is much deeper and more complex, such that the model weights' range in each layer differs significantly. In such a case, the adaptive range setting is able to reduce the variance of the estimated weights in some layers when the corresponding weight range is small. This improves the model accuracy dramatically. The results also explain why previous approach using fixed range can achieve a good accuracy on simple and shallow model. We take a closer look at the performance for CIFAR-10 with = 10. As illustrated in Figure 5(d), no matter how we tune the value of r for fixed range setting, the model accuracy always stay around 20% and can never be improved. The reason might be that the larger r increases the variance of model weights estimation, while the smaller r may generate the perturbed weights irrelevant to the true data range and cause an accuracy loss. We argue that for deeper neural networks, the fixed range setting might completely fail.

Related Work
Differential privacy [Dwork et al., 2014] provides a mathematically provable framework to design and evaluate a privacy protection scheme. Traditional differential privacy [Dwork et al., 2014], also known as Central Differential Privacy (CDP), considers the private data publication of the aggregated raw data. It usually assumes that a trusted data curator in the cloud perturbs the data statistic information by differential privacy mechanism. However, such assumption is often unrealistic in many use cases. Therefore, a new differential privacy model, Local Differential Privacy (LDP), was recently pro-posed [Duchi et al., 2013], in which, the raw data is perturbed before being sent to the data curator in the cloud.
Recently, more works studies how to use DP in federated learning [Geyer et al., 2017;McMahan et al., 2017] or use LDP in the federated learning [Bhowmick et al., 2018;Nguyên et al., 2016;Seif et al., 2020;Truex et al., 2020]. However, existing approaches can not be applied practically on deep learning. Some of them [Nguyên et al., 2016;Seif et al., 2020] only focus on small tasks and simple datasets and do not support deep learning approaches yet. The other works [Bhowmick et al., 2018;Truex et al., 2020] studied the LDP on federated learning problem. However, as we discussed in the experiments part, both of them hardly achieve a good performance with a small limited budget. Bhowmick et al. [Bhowmick et al., 2018] is the first work focus on the LDP on federated learning with deep learning models. However, it first need a strong assumption that attacker has little prior acknowledge about user data. Meanwhile, it spends = 500 for MINST and = 5000 for CIFAR-10, which means the LDP is not practical and needs traditional differential privacy for second protection. Last, they did not report the absolute performance on MNIST and CIFAR-10. Truex et al. [Truex et al., 2020] is another recent work. It uses It contains two obvious problems. First, it replaces LDP by Condensed LDP (CLDP), which spends a large privacy budget with a large clip bound reported in the work. Second, this work does not provide a complete privacy utility analysis of the number of weights and communication rounds. Due to the high variance of the noises in their approaches, it requires more communication rounds between cloud and clients, which spends more privacy cost in their framework. Our approach focus on solving the weakness of all previous approaches and accelerates the practical solution on complex dataset.

Conclusion
In this paper, we propose a new LDP mechanism for federated learning with DNNs. By giving a generalized data perturbation that is applicable for arbitrary input ranges, we proposed an adaptive range setting for improving privacy/utility trade-off. We also designed a parameter shuffling mechanism to mitigate the privacy degradation caused by high data dimension and many query iterations. Our empirical studies demonstrate that the performance of LDP-FL is superior to the previous related works on the same image classification tasks. Hopefully, our work can considerably accelerate the practical applications of LDP in federated learning.
A Proof Theorem 1. Given any single number w ∈ [c − r, c + r], where c is the center of w's range and r is the radius of the range, the proposed mechanism M in Eq. 2 satisfies -LDP w.r.t. [c − r, c + r].