Year: 2021

Abstract:
In this paper, we develop BitRand, a bit-aware randomized response algorithm, to preserve local differential privacy (LDP) in federated learning (FL). We encode embedded features extracted from clients’ local data into binary encoding bits, in which different bits have different impacts on the embedded features. Based upon that, we randomize all the bits to preserve LDP with three key advantages: (1) Bit-aware: Bits with a more substantial influence on the model utility have smaller randomization probabilities, and vice-versa, under the same privacy protection; (2) Dimension-elastic: Increasing the dimensions of embedded features, gradients, model outcomes, and training rounds marginally affect the randomization probabilities of binary encoding bits under the same privacy protection; and (3) LDP protection is achieved for both embedded features and labels with tight privacy loss and expected error bounds ensuring high model utility. Extensive theoretical and experimental results show that our BitRand significantly outperforms various baseline approaches in text and image classification.

heading: 1 INTRODUCTION
text: Recent data privacy and security regulations (GDPR, 2018; Regulation, 2018; Cybersecurity Law, 2016) pose major challenges in collecting and using personally sensitive data in different places for machine learning (ML) applications. Federated Learning (FL) (McMahan et al., 2017; Kairouz et al., 2019) is a promising way to address these challenges, enabling clients to jointly train ML models by sharing and aggregating gradients computed from clients’ local data through a coordinating server for model updates. However, recent attacks (Zhu et al., 2019; Y. et al., 2021; Zhao et al., 2020a) have shown that clients’ training samples, each of which includes an input x and a ground-truth label yx, can be extracted from the shared gradients. These attacks underscore the implicit privacy risk in FL.
Our main goal is to provide a strong guarantee that the shared gradients protect the privacy of clients’ local data without undue sacrifice in model utility. Local differential privacy (LDP) has emerged as a crucial component in various FL applications (Yang et al., 2019; Kairouz et al., 2019). To achieve our goal, we focus on preserving LDP in cross-device FL, i.e., in which clients jointly train an FL model (Kairouz et al., 2019).
In cross-device FL, existing LDP-preserving approaches can be categorized into three lines: Clients (1) add noise into local gradients derived from their local training samples, e.g., using Gaussian mechanism (Abadi et al., 2016), to protect membership information at the training sample level with DP guarantees (Zheng et al., 2021; Dong et al., 2019; Malekzadeh et al., 2021; Geyer et al., 2017; Huang et al., 2020), (2) add noise to local gradients using Randomized Response (RR) mechanisms to protect the values of the local gradients with LDP guarantees (Sun et al., 2021; Liu et al., 2020; Zhao et al., 2020b; Wang et al., 2019a), and (3) add noise into each training sample, e.g., embedded features and labels, using RR mechanisms to protect the value of each training sample with LDP guarantees (Arachchige et al., 2019; Lyu et al., 2020a), then the clients use LDP-preserved training samples to derive local gradients. For all three approaches, in each training round, clients send DP or LDP-preserved local gradients to the coordinating server for model updates, which will be sent back to the clients for the next training round.
In this paper, we focus on protecting clients’ training data at the value level with LDP guarantees. Existing RR mechanisms to preserve LDP in FL suffer from the curse of privacy composition, in which excessive privacy budgets are consumed proportionally to the large dimensions of input or embedded features (Arachchige et al., 2019), gradients (Zhao et al., 2020b; Wang et al., 2019a), and training rounds (Zhao et al., 2020b; Wang et al., 2019a), causing loose privacy protection or inferior model accuracy (Wagh et al., 2021).
Addressing the curse of privacy composition is non-trivial. Existing approaches, such as anonymizers (assumed to be trusted), i.e., shuffler (Erlingsson et al., 2019; Sun et al., 2021; L. et al., 2020; Wang et al., 2019b; Cheu et al., 2019; Balle et al., 2019) or anonymity approaches (e.g., faking source IP, VPN, Proxy, etc. (Sun et al., 2021; Cormode et al., 2018)), and dimension reduction (Liu et al., 2020; Zhao et al., 2020b; Shin et al., 2018; Xu et al., 2019), mitigate the problem but also have limitations. In the real world, it is possible that the anonymizers can either be compromised or collude with the coordinating server to extract sensitive information from observing LDP-preserved local gradients (Erlingsson et al., 2019). Meanwhile, applying RR mechanisms on reduced sets of embedded features or gradients using dimension reduction techniques can work well with lightweight models, such as logistic regression and SVM (Liu et al., 2020; Zhao et al., 2020b; Wang et al., 2019a). However, it is challenging for these techniques to achieve good model utility under tight LDP guarantees given complex models and tasks, such as DNNs, since the dimensions of reduced embedded features, gradients, and training rounds still need to be sufficiently large (Zhao et al., 2020b; Liu et al., 2020).
Hence, the curse of privacy composition in preserving LDP by applying RR mechanisms in FL remains a largely open problem. Orthogonal to this, preserving LDP to protect ground-truth labels yx in FL has not been well-studied. Two known approaches for centralized training are 1) injecting Laplace noise into the labels (Phan et al., 2020) and 2) applying RR mechanisms on the labels to achieve DP at the label level (Ghazi et al., 2021). However, centralized training in Ghazi et al. (2021) has not been designed for FL with LDP guarantees since they require centralized and trusted databases. The model utility in Phan et al. (2020) is notably affected by the number of model outcomes.
Key Contributions. To mitigate the curse of privacy composition and optimize the trade-off between privacy and model utility, our paper is structured around the following contributions: 1) We propose BitRand, which is a combination of a novel bit-aware f -RR mechanism and label-RR mechanism, to preserve LDP at both levels of embedded features and labels in FL. In f -RR, we encode embedded features (extracted from x) into a binary-bit string, which will be adaptively randomized such that bits with a more substantial impact on model utility will have smaller randomization probabilities and vice-versa under the same privacy budget. To preserve LDP on yx, we develop a generalized randomization, in which the probability of randomizing label yx from one to another class is a function of the number of model outcomes C. By doing that, we can optimize the trade-off between model utility and privacy loss with significantly tighter expected error bounds. 2) By incorporating sensitivities of binary encoding bits into a generalized privacy loss bound, we show that increasing the dimensions of embedded features r, encoding bits l, and model outcomes C marginally affect the randomization probabilities in BitRand under the same privacy budget. This dimension-elastic property is crucial to evade the curse of privacy composition by retaining a high value of data transmitted correctly through our randomization given large dimensions of r, l, and C. 3) These bit-aware and dimension-elastic properties allow us to work with complex models and tasks with formal LDP guarantees for training samples (x, yx) while retaining high model utility. Extensive theoretical analysis and experimental results conducted on fundamental FL tasks, i.e., text and image classification, using benchmark datasets and our collected Security and Exchange Commission financial contract dataset show that our BitRand significantly outperforms a variety of baseline approaches in terms of model utility under the same privacy budget.

heading: 2 BACKGROUND
text: LDP-preserving mechanisms (Erlingsson et al., 2014; Duchi et al., 2018; Wang et al., 2017; Acharya et al., 2019; Bassily & Smith, 2015) generally build on the ideas of randomized response (Warner, 1965), which was initially introduced to allow survey respondents to provide their correct inputs while maintaining their confidentiality. -LDP is presented as follows: Definition 1. -LDP. A randomized algorithmM fulfills -LDP, if for any two inputs x and x′, and for all possible outputs O ∈ Range(M), we have: Pr[M(x) = O] ≤ e Pr[M(x′) = O], where is a privacy budget and Range(M) denotes every possible output of the algorithmM. The privacy budget controls the amount by which the distributions induced by inputs x and x′ may differ. A smaller enforces a stronger privacy guarantee. We revisit RR mechanisms for LDP preservation in Appendix A. Our approach is a binary encoding-based approach, similar to (Arachchige et al., 2019; Lyu et al., 2020a), since it has the potential to overcome the curse of privacy composition. In binary encoding, x is converted into an l-bit vector v consisting of 1 sign bit, m bits for the integer part, and l−m−1 bits for the fraction part (Figure 1), as follows:
∀i ∈ [0, l − 1] : vi = b2i−m|x|c mod 2 (1)
Each bit in v is randomized by applying a RR mechanism, e.g., (Erlingsson et al., 2014; Bassily & Smith, 2015; Wang et al., 2017), to generate a perturbed l-bit vector v′, which preserves LDP. However, in our theoretical reassessment (Appendices I and J), directly applying RR mechanisms on binary encoded vectors as in existing mechanisms, i.e.,
LATENT (Arachchige et al., 2019) and OME (Lyu et al., 2020a), consumes huge privacy budgets since each binary encoding bit cannot be treated as a bit in a hash. Each binary encoding bit i has a different sensitivity, i.e., ∆i = 2m−i for the integer and fraction parts or ∆i = 2m+1 for the sign bit (Lemma 1), compared with a bit Bi in a hash, i.e., ∀Bi : ∆Bi = 1. Our mechanism does not suffer from this problem, thanks to our bit-aware randomization in binary encoding (Theorem 2).

