# Group fairness under obfuscated sensitive information

Héber Hwang Arcolezi, Karima Makhlouf, Catuscia Palamidessi

► To cite this version:

Héber Hwang Arcolezi, Karima Makhlouf, Catuscia Palamidessi. Group fairness under obfuscated sensitive information. Journal of Computer Security, 2025, pp.1-26. 10.1177/0926227X251330212. hal-05070800

HAL Id: hal-05070800

https://inria.hal.science/hal-05070800v1

Submitted on 16 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Group Fairness Under Obfuscated Sensitive Information

Héber Hwang Arcolezi<sup>a,*</sup>, Karima Makhlouf<sup>b,c</sup> and Catuscia Palamidessi<sup>b</sup>

**Abstract.** In the era of Big Data, the development of AI systems presents both opportunities and challenges, particularly concerning privacy and fairness. While Differential Privacy (DP) has emerged as a robust methodology for preserving privacy in real-world applications, its local variant (LDP) specifically addresses trust issues by removing the reliance on a centralized server. Equally critical, conducting fairness audits of AI systems helps identify and mitigate discriminatory outcomes in machine learning. Although the relationship between DP and fairness is inherently multifaceted, this paper offers a detailed empirical examination of how collecting multidimensional sensitive attributes under LDP affects fairness in binary classification tasks. Our findings reveal that LDP can *slightly improve* fairness without substantially degrading model performance—challenging the notion that DP necessarily exacerbates unfairness. We demonstrate these results by evaluating seven state-of-the-art LDP protocols on three benchmark datasets, using established group fairness metrics. Moreover, we propose a novel privacy budget allocation scheme that incorporates varying domain sizes of sensitive attributes, achieving a superior privacy-utility-fairness trade-off compared to existing solutions.

**Keywords:** Machine Learning Fairness, Local Differential Privacy, Responsible AI, Fairness Audit

## 1. Introduction

The advent of the Big Data era has brought many benefits but has also raised significant concerns about privacy and algorithm bias in Machine Learning (ML). In a landscape where vast amounts of data are being generated and collected by various entities, safeguarding not only individuals’ personal information but also ensuring the reliability, fairness, and transparency of ML-based systems has become increasingly challenging. Recent events, such as Amazon’s deployment of an AI-powered hiring tool to streamline recruitment, have drawn attention due to the system’s revelation of gender bias against female candidates [1]. In the realm of privacy, incidents like the Cambridge Analytica scandal [2], where the company accessed personal data from over 50 million Facebook profiles without authorization, aiming to deliver personalized political ads based on users’ psychological profiles, underscore the critical need for robust data protection measures. Moreover, the persistent threat of data breaches [3] remains a concern despite the diligent efforts made by service providers to secure data.

© The Author(s) 2025. DOI: https://doi.org/10.1177/0926227X251330212

<footnote><sup>a</sup> Inria Centre at the University Grenoble Alpes, France</footnote>

<footnote>E-mail: heber.hwang-arcolezi@inria.fr</footnote>

<footnote><sup>b</sup> Inria Saclay and École Polytechnique (IPP), France</footnote>

<footnote>E-mails: karima.makhlouf@lix.polytechnique.fr, catuscia@lix.polytechnique.fr</footnote>

<footnote><sup>c</sup> University of Doha for Science and Technology (UDST), Qatar</footnote>

<footnote>* Corresponding author. E-mail: heber.hwang-arcolezi@inria.fr.</footnote>
In response to these challenges, the European Union is actively working to enhance the account-
ability of data processors by enforcing and guiding the development of responsible AI [4, 5], which
is characterized by qualities such as robustness, transparency, fairness, and privacy. As a requirement
under the General Data Protection Regulation (GDPR) [6], implementing data anonymization to pre-
vent re-identification or retrieval of personal information remains a challenge in practice. In this context,
research communities have proposed different methods to preserve privacy, with ε-differential privacy
(ε-DP) [7] standing out as a formal definition that allows quantifying the privacy-utility trade-off with
the parameter ε (the smaller, the more private). Simultaneously, there have been many efforts to develop
methods and metrics to evaluate and promote fairness in ML due to unequal treatments of individuals or
groups based on factors such as race, gender, or socio-economic status (e.g., see [8–13] and references
within).

While significant advancements have been made in developing methods and metrics to address privacy and fairness issues in ML, practical challenges persist. For instance, from the previous examples [2, 3], *critical privacy issues arise because original sensitive data is collected and processed*. Thus, the direct collection and storage of users’ raw data on a centralized server should be avoided to preserve users’ privacy better. In addition, it is not common anymore for entities to have access to *sensitive* (or *protected*<fnref n="1" />) attributes like race due to legal restrictions and regulations<fnref n="2" /> governing their collection. Therefore, it can be difficult for these entities to quantify/assess the fairness of the models they deploy since they cannot access the protected attributes used for the fairness assessment. One way to address these problems, ignoring legal feasibility, is to enable users to share their sensitive attributes using protocols satisfying Local Differential Privacy (LDP) [14] and learn a non-discriminatory predictor.

However, while collecting only the protected attribute in a privacy-preserving manner, as in [15–17],
may seem sufficient, it is worth noting that proxy variables can exist [18] and can still lead to inferences
about the protected attribute (e.g., by exploiting correlations). It is also important to acknowledge that
proxy variables may be considered personal information under the GDPR, requiring the same level
of privacy protection. Thus, as collecting multiple sensitive information (i.e., *multidimensional data*)
becomes increasingly prevalent in various industries, protecting this information is a legal obligation
and an ethical responsibility.

Expanding upon our preliminary findings outlined in [19], this paper provides a comprehensive fair-
ness audit of how collecting multidimensional data under ε-LDP guarantees affects group fairness and
utility in ML binary classification tasks. For fairness assessment, we employed various group fairness
metrics, including disparate impact [20], equal opportunity [21], and overall accuracy [22]. The experi-
mental evaluation encompasses seven state-of-the-art LDP protocols, namely, Generalized Randomized
Response (GRR) [23], Binary Local Hashing (BLH) [24], Optimal Local Hashing (OLH) [25], RAP-
POR [26], Optimal Unary Encoding (OUE) [25], Subset Selection (SS) [27, 28], and Thresholding with
Histogram Encoding (THE) [25]. To broaden the scope of our study, we conducted our experiments on
three benchmark datasets: Adult [29], ACSCoverage [29], and LSAC [30].

Moreover, since proxy variables can still introduce unintended biases and thus lead to unfair deci-
sions [18], we consider the setting in which each sensitive attribute (protected and proxy attribute) is
collected independently under ε-LDP guarantees. In other words, applying this independent setting au-
tomatically removes the correlation between the sensitive attributes. To this end, the privacy budget ε

<footnote n="1">¹Throughout this paper, we use the term *sensitive* attribute from a privacy perspective and the term *protected* attribute from a fairness perspective. Note that we always consider *protected* attributes as *sensitive* attributes.</footnote>

<footnote n="2">²For example, the GDPR [6].</footnote>
should be divided among all sensitive attributes to ensure $\epsilon$-LDP under sequential composition [31]. Let $d_s$ be the total number of sensitive attributes, the LDP literature for multidimensional data [32–35] considers a **uniform** solution that collects each sensitive attribute under $\frac{\epsilon}{d_s}$-LDP. In [19], we propose a new **k-based** solution that considers the varying domain size $k$ of different sensitive attributes. More precisely, for the $j$-th sensitive attribute, for $j \in [d_s]$, we allocate $\epsilon_j = \frac{\epsilon \cdot k_j}{\sum_{i=1}^{d_s} k_i}$.

In addition to the experiments conducted in [19], where a fixed number of sensitive attributes $d_s = 4$ was employed, this paper explores a more dynamic scenario with a variable $d_s$. These attributes are selected randomly to underscore the generalization of our findings. Overall, this study challenges the common belief that using DP necessarily leads to worsened fairness in ML [36, 37]. More specifically, we show that training a classifier on LDP-based multidimensional data slightly improved fairness results without significantly affecting classifier performance. We hope this work can aid practitioners in collecting multidimensional user data in a privacy-preserving manner by providing insights into which LDP protocol and privacy budget-splitting solutions are best suited to their needs. In summary, the main contributions of this paper are as follows:

* We conducted a comprehensive empirical analysis on the impact of collecting (or pre-processing<fnref n="3" />) multidimensional data under $\epsilon$-LDP guarantees on fairness and utility in ML binary classification.

* We compared the impact on fairness and utility of seven state-of-the-art LDP protocols under a homogeneous encoding (see Figure 1) when training ML binary classifiers.

* We proposed a novel **k-based** solution for privacy budget allocation [19], which generally led to a better privacy-utility-fairness trade-off in our experiments.

* We open-sourced our codes in the following **GitHub repository** [38].

**Outline.** The rest of this paper is organized as follows. Section 2 discusses related work. In Section 3, we present the notation, fairness, and LDP protocols used. Next, Section 4 states the problem addressed in this paper and the proposed **k-based** solution. Section 5 details the experimental setting and main results. Finally, we conclude this work indicating future perspectives in Section 6.

## 2. Related Work

The recent survey work by Fioretto et al. [39] discusses two views (**friends or foes?**) about the relationship between DP and fairness in learning and decision tasks. This section briefly reviews related work on how fairness interacts with both central and LDP methods in ML.

**Central DP & Fairness.** Early foundational results by Dwork et al. [40] show that DP can promote individual fairness–placing it in an "aligned" or "friendly" relationship with fairness goals. In contrast, Bagdasaryan, Poursaeed, & Shmatikov [36] analyzed the fairness implications of training deep learning models with central DP, specifically using *gradient perturbation* methods such as DP-SGD [41]. They reported significantly reduced accuracy for underrepresented groups when hyperparameters optimized on non-private baselines were kept unchanged for private training. Similarly, Ganev et al. [37] observed disparities for the underrepresented group when generating $\epsilon$-DP synthetic data for training ML models while keeping the default hyperparameters of differentially private generative models. These findings suggest that fairness degradation can partly result from suboptimal hyperparameter settings. Indeed, de

<footnote n="3">³While the privacy-preserving mechanisms experimented with within this paper are specifically designed for an LDP setting, a trusted server can also employ them in a centralized DP setting.</footnote>
Oliveira et al. [42] empirically demonstrated that when searching for the best hyperparameters for both non-private and $\epsilon$-DP models, the impact of DP on fairness is negligible. The importance of hyperparameter optimization arises because privately searching optimal hyperparameters is costly in terms of privacy budget, often making non-private hyperparameter tuning practically necessary yet potentially fairness-affecting. Recent works by Cummings et al. [43], Tran, Dinh, & Fioretto [44], and by Mangold et al. [45] formally investigated the reasons and contexts for this impact of central DP on fairness. Beyond explaining the phenomenon, Ficiu et al. [46] propose an integrated optimization framework targeting the fairness-privacy-utility trade-off in DP-based ML.

**LDP & Fairness.** Mozannar, Ohannessian, & Srebro [15] were the first to propose a fair classifier when obfuscating only the protected attribute under $\epsilon$-LDP in both the training and testing sets. Subsequently, Chen et al. [16] considers a "semi-private" setting in which a small portion of users share their protected attribute with no obfuscation, while all other users apply an $\epsilon$-LDP protocol. Carey, Bhaila, and Wu [47] further showed empirically that obfuscating the sensitive attribute, the label, or both under $\epsilon$-LDP does not introduce disparate impact on fairness. More recently, Makhlouf et al. [10] formally analyzed the impact of obfuscating the protected attribute with $\epsilon$-LDP on fairness in ML. In particular, they provided bounds in terms of the joint distributions and the privacy level, delimiting the extent to which LDP can impact the fairness of the model. They characterized the cases where privacy reduces discrimination and those with the opposite effect. While these works [10, 15, 16, 47] focus on collecting a single sensitive attribute–often using only the GRR [23] protocol–real-world scenarios typically involve multiple sensitive attributes. A recent study by Makhlouf et al. [48] does consider multidimensional data but still relies exclusively on GRR. In contrast, our work addresses multidimensional data by leveraging seven state-of-the-art $\epsilon$-LDP protocols and evaluating a range of fairness and utility metrics. Finally, we propose a novel privacy budget allocation strategy, called **k-based**, which achieves superior privacy-fairness-utility trade-offs in binary classification tasks compared to the widely used **uniform** solution from the LDP literature [32–35].

# 3. Preliminaries and Background

This section briefly reviews the group fairness metrics, differentially private ML, LDP, and LDP protocols. The notation used throughout this paper is summarized in Table 1. Note that in this work, we always consider a single protected attribute $A_p$ and assess fairness w.r.t. that attribute. For LDP, we consider a set of sensitive attributes $A_s$ instead. Moreover, the protected attribute is always considered sensitive, i.e., $A_p \in A_s$, but the opposite is untrue.

## 3.1. Group Fairness Metrics

In this paper, we focus on group fairness metrics, which assess the fairness of ML models for different demographic groups that differ by the protected attribute (e.g., race, gender, age, ...). Let $A_p$ be the protected attribute, $\hat{Y} \in \{0, 1\}$ be a predictor of a binary target $Y \in \{0, 1\}$. The metrics we use to evaluate fairness are:

* **Disparate Impact (DI)** [20]. DI is defined as the ratio of the proportion of positive predictions ($\hat{Y} = 1$) for the *unprivileged* group ($A_p = 0$) over the ratio of the proportion of positive predictions for the *privileged* group ($A_p = 1$). The formula for DI is:
<table><caption>Table 1
Notations.</caption><thead><tr><th>Symbol</th><th>Description</th></tr></thead><tbody><tr><td><i>n</i></td><td>Number of users</td></tr><tr><td>[<i>n</i>]</td><td>Set of integers, {1, 2, ..., <i>n</i>}</td></tr><tr><td><b>x</b><sub><i>i</i></sub></td><td><i>i</i>-th coordinate of vector <b>x</b></td></tr><tr><td><i>z</i> = <i>M</i>(<i>v</i>)</td><td>Protocol <i>M</i> perturbs <i>v</i> into <i>z</i> under <i>&epsilon;</i>-LDP</td></tr><tr><td><i>X</i></td><td>Set of "non-sensitive" attributes</td></tr><tr><td><i>A</i><sub>s</sub></td><td>Set of sensitive attributes (<b>privacy viewpoint</b>)</td></tr><tr><td><i>A</i><sub>p</sub></td><td>Protected attribute (<b>fairness viewpoint</b>), <i>A</i><sub>p</sub> &isin; <i>A</i><sub>s</sub></td></tr><tr><td><i>Z</i><sub>s</sub></td><td>Set of locally differentially private sensitive attributes, <i>Z</i><sub>s</sub> = <i>M</i>(<i>A</i><sub>s</sub>)</td></tr><tr><td><i>k</i><sub>j</sub></td><td>Domain size of the <i>j</i>-th attribute</td></tr><tr><td><i>d</i><sub>s</sub></td><td>Number of sensitive attributes, <i>d</i><sub>s</sub> = |<i>A</i><sub>s</sub>|</td></tr><tr><td><i>Y</i></td><td>Set of target values, <i>Y</i> &isin; {0, 1}</td></tr><tr><td><i>D</i></td><td>Original dataset, <i>D</i> = (<i>X</i>, <i>A</i><sub>s</sub>, <i>Y</i>)</td></tr><tr><td><i>D</i><sub>z</sub></td><td>Dataset with obfuscated sensitive attributes, <i>D</i><sub>z</sub> = (<i>X</i>, <i>Z</i><sub>s</sub>, <i>Y</i>)</td></tr></tbody></table>

$$DI = \frac{\Pr[\hat{Y} = 1 | A_p = 0]}{\Pr[\hat{Y} = 1 | A_p = 1]}. \qquad (1)$$

Note that a perfect DI value is equal to 1.

* **Statistical Parity Difference (SPD) [49]**. Instead of the ratio, SPD computes the difference in the proportion of positive predictions for *unprivileged* and *privileged* groups and is defined as:

$$SPD = \Pr[\hat{Y} = 1 | A_p = 1] - \Pr[\hat{Y} = 1 | A_p = 0]. \qquad (2)$$

A perfect SPD value is equal to 0.

* **Equal Opportunity Difference (EOD) [21]**. EOD measures the difference between the true positive rates (i.e., recall) of the *unprivileged* and the *privileged* groups. Formally, EOD is defined as:

$$EOD = \Pr[\hat{Y} = 1 | Y = 1, A_p = 1] - \Pr[\hat{Y} = 1 | Y = 1, A_p = 0]. \qquad (3)$$

A perfect EOD value is equal to 0.

* **Overall Accuracy Difference (OAD) [22]**. OAD measures the difference between the overall accuracy rates between the *privileged* group and the *unprivileged* group. Formally, OAD is defined as:

$$OAD = \Pr[\hat{Y} = Y | A_p = 1] - \Pr[\hat{Y} = Y | A_p = 0]. \qquad (4)$$

A perfect OAD value is equal to 0.
## 3.2. Differentially Private Machine Learning

When satisfying DP in ML, there are two major considerations [50]: (1) **where the noise is added** (the data vs. the model) and (2) which **trust assumptions** are made (central vs. local). Table 2 summarizes the characteristics of these distinct DP paradigms.

Under **central DP**, the server is assumed to be trusted, allowing noise injection after data aggregation. The most common scenario involves perturbing the gradients or parameters of an ML model, exemplified by DP-SGD [41]. Alternatively, though less commonly applied, noise can directly perturb the collected data. Under **LDP**, no trusted server exists. Each user independently applies noise to their data locally, eliminating direct access to sensitive raw data by the server and hence providing stronger privacy at the expense of higher noise variance and potentially reduced utility. Federated learning scenarios can also implement **LDP** through local gradient perturbation [51], where users locally add noise to model updates. However, this requires each user to be able to perform gradient computations.

Our work primarily focuses on **LDP with data perturbation**, motivated by scenarios where users individually obfuscate their sensitive attributes before sending them to a server. Nevertheless, our methods can also readily be applied within a central DP framework, provided the server is considered trustworthy enough to privately preprocess multidimensional data centrally.

<table><caption>Table 2</caption><thead><tr><th></th><th>Model (Gradient) Perturbation</th><th>Data (Input) Perturbation</th></tr></thead><tbody><tr><th>Central DP</th><td>Noise added to gradients/parameters, e.g., DP-SGD [41]</td><td>Noise added to data (less common but possible)</td></tr><tr><th>LDP</th><td>User adds noise to model updates locally, i.e., federated learning [51]</td><td>Each user perturbs their own data before sharing with the server</td></tr></tbody></table>

Overview of Differential Privacy Approaches in ML

## 3.3. Local Differential Privacy

In this article, we use LDP [14] as the privacy model, which is formalized as:

**Definition 1** ($\epsilon$-LDP). A randomized algorithm $\mathcal{M}$ satisfies $\epsilon$-local-differential-privacy ($\epsilon$-LDP), where $\epsilon > 0$, if for any pair of input values $v_1, v_2 \in \text{Domain}(\mathcal{M})$ and any possible output $z$ of $\mathcal{M}$:

$$ \Pr[\mathcal{M}(v_1) = z] \le e^{\epsilon} \cdot \Pr[\mathcal{M}(v_2) = z]. $$

In essence, LDP ensures that the data aggregator cannot reliably reconstruct the true data source regardless of the prior knowledge. The privacy budget $\epsilon$ controls the privacy-utility trade-off for which lower values of $\epsilon$ result in tighter privacy protection.

Similar to central DP, LDP also has several important properties, such as immunity to post-processing and composability [31], defined as follows.

**Proposition 1** (Post-Processing [31]). If $\mathcal{M}$ is $\epsilon$-LDP, then for any function $f$, the composition of $\mathcal{M}$ and $f$, i.e., $f(\mathcal{M})$ satisfies $\epsilon$-LDP.
**Proposition 2 (Sequential Composition [31]).** Let $x = (x_1, \dots, x_d)$ denote a user's vector of d attributes. For each $j \in \{1, \dots, d\}$, let $M_j$ be an $\epsilon_j$-LDP mechanism that takes only the j-th attribute $x_j$ as input. Define the composed mechanism $M_{1, \dots, d}(x) = (M_1(x_1), M_2(x_2), \dots, M_d(x_d))$. Then $M_{1, \dots, d}$ is $(\sum_{j=1}^d \epsilon_j)$-LDP.

### 3.4. LDP Protocols

Let $A_s = \{v_1, \dots, v_k\}$ be a sensitive attribute with a discrete domain of size $k = |A_s|$. In this subsection, we briefly review seven state-of-the-art LDP protocols.

#### 3.4.1. Generalized Randomized Response (GRR)

GRR [23] uses no particular encoding. Given a value $v \in A_s$, GRR($v$) outputs the true value $v$ with probability $p$, and any other value $v' \in A_s \setminus \{v\}$, otherwise. More formally:

$$ \forall z \in A_s: \quad \Pr[z=a] = \begin{cases} p = \frac{e^{\epsilon}}{e^{\epsilon}+k-1} & \text{if } z=a \\ q = \frac{1}{e^{\epsilon}+k-1} & \text{otherwise,} \end{cases} $$

where $z$ is the perturbed value sent to the server.

#### 3.4.2. Binary Local Hashing (BLH)

Local Hashing (LH) protocols [24, 25] can handle a large domain size $k$ by first using hash functions to map an input value to a smaller domain size $g$ (typically $2 \le g \ll k$), and then applying GRR to the hashed value. Let $\mathcal{H}$ be a universal hash function family such that each hash function $H \in \mathcal{H}$ hashes a value in $A_s$ into $[g]$, i.e., $H: A_s \to [g]$. With BLH, $[g] = \{0, 1\}$, each user selects at random one hash function $H$, calculates $b = H(v)$, and perturbs $b$ to $z$ as:

$$ \Pr[z=1] = \begin{cases} p = \frac{e^{\epsilon}}{e^{\epsilon}+1} & \text{if } b=1 \\ q = \frac{1}{e^{\epsilon}+1} & \text{if } b=0. \end{cases} $$

The user sends the tuple $\langle H, z \rangle$, i.e., the hash function and the perturbed value. Thus, for each user, the server can calculate the subset of all values $v \in A_s$ that hash to $z$, i.e., $S(\langle H, z \rangle) = \{v | H(v) = z\}$.

#### 3.4.3. Optimal LH (OLH)

To improve the utility of LH protocols, Wang et al. [25] proposed OLH in which the output space of the hash functions in family $\mathcal{H}$ is no longer binary as in BLH. Thus, with OLH, $g = \lfloor e^{\epsilon} + 1 \rfloor$, each user selects at random one hash function $H$, calculates $b = H(v)$, and perturbs $b$ to $z$ as:

$$ \forall i \in [g]: \quad \Pr[z=i] = \begin{cases} p = \frac{e^{\epsilon}}{e^{\epsilon}+g-1} & \text{if } b=i \\ q = \frac{1}{e^{\epsilon}+g-1} & \text{if } b \neq i. \end{cases} $$

Similar to BLH, the user sends the tuple $\langle H, z \rangle$ and, for each user, the server can calculate the subset of all values $v \in A_s$ that hash to $z$, i.e., $S(\langle H, z \rangle) = \{v | H(v) = z\}$.
### 3.4.4. RAPPOR

The RAPPOR [26] protocol uses One-Hot Encoding (OHE) to interpret the user's input $v \in A_s$ as a one-hot $k$-dimensional vector. More precisely, $v = \text{OHE}(v)$ is a binary vector with only the bit at position $v$ set to 1 and the other bits set to 0. Then, RAPPOR randomizes the bits from $v$ independently to generate $z$ as follows:

$$ \forall i \in [k]: \quad \text{Pr}[\mathbf{z}_i = 1] = \begin{cases} p = \frac{e^{\epsilon/2}}{e^{\epsilon/2} + 1} & \text{if } \mathbf{v}_i = 1, \\ q = \frac{1}{e^{\epsilon/2} + 1} & \text{if } \mathbf{v}_i = 0, \end{cases} $$

where $p + q = 1$ (i.e., symmetric). Afterward, the user sends $z$ to the server.

### 3.4.5. Optimal Unary Encoding (OUE)

To minimize the variance of RAPPOR, Wang et al. [25] proposed OUE, which perturbs the 0 and 1 bits asymmetrically, i.e., $p + q \neq 1$. Thus, OUE generates $z$ by perturbing $v$ as follows:

$$ \forall i \in [k]: \quad \text{Pr}[\mathbf{z}_i = 1] = \begin{cases} p = \frac{1}{2} & \text{if } \mathbf{v}_i = 1, \\ q = \frac{1}{e^{\epsilon} + 1} & \text{if } \mathbf{v}_i = 0. \end{cases} $$

Afterward, the user sends $z$ to the server.

### 3.4.6. Subset Selection (SS)

The SS [27, 28] protocol randomly selects $1 \le \omega < k$ items within the input domain to report a subset of values $\Omega \subseteq A_s$. The user's true value $v$ has a higher probability of being included in the subset $\Omega$, compared to the other values in $A_s \setminus \{v\}$. The optimal subset size that minimizes the variance is $\omega = \max(1, \lfloor \frac{k}{e^{\epsilon}+1} \rfloor)$. Given a value $v \in A_s$, SS($v$) starts by initializing an empty subset $\Omega$. Afterwards, the true value $v$ is added to $\Omega$ with probability $p = \frac{\omega e^{\epsilon}}{\omega e^{\epsilon} + k - \omega}$. Finally, it adds values to $\Omega$ as follows:

* If $v \in \Omega$, then $\omega - 1$ values are sampled from $A_s \setminus \{v\}$ uniformly at random (without replacement) and are added to $\Omega$;

* If $v \notin \Omega$, then $\omega$ values are sampled from $A_s \setminus \{v\}$ uniformly at random (without replacement) and are added to $\Omega$.

Afterward, the user sends the subset $\Omega$ to the server.

### 3.4.7. Thresholding with Histogram Encoding (THE)

Histogram Encoding (HE) [25] encodes the user value as a one-hot $k$-dimensional histogram, i.e., $v = [0.0, 0.0, \dots, 1.0, 0.0, \dots, 0.0]$ in which only the $v$-th component is 1.0. HE($v$) perturbs each bit of $v$ independently using the Laplace mechanism [7]. Two different input values $v_1, v_2 \in A_s$ will result in two vectors with L1 distance of $\Delta = 2$. Thus, HE will output $z$ such that $z_i = v_i + \text{Lap}(\frac{2}{\epsilon})$. To improve the utility of HE, Wang et al. [25] proposed THE such that the user reports (or the server computes): $S(z) = \{v | z_v > \theta\}$, in which $\theta$ is the threshold with optimal value in $(0.5, 1)$.

## 4. Problem Setting and Methodology
We consider the scenario in which the server collects a set of multiple sensitive attributes $A_s$ under $\epsilon$-LDP guarantees from $n$ distributed users $U = \{u_1, \dots, u_n\}$. Furthermore, in conjunction with the LDP-based multidimensional data, we assume that the users will also provide non-obfuscated data $X$, which we consider as "non-sensitive" attributes. Together with a binary target variable $Y \in \{0, 1\}$, these data form the basis for training an ML classifier.

**Overview of Training and Testing.** Our primary objective is to examine how training a classifier on obfuscated data $D_z = (X, Z_s, Y)$, where $Z_s = \mathcal{M}(A_s)$ is the LDP-obfuscated version of sensitive attributes, compares to training on original data $D = (X, A_s, Y)$ in terms of fairness and utility. Concretely:

* **Training:** The classifier is trained on dataset $D_z = (X, Z_s, Y)$, where $Z_s = \mathcal{M}(A_s)$ is the obfuscated version of the sensitive attributes.

* **Testing:** The classifier is evaluated on the original, non-obfuscated dataset $D = (X, A_s, Y)$.

Practically, we obfuscate only the training set to prevent privacy threats like membership inference [52], attribute inference [53], and reconstruction attacks [54, 55]. Unlike approaches employing on-the-fly obfuscation at test time (e.g., [15]), we perturb only training data. By the post-processing property (Proposition 1), the learned ML model itself satisfies $\epsilon$-LDP with respect to the sensitive attributes.

**Independent Per-Attribute Obfuscation and Sequential Composition.** Let $d_s = |A_s|$ be the total number of sensitive attributes. For each attribute $A_j \in A_s$, we apply a separate LDP mechanism $\mathcal{M}_j$, ensuring $\epsilon_j$-LDP. By sequential composition (Proposition 2), the combined mechanism $(\mathcal{M}_1(A_1), \mathcal{M}_2(A_2), \dots, \mathcal{M}_{d_s}(A_{d_s}))$ incurs a total privacy loss of $\sum_{j=1}^{d_s} \epsilon_j$.

*Example.* If a user has three sensitive attributes (*age*, *gender*, *marital status*) and we want an overall budget of $\epsilon = 1$, assigning $\epsilon = 1$ per attribute would sum to 3, violating the desired budget. Instead, each attribute can be allocated $\frac{1}{3}$-LDP, keeping the combined privacy cost $\le 1$.

**Privacy Budget Splitting.** To ensure $\sum_{j=1}^{d_s} \epsilon_j \le \epsilon$, we consider two approaches:

* **Uniform Splitting** [32–35]: Each attribute receives $\epsilon_j = \frac{\epsilon}{d_s}$. This approach is straightforward but may not account for large domain discrepancies across attributes.

* **$k$-based Splitting** [19]: If the $j$-th attribute $a_j$ has domain size $k_j$, then $\epsilon_j = \frac{\epsilon \cdot k_j}{\sum_{i=1}^{d_s} k_i}$. Attributes with larger domains get proportionally more budget, counteracting the stronger noise they might otherwise incur.

**LDP Protocols and Encoding.** Different LDP protocols (see Section 3.4) encode and perturb categorical data in various ways. To ensure a fair comparison, we convert *all* protocol outputs into a consistent representation before training. Specifically:

(1) We use *One-Hot Encoding (OHE)* or *Indicator Vector Encoding (IVE)* [56] to produce a unified binary feature vector.

(2) For example, let $\Omega$ be the reported subset of a user after using SS as LDP protocol. Following IVE, we create a binary vector $z = [b_1, \dots, b_k] \in \{0, 1\}^k$ of length $k$, where the $v$-th entry is set to 1 if $v \in \Omega$, and 0, otherwise. In other words, $z$ represents the subset $\Omega$ in a binary format.

(3) Non-sensitive attributes $X$ are encoded with standard OHE (without privacy perturbation).

This unified encoding framework isolates performance and fairness variations attributable solely to differences among the LDP protocols themselves, rather than encoding discrepancies. Figure 1 illustrates this standardized client-server encoding pipeline clearly.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Overview of client-side encoding and perturbation steps for the seven different LDP protocols applied. On the server side, there is also a post-processing step with one-hot encoding (OHE) or indicator vector encoding (IVE), if needed.</figcaption></figure>

## 5. Experimental Evaluation

In this section, we present our experiments' setting and results. Our Research Questions (RQ) are:

* **RQ1.** Overall, how does pre-processing multidimensional data with $\epsilon$-LDP affect the fairness and utility of ML binary classifiers with the same hyperparameters used before and after obfuscation?

* **RQ2.** Which privacy budget-splitting solution has a better privacy-utility-fairness trade-off?
* **RQ3.** How do different LDP protocols affect the fairness and utility of an ML binary classifier, and which one is more suitable for the different real-world scenarios applied?

## 5.1. Setup of Experiments

**General setting.** For all experiments, we consider the following setting:

* **Environment.** All algorithms are implemented in Python 3 with Numpy [57], Numba [58], and Multi-Freq-LDPy [59] libraries, and run on a local machine with 2.50GHz Intel Core i9 and 64GB RAM. The codes we develop for all experiments are available in a GitHub repository [38].

* **ML classifier.** We used the state-of-the-art<fnref n="4" /> LGBM [60] as predictor $\hat{Y}$.

* **Encoding.** We only use discrete and categorical attributes, which are encoded using OHE or IVE (see Figure 1) and the target is binary, i.e., $Y \in \{0, 1\}$.

* **Training and testing sets.** We randomly select 80% as training set and the remaining 20% as testing set. We apply LDP on the training set only. That is, the samples in the testing set are the original samples (i.e., no LDP).

* **Stability.** Since LDP protocols, train/test splitting, and ML algorithms are randomized, we report average results over 50 runs.

**Datasets.** Table 3 summarizes all datasets used in our experiments. For ease of reproducibility, we use real-world and open datasets.