heading: 3 BITRAND ALGORITHM
text: Let us now present our FL setting, threat model, and BitRand algorithm (Figure 2 and Alg. 1, Appendix B), and privacy guarantees. Then, we will show that our algorithm is dimension-elastic and the ability to opti-
mize the randomization probabilities with expected error bounds in our theoretical analysis.
Federated Learning Given N clients, each client u ∈ [1, N ] has a set of training samples Du = {(x, yx)}nu where x ∈ Rd is the input features, and its associated ground-truth label yx ∈ ZC is one-hot encoded with C categorical model outcomes {yx,1, . . . , yx,C}, and nu is the number of training samples. In a pre-processing step, each client u extracts r numerical embedded features from x, denoted ex, by using a pre-trained model fpre. In practice, fpre could be trained on large-scale and publicly available datasets without introducing any extra privacy cost to the clients’ local data (He et al., 2016; Devlin et al., 2018). N clients jointly train the model fθ : Rr → RC by minimizing a loss function L ( fθ(ex), yx ) on their local training samples in Du that penalizes mismatching between the prediction fθ(ex) and the ground-truth label yx, given the model’s parameters θ. In each training round t, each client u receives the most updated model parameters θt from the coordinating server and then computes local gradients5uθt = ∑ (vx,yx)∈Du 5θtL(f(ex), yx)/nu, which are sent
to the coordinating server for aggregating and model updating: θt+1 = θt − ηt ∑ u∈[1,N ]5uθt/N .
Threat Model. The coordinating server strictly follows the training procedure but curious about the training data Du. This is a practical threat model in the real world since service providers always aim at providing the best services to the clients (Haeberlen et al., 2011; Truex et al., 2019; Lyu et al., 2020b). Given the observed gradients 5uθt , the coordinating server can extract the clients’ data {ex, yx}nu by using recently developed attacks (Carlini et al., 2020; Fredrikson et al., 2015). In a defense-free environment, {ex, yx}nu can be used to infer the sensitive training data Du = {(x, yx)}nu using the pre-trained model fpre, since fpre(x) = ex (Song & Raghunathan, 2020). This poses a severe privacy risk to the sensitive data Du.
BitRand Algorithm. To protect the sensitive training data Du against the threat model, in our algorithm, we preserve LDP on both embedded features ex and labels yx.
Each of the r embedded features in ex is encoded into l binary bits following Eq. 1. Binary encoded features are concatenated together into a vector vx consisting of rl binary bits to represent the embedded features ex (Alg. 1, line 16). Each bit i ∈ [0, rl − 1] in vx is randomized by our f -RR mechanism (Alg. 1, line 17) with a bit-aware term i%ll optimizing randomization probabilities:
(f -RR mechanism) ∀i ∈ [0, rl − 1] : P (v′x(i) = 1) =  pX =
1
1 + α exp( i%l l X)
, if vx(i) = 1
qX = α exp( i%l l X)
1 + α exp( i%l l X)
, if vx(i) = 0 (2)
where vx(i) ∈ {0, 1} is the value of vx at the bit i, v′x is the perturbed vector created by randomizing all the bits in vx, X is a privacy budget, and α is a parameter bounded in Theorem 2. From Eq. 2, we also have that P (v′x(i) = 0) = 1− pX if vx(i) = 1, and P (v′x(i) = 0) = 1− qX if vx(i) = 0. We use the bit-aware term i%ll to indicate the location of bit i, which is associated with the sensitivity of the bit at that location, in its l-bit binary encoded vector among rl concatenated binary bits.
One of the key differences between our mechanism and existing works (Sun et al., 2021; Zhao et al., 2020b; Wang et al., 2019a; Liu et al., 2020; Arachchige et al., 2019; Lyu et al., 2020a) is the bit-aware randomization probabilities. By introducing the bit-aware term i%ll , we are able to: 1) Derive significantly tighter privacy loss and expected error bounds compared with existing approaches (Sections 4 and 5); and 2) Adaptively control the randomization probabilities across bits, such that bits with a stronger influence on the model utility, e.g., sign bits and integer bits, have smaller randomization probabilities qX , and vice-versa (Section 5). These advantages are crucial to evade the curse of privacy composition enabling us to work with complex tasks and models (Section 6).
In addition, inspired by the LabelDP (Ghazi et al., 2021), we randomize yx using the following label-RR mechanism (Alg. 1, line 18):
(label-RR mechanism) P (y′x = ȳx) =  pY = exp(β) 1 + exp(β) , if ȳx = yx qY = 1
(1 + exp(β))(C − 1) , if ȳx 6= yx, ȳx ∈ Z C
(3)
where ȳx is one-hot encoded, and β is a parameter bounded in Theorem 3 under a privacy budget Y .
Randomizing the label yx provides a complete LDP protection to each local training sample (ex, yx). All the perturbed training samples (e′x, y ′ x) are included in a local dataset D ′ u, which will be used to train the model fθ : Rr → RC , i.e., e′x = E(v′x) where E(·) is a decoding function, (Alg. 1, lines 20-22). The training will never access the original data Du. All other operations remain the same with our aforementioned FL setting.

heading: 4 PRIVACY GUARANTEES OF BITRAND
text: In this section, we focus on bounding formal privacy loss of BitRand for input and label protection. To achieve our goal, we need to bound α and β in Eqs. 2 and 3 such that our algorithm preserves LDP for each training sample (x, yx) ∈ Du given (v′x, y′x) ∈ D′u. Note that the decoding e′x = E(v′x) does not incur any extra privacy risk following the post-processing property (Dwork & Roth, 2014). Given vx and ṽx can be different at any bit, for the LDP condition to hold, the ratio of two probabilities P (f -RR(vx)=vz) P (f -RR(ṽx)=vz) needs to be bounded by exp( X) with vz ∈ Range(f -RR).
Given a feature a, i.e., one of the r features, let us first consider a bit i in the encoding vector va. Intuitively, when we apply our f -RR only on the bit i in va (i.e., all the other bits remain the same), denoted as f -RR(va, i), the l1-sensitivity of the bit i is 1. This is because, given two neighboring vectors va and va|i that differs only at the bit i, we have that ∀i ∈ va : arg maxva‖f -RR(va, i) − f -RR(va|i, i)‖1 = 1. However, the coordinating server can infer the decoded features E(f -RR(va)) instead of just the intermediate result f -RR(va). Thus, we need to quantify the l1-sensitivity of a single encoding bit i ∈ va to determine just how accurately we can return the decoded features E(f -RR(va)) through our randomization f -RR applied on va. Following (Dwork & Roth, 2014), the sensitivity ∆i of a bit i can be quatified as follows: Definition 2. Bit l1-sensitivity. Given two neighboring vectors va and va|i that differs only at a bit i, the sensitivity ∆i captures the magnitude by which the bit i can change the decoding function E(f -RR(·)) in the worst case, as follows:
∀i ∈ [0, rl − 1] : ∆i = max va ‖E ( f -RR(va) ) − E ( f -RR(va|i) ) ‖1 (4)
Based on Eq. 4, sensitivities ∆i of all the bits in vx are bounded in the following lemma. Lemma 1. The l1-sensitivity of a single binary encoding bit is bounded as follows:
∀i ∈ [0, rl − 1] : ∆i =
{ 2m+1, if i is a sign bit
2m−i%l, if i is an integer/fraction bit (5)
All the proofs are in Appendix. Unlike existing RR mechanisms, we incorporate the l1-sensitivity ∆i into the privacy loss bound of f -RR by ensuring that the privacy loss in randomizing a bit i is bounded by the privacy loss in the embedded feature space. By doing so, we can derive tighter privacy loss bounds as discussed next.
Given ∆i, there always exists a Laplace noise injected into the feature a, i.e.,M(va, i) = E(va) + Lap(∆i/ i), to achieve i-LDP in the embedded feature space (Dwork & Roth, 2014). In other words, P (M(va,i)=z)P (M(va|i,i)=z) ≤ exp( i|E(va)−E(va|i)| ∆i ) and z ∈ Range(M). To ensure that the privacy loss
in randomizing the bit i is bounded by the privacy loss in the embedded feature space is to find α in Eq. 2 such that: P (f -RR(va,i)=vz)P (f -RR(va|i,i)=vz) ≤ exp( i|E(va)−E(va|i)| ∆i
). However, randomizing a binary encoding bit i given va and va|i results in a smaller l1-distance |E(f -RR(va, i))− E(f -RR(va|i, i))| compared with |E(va) − E(va|i)|; since |E(f -RR(va, i)) − E(f -RR(va|i, i))| ≤ |E(va) − E(va|i)|. Thus, we can derive a tighter bound by replacing |E(va)− E(va|i)| with |E(f -RR(va, i))− E(f -RR(va|i, i))|. Given va(i) is the bit i in va, we have
P (f -RR(va, i) = vz) P (f -RR(va|i, i) = vz) = P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i))
× ∏
j 6=i,j∈[0,l−1]
P (va(j) = vz(j))
P (va|i(j) = vz(j))
= P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ≤ exp( i|E(f -RR(va, i))− E(f -RR(va|i, i))| ∆i ) (6)
However, finding a closed-form solution of α for the tight privacy bound in Eq. 6 is non-trivial, since i is intractable. To address this, we consider two cases: (1)
P (f -RR(va(i))=vz(i)) P (f -RR(va|i(i))=vz(i)) ≥ 1 below, and (2)
0 < P (f -RR(va(i))=vz(i))P (f -RR(va|i(i))=vz(i)) < 1 in Appendix D. Since ∆i captures the magnitude by which the bit i can change the decoding function E(·) in the worst case, we have ∆i|E(f -RR(va,i))−E(f -RR(va|i,i))| ≥ 1. As a result, we have
P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ≤ ( P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ) ∆i |E(f -RR(va,i))−E(f -RR(va|i,i))| ≤ exp( i) (7)
Eq. 7 enables us to quantify a generalized privacy loss bound of a RR mechanism, in which different bits have different sensitivities by randomizing all the bits in vx independently in Theorem 1. Theorem 1. Generalized privacy loss bound. The privacy loss for randomizing a binary encoding vector vx is bounded as follows:
P (f -RR(vx) = vz) P (f -RR(ṽx) = vz) ≤ rl−1∏ i=0 ( P (f -RR(vx(i)) = vz(i)) P (f -RR(vx|i(i)) = vz(i)) ) ∆i |E(f -RR(vx,i))−E(f -RR(vx|i,i))| ≤ exp( rl−1∑ i=0 i) (8)
Now, we enforce the condition ∑rl−1 i=0 i = X to ensure that the total privacy budget will be bounded by X . Based upon that, we derive a closed-form solution showing that there always exists an upper bound of α so that v′x preserves X -LDP given vx in Theorem 2 (Alg. 1, line 17). Theorem 2. ∀α : 0 < α ≤ √ X+rl
2r ∑l−1 i=0 exp(2 X l i%l)
, the f -RR mechanism satisfies X -LDP: P (f -RR(vx)=z) P (f -RR(ṽx)=z) < X , where vx and ṽx can be different at any bit, and z ∈ Range(f -RR).
Regarding to the ground-truth label yx, given a privacy budget Y , we show that there always exists an upper bound of β so that y′x preserves Y -LDP given yx. Theorem 3. ∀β : β ≤ Y − ln(C − 1), the label-RR mechanism (Alg. 1, line 18) satisfies Y -LDP: P (label-RR(yx)=z|yx) P (label-RR(ỹx)=z|ỹx) ≤ exp( Y ), given any distinct labels yx and ỹx, and z ∈ Range(label-RR).
From Theorems 2 and 3, our BitRand preserves X -LDP for the vector vx and Y -LDP for label yx. The gradients 5uθt preserve ( X , Y )-LDP in any training rounds t for any training samples (x, yx) ∈ Du and for all clients u ∈ [1, N ]; since, ∀u, t: 5uθt are computed from the randomized training samples {(v′x, y′x)}nu without accessing any further information from {(x, yx)}nu .

heading: 5 PRIVACY AND UTILITY TRADE-OFF
text: As shown in Theorem 1, we can derive a tighter privacy loss bound. Therefore, we focus on understanding how BitRand can address the privacy-utility tradeoff in comparison with existing approaches by theoretically studying: (1) the utility of f -RR regarding the expected error bound (Theorem 4), and (2) the trade-off between privacy budget and randomization probabilities. All statistical tests are 2-tail t-tests.
Expected Error Bounds. We analyze the data utility through expected error, denoted as ξa, measuring the
expected change of each embedded feature a after applying f -RR: ξa = E|E(f -RR(va))− E(va)|. The smaller expected error is, the better data utility the randomization mechanism achieves. The expected error ξa is bounded by ∑ i∈[0,l−1] qXi ×∆i. Theorem 4. The f -RR expected error bound is quantified by ξa = E|E(f -RR(va)) − E(va)| =∑ i∈[0,l−1] qXi ×∆i.
Theorem 4 can be directly applied to quantify the expected error bounds of f -RR without the bitaware term i%l/l, corrected LATENT (Appendix I), and corrected OME (Appendix J). Regarding existing mechanisms applied on the embedded feature a, including Duchi mechanism (DM) (Duchi et al., 2013), Piecewise mechanism (PM) (Wang et al., 2019a), Hybrid mechanism (HM) (Wang et al., 2019a), Suboptimal mechanism (PM-SUB) (Zhao et al., 2020b), Gaussian and Laplace (Dwork & Roth, 2014), we derive a general form of expected error bounds ξa for these mechanisms as: ξa = E|M(a) − a| u 1/r ∑ a∈[1,r] |M(a) − a| whereM is an X -LDP preserving mechanism,
since limr→∞ E|M(a)− a| = 1/r ∑ a∈[1,r] |M(a)− a|.
Figure 3 illustrates the expected error bound of each algorithm as a function of X . It is obvious that f -RR has significantly tighter expected error bounds compared with baseline approaches under a wide range of privacy budgets given reasonable large numbers of embedded features and encoding bits (p = 0.02); thus indicating that our mechanism achieves better data utility compared with the baselines. The improvement of our f -RR over existing mechanisms is larger when X increases.
To profoundly study the data utility, we take a depth look into bit-level analysis by relaxing Theorem 4 into (1) an expected error bound ξi = qXi ×∆i for each bit i ∈ [0, l− 1], and (2) an average top-k expected error bound ξtop−k = 1/k ∑k i=0 ξi, ∀k ∈ [0, l − 1]. Figure 11 (Appendix K) show that, at the bit-level, f -RR achieves smaller values of ξi for most important bits, especially the sign bit and integer bits, and comparable ξi for least important bits, i.e., fraction bits. The gap between f -RR and the baselines are significantly larger given the ξtop−k. We obtain smaller values of ξtop−k for all k ∈ [0, l − 1], under a tight privacy budget X = 0.1. Importantly, when increasing privacy budget X (Figures 11b,c), the gap between f -RR and the baselines is larger. In fact, the expected error bounds in f -RR is reduced while the expected error bounds in the baselines are remained the same.
Privacy budget and randomization probabilities trade-off. Compared with existing RR mechanisms (Lyu et al., 2020a; Arachchige et al., 2019; Sun et al., 2021; Zhao et al., 2020b; Duchi & Rogers, 2019; Wang et al., 2019a; Liu et al., 2020), in our algorithm, bits with a stronger influence on the model utility, e.g., sign bits and integer bits, have smaller randomization probabilities qX , and vice-versa. This is because we consider the influence of each bit i through the term i%ll in modeling the randomization probabilities qX (and pX ). This unique property of our algorithm enables us to better optimize the trade-off between privacy loss and model utility.
to evaluate the average qX across bits. The smaller qtop-k is, the better the randomization probability qX is. Given a tight privacy budget X = 0.1, our mechanism and the corrected OME have a similar qtop-k. However, when X increases, i.e., X ∈ {1, 2}, our mechanism achieves significantly smaller values of qtop-k than the corrected OME (p = 5.1e− 3).