* **Adult.** We use 26000$ as a threshold to binarize the target variable "income" of the reconstructed Adult dataset [29]. After cleaning, $n = 45849$ samples are kept. We excluded "capital-gain" and "capital-loss" and used the remaining 10 discrete and categorical attributes. We considered $A_s = \{\text{gender, race, native country, age, hours per week, education}\}$ as the set of possible sensitive attributes for LDP obfuscation. We consider two scenarios for the Adult dataset depending on the protected attribute to assess fairness. *Gender* is the protected attribute for the first scenario, while *race* is considered as the protected attribute for the second scenario. We call the Adult dataset differently depending on the protected attribute at hand:

* **Adult$_G$:** With $A_p = \text{gender}$.

* **Adult$_R$:** With $A_p = \text{race}^5$.

* **ACS Coverage<fnref n="6" />.** This dataset is retrieved with the `folktables` [29] Python package and the binary target "PUBCOV" designates whether an individual is covered by public health insurance or not. We select 2018 and the "Texas" state, with $n = 98739$ samples. We removed "DEAR", "DEYE", "DREM", and "PINCP" and used the remaining 15 discrete and categorical attributes. We considered $A_s = \{\text{DIS, AGEП, SEX, SCHL, RAC1P, NATIVITY}\}$ as the set of sensitive attributes for LDP obfuscation and $A_p = \text{DIS}$ (i.e., disability) as the protected attribute to assess fairness.

* **LSAC.** This dataset is from the Law School Admissions Council (LSAC) National Bar Passage Study [30] and the binary target "pass_bar" indicates whether or not a candidate has passed the bar exam. After cleaning, $n = 20427$ samples are kept. We only consider as attributes: 'gender', 'race', 'family income', 'full time', 'undergrad GPA score' (discretized to $\{1.5, 2.0, ..., 4.5\}$), and

<footnote n="4">⁴https://www.kaggle.com/kaggle-survey-2022.</footnote>

<footnote n="5">⁵We consider race as a binary attribute with the two categories: non-white and white.</footnote>

<footnote n="6">⁶The full documentation for the description of all attributes is in https://www.census.gov/programs-surveys/acs/microdata/documentation.html.</footnote>
<table><caption>Table 3
Description of the datasets used in the experiments.</caption><thead><tr><th>Dataset</th><th>n</th><th>A<sub>p</sub></th><th>A<sub>s</sub>, domain size k</th><th>Y</th></tr></thead><tbody><tr><td>Adult<sub>G</sub></td><td>45849</td><td>gender</td><td>- gender, k = 2<br>- race, k = 5<br>- native country, k = 41<br>- age, k = 74<br>- hours per week, k = 96<br>- education, k = 16</td><td>income</td></tr><tr><td>Adult<sub>R</sub></td><td>45849</td><td>race</td><td>- race, k = 2<br>- gender, k = 2<br>- native country, k = 41<br>- age, k = 74<br>- hours per week, k = 96<br>- education, k = 16</td><td>income</td></tr><tr><td>ACSCoverage</td><td>98739</td><td>DIS</td><td>- DIS, k = 2<br>- AGEП, k = 50<br>- SEX, k = 2<br>- SCHL, k = 24<br>- RACIP, k = 2<br>- NATIVITY, k = 2</td><td>PUBCOV</td></tr><tr><td>LSAC</td><td>20427</td><td>race</td><td>- race, k = 2<br>- gender, k = 2<br>- family income, k = 5<br>- full time, k = 2</td><td>pass bar</td></tr></tbody></table>

‘LSAT score’ (rounded to the closest integer). The ‘race’ attribute was binarized to {black, other}. We considered $A_s$ = {gender, race, family income, full time} as the set of sensitive attributes for LDP obfuscation and $A_p$ = race as the protected attribute for fairness assessment.

**Evaluated methods.** The methods we use and compare are:

* **(Baseline) NonDP.** This is our baseline with LGBM trained over original data (i.e., $D = (X, A_s, Y)$). The attributes of non-sensitive X and sensitive $A_s$ are encoded with OHE. To ensure a meaningful and robust baseline, we first optimize the hyperparameters of the LGBM classifier solely for utility maximization, using Bayesian optimization [61] through 100 iterations varying: $max_depth \in [3, 50]$, $n_estimators \in [50, 2000]$, and $learning_rate \in (0.01, 0.25)$. While using default hyperparameters would also be valid, we chose to optimize hyperparameters explicitly to establish the strongest possible baseline model in terms of predictive performance. This approach ensures that any subsequent variations observed in fairness or utility metrics result directly from the privacy-preserving mechanisms applied, rather than from suboptimal or arbitrary hyperparameter choices.

* **LDP protocols.** For all the four datasets of Table 3, we selected the number of sensitive attributes uniformly at random with $2 \le d_s \le |A_s|^7$, in each of the 50 runs. We then pre-processed the sensi-

<footnote n="7">⁷The protected attribute $A_p$ is always considered as a sensitive attribute requiring LDP obfuscation. Once the total number of sensitive attributes $d_s$ is established, the remaining $d_s - 1$ sensitive attributes are selected uniformly at random.</footnote>
tive attributes of the training sets (i.e., $Z_s = M(A_s)$) using each of the seven LDP protocols from Section 3.4 (i.e., GRR, RAPPOR, OUE, SS, BLH, OLH, and THE). Next, we fixed the optimized hyperparameters found for the NonDP model and trained LGBM over $D_z = (X, Z_s, Y)$ using these hyperparameters. To satisfy $\epsilon$-LDP (cf. Proposition 2), we split the privacy budget following the two solutions described in Section 4, namely, the state-of-the-art **uniform** and our **k-based** solutions.

**Metrics.** We evaluate the performance of LGBM trained over the original data (i.e., NonDP baseline) and LDP-based data on privacy, utility, and fairness:

* **Privacy.** We vary the privacy parameter in the range of $\epsilon = \{0.25, 0.5, 1, 2, 4, 8, 10, 20, 50\}$. At $\epsilon = 0.25$, the ratio of probabilities is bounded by $e^{0.25} \approx 1.3$, giving nearly indistinguishable distributions, whereas at $\epsilon = 50$ almost no privacy is guaranteed.

* **Utility.** We use accuracy (acc), f1-score (f1), area under the receiver operating characteristic curve (auc), and recall as utility metrics;

* **Fairness.** We use the group fairness metrics of Section 3.1 (i.e., DI, SPD, EOD, and OAD).

## 5.2. Main Results

**LDP impact on fairness.** Figure 2 (Adult$_G$), Figure 3 (Adult$_R$), Figure 4 (ACSCoverage), and Figure 5 (LSAC) illustrate the privacy-fairness trade-off for the NonDP baseline and all the seven LDP protocols, considering both **uniform** and our **k-based** privacy budget splitting solutions. From these figures, one can observe a general trend of slight improvement in fairness for all the seven LDP protocols under both the **uniform** and the **k-based** solutions. For instance, for the DI metric in Figure 2, the NonDP data indicates a value of 0.44 showing discrimination against women. Upon applying LDP protocols, DI tends to increase to approximately 0.48 (with $\epsilon \le 2$), slightly improving fairness. Similarly, SPD decreased from 0.37 to ~0.34 after applying LDP protocols. Similar trends are observed for other fairness metrics such as EOD, indicating consistent improvements after applying LDP protocols.

The main exception occurred in Figure 4 for the OAD metric, where the gap between the privileged and the unprivileged groups was accentuated (favoring the unprivileged group). Specifically, the OAD is -0.17 with the NonDP baseline. After applying all the LDP protocols using either the **uniform** or the **k-based** solutions, the gap between the privileged and the unprivileged groups increased to -0.25. In other words, we initially observed favoritism towards the unprivileged group (indicated by a negative value), which increased after applying LDP. It is noteworthy that even this exception contrasts with the findings of [36, 37] in central DP, where the underrepresented group is consistently negatively affected.