heading: 6 DIMENSION-ELASTIC ANALYSIS
text: In existing RR mechanisms, the curse of privacy composition is rooted in the privacy composition across bits l and features r (Duchi et al., 2013; Lyu et al., 2020a; Arachchige et al., 2019), gradients 5uθt (Zhao et al., 2020b; Wang et al., 2019a), and training rounds T (Zhao et al., 2020b; Wang et al.,
2019a). Thus, increasing the dimensions of l, r,5uθt , and T either significantly increases the privacy budget (i.e., resulting in loose privacy protection) (Wang et al., 2019a; 2017) or notably affects the randomization probabilities (i.e., the value transmitted correctly through the randomization becomes smaller resulting in poor utility (Wang et al., 2016a)) (Lyu et al., 2020a; Arachchige et al., 2019).
In Theorem 1, the privacy composition across bits and features is unavoidable. However, the values of embedded features transmitted correctly through our randomization mechanism is minimally affected when increasing the dimensions of r, l,5uθt , T , and C under the same X and Y . That enable us to evade the curse of privacy composition when working with complex models and tasks under rigorous LDP protection. To shed light into this property, we conduct a theoretical analysis to examine: (1) How the dimensions of r, l, gradients5uθt , and training rounds T impact the privacy budget X and the randomization probabilities qX and pX (= 1− qX); and (2) How the number of model outcomes C impacts the privacy budget Y and the randomization probabilities qY and pY . We select the upper bounds of α = √ ( X + rl)/(2r ∑l−1 i=0 exp(2 X i l )) and β = Y − ln(C − 1) (Theorems 2, 3) in our analysis.
Dimensions of gradients 5uθt and training rounds T . In BitRand, the clients only use the perturbed samples (v′x, y ′ x) to train their local models without accessing any further information from (x, yx). Thus, the privacy budgets X and Y are independent of the dimension of gradients 5uθt and the training rounds T , i.e., following the post-processing property in DP (Dwork & Roth, 2014). Also, the size of 5uθt and T do not affect the randomization probabilities, since5uθt and T are not used to model qX , pX , qY , and pY as in Eqs. 2 and 3.
Dimensions of embedded features r and encoding bits l. Varying the dimensions of r and l does not affect the privacy budget X ∈ R+, since there always exists an α for Theorem 2
to hold. However, it is necessary to understand the influence of varying r and l on the privacy-utility trade-off. We theoretically analyze the impacts of r and l on the randomization probabilities qX and pX , given fixed values of X . A model is expected to achieve higher model utility given smaller values of qX (higher values of pX ) under the same privacy budget. We examine qX and pX in the following experiments: (i) Fixing l, then varying r; and (ii) Fixing r, then varying l.
Figures 5 and 13 (Appendix K) illustrate qX as a function of r, under l ∈ {5, 20, 100, 1, 000} and X ∈ {0.1, 1, 2}. Varying r does not affect the randomization probability qX (and pX ) for all the bits in vx. To explain this, we take a deeper look into the α’s bound, which is the only factor affecting qX and pX . Given fixed X and l, ∑l−1 i=0 exp(2 X i l ) is a constant, denoted C. So,
we have α = √ ( X + rl)/(2rC) = √
( X r
+ l)/(2C) u √ l/(2C),
since Xr u 0.0 in practice. Thus, with fixed X and l, qX and pX are r-elastic, given α approximately is a constant √ l/(2C).
Now, we fix r = 1, 000, which is a decent number of embedded features, and show qX as a function of l under a wide range of r ∈ [10, 10, 000] and X ∈ {0.1, 1, 2} (Figures 6 and 14,
Appendix K). Given a tight privacy budget X = 0.1, varying l does not affect the randomization probability qX , i.e., m = bl/2c in our analysis covering most values of embedded features in practice. However, with higher values of X ∈ {1.0, 2.0}, using more encoding bits l lowers qX for most important bits, i.e., sign and integer bits; while increasing qX for least important bits, i.e., fraction bits. When l is large enough (l ≥ 20), the randomization probability qX is l-elastic since the impact of l becomes marginal to all the bits. This is also true for pX .
Number of model outcomes C. Similar to X , from Eq. 3 and Theorem 3, the privacy budget Y is not directly affected by the number of model outcomes C, since ∀C, X : ∃β for Theorem 3 to hold. However, C may impact the trade-off between privacy and model utility by affecting the randomization probabilities qY and pY . Figure 7 shows that, when C is sufficiently large, i.e., C ≥ 100, the randomization probability qY is C-elastic since the impact of C on qY is marginal given a wide range of the privacy budget Y . This is also true for pY . When Y increases, the randomization probability qY becomes smaller (pY becomes larger). This is a reasonable observation.
Thanks to the bit-aware and dimension-elastic properties, our BitRand can achieve high data utility, especially under tight privacy budgets and expected error bounds.
7 EXPERIMENTAL RESULTS
We have conducted an extensive experiment on benchmark datasets under two fundamental FL tasks, text and image classification, to shed light on understanding 1) the interplay among privacy budget and model utility in BitRand, 2) the effectiveness of the dimension-elastic and bit-aware properties on model utility, and 3) different settings of applying RR to preserve LDP.
Baseline Approaches. We consider a variety of LDP-preserving mechanisms as baseline approaches: (1) Binary encoding ap-
proaches, including the corrected LATENT (Arachchige et al., 2019) and the corrected OME (Lyu et al., 2020a) (Appendices I and J); (2) LDP-FL (Sun et al., 2021); (3) Duchi mechanism (DM) (Duchi et al., 2013); (4) Piecewise mechanism (PM) (Wang et al., 2019a); (5) Hybrid mechanism (HM) (Wang et al., 2019a); (6) Three-Outputs mechanism (Zhao et al., 2020b); (7) Suboptimal mechanism (PM-SUB) (Zhao et al., 2020b); and (8) Label-Laplace (Phan et al., 2020). Each baseline approach is applied to randomize (when applicable): (i) Embedded features ex; (ii) Gradients 5uθt ; and (iii) Gradients5 u θt
with a recent anonymizer (Sun et al., 2021) to reduce the privacy budget consumption. In addition, Label-Laplace is used as a baseline to protect the ground-truth labels yx. Note that, in our experiment, we use the upper bound of β resulting in the same randomizing probabilities as in LabelDP. Therefore, we do not include LabelDP in comparison. More details about the difference of label-RR and LabelDP are in Appendix G. These settings are widely accepted to preserve LDP in FL; thus, offering a comprehensive view of preserving LDP in FL. Note that LATENT, OME, and BitRand can only be applied on embedded features ex; while LDP-FL can only be applied on gradients 5uθt with and without the anonymizer (Sun et al., 2021). We include the Noiseless FL model trained on the original data Du to show upper-bounds and a Random guess model to understanding model utility better.
Datasets, Metrics, and Model Configuration. The complete details of the datasets, metrics, and model configuration are in Appendix L. We carried out our experiments on two textual datasets and two image datasets, including the AG dataset (Gulli et al., 2012), our collected Security and Exchange Commission (SEC) financial contract dataset, the large-scale celebFaces attributes (CelebA) dataset (Liu et al., 2015), and the Federated Extended MNIST (FEMNIST) dataset (Caldas et al., 2018). We use the test accuracy and the test area under the curve (AUC) as evaluation metrics. Models with higher values of test accuracy and AUC are better. We use the BERT-Base (Uncased) pre-trained model (ber; Devlin et al., 2018) to extract embedded features in the AG and SEC datasets. In the CelebA and FEMNIST datasets, we use the ResNet-18 pre-trained model (img; He et al., 2016). For text and image classification tasks, we use two fully connected layers on top of embedded features, each of which consists of 1, 500 hidden neurons and uses a ReLU activation function.
Evaluation Results. Comprehensive results show that BitRand offers stronger privacy protection with higher model utility, compared with all baseline approaches, as discussed next.
LDP-preserving approaches applied on the embedded features ex. Baseline approaches do not work well when they are applied on embedded features ex (Figures 15 and 19, Table 3, Appendix L). In SEC, AG, and FEMNIST datasets, BitRand achieves the highest model utility compared with the best baseline approach, which is the corrected OME, under a tight privacy budget X = 1. In terms of accuracy and AUC values, BitRand ( Y =∞) achieves an improvement of 46.03% and 38.51% in the AG dataset (p = 2.7e−22), 13.69% and 13.79% in the SEC dataset (p = 4.1e−12), and 21.62% and 13.42% in the FEMNIST dataset (p = 5.6e − 11) respectively. In the CelebA dataset (Table 3, Appendix L), BitRand outperforms the best baseline approach, i.e., PM-SUB, with an average improvement of 1.66% across all 40 attributes in terms of AUC measure (p = 1.2e− 2). Since the CelebA dataset is highly imbalanced, we use the AUC measure instead of the model accuracy. The gaps between BitRand and the baseline approaches are significantly wider when the privacy budget X is larger. In addition to X = 1, with a tight privacy budget for the class labels Y ∈ {1, 2.5}, BitRand still outperforms baseline approaches in most of cases, offering stronger privacy protection with better model utility, i.e., LDP at both embedded feature and label levels instead of only LDP on the embedded features as in baseline approaches.
The key reason is that, in the baseline approaches, the model utility is significantly affected by the size of the embedded features. Thanks to the dimension-elastic and bit-aware properties, BitRand can achieve high model accuracy and AUC values, especially under tight privacy budgets. In addition, BitRand achieves the highest improvement in the AG dataset, since it is a balanced dataset compared with the highly imbalanced CelebA dataset, in which BitRand achieves the least improvement. Addressing imbalanced data in FL under DP (Huang et al., 2020) is out-of-scope of our study.
LDP-preserving approaches applied on on gradients 5uθt without and with the anonymizer (Sun et al., 2021). We observe the same phenomenon when baseline approaches are applied on gradients 5uθt without and with the anonymizer (Sun et al., 2021), even though the gaps between BitRand and baseline approaches are (marginally) smaller (Figures 8, 16-17, 20, and Tables 4, 5, Appendix L). Without using the anonymizer in the baseline approaches, in terms of accuracy and AUC, compared with the best baseline approach PM-SUB, BitRand ( X = 1, Y = 1) achieves an improvement of 44.95% and 37.52% in the AG dataset (p = 3.9e− 20), 12.82% and 12.92% in the SEC dataset (p = 1.3e− 11), 24.17% and 13.40% in the FEMNIST dataset (p = 4.1e− 11). When the anonymizer is applied in the baseline approaches, in terms of accuracy and AUC, compared with the best baseline approache HM, our BitRand achieves an improvement of 39.38% and 32.75% in the AG dataset (p = 1.2e− 16), 13.59% and 13.69% in the SEC dataset (p = 2.1e− 10), and 23.12% and 37.02% in the FEMNIST dataset (p = 2.8e − 11). Regarding the CelebA dataset, BitRand outperforms the best baseline approaches, which are Three-outputs and HM, with improvements of 1.28% and 0.3%, in the cases of with and without the anonymizer, across all 40 attributes in terms of AUC (p = 3.1e−2). The model utility in baselines is affected by the size of gradients and the training rounds (when the anonymizer is not applied) and their finite numbers of randomization outputs of the gradients (Zhao et al., 2020b). Thanks to the bit-aware and dimension-agnostic properties, BitRand can achieve high model utility under rigorous LDP protection.
LDP-preserving labels. Figures 18, 21, and Table 3 (Appendix L) present the model utility of BitRand as a function of the privacy budgets X and Y , in which label-RR is replaced by the Label-Laplace, denoted as f -RR & Label-Laplace. label-RR outperforms the Label-Laplace in all values of X , Y , and datasets. Under rigorous LDP protection Y = 1 given X ∈ [1, 10], there is an average improvement of 9.65% accuracy and 7.92% AUC in the AG dataset (7.3e− 6), 7.84% accuracy and 7.35% AUC in the SEC dataset (1.2e− 5), and 9.91% accuracy and 10.55% AUC in the FEMNIST dataset (p = 9.8e− 5), and 2.04% AUC in the CelebA dataset (p = 1.6e− 2). The gaps are delicately smaller in the AG and SEC datasets, and substantially larger in the FEMNIST and CelebA datasets when Y is increased. Given Y = 2.5, there is an average improvement of 1.71% accuracy and 1.37% AUC in the AG dataset (8.5e− 2), 4.65% accuracy and 4.73% AUC in the SEC dataset (6.9e− 3), and 14.43% accuracy and 12.02% AUC in the FEMNIST dataset (p = 1.9e− 4), and 4.24% AUC in the CelebA dataset (p = 2.3e − 2). The reason is that Label-Laplace injects Laplace noise across C classes in a label yx causing more noisy model outcomes compared with label-RR, in which only one of the C model outcomes is selected as the result of the randomization.

heading: 8 CONCLUSION
text: In this paper, we introduced a bit-aware algorithm, called BitRand, providing rigorous LDP protection to both embedded features and labels in FL via binary encoding. In BitRand, the trade-off between the privacy budget consumption and randomization probabilities is dimension-elastic to the numbers of embedded features, encoding bits, gradients, model outcomes, and training rounds, enabling us to work with complex models and FL tasks. We further optimize the randomization probabilities by having smaller randomization probabilities assigned to more critical bits and vice-versa under the same privacy budgets. Theoretical analysis and extensive experiments showed that our BitRand outperforms baseline approaches in text and image classification.

heading: A REVISITING RANDOMIZED RESPONSE MECHANISMS FOR LDP
text: To preserve LDP given the client’s input x, we can apply existing RR mechanisms (Wang et al., 2016b; Fanti et al., 2015; Bassily et al., 2017; Kim et al., 2018; Ren et al., 2018; Zheng et al., 2017; Wang & Xu, 2019; Zhao et al., 2019; Gursoy et al., 2019; Alvim et al., 2018; Xiong et al., 2019), such as unary encoding-based approaches (Wang et al., 2017; Erlingsson et al., 2014), hash-based approaches (Wang et al., 2017; Bassily & Smith, 2015; Acharya et al., 2019; Wang et al., 2019c), binary encoding-based approaches (Arachchige et al., 2019; Lyu et al., 2020a), etc. For instance, hash-based approaches such as those of Google RAPPOR (Erlingsson et al., 2014) and OLH (Wang et al., 2017) hash the client’s input x onto a bloom filter B of size k using h hash functions. Then, for each client’s input x and a bit i ∈ B, RAPPOR creates a perturbed binary value B′i from Bi with the following randomization probability:
B′i =  1, with probability p/2 0, with probability p/2 Bi, with probability 1− p
(9)
where p is a hyper-parameter. This B′ is reused as the basis for all future analysis, learning, and reports on this distinct input x. This approach achieves X -LDP, where X = 2h ln((1 − p2 )/ p 2 ), given that the sensitivity of every bit Bi is ∆Bi = 1 (Erlingsson et al., 2014).
To deal with numerical inputs, e.g., embedded features, generalized RR mechanisms such as Duchi (Duchi & Rogers, 2019; Bhowmick et al., 2018), Piece-wise (Wang et al., 2019a), Hybrid (Wang et al., 2019a), Three-outputs (Zhao et al., 2020b), Suboptimal (Zhao et al., 2020b), LDP-FL (Sun et al., 2021), LATENT (Arachchige et al., 2019), and OME (Lyu et al., 2020a) can be applied.
Asymmetric version of RAPPOR (e.g., (Wang et al., 2017)) designs different randomization probabilities for different inputs. The technique is well-applied in the context of frequency estimation and successfully reduce the communication cost from O(d) to O(log n) (d is data dimension and n is the number of samples). However, simply applying the mechanism (Wang et al., 2017) does not optimize the model utility and the privacy-utility trade-off when working with machine learning or deep learning models.
Another line of work in LDP is Mironov (2012), which addresses the floating-point arithmetic in implementation of DP applications. The inconsistency between mathematical abstraction of Laplace mechanism with sampling “uniform” floating-point numbers can be exploited to carry out privacy attacks. Floating-point arithmetic is a leaky abstraction, which is ubiquitous in computer systems and is difficult to argue about formally and hard to get right in applications, including all the RR mechanisms.
However, different from the asymmetric version of RAPPOR and the floating-point arithmetic, our proposed f -RR mechanism focuses on mitigating the privacy-utility trade-off. To achieve that, besides the asymmetric nature of the randomization probabilities, our designed f -RR consists of two key components: 1) The bit-aware term i%l/l, which indicates the location of the bit i in each embedded feature associated with the sensitivity of the bit at that location; and 2) The adjustable but bounded α, which takes into account the correlation between privacy loss and the sensitivity of embedded features to mitigate the privacy-utility trade-off and the curse of privacy composition.
The bit-aware property refers to the bits with a more substantial influence on the model utility have smaller randomization probabilities, and vice-versa, under the same privacy protection. By incorporating sensitivities of binary encoding bits into a generalized privacy loss bound, we show that increasing the dimensions of embedded features r, encoding bits l, and model outcomes C marginally affect the randomization probabilities in BitRand under the same privacy budget. This dimension-elastic property is crucial to mitigate the curse of privacy composition by retaining a high value of data transmitted correctly through our randomization given large dimensions of r, l, and C.
Besides the f -RR for protecting the data, we also include the label-RR for protecting the label in our proposed BitRand mechanism, that provides a complete protection for every data sample.

heading: B BITRAND ALGORITHM PSEUDO-CODE
text: 1: Input: Privacy budget X and Y , number of training iterations T , learning rate ηt, binary encoding parameters (l and m) 2: At server side: 3: Initialize model θ0 4: Send the pre-trained model fpre to clients 5: for t ∈ T do 6: Distribute model parameter θt to each client 7: for each client u do 8: 5uθt ← Client-Update(θ
t) 9: end for 10: θt+1 = θt − ηt ∑ u∈[1,N ]5 u θt/N 11: end for 12: Output: ( X , Y )-LDP θ
13: At client side u ∈ [1, N ]: 14: for each data sample (x, yx) ∈ Du do 15: Extracting embedded features: ex ← fpre(x) 16: vx ← BinaryEncoding(ex) # using Eq. 1 17: Randomizing vx: v′x ← f -RR(vx) with
α =
√ X+rl
2r ∑l−1 i=0 exp(2 X i l ) # using Eq. 2
18: Randomizing the label yx: y′x ← label-RR(yx) with β = Y − ln(C − 1) # using Eq. 3 19: end for 20: Client-Update(θt): 21: 5uθt = ∑ (v′x,y ′ x)∈D′u
5θtL(f(e′x), y′x)/nu 22: return5uθt
Algorithm 1: BitRand Algorithm in Federated Learning

heading: C PROOF OF LEMMA 1
text: Proof. Without loss of generality, let us study the l1-sensitivity of binary encoding bits of a feature’s value a in ex. It is obvious that f -RR(va, i) and f -RR(va|i, i) differs at the bit i in the worst case. The decoded feature of f -RR(va, i) is a′ = E(f -RR(va, i)). Let us denote b0b1 . . . bl−1 as the binary representation f -RR(va, i) of a′, where b0 is the value of a sign bit (i.e., b0 = 1 if a′ >= 0 and b0 = 0 if a′ < 0), and {bi}l−1i=1 is the value of integer bits and fraction bits. We have a decoding function: E(f -RR(va, i)) = (2b0 − 1) ∑l−1 i=1 bi × 2m−i. This decoding function is also applicable to E(f -RR(va|i, i)). Let us denote {b′i} l−1 i=0 as the value of the bit i in f -RR(va|i, i). Following Eq. 4, the l1-sensitivity of the bit bi is computed as follows:
• If i is an integer or a fraction bit (i ∈ [1, l − 1]), we have: ∆i = maxva ‖ E(f -RR(va, i))−E ( f -RR(va|i, i) ) ‖1= maxva ‖(2b0−1) (∑l−1 j=1,j 6=i bj2 m−j+bi2 m−i ) −(2b0−
1) (∑l−1
j=1,j 6=i bj2 m−j + b′i2 m−i ) ‖1 = maxva ‖(2b0 − 1)(bi − b′i)2m−i‖1 ≤ maxva ( |(2b0 −
1)|‖bi − b′i‖12m−i )
. The ∆i is maximized when bi and b′i are different, and |2b0 − 1| = 1. Therefore, ∆i = 2m−i. • If i is the sign bit (i = 0), we have: ∆i = maxva ‖ E(f -RR(va, 0)) − E ( f -RR(va|i, 0) ) ‖1= maxva ‖(2b0 − 1) ∑l−1 i=1 bi2 m−i − (2b′0 − 1) ∑l−1 i=1 bi2
m−i‖1 = maxva ‖(2b0 − 2b′0) ∑l−1 i=1 bi2 m−i‖1 ≤ maxva ( |2b0 − 2b′0|‖ ∑l−1 i=1 bi2 m−i‖1 ) . The ∆i is maxi-
mized when b0 and b′0 are different and all {bi}l−1i=1 = 1. Then, ∆i ≤ maxva|0 2 ∑l−1 i=1 2
m−i. Since 21 + . . .+ 2l−2 = 2l−1 − 2 (mat), we have: 2 ∑l−1 i=1 2
m−i = 2m+1−(l−1)(2l−1 − 1) < 2m+1. As a result, ∆i = 2m+1.
From the aforementioned ∆i of a feature’s value in ex, it is easily expanded to the entire ex. Since ex is the concatenation of all l bits of r values in ex, all bits with the same value of i%l have the same l1-sensitivity across rl bits. Therefore, the ∆i of the sign bit and the integer/fraction bits are 2m+1 and 2m−i%l, respectively. Consequently, Lemma 1 hold.

heading: D PROOF OF THEOREM 1
text: Let us consider a bit i belonging to a feature a, i.e., one of the r features. We denote f -RR(va, i) as vector va with only the bit i randomized by our f -RR, i.e., all the bits different from i are kept the same in va; that is, we only protect the bit i when using the notation f -RR(va, i). Given the l1-sensitivity ∆i, there always exists a Laplace noise injected into the embedded feature a, i.e.,
M(va, i) = E(va) +Lap(∆i/ i), to achieve i-LDP in the embedded feature space (Dwork & Roth, 2014). In other words, P (M(va,i)=z)P (M(va|i,i)=z) ≤ exp( i|E(va)−E(va|i)| ∆i
) where va|i is the vector that differs from va only at the bit i and z ∈ Range(M). To ensure that the privacy loss in randomizing the bit i, we need to bound α in Eq. 2 such that P (f -RR(va,i)=vz) P (f -RR(va|i,i)=vz)
≤ exp( i|E(va)−E(va|i)|∆i ). However, randomizing a binary encoding bit i given va and va|i results in a smaller l1-distance |E(f -RR(va, i)) − E(f -RR(va|i, i))| compared with |E(va) − E(va|i)|; since |E(f -RR(va, i)) − E(f -RR(va|i, i))| ≤ |E(va) − E(va|i)|. Thus, we can derive a tighter bound by replacing |E(va) − E(va|i)| with |E(f -RR(va, i)) − E(f -RR(va|i, i))|. Given va(i) is the bit i in va, we have
P (f -RR(va, i) = vz) P (f -RR(va|i, i) = vz) = P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i))
× ∏
j 6=i,j∈[0,l−1]
P (va(j) = vz(j))
P (va|i(j) = vz(j))
= P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ≤ exp( i|E(f -RR(va, i))− E(f -RR(va|i, i))| ∆i ) (10)
However, finding a closed-form solution of α for the tight privacy bound in Eq. 10 is non-trivial, since i is intractable. To address this problem, we consider two cases: (1)
P (f -RR(va(i))=vz(i)) P (f -RR(va|i(i))=vz(i)) ≥ 1
and (2) 0 < P (f -RR(va(i))=vz(i))P (f -RR(va|i(i))=vz(i)) < 1. Also, since ∆i captures the magnitude by which a bit i can change the decoding function E() in the worst case, we have ∆i|E(f -RR(va,i))−E(f -RR(va|i,i))| ≥ 1.
In the first case, the privacy loss for a bit i can be bounded as follows:
P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ≤ ( P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ) ∆i |E(f -RR(va,i))−E(f -RR(va|i,i))| ≤ exp( i) (11)
Since the RR mechanism is independently applied on each bit i in va and on every va of the r features, Eq. 11 enables us to quantify a generalized privacy loss bound of a RR mechanism, in which different bits have different sensitivities to the randomized outcome as follows.
P (f -RR(vx) = vz) P (f -RR(ṽx) = vz) = rl−1∏ i=0 P (f -RR(vx(i)) = vz(i)) P (f -RR(vx|i(i)) = vz(i))
≤ rl−1∏ i=0 ( P (f -RR(vx(i)) = vz(i)) P (f -RR(vx|i(i)) = vz(i)) ) ∆i |E(f -RR(vx,i))−E(f -RR(vx|i,i))| ≤ rl−1∏ i=0 exp( i) = exp( rl−1∑ i=0 i)
(12)
In the second case, the privacy loss for a bit i can be bounded as follows:
P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ≤ P (f -RR(va|i(i)) = vz(i)) P (f -RR(va(i)) = vz(i))
≤ (P (f -RR(va|i(i)) = vz(i)) P (f -RR(va(i)) = vz(i)) ) ∆i |E(f -RR(va,i))−E(f -RR(va|i,i))| ≤ exp( i)
(13)
Similarly, we obtain the same result with Eq. 12 in the second case:
P (f -RR(vx) = vz) P (f -RR(ṽx) = vz) = rl−1∏ i=0 P (f -RR(vx(i)) = vz(i)) P (f -RR(vx|i(i)) = vz(i)) ≤ rl−1∏ i=0 P (f -RR(vx|i(i)) = vz(i)) P (f -RR(vx(i)) = vz(i))
≤ rl−1∏ i=0 (P (f -RR(vx|i(i)) = vz(i)) P (f -RR(vx(i)) = vz(i)) ) ∆i |E(f -RR(vx,i))−E(f -RR(vx|i,i))| ≤ rl−1∏ i=0 exp( i) = exp( rl−1∑ i=0 i)
(14)
Consequently, Theorem 1 holds.