Additionally, it is noteworthy that when applying the **uniform** privacy budget splitting solution (refer to the left-side in the plots), all fairness metrics demonstrated less robustness to LDP than our **k-based** solution. Consequently, they reverted to the NonDP baseline value in low privacy regimes. On the other hand, when applying our **k-based** solution (refer to the right-side in the plots), all fairness metrics consistently performed better across all privacy regimes, especially for the Adult dataset, as depicted in Figures 2 and 3. For the ACSCoverage dataset, not all fairness metrics returned to the NonDP baseline value with our **k-based** solution. However, with the **uniform** solution, for $\epsilon \ge 8$, all fairness metrics reverted to the NonDP baseline value. A similar behavior was noticed for the LSAC dataset, where our **k-based** solution exhibited more robustness to LDP than the **uniform** solution, reverting to the NonDP baseline values only when $\epsilon \ge 20$ in contrast with $\epsilon \ge 8$ for the **uniform** solution.

**LDP impact on utility.** Figure 6 (Adult$_G$), Figure 7 (Adult$_R$), Figure 8 (ACSCoverage), and Figure 9 (LSAC) illustrate the privacy-utility trade-off for the NonDP baseline and all the seven LDP protocols,
<figure><img src="image_3.png" /><figcaption>Fig. 2. Fairness metrics (y-axis) by varying the privacy guarantees (x-axis), the $\epsilon$-LDP protocol, and the privacy budget splitting solution (i.e., uniform on the left-side and our *k*-based on the right-side), on the Adult$_G$ [29] dataset.</figcaption></figure>

considering both the *uniform* and our *k-based* privacy budget splitting solutions. From these figures, one can note that, in general, the impact of $\epsilon$-LDP on utility metrics is minor. For instance, for the Adult (see Figures 6 and 7) and LSAC (see Figure 9) datasets, only ~2% of utility loss for all metrics is observed. Regarding privacy budget splitting, for the Adult$_G$ and Adult$_R$ datasets, our *k-based* solution was more robust to LDP as it only lost performance in high privacy regimes (i.e., smaller $\epsilon$ values). However, the *uniform* solution drops performance faster, i.e., even with $\epsilon \le 10$. One main explanation for this
<figure><img src="image_4.png" /><figcaption>Fig. 3. Fairness metrics (y-axis) by varying the privacy guarantees (x-axis), the ε-LDP protocol, and the privacy budget splitting solution (i.e., *uniform* on the left-side and our *k-based* on the right-side), on the Adult_R [29] dataset.</figcaption></figure>

behavior is the high discrepancy in the domain size *k* of the sensitive attributes *A*<sub>s</sub> and, consequently, more privacy budget *ε* is allocated to those attributes with high *k*. For this reason, the *uniform* solution preserved more utility for the ACSCoverage dataset in Figure 8, and both solutions had similar results for the LSAC dataset in Figure 9 due to sensitive attributes with a small domain size *k*.

**Impact of the number of sensitive attributes d<sub>s</sub>.** Figure 10 (fairness metrics) and Figure 11 (utility
<figure><img src="image_5.png" /><figcaption>Fig. 4. Fairness metrics (y-axis) by varying the privacy guarantees (x-axis), the ε-LDP protocol, and the privacy budget splitting solution (i.e., *uniform* on the left-side and our *k-based* on the right-side), on the ACSCoverage [29] dataset.</figcaption></figure>

metrics) illustrate the privacy-utility-fairness trade-off when varying the number of sensitive attributes $d_s$ when applying the GRR protocol on the Adult$_G$ dataset. Naturally, as more sensitive attributes undergo obfuscation via $\epsilon$-LDP, utility experiences a decline, albeit with a positive impact on fairness. Note that our experiments showed similar trend results for the other LDP protocols and datasets. Indeed, averaged results considering all the number of sensitive attributes $d_s$ at once can be observed from Figure 2 to Figure 9.
<figure><img src="image_6.png" /><figcaption>Fig. 5. Fairness metrics (y-axis) by varying the privacy guarantees (x-axis), the ε-LDP protocol, and the privacy budget splitting solution (i.e., *uniform* on the left-side and our *k-based* on the right-side), on the LSAC [30] dataset.</figcaption></figure>

**Summary.** We summarize our main findings for the three research questions formulated at the beginning of Section 5. (RQ1) Using the same hyperparameters configuration, ε-LDP positively affects fairness in ML (see Figures 2–5 and Figure 10) while having a negligible impact on model’s utility (see Figures 6–9 and Figure 11). This contrasts the findings of [36, 37] that state that ε-DP negatively impacts fairness under the same hyperparameters configuration. While the aforementioned research works concern gra-
<figure><img src="image_7.png" /><figcaption>Fig. 6. Utility metrics (y-axis) by varying the privacy guarantees (x-axis), the ε-LDP protocol, and the privacy budget splitting solution (i.e., *uniform* on the left-side and our *k-based* on the right-side), on the Adult_G [29] dataset.</figcaption></figure>

dient perturbation in central DP, we focused on *input perturbation*, i.e., randomizing multiple sensitive attributes before training any ML algorithm, and discovered a positive impact of ε-(L)DP on fairness. (RQ2) Our *k-based* solution consistently led to better fairness improvement than the state-of-the-art *uniform* solution for all the four datasets. Regarding utility, *k-based* was better than *uniform* when sensitive attributes had higher domain sizes k (e.g., with the Adult_G and Adult_R datasets), which coincides with
<figure><img src="image_8.png" /><figcaption>Fig. 7. Utility metrics (y-axis) by varying the privacy guarantees (x-axis), the ε-LDP protocol, and the privacy budget splitting solution (i.e., uniform on the left-side and our *k*-based on the right-side), on the Adult_R [29] dataset.</figcaption></figure>

real-world data collections. Naturally, when all sensitive attributes have a binary domain, our *k*-based solution is equivalent to the *uniform* solution. For this reason, both state-of-the-art *uniform* and our *k*-based solution led to similar (favoring our *k*-based solution) privacy-utility-fairness trade-off for the LSAC dataset (see Figs. 5 and 9). (RQ3) In general, GRR and SS presented the best privacy-utility-fairness trade-off for all the four datasets. This is because GRR has only one perturbed output value and
<figure><img src="image_9.png" /><figcaption>Fig. 8. Utility metrics (y-axis) by varying the privacy guarantees (x-axis), the $\epsilon$-LDP protocol, and the privacy budget splitting solution (i.e., uniform on the left-side and our k-based on the right-side), on the ACSCoverage [29] dataset.</figcaption></figure>

SS is equivalent to GRR when $\omega = 1$, thus, not introducing inconsistencies for a user's profile. The term inconsistency refers to a user being in multiple categories in a given attribute, i.e., being both woman and man simultaneously. This can happen with all the other LDP protocols that utilize some specific encoding. For example, UE protocols perturb each bit independently, and when using LH protocols, many values can hash to the same perturbed value. In particular, since BLH hashes the input set $V \to \{0, 1\}$,
<figure><img src="image_10.png" /><figcaption>Fig. 9. Utility metrics (y-axis) by varying the privacy guarantees (x-axis), the ε-LDP protocol, and the privacy budget splitting solution (i.e., *uniform* on the left-side and our *k-based* on the right-side), on the LSAC [30] dataset.</figcaption></figure>

it consistently presented the worst utility results for all the four datasets.
<figure><img src="image_11.png" /><figcaption>Fig. 10. Fairness metrics (y-axis) by varying the privacy guarantees (x-axis), the number of sensitive attributes *d*<sub>s</sub>, and the privacy budget splitting solution (i.e., *uniform* on the left-side and our *k-based* on the right-side), with the GRR protocol on the Adult<sub>G</sub> [29] dataset.</figcaption></figure>

**6. Conclusion and Perspectives**

This paper presented an in-depth AI audit study of how pre-processing multidimensional data us-
ing seven state-of-the-art ϵ-LDP protocols affects fairness and utility in binary classification tasks. Our
experimental evaluation revealed that GRR [23] and SS [27, 28] offered the most favorable privacy-
<figure><img src="image_12.png" /><figcaption>Fig. 11. Utility metrics (y-axis) by varying the privacy guarantees (x-axis), the number of sensitive attributes *d*<sub>s</sub>, and the privacy budget splitting solution (i.e., *uniform* on the left-side and our *k-based* on the right-side), with the GRR protocol on the Adult<sub>G</sub> [29] dataset.</figcaption></figure>

utility-fairness trade-offs compared to RAPPOR [26], OUE [25], THE [25], BLH [24], and OLH [25].
Additionally, we proposed a novel privacy-budget splitting solution, called *k-based*, which outperformed
the conventional *uniform* splitting approach widely adopted in previous LDP works [32–35].