heading: E PROOF OF THEOREM 2
text: To ensure that the privacy loss in randomizing the bit i is bounded by the privacy loss in the embedded space and to take into account different sensitivities of different bits (Theorem 1), we need to find α in Eq. 2 to solve Eq. 12. However, solving Eq. 12 is not straightforward since the privacy budget i and the actual l1-distance |E(f -RR(vx, i)) − E(f -RR(vx|i, i))| are intractable. To address this problem, from Eq. 12, we first consider the bit i in all the r embedded features, as follows: ∏ a∈[1,r] P (f -RR(va(i))=vz(i)) P (f -RR(va|i(i))=vz(i)) ≤ exp( ∑ a∈[1,r] i|E(f -RR(va,i))−E(f -RR(va|i,i))| ∆i ) =
exp( i∆i ∑ a∈[1,r] |E(f -RR(va, i)) − E(f -RR(va|i, i))|). Note that all the bits i, e.g., sign bits, in all the features a ∈ [1, r] consume the same privacy budget i with the same sensitivity ∆i. The term ∑ a∈[1,r] |E(f -RR(va, i)) − E(f -RR(va|i, i))| can be unbiasedly replaced with r × E|E(f -RR(va, i)) − E(f -RR(va|i, i))| where E is the expectation of |E(f -RR(va, i)) − E(f -RR(va|i, i))|, since limr→∞ E|E(f -RR(va, i)) − E(f -RR(va|i, i))| =∑
a∈[1,r] |E(f -RR(va,i))−E(f -RR(va|i,i))| r . Hence, we have that∏
a∈[1,r]
P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ≤ exp( r i × E|E(f -RR(va, i))− E(f -RR(va|i, i))| ∆i )
⇔ ∏
a∈[1,r]
( P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ) ∆iE|E(f -RR(va,i))−E(f -RR(va|i,i))| ≤ exp(r i) (15) Note that, in our work, we consider the worst case is the case that all the bits of two neighboring vectors can be different. The expectation E|E(f -RR(va, i))− E(f -RR(va|i, i))| in Eq. 15 is used to quantify the difference of every two extreme vectors at bit i. Then for the whole vector, it is the sum over the expectation E(·) of all bits i, as follows: ∑ a∈[1,r] |E(f -RR(va, i))− E(f -RR(va|i, i))| = r × E|E(f -RR(va, i))− E(f -RR(va|i, i))|. Therefore, the expectation in Eq. 15 does not imply the average-case scenario.
The sum over the expectation E(·) of all bits i, i.e., ∑ a∈[1,r] ∑ i∈[0,l−1] |E(f -RR(va, i)) −
E(f -RR(va|i, i))| = r × ∑ i∈[0,l−1] E|E(f -RR(va, i)) − E(f -RR(va|i, i))|, is used to bound the privacy loss as follows:
P (f -RR(vx) = vz) P (f -RR(ṽx) = vz)
≤ ∏
a∈[1,r] ∏ i∈[0,l−1] ( P (f -RR(va(i)) = vz(i)) P (f -RR(va|i(i)) = vz(i)) ) ∆i E|E(f -RR(va,i))−E(f -RR(va|i,i))|
≤ exp( ∑ a∈[1,r] ∑ i∈[0,l−1] i|E(f -RR(va, i))− E(f -RR(va|i, i))| ∆i )
= exp( ∑
i∈[0,l−1]
i ( r × E|E(f -RR(va, i))− E(f -RR(va|i, i))| ) ∆i )
≤ exp(r ∑
i∈[0,l−1]
i)
⇔ rl−1∏ i=0 ( P (f -RR(vx(i)) = vz(i)) P (f -RR(vx|i(i)) = vz(i)) ) ∆i E|E(f -RR(vx,i))−E(f -RR(vx|i,i))| ≤ exp( rl−1∑ i=0 i) (16)
Now, we need to bound the generalized privacy loss by discovering closed-form solutions of α given the privacy budgets X (Theorem 2). In other words, we need to solve Eq. 16 for discovering the closed-form solution of α. To solve it, first we need to calculate E|E(f -RR(vx, i)) − E(f -RR(vx|i, i))|. To be more precise, let us denote pXi and qXi as pX and qX in Eq. 2 for a particular bit i, respectively. Given the worse case of vx and vx|i, there are four possible cases of |E(f -RR(vx, i))− E(f -RR(vx|i, i))|:
• If f -RR(vx(i)) = 1 and f -RR(vx|i(i)) = 1, then |E(f -RR(vx, i))− E(f -RR(vx|i, i))| = 0.
• If f -RR(vx(i)) = 0 and f -RR(vx|i(i)) = 0, then |E(f -RR(vx, i))− E(f -RR(vx|i, i))| = 0.
• If f -RR(vx(i)) = 1 and f -RR(vx|i(i)) = 0, then |E(f -RR(vx, i)) − E(f -RR(vx|i, i))| = ∆i. This happens with the probability P (f -RR(vx(i)) = 1, f -RR(vx|i(i)) = 0). To compute this probability, we use marginal probability and Bayes’ theorem, as follows:
P (f -RR(vx(i)) = 1, f -RR(vx|i(i)) = 0) = P ( f -RR(vx(i)) = 1, f -RR(vx|i(i)) = 0, vx(i) = 1, vx|i(i) = 0 ) + P ( f -RR(vx(i)) = 1, f -RR(vx|i(i)) = 0, vx(i) = 0, vx|i(i) = 1
) = P ( f -RR(vx(i)) = 1|f -RR(vx|i(i)) = 0, vx(i) = 1, vx|i(i) = 0
) × P (f -RR(vx|i(i)) = 0|vx(i) = 1, vx|i(i) = 0) × P (vx(i) = 1|vx|i(i) = 0)× P (vx|i(i) = 0)
+ P ( f -RR(vx(i)) = 1|f -RR(vx|i(i)) = 0, vx(i) = 0, vx|i(i) = 1 ) × P (f -RR(vx|i(i)) = 0|vx(i) = 0, vx|i(i) = 1) × P (vx(i) = 0|vx|i(i) = 1)× P (vx|i(i) = 1)
= P ( f -RR(vx(i)) = 1|vx(i) = 1 ) × P (f -RR(vx|i(i)) = 0|vx|i(i) = 0)× P (vx|i(i) = 0)
+ P ( f -RR(vx(i)) = 1|vx(i) = 0 ) × P (f -RR(vx|i(i)) = 0|vx|i(i) = 1)× P (vx|i(i) = 1)
= p2XiP (vx|i(i) = 0) + q 2 XiP (vx|i(i) = 1) (17)
• If f -RR(vx(i)) = 0 and f -RR(vx|i(i)) = 1, then |E(f -RR(vx(i))) − E(f -RR(vx|i(i)))| = ∆i. This happens with the probability P (f -RR(vx(i)) = 0, f -RR(vx|i(i)) = 1). To compute this probability, we use marginal probability and Bayes’ theorem, as follows:
P (f -RR(vx(i)) = 0, f -RR(vx|i(i)) = 1) = P ( f -RR(vx(i)) = 0, f -RR(vx|i(i)) = 1, vx(i) = 1, vx|i(i) = 0 ) + P ( f -RR(vx(i)) = 0, f -RR(vx|i(i)) = 1, vx(i) = 0, vx|i(i) = 1
) = q2XiP (vx|i(i) = 0) + p 2 XiP (vx|i(i) = 1) (18)
Consequently, the expectation E|E(f -RR(vx, i))− E(f -RR(vx|i, i))| is computed as follows:
E|E(f -RR(vx, i))− E(f -RR(vx|i, i))| = ( p2XiP (vx|i(i) = 0) + q 2 XiP (vx|i(i) = 1) ) ∆i
+ ( q2XiP (vx|i(i) = 0) + p 2 XiP (vx|i(i) = 1) ) ∆i
= (p2Xi + q 2 Xi)∆i (19)
From Eqs. 12, 16, and 19, we have that
P (f -RR(vx) = vz) P (f -RR(ṽx) = vz)
≤ rl−1∏ i=0 ( P (f -RR(vx(i)) = vz(i)) P (f -RR(vx|i(i)) = vz(i)) ) ∆i E|E(f -RR(vx,i))−E(f -RR(vx|i,i))|
= rl−1∏ i=0 (P (f -RR(vx(i)) = 0|vx(i) = 1)P (f -RR(vx(i)) = 1|vx(i) = 0) P (f -RR(vx(i)) = 1|vx(i) = 1)P (f -RR(vx(i)) = 0|vx(i) = 0) ) 1 p2 Xi +q2 Xi
= l−1∏ i=0 ( α2 exp(2 X i l ) ) r p2 Xi +(1−pXi)2 (20)
Taking the natural logarithm of two sides of Eq. 20:
ln P (f -RR(vx) = vz) P (f -RR(ṽx) = vz) ≤ l−1∑ i=0 ln ( α2 exp(2 X i l ) ) r p2 Xi +(1−pXi)2
= l−1∑ i=0 ( r p2Xi + (1− pXi)2 ln ( α2 exp(2 X i l ) ))
(21)
Let us bound the summation in Eq. 21 using the following inequality:
ln(a) ≤ a− 1 for a > 0 (22)
The proof of Eq. 22 is as follows. Let a > 0, we define h(a) = ln(a) − a + 1. We have: h′(a) = 1a − 1 = 0 ⇔ a = 1, and since h
′′(a) = − 1a2 < 0,∀a > 0, we get the maximal point at a = 1. We also have: lima→0+ h(a) = −∞ = lima→∞ h(a). Therefore, a = 1 is the global maximal point and than ∀a > 0, h(a) ≤ h(a = 1) = 0, so ln(a) − a + 1 ≤ 0. Therefore, Eq. 22 does hold.
Note that, to simultaneously satisfy the randomization probabilities pX = 11+α exp( i%ll X) ≥ 0 and qX = α exp( i%ll X)
1+α exp( i%ll X) ≥ 0 in Eq. 2, we need to have: (i) 1 + α exp( i%ll X) ≥ 0 and (ii)
α exp( i%ll X) ≥ 0. Since exp( i%l l X) ≥ 0 is always true, from (i), α ≥ − exp(− i%l l X), and from (ii), α ≥ 0. Therefore, α ≥ 0 is necessary to satisfy the condition pX ≥ 0 and qX ≥ 0. To apply Eq. 22 into Eq. 21, we need to have a = α2 exp(2 X il ) > 0⇒ α 6= 0. As a result, we have that
α > 0 (23)
Applying Eq. 22 into Eq. 21 where a = α2 exp(2 X il ):
ln P (f -RR(vx) = vz) P (f -RR(ṽx) = vz) ≤ l−1∑ i=0 ( r p2Xi + (1− pXi)2 ln ( α2 exp(2 X i l ) ))
≤ l−1∑ i=0 rα2 exp(2 X i l ) p2Xi + (1− pXi)2 − l−1∑ i=0
r
p2Xi + (1− pXi)2 (24)
To bound the logarithm in Eq. 24, we use: p2Xi + q2Xi = p2Xi + (1 − pXi)2 = (
1
1+α exp( i%l l X )
)2 +
( α exp( i%l
l X )
1+α exp( i%l l X )
)2 = 1+
( α exp( i%l
l X ) )2( 1+α exp( i%l
l X )
)2 ≤ 1, and p2Xi + (1 − pXi)2 ≥ (pXi+1−pXi)22 = 12 (In fact,
∀a, b : a2 + b2 ≥ (a+b) 2
2 ⇔ (a − b) 2 ≥ 0, which is true). Note that, from Eq. 19, we have that
∆i E|E(f -RR(va,i))−E(f -RR(va|i,i))| = 1 p2Xi+q 2 Xi ≥ 1.
Applying these inequalities in Eq. 24, we obtain:
ln P (f -RR(vx) = vz) P (f -RR(ṽx) = vz) ≤ l−1∑ i=0 rα2 exp(2 X i l ) p2Xi + (1− pXi)2 − l−1∑ i=0
r
p2Xi + (1− pXi)2
< l−1∑ i=0 2rα2 exp(2 X i l )− l−1∑ i=0 r = l−1∑ i=0 2rα2 exp(2 X i l )− rl ≤ X (25)
By solving Eq. 25, we have that
α2 ≤ X + rl 2r ∑l−1 i=0 exp(2 X i l ) ⇔ |α| ≤
√ X + rl
2r ∑l−1 i=0 exp(2 X i l )
(26)
Therefore, from Eqs. 23 and 26, we have that ∀α : 0 < α ≤ √
X+rl 2r ∑l−1 i=0 exp(2 X i l ) , the f -RR
mechanism satisfies X -LDP. Consequently, Theorem 2 holds.