Contrary to existing research [36, 37], which indicated that central DP generally deteriorates fairness
under fixed hyperparameter configurations, our study demonstrates that LDP can slightly improve fairness outcomes without significantly compromising model utility. These insights have practical implications for the growing area of private- and fairness- aware ML, suggesting that LDP could be used as part of data pre-processing pipelines to simultaneously safeguard privacy and enhance fairness. However, our study also highlights that much remains to be explored in privacy-fairness-aware ML. For future work, we aim to formally investigate how variations in the distribution of the protected attribute, the target, and their joint distribution affect the privacy-utility-fairness trade-off, and propose novel methods accordingly. Furthermore, we plan to extend our analysis by evaluating the impact of LDP pre-processing on different ML models, including deep neural networks, and by considering additional fairness metrics.

## Acknowledgement

This work has been partially supported by the French National Research Agency (ANR), under contracts "ANR-24-CE23-6239" JCJC project AI-PULSE, "ANR-19-P3IA-0003" MIAI @ Grenoble Alpes, and "ANR 22-PECY-0002" IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR, and by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement 835294).

## References

[1] J. Dastin, Amazon scraps secret AI recruiting tool that showed bias against women, 2018, Available online: https://www.reuters.com/article/us-amazon-com-jobs-automation-insight/amazon-scrops-secret-ai-recruiting-tool-that-showed-bias-against-women-idUSKCN1MK08G/ (accessed on 29 November 2023).

[2] J.C. Wong, Facebook to be fined $5bn for Cambridge Analytica privacy violations - reports, 2019, Available online: https://www.theguardian.com/technology/2019/jul/12/facebook-fine-ftc-privacy-violations (accessed on 11 March 2023).

[3] D. McCandless, T. Evans, M. Quick, E. Hollowood, C. Miles, D. Hampson and D. Geere, World's Biggest Data Breaches & Hacks, 2021, Available online: https://www.informationisbeautiful.net/visualizations/worlds-biggest-data-breaches-hacks/ (accessed on 11 March 2023).

[4] European Commission, Ethics guidelines for trustworthy AI, 2019, Available online: https://digital-strategy.ec.europa.eu/en/library/ethics-guidelines-trustworthy-ai (accessed on 29 November 2023).

[5] European Commission, Laying down harmonised rules on artificial intelligence (Artificial Intelligence Act) and amending certain union legislative acts, 2021, Available online: https://eur-lex.europa.eu/legal-content/EN/TXT/?uri=CELEX:52021PC0206 (accessed on 29 November 2023).

[6] General Data Protection Regulation (GDPR), 2018, Available online: https://gdpr-info.eu/ (accessed on 26 March 2023).

[7] C. Dwork, F. McSherry, K. Nissim and A. Smith, Calibrating Noise to Sensitivity in Private Data Analysis, in: Theory of Cryptography, Springer Berlin Heidelberg, 2006, pp. 265–284. doi:10.1007/11681878_14.

[8] G. Alves, F. Bernier, M. Couceiro, K. Makhlouf, C. Palamidessi and S. Zhioua, Survey on fairness notions and related tensions, EURO journal on decision processes 11 (2023), 100033. doi:10.1016/j.ejdp.2023.100033.

[9] K. Makhlouf, S. Zhioua and C. Palamidessi, Machine learning fairness notions: Bridging the gap with real-world applications, Information Processing & Management 58(5) (2021), 102642. doi:10.1016/j.ipm.2021.102642.

[10] K. Makhlouf, S. Zhioua and C. Palamidessi, On the Applicability of Machine Learning Fairness Notions, ACM SIGKDD Explorations Newsletter 23(1) (2021), 14–23. doi:10.1145/3468507.3468511.

[11] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman and A. Galstyan, A Survey on Bias and Fairness in Machine Learning, ACM Computing Surveys 54(6) (2021), 1–35. doi:10.1145/3457607.

[12] S. Barocas, M. Hardt and A. Narayanan, Fairness and Machine Learning: Limitations and Opportunities, MIT Press, 2023.

[13] G. Maheshwari and M. Perrot, Fairgrad: Fairness aware gradient descent, arXiv preprint arXiv:2206.10923 (2022).

[14] S.P. Kasiviswanathan, H.K. Lee, K. Nissim, S. Raskhodnikova and A. Smith, What Can We Learn Privately?, SIAM Journal on Computing 40(3) (2011), 793–826. doi:10.1137/090756090.

[15] H. Mozannar, M. Ohannessian and N. Srebro, Fair Learning with Private Demographic Data, in: Proceedings of the 37th International Conference on Machine Learning, H.D. III and A. Singh, eds, Proceedings of Machine Learning Research, Vol. 119, PMLR, 2020, pp. 7066–7075.
[16] C. Chen, Y. Liang, X. Xu, S. Xie, Y. Hong and K. Shu, On Fair Classification with Mostly Private Sensitive Attributes, *arXiv preprint arXiv:2207.08336* (2022).

[17] K. Makhlouf, T. Stefanović, H.H. Arcolezi and C. Palamidessi, A Systematic and Formal Study of the Impact of Local Differential Privacy on Fairness: Preliminary Results, in: *2024 IEEE 37th Computer Security Foundations Symposium (CSF)*, 2024, pp. 1–16. doi:10.1109/CSF61375.2024.00039.

[18] N. Kallus, X. Mao and A. Zhou, Assessing Algorithmic Fairness with Unobserved Protected Class Using Data Combination, *Management Science* **68**(3) (2022), 1959–1981. doi:10.1287/mnsc.2020.3850.

[19] H.H. Arcolezi, K. Makhlouf and C. Palamidessi, (Local) Differential Privacy has NO Disparate Impact on Fairness, in: *Data and Applications Security and Privacy XXXVII*, V. Atluri and A.L. Ferrara, eds, Springer Nature Switzerland, Cham, 2023, pp. 3–21. doi:10.1007/978-3-031-37586-6_1.

[20] S. Barocas and A.D. Selbst, Big data’s disparate impact, *Calif. L. Rev.* **104** (2016), 671.

[21] M. Hardt, E. Price and N. Srebro, Equality of opportunity in supervised learning, *Advances in neural information processing systems* **29** (2016).

[22] R. Berk, H. Heidari, S. Jabbari, M. Kearns and A. Roth, Fairness in criminal justice risk assessments: The state of the art, *Sociological Methods & Research* (2018).

[23] P. Kairouz, K. Bonawitz and D. Ramage, Discrete distribution estimation under local privacy, in: *International Conference on Machine Learning*, PMLR, 2016, pp. 2436–2444.

[24] R. Bassily and A. Smith, Local, Private, Efficient Protocols for Succinct Histograms, in: *Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing*, STOC ’15, Association for Computing Machinery, New York, NY, USA, 2015, pp. 127–135+. doi:10.1145/2746539.2746632.

[25] T. Wang, J. Blocki, N. Li and S. Jha, Locally Differentially Private Protocols for Frequency Estimation, in: *26th USENIX Security Symposium (USENIX Security 17)*, USENIX Association, Vancouver, BC, 2017, pp. 729–745.

[26] U. Erlingsson, V. Pihur and A. Korolova, RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response, in: *Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security*, ACM, New York, NY, USA, 2014, pp. 1054–1067. doi:10.1145/2660267.2660348.

[27] S. Wang, L. Huang, P. Wang, Y. Nie, H. Xu, W. Yang, X.-Y. Li and C. Qiao, Mutual information optimally local private discrete distribution estimation, *arXiv preprint arXiv:1607.08025* (2016).

[28] M. Ye and A. Barg, Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy, *IEEE Transactions on Information Theory* **64**(8) (2018), 5662–5676. doi:10.1109/TIT.2018.2809790.

[29] F. Ding, M. Hardt, J. Miller and L. Schmidt, Retiring adult: New datasets for fair machine learning, *Advances in Neural Information Processing Systems* **34** (2021).

[30] L.F. Wightman, LSAC National Longitudinal Bar Passage Study. LSAC Research Report Series. (1998).

[31] C. Dwork, A. Roth et al., The algorithmic foundations of differential privacy, *Foundations and Trends® in Theoretical Computer Science* **9**(3–4) (2014), 211–407.