heading: F PROOF OF THEOREM 3
text: Proof. We have: P (label-RR(yx)=z|yx)P (label-RR(ỹx)=z|ỹx) ≤ maxP (label-RR(yx)=z|yx) minP (label-RR(ỹx)=z|ỹx) =
exp(β) 1+exp(β)
1 (1+exp(β))(C−1)
= exp(β +
ln(C − 1)) ≤ exp( Y )⇔ β ≤ Y − ln(C − 1). Consequently, Theorem 3 does hold.
G label-RR AND LABELDP COMPARISON
Although our label-RR is inspired by the randomizing probability (Eq. 1, (Ghazi et al., 2021)) in the LabelDP showcased by (Ghazi et al., 2021), there are two major differences between our label-RR and LabelDP discussed next.
(1) We combine f -RR and label-RR to completely protect a data sample. As pointed out in (BusaFekete et al., 2021), only protecting the label as in the LabelDP offers a weaker privacy protection than it appears, as the features are sufficiently predictive of the label, obscuring the label is not enough, as a classifier can still be trained on such noisy data; hence, a user experiences privacy loss due to both the public release of the features and the private release of the label.
(2) The RRWithPrior algorithm that is used to guarantee LabelDP requiring publicly available priors and the multi-stage training (LP-MST) illustrating RRWithPrior algorithm cannot be straightforwardly applied to federated learning. In LP-MST algorithm, the dataset is partitioned into subsets, then based on the prior probability to randomize the label and add the data with that randomized label to the training data. These steps are presently applied on centralized training and it has not been show how to be effectively applied in federated learning.
Using the upper bound of β (Theorem 3) results in the same randomizing probabilities between labelRR and LabelDP. For instance, in Eq. 3, pY = exp(β) 1+exp(β) = exp( Y −ln(C−1)) 1+exp( Y −ln(C−1)) = exp( Y ) C−1+exp( Y ) and qY = 1 (1+exp(β))(C−1) = 1
C−1+exp( Y ) , which is equivalent to Eq. 1 (Ghazi et al., 2021). Therefore, we did not include LabelDP (Ghazi et al., 2021) in comparison.

heading: H PROOF OF THEOREM 4
text: Proof. We have ξa = E|E(f -RR(va)) − E(va)| = ∑ i∈[0,l−1](pXi × 0 + qXi × ∆i) =∑
i∈[0,l−1] qXi ×∆i. Therefore, Theorem 4 hold.

heading: I CORRECTED PRIVACY BUDGET BOUNDS IN LATENT (ARACHCHIGE ET AL., 2019)
text: In this section, we aim at providing corrected privacy budget bounds for LATENT (Arachchige et al., 2019). LATENT first encodes embedded features ex into an rl-bit binary vector vx. Then, each bit i ∈ [0, rl − 1] is randomized by a RR mechanism (i.e., the MOUE algorithm for high sensitivities in Theorem 3.3 (Arachchige et al., 2019)), denoted f -LT, as follows:
∀i ∈ [0, rl − 1] : P (v′x(i) = 1) =  pX = 1 1 + α , if vx(i) = 1 qX = 1
1 + α exp( Xrl ) , if vx(i) = 0
(27)
From Eq. 27, we also have that P (v′x(i) = 0) = 1− pX = α1+α if vx(i) = 1, and P (v ′ x(i) = 0) = 1− qX = α exp( X rl )
1+α exp( X rl )
if vx(i) = 0.
Theorem 5. LATENT with the randomization probabilities as in Eq. 27 preserves corrected-LDP, where corrected = (1+α)(1+α exp( X rl ))
α(1+exp( X rl ))
X .
Proof. Similar to the analysis in Appendix E, we obtain the following inequality:
P (f -LT(vx) = vz) P (f -LT(ṽx) = vz) ≤ rl−1∏ i=0 ( P (f -LT(vx(i)) = vz(i)) P (f -LT(vx|i(i)) = vz(i)) ) ∆i E|E(f -LT(vx,i))−E(f -LT(vx|i,i))| ≤ exp( X)
(28)
and the expectation E|E(f -LT(vx, i))− E(f -LT(vx|i, i))| is computed as follows:
E|E(f -LT(vx, i))− E(f -LT(vx|i, i))| = ( P (f -LT(vx, i) = 1|vx(i) = 1)
× P (f -LT(vx|i, i) = 0|vx|i(i) = 0)× P (vx|i(i) = 0) + P (f -LT(vx, i) = 1|vx(i) = 0)
× P (f -LT(vx|i, i) = 0|vx|i(i) = 1)× P (vx|i(i) = 1) ) ∆i
+ ( P (f -LT(vx, i) = 0|vx(i) = 1)
× P (f -LT(vx|i, i) = 1|vx|i(i) = 0)× P (vx|i(i) = 0) + P (f -LT(vx, i) = 0|vx(i) = 0)
× P (f -LT(vx|i, i) = 1|vx|i(i) = 1)× P (vx|i(i) = 1) ) ∆i
= ( pXi(1− qXi)P (vx|i(i) = 0) + qXi(1− pXi)P (vx|i(i) = 1)
+ (1− pXi)qXiP (vx|i(i) = 0) + (1− qXi)pXiP (vx|i(i) = 1) ) ∆i
= ( pXi(1− qXi) + qXi(1− pXi) ) ∆i (29)
Furthermore, we have:
pXi(1− qXi) + qXi(1− pXi) = α(1 + exp( Xrl ))
(1 + α)(1 + α exp( Xrl )) (30)
From Eqs. 28-30, we have that
P (f -LT(vx) = vz) P (f -LT(ṽx) = vz)
≤ rl−1∏ i=0 ( P (f -LT(vx(i)) = vz(i)) P (f -LT(vx|i(i)) = vz(i)) ) ∆i E|E(f -LT(vx,i))−E(f -LT(vx|i,i))|
= rl−1∏ i=0 (P (f -LT(vx(i)) = 1|vx(i) = 1) P (f -LT(vx(i)) = 0|vx(i) = 1) ) ∆i (pXi(1−qXi)+qXi(1−pXi))∆i
× rl−1∏ i=0 (P (f -LT(vx(i)) = 0|vx(i) = 0) P (f -LT(vx(i)) = 1|vx(i) = 0) ) ∆i (pXi(1−qXi)+qXi(1−pXi))∆i
= rl−1∏ i=0 ( exp( X rl ) ) 1 pXi(1−qXi)+qXi(1−pXi) (31)
Then, from Eq. 31, we have:
corrected = ln ( Πrl−1i=0 (
exp( X rl
) ) 1 pXi(1−qXi)+qXi(1−pXi) ) = (1 + α)(1 + α exp( Xrl ))
α(1 + exp( Xrl )) X (32)
Consequently, Theorem 5 holds.
From Theorem 5, we show the proportion corrected/ X as a function of r in Figure 9a and as a function of l in Figure 9b. Following the experiment settings in LATENT (Arachchige et al., 2019), with the commonly used α = 7, when changing r ∈ {10, 100, 1, 000, 10, 000} with a fixed l = 10 (Figure 9a), or when changing l ∈ {5, 10, 20, 100, 1, 000} with a fixed r = 1, 000 (Figure 9b) and under a tight privacy budget X = 0.1, the proportion corrected/ X moderately changes among [4.57, 4.75]. In other words, the corrected is remarkably larger than X , for most r and l values in practice. Unlike LATENT, our mechanism does not suffer from this problem, i.e., in BitRand, corrected/ X = 1, thanks to our bit-aware randomization probabilities for LDP in binary encoding (Theorem 2).