[32] H.H. Arcolezi, J.-F. Couchot, B. Al Bouna and X. Xiao, Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy, in: *Proceedings of the 30th ACM International Conference on Information & Knowledge Management*, CIKM ’21, Association for Computing Machinery, New York, NY, USA, 2021, pp. 47–57+. doi:10.1145/3459637.3482467.

[33] X. Ren, C.-m. Yu, W. Yu, S. Yang, S. Member, X. Yang, J.A. Mccann, P.S. Yu and L. Fellow, LoPub: High-Dimensional Crowdsourced Data **13**(9) (2018), 2151–2166. doi:10.1109/TIFS.2018.2812146.

[34] H. Kikuchi, Castell: Scalable Joint Probability Estimation of Multi-dimensional Data Randomized with Local Differential Privacy, *arXiv preprint arXiv:2212.01627* (2022).

[35] G. Liu, P. Tang, C. Hu, C. Jin and S. Guo, Multi-Dimensional Data Publishing with Local Differential Privacy, in: *Proceedings of the 26th International Conference on Extending Database Technology, EDBT 2023*, 2023, pp. 183–194. doi:10.48786/edbt.2023.15.

[36] E. Bagdasaryan, O. Poursaeed and V. Shmatikov, Differential Privacy Has Disparate Impact on Model Accuracy, in: *Advances in Neural Information Processing Systems*, Vol. 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox and R. Garnett, eds, Curran Associates, Inc., 2019.

[37] G. Ganev, B. Oprisanu and E. De Cristofaro, Robin Hood and Matthew Effects: Differential Privacy Has Disparate Impact on Synthetic Data, in: *Proceedings of the 39th International Conference on Machine Learning*, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu and S. Sabato, eds, Proceedings of Machine Learning Research, Vol. 162, PMLR, 2022, pp. 6944–6959.

[38] LDP impact on fairness repository, https://github.com/hharcolezi/ldp-fairness-impact.

[39] F. Fioretto, C. Tran, P.V. Hentenryck and K. Zhu, Differential Privacy and Fairness in Decisions and Learning Tasks: A Survey, in: *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, 2022. doi:10.24963/ijcai.2022/766.

[40] C. Dwork, M. Hardt, T. Pitassi, O. Reingold and R. Zemel, Fairness through awareness, in: *Proceedings of the 3rd Innovations in Theoretical Computer Science Conference*, ACM, 2012. doi:10.1145/2090236.2090255.
[41] M. Abadi, A. Chu, I. Goodfellow, H.B. McMahan, I. Mironov, K. Talwar and L. Zhang, Deep Learning with Differential Privacy, in *CCS '16, Association for Computing Machinery, New York, NY, USA, 2016*, pp. 308–318. ISBN 9781450341394. doi:10.1145/2976749.2978318.

[42] A.S. de Oliveira, C. Kaplan, K. Mallat and T. Chakraborty, An Empirical Analysis of Fairness Notions under Differential Privacy, *arXiv preprint arXiv:2302.02910* (2023).

[43] R. Cummings, V. Gupta, D. Kimpara and J. Morgenstern, On the Compatibility of Privacy and Fairness, in: *Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization, UMAP'19 Adjunct, Association for Computing Machinery, New York, NY, USA, 2019*, pp. 309–315. doi:10.1145/3314183.3323847.

[44] C. Tran, M. Dinh and F. Fioretto, Differentially Private Empirical Risk Minimization under the Fairness Lens, in: *Advances in Neural Information Processing Systems*, Vol. 34, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang and J.W. Vaughan, eds, Curran Associates, Inc., 2021, pp. 27555–27565.

[45] P. Mangold, M. Perrot, A. Bellet and M. Tommasi, Differential Privacy has Bounded Impact on Fairness in Classification, in: *Proceedings of the 40th International Conference on Machine Learning*, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato and J. Scarlett, eds, *Proceedings of Machine Learning Research*, Vol. 202, PMLR, 2023, pp. 23681–23705.

[46] B. Ficiu, N.D. Lawrence and A. Paleyes, Automated discovery of trade-off between utility, privacy and fairness in machine learning models, in: *Joint European Conference on Machine Learning and Knowledge Discovery in Databases*, Springer, 2023, pp. 127–144. doi:10.1007/978-3-031-74630-7_9.

[47] A.N. Carey, K. Bhaila and X. Wu, Randomized Response Has No Disparate Impact on Model Accuracy, in: *2023 IEEE International Conference on Big Data (BigData)*, 2023, pp. 5460–5465. doi:10.1109/BigData59044.2023.10386574.

[48] K. Makhlouf, H.H. Arcolezi, S. Zhioua, G.B. Brahim and C. Palamidessi, On the impact of multi-dimensional local differential privacy on fairness, *Data Mining and Knowledge Discovery* **38**(4) (2024), 2252–2275. doi:10.1007/s10618-024-01031-0.

[49] A. Agarwal, H. Agarwal and N. Agarwal, Fairness Score and process standardization: framework for fairness certification in artificial intelligence systems, *AI and Ethics* (2022), 1–13.

[50] N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, C. Denison, H.B. McMahan, S. Vassilvitskii, S. Chien and A.G. Thakurta, How to dp-fy ml: A practical guide to machine learning with differential privacy, *Journal of Artificial Intelligence Research* **77** (2023), 1113–1201.

[51] S. Truex, L. Liu, K.-H. Chow, M.E. Gursoy and W. Wei, LDP-Fed: federated learning with local differential privacy, in: *Proceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking, EdgeSys '20*, Association for Computing Machinery, New York, NY, USA, 2020, pp. 61–66. ISBN 9781450371322. doi:10.1145/3378679.3394533.

[52] H. Hu, Z. Salcic, L. Sun, G. Dobbie, P.S. Yu and X. Zhang, Membership Inference Attacks on Machine Learning: A Survey, *ACM Computing Surveys* **54**(11s) (2022), 1–37. doi:10.1145/3523273.

[53] J. Aalmoes, V. Duddu and A. Boutet, On the Alignment of Group Fairness with Attribute Privacy, in: *International Conference on Web Information Systems Engineering*, Springer, 2025, pp. 333–348. doi:10.1007/978-981-96-0567-5_24.

[54] A.M.G. Salem, A. Bhattacharyya, M. Backes, M. Fritz and Y. Zhang, Updates-leak: Data set inference and reconstruction attacks in online learning, in: *29th USENIX Security Symposium*, USENIX, 2020, pp. 1291–1308.

[55] B. Liu, M. Ding, S. Shaham, W. Rahayu, F. Farokhi and Z. Lin, When Machine Learning Meets Privacy, *ACM Computing Surveys* **54**(2) (2021), 1–36. doi:10.1145/3436755.

[56] Indicator vector, Available online: https://en.wikipedia.org/wiki/Indicator_vector (accessed on 04 April 2023).

[57] S. van der Walt, S.C. Colbert and G. Varoquaux, The NumPy Array: A Structure for Efficient Numerical Computation, *Computing in Science & Engineering* **13**(2) (2011), 22–30. doi:10.1109/MCSE.2011.37.

[58] S.K. Lam, A. Pitrou and S. Seibert, Numba: A LLVM-Based Python JIT Compiler, in: *Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC*, LLVM '15, Association for Computing Machinery, New York, NY, USA, 2015. doi:10.1145/2833157.2833162.

[59] H.H. Arcolezi, J.-F. Couchot, S. Gambs, C. Palamidessi and M. Zolfaghari, Multi-Freq-LDPy: Multiple Frequency Estimation Under Local Differential Privacy in Python, in: *Computer Security – ESORICS 2022*, V. Atluri, R. Di Pietro, C.D. Jensen and W. Meng, eds, Springer Nature Switzerland, Cham, 2022, pp. 770–775. doi:10.1007/978-3-031-17143-7_40.

[60] G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye and T.-Y. Liu, LightGBM: A Highly Efficient Gradient Boosting Decision Tree, in: *Advances in Neural Information Processing Systems*, Vol. 30, I. Guyon, U.V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan and R. Garnett, eds, Curran Associates, Inc., 2017.

[61] J. Bergstra, D. Yamins and D.D. Cox, Making a Science of Model Search: Hyperparameter Optimization in Hundreds of Dimensions for Vision Architectures, in: *Proceedings of the 30th International Conference on International Conference on Machine Learning*, ICML'13, JMLR, 2013, pp. I–115–I–123–.