heading: J CORRECTED PRIVACY BUDGET BOUNDS IN OME (LYU ET AL., 2020A)
text: In this section, we aim at providing corrected privacy budget bounds for OME. OME first encodes embedded features ex into an rl-bit binary vector vx. Then, each bit i ∈ [0, rl − 1] is randomized by the following f -OME mechanism:
∀i ∈ [0, rl − 1] : P (v′x(i) = 1) =  p1X = α 1 + α , if i ∈ 2j, vx(i) = 1 p2X = 1 1 + α3 , if i ∈ 2j + 1, vx(i) = 1 qX = 1
1 + α exp( X rl
) , if vx(i) = 0
(33)
From Eq. 33, we also have that P (v′x(i) = 0) = 1−p1X = 11+α if vx(i) = 1 and i ∈ 2j, P (v ′ x(i) = 0) = 1− p2X = α 3 1+α3 if vx(i) = 1 and i ∈ 2j + 1, and P (v ′ x(i) = 0) = 1− qX = α exp( X rl )
1+α exp( X rl )
if
vx(i) = 0. Theorem 6. OME with the randomization probabilities as in Eq. 33 preserves corrected-LDP, where corrected = (
rl Q1 − rlQ2 ) ln(α) + X 2Q1 + X2Q2 in which Q1 = α 1+α
α exp( X rl )
1+α exp( X rl )
+ 1 1+α exp(
X rl )
1 1+α
and Q2 = 11+α3 α exp( X rl )
1+α exp( X rl )
+ 1 1+α exp(
X rl )
α3
1+α3 .
Proof. Similar to the analysis in Appendix E and Appendix I, we obtain:
P (f -OME(vx) = vz) P (f -OME(ṽx) = vz) ≤ rl−1∏ i=0 ( P (f -OME(vx(i)) = vz(i)) P (f -OME(vx|i(i)) = vz(i)) ) ∆i E|E(f -OME(vx,i))−E(f -OME(vx|i,i))| ≤ exp( X)
(34)
and the expectation E|E(f -OME(vx, i))− E(f -OME(vx|i, i))| is computed as follows:
E|E(f -OME(vx, i))− E(f -OME(vx|i, i))|
=
{( p1Xi(1− qXi) + qXi(1− p1Xi) ) ∆i = Q1∆i, if i ∈ 2j(
p2Xi(1− qXi) + qXi(1− p2Xi) ) ∆i = Q2∆i, if i ∈ 2j + 1
(35)
where Q1 = p1Xi(1− qXi) + qXi(1− p1Xi) = α1+α α exp( X rl )
1+α exp( X rl )
+ 1 1+α exp(
X rl )
1 1+α ,
and Q2 = p2Xi(1− qXi) + qXi(1− p2Xi) = 11+α3 α exp( X rl )
1+α exp( X rl )
+ 1 1+α exp(
X rl )
α3
1+α3 .
From Eqs. 34 and 35, we have:
P (f -OME(vx) = vz) P (f -OME(ṽx) = vz)
≤ rl−1∏ i=0 ( P (f -OME(vx(i)) = vz(i)) P (f -OME(vx|i(i)) = vz(i)) ) ∆i E|E(f -OME(vx,i))−E(f -OME(vx|i,i))|
= ∏ i∈2j (P (f -OME(vx(i)) = 1|vx(i) = 1)P (f -OME(vx(i)) = 0|vx(i) = 0) P (f -OME(vx(i)) = 1|vx(i) = 0)P (f -OME(vx(i)) = 0|vx(i) = 1) ) ∆i Q1∆i
× ∏
i∈2j+1
(P (f -OME(vx(i)) = 1|vx(i) = 1)P (f -OME(vx(i)) = 0|vx(i) = 0) P (f -OME(vx(i)) = 1|vx(i) = 0)P (f -OME(vx(i)) = 0|vx(i) = 1) ) ∆i Q2∆i
= α rl Q1 − rlQ2 exp( X 2Q1 + X 2Q2 ) (36)
Then, from Eq. 36, we have:
corrected = ln ( α rl Q1 − rlQ2 exp(
X 2Q1 + X 2Q2 ) ) = ( rl Q1 − rl Q2 ) ln(α) + X 2Q1 + X 2Q2
(37)
Consequently, Theorem 6 does hold.
From Theorem 6, we show the proportion corrected/ X as a function of r in Figure 9a and as a function of l in Figure 9b. Following the experiment settings in OME (Lyu et al., 2020a), with the commonly used α = 100, when changing r ∈ {10, 100, 1, 000, 10, 000} with a fixed l = 10 (Figure 9a), or when changing l ∈ {5, 10, 20, 100, 1, 000} with a fixed r = 1, 000 (Figure 9b) and under a tight privacy budget X = 0.1, the proportion corrected/ X significantly changes among [4.6e + 6, 4.6e + 9]. In other words, the corrected is extremely larger than X , for most r and l values in practice. Since α = 100 causes the extreme privacy exaggeration, in our experiment, to compare with OME, we use α = 1. This value is used in OME (Lyu et al., 2020a) and generates corrected/ X ≈ 2, which offers a reasonable range to apply OME in practice. Unlike OME, our mechanism does not suffer from this problem, i.e., in BitRand, corrected/ X = 1, thanks to our bit-aware randomization probabilities for LDP in binary encoding (Theorem 2).

heading: K SUPPLEMENTARY THEORETICAL RESULTS
text: Setting for Gaussian and Laplace mechanisms. The Gaussian and Laplace mechanisms naturally apply an addition operation, which add noise into the data or embedded features. Therefore, in our analysis of expected error bound comparison for an embedded feature (Figure 3), we add noise into the embedded feature following the Gaussian and Laplace mechanisms. The sensitivity captures the magnitude by which an embedded feature can change in the
worst case. In our experiment and analysis, we use l = 10 bits in which 1 sign bit, 5 bits for the integer, and 4 bits for the fraction part. Therefore, the maximum the embedded feature can be change, i.e., the sensitivity, is 2 ∑4 i=−4 2 i. Note that, we multiply ∑4 i=−4 2
i by 2 since when we flip the sign bit, it significantly changes the value of the embedded feature from −a to a in which a = ∑4 i=−4 2 i.
RMSE error comparison in mean estimation. To investigate how our proposed approach f -RR works with statistical query, we study our f -RR and other baselines with a mean estimation. We created a synthetic data that consists of N = 1, 000 data samples {xi}Ni=1, each of them has d = 768 dimensions. The mean estimation is calculated over each dimension as fj(D) = 1N ∑N i=1 xij for j ∈ [1, d]. Root mean square error (RMSE) is used to evaluate the error between the original vector and the randomized/estimated vector. The binary-encoding-based approaches (i.e., f -RR, corrected LATENT, and corrected OME) achieve a significantly small error compared with others. As can be seen in Figure 10, f -RR obtains the smallest error, which further shows the effectiveness of our proposed mechanism.

heading: L SUPPLEMENTARY EXPERIMENTAL RESULTS
text: Datasets and Data Processing. We carried out our experiments on two textual datasets and two image datasets, including the AG dataset (Gulli et al., 2012), our collected Security and Exchange Commission (SEC) financial contract dataset, the large-scale celebFaces attributes (CelebA) dataset (Liu et al., 2015), and the Federated Extended MNIST (FEMNIST) dataset (Caldas et al., 2018). The AG dataset is a collection of news articles gathered from more than 2, 000 news sources by (Com). It is categorized into four classes: world, sport, business, and science/technology classes. Our SEC dataset consists of over 1, 000 contract clauses collected from contracts submitted in SEC filings1. The CelebA dataset consists of more than 200, 000 celebrity images, each with 40 attributes, e.g., attractive face, big lips, big noses, black hair, etc., which are used as binary classes. The FEMNIST dataset is built by partitioning the images in Extended MNIST (Cohen et al., 2017) based on the writer of the handwritten digits and characters. For data preprocessing, we changed all words in the AG and SEC datasets to lower-case and removed punctuation marks. The breakdown of the datasets is in Table 1.
Model Configuration. We use the test accuracy and the test area under the curve (AUC) as evaluation metrics. Models with higher values of test accuracy and AUC are better. We use the BERT-Base (Uncased) pre-trained model (ber; Devlin et al., 2018) to extract embedded features in the AG and SEC datasets. In the CelebA and FEMNIST datasets, we use the ResNet-18 pre-trained model (img; He et al., 2016). Dimension of the extracted embedded features in the AG and SEC datasets is r = 768, and in the CelebA and FEMNIST datasets is r = 512. For text and image classification tasks, we use two fully connected layers on top of embedded features, each of which consists of 1, 500 hidden neurons and uses a ReLU activation function. The output dimension is corresponding to the number of classes, i.e., 4, 2, 40, and 62 in the AG, SEC, CelebA, and FEMNIST datasets. SGD optimizer with the learning rate is 0.01 in the AG and SEC datasets, 0.1 in the FEMNIST and CelebA datasets.
Experimental setting for anonymization (Sun et al., 2021).
In LDP-FL (Sun et al., 2021), they design a LDP mechanism to perturb the weights at the local client, then 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. The purpose of the shuffling mechanism is 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. Therefore, the key idea of the shuffle mechanism in LDP-FL is to mitigate the privacy degradation by high data dimension and many training/query iterations. In other words, the client anonymity is preserved, and the privacy budget will not accumulate.
When comparing with LDP-FL, we maintain their mechanism’ spirits of no privacy accumulation. In the submission, we consider there is no privacy accumulation over the training iterations. It is equivalent to the shuffling step that breaks the linkage among the model weight updates with associated clients. We also used the same randomized response mechanism in the paper, which is Eq. 2 (Sun et al., 2021), to perturb the weight.
In the revision, we added an experiment that do not consider the privacy accumulation over data dimension and training/query iterations. This completely follows the gist of LDP-FL. In addition,
1https://www.sec.gov/edgar.shtml
the weights we used for LDP-FL. without actual shuffling or splitting can be considered a lossless process, therefore the results we reported here can be counted as an upper-bound result for LDP-FL.
As shown in Table 2, we obtained the slightly higher accuracy of LDP-FL compared with f -RR on the AG dataset. The key component of LDP-FL that helps to reduce the privacy accumulation issue is the shuffling mechanism. However, as pointed out in (Erlingsson et al., 2019), in the real world, it is possible that the anonymizers (i.e., shuffler) can either be compromised or collude with the coordinating server to extract sensitive information. Even though there is a marginally lower trade-off between privacy loss and model utility compared with LDP-FL, the advantage of f -RR is that it perturbs the data only once, then used the perturbed data for training process without facing an extra privacy risk potentially caused by the compromised or colluded anonymizer.
Figure 19: AUC values of LDP algorithms applied on the embedded features ex in the AG, SEC, and FEMNIST dataset.
Figure 20: AUC values of LDP algorithms applied on the gradients 5uθt in the AG, SEC, and FEMNIST datasets.

Review summaries:
The importance of rigorously taking care of privacy leakage in a DP algorithm on the bit level is well-know, see e.g.  Mironov, Ilya. On significance of the least significant bits for differential privacy. In: Proceedings of the 2012 ACM conference on Computer and communications security. 2012. p. 650-661.  This paper considers locally differentially private (LDP) mechanisms for binary representations of floating point numbers. The technique seems like a natural thing to do: the individual bits are flipped with a probability that scales with their importance. 

The paper proposes a randomized-response algorithm that takes into the bit indices and prioritises higher order bits. As a result, the utility is higher than other competitive algorithms. Additionally, the analysis allows the bit randomization probabilities not to be affected too much by the dimension of the data.

The paper proposes an $\epsilon$-LDP mechanism, termed $f$-RR, to privatize a real number. The mechanism first maps $v$ into its binary representation (with a sign bit) and then flips each bit with probability $p_i$. The authors then extend their mechanism to privatize a $r$-dimensional vector by sequentially performing the (scalar version) algorithm for each of the $r$ coordinates. By picking proper parameters, the proposed mechanism preserves $\epsilon$-LDP. Finally, several experimental results compared with other previous methods are provided.