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

HAL
open science

# Comprendre et optimiser le compromis entre vie privée et utilité d'un point de vue fondamental

Sayan Biswas

► To cite this version:

Sayan Biswas. Comprendre et optimiser le compromis entre vie privée et utilité d'un point de vue fondamental. Artificial Intelligence [cs.AI]. Institut Polytechnique de Paris, 2023. English. NNT: 2023IPPAX092. tel-04407120

HAL Id: tel-04407120

https://hal.science/tel-04407120

Submitted on 9 Apr 2024

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.
# Understanding and optimizing the trade-off between privacy and utility from a foundational perspective

Thèse de doctorat de l'Institut Polytechnique de Paris préparée à INRIA et l'École polytechnique

École doctorale n°626 École doctorale de l'Institut Polytechnique de Paris (EDIPP)
Spécialité de doctorat : Informatique

Thèse présentée et soutenue à Palaiseau, le 18 octobre, 2023, par

SAYAN BISWAS

## Composition du Jury :

<table><tr><td>Benjamin Nguyen<br>Professeur, INSA Centre Val de Loire</td><td>Président</td></tr><tr><td>Aurélien Bellet<br>Directeur de recherche, INRIA Lille et Télécom Paris</td><td>Rapporteur</td></tr><tr><td>Marco Gaboardi<br>Professeur associé, Boston University</td><td>Rapporteur</td></tr><tr><td>Graham Cormode<br>Professeur, The University of Warwick et Meta</td><td>Examinateur</td></tr><tr><td>Ehab ElSalamouny<br>Professeur assistant, Suez Canal University</td><td>Examinateur</td></tr><tr><td>Anne-Marie Kermarrec<br>Professeure, EPFL</td><td>Examinatrice</td></tr><tr><td>Simon Oya<br>Professeur assistant, University of British Columbia</td><td>Examinateur</td></tr><tr><td>Catuscia Palamidessi<br>Directrice de recherche, INRIA Saclay et École Polytechnique</td><td>Directrice de thèse</td></tr></table>
Understanding and optimizing the trade-off
between privacy and utility from a foundational
perspective

By

SAYAN BISWAS

INRIA and Institute Polytechnique de Paris

Thése de Doctorat · Doctoral Thesis

Spécialité: Informatique · Specialization: Computer Science

Rapporteurs:
Aurélien BELLET
Marco GABOARDI

Directeur de thése: Catuscia PALAMIDESSI

Examinateurs:
Graham CORMODE
Ehab ELSALAMOUNY
Anne-Marie KERMARREC
Benjamin NGUYEN
Simon OYA

October 2023
"To the cherished memories of past adventures and the exciting prospects of those yet to come. To Kolkata, the place where my roots are firmly planted. To Bath, the city that nurtured my growth. To Paris, where I learned the art of truly living life. To the countless inspiring individuals and enriching experiences that have graced my journey so far, and to the countless more awaiting me in the future."
Abstract

With recent advancements in technology, the threats of privacy violations of individuals' per-
sonal data are surging like never before. While protecting the privacy of sensitive informa-
tion is becoming more important than ever before, it is also crucial to uphold the utility of
the data especially as data is becoming one of the most essential resources in the contempo-
rary information-based society. Differential privacy (DP) is considered to be the gold standard
of formal privacy guarantees. Its widespread applicability and uncomplicated implementation
technique have led to a rapid growth in its popularity and interest in studying and applying DP
to a variety of domains in academia and industry alike. Over time, the community has explored
various variants of DP addressing privacy concerns in different contexts and under a variety of
threat models.

Despite the prolific acceptance of DP, it is still nebulous to interpret how it interacts with and
affects the utility of data, escalating the need for answers to rudimentary questions like how
adding DP noise affects the utility of the shared data (e.g., the quality of service of the data
owners, the statistical utility of the service providers, the accuracy of the analysis and model
training performed, etc.) and does there exist some optimal DP mechanism with respect to the
usefulness of data in different realms and contexts. The objective of this thesis is to address
these questions and, in particular, establish a theoretical foundation to comprehensively analyze
the trade-off between privacy and the utility of sensitive data from a variety of perspectives and
in the context of different use cases. Aside from dissecting the age-old battle between privacy
and utility, this thesis also develops privacy-preserving mechanisms to proceed in the direction
of optimizing utility loss with formal privacy guarantees in diverse domains of applicability.

The first part focuses on location privacy and explores its trade-offs with utilities applica-
ble in the context of location-based services. In particular, Chapter 3 probes the triadic trade-
off between the utility for the users of location-based services and the corresponding service
providers. A standard method to mitigate the privacy risks for location data is by achieving
geo-indistinguishability (geo-ind). However, isolated locations are not sufficiently protected by
the state-of-the-art Laplace mechanism (LAP) for geo-ind. We, therefore, focus on a mechanism
based on the Blahut-Arimoto algorithm (BA) and show that it provides comprehensive location-
privacy guarantees and an optimal trade-off between information leakage and quality of ser-
vice. Moreover, by establishing an intriguing duality between BA and an iterative expectation-
maximization method, and by showing that BA's statistical utility is better than LAP's, we pro-
pose a method for a privacy-friendly incremental collection of location data from users by service
providers.
Following this, in Chapter 4, fabricates an efficient privacy-preserving querying mechanism for the navigation of electric vehicles (EVs) with a high utility. Since there are disproportionately fewer charging stations than EVs, range anxiety plays a major role in the rise in the number of queries made along the journeys to find available charging stations. In this work, we introduce the notion of approximate geo-indistinguishability (AGeoI) which allows the EVs to achieve geo-ind in a strictly bounded space (e.g., remaining within their preferred area on the map) and also ensure that the overall trajectories of the EVs also remain private. The proposed method illustrates that a very high percentage of EVs get “privacy for free”. Our method also proves effective for an accurate online prediction of charging station occupancies under privacy guarantees which is vital for efficient route planning.

The second part of this thesis studies privacy in the context of federated learning (FL). Chapter 5, in particular, aims to address this triadic interaction between the personalization, privacy guarantees, and fairness achieved by the trained models under the FL framework. Clients in FL often hold very diverse datasets representing heterogeneous communities, making it important to protect their sensitive and personal information while ensuring that the trained model is fair for all the users. To achieve this, we propose a method that provides group privacy guarantees using *d*-privacy (a generalization of geo-ind). Our method, besides enabling personalized model training in a federated approach and providing formal privacy guarantees, possesses significantly better group fairness measured under a variety of standard metrics than a global model trained within a classical FL template.

Continuing to study the privacy aspects of FL, Chapter 6 investigates information leakage via gradients FL from a foundational perspective. Despite being believed to be one of the first significant steps towards privacy-preserving machine learning, numerous attacks against the training data in typical FL frameworks have been discovered of late that make use of the shared gradients as well as the model. This part of the thesis provides a formal understanding to explain the working of such empirically driven gradient-inversion attacks in FL elucidating how shared gradients leak information that can be exploited to recover sensitive training data.

The last part of the thesis is dedicated to efficient and optimal techniques to price and trade private data through the emerging concept of data markets. In Chapter 7, we propose a truthful incentive mechanism that furnishes a differentially private data trading mechanism optimal with respect to the utility of the data owners and the data collectors involved in data markets. Then we extend this work in Chapter 8 to propose a model of federated data markets in which data providers form coalitions for trading their private data. We illustrate a technique to price private data and distribute the revenue fairly in such a federated environment while motivating the data providers to cooperate with their respective federations, facilitating a fair and swift private data trading process.
Résumé

Avec les récentes avancées technologiques, les menaces de violation de la vie privée concernant les données personnelles des individus se multiplient comme jamais auparavant. Si la protection de la confidentialité des informations sensibles devient plus importante que jamais, il est également crucial de préserver l'utilité des données, d'autant plus que les données deviennent l'une des ressources les plus essentielles dans la société contemporaine basée sur l'information. La protection différentielle de la vie privée est considérée comme l'étalon-or des garanties formelles de protection de la vie privée. Son applicabilité étendue et sa technique de mise en œuvre simple ont conduit à une croissance rapide de sa popularité et de l'intérêt pour l'étude et l'application de la confidentialité différentielle à une variété de domaines, tant dans les universités que dans l'industrie. Au fil du temps, la communauté a exploré diverses variantes de la protection de la vie privée pour répondre aux problèmes de confidentialité dans différents contextes et dans le cadre de divers modèles de menace.

Malgré l'acceptation prolifique du DP, il est encore difficile d'interpréter la manière dont il interagit avec les données et affecte leur utilité, ce qui accroît le besoin de réponses à des questions rudimentaires telles que la manière dont l'ajout de bruit DP affecte l'utilité des données partagées (par exemple, la qualité de service des propriétaires de données, l'utilité statistique des fournisseurs de services, la précision de l'analyse et de l'entraînement des modèles effectués, etc. L'objectif de cette thèse est de répondre à ces questions et, en particulier, d'établir une base théorique pour analyser de manière exhaustive le compromis entre la protection de la vie privée et l'utilité des données sensibles selon diverses perspectives et dans le contexte de différents cas d'utilisation. Outre la dissection de la bataille séculaire entre la vie privée et l'utilité, cette thèse développe également des mécanismes de préservation de la vie privée afin d'optimiser la perte d'utilité avec des garanties formelles de respect de la vie privée dans divers domaines d'applicabilité.

La première partie se concentre sur la confidentialité de la localisation et explore ses compromis avec les utilités applicables dans le contexte des services basés sur la localisation. En particulier, le chapitre 3 étudie le compromis triadique entre l'utilité pour les utilisateurs de services basés sur la localisation et les fournisseurs de services correspondants. Une méthode standard pour atténuer les risques d'atteinte à la vie privée liés aux données de localisation consiste à assurer l'indiscernabilité géographique (geo-ind). Toutefois, les emplacements isolés
ne sont pas suffisamment protégés par le mécanisme de Laplace (LAP) de pointe pour la géo-
indiscernabilité. Nous nous concentrons donc sur un mécanisme basé sur l'algorithme de Blahut-
Arimoto (BA) et montrons qu'il fournit des garanties complètes de confidentialité de la locali-
sation et un compromis optimal entre la fuite d'informations et la qualité de service. En outre,
en établissant une dualité intrigante entre l'algorithme BA et une méthode itérative de maximi-
sation des attentes, et en montrant que l'utilité statistique de l'algorithme BA est meilleure que
celle de l'algorithme LAP, nous proposons une méthode de collecte progressive, respectueuse de
la vie privée, des données de localisation des utilisateurs par les fournisseurs de services.

Ensuite, dans le chapitre 4, nous fabriquons un mécanisme d'interrogation efficace et re-
spectueux de la vie privée pour la navigation des véhicules électriques (EVs) avec une utilité
élevée. Étant donné que les stations de recharge sont disproportionnellement moins nombreuses
que les VE, l'anxiété liée à l'autonomie joue un rôle majeur dans l'augmentation du nombre de
requêtes effectuées tout au long des trajets pour trouver des stations de recharge disponibles.
Dans ce travail, nous introduisons la notion de géo-indiscernabilité approximative (AGeoI) qui
permet aux VE d'atteindre la géo-ind dans un espace strictement délimité (par exemple, en
restant dans leur zone préférée sur la carte) et de garantir que les trajectoires globales des VE
restent également privées. La méthode proposée montre qu'un pourcentage très élevé de VE
obtient la "confidentialité gratuitement". Notre méthode s'avère également efficace pour une
prédiction en ligne précise de l'occupation des stations de recharge avec des garanties de confi-
dentialité, ce qui est vital pour une planification efficace des itinéraires.

La deuxième partie de cette thèse étudie la protection de la vie privée dans le contexte
de l'apprentissage fédéré (AF). Le chapitre 5, en particulier, vise à aborder cette interaction
triadique entre la personnalisation, les garanties de confidentialité et l'équité obtenue par les
modèles formés dans le cadre de l'apprentissage fédéré. Les clients de FL détiennent souvent des
ensembles de données très divers représentant des communautés hétérogènes, d'où l'importance
de protéger leurs informations sensibles et personnelles tout en veillant à ce que le modèle
formé soit équitable pour tous les utilisateurs. Pour y parvenir, nous proposons une méthode qui
fournit des garanties de confidentialité de groupe en utilisant *d*-privacy (une généralisation de
geo-ind). Notre méthode, en plus de permettre la formation de modèles personnalisés dans une
approche fédérée et de fournir des garanties formelles de confidentialité, possède une équité
de groupe significativement meilleure, mesurée selon une variété de métriques standard, qu'un
modèle global formé à l'intérieur d'un modèle FL classique. Nous fournissons des justifications
théoriques pour l'applicabilité et la validation expérimentale sur des ensembles de données du
monde réel pour illustrer le fonctionnement de la méthode proposée.

Poursuivant l'étude des aspects de confidentialité du FL, le chapitre 6 étudie les fuites d'informations
via les gradients FL d'un point de vue fondamental. Bien qu'elle soit considérée comme l'une
des premières étapes significatives vers l'apprentissage automatique préservant la vie privée, de
nombreuses attaques contre les données d'apprentissage dans les cadres FL typiques ont été dé-
couvertes récemment, qui utilisent les gradients partagés ainsi que le modèle. Cette partie de la
thèse fournit une compréhension formelle pour expliquer le fonctionnement de telles attaques
empiriques par inversion de gradient dans l'apprentissage automatique, en élucidant la manière
dont les gradients partagés laissent échapper des informations qui peuvent être exploitées pour
récupérer des données d'apprentissage sensibles.

La dernière partie de la thèse est consacrée aux techniques efficaces et optimales permettant
de fixer le prix et d'échanger des données privées grâce au concept émergent des marchés de
données. Dans le chapitre 7, nous proposons un mécanisme d'incitation véridique qui fournit un
mécanisme d'échange de données différentiellement privées optimal en ce qui concerne l'utilité
des propriétaires de données et des collecteurs de données impliqués dans les marchés de don-
nées. Nous étendons ensuite ce travail au chapitre 8 pour proposer un modèle de marchés de
données fédérés dans lequel les fournisseurs de données forment des coalitions pour échanger
leurs données privées. Nous illustrons une technique de tarification des données privées et de
distribution équitable des revenus dans un tel environnement fédéré, tout en motivant les four-
nisseurs de données à coopérer avec leurs fédérations respectives, facilitant ainsi un processus
d'échange de données privées équitable et rapide.
Acknowledgements

I am massively thankful and would like to express my deepest gratitude and appreciation to
everyone who has made my PhD journey so incredibly enjoyable and rewarding.

To my supervisor Catuscia Palamidessi: you have been one of my biggest inspirations through my entire PhD journey. To date, I continue getting amazed by your diverse range of qualities including and not limited to your immaculate work ethic, fierce intelligence, an alluring sense of aesthetics, and extraordinary care of and encouragement for your students. Thank you for replying to my hundreds of emails over the last four years – at every possible time of the day (and night) – answering my countless questions and for the unending appreciation, encouragement, and motivation. You are one of the best teachers and guides I could ever get in my life making my PhD journey so thoroughly enjoyable with your perpetual support in every realm possible, professional and personal alike. Last but not least, thank you for financially supporting my PhD through the HYPATIA project of the European Research Council (ERC) under the Horizon 2020 research and innovation program of the European Union (Grant agreement N. 835294).

To my Mum (Ma) and late Dad (Baba): Ma, no amount of “thank you” will suffice to express my gratitude to you for raising me the way you have and for your endless selfless sacrifice and help in every stage of my life including and not limited to my PhD. Baba, you have always been there for me in every capacity whenever I needed you — thank you for all your support and encouragement. I wish you were there today to hug me and see your “Gogol” to finally complete his PhD. I am certain that you are proud of me and blessing me for my upcoming endeavours from wherever you are.

To all my extended family: Thank you for your ineffable support in every situation and for never letting me feel alone despite being thousands of miles away from you all. In particular, Bapis, without you teaching me to solve those algebraic equations and making me appreciate the essence of mathematics as a kid, I probably would have had a much harder time proving any of the theorems during my PhD. Dia, thank you for always wishing the best for me and for your continued encouragement. Mani, Tatali, Putai Didi, and Pavel Dada, thank you all for always being there for me since my childhood and making every celebration worth it.

To all my collaborators and mentors: Thank you for the plethora of email exchanges, video
calls, and brainstorming sessions resulting in our successful collaborations and publications.
You all have contributed immensely to my professional growth and enriched my overall PhD
experience. In particular, I extend my gratitude to Kangsoo Jung for mentoring me on a variety
of topics ranging from writing codes to Korean culture and to Graham Cormode, Carsten Maple,
Natasha Fernandes, and Annabelle McIver for all your valuable support, advice, and comments enabling our long-distance collaboration to go through without any hindrance.

To the entire COMÈTE team at Inria Saclay: I am truly grateful to have been a part of such a stimulating, encouraging, and fun academic environment during my PhD. I would cherish the friendships I have made within the team for a lifetime. Thank you all for being so supportive and fun. In particular, I am truly thankful to have Federica Granese as one of my best friends in my PhD life.

To my best friends: Aabesh, Anuraag, and Souvik, life (PhD and beyond) would be a quarter as enjoyable without having you three (horrible yet awesome) blokes around. On a serious note, you three occupy one of the most priceless parts of my life — thank you for always being there.

To Nikita: My PhD journey would have been incomplete without you. Thanks for your endless support, motivation, and encouragement over the last three years, being there by me through thick and thin. Moreover, thank you for always taking the time to listen to my rants, celebrating my publications, and always cheering me up – you have been the one of the most beautiful and integral parts of my PhD life.
Contents

<table><tr><td>Contents</td><td>x</td></tr><tr><td>List of Figures</td><td>xiv</td></tr><tr><td>List of Tables</td><td>xviii</td></tr><tr><td>I Overview</td><td>1</td></tr><tr><td>1 Introduction</td><td>3</td></tr><tr><td>1.1 Privacy in Practice</td><td>4</td></tr><tr><td>1.2 Privacy-Utility Trade-off</td><td>5</td></tr><tr><td>1.3 Contributions of this thesis</td><td>6</td></tr><tr><td>1.3.1 Synopsis</td><td>7</td></tr><tr><td>1.3.2 Publications</td><td>9</td></tr><tr><td>1.3.3 Select Talks</td><td>10</td></tr><tr><td>2 Foundations</td><td>11</td></tr><tr><td>2.1 Standards of Privacy</td><td>11</td></tr><tr><td>2.2 Federated Learning</td><td>13</td></tr><tr><td>2.3 Notions of Utility</td><td>14</td></tr><tr><td>II Location privacy</td><td>16</td></tr><tr><td>3 PRIVIC: A privacy-preserving method for incremental collection of location data</td><td>18</td></tr><tr><td>3.1 Introduction</td><td>18</td></tr><tr><td>3.2 Technical preliminaries</td><td>21</td></tr><tr><td>3.3 Related Work</td><td>24</td></tr><tr><td>3.4 Location-privacy with the Blahut-Arimoto algorithm</td><td>25</td></tr><tr><td>3.4.1 Elastic location-privacy with BA</td><td>25</td></tr><tr><td>3.4.2 Statistical utility: BA vs LAP</td><td>29</td></tr><tr><td>3.5 Duality between IBU and BA</td><td>30</td></tr><tr><td>3.6 PRIVIC: a privacy-preserving method for incremental data collection</td><td>31</td></tr><tr><td>3.7 Experimental analysis of PRIVIC</td><td>34</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>3.8</td>
      <td>Vulnerability of PRIVIC</td>
      <td>39</td>
    </tr>
    <tr>
      <td>4</td>
      <td>A privacy-preserving querying mechanism with high utility for electric vehicles</td>
      <td>41</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Introduction</td>
      <td>41</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Related Work</td>
      <td>43</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Approximate geo-indistinguishability (AGeoI)</td>
      <td>45</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>System Model</td>
      <td>47</td>
    </tr>
    <tr>
      <td>4.4.1</td>
      <td>Problem Statement</td>
      <td>47</td>
    </tr>
    <tr>
      <td>4.4.2</td>
      <td>Road Network Model</td>
      <td>48</td>
    </tr>
    <tr>
      <td>4.4.3</td>
      <td>System Architecture</td>
      <td>48</td>
    </tr>
    <tr>
      <td>4.4.4</td>
      <td>Privacy Threat Landscape</td>
      <td>50</td>
    </tr>
    <tr>
      <td>4.4.5</td>
      <td>Proposed Query Model</td>
      <td>51</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Cost of privacy analysis</td>
      <td>53</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Experimental Study</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.6.1</td>
      <td>Dataset Preparation</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.6.2</td>
      <td>Experimental Setup</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.6.3</td>
      <td>Results and Discussion</td>
      <td>56</td>
    </tr>
    <tr>
      <td>III</td>
      <td>Federated learning</td>
      <td>61</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Advancing Personalized Federated Learning: Group Privacy, Fairness, and Beyond</td>
      <td>63</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Introduction</td>
      <td>63</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Technical Preliminaries</td>
      <td>65</td>
    </tr>
    <tr>
      <td>5.2.1</td>
      <td>Personalized Federated Learning</td>
      <td>65</td>
    </tr>
    <tr>
      <td>5.2.2</td>
      <td>Fairness</td>
      <td>66</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Related Works</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>An Algorithm for Private and Personalized Federated Learning</td>
      <td>68</td>
    </tr>
    <tr>
      <td>5.4.1</td>
      <td>The Laplace mechanism under Euclidean distance in R<sup>n</sup></td>
      <td>69</td>
    </tr>
    <tr>
      <td>5.4.2</td>
      <td>A Heuristic for defining the Neighbourhood of a Client</td>
      <td>70</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Experiments</td>
      <td>70</td>
    </tr>
    <tr>
      <td>5.5.1</td>
      <td>Characterizing privacy</td>
      <td>70</td>
    </tr>
    <tr>
      <td>5.5.2</td>
      <td>Synthetic Data</td>
      <td>71</td>
    </tr>
    <tr>
      <td>5.5.3</td>
      <td>Hospital Charge Data</td>
      <td>71</td>
    </tr>
    <tr>
      <td>5.5.4</td>
      <td>FEMNIST Image Classification</td>
      <td>73</td>
    </tr>
    <tr>
      <td>5.5.5</td>
      <td>Characterizing fairness</td>
      <td>75</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Characterizing the information leakage from gradient updates in federated learning</td>
      <td>79</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Introduction</td>
      <td>79</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Preliminaries</td>
      <td>80</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Federated learning setup</td>
      <td>81</td>
    </tr>
    <tr>
      <td>6.3.1</td>
      <td>Overview of the federated model training</td>
      <td>82</td>
    </tr>
    <tr>
      <td>6.3.2</td>
      <td>The neural network model</td>
      <td>82</td>
    </tr>
  </tbody>
</table>
<table><tr><td>6.3.3 The NN training process</td><td>82</td></tr><tr><td>6.3.4 Adversarial assumptions</td><td>82</td></tr><tr><td>6.3.5 Measuring information leakage</td><td>83</td></tr><tr><td>6.4 Information leakage in simple FL models</td><td>83</td></tr><tr><td>6.4.1 Technical setup</td><td>84</td></tr><tr><td>6.4.2 Analysing gradient leaks</td><td>85</td></tr><tr><td>6.4.3 Leakage from bigger batches</td><td>87</td></tr><tr><td>6.4.4 Leakage from batches size = 2:</td><td>89</td></tr><tr><td>6.5 Analyzing multi-layer neural networks</td><td>90</td></tr><tr><td>6.5.1 Extending the TNN to a larger NN</td><td>92</td></tr><tr><td>6.5.2 Leakage from the penultimate layer.</td><td>93</td></tr><tr><td>6.6 Discussion and open questions.</td><td>93</td></tr><tr><td><b>IV Private data trading</b></td><td><b>94</b></td></tr><tr><td><b>7 An incentive mechanism for trading personal data in data markets</b></td><td><b>96</b></td></tr><tr><td>7.1 Introduction.</td><td>96</td></tr><tr><td>7.2 Related Work</td><td>97</td></tr><tr><td>7.3 Incentive mechanism for data markets</td><td>99</td></tr><tr><td>7.3.1 Overview of the proposed technique</td><td>99</td></tr><tr><td>7.3.2 Truthful price report mechanism</td><td>101</td></tr><tr><td>7.3.3 Optimizing the incentive mechanism</td><td>103</td></tr><tr><td>7.3.4 Discussion.</td><td>105</td></tr><tr><td>7.3.5 Optimized privacy budget splitting mechanism for data providers</td><td>106</td></tr><tr><td>7.4 Experimental results</td><td>107</td></tr><tr><td><b>8 Establishing the price of privacy in federated data trading</b></td><td><b>109</b></td></tr><tr><td>8.1 Introduction.</td><td>109</td></tr><tr><td>8.2 Related Work</td><td>110</td></tr><tr><td>8.3 Technical Preliminaries.</td><td>111</td></tr><tr><td>8.3.1 Shapley value.</td><td>111</td></tr><tr><td>8.4 Differentially Private Data Trading Mechanism</td><td>112</td></tr><tr><td>8.4.1 Mechanism outline</td><td>112</td></tr><tr><td>8.4.2 Earning Splitting</td><td>115</td></tr><tr><td>8.5 Experimental results</td><td>118</td></tr><tr><td>8.5.1 Number of rounds needed for data collection</td><td>119</td></tr><tr><td>8.5.2 Number of free riders by penalty scheme</td><td>120</td></tr><tr><td>8.5.3 Reduced Shapley value computation time</td><td>121</td></tr><tr><td><b>9 Conclusion and Future Work</b></td><td><b>122</b></td></tr><tr><td><b>References</b></td><td><b>127</b></td></tr></table>
<table><thead><tr><th>Contents</th><th>xiii</th></tr></thead><tbody><tr><td>Appendices</td><td>147</td></tr><tr><td>A Proofs from Chapter 3</td><td>148</td></tr><tr><td>B Tables from Chapter 3</td><td>151</td></tr><tr><td>C Proofs from Chapter 4</td><td>152</td></tr><tr><td>D Proofs from Chapter 5</td><td>154</td></tr><tr><td>E Experimental settings in Chapter 5</td><td>158</td></tr><tr><td>F Proofs from Chapter 6</td><td>161</td></tr><tr><td>G Proofs from Chapter 7</td><td>171</td></tr><tr><td>H Examples from Chapter 7</td><td>173</td></tr><tr><td>I Proofs from Chapter 8</td><td>176</td></tr></tbody></table>
List of Figures

<table>
  <tbody>
    <tr>
      <td>2.1</td>
      <td>A schematic overview of the working of local differential privacy.</td>
      <td>12</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>Illustration of the working of federated learning for model training</td>
      <td>13</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Distribution of privatizing the vulnerable and the strong locations for different levels of privacy. Top-down, the rows illustrate the results for ε = 0.4, 1.2, 1.6, 2, respectively.</td>
      <td>27</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Gowalla check-in locations in Paris with an artificially planted vulnerable point, A, in isolation, and a strong point, B, in a crowded area.</td>
      <td>28</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>Statistical utility in terms of earth mover's distance (EMD) between the true and the estimated distributions for locations in Paris and San Francisco, under BA and LAP.</td>
      <td>29</td>
    </tr>
    <tr>
      <td>3.4</td>
      <td>Illustration of the duality between BA and IBU.</td>
      <td>30</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>Illustration of the iterative process of PRIVIC.</td>
      <td>32</td>
    </tr>
    <tr>
      <td>3.6</td>
      <td>(a) visualizes the original locations from Gowalla dataset from Paris and San Francisco. (b) illustrates a heatmap representation of the locations in the two cities to capture the distribution of the data.</td>
      <td>35</td>
    </tr>
    <tr>
      <td>3.7</td>
      <td>Visualization of the estimated true distribution of the locations in Paris (a) and (b)) and San Francisco (c) and (d)) by PRIVIC after its convergence; the first column is for β = 0.5 and the second column is for β = 1.</td>
      <td>37</td>
    </tr>
    <tr>
      <td>3.8</td>
      <td>(a) and (b) show the EMD between the true PMF of the Paris locations and its estimation by PRIVIC in each of its cycle for β = 0.5 and β = 1, respectively.</td>
      <td>37</td>
    </tr>
    <tr>
      <td>3.9</td>
      <td>(a) and (b) show the EMD between the true PMF of the San Francisco locations and its estimation by PRIVIC in each of its cycles for β = 0.5 and β = 1, respectively.</td>
      <td>38</td>
    </tr>
    <tr>
      <td>3.10</td>
      <td>(a) and (b) illustrate that EMD between the true and the estimated distributions of the locations in Paris and San Francisco, respectively, after the empirical convergence of PRIVIC for the different values of the loss parameters β.</td>
      <td>38</td>
    </tr>
    <tr>
      <td>3.11</td>
      <td>Effect on the privacy provided by BA to obfuscate the geo-spatially isolated location (Location A as in Figure 3.1) for different fractions of adversarial users who intentionally report their locations falsely under two different levels of formal geo-ind guarantees by BA.</td>
      <td>40</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>System Architecture (EV: Electric Vehicle, RSU: Roadside Unit, MEC: Mobile-Edge Computing Unit)</td>
      <td>49</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>4.2</td>
      <td>Reported dummy and privatised locations for two respective time windows (White Pins: Privatised locations, Orange Pins: Dummy locations in 1<sup>st</sup> Time window, Blue Pins: Dummy locations in 2<sup>nd</sup> Time window)</td>
      <td>52</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>A toy example for a static location query on discrete road network</td>
      <td>52</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>A toy example for linked 3 location queries on discrete road network</td>
      <td>52</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>CoP (i.e., by Definition 4.5.1, the difference in the distance an EV needs to cover to reach the nearest CS with and without local obfuscation to achieve AGeoI) for varying ε or r of AGeoI (1<sup>st</sup> row is for sparse CS, 2<sup>nd</sup> row is for dense CS).</td>
      <td>57</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Fraction of EVs incurring no CoP for varying ε or r of AGeoI (1<sup>st</sup> row is for sparse CS, 2<sup>nd</sup> row is for dense CS).</td>
      <td>57</td>
    </tr>
    <tr>
      <td>4.7</td>
      <td>Impact of introducing dummy locations along with AGeoI on the CoP.</td>
      <td>58</td>
    </tr>
    <tr>
      <td>4.8</td>
      <td>The Kantorovich-Wasserstein distance between the original and estimated distributions using IBU for ε = 0.6 and ε = 2 noisy distributions.</td>
      <td>58</td>
    </tr>
    <tr>
      <td>4.9</td>
      <td>Estimations of the original distribution using IBU for the ε = 0.6 and ε = 2 noisy distributions.</td>
      <td>59</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>A schematic overview of the personalized approach of federated model training</td>
      <td>65</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>An illustration of the implementation of the Laplace mechanism to achieve ε-d-privacy for model parameters in R<sup>2</sup></td>
      <td>70</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Learning federated linear models with (a, b, c) one initial hypothesis and non-sanitized communication, (d, e, f) two initial hypotheses and non-sanitized communication, (g, h, i) two initial hypotheses and sanitized communication. The first two figures of each row show the parameter vectors released by the clients to the server.</td>
      <td>72</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Synthetic data: max privacy leakage among clients. Privacy leakage is constant when clients with the largest privacy leakage are not sampled (by chance) to participate in those rounds.</td>
      <td>73</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>RMSE for models trained with Algorithm 6 on the Hospital Charge Dataset. Error bars show ±σ, with σ the empirical standard deviation. Lower RMSE values are better for accuracy.</td>
      <td>74</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>Hospital charge data: the empirical distribution of the privacy budget over the clients for v = 3, 5 initial hypotheses, seed = 3, r is the radius of the neighbourhood, and the total number of clients is 2062.</td>
      <td>74</td>
    </tr>
    <tr>
      <td>5.7</td>
      <td>Effects of the Laplace mechanism in Proposition 5.1 with different noise multipliers as a defense strategy against the DLG attack.</td>
      <td>75</td>
    </tr>
    <tr>
      <td>5.8</td>
      <td>The first two plots from the left illustrate the spatial distribution of the samples in g<sub>1</sub> and g<sub>2</sub>, respectively, and the third plot shows g<sub>1</sub> and g<sub>2</sub> superimposed together in the same space.</td>
      <td>76</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>5.9</td>
      <td>The figure shows the comparison between the personalized and non-personalized models for (from left) equal opportunity, equalized odds, and demographic parity, respectively. Experiments were performed for noise multipliers v of 0.1, 1, 2, and 4. For all the metrics of fairness and the values of the noise multiplier, the personalized model is seen to possess improved fairness over the non-personalized model.</td>
      <td>77</td>
    </tr>
    <tr>
      <td>5.10</td>
      <td>The figure shows the comparison between the personalized and non-personalized models for equal opportunity equalized odds, and demographic parity. Experiments were performed for noise multipliers v of 0.1, 1, 2, and 4. For all metrics of fairness and values of the noise multiplier, the personalized model improved fairness over the non-personalized model.</td>
      <td>78</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Illustration of a toy neural network consisting of a single input x and a final layer with 2 nodes and a softmax activation function, interpreted as a probability distribution over labels. We include bias terms in each node in the final layer.</td>
      <td>84</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Larger neural network example. The final layer is fully connected although this is not depicted in the diagram for simplicity of labelling. We make no assumptions about the number of hidden layers.</td>
      <td>91</td>
    </tr>
    <tr>
      <td>7.1</td>
      <td>An example of data trading process. In this figure, u<sub>i</sub> means the i<sup>th</sup> data provider and D<sub>j</sub> means the j<sup>th</sup> data consumer.</td>
      <td>99</td>
    </tr>
    <tr>
      <td>7.2</td>
      <td>An example of a monotonically decreasing function f(z). Let c be a parameter representing the “reported value-to-admitted ε value” ratio. For z ≥ 0, we set f(z) as f(z) = ln(e − cz) if (e − cz) ≤ 1, and f(x) = 0 otherwise.</td>
      <td>101</td>
    </tr>
    <tr>
      <td>7.3</td>
      <td>Graphical illustration of Theorem 7.3. We prove that ρ(π<sub>i</sub>)(blue hatching area) is always larger than ρ(p<sub>i</sub>)(blue rectangle area+red hatching area–green rectangle area).</td>
      <td>102</td>
    </tr>
    <tr>
      <td>7.4</td>
      <td>Illustrating the payoff for c and the incentive plot for the data consumer involving one data provider reporting p<sub>1</sub>. The Y-intercept of μ is ∫<sub>p<sub>1</sub></sub><sup>∞</sup> f(z)dz.</td>
      <td>104</td>
    </tr>
    <tr>
      <td>7.5</td>
      <td>Experimental result of profit under a fixed budget. The log function represents the family ln(e − cp) and the linear function represents the family 1 − cp. We let the parameter c range from 0 to 1. The red bin represents the optimal value of c, namely the c that gives maximum information.</td>
      <td>108</td>
    </tr>
    <tr>
      <td>8.1</td>
      <td>Some examples of the privacy valuation function f illustrated with different values of K<sub>1</sub> and K<sub>2</sub>. The data consumer decides the values of the scaling factors K<sub>1</sub> and K<sub>2</sub> according to her requirement and broadcasts the determined function to the federations.</td>
      <td>113</td>
    </tr>
    <tr>
      <td>8.2</td>
      <td>The number of rounds required by a federation (of varying sizes) to achieve the privacy level (i.e., information accuracy) to be reported to the data consumer is less for the catalyzing method introduced in the data collection than its non-catalyzing counterpart.</td>
      <td>120</td>
    </tr>
  </tbody>
</table>
8.3 The number of free riders incurred by the penalty scheme (for varying sizes of the federation and the tolerance threshold) is significantly less adapting the catalyzing method for data collection than the non-catalyzing method. . . . . . . . . 121
List of Tables

<table><tr><td>3.1</td><td>Run-time and complexity of BA and IBU in each cycle of PRIVIC</td><td>35</td></tr><tr><td>5.1</td><td>Hospital charge data: median and maximum local privacy budgets over the whole set of clients, averaged over 10 runs with different seeds. v = 0 means no privacy guarantee.</td><td>73</td></tr><tr><td>5.2</td><td>Effects of increasing the noise multiplier on the validation accuracy and standard deviation.</td><td>74</td></tr><tr><td>6.1</td><td>An example of a batch used in a given round of training consisting of datapoints which are similar as per Def. 6.4.3 for an FL model that has learnt well as per Def. 6.4.2. In other words, the images of the dog, the wolf, and the fox used in the training batch have very similar true-positive and true-negative probabilities.</td><td>89</td></tr><tr><td>8.1</td><td>Computation time of brute force and proposed pruning method</td><td>121</td></tr><tr><td>B.1</td><td>EMD between the true and the estimated PMFs by PRIVIC on the Paris locations.</td><td>151</td></tr><tr><td>B.2</td><td>EMD between the true and the estimated PMFs by PRIVIC on the San Francisco locations.</td><td>151</td></tr><tr><td>E.1</td><td>NN architecture adopted in the experiments of Section 5.5.4</td><td>160</td></tr></table>
# Part I

## Overview
"Remember, Red, hope is a good thing, maybe the best of things, and no good thing ever dies."

– Andy Dufresne, *The Shawshank Redemption*
Introduction

Ronald H. Coase, a renowned and celebrated economist, in a talk at the University of Virginia in the early 1960s, famously quoted “Torture the data and it will confess to anything.” About half a century later, Forbes' estimation that about 90% of the data in the world was generated in the last two years [1] suggests that we are, well and truly, headed towards a data-driven society. This huge surge of data harvesting mainly caters to a diverse range of analytics performed and technologies developed using them which, in turn, contributes to the rise of a variety of services that we indispensable cherish in our daily lives.

A flip side to this flourishing advancement of data science and technology is the progressive growth of dangerous attacks invading the privacy of the individuals whose sensitive information is often contained in the datasets produced, used, and analysed. One of the scarier facets of such blooming threats to violate individuals' privacy is that they often involve, feature, or compromise institutions, organisations, and services (e.g., Facebook [2–4], Google [5, 6], Yahoo [7], Netflix [8], Public Transport Victoria, Government of Australia [9], etc.) that are typically inseparable from and intrinsically facilitate our contemporary lifestyle.

The right to privacy is a universally recognised human right. Criticizing the *nothing to hide argument*, former computer intelligence consultant and whistleblower Edward Snowden famously stated “Arguing that you don’t care about privacy because you have nothing to hide is no different than saying you don’t care about free speech because you have nothing to say.” An individual’s right to digital privacy involves their right to moderate the use of their personal data – the manner in which they are stored, handled, and protected from potential threats. Although data privacy often intertwines with cybersecurity, it is crucial to note that with modern standards, while leaked passwords can be modified or stolen credit cards blocked or re-issued,
privacy, once compromised, cannot be so easily reinstated. Hence, it is of utmost importance to furnish sound and applicable privacy-preserving technologies, methods, and tools. Alongside protecting the privacy of individuals’ personal information, it is unequivocally acknowledged that, under such privacy guarantees, the shared data still needs to be utilisable in order to foster the services and analytics that are essential to sustain the modern technology-driven lifestyle around the globe.

### 1.1 Privacy in Practice

In the past, privacy breaches, although deemed to be threatening<fnref n="1" /> indeed they were characterised and documented by the statistician Tore Dalenius [10], but not enough attention was given to this as they were thought to be practically infeasible due to the amount of information needed by an attacker in order to correlate any released statistics with particular individuals and their sensitive attributes. In fact, until the early 2000s, data anonymisation was regarded as a sufficient step for protecting individuals’ privacy, and this understanding is reflected in the privacy laws that still stand today in many countries including Australia and the United States.<fnref n="2" />

Early in the 2000’s some infamous privacy-compromising attacks elucidated the weaknesses of anonymisation-based techniques in the face of large-scale access to publicly available datasets. Some major examples include: In 2002, Latanya Sweeney identified the medical data of the governor of Massachusetts from anonymized hospital records by linking them with the publicly available information in a voter database [11]; In 2006, an anonymised dataset of movie ratings released by Netflix for a competition designed to improve their recommendation model was famously attacked by researchers Shmatikov and Narayanan [8]<fnref n="3" />; Recently, the US Census Bureau re-examined census data from 1940 and was able to reconstruct the details of individuals using now-available information [12]. These attacks were made possible by the scale of publicly available data on the internet and showed a gaping loophole in the anonymization-based data protection techniques which did not consider an attacker’s background knowledge.

In 2006, differential privacy (DP) was proposed by Dwork et al. [13, 14] that emerged to solve the problem of privacy for individuals in structured datasets. The rudimentary idea behind DP relies on ‘plausible deniability’ for individuals in that the response of a query performed on the dataset is almost probabilistically agnostic to the presence or the absence of the record of a certain individual in the dataset and, thus, it is argued that an individual’s presence in a dataset is protected. DP is now flourished to be arguably the state-of-the-art standard for data privacy due to a variety of advantages it endorses including but not limited to its well-behaved compositionability, its robustness to background knowledge, the possibility to tune the noise to harbour a desirable level of accuracy, and its straightforward applicability. These properties set it apart from anonymisation-based privacy standards that were promoted in the past and have

<footnote n="1">¹The US Census Bureau has had formal privacy requirements for statistical data releases in place since the 1920’s: https://www.census.gov/history/www/reference/privacy_confidentiality/privacy_and_confidentiality_2.html.</footnote>

<footnote n="2">²See Australian Privacy Act: https://www.oaic.gov.au/privacy/guidance-and-advice/de-identification-and-the-privacy-act/ or the US HIPAA: https://www.hhs.gov/hipaa/for-professionals/privacy/laws-regulations/index.html.</footnote>

<footnote n="3">³https://www.wired.com/2009/12/netflix-privacy-lawsuit/</footnote>
been shown to be susceptible to adversarial attacks when combined with other anonymised datasets [15].

In 2012, the notion of “metric differential privacy” was introduced in order to enable DP-style reasoning in the domain of arbitrary spaces endowed with metrics. Such metric-based DP provides a generalisation and re-interpretation of DP accounting for a notion of “distance” between the secrets. Exploiting the fact that some of the main characteristics of DP rely on the metric properties of the Hamming distance between datasets, the notion of geo-indistinguishability and *d*-privacy were proposed [16, 17] that proved to be extremely suitable to privatize location data while harbouring a high utility without digressing from the strong and formal qualities that classical DP offers.

The aforementioned standards of privacy guarantees, although formal, are often hard to interpret for non-experts. For example, in practical scenarios, the privacy parameter of DP – typically denoted by an $\varepsilon$ – is usually seen as a parameter for tweaking *utility* without associating any specific and interpretable meaning to the resulting privacy guarantee [18]. Since the value of $\varepsilon$ in DP is not consequentially meaningful to an end user, the community, of late, has focussed on more “pragmatic” interpretation of data privacy like measuring the information leakage in a given mechanism [19] and defending against the rising data-reconstruction attacks [20, 21] in privacy-preserving machine learning.

In this thesis, we study the interaction privacy guarantees and the utility of data from a variety of perspectives considering a diverse range of contexts and use cases. The work presented in the thesis primarily focuses on a foundational approach to analyse the trade-off between formal cutting-edge standards of data privacy and their context-specific utility across different applications like location privacy, privacy-preserving machine learning, and economics of data privacy involving private data trading in data markets.

## 1.2 Privacy-Utility Trade-off

Our goal in this thesis is to explore the trade-off between privacy and utility endorsed by the application of DP and its variants and optimize it from a foundational perspective. Because of its widespread acceptance, the community (industry and academia alike) have been tempted to study and adopt DP and its variants in a wide range of domains. However, such extensive application of DP comes at the cost of degrading the utility of the data due to the addition of noise. To adhere to the rudimentary purpose of data analytics, it is imperative that the privacy guarantees on the collected and shared data do not make the utility for the users and the service providers redundant. Therefore, in order to succumb to the role of data in the development of technologies integral to our contemporary life, it is very important to understand and optimise the age-old battle between privacy and accuracy.

“Utility” is a highly metaphysical concept. In particular, the utility of data typically alters with the context and the priorities. Therefore, to fabricate a foundational understanding of how this rather philosophical concept entangles with the standards of privacy used in practice, it is crucial to quantify it. Broadly speaking, the utility of the shared data has two primary facets: a)
for the data providers (e.g., users of a service) and b) for the data collectors (e.g., the service providers). The literature has explored a bundle of formalizations of the notion of utility from both ends. For example, for location-based services (e.g., GPS, location-based games, dating apps, etc.), the most intuitive and commonly accepted notion for the utility of the users is their quality of service (QoS) with respect to some chosen distortion metric (e.g., on an average, how much extra distance one needs to cover as a result of privatizing their reported locations). In machine learning, depending on the task, utility for the users usually revolve around the trained model's accuracy and fairness. In data markets, the utility of the participating clients is mostly related to financial incentives. For data collectors, utility fundamentally depends on the statistical precision (e.g., the accuracy of the estimation of the true distribution of the original data having observed the privatized data) of the collected data under their privacy guarantees.

Garfinkel et al. famously quoted in [22], “Differential privacy lacks a well-developed theory for measuring the relative impact of added noise on the utility of different data products, tuning equity trade-offs, and presenting the impact of such decisions.” Indeed, in complex domains, the question of *how to appropriate the noise so that the data still remains desirably utilisable?* becomes relevant. This, in turn, leads us to many open questions along this line. For example, a) in location privacy, how non-trivial is it to optimize the three-way trade-off between the privacy of the users, their QoS, and the statistical utility of the service providers? b) in machine learning, how much *really* does federated learning help in protecting the information leakage from the shared model updates and how do the model accuracy and the formal privacy guarantees interact with the more pragmatic comprehension of a user's data privacy (e.g., defending against attacks that are able to reconstruct the training data from the available information)? c) Does there exist a sound way to price private data and enable an efficient working of data markets? These questions underlie the need for a more principled and foundational approach to understanding the nature of the privacy-utility balance which forms the kernel of this thesis.

## 1.3 Contributions of this thesis

In this thesis, we examine some of the riveting questions around privacy and utility posed in the previous section with the overall goal of advancing the understanding and optimization of the privacy-utility trade-off in various domains. In particular, this work makes the following contributions:

1. We have explored the extensive privacy-preserving properties of the Blahut-Arimoto algorithm and highlighted its substantial advantages over the state-of-the-art Laplace mechanism for geo-indistinguishability and, thus, established it as a prime candidate for a location privacy-preserving mechanism. Hence, bridging some key ideas from information theory and statistics, we proposed a method allowing an incremental collection of location data as a step towards optimizing the location privacy of the data owners, their quality of service, and the statistical utility for the data consumers.

2. Due to the disproportionately fewer charging stations (CSs) as compared to the surge in
the use of electric vehicles (EVs), we addressed a fundamental problem of the risk of privacy violation for EVs dynamically querying for available CSs along their journeys. To this, we theorised the notion of approximate geo-indistinguishability that allows us to attain geo-indistinguishability in a strictly bounded space. Hence, we proposed an efficient privacy-preserving navigation method for EVs that protect the privacy of both their individual query locations and the overall trajectories of their journeys alongside upholding a high utility for the EVs.

3. We extended the notion of geo-indistinguishability to federated learning and proposed a method leveraging advanced techniques for model personalization and addressing user privacy concerns by formalizing privacy guarantees in terms of *d*-privacy. Analyzing the role of *d*-privacy in personalized federated learning, we demonstrated a significant improvement in group fairness under formal privacy guarantees compared to the non-personalized federated learning framework and, hence, establish that our method enhances the trade-off between privacy and fairness.

4. Continuing investigating the privacy-preserving aspects of machine learning, we provided a formal characterization of the information leakage from the shared gradient updates in federated learning and analyzed the gradient-inversion type reconstruction attacks in federated learning to understand their working from a foundational perspective.

5. Shifting towards the economics of data privacy, we proposed a framework in data markets that maximizes the data providers' financial utility while optimizing a data consumer's profit and information gain w.r.t. their financial constraints. Thereafter, we considered a federated data trading environment and proposed a method to achieve an efficient working of federated data markets for trading data under differential privacy.

### 1.3.1 Synopsis

The technical chapters of this thesis are divided into 3 parts:

**Part II: Location Privacy** focuses on the privacy-utility trade-offs in domains specifically pertaining to the sharing of location data containing sensitive information.

- **Chapter 3** illustrates that geo-indistinguishability (geo-ind), a cutting-edge standard to mitigate the privacy risks for location data, alone is insufficient to cover all privacy concerns. In particular, isolated locations are not protected by the canonical Laplace mechanism (LAP), the state-of-the-art for geo-ind. We show that the Blahut-Arimoto algorithm (BA), in addition to providing geo-ind, protects the geo-spatially isolated points. Furthermore, BA provides an optimal trade-off between information leakage and quality of service and has a better statistical utility than LAP for high privacy levels. Exploiting these properties of BA and establishing its duality with the iterative Bayesian update, an instance of the expectation-maximization method, we propose PRIVIC, an iterative method for a privacy-friendly incremental collection of location data.
- **Chapter 4** considers the surge in popularity of electric vehicles (EVs) and, due to the fact that the number of charging stations (CSs) is disproportionately fewer than that of the EVs in use, a rise in range anxiety and an increase in queries made during journeys to find an available CS. We introduce the notion of approximate geo-ind (AGeoI) which allows the EVs to obfuscate the individual query locations while ensuring that they remain within their preferred area of interest. It is vital because journeys are often sensitive to a sharp drop in quality of service (QoS) which incurs a high cost. The proposed method combines the application of AGeoI and the generation of dummy data to provide two-fold privacy protection (individual query locations and the trajectory of the entire journeys) for EVs while preserving a high level of utility. Moreover, our method allows for a private and precise prediction of occupancies of CSs which is crucial in unprecedented traffic congestion scenarios and efficient route planning.

**Part III: Federated learning** analyzes the privacy-preserving aspects of federated learning and aims to deepen the understanding of the privacy-utility trade-off in federated learning.

- **Chapter 5** explores some of the vulnerabilities of federated learning (FL) such as leakage of private information, lack of personalization of the model, and the possibility of the trained model being fairer to some groups than to others. We aim to address a triadic interaction between the personalization, privacy guarantees, and fairness achieved by the trained models under FL. Clients in FL often hold very diverse datasets representing heterogeneous communities, making it important to protect their sensitive and personal information while still ensuring that the trained model is utilisable and fair. We propose a method that incorporates a generalization of geo-ind in FL that enables personalized model training in a federated approach, provides formal group privacy guarantees locally (i.e., does not have the need for clipping or a trusted curator to add noise), and possesses significantly better group fairness measured under a variety of standard metrics than a global model trained in a classical FL template.

- **Chapter 6** analyzes the potential privacy concerns in the federated framework of model training. We show that FL, although typically perceived as a stepping stone towards privacy-preserving machine learning, is vulnerable to significant information leakage via the gradients shared by the clients. Therefore, some recent work has highlighted potential gradient inversion based attacks that can reconstruct the training data despite not having direct access to them which, in turn, defeats the whole philosophy and motivation behind the development of FL. This work aims to provide a formal characterization and an elaborate comprehension of the information leakage from the shared gradient updates in FL from a foundational perspective to analyse such data reconstruction attacks relying on gradient inversion violating the clients' privacy in FL.

**Part IV: Private data trading** presents the application of differential privacy in digital economics and proposes efficient and practical ways to trade private data in data markets.

- **Chapter 7** introduces a truthful price report mechanism that facilitates an accurate reporting of privacy requirements by data providers in data markets and, eventually, optimizes the data consumer's profit trading differentially private data w.r.t. their budget constraints.
- **Chapter 8** considers a model of federated data markets, i.e., data markets in which data providers, who are, generally, less influential on the market than data consumers, form federations for trading their data under differential privacy guarantees. We propose an efficient technique to price private data and a revenue-distribution mechanism to distribute the utility fairly within federations while motivating the data providers to cooperate with their respective federations, facilitating a fair and swift private data trading process.

### 1.3.2 Publications

The following is a list of the published papers that I have co-authored during the course of my Doctoral studies which have been used in this thesis.

1. F. Galli, K. Jung, S. Biswas, C. Palamidessi, and T. Cucinotta, "Advancing personalized federated learning: Group privacy, fairness, and beyond," *Special Issue of Springer Nature Computer Science: Recent Trends on Information Systems Security and Privacy*, 2023 (to appear). The work carried out in this paper has been used in Chapter 5 of this thesis.

2. S. Biswas and C. Palamidessi, "PRIVIC: A privacy-preserving method for incremental collection of location data," in *Proceedings on Privacy Enhancing Technologies (PoPETs) – PETS 2024 (to appear)*. The work carried out in this paper has been used in Chapter 3 of this thesis.

3. F. Galli., S. Biswas., K. Jung., T. Cucinotta., and C. Palamidessi., "Group privacy for personalized federated learning," in *Proceedings of the 9th International Conference on Information Systems Security and Privacy - ICISSP*, pp. 252–263, INSTICC, SciTePress, 2023. The work carried out in this paper has been used in Chapter 5 of this thesis.

4. S. Biswas, K. Jung, and C. Palamidessi, "An incentive mechanism for trading personal data in data markets," in *Theoretical Aspects of Computing – ICTAC 2021* (A. Cerone and P. C. Ölveczky, eds.), (Cham), pp. 197–213, Springer International Publishing, 2021. The work carried out in this paper has been used in Chapter 7 of this thesis.

5. K. Jung, S. Biswas, and C. Palamidessi, *Establishing the Price of Privacy in Federated Data Trading*, pp. 232–250. Cham: Springer International Publishing, 2021. The work carried out in this paper has been used in Chapter 8 of this thesis.

The following is a paper that I have co-authored during the course of my Doctoral studies which have been used in this thesis and is currently under review for publication.

1. U. I. Atmaca, S. Biswas, C. Maple, and C. Palamidessi, "A privacy preserving querying mechanism with high utility for electric vehicles," in *IEEE Open Journal of Vehicular Technology*. The work carried out in this paper has been used in Chapter 4 of this thesis.

2. S. Biswas, K. Jung, and C. Palamidessi, "Tight differential privacy guarantees for the shuffle model with $k$-randomized response," in *Proceedings of the 16th International Symposium on Foundations & Practice of Security (FPS – 2023)*.

3. K. Jung, S. Biswas, and C. Palamidessi, "Optimal mechanism for private data trading in federated data market," in *Elsevier Advanced Engineering Informatics*.
The following is a list of papers that I have co-authored during the course of my Doctoral studies which got selected for presentation at some esteemed non-archival workshops.

1. S. Biswas and C. Palamidessi, "PRIVIC: A privacy-preserving method for incremental collection of location data," in *Theory and Practice of Differential Privacy (TPDP) 2023*. Selected for poster presentation. The work carried out in this paper has been used in Chapter 3 of this thesis.

2. F. Galli, S. Biswas, K. Jung, C. Palamidessi, and T. Cucinotta, "On the adaptive sensitivity of differentially private machine learning," in *The Fourth AAAI Workshop on Privacy-Preserving Artificial Intelligence in Conjunction with AAAI – PPAI 2023*. Selected for poster presentation.

3. F. Galli, S. Biswas, K. Jung, T. Cucinotta, and C. Palamidessi, "Group privacy for personalized federated learning," in *Workshop on Federated Learning: Recent Advances and New Challenges in Conjunction with NeurIPS – FL-NeurIPS 2022*. Selected as **one of the 12 amongst the 103 submissions for oral presentation**. The work carried out in this paper has been used in Chapter 5 of this thesis.

The following is a list of the published papers that I have co-authored which, although have not directly been used in this thesis, have supported and contributed immensely to the overall enhancement of my Doctoral studies.

1. S. Biswas, G. Cormode, and C. Maple, "Impact of sampling on locally differentially private data collection," in *Competitive Advantage in the Digital Economy (CADE 2022)*, vol. 2022, pp. 64–70, 2022. Winner of the **Best Paper Award**.

2. S. Biswas, K. Jung, and C. Palamidessi, "Tight differential privacy blanket for shuff model," in *Competitive Advantage in the Digital Economy (CADE 2022)*, vol. 2022, pp. 61–63, 2022.

### 1.3.3 Select Talks

1. "Group privacy for personalized federated learning" at the *Workshop on Federated Learning: Recent Advances and New Challenges in Conjunction with NeurIPS 2022 – FL-NeurIPS 2022* co-located with NeurIPS 2022 in New Orleans, USA on the 02 of December, 22.

2. "Group privacy for personalized federated learning" at the *Privacy Preserving Machine Learning (PPML) Workshop* organised by Meta in Paris, France on the 09 of November, 22.

3. "A privacy-preserving method for incremental collection of location data: Differential Privacy and beyond..." at the *7th Franco-Japanese Cybersecurity Workshop* in Tokyo, Japan on the 24th of October, 2022.

4. "Three-way optimization of privacy and utility of location data" at *Atelier sur la Protection de la Vie Privée (APVP) 2022* in Chatenay sur Seine, France on 15th of June, 2022.
## 2.1 Standards of Privacy

One of the most successful approaches to address the privacy risks of personal data while preserving their utility is differential privacy (DP) which mathematically guarantees that a query output does not change significantly regardless of whether a specific personal record is in a dataset or not. DP is considered to be the gold standard of formal privacy guarantees. Its widespread applicability, uncomplicated implementation techniques, and formal properties have led to a rapid growth in the popularity and interest to study and apply DP to a variety of domains in academia and industry alike. Over time, the community has explored various variants of DP addressing privacy concerns in different contexts and under a variety of threat models.

**DEFINITION 2.1.1 (Differential privacy [13, 14]).** Let $\mathcal{X}$ be a domain of secrets (e.g., personal data of users). For $\varepsilon, \delta \ge 0$, a randomizing mechanism $\mathcal{R}$ is $(\varepsilon, \delta)$-differentially private or $(\varepsilon, \delta)$-DP if, for any pair of adjacent 1 datasets $D_1$ and $D_2$ on $\mathcal{X}$ and measurable $S \subseteq \text{Range}(\mathcal{R})$, we have:

$$ \mathbb{P}[\mathcal{R}(D_1) \in S] \le e^{\varepsilon} \mathbb{P}[\mathcal{R}(D_2) \in S] + \delta \quad (2.1) $$

**REMARK 2.1.1.** When $\delta = 0$ in Equation (2.1), $\mathcal{R}$ is said to satisfy $\varepsilon$-DP which is often termed as pure DP.

<footnote n="1">¹We recall that two datasets *adjacent* if they differ in at most one entry.</footnote>
<figure><img src="image_2.png" /><figcaption>**Figure 2.1:** A schematic overview of the working of *local differential privacy*</figcaption></figure>

The above formulation of DP is typically referred to as the *central model* of DP as the noise to the true query response is generally added by a trusted central curator before publishing or performing analytics on it. Therefore, a major drawback of the central model is that it is vulnerable to security breaches because the entire original data is stored in a central server. Moreover, there is the risk that the curator may be corrupted. Hence, a local variant of the central model has been widely popularized recently [23], where the users apply a randomizing mechanism locally on their data and send the perturbed data to the collector such that a particular value of a user's data does not have a major probabilistic impact on the outcome of the query.

**DEFINITION 2.1.2 (Local differential privacy [23]).** For the domain of secrets $\mathcal{X}$ and an output set $\mathcal{Y}$, a randomizing mechanism $\mathcal{R}$ satisfies $\varepsilon$-local differential privacy or $\varepsilon$-LDP if, for every $x_1, x_2 \in \mathcal{X}$ and all measurable $S \subseteq \mathcal{Y}$, we have:

$$ \mathbb{P}[\mathcal{R}(x_1) \in S] \le e^{\varepsilon} \mathbb{P}[\mathcal{R}(x_2) \in S] \quad (2.2) $$

LDP is particularly suitable for situations where users need to communicate their personal data in exchange for some service. One such scenario is the use of location-based services where a user typically reports her location in exchange for information like the shortest path to a destination, points of interest in the surroundings, traffic information, friends nearby, etc. One of the recently popularised standards in location privacy is *geo-indistinguishability* (geo-ind) [16], which optimises the quality of service for users while preserving a generalised notion of LDP on their location data. The obfuscation mechanism of geo-ind depends on the distance between the original location of a user and a potential noisy location that they report [24, 25]. In general, *d-privacy* or *metric privacy* extends the concept of LDP to obfuscate points by capturing the essence of the distance between them. This notion of privacy is particularly useful in the context of location privacy as we will see in detail in Chapter II.

**DEFINITION 2.1.3 (d-privacy, a.k.a. metric privacy [17]).** For any space $\mathcal{X}$ equipped with a metric $d: \mathcal{X}^2 \to \mathbb{R}_{\ge 0}$ and an output space $\mathcal{Y}$, a randomizing mechanism $\mathcal{R}: \mathcal{X} \to \mathcal{Y}$ is $\varepsilon$-d-private if, for every $x_1, x_2 \in \mathcal{X}$ and all measurable $S \subseteq \mathcal{Y}$, we
<figure><img src="image_3.png" /><figcaption>Figure 2.2: Illustration of the working of federated learning for model training</figcaption></figure>

have:

$$ \mathbb{P}[\mathcal{R}(x_1) \in S] \le e^{\epsilon d(x_1, x_2)} \mathbb{P}[\mathcal{R}(x_2) \in S] \quad (2.3) $$

**DEFINITION 2.1.4 (Geo-indistinguishability [16]).** Setting $\mathcal{X} = \mathcal{Y} = \mathbb{R}^2$ and $d$ as the Euclidean metric in Definition 2.1.3 gives rise to a cutting-edge standard for location privacy known as *geo-indistinguishability (geo-ind)*.

As a generalization of LDP, geo-ind is the cutting-edge standard for location privacy circumventing the need for a central trusted curator. It can preserve the privacy of location data amongst a set of locations with similar probability distributions without requiring a trusted third party. It provides rigorous privacy for location-based query processing and location data collection by modelling the location domain based on the Euclidean plane and capturing the essence of the ground distance between points in the domain.

Note that:

i) If $\mathcal{X}$ is the set of all datasets and $d$ is the Hamming distance on the datasets in $\mathcal{X}$, we reduce down to the definition of DP.

ii) Setting $d$ as the discrete metric on any $\mathcal{X}$, we obtain the definition of LDP.

## 2.2 Federated Learning

Federated learning (FL) [26] has been in the spotlight recently as a rudimentary stepping stone towards privacy-preserving machine learning. FL is a distributed, collaborative approach to machine learning that aims to train a model without the need for the clients to share their personal data. In particular, in the classical framework of FL, a central server selects a random subset
of users and sends them a model for local optimization, following which the users locally optimize their model parameters to minimize a loss function over their own data (without sharing them with the server or any other participating client). Then these local updates are communicated back to the server which aggregates them to furnish the global update to be used by the next round's participating clients. This process is repeated until convergence. Figure 2.2 demonstrates a schematic outline of the working of FL. Despite being initially perceived as a foolproof solution to defend against major privacy concerns in machine learning, the community has exposed multiple vulnerabilities in FL (discussed and elaborated in Part III of the thesis). Therefore, there has been a surge of recent research that focuses on combining DP with FL in the quest to achieve a secure and private way of model training [27–30].

## 2.3 Notions of Utility

It is not preposterous to intuitively believe that, in most cases, privacy and utility of data stand against each other. As the primary goal of this thesis is to analyze this trade-off between privacy and utility in various contexts, it is important to quantify the corresponding application-specific concept of *utility*. Therefore, there has been a wide range of notions of utility considered in this thesis to incorporate the variety of use cases that we take into account. However, one of the fundamental and widely analyzed ideas to measure utility under differentially private (and, in general, noisy) data takes into account the level of statistical accuracy preserved by the data after being privatized. This is regarded as the statistical utility of the sanitized datasets and is often assessed by considering the difference between the distribution of the raw (non-privatized) data and that of the sanitized one.

While for the central model of DP, the “best guess” for the true distribution by observing the noisy dataset is the (normalized) noisy histogram itself, the problem of approximating the distribution of the original data from observing the noisy sample under local DP is slightly more non-trivial. To this purpose, two of the standard techniques to “de-noise” the locally obfuscated data, with the knowledge of the underlying privacy mechanism, to estimate true distribution are the methods of *matrix inversion* [31, 32] and *iterative Bayesian update (IBU)* [33]. IBU, an iterative method of expectation maximization, has been shown to be more robust and effective than the method of matrix inversion [34]. Amongst the diverse notions of utility under local privatizing methods (e.g., LDP, geo-indistinguishability, etc.) that have been considered in this thesis, one of the most fundamental ones, emphasized especially in the context of location privacy in Chapter II, have been comparing the distributions of the original data and that estimated by de-noising the privatized data using IBU and this notion is regarded as the statistical utility of the service providers of the privacy-preserving location-based services. The other diverse quantifications of utility (e.g., quality of service of users, accuracy in machine learning-related tasks, financial utility of parties involved in private data trading, etc.) have been introduced in the relevant chapter-specific preliminaries.

**DEFINITION 2.3.1 (Full-support probability distribution).** Let $\theta$ be a probability
distribution defined on the space $\mathcal{X}$. $\theta$ is a full-support distribution on $\mathcal{X}$ if $\theta(x) > 0$ for every $x \in \mathcal{X}$.

**DEFINITION 2.3.2 (Iterative Bayesian update [33]).** Let $C$ be a privacy mechanism that locally obfuscates points from the discrete space $\mathcal{X}$ to $\mathcal{Y}$ such that $C_{xy} = \mathbb{P}[y|x]$ for all $x, y \in \mathcal{X}, \mathcal{Y}$. Let $X_1, \dots, X_n$ be i.i.d. random variables on $\mathcal{X}$ following some PMF $\pi_{\mathcal{X}}$. Let $Y_i$ denote the random variable of the output when $X_i$ is obfuscated with $C$.

Let $\bar{y} = \{y_1, \dots, y_n\}$ be a realisation of $\{Y_1, \dots, Y_n\}$ and $q$ be the empirical distribution obtained by counting the frequencies of each $y$ in $\bar{y}$. The iterative Bayesian update (IBU) estimates $\pi_{\mathcal{X}}$ by converging to its maximum likelihood estimate (MLE) with the knowledge of $q$ and $C$. IBU works as follows:

1. Start with any full-support PMF $\theta_0$ on $\mathcal{X}$.

2. Iterate $\theta_{r+1}(x) = \sum_{y \in \mathcal{Y}} q(y) \frac{\theta_r(x) C_{xy}}{\sum_{z \in \mathcal{X}} \theta_r(z) C_{zy}}$ for all $x \in \mathcal{X}$.

The convergence of IBU has been studied in [33, 34]. For a given set of observed locations, the limiting estimate $\hat{\pi}_{\mathcal{X}} = \lim_{r \to \infty} \theta_r$ is well-defined by the privacy mechanism in use, $C$, and the empirical distribution of the noisy locations, $q$. We will functionally denote $\hat{\pi}_{\mathcal{X}}$ as IBU($q, C$).

**DEFINITION 2.3.3 (Earth mover's distance [35]).** Let $\pi_1$ and $\pi_2$ be PMFs defined over a discrete space of locations $\mathcal{X}$. For a metric $d: \mathcal{X}^2 \to \mathbb{R}_{\ge 0}$, the earth mover's distance (EMD) (aka the Kantorovich-Wasserstein metric) is defined as

$$EMD(\pi_1, \pi_2) = \min_{\mu \in \Pi(\pi_1, \pi_2)} \sum_{x,y} \mu(x,y)d(x,y)$$

where $\Pi(\pi_1, \pi_2)$ is the set of all joint distributions over $\mathcal{X}^2$ such that for any $\eta \in \Pi(\pi_1, \pi_2)$, $\sum_{x \in \mathcal{X}} \eta(x_0, x) = \pi_1(x_0)$ and $\sum_{x \in \mathcal{X}} \eta(x, x_0) = \pi_2(x)$ for every $x_0 \in \mathcal{X}$.

EMD is considered a canonical way to lift a distance on a certain domain to a distance between distributions on the same domain.

**DEFINITION 2.3.4 (Statistical utility).** Let $C$ be a privacy mechanism that obfuscates data on the discrete space $\mathcal{X}$. Let $\pi_{\mathcal{X}}$ be the PMF of the original locations and let $\hat{\pi}_{\mathcal{X}}$ be its estimate by IBU. Then we define the statistical utility of the mechanism $C$ as EMD($\hat{\pi}_{\mathcal{X}}, \pi_{\mathcal{X}}$).
Part II

Location privacy
"If self is a location, so is love."

– Seamus Heaney, *The Aerodrome*
3

PRIVIC: A privacy-preserving method for
incremental collection of location data

**3.1 Introduction**

As the need and development of various kinds of research and analysis using personal data are becoming more and more significant, the risk of privacy violations of sensitive information of the data owners is also increasing manifold. One of the most successful proposals to address the issue of privacy protection is differential privacy (DP) [13, 14], a mathematical property that makes it difficult for an attacker to detect the presence of a record in a dataset. This is typically achieved by answering queries performed on the dataset in a (controlled) noisy fashion. Lately, the local variant of differential privacy (LDP) [23] has gained popularity due to the fact that the noise is applied at the data owner's end without needing a trusted curator. LDP is particularly suitable for situations where a data owner is a user who communicates her personal data in exchange for some service. One such scenario is the use of location-based services (LBS), where a user typically sends her location in order to obtain information like the shortest path to a destination, nearby points of interest, traffic information, etc. The security and the convenience of implementing the local model directly on a user's device (tablets, smartphones, etc.) make LDP very appealing.

Typically, in exchange for their service, providers incrementally collect their users' data and then make them available to other parties which process them to provide useful statistics to companies and institutions. Obviously, the statistical precision of the collected data is essential for the quality of the analytics performed (statistical utility). However, injecting noise locally
into the data to protect the privacy of the users usually has a negative effect on the statistical utility. Additionally, the noise degrades the *quality of service* (QoS) as well, since, obviously, the service results from the elaboration of the information received.

Substantial research has been done to address the privacy-utility trade-off in the context of DP. In LDP, the primary focus has been to optimize the utility from the data collector's perspective, i.e., devising mechanisms and post-processing methods that would allow deriving the most accurate statistics from the collection of the noisy data [23, 36]. In contrast, in domains such as location privacy, the focus usually has been on optimizing the QoS, i.e., the utility from the point of view of the users. In particular, this is the case for the framework proposed by Shokri et al. [37, 38].

We argue that it is important to meet the interest of all parties involved, and hence to consider both kinds of utility at the same time. Hence, the first goal of this paper is to develop a *location-privacy preserving mechanism (LPPM)* that, in addition to providing formal location-privacy guarantees, preserves as much as possible *both* the statistical utility and the QoS.

One may think that statistical utility and QoS are aligned since they both benefit from preserving as much original information as possible under the privacy constraint. However, this is not true in general: the optimization of statistical utility does not necessarily imply a significant improvement in the QoS, nor vice-versa. A counterexample is provided by Example 3.6.1 in Section 3.6. Hence, the preservation of both statistical utility and QoS is trickier than it may appear at first sight.

*Geo-indistinguishability (geo-ind)* [16], one of the most popular and widely used approaches to protect location-privacy, essentially obfuscates locations based on the distance between them. This idea works particularly well for protecting the precision of the location as it ensures that an attacker would not be able to differentiate between points that are close on the map by observing the reported noisy location. At the same time, it does not inject an enormous amount of noise that would be necessary to make far-away locations indistinguishable. Moreover, geo-ind has been shown to formally satisfy the basic sequential compositionality theorem [39], just like DP and its local variant. Although this approach of distance-based obfuscation seems enticing at a first glance, one of the issues it poses is that it may leave the geo-spatially isolated locations vulnerable, i.e., identifiable despite being formally geo-indistinguishable [40]. To improve the situation, [40] introduced the notion of *elastic distinguishability metrics*, which essentially leads to injecting more noise when the location to protect is isolated.

The *Blahut-Arimoto algorithm* (BA) [41, 42] from rate-distortion theory (a branch of information theory) Pareto-optimizes the trade-off between *mutual information (MI)* and average distortion. This property is appealing in the context of privacy because MI is often considered a measure of information leakage and average distortion is a commonly used metric for quantifying QoS. Moreover, BA was proven to satisfy geo-ind in [43] opening a door to study it as a potential LPPM. In this paper, we start off by exploring the privacy-preserving properties of BA and comparing them with those of the *Laplace mechanism* (LAP) [16] which is considered as the state-of-the-art mechanism for geo-ind. We show that, besides geo-ind, BA provides an elastic distinguishability metric and, hence, protects even the most isolated points in the map, unlike
LAP. We then examine the statistical utility, focusing on the estimation of the most general statistical information, namely the distribution of the original location data (true distribution). The "best" estimation is known in statistics as the *maximum likelihood estimation* (MLE), and can be computed using the *iterative Bayesian update* (IBU) [33], an instance of the *expectation maximization* (EM) method. We discover a duality between BA and IBU, which in our opinion is quite intriguing, because BA and IBU were developed in different contexts, using different concepts and metrics, and for completely different purposes. We prove experimentally that the statistical utility of BA is very good, i.e., the MLE is very close to the true distribution. We conjecture that this is probably due to the duality between the mechanism that injects the noise (BA) and the one that de-noises the noisy data (IBU). In any case, the experiments show that the statistical utility of BA outperforms that of LAP for high levels of privacy, eventually becoming comparable as the level of privacy decreases.

One important point to note is that BA requires the knowledge of the original distribution to provide the optimal mechanism. When it is fed with only an approximation of the distribution, it only provides an approximated result. We acknowledge that the distribution of the original data is usually off-limits and, even when available, it typically gets outdated over time. In any case, we can soundly assume that it is not available because it is essentially the reason for collecting the data. Hence we have a vicious circle: we want to collect data in a privacy-friendly fashion to estimate the original distribution while wanting to use a privacy mechanism that requires knowing a good approximation of the original distribution. Motivated by this dilemma, we propose PRIVIC, an incremental data collection method providing extensive privacy protection for the users of LBS's, while retaining a high utility for both them and the service providers, and ensuring that both parties, acting in their best interest, would benefit from the end mechanism.

Finally, we prove formally the convergence of PRIVIC to the true distribution, and illustrate empirically the privacy-utility trade-off of our method. The experiments also demonstrate the efficacy of combining BA and IBU, in that the estimation of the original distribution is very accurate, especially when measured using a notion of distance between distributions compatible with the ground distance used to measure the QoS (e.g., the Earth Mover's distance). All the experiments were performed using real location data from the Gowalla dataset for Paris and San Francisco.

## Contributions

The key contributions in this chapter are:

1. We show, analytically and with experiments on real datasets, that the BA mechanism, in addition to geo-ind, provides an elastic distinguishability metric. As such, it protects the privacy of isolated locations, which the standard LAP for geo-ind fails at.

2. We prove that BA produces an invertible mechanism, which means that the MLE is unique. This is crucial to prove that the IBU always converges to the true distribution and that, therefore, we can get a good statistical utility.
3. We establish a duality between BA and IBU, thus demonstrating a connection between rate-distortion theory and the expectation-maximization method from statistics.

4. We show experimentally that BA provides a better statistical utility than LAP for high levels of privacy, eventually becoming comparable as the level of privacy decreases.

5. Since the construction of the optimal BA requires precise knowledge of the true distribution, we propose an iterative method (PRIVIC) that alternates between BA and IBU, thus getting a better and better estimation of the true distribution as more (noisy) data get collected. We show, both formally and with experiments on real location datasets, that PRIVIC converges to the true distribution. In summary, PRIVIC produces a geo-indistinguishable LPPM with an elastic distinguishability metric, which optimizes the trade-off with the QoS and provides high statistical utility.

6. We investigate the effect on the privacy guarantees of our method by considering adversarial users who report their locations falsely to compromise the privacy of the isolated locations in the map.

## 3.2 Technical preliminaries

Aside from the formal guarantees of DP and its variants as introduced in Section 2.1, in this chapter, we consider an additional notion of quantifying and measuring data privacy from an information theoretical perspective using mutual information (MI). As such, information theoretical MI has often been explored and used in the context of privacy (and security) in the literature and we have discussed some of the key works in this area in Section 3.3.

**DEFINITION 3.2.1 (Mutual information [44]).** Let $(X, Y)$ be a pair of random variables defined over the discrete space $X \times Y$ such that $\mu$ is the joint probability mass function (PMF) of $X$ and $Y$, and $p_X$ and $p_Y$ are the marginal PMFs of $X$ and $Y$, respectively, and $p_{X|Y}$ is the conditional probability of $X$ given $Y$. Then the (Shannon) entropy of $X$, $H(X)$, is defined as $H(X) = - \sum_{x \in \mathcal{X}} p_X(x) \log p_X(x)$. The residual entropy of $X$ given $Y$ is defined as $H(X|Y) = \sum_{y \in \mathcal{Y}} p_Y(y)H(X|Y = y) = - \sum_{y \in \mathcal{Y}} p_Y(y) \sum_{x \in \mathcal{X}} p_{X|Y}(x|y) \log p_{X|Y}(x|y)$, and, finally, the mutual information (MI) is given by:

$$I(X|Y) = H(X) - H(X|Y) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \mu(x, y) \log \frac{\mu(x, y)}{p_X(x)p_Y(y)} \quad (3.1)$$

In addition to the concept of statistical utility for the service providers as introduced in Chapter 2.3, in this chapter, we also consider the Quality of Service (QoS) as a measure of utility for the users of location-based services.
**DEFINITION 3.2.2 (Quality of Service).** For discrete spaces, $\mathcal{X}$ and $\mathcal{Y}$, let $d: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$ be any distortion metric (a generalization of the notion of distance). Let $\mathcal{X}$ be a random variable on $\mathcal{X}$ with PMF $p_{\mathcal{X}}$ and $\mathcal{C}$ be any randomizing mechanism where $C_{\mathcal{X}\mathcal{Y}}$ is the probability of $\mathcal{X}$ being mapped to $\mathcal{Y}$ by $\mathcal{C}$. We define the *quality of service (QoS)* of $\mathcal{X}$ for $\mathcal{C}$ as the *average distortion w.r.t. $d$, given as:*

$$ AvgD(X, C, d) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p_{\mathcal{X}}(x) C_{\mathcal{X}y} d(x, y) $$

Now we introduce the *Blahut-Arimoto algorithm (BA)* [41, 42] that was initially developed in 1972 to present an iterative method for optimizing the information-theoretical channel capacity w.r.t. a given constraint on the average distortion. In this work, we shall resort to BA to optimize the information theoretical notion of privacy (Definition 3.2.1) and the QoS (Definition 3.2.2) of the users sharing their locations and explore its extensive location privacy-preserving properties.

**DEFINITION 3.2.3 (Blahut-Arimoto algorithm [41, 42]).** Let $\mathcal{X}$ be a random variable on the discrete space $\mathcal{X}$ with PMF $\pi_{\mathcal{X}}$ and $\mathcal{C}(\mathcal{X}, \mathcal{Y})$ be the space of all mechanisms encoding $\mathcal{X}$ to $\mathcal{Y}$. For a distortion $d: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$ and fixed $d^* \in \mathbb{R}^+$, we wish to find the mechanism $\hat{C} \in \mathcal{C}(\mathcal{X}, \mathcal{Y})$ that minimizes MI given the bound $d^*$ on distortion:

$$ \hat{C} = \underset{C \in \mathcal{C}(\mathcal{X}, \mathcal{Y})}{\operatorname{argmin}} I(X|Y_{\mathcal{X},C}) \\ \text{AvgD}(X,C,d) \le d^* $$

where, for any $C \in \mathcal{C}(\mathcal{X}, \mathcal{Y})$, $Y_{\mathcal{X},C}$ is the random variable on $\mathcal{Y}$ denoting the output of the encoding of $\mathcal{X}$. The *Blahut-Arimoto algorithm (BA)* provides an iterative method to construct $\hat{C}$ as follows:

1. Start with any full-support PMF $c_0$ on $\mathcal{X}$ and any $C^{(0)}$.

2. Iterate:

$$ C_{\mathcal{X}\mathcal{Y}}^{(t+1)} = \frac{c_t(y) \exp\{-\beta d(x, y)\}}{\sum_{z \in \mathcal{Y}} c_t(z) \exp\{-\beta d(x, z)\}} \quad (3.2) $$

$$ c_{t+1}(y) = \sum_{x \in \mathcal{X}} \pi_{\mathcal{X}}(x) C_{\mathcal{X}y}^{(t+1)} \quad (3.3) $$

where $\beta > 0$ is the negative of the slope of the *rate-distortion function* $RD(X, d^*) = \min_{C \in \mathcal{C}(\mathcal{X}, \mathcal{Y})} I(X|Y_{\mathcal{X},C})$ under $AvgD(X, C, d) \le d^*$. We call $\beta$ the *loss parameter*, capturing the role of $d^*$ in BA.

**REMARK 3.2.1.** The equations (3.2) and (3.3) above define two transformations $\mathcal{F}: \mathcal{D}(\mathcal{X}) \to \mathcal{C}(\mathcal{X}, \mathcal{Y})$ and $\mathcal{G}: \mathcal{C}(\mathcal{X}, \mathcal{Y}) \to \mathcal{D}(\mathcal{X})$, where $\mathcal{D}(\mathcal{X})$ is the space of distributions on $\mathcal{X}$, so that $C^{(t+1)} = \mathcal{F}(c_t)$ and $c_{t+1} = \mathcal{G}(C^{(t+1)})$.

**REMARK 3.2.2.** In [45], Csiszár proved the convergence of BA when $\mathcal{X}$ is finite. The limit $\lim_{n \to \infty} (\mathcal{F} \circ \mathcal{G})^n(C^{(0)})$ is the optimal mechanism $\hat{C}$ (parametrized by $\beta$), and it is uniquely determined by the prior $\pi_{\mathcal{X}}$ and by the initial PMF $c_0$. Note
that $\hat{C}$ is a fixpoint of $\mathcal{F} \circ \mathcal{G}$, i.e. $\hat{C} = (\mathcal{F} \circ \mathcal{G})(\hat{C})$, and that $\hat{c} = \mathcal{G}(\hat{C})$ is a fixpoint of $\mathcal{G} \circ \mathcal{F}$.

**REMARK 3.2.3.** In [43], Oya et al. proved that, when $d$ is the Euclidean metric, the mechanism $\hat{C}$ obtained from BA with loss parameter $\beta$ satisfies $2\beta$-geo-ind.

Finally, to conclude the technical preliminaries relevant to this chapter, we recall a generalization of IBU from the literature that we use in this work. Generalized IBU (GIBU) [46] applies IBU in parallel to several empirical distributions derived from the application of (possibly different) obfuscation mechanisms to various sets of samples from the same distribution.

**DEFINITION 3.2.4 (Generalized iterative Bayesian update [46]).**

Let $\mathbf{x}^{(1)}, \dots, \mathbf{x}^{(N)}$, with $\mathbf{x}^{(t)} = (x_1^{(t)}, \dots, x_n^{(t)})$ for every $t \in \{1, \dots, N\}$, be $N$ datasets s.t. the entries $x_i^{(t)}$ for each $i \in \{1, \dots, n\}$ are i.i.d. samples from the discrete space $\mathcal{X}$ following the probability distribution $\pi_{\mathcal{X}}$. Let $C^{(1)}, \dots, C^{(N)}$ be $N$ privacy mechanisms that locally obfuscate points from $\mathcal{X}$ to $\mathcal{Y}$ such that the mechanism $C^{(t)}$ is applied to the dataset $\mathbf{x}^{(t)}$ and $C_{xy}^{(t)} = \mathbb{P}[y|x]$ for all $x, y \in \mathcal{X}, \mathcal{Y}$ and $i \in \{1, \dots, N\}$. Denoting the random variable of the output when $x_i^{(t)}$ is obfuscated with $C^{(t)}$ as $Y_i^{(t)}$, let $(y_1^{(t)}, \dots, y_n^{(t)})$ be a realisation of $(Y_1^{(t)}, \dots, Y_n^{(t)})$ for every $t \in \{1, \dots, N\}$.

Let $\mathcal{G} = (C^{(1)} \dots C^{(N)})$ be referred to as the combined mechanism a.k.a. the output probability matrix satisfying:

$$ \mathcal{G}(x, y_i^{(t)}) = \mathbb{P}[y_i^{(t)} | x] = C_{x, y_i^{(t)}}^{(t)} \\ \forall x \in \mathcal{X}, i \in \{1, \dots, n\}. $$

GIBU estimates $\pi_{\mathcal{X}}$ by converging to the maximum likelihood estimate (MLE) of $\pi_{\mathcal{X}}$ with the knowledge of the noisy data and the obfuscating channels. GIBU works as follows:

1. Start with any full-support PMF $\theta_0$ on $\mathcal{X}$.

2. Iterate $\theta_{r+1}(x) = \frac{1}{N_n} \sum_{t=1}^{N} \sum_{i=1}^{n} \frac{\theta_r(x) \mathcal{G}(x, y_i^{(t)})}{\sum_{z \in \mathcal{X}} \theta_r(z) \mathcal{G}(z, y_i^{(t)})}$ for all $x \in \mathcal{X}$.

Setting $\hat{\pi}_{\mathcal{X}} = \lim_{r \to \infty} \theta_r$ and $\mathbf{y}^t = (y_1^{(t)}, \dots, y_n^{(t)})$, let $\hat{\pi}_{\mathcal{X}}$ (the MLE of the prior obtained with GIBU) be functionally denoted by:

$$ \text{GIBU}((C^{(1)}, \mathbf{y}^{(1)}), \dots, (C^{(N)}, \mathbf{y}^{(N)})). $$

In the context of the location-privacy, as addressed in this work, we obfuscate the original locations to points in the same space and, hence, in the rest of the chapter we consider the spaces of the secrets and the noisy locations to be the same, i.e., $\mathcal{X} = \mathcal{Y}$.
## 3.3 Related Work

The trade-off between privacy and utility has been widely studied in the literature [47, 48]. Optimization techniques for DP and utility for statistical databases have been analyzed by the community from various perspectives [49–51]. There have been works focusing on devising privacy mechanisms that are optimal to limit the privacy risk against Bayesian inference attacks while maximizing the utility [37, 38]. In [43], Oya et al. examine an optimal LPPM w.r.t. various privacy and utility metrics for the user.

In [52], Oya et al. consider the optimal LPPM proposed by Shokri et al. in [37] which maximizes a notion of privacy (the adversarial error) under some bound on the QoS. The construction of the optimal LPPM requires the knowledge of the original distribution, and [52] uses the EM method to estimate it and design blank-slate models empirically shown to outperform the traditional hardwired models. However, a problem with their approach is that there may exist LPPMs that are optimal in the sense of [37], but with no statistical utility, see Example 3.6.1 in Section 3.6. Furthermore, for the mechanisms considered in [52] the EM method may fail to converge to the true distribution. Indeed, [34] points out various mistakes in the results of [33], on which [52] intrinsically relies to prove the convergence of their method.

[53] proposed a method for generating privacy mechanisms that tend to minimize mutual information using a machine learning based approach. However, this work assumes the knowledge of the exact prior from the beginning, unlike ours. Moreover, [53] does not provide formal guarantees for location-privacy (e.g., geo-ind) which is one of the main aspects captured by our work. In [54], Zhang et al. consider the Blahut-Arimoto algorithm in the context of location-privacy. However, their proposed method also requires the knowledge of the prior distribution to construct the LPPM. Additionally, [54] focuses on measuring privacy for the trace of a single user. On the contrary, our notion of privacy assumes the collection of single check-ins (or check-ins separated in time) by a set of users.

The Laplace mechanism has been rigorously studied in the literature in various scenarios as the cutting-edge standard to achieve geo-ind [16, 39, 55] and has been proven to be optimal for one-dimensional data w.r.t. Bayesian utility [25]. Despite its wide popularity, it has been recently criticized due to its limitation to protect geo-spatially isolated points from being identified by adversaries [40]. The authors of [40] addressed this concern by proposing the idea of *elastic distinguishability metrics*.

Our work also considers mutual information (MI) as an additional privacy guarantee. MI and its closely related variants (e.g. conditional entropy) have been shown to nurture a compatible relationship with DP [56]. [57] has provided an operational interpretation of MI in terms of an attacker model. MI essentially measures the correlation between observations and secrets, and its use as a privacy metric is widespread in the literature. Some key examples are: gauging anonymity [58, 59], estimating privacy in training machine learning models with a typical cross-entropy loss function [53, 60–62], and assessing location-privacy [43].

Alongside the widespread interest in studying MI as an information theoretical notion of privacy by the community, some researchers have strongly criticized the use of Shannon entropy
and MI as measures of privacy (e.g., [63]). We do not take sides in this controversy: for us (and specifically in this work), MI is only a means to construct a mechanism that provides geo-ind under an elastic metric, which is our reference privacy notion.

A popular choice of utility metric for the users is the *average distortion*, which quantifies the expected quality loss of the service due to the noise induced by the mechanism. Such a metric has gained the spotlight in the community [16, 37, 64–66] due to its intuitive and simple nature. On the other hand, a standard notion of statistical utility for the data consumer is the precision of the estimation of the distribution on the original data from that of the noisy data. Iterative Bayesian update [31, 33] provides one of the most flexible and powerful estimation techniques and has recently become in the focus of the community [34, 46].

Incremental and privacy-friendly data collection has been explored both in the context of *k*-anonymity [67–69] and DP [70, 71]. However, to the best of our knowledge, the problem of providing a rather robust privacy guarantee while preserving utility for both data owners and data consumers has not been addressed by the community so far.

## 3.4 Location-privacy with the Blahut-Arimoto algorithm

Definition 3.2.3 shows that the BA mechanism optimizes between MI and average distortion, which is a standard choice for measuring QoS. Furthermore, Remark 3.2.3 formally links the mechanism produced by BA with geo-ind, which is our reference privacy notion.

In this section, we investigate the privacy protection offered by BA beyond geo-ind, study the statistical utility it renders, and compare it with LAP, the canonical mechanism for geo-ind.

### 3.4.1 Elastic location-privacy with BA

One of the concerns harboured by geo-ind is that it treats the space in a uniform way, thus making isolated locations vulnerable to an attacker that knows the prior distribution. This issue has been raised and addressed by Chatzikokolakis et al. in [40] where the authors introduce a variant of LAP based on an *elastic distinguishability metrics*, which they refer to as *elastic mechanisms*. Such mechanisms obfuscate locations not only by considering the Euclidean distance between them but also by taking into account an abstract attribute of the reported location, called *mass*, which is a parameter of the definition.

Formally, if $\mathcal{R}_{\text{elas}}$ is an elastic mechanism with privacy parameter $\varepsilon$ defined on $\mathcal{X}$, then, for all $x, y \in \mathcal{X}$, $\mathcal{R}_{\text{elas}}$ must satisfy:

$$ \mathbb{P}[\mathcal{R}_{\text{elas}}(x) = y] \propto \exp\{-\varepsilon d_{\text{E}}(x, y)\} \quad (3.4) $$

$$ \mathbb{P}[\mathcal{R}_{\text{elas}}(x) = y] \propto q(y) \quad (3.5) $$

where $q$ is the probability distribution of the reported locations.
Note that Equations 3.4 and 3.5 characterize the properties of an elastic mechanism $\mathcal{R}_{\text{elas}}$, but they do not define what $\mathcal{R}_{\text{elas}}$ exactly is, as a function. In fact, as a definition, Equation 3.5 would be circular, since it uses the probability mass $q$ generated by $\mathcal{R}_{\text{elas}}$ without knowing what $\mathcal{R}_{\text{elas}}$ is. As we will see, BA solves this problem by constructing the mechanism $\mathcal{R}_{\text{elas}}$ as a fix-point of a recursive process starting from a uniform output distribution $q$. (To be precise the process is mutually recursive, alternating the generation of a new mechanism and a new output distribution, that, in turn, is fed into BA to generate the mechanism at the next step.)

$\mathcal{R}_{\text{elas}}$, unlike LAP, protects a point in a densely populated area (e.g. city) and a geo-spatially isolated point (e.g. island) differently by considering not only the ground distance between the true and the reported locations but also the mass of the reported location. The exact mechanism depends of course on how we define the notion of mass. A natural way, and the most meaningful from the privacy point of view, is to set the mass of $y$ to be the probability to be reported (from any true location $x$). Under this definition, the interpretation of (3.5) is in the spirit of obtaining privacy by ensuring that the set of possible true locations (given the reported one) is large. In other words, given a true location $x$, we tend to report with higher probability those locations $y$ that are reported with high probability from other locations as well so that it becomes harder to re-identify $x$ as the original one. Note that this property is not incompatible with the geo-ind guarantee. However, LAP does not provide it.

Obviously, the definition of mass as the probability to be reported would be circular, because it would depend on the mechanism, which in turn is defined in terms of the mass. The authors of [40] do not explain how this mechanism could be constructed. Fortunately, the following theorem shows that an elastic mechanism of this kind can be constructed using BA. The proof is provided in Appendix A.

**THEOREM 3.1.** The privacy mechanism generated by BA produces an elastic location-privacy mechanism.

Note also that there can be many mechanisms satisfying (3.4) and (3.5) (also with the mass interpreted as probability). The one produced by the BA is the mechanism that offers the best QoS among these. Finally, a consequence of the connection with BA is that it provides an understanding of the elastic mechanism in terms of information theory and of the attacker illustrated in the previous section.

## Experimental validation

Having furnished the theoretical foundation, we now enable ourselves to empirically validate that BA, indeed, satisfies the properties of the elastic mechanism unlike LAP, its state-of-the-art geo-indistinguishable counterpart. We perform experiments using real location data from the Gowalla dataset [72, 73]. We consider 10,078 Gowalla check-ins from a central part of Paris bounded by latitudes (48.8286, 48.8798) and longitudes (2.2855, 2.3909) covering an area of $8\text{Km} \times 6\text{Km}$ discretized with a $16 \times 12$ grid.

In order to demonstrate the property of an elastic mechanism, we artificially introduced an
“island” amidst the locations in Paris by choosing a grid A in a low-density area of the dataset (in the south-west region), assigning the probability mass of the grids around A to 0, and dumping this cumulative mass from the surrounding region to A, ensuring that the sum of the probability masses of all the grids remains to be 1. We call A as a *vulnerable location* in the map as it is isolated from the crowded area. To visualize the elastic behaviour of the mechanisms for locations in crowded regions, we consider another grid B in the central part of the map which has a high probability mass and has a highly populated surrounding – we refer to such a grid B as a *strong location* in the map. Figure 3.1 illustrates the selection of vulnerable and strong locations in the Paris dataset.

<figure><img src="image_4.png" /><figcaption>**Figure 3.2:** Distribution of privatizing the vulnerable and the strong locations for different levels of privacy. Top-down, the rows illustrate the results for $\epsilon$ = 0.4, 1.2, 1.6, 2, respectively.</figcaption></figure>

For the mechanism derived from BA with a loss parameter $\beta$, we know, by Remark 3.2.3, that the privacy parameter $\epsilon$ is $2\beta$, which we use to tune the privacy level of LAP in order to compare the two mechanisms under the same level of geo-ind. Figure 3.2 illustrates the probability distribution of reporting a privatized point on the map by obfuscating the vulnerable and the strong locations with different levels of geo-ind – we vary the value of $\epsilon$ to be 0.4, 1.2, 1.6, 2.

By comparing with the distribution of the true locations in Paris given by Figure 3.1, we observe that when the value of $\epsilon$ is low (privacy is high), the reported location with BA is likely to be mapped to a nearby densely populated place. For example, with $\epsilon$ = 0.2, the highest level
of privacy considered in the experiments, the location reported by BA will most probably be
around the most crowded region of Paris. As $\epsilon$ increases, the location most likely to be reported
by BA systematically moves to a densely populated region closer and closer to the true vulnerable
location. LAP, on the other hand, always obfuscates every location around its true position in
the map – varying the value of $\epsilon$ changes the spread of the distribution around the true location.
As explained in the introduction, this might be problematic as the vulnerable location is known
to be isolated and, hence, even being reported somewhere nearby would potentially result in its
re-identification.

<figure><img src="image_5.png" /><figcaption>**Figure 3.1:** Gowalla check-in locations in Paris with an artificially planted vulnerable point, A, in isolation, and a strong point, B, in a crowded area.</figcaption></figure>

For example, we would like to highlight
the setting of $\epsilon = 1.6$ for the vulnerable lo-
cation to show that the distribution of the lo-
cation reported by LAP is almost completely
around the true vulnerable point covering an
area that is deserted, i.e., there is no realis-
tic chance of someone being located in that
region. Thus, despite providing formal 1.6-
geo-ind, LAP fails to protect such a vulnerable
location from being potentially identified. BA,
on the other hand, does the job quite well, ad-
hering to the principles of the elastic mecha-
nism – it distributes the reported location in
the crowded areas nearby providing a sense
of camouflage amidst the many possibilities,
in addition to 1.6-geo-ind.

In the case of privatizing the strong loca-

tion, Figure 3.2b shows that both BA and LAP behave similarly by concealing the point around its true position. This would not give rise to a similar issue as for the vulnerable location because, by definition, the strong location *B* is already positioned in a highly dense region of the map and, hence, being privatized, it will still remain among the crowd with a high probability.

Focusing on the utility of individual users, we note that due to theories from Nash equi-
librium [74] and Hotelling's spatial competition [75], a huge fraction of the typical points of
interest (POIs) like cinemas, theatres, restaurants, retails, etc. lie in crowded areas syncing with
the distribution of population. Therefore, for an isolated point in the map that is located in
some extremely unpopulated area (e.g. some forest or island far from the city), the closest POI
is usually going to be in the nearest urban region, i.e., a region on the map with a high density
of population. Suppose A is one such isolated location and let A<sub>BA</sub> and A<sub>LAP</sub> be the reported lo-
cations for A obfuscated with BA and LAP, respectively. Due to the elastic property of BA, A<sub>BA</sub> is
likely to be at a nearby crowded location to A, while A<sub>LAP</sub> is likely to be around the true location
A. Let P<sub>BA</sub> and P<sub>LAP</sub> be the nearest POIs from the reported locations A<sub>BA</sub> and A<sub>LAP</sub>, respectively.
The most likely scenario is that P<sub>BA</sub> and P<sub>LAP</sub> are almost at a similar place under the assumption
that typical POIs follow the distribution of the crowd and, therefore, a vulnerable user has to
travel a similar distance from their true position in both the cases, except that under LAP, the privacy of A will be compromised much more than that under BA.

3.4.2 Statistical utility: BA vs LAP

<figure><img src="image_6.png" /><figcaption>**Figure 3.3:** Statistical utility in terms of earth mover's distance (EMD) between the true and the estimated distributions for locations in Paris and San Francisco, under BA and LAP.</figcaption></figure>

Now we proceed to empirically compare the statistical utility of BA and LAP by performing experiments on the locations obtained from the Gowalla dataset for two different cities: Paris and San Francisco. In addition to the same setting for the Gowalla check-ins in Paris as considered in the experiments of Section 3.4.1, here we also test for 123,025 check-in locations from the Gowalla dataset in a northern part of San Francisco bounded by latitudes (37.7228, 37.7946) and longitudes (-122.5153, -122.3789) covering an area of 12Km×8Km discretized with a 24×17 grid. The locations were privatized with BA and LAP under varying levels of privacy – the loss parameter, $\beta$, for BA ranged from 0.2 to 5.0, which implies that the value of the geo-ind parameter, $\varepsilon$, ranged from 0.4 (very high level of privacy) to 10.0 (almost no privacy). To account for the randomness in the process of generating the sanitized locations, 5 simulations were run for each value of the privacy parameter for obfuscating every location in both datasets.

Figure 3.3 reveals that BA possesses a significantly better statistical utility than LAP for a high level of privacy (for $\beta \in (0.4, 1.4]$ and $\beta \in (0, 1)$, i.e., $\varepsilon$ up to 2.8 and 2, in Paris and San Francisco datasets, respectively). As the level of privacy decreases, the EMD of BA becomes worse than that of LAP. We conjecture that this is the price to pay for the added privacy provided by the elasticity of the mechanism. Eventually, the EMD between the true and the estimated PMFs converge to 0 in both mechanisms, as we would expect, fostering the maximum possible statistical utility with, practically, no privacy guarantee.

Summarizing the results from Sections 3.4.1 and 3.4.2, we can establish that:
<figure><img src="image_7.png" /><figcaption>Figure 3.4: Illustration of the duality between BA and IBU.</figcaption></figure>

* in addition to providing a formal geo-ind guarantee, BA also gives an LPPM with an elastic distinguishability metric to enhance the privacy of vulnerable locations.

* BA optimizes the trade-off between QoS and MI.

* the statistical utility for high levels of privacy is significantly better for BA than LAP.

Therefore, we conclude that BA is a key contender for providing a comprehensive notion of location-privacy while preserving the utility of the data for both the users and the service providers.

## 3.5 Duality between IBU and BA

We now explore a relationship between BA and IBU which we found rather intriguing. For a metric space $(X, d)$, let $X$ be a random variable on $X$ with PMF $\pi_X$. Recalling the iteration of BA from (3.3) and (3.2):

$$c_t(y) = \sum_{x \in \mathcal{X}} \pi_X(x) C_{xy}^{(t)} \quad \text{and} \quad C_{xy}^{t+1} = \frac{c_t(y) \exp\{-\beta d(x, y)\}}{\sum_{z \in \mathcal{X}} c_t(z) \exp\{-\beta d(x, z)\}}$$

Hence, we obtain:

$$c_{t+1}(y) = \sum_{x \in \mathcal{X}} \pi_X(x) C_{xy}^{(t+1)} = \sum_{x \in \mathcal{X}} \pi_X(x) \frac{c_t(y) \exp\{-\beta d(x, y)\}}{\sum_{z \in \mathcal{X}} c_t(z) \exp\{-\beta d(x, z)\}} \quad (3.6)$$

Comparing it with the iteration of IBU as in Definition 2.3.2, we observe that (3.6) BA is dual to IBU. Indeed, consider an exponential mechanism of the form $C = c \exp\{-\beta d(x, y)\}$. Flipping the roles of $x$ and $y$ in (3.6), and replacing the input distribution $\pi_X$ with the empirical distribution in output to $C$, we obtain the iterative step of IBU.

Due to this duality between BA and IBU (illustrated in Figure 3.4) and taking advantage of the fact that BA converges [45], i.e., $\lim_{t \to \infty} c_t$ exists, we obtain that also IBU converges.
## 3.6 PRIVIC: a privacy-preserving method for incremental data collection

To ensure that the produced mechanism is truly optimal, BA needs a good approximation of the prior distribution. In the beginning, we cannot assume to have such knowledge, but as the service providers incrementally collect data from their users, we can use these data to refine the estimation of the prior and get a better mechanism. These data, however, are obfuscated by the privacy mechanism and, hence, it is not obvious that the estimation of the prior really improves in the process. We show that this is the case, and, summarizing all results obtained for BA so far, we propose a method that facilitates the service providers to incrementally collect data and gradually achieve a high statistical utility with respect to the QoS. We shall refer to our proposed method for PRIVACY-preserving Incremental Collection of location data as PRIVIC.

The goal of PRIVIC is to construct an obfuscation mechanism that guarantees formal geo-ind, acts as an elastic mechanism, and eventually optimizes between MI and QoS, while producing, at the same time, a good estimation of the distribution of the data.

We shall consider locations sampled from a finite space $\mathcal{X} = \{x_1, \dots, x_m\}$. Let the true distribution or true PMF on $\mathcal{X}$ (from which the users' locations are sampled) be $\pi_{\mathcal{X}}$. Note that we do not assume the knowledge of $\pi_{\mathcal{X}}$ in our method. We assume that the new locations are sampled independently from the previous ones. This hypothesis is reasonable if the collection of the new data is enough separated in time from the previous one, otherwise, we would have a potential correlation between samplings due to the possibility that a user sends repeated check-ins from spatially closed locations. In any case, geo-ind, like DP, satisfies the property of sequential compositionality [39], which means that privacy degradation is under control.

In this work, to achieve geo-ind, we shall adhere to the Euclidean metric $d_E$ to measure the ground distance between locations.

PRIVIC proceeds as follows (cf. also Figure 3.5):

1. Set $\theta_0, c_0$ to be the uniform distributions on $\mathcal{X}$, i.e., $\theta_0(x) = c_0(x) = 1/|\mathcal{X}|$ for all $x \in \mathcal{X}$.

2. In step $t \ge 1$:

i) For a fixed the maximum average distortion, set $\hat{C}^{(t)} = \text{BA}(\theta_{t-1}, c_0)$.

ii) Sample a new set of locations $\mathbf{x}^{(t)}$ from the (unknown) true distribution and obfuscate them locally by the mechanism $\hat{C}^{(t)}$ to get $\mathbf{y}^{(t)}$, thus obtaining the empirical distribution of the reported locations $\mathbf{q}_t = \{\mathbf{q}_t(x): x \in \mathcal{X}\}$.

iii) $\mu_t = \text{IBU}(\hat{C}^{(t)}, \theta_{t-1}, \mathbf{q}_t)$.

iv) if $t=1$ then $\theta_t = \mu_t$ else $\theta_t = \mu_t \oplus \theta_{t-1}$ (combination of previous and new estimation proportional to the respective number of samples).

3. $\hat{\pi}_{\mathcal{X}} = \text{GIBU}((\hat{C}^{(1)}, \mathbf{y}^{(1)}), \dots, (\hat{C}^{(N)}, \mathbf{y}^{(N)}))$.
<figure><img src="image_8.png" /><figcaption>**Figure 3.5:** Illustration of the iterative process of PRIVIC</figcaption></figure>

**REMARK 3.6.1.** The initial distribution $\theta_0$ does not need to be a uniform distribution, any fully-supported distribution would suffice for the process to eventually converge to an optimal mechanism. However, starting with a uniform distribution allows us to avoid any bias in the mechanisms produced in the intermediate steps.

**REMARK 3.6.2.** We believe that the last step (3) is not really necessary: The combination of all estimations should already be the MLE of the true distribution, and this is also what we have witnessed in the experiments. However, applying this last step allows us to *formally prove* the convergence to the MLE, using the results for GIBU in [46].

In the practical implementation of PRIVIC, we use the precision parameters $\delta_{\text{BA}}$, $\delta_{\text{IBU}}$, and $\delta_{\text{GIBU}}$ to set the threshold of empirical convergence of BA, IBU, and GIBU, respectively. Let the privacy mechanism generated this way after $N$ iterations, for fixed parameters $c_0$, $\beta$, $\delta_{\text{BA}}$, $\delta_{\text{IBU}}$, and $\delta_{\text{GIBU}}$, be functionally represented as $\hat{C}_{\text{BA}}(\theta_0, N)$.

Concerning statistical utility, it is important to ensure that IBU converges to the true distribution. As a matter of fact, IBU always converges to an MLE but the MLE may not be unique [46]. More precisely, there can be more than one distribution that is the most likely input to the obfuscation mechanism, for a given empirical distribution on the noisy data. Thus, even though IBU converges, it may converge to a distribution different from the true one. This is a problem in
**Algorithm 1: PRIVIC**

**Input:** Loss parameter: $\beta$, No. of iterations: $N$, precision of BA: $\delta_{\text{BA}}$, precision of IBU: $\delta_{\text{IBU}}$, precision of GIBU: $\delta_{\text{GIBU}}$;

**Output:** Optimal channel: $\hat{C}$, Estimation of true PMF: $\hat{\pi}_{\chi}$;

$$ \theta_0(x) \leftarrow 1/|\chi|; $$

$$ c_0 \leftarrow 1/|\chi|; $$

$$ t \leftarrow 0; $$

**while** $t \le N$ **do**

$$ \hat{C}^{(t+1)} = \text{BA}(\theta_t, c_0, \beta, \delta_{\text{BA}}); $$

$$ \mathbf{y}^{(t)} \leftarrow (y_1^{(t)}, \dots, y_n^{(t)}) : \begin{array}{l} \text{New noisy locations reported by users after obfuscating their} \\ \text{newly sampled true locations with } \hat{C}^{(t)}; \end{array} $$

$$ \mathbf{q} \leftarrow \{q(x) : x \in \chi\} : \text{Empirical PMF obtained from } \mathcal{L} \text{ by the service provider;} $$

$$ \mu \leftarrow \text{IBU}(\hat{C}^{(t+1)}, \theta_t, \mathbf{q}, \delta_{\text{IBU}}); $$

if $t=0$ then $\theta_{t+1} \leftarrow \mu$ else $\theta_{t+1} \leftarrow \mu \oplus \theta_t$;

$$ t \leftarrow t + 1; $$

$$ \hat{\pi}_{\chi} \leftarrow \text{GIBU}((\hat{C}^{(1)}, \mathbf{y}^{(1)}), \dots, (\hat{C}^{(N)}, \mathbf{y}^{(N)}), \delta_{\text{GIBU}}); $$

$$ \hat{C} \leftarrow \text{BA}(\hat{\pi}_{\chi}, c_0, \beta, \delta_{\text{BA}}); $$

**Return:** $\hat{C}, \hat{\pi}_{\chi}$

**Algorithm 2: Blahut-Arimoto algorithm (BA)**

**Input:** PMF: $\pi$, initial mechanism: $C^{(0)}$, loss parameter: $\beta$, precision: $\delta_{\text{BA}}$;

**Output:** mechanism giving minimum mutual information for maximum avg. distortion encapsulated by $\beta$: $\hat{C}$;

**Function** BA($\pi, c_0, \beta, \delta_{\text{BA}}$):

$t \leftarrow 0;$

**while** $\delta_{\text{BA}} \le |C^{(t)} - C^{(t-1)}|$ **do**

$$ C_{xy}^{(t+1)} \leftarrow \frac{c_t(y) \exp\{-\beta d_E(x, y)\}}{\sum_{z \in \chi} c_t(z) \exp\{-\beta d_E(z, y)\}}; $$

$$ c_{t+1}(y) \leftarrow \sum_{x \in \chi} \pi(x) C_{xy}^{(t+1)}; $$

$$ t \leftarrow t + 1; $$

$$ \hat{C} \leftarrow C^{(t)}; $$

**Return:** $\hat{C}$

the method by Oya et al. in [52] which computes the obfuscation mechanism via the algorithm of Shokri et al. [76]. The resulting mechanism optimizes the trade-off between distortion and a Bayesian notion of privacy, but may not have a unique MLE, as illustrated in the example below. They probably did not realize the problem, because they relied on the flawed results by [33] according to which every mechanism would have a unique MLE.

The following example is a simplified version of the example given in [46] (Sections 3.1 and 3.2.) which was aimed at showing the non-uniqueness of the MLE, and consequent convergence to the wrong distribution, in a more general setting. However, for the scope of our work, a simpler variant suffices.

**EXAMPLE 3.6.1.** Consider three collinear locations, *a*, *b* and *c*, where *b* lies in between *a* and *c* at a unit distance from each of them. Assume that the prior
**Algorithm 3:** iterative Bayesian update (IBU)

**Input:** Privacy mechanism: $C$, Full-support PMF: $\vartheta_0$, empirical PMF from observed data: $\mathbf{q}$, precision: $\delta_{IBU}$;

**Output:** MLE of true PMF: $\theta$;

**Function** IBU($C$, $\vartheta_0$, $\mathbf{q}$, $\delta_{IBU}$):

Set $t \leftarrow 0$;
while $\delta_{IBU} < |\vartheta_t - \vartheta_{t-1}|$ do
  $\vartheta_{t+1}(x) \leftarrow \sum_{y \in \mathcal{X}} \mathbf{q}(y) \frac{C_{xy} \vartheta_t(x)}{\sum_{z \in \mathcal{X}} C_{zy} \vartheta_t(z)}$;
  $t \leftarrow t + 1$
  $\theta \leftarrow \vartheta_t$;
  **Return:** $\theta$;

distribution on these three locations is uniform and that the constraint on the utility is that it should not exceed $2/3$. Then a mechanism that optimizes the QoS in the sense of [76] is the one that maps all locations to $b$. However, this mechanism has no statistical utility, as the $b$'s do not provide any information about the original distribution. Indeed, given $n$ obfuscated locations (i.e., $n$ $b$'s) all distributions on $a$, $b$ and $c$ of the form $k_a/n$, $k_b/n$, $k_c/n$ with $k_a + k_b + k_c = n$, have the same likelihood to be the original one.

Fortunately, our method does not have this problem, because the BA produces an invertible mechanism, and invertibility implies the uniqueness of the MLE [46]. In particular, we are now able to show the convergence of PRIVIC as a whole using the results of [46].

**THEOREM 3.2.** For any $t \ge 1$, the mechanism generated by BA over $\mathcal{X}$ at the $t$'th iteration, seen as a stochastic matrix, is invertible.

*Proof.* In Appendix A.

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

**THEOREM 3.3.** PRIVIC converges to the unique MLE of the true distribution.

*Proof.* In Appendix A.

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

To evaluate the statistical utility of $\hat{C}_{BA}(\theta_0, N)$ (cf. Section 3.7), we will measure the EMD between the true and the estimated PMFs at the end of $N$ iterations of PRIVIC. Thus, the quantity EMD($\hat{\pi}_{\mathcal{X}}, \pi_{\mathcal{X}}$) parameterizes the utility of $\hat{C}_{BA}(\theta_0, N)$ for the service providers. We use the same Euclidean distance as the underlying metric for computing, both, the EMD and the average distortion – this consistency threads together and complements the notion of *utility* of the service providers and that from the sense of the QoS of the users.

## 3.7 Experimental analysis of PRIVIC
In this section, we describe the empirical results obtained by carrying out experiments to illustrate and validate the working of our proposed method. Standard Python packages were used to run the experiments in a MacOS Ventura 13.2.1 environment with an Intel core i9 processor and 32 GB of RAM. Like in the previous experiments to compare the statistical utilities of BA and LAP, as elaborated in Section 3.4.2, we use real locations from the same regions in Paris and San Francisco from the Gowalla dataset [72, 73]. In particular, we consider Gowalla check-ins from (i) a northern part of San Francisco bounded by latitudes (37.7228, 37.7946) and longitudes (-122.5153, -122.3789) covering an area of 12Km×8Km discretized with a 24×17 grid; (ii) a central part of Paris bounded by latitudes (48.8286, 48.8798) and longitudes (2.2855, 2.3909) covering an area of 8Km×6Km discretized with a 16×12 grid. In this setting, we work with 123,108 check-in locations in San Francisco and 10,260 check-in locations in Paris. Figure 3.6a shows the particular points of check-in from Paris and San Francisco and Figure 3.6b highlights their distribution.

<figure><img src="image_11.png" /><figcaption>**Figure 3.6:** (a) visualizes the original locations from Gowalla dataset from Paris and San Francisco. (b) illustrates a heatmap representation of the locations in the two cities to capture the distribution of the data.</figcaption></figure>

<table><caption>**Table 3.1:** Run-time and complexity of BA and IBU in each cycle of PRIVIC</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="2">BA</th><th colspan="2">IBU</th></tr><tr><th>Mean run-time (sec.)</th><th>Complexity</th><th>Mean run-time (sec.)</th><th>Complexity</th></tr></thead><tbody><tr><td>Paris</td><td>3.256</td><td>O(n<sup>2</sup>)</td><td>1.30</td><td>O(n<sup>2</sup>)</td></tr><tr><td>San Francisco</td><td>16.805</td><td>O(n<sup>2</sup>)</td><td>128.192</td><td>O(n<sup>2</sup>)</td></tr></tbody><tfoot><tr><td colspan="5" style="text-align: center;">Framework: MacOS Ventura 13.2.1 with Intel core i9 processor and 32 GB RAM</td></tr></tfoot></table>

We implemented PRIVIC on the locations from Paris and San Francisco separately to judge
its performance on real data with very different priors. In both cases, we ran our mechanism
until it empirically converged. 15 cycles of PRIVIC were required for the Paris dataset where
each cycle comprised 8 iterations of BA until it converged to generate the privacy mechanism
and 10 iterations of IBU until it converged to the MLE of the prior. For the San Francisco dataset,
PRIVIC needed 8 cycles to converge with 5 iterations of BA and IBU each to converge in every
cycle. The complexities and the run-times of BA and IBU are summarised in Table 3.1. In both
cases, we assigned the value of the loss parameter signifying the QoS of the users, $\beta$, to be 0.5
and 1. This was done to test the performance of PRIVIC in estimating the true PMF under two
different levels of privacy. Each experiment was run for 5 rounds of simulation to calibrate the
randomness of the sampling and obfuscation. In each cycle of PRIVIC, across all the settings, BA
was initiated with the uniform marginal $c_0$ and a uniform distribution over the space of locations
as the “starting guess” of the true distribution.

With $\beta = 1$, BA produces a geo-indistinguishable mechanism that injects less local noise than that obtained with $\beta = 0.5$. As a result, PRIVIC obtains a more accurate estimate of the true PMF for the $\beta = 1$ than for $\beta = 0.5$. However, in both cases, the EMD between the true and the estimated distributions is very low, indicating that the PRIVIC mechanism is able to preserve a good level of statistical utility. Moreover, for both Paris and San Francisco, PRIVIC seems to significantly improve its estimation of the true PMF with every iteration until it converges to the MLE. Comparing Figures 3.7 and 3.6b, we see that the estimations of the true distributions of the locations in Paris and San Francisco by IBU under PRIVIC for both the settings of the loss parameter are fairly accurate. However, as we would anticipate, the statistical utility for $\beta = 1$ is better than that for $\beta = 0.5$.

Now we shift our attention to analyze the performance of PRIVIC in preserving the statistical
utility and its long-term behaviour of the two datasets. Figure 3.8 shows us the EMD between the
true distribution of the locations in Paris and its estimate by IBU under PRIVIC in each of its 15
cycles under the two settings of privacy ($\beta$ = 0.5, 1). One of the most crucial observations here
is that the EMD between the true and the estimated PMFs seems to decrease with the number of
iterations and it finally converges, implying that the estimation of PMFs given by PRIVIC seems
to improve at the end of each cycle and, eventually, it converges to the MLE of the prior of the
noisy locations, giving the estimate of the true PMF. This, empirically, suggests the convergence
of the entire method. This is a major difference from the work of [52] which, as we pointed out
before, has the potential of encountering an LPPM which is optimal according to the standards
set by Shokri et al. in [76] but the EM method used to estimate the true distribution would fail to
converge for that mechanism as illustrated in Example 3.6.1. We observe a very similar trend for
the San Francisco dataset. Figure 3.9 shows the statistical utility of the mechanism generated by
PRIVIC under each of its 8 cycles for $\beta$ = 0.5 and $\beta$ = 1. The explicit values of the EMD between
the true and the estimated PMFs on the location data from Paris and San Francisco for both the
settings of the loss parameter can be found in Tables B.1 and B.2 in Appendix B.

In the next part of the experiments, we set ourselves to dissect the trend of the statistical
utility harboured by PRIVIC w.r.t. the level of geo-ind it guarantees. We recall that the higher the
value of $\beta$, the lesser the local noise that is injected into the data, and, hence, the worse will be
<figure><img src="image_12.png" /><figcaption>**Figure 3.7:** Visualization of the estimated true distribution of the locations in Paris ((a) and (b)) and San Francisco ((c) and (d)) by PRIVIC after its convergence; the first column is for $\beta = 0.5$ and the second column is for $\beta = 1$.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>**Figure 3.8:** (a) and (b) show the EMD between the true PMF of the Paris locations and its estimation by PRIVIC in each of its cycle for $\beta = 0.5$ and $\beta = 1$, respectively.</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>**Figure 3.9:** (a) and (b) show the EMD between the true PMF of the San Francisco locations and its estimation by PRIVIC in each of its cycles for $\beta = 0.5$ and $\beta = 1$, respectively.</figcaption></figure>

the statistical utility, staying consistent with our observations in Figure 3.7. We continue working with the location data from Paris and San Francisco obtained from the Gowalla dataset in the same framework as described before. We consider $\beta$ taking the values 0.1, 0.3, 0.5, 0.7, 0.9, 1, and for each value of the loss parameter, we run PRIVIC on both datasets using the same number of iterations as in the previous experiments. We adhere to 5 rounds of simulation for each $\beta$ to account for the randomness generated in the obfuscation process.

<figure><img src="image_15.png" /><figcaption>**Figure 3.10:** (a) and (b) illustrate that EMD between the true and the estimated distributions of the locations in Paris and San Francisco, respectively, after the empirical convergence of PRIVIC for the different values of the loss parameters $\beta$.</figcaption></figure>

Figure 3.10 shows us that the difference between the true and the estimated PMFs under PRIVIC starts by sharply decreasing and then eventually stabilizes with an increase in the value of the loss parameter. In other words, as the intensity of the local noise decreases, we will end
up estimating the unique MLE of the original distribution while optimizing MI and the users'
QoS. Both the location datasets result in a Pareto curve showing a similar trend. This depicts an
improvement of the estimated PMF until it converges to the true distribution. This observation
complements the Pareto-optimality of MI with the maximum average distortion as studied in
*rate-distortion theory* [44], and thus, we empirically weave together the two ends of utility with
the information theoretical notion of privacy under PRIVIC.

Discussion

As a justification for the applicability and the working of our method, in a setting where the ser-
vice providers periodically collect location data from clients, it is reasonable to assume that, over
time, they would like to maximize their utility by accurately approximating the true distribution
of the population for improving their service in various aspects (crowd management, security
enhancement, WLAN hotspot positioning, etc.). BA, in addition to guaranteeing geo-ind, acts
as an elastic location-privacy mechanism and optimizes between MI and the data owners' QoS
when it initiates with the true prior. Therefore, as every iteration of PRIVIC improves the estima-
tion of the original distribution, as seen in Figures 3.3a and 3.3b, which is used as the starting
distribution in its next cycle, the overall privacy protection and its trade-off with QoS of the
users will also improve, motivating the users and the service providers comply with PRIVIC to
act in their best interests and, in turn, engaging them in a positive feedback loop to maximize
the corresponding privacy and utility goals.

**3.8 Vulnerability of PRIVIC**

In this section, we illustrate a potential vulnerability of PRIVIC when a subset of colluded
users (*adversarial users*) intentionally deviate from the correct use of the protocol.

The attack consists in falsely reporting their location in order to alter the estimation of the
true distribution and, consequently, the obfuscation mechanism produced by BA. Specifically, we
study two cases: (i) adversaries reporting a crowded location (*strong location*) and adversaries
reporting an isolated location (*vulnerable location*).

We used the real locations from the Paris dataset with the geo-spatially isolated “island”
(as illustrated by Figure 3.1 presented in Section 3.4) representing a strong and a vulnerable
location in the map denoted by points A and B in the figure, respectively. We performed the
experiments with two different levels of formal geo-indistinguishability (ε = 0.8 and ε = 1.2)
considering different fractions of “adversarial data submissions” (i.e., adversarial users reporting
their locations falsely to compromise the privacy of other users) in each case.

Although, in both cases (i) and (ii), we observed that with an increase in the fraction of
adversaries, the probability mass assigned by BA (used to obfuscate the corresponding points
locally) becomes higher in and around the corresponding reported points, the impact of privacy
differs across both settings. For (i), the obfuscation distribution happens to be weighed heavily
around the true crowded location (point B) by both BA and LAP (as illustrated by Figures 3.2b
<figure><img src="image_16.png" /><figcaption>(a) Obfuscation distribution of a vulnerable location in the map using BA satisfying 0.8-geo-location in the map using BA satisfying 1.2-geo-ind with (left-to-right, top-to-bottom) 0%, 29%, and 34%, and 39% adversarial users, respectively. (b) Obfuscation distribution of the vulnerable location in the map using BA satisfying 1.2-geo-location in the map using BA satisfying 0.8-geo-location with (left-to-right, top-to-bottom) 0%, 10%, 15%, and 20% adversarial users, respectively.</figcaption></figure>

**Figure 3.11:** Effect on the privacy provided by BA to obfuscate the geo-spatially isolated location (Location A as in Figure 3.1) for different fractions of adversarial users who intentionally report their locations falsely under two different levels of formal geo-ind guarantees by BA.

and 3.2a) even without any adversarial users. This trend was seen to continue even when we assumed different levels of adversaries.

However, case (ii) represents a much more serious attack. As the number of adversarial users increases, BA and, in turn, PRIVIC become less potent to be able to protect the privacy of honest users who are genuinely located in an isolated location on the map. We also observe that BA and PRIVIC start behaving more like LAP. In particular, Figures 3.11a and 3.11b illustrate that the obfuscation distribution generated by BA satisfying geo-ind with $\epsilon = 0.8$ and $\epsilon = 1.2$, respectively, of the (non-adversarial) users located in point A assigns more and more weight to and around point A which, as a result, makes them more and more identifiable. This evaluation of the vulnerability of PRIVIC under adversarial data submission essentially exposes a weakness of the elastic distinguishability metric. We plan to address this aspect and aim to make PRIVIC more robust against adversarial users in our future works.
4

A privacy-preserving querying mechanism with
high utility for electric vehicles

**4.1 Introduction**

Air pollution is one of the immediate issues that the world is experiencing [77–79]. In the United Kingdom in 2019, 27% of all greenhouse gas emissions come from transportation, as the largest emitting sector [80–82]. Hence, the transportation industry and academic communities are increasingly interested in developing alternative energy vehicles to reduce emissions. Autotobile manufacturers are introducing a new generation of electric vehicles (EVs) that often employ connected and automated driving functions [83].

EVs are regarded as one of the most promising means of reducing emissions and reliance on fossil fuels. Along with environmental benefits, EVs provide superior energy efficiency to conventional vehicles [84]. As the cost of batteries continues to decrease, the large-scale adoption of EVs is becoming more viable [85]. Despite the advantages and competitive cost, many customers remain concerned about running out of battery power before reaching their destination or waiting for their EVs to charge. The primary obstacles to EV adoption are the availability of chargers and the range that can be travelled on a single charge, often referred to as *range anxiety* in the literature [86].

There has been some recent focus on forecasting how busy the charging stations (CS) are in certain areas to ensure that the EVs can plan their journeys conveniently [87, 88]. However, the existing research in this direction, primarily founded upon machine learning based methods,
does not address the privacy concerns involved in such predictive techniques and does not con-
sider situations where there may arise unprecedented traffic congestion (e.g. due to a one-off
concert or an event). DP has been one of the cutting-edge approaches for protecting the privacy
of personal data while allowing for analysing and exploring its utility. However, as discussed
in Section 2.1, such central DP models possess a risk of a single point of failure and are vul-
nerable to having an adversarial curator. To circumvent the need for such a central and trusted
dependency, LDP was proposed which has been getting a lot of attention lately.

On the other hand, future vehicles are getting more sophisticated in their sensory, onboard
computation, and communication capacities. Furthermore, the emergence of Mobile Edge Com-
puting (MEC) also changes the Intelligent Transportation Systems (ITS) by providing a platform
to assist computationally heavy tasks by offloading the computation to the Edge cloud [89].
This architecture often employs three tiers, with the vehicle on the first, MEC on the second,
and standard cloud services on the third [90]. Figure 4.1 shows the system architecture for the
location privacy framework proposed in this chapter.

ITS provides a platform containing distributed and resource-constrained systems to support
real-time vehicular functions where these functions' efficacy relies on the data shared across
entities. However, the risk of privacy disclosure and tracking increases due to data sharing [91].
Privacy-preserving schemes are developed using established techniques such as group signature,
anonymity, and pseudonymity [92, 93]. However, it is possible to identify privatised data with
adequate background information. Hence, DP approaches have emerged as the gold standard
of data privacy because they provide a formal privacy guarantee independent of a threat actor's
background knowledge and computing capability [94].

As introduced in Section 2.1, geo-ind has been emerging as a gold standard for privacy-
preserving location-based services (LBS) and can be implemented directly on the user's device
(tablet, smartphone, etc.). The fact that the users can control their explicit privacy-protection
level for various LBS makes it very appealing. However, a drawback of injecting noise locally
to the datum is that it deteriorates the QoS due to the lack of accuracy of the data. However,
vehicles are located on the road network under normal circumstances. For vehicular location
queries, the classical geo-ind mechanism may result in publishing unrealistic privatised locations
such as houses, parks, or lakes or may even perturb the real location to a very faraway point
with some probability. Thus, there is a need for an adapted model of geo-ind for vehicular appli-
cations. This chapter proposes a novel privacy model called approximate geo-indistinguishability
(AGeoI), which is based on the notion of geo-ind, by using a discrete road network graph.

Our proposed method, in addition to allowing the EVs to have formal privacy guarantees on
their queries to locate the nearest CS, enables the users to estimate the live occupancy of the CS
efficiently allowing convenient journey planning (e.g., avoid going through a route aiming for a
CS which has a dense crowd of EVs looking for a CS around it).

Contributions

Our key contributions in this chapter are:
1. We present the notion of *approximate geo-indistinguishability (AGeoI)*, a formal standard of location-privacy in a bounded co-domain, by generalising the classical paradigm of geo-ind and adapting it to a graphical environment. We illustrate its applicability by proving that it satisfies the compositionality theorem. Moreover, we show that the truncated Laplace mechanism satisfies AGeoI by deriving the appropriate privacy parameters.

2. We propose a two-fold privacy-preserving navigation method for EVs dynamically querying for CS on road networks – the method protects against threats to individual locations of their queries with formal AGeoI guarantees and we provide protection against adversaries tracing the trajectories of the EVs by interpolating their query locations in an online setting.

3. We perform experiments on real vehicular journey data from San Francisco with real locations of charging stations from the area under two settings of their sparsity in the road network, and show that our method ensures that a very high fraction of EVs enjoys “privacy for free” and that the cost of utility-loss for the EVs is very low compared to the formal gain in privacy.

4. We demonstrate that our method, aside from providing formal location-privacy guarantees, allows the EVs to predict the live occupancy of the charging stations based on the sanitised queries received by the server, enabling the users to conveniently and efficiently plan their journeys.

## 4.2 Related Work

Both corporate and academic communities have recently piqued interest in advancing EVs and charging infrastructure to improve the transportation system's sustainability. Despite the advancements, the EV sector confronts challenges that delay the adoption process, such as range anxiety, an absence of convenient and available charging infrastructure, and waiting time to charge [95, 96]. An offline static map of CS is insufficient to resolve these obstacles since EVs may need to reserve a charging station when a trip is planned or query the available stations based on their battery state. Thus, live vehicular and charging station data is utilised in querying and reservation/scheduling mechanisms [97–99]. Encryption techniques can be used in such mechanisms to prevent external intrusions, but they cannot preserve users' privacy from malicious servers and third-party providers.

Several data types are considered in these mechanisms, including real-time location, intended route, battery level, and station availability, to ensure the drivers are not detoured from their intended route [97, 100]. Although disclosing such information poses privacy concerns for the driver's location and vehicle tracking, the privacy requirements of such mechanisms are not sufficiently studied in the literature. Existing methods for planning charging points for EV journeys are considered mechanisms for confidentiality and integrity, but the drivers' location privacy is regarded as an issue of trust in the third-party service provider [101, 102].

This problem can be addressed by several approaches based on the threat model of the system. Location anonymity is achieved through cloaking an area [103, 104]. This approach can
only be applied to the Edge of our system model to provide anonymity to a group of EVs, but we consider the Edge as an honest-but-curious threat actor and aim to preserve individual vehicles' privacy locally. Thus, such techniques are not trivially applicable to our considered threat model. Furthermore, anonymity techniques do not provide a formal privacy guarantee [105]. Similarly, mix-network approaches cannot be applied because there is no guarantee that multiple vehicles will be present in an Edge's coverage in any timestamp due to vehicles' movement [106].

An applicable approach to download the charging station's live map on EVs to search for the nearest or on-the-route available charging station has been considered and studied by the community [107]; however, the communication overhead of this technique is predicted to be much higher than the vehicles' location-based inquiry since it will require downloading a recent snapshot of the map for each query and, therefore, has been criticised in the literature [108]. Moreover, due to the absence of data sharing, such methods hinder the statistical utility of the location data for the servers that may be useful for a variety of purposes (e.g. providing vital statistics to industries and institutions for optimally placing the CS on the map based on the query densities) and prevent the EVs from receiving any information about the traffic around and occupancy of certain CS restricting them to plan their journeys accordingly.

DP methods are increasingly being deployed to preserve location privacy in a variety of domains, including automotive systems. The studies in [109, 110] proposed models by deploying a geo-ind based mechanism on the Edge for LBS. However, their approach did not consider preserving vehicles' location privacy against the Edge. An approach that complements the problem we aim to address in this work was proposed by Qiu et al. in [111] where the authors proposed a technique to crowd-source a task in a vehicular network while preserving geo-ind of the location of the vehicles offering Mobility as a Service in the spatial network to solve a task at a publicly known location in the map (e.g. taxi services). The problem formulation in this work is the inverse of what we aim to achieve in this chapter. As a result, the work in [111] cannot be extended to address the privacy concerns induced by multiple queries dynamically made along the journey.

In [112], Cunningham et al. studied the problem of trajectory sharing under DP and proposed a mechanism to tackle it. However, this work assumes the setting of an offline trajectory sharing which breaks down in the practical environment where the trajectories are being shared online as there is no prior information or limitation on the number of queries made by an EV during a journey and their respective locations. Therefore, the method proposed by the authors in [112] cannot be directly adapted to our dynamic environment closely simulating the real-world scenario for such a use case.

Of late, a major direction of research is along the lines of studying the statistical utility of differentially private data. A standard notion of statistical utility, which is extended to a variety of contexts, is the precision of the estimation of the distribution on the original data from that of the noisy data. Iterative Bayesian update (IBU) [31, 33], an instance of the famous expectation maximization (EM) method from statistics, provides one of the most flexible and powerful estimation techniques and has recently become in the focus of the community [34, 46]. In this work, we use IBU to approximate the distribution of the true locations of the queries made
to the server and based on that, the users of the EVs can predict the availability of the CS around them in real-time and plan their route accordingly.

## 4.3 Approximate geo-indistinguishability (AGeoI)

In the classical framework of GeoI [16], the space of the noisy data is, in theory, unbounded under the planar Laplace mechanism. Under a certain level of GeoI that is achieved, the planar Laplace mechanism ensures a nonzero probability of obfuscating an original location to a privatized one which may be quite far, thus inducing a possibility of a substantial deterioration in the QoS of the users. This loss of QoS can be more sensitive in the context of the navigation of EVs, where it is extremely important to prioritize a bounded domain where a user is willing to drive; this may be a result of time constraints, the rising cost of fuel, geographical boundaries (e.g. international borders), etc. – giving rise to an idea of *area of interest* for each EV. This motivated us to extend the classical GeoI to a more generalized approximate paradigm, inspired by the approach of the development of approximate DP from its pure counterpart.

Let $\mathcal{X}$ and $\mathcal{Y}$ be the spaces of the real and noisy locations equipped with distance metrics $d_{\mathcal{X}}$ and $d_{\mathcal{Y}}$, respectively. In general, $(\mathcal{X}, d_{\mathcal{X}})$ and $(\mathcal{Y}, d_{\mathcal{Y}})$ may be different and unrelated. However, for simplicity, here we assume $\mathcal{X} \subseteq \mathcal{Y}$ and, therefore, $d_{\mathcal{X}} = d_{\mathcal{Y}} = d$, and we proceed to define the notion of approximate geo-indistinguishability. It is worth noting here that, to an extent, we abuse the formal notion of “metric” as $d$ is not required to be symmetric, i.e., there may exist $x_1, x_2 \in \mathcal{Y}$ such that $d(x_1, x_2) \neq d(x_2, x_1)$.

**DEFINITION 4.3.1 (Approximate geo-indistinguishability).** A mechanism $\mathcal{K}$ is approximately geo-indistinguishable (AGeoI) or $(\varepsilon, \delta)$-geo-indistinguishable if for every measurable $S \subseteq \mathcal{Y}$, any pair of secrets $x, x' \in \mathcal{X}$, and for $\varepsilon, \delta \in \mathbb{R}_{\ge 0}$ satisfying $\delta e^{\varepsilon d(x, x')} \in [0, 1]$:

$$ \mathbb{P}_{\mathcal{K}}[y \in S|x] \le e^{\varepsilon d(x, x')} \mathbb{P}_{\mathcal{K}}[y \in S|x'] + \delta e^{\varepsilon d(x, x')} \quad (4.1) $$

One of the biggest advantages of DP and all of its variants that are accepted by the community is the property of compositionality, where the level of privacy can be formally derived with a repeated number of queries. Thus, we now enable ourselves to investigate the working of the compositionality theorem with the AGeoI which we defined, to stay consistent with the literature [105].

**THEOREM 4.1.** [Compositionality Theorem for AGeoI] Let mechanisms $\mathcal{K}_1$ and $\mathcal{K}_2$ be $(\varepsilon_1, \delta_1)$ and $(\varepsilon_2, \delta_2)$ geo-indistinguishable, respectively. Then their composition is $(\varepsilon_1 + \varepsilon_2, \delta_1 + \delta_2)$-geo-indistinguishable. In other words, for every $S_1, S_2 \subseteq \mathcal{Y}$ and all $x_1, x'_1, x_2, x'_2 \in \mathcal{X}$:

$$ \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2}[(y_1, y_2) \in S_1 \times S_2|(x_1, x_2)] \le e^{\varepsilon_1 d(x_1, x'_1) + \varepsilon_2 d(x_2, x'_2)} \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2}[(y_1, y_2) \in S_1 \times S_2|(x'_1, x'_2)] + (\delta_1 e^{\varepsilon_1 d(x_1, x'_1)} + \delta_2 e^{\varepsilon_2 d(x_2, x'_2)}) $$
Proof. In Appendix C.

We now proceed to generalize the conventional planar Laplace mechanism [113] to define the truncated Laplace mechanism extended to a generic metric space.

**DEFINITION 4.3.2 (Truncated Laplace mechanism).** The truncated Laplace mechanism $\mathcal{L}$ on a space $\mathcal{X}$ equipped with, not necessarily symmetric, distance metric $d$ truncated to a radius $r$, is defined as:

$$ \mathbb{P}_{\mathcal{L}}[y|x] = \begin{cases} c e^{-\varepsilon d(y,x)} & \text{if } d(x, y) \le r \\ 0 & \text{otherwise} \end{cases} \qquad (4.2) $$

where $c$ is the truncated normalization constant defined such that $\int_{y \in \mathcal{Y}} \mathbb{P}_{\mathcal{L}}[y|x]dy = 1$, and $\varepsilon$ is the desired privacy parameter. Let us call $r$ the radius of truncation for $\mathcal{L}$.

Note that for a discrete domain $\mathcal{Y}$, $c$ is defined by normalizing $\sum_{y \in \mathcal{Y}} \mathbb{P}_{\mathcal{L}}[y|x] = 1$, and, in this case, $\mathcal{L}$ is a truncated geometric mechanism [114] extended to a generic metric space.

**LEMMA 4.2.** For every $x_1, x_2 \in \mathcal{X}$ and $y \in \mathcal{Y}$, we have $e^{-\varepsilon d(x_1, x_2)}\mathbb{P}_{\mathcal{L}}[y|x_1] - \mathbb{P}_{\mathcal{L}}[y|x_2] \le 1$.

Proof. In Appendix C.

**THEOREM 4.3.** $\mathcal{L}$ satisfies $(\varepsilon, \delta)$-geo-indistinguishability where

$$ \delta = \max \left\{ \max_{\substack{y \in \mathcal{Y} \\ x_1, x_2 \in \mathcal{X}}} e^{-\varepsilon d(x_1, x_2)} \mathbb{P}_{\mathcal{L}}[y|x_1] - \mathbb{P}_{\mathcal{L}}[y|x_2], 0 \right\}. $$

Proof. Trivially $\delta e^{\varepsilon d(x_1, x_2)} > 0$ for any $x_1, x_2 \in \mathcal{X}$ as $\delta > 0$. Moreover, Lemma 4.2 ensures that $\delta e^{\varepsilon d(x_1, x_2)} \le 1$. Hence, for every $y \in \mathcal{Y}$ and for all $x_1, x_2 \in \mathcal{X}$, we have:

$$ \begin{aligned} & e^{-\varepsilon d(x_1, x_2)} \mathbb{P}_{\mathcal{L}}[y|x_1] - \mathbb{P}_{\mathcal{L}}[y|x_2] \le \delta \\ & \Rightarrow \mathbb{P}_{\mathcal{L}}[y|x_1] - e^{-\varepsilon d(x_1, x_2)} \mathbb{P}_{\mathcal{L}}[y|x_2] \le \delta e^{d(x_1, x_2)} \end{aligned} $$

□

The explicit process of sampling private locations satisfying AGeoI from a given set of original locations through a truncated Laplace mechanism on a discrete location space has been described in Algorithms 4 and 5.
<caption>**Algorithm 4:** Discrete and truncated Laplace mechanism (DTLap)</caption>

**Input:** Discrete domain of original locations: $\mathcal{X}$, Discrete domain of private locations: $\mathcal{Y}$, Desired privacy parameter: $\varepsilon$, Desired truncation radius: $r$; **Output:** Channel $C$ satisfying (4.2);

**Function** DTLap($\mathcal{X}, \mathcal{Y}, \varepsilon, r$):

Set $C \leftarrow$ empty channel;
Set $Y \leftarrow$ empty list;
**for** $x \in \mathcal{X}$ **do**
$c_x = \frac{1}{\sum_{y \in \mathcal{Y}} d(x,y) \le r}$;
**for** $y \in \mathcal{Y}$ **do**
  **if** $d(x,y) \le r$ **then**
    $C[x,y] = 0$;
  **else**
    $C[x,y] = c_x e^{-\varepsilon d(x,y)}$;
**Return:** $C$;

<caption>**Algorithm 5:** Sampling private locations with DTLap (DTLapSamp)</caption>

**Input:** Discrete domain of original locations: $\mathcal{X}$, Discrete domain of private locations: $\mathcal{Y}$, Desired privacy parameter: $\varepsilon$, Desired truncation radius: $r$; Vector of original locations: $X$;
**Output:** Corresponding vector of private locations: $Y$;

**Function** DTLapSamp($\mathcal{X}, \mathcal{Y}, \varepsilon, r, X$):

$C = \text{DTLAP}(\mathcal{X}, \mathcal{Y}, \varepsilon, r)$;
Set $Y \leftarrow$ empty list;
**for** $x \in X$ **do**
  Randomly sample $y \in \mathcal{Y} \sim C[x, :]$;
  Append $y$ to $Y$;
**Return:** $Y$;

# 4.4 System Model

This section details our privacy-preserving model for finding an optimal charging station in the Internet of Vehicles (IoV) as a use case of the proposed AGeoI technique. We begin with a discussion of the location privacy problems inherent in finding optimal CS in the IoV. This is followed by road networking modelling, a description of the system architecture for differentially private location sharing, the trust relationship between system tiers, and the privacy threat model.

## 4.4.1 Problem Statement

EVs have emerged as crucial components of future sustainable transportation systems, aimed at reducing CO2 emissions. Consequently, they have received considerable attention from both academia and industry [96]. However, due to their limited battery capacity, EVs often need to visit CS during journeys. This requirement leads to range anxiety among some drivers, where they fear that their vehicles lack sufficient battery power to reach their intended destinations. Range anxiety has been identified as a significant barrier to the widespread adoption
of EVs [115]. While CS are not always readily available, as it takes time to sufficiently charge EVs, the implementation of a CS booking service can help alleviate range anxiety.

To minimize charging wait times, EVs can access CS booking services through third-party providers, enabling them to discover the nearest and readily available CS. This can be achieved through static or live location queries. However, location sharing raises privacy challenges, such as vehicle tracking. GeoI technique provides a formal privacy guarantee for location queries. However, it is not highly applicable to this use case for two reasons. It does not consider the feasible locations where a vehicle can be present, and it does not stop vehicle tracking in the case of linked queries during the vehicle trajectory. Thus, a tailored privacy-preserving mechanism is facilitated by combining the proposed AGeoI technique with dummy location generation.

### 4.4.2 Road Network Model

Similar to [111], the road network G is represented as a weighted directed graph $G = (N, E, W)$, where N is the set of nodes, $E \subseteq N^2$ is the set of edges, and $W: N^2 \to \mathbb{R}^+$ is the set of weights representing the minimum travelling distance between any two nodes. The nodes and edges correspond to junctions and road segments of the network, respectively. Each edge $e \in E$ is addressed by the pair of respective starting node, ending node, and a weight representing the travelling distance through that edge, i.e., $e = (N_e^s, N_e^e, w_e) \in N$, where the direction of the traffic is from $N_e^s$ to $N_e^e$ on e. For any $i \in N$ and $j \in N$, let the sequence of edges $(e_1, \dots, e_r)$ denote a path from node i to node j if $N_{e_1}^s = i$ and $N_{e_r}^e = j$. Hence, let $C(i, j)$ represent the set of paths that connect node i to node j. Then W is a $N \times N$ matrix, where

$$W_{ij} = \begin{cases} \min_{p \in C(i,j)} \sum_{e \in p} w_e & \text{if } C(i,j) \neq \emptyset \\ \infty & \text{otherwise} \end{cases}$$

Essentially $W_{ij}$ is the shortest travelling distance from node i to node j in the network. We shall address the quantity $W_{ij}$ as the traversal distance between nodes i and j in the graph G and denote it as $d_G(i, j)$ for every $(i, j) \in N^2$. Note that, as G is a directed graph, $d_G$ may not be symmetric.

### 4.4.3 System Architecture

IoV applications are revolutionising transportation systems by mitigating human errors, enhancing travel convenience, and reducing energy, operational, and environmental costs [116, 117]. EVs have emerged as a viable technology for lowering carbon emissions and travel costs [118]. However, range anxiety is one of the major challenges of their wide adoption. Vehicular location data can be utilised to optimise the vehicle charging plan and mitigate range anxiety. Third-party services can assist users by recommending available CS in close proximity. Nevertheless, relying on these third-party providers raises significant privacy concerns within the honest-but-curious service provider threat model, necessitating users to trust them.

The system architecture, illustrated in Figure 4.1, incorporates vehicles within an ITS that
<figure><img src="image_17.png" /><figcaption>**Figure 4.1:** System Architecture (EV: Electric Vehicle, RSU: Roadside Unit, MEC: Mobile-Edge Computing Unit)</figcaption></figure>

operates on a three-tier architecture. This architecture comprises Roadside Units (RSUs) connected to a Mobile Edge Computing (MEC) Server, which is connected to the Core Cloud through a secure communication channel. The Core Cloud facilitates the connection between vehicles and third-party services, including the charging station recommender system, which is the main focus of our work. However, guaranteeing the complete trustworthiness of the cloud architecture and third-party service providers in handling vehicular location data is not feasible, aligning with the honest-but-curious threat model. Consequently, our proposed architecture only shares privatised vehicular location data. The subsequent sections delve into a comprehensive description of the roles and functions of each system component.

### Vehicle Tier

We fix a road network $G$ with nodes $G(N)$ and edges $G(E)$. We choose an arbitrary edge $I \in G$, and focus on the queries made by the EVs in $I$'s range of coverage, $R(I)$, provided by its RSU. An EV $u$ employs a local obfuscation technique to protect its true location $x^u \in R(I)$ to $x_1^u \in R(I)$ within the coverage area $R(I)$ of a specific edge. When an EV moves from the area of coverage of one Edge cloud to another, we can assume the queries and the privacy threats against the Edge to reset as each Edge communicates with the Cloud-based services and the third-party service providers.

### Edge Tier

Given the substantial volume of data generated and exchanged between vehicles and infrastructure, the installation of edge clouds in close proximity to vehicles becomes essential to host off-board vehicular services, which require low access latency from onboard vehicular services [119]. In addition to performing essential data processing and forwarding functions, the
Edge also serves as a layer for data aggregation. Moreover, it enables the deployment of supplementary privacy-preserving measures before sharing the data with third-party entities.

### Cloud Tier

It is expected to provide computation and storage capabilities for top-level processes, including data-sharing interfaces for third-party services.

### Third-party Service Provider

It is the external party to ITS and is expected to enhance the quality of the function for finding the available CS for the vehicles by receiving search queries compromised of privatised and dummy location vectors for the respective vehicles.

### Communication Channel

ITS comprises a network of RSU, vehicle on-board electronic control units (ECU), and distributed cloud computing and storage services. Wireless communications are enabled for V2V (Vehicle-to-Vehicle), V2I (Vehicle-to-Infrastructure) and V2X (Vehicle-to-Everything) by the technologies such as IEEE 802.11p DSRC/WAVE (Dedicated Short Range Communication/Wireless Access in Vehicular Environments), cellular advances such as C-V2X, and the long-term evolution for vehicles (LTE-V) [120]. Confidentiality of the wireless communication channel is secured by public key infrastructure (PKI) encryption methods which are beyond the scope of this work.

### 4.4.4 Privacy Threat Landscape

In real-time IoV location-based applications, it is often necessary for users to share their location information with the service provider in order to access location-specific services. However, this raises privacy concerns as it can potentially expose sensitive information about individuals' movements and activities. To address these concerns, data perturbation techniques can be employed to protect the privacy of users while still allowing them to access the services they need. These techniques introduce uncertainty or noise into the data, preventing an attacker from identifying the precise location of an individual. However, real-world solutions often rely on user consent, access control, and non-disclosure agreement-based mechanisms instead of providing formal privacy guarantees. Thus, there are existing privacy challenges related to shared location data, including journey tracing and location identification.

Furthermore, apart from these major privacy challenges, vehicular location data may also be susceptible to unauthorised use, data inference, retention, or insider privacy breaches within the service provider when formal privacy guarantees are lacking. The third-party provider is typically considered an honest-but-curious adversary model, assuming it is honest in accurately executing the protocol required to provide location data. However, there is a possibility that the provider may be curious about inferring users' private information based on the acquired location data [121].
This study aims to offer a formal privacy guarantee for location-based querying that can be
utilised by vehicles throughout their trajectories to effectively address the associated privacy
challenges with this process. To achieve this, the system is considered in three categories: (i)
the vehicle users (data subject), (ii) ITS encompassing the Edge and Core Cloud Tiers (data
controller and data processor), and (iii) the third party that receives the privatised data through
the deployed privacy-preserving mechanisms. The third party is assumed to be an EV charging
management system, which may operate under a registration-based approach for a specific area.
Our focus is on mitigating the following two major sources of threats that have the potential to
compromise the privacy of EVs.

**Location identification:** It is vital to ensure that the privatized version of the true location of the EV is within a certain radius of interest w.p. 1, making sure that the reported location is within a feasible and drivable distance away, and most importantly, within the area of coverage of the Edge where its true location lies. Therefore, we defined AGeoI as an extension of GeoI. Thus, to ensure the privacy of any given query in the road network, the EVs locally obfuscate their true locations using the truncated Laplace mechanism with their desired parameter $\varepsilon$ and the radius of truncation $r$, which, in turn, decide the value of $\delta$.

**Journey tracing:**

EVs may inquire about the nearest available charging station without proceeding with the query and raise further queries along the journey. Subsequently, additional queries may be raised at different points during the journey. In our model, we aim to capture this realistic setting by allowing multiple queries to be made by the EV within a single journey. However, this introduces a potential threat of approximately tracing the trajectory of the EV's journey by interpolating the locations of the queries, despite each individual location being AGeoI-protected. This is due to the fact that the obfuscated location of each query is not distinguishable from the real location, but they are not too far off from each other with a very high probability. Consequently, if a large number of queries are made within a single journey, it becomes relatively straightforward to approximate the trajectory of the EV's journey.

Cunningham et al. [112] proposed a mechanism to securely share trajectories under LDP. However, the authors in [112] assumed a model of offline sharing of the entire trajectory and, hence, sanitising it with the proposed mechanism to engender LDP guarantees. In our setting, this method cannot be directly implemented as we consider a dynamic environment where the queries made by the EVs are in real-time, with the server not having any prior knowledge of the number or the location of the queries made by a certain EV. Therefore, the mechanism of [112] cannot trivially be extended in the online location-sharing environment, and hence, the threat of adversaries able to reconstruct the journey of a particular EV with a high number of queries remains as a concern.

4.4.5 Proposed Query Model

During the journey, an EV *u* located within the coverage of an Edge *I* locally obfuscates its true
location *x*^u ∈ R(I) to *x*^u_1 ∈ R(I) using the truncated Laplace mechanism, guaranteeing AGeoI,
and generate *m* − 1 feasible dummy locations {*x*^u_2, ..., *x*^u_m} ∈ R(I)^{m−1}, i.e., locations that cannot
<figure><img src="image_18.png" /><figcaption>**Figure 4.2:** Reported dummy and privatised locations for two respective time windows (White Pins: Privatised locations, Orange Pins: Dummy locations in 1st Time window, Blue Pins: Dummy locations in 2nd Time window)</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>**Figure 4.3:** A toy example for a static location query on discrete road network</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>**Figure 4.4:** A toy example for linked 3 location queries on discrete road network</figcaption></figure>
be trivially identified as being artificially generated given the query of the previous time stamp w.r.t. realistic speed limits, travelling conditions, etc. For the first query that $u$ makes along its journey, it can generate any random $m-1$ dummy locations in $R(I)$. Thus, each CS query of $u$ consists of reporting the vector of $m$ locations, $l_u = (x_1^u, \dots, x_m^u) \in R(I)^m$, to $I$ for the Edge to process and communicate the query to the Cloud services and the third-parties to find the nearest available CS in $R(I)$ for $u$. This approach ensures that the adversary will have at least $m$ possible trajectories that the EV could have realistically followed at every time stamp, making it highly improbable for the Edge and the third party to be able to conclude which of them was the actual journey as, after $k$ queries made along a single journey, each interpolated trajectory will have a probability of at least $1/m^k$ of being the real one.

Figure 4.2 illustrates 10 reported dummy locations along with the privatized location for two consecutive time windows. Notably, the dummy locations in the subsequent time window can be feasibly linked to at least one of the preceding dummy locations. For a clearer understanding of the proposed privacy-preserving mechanism, Figures 4.3 and 4.4 present simplified examples. The former demonstrates a static query on a discrete road network, while the latter showcases linked dynamic queries on the same network.

At any given time, the Edge collects all the reported locations from the querying EVs, shuffles them by effacing the links between the location vectors and the corresponding EVs, and sends this jumbled collection of all the reported locations in the network to know their respective nearest available CS to the third-party service provider. After receiving the response, the Edge, which internally keeps the record of the IDs of the EVs against their queried locations, assigns the corresponding vector of locations of the nearest available CS to each EV and communicates them back to the respective vehicles.

In other words, at time $t$, if the Edge receives the location vectors from $k_t$ querying EVs as $\mathcal{L}(t) = \{l_{u_1}, \dots, l_{u_{k_t}}\}$, the Edge is responsible for shuffling all the individual location points in these reported vectors and forward the scrambled collection of locations $\mathcal{L}'(t) = \{x_i^u: u \in \{u_1, \dots, u_{k_t}, i \in [m]\}$ to the Cloud and the third-party, while internally keeping a track of the IDs of the EVs to reconnect the query-response back to the corresponding users. Setting $\hat{x}$ as the location of the nearest available charging station from location $x$ in $R(I)$, the Edge receives $\mathcal{R}(t) = \{\hat{x}_i^u: u \in \{u_1, \dots, u_{k_t}, i \in [m]\}$ as the response from the third-party service provider handling the CS data real-time. After this, matching the stored IDs of the EVs with the locations of the CS, the Edge communicates the response vector $\hat{l}_u = (\hat{x}_i^u: i \in [m])$ back to the corresponding EV $u$. Then the EV can choose to navigate to $\text{argmin}_{x \in \hat{l}_u} \{d_G(x, x_u)\}$, where $x_u$ is the real location of EV $u$. The overview of this mechanism is explained in Figure 4.1.

## 4.5 Cost of privacy analysis

**DEFINITION 4.5.1 (Cost of privacy).** Suppose an EV $u$ at location $x^u$ chooses to locally obfuscate its real location of a query as $x_1^u$ using the truncated Laplace mechanism $\mathcal{L}_{\varepsilon,r}$ satisfying $(\varepsilon, \delta)$-geo-indistinguishability with a corresponding radius of truncation $r$. Then we define the *cost of privacy (CoP)* of EV $u$ as
CoP($u$, $\mathcal{L}_{\varepsilon,r}$) = $\mathbf{c}(x^u, \hat{x}_1^u) - \mathbf{c}(x^u, \hat{x}^u)$, where $\hat{x}^u$ and $\hat{x}_1^u$ are the nearest available CS in the network to $x^u$ and $x_1^u$, respectively, and $\mathbf{c}: G(N)^2 \to \mathbb{R}^+$ is any cost function that reflects the “cost” of the commute from locations $x$ to $y$ in the network.

In other words, CoP, as in Definition 4.5.1, essentially captures the extra cost that an EV needs to cover as a result of the privatized location it reports to the Edge satisfying AGeoI, as opposed to its true location. For the purpose of simplicity of the analysis, we considered the cost function as the travelling distance in the network, i.e., $\mathbf{c} = d_G$. However, in practice, any suitable cost function could be used (e.g. fuel efficiency, time, etc.) could be used as $\mathbf{c}$, depending on the context and requirement of the architecture.

To formally characterize and analyze the CoP of the EVs in the network, inspired from the classical version of Voronoi decomposition, we extend the concept in the setting of our road network in the network coverage for a fixed Edge w.r.t. graph-traversal distance, $d_g$.

**DEFINITION 4.5.2 (Voronoi decomposition).** Let $G$ be the graph representing the road network equipped with travelling distance $d_G$. Let the set of CS in $G$ be $C_G = \{c_1, \dots, c_{n_G}\}$. Then the Voronoi decomposition on $G$ w.r.t. $C_G$ is defined as $V_G = \{V_i: i \in [n_G]\}$ such that $V_i \cap V_j = \emptyset$ for any $i \neq j$ and $\bigcup_{i \in [n_G]} V_i = G$, where

$$V_i = \{x \in G: d_G(x, c_i) \leq d_G(x, c_j) \forall j \in [n_G], j \neq i\}$$

**DEFINITION 4.5.3 (Closed ball around a location).** For any $x \in G$ and $r \in \mathbb{R}_{\geq 0}$, the closed ball of $x$ of radius $r$ is defined as $\beta_r(x) = \{y \in G: d_G(x, y) \leq r\}$

**DEFINITION 4.5.4 (Fenced Voronoi decomposition).** For any $r \in \mathbb{R}_{\geq 0}$ and charging station $i$, let the $r$-fenced Voronoi decomposition on road network $G$ be defined as $V_G^{-r} = \{V_i^{-r}: i \in [n_G]\}$ such that $V_i^{-r} \cap V_j^{-r} = \emptyset$ for $i \neq j$ and $V_i^{-r} = \{x \in V_i: B_r(x) \subseteq V_i\}$. In other words, $V_i^{-r}$ essentially constructs an area contained within $V_i$ restricted by a fence at a distance $r$ from the edge of $V_i$.

**THEOREM 4.4.** Suppose an EV $u$ positioned at $x^u$ on $G$ obfuscates its location using AGeoI with any radius of truncation $r \in \mathbb{R}_{\geq 0}$. Let $\hat{x}^u$ be the location of the nearest available charging station to the true location $x^u$. Then $\mathbb{P}[\text{CoP}(u, \mathcal{L}_{\varepsilon,r}) = 0] = 1$ for every $x^u \in V_{\hat{x}^u}^{-r}$. In other words, if an EV lies in the $r$-fenced Voronoi decomposition for its nearest available CS, it has a zero cost for privacy w.p. 1.

*Proof.* Immediate from Definition 4.5.4. □

**THEOREM 4.5.** Suppose an EV $u$ lies in $V_{\hat{x}^u} \setminus V_{\hat{x}^u}^{-r}$ and it uses AGeoI to obfuscate its true location $x^u$ to $x_1^u$ with a radius of truncation $r$ and privacy parameter $\varepsilon$ for making a private query to the Edge. Then $\mathbb{P}[\text{CoP}(u, \mathcal{L}_{\varepsilon,r}) = 0] =$
$\sum_{x_1^u \in V_{\hat{x}u}} c e^{-\varepsilon d_G(x^u, x_1^u)}$, where c is the normalizing constant of the truncated Laplace mechanism as in Definition 4.3.2.

*Proof.* To compute $\mathbb{P}[\text{CoP}(u, \mathcal{L}_{\varepsilon,r}) = 0]$, we only need to exclude the possibilities where the reported location of the EV lies outside the Voronoi decomposition of the station $\hat{x}^u$, which, essentially, is $\sum_{x_1^u \in V_{\hat{x}u}} c e^{-\varepsilon d_G(x^u, x_1^u)}$. $\square$

# 4.6 Experimental Study

This section presents the experimental study with the objectives as follows: (i) to validate proposed theoretical claims and solutions empirically; (ii) to use the method to find the nearest available charging station for EVs as a case study; (iii) to investigate the cost of privacy in real-time settings; and (iv) to conduct a real-time CS occupancy prediction technique from the noisy vehicle distribution.

## 4.6.1 Dataset Preparation

The road network data extracted from OpenStreetMap [122]. The cost of privacy is calculated as the additional routing distance caused by noise in vehicular locations during queries to identify the optimal charging station. The cost of privacy depends on the sparsity of CS. We prepared two datasets: one with 404 existing charging station locations in San Francisco obtained from the United States Department of Energy [123], and another by merging existing and planned charging station locations with on-street and off-street parking locations from DataSF [124], resulting in 716 independently distributed locations.

The EPFL mobility dataset includes GPS records of 536 taxi trajectories in San Francisco over four weeks [125]. The dataset provides information such as the taxi identifier, latitude, longitude, occupancy state (vacant or occupied), and a UNIX epoch timestamp. Leveraging the occupancy information, we were able to split the complete taxi trajectories into individual customer trajectories, resulting in over 450,000 exported trajectories. For our study, we randomly selected 536 trajectories from each taxi.

## 4.6.2 Experimental Setup

A group of EVs sends out location queries to find the closest available CS during their journeys on the road network $G$. The edges of the road network $G$ are truncated into discrete segments with an equal $k$ travel distance, similar to the work in [111]. DTLap is utilised to generate the privacy channel by using the Laplace mechanism for the user's desired values for privacy budget $\varepsilon$ and truncation radius $r$. Following this, DTLapSamp is used to generate privatised locations with respect to the users' real locations.

A location query contains a privatised location and $m-1$ dummy locations as a vector and is collected by the Edge for sending them to the third party through the core cloud as a single vector of all locations. The third party responds to the locations in the vector with the closest
available CS for each, and the Edge sends vehicle location vectors to the related vehicles without being able to differentiate privatised and dummy locations.

For IBU to approximate the original distribution of the query locations of the EVs in the road network in order to predict the availability of the CS and, thus, assist the users in planning their journeys appropriately, we note that each original query location goes through two independent steps of sanitization: a) locally using the truncated Laplace mechanism to achieve AGeoI and b) generating the realistic dummy locations in the area of coverage of the Edge to ensure protection against attacks reconstructing their journeys. Setting the domain $\mathcal{X}$ as the area of coverage of the RSU of the fixed Edge that we focus on, while the former is a straightforward use of the channel $\mathcal{L}$, the latter can be thought of as $m - 1$ independent applications of the uniform channel $\mathcal{U}$, where $U: \mathcal{X}^2 \to \mathbb{R}$ with $\mathcal{U}_{x,y}$ denoting $\mathbb{P}_U[y|x] = 1/|\mathcal{X}|$, by each EV. Therefore, after accounting for the normalization, the channel incorporating the local obfuscation and the generation of the dummy locations used by each EV reduces down to $\frac{1}{m}\mathcal{L} + \frac{m-1}{m}\mathcal{U}$ which we use as the privacy channel to implement IBU.

The first set of experiments examines the CoP for randomly selected 536 vehicle traces, where each trace contains a series of GPS coordinates and 3 randomly selected points along each for the real locations of the queries. The discrete road network is generated by setting the distance $k = 100$ meters. The parameters of $\varepsilon$ and $r$ are varied in the range of 0.2 to 2, and 1 to 20, respectively.

The privatised location, together with the dummy locations, is sent to the third-party for a query to prevent the third-party from tracking the vehicle. The area of Edge coverage, rather than the vehicle's area of interest, is considered for dummy location generation rather than the vehicle's area of interest, as the centre of mass may give away the true location. The second set of experiments examined the impact of dummy locations on the CoP.

The location queries could be used for real-time predictive analysis on the optimisation of the smart power grid, managing staff, and determining where new CS should be deployed. Thus, service providers can have the utility of the datasets (e.g., train ML models, etc.) with DP-based methods while the privacy of individuals is preserved. The third set of experiments utilises the IBU method to retrieve the true distribution of locations of the queries from the noisy distribution, which includes privatised and dummy locations.

### 4.6.3 Results and Discussion

#### Cost of Privacy: empirical results

DP approaches introduce a trade-off between privacy and data utility, with a higher level of privacy requiring a greater level of noise. The efficacy of the respective service may correspondingly decrease due to the fall in data utility, and this difference in the *quality of service* is referred to as the ‘cost of privacy’ (CoP) in this study. In particular, in the context of the use case considered in this work, the CoP is formalised in Definition 4.5.1.

The following results are achieved by carrying out the experiments for 3 linked queries of 536 randomly selected vehicle trajectories for varying values of $\varepsilon$ or $r$ ranging from 0.2 to 2, and
<figure><img src="image_21.png" /><figcaption>**Figure 4.5:** CoP (i.e., by Definition 4.5.1, the difference in the distance an EV needs to cover to reach the nearest CS with and without local obfuscation to achieve Ageol) for varying $ε$ or $r$ of AGeoI (1st row is for sparse CS, 2nd row is for dense CS).</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>**Figure 4.6:** Fraction of EVs incurring no CoP for varying $ε$ or $r$ of AGeoI (1st row is for sparse CS, 2nd row is for dense CS).</figcaption></figure>
<figure><img src="image_23.png" /><figcaption>Figure 4.7: Impact of introducing dummy locations along with AGeoI on the CoP.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 4.8: The Kantorovich-Wasserstein distance between the original and estimated distributions using IBU for $\epsilon = 0.6$ and $\epsilon = 2$ noisy distributions.</figcaption></figure>

1 to 20, respectively. Figure 4.5 demonstrates the CoP in terms of the extra travelling distance due to the privacy-preserving mechanism, where a similar pattern is observed for both of the datasets. Another observation is that a high frequency of queries resulted in no cost for privacy preservation. Figure 4.6 shows the fraction of the queries with “privacy for free” where both datasets followed similar patterns. Vehicle queries contain dummy locations and their privatised true locations. It is possible that the dummy locations can sometimes provide a better utility, but our experiments consider the utility of a privatised location as the worst-case for analysis.

Figure 4.5 shows that our method provides a negligible cost of utility loss for the formal privacy gain enjoyed by the EVs. By increasing the truncation radius, an abrupt drop in the distance between the location of the nearest available charging station for the true location of the query and that of the privatised one implies that the cost of the extra travel distance needed to be taken due to the AGeoI guarantee is almost negligible. A similar trend is seen for the varying $\epsilon$ with a fixed radius. As the level of privacy decreases, the fraction of EVs in the network enjoying *privacy for free* grows to be more than 60% for a radius of truncation of merely
<figure><img src="image_25.png" /><figcaption>**Figure 4.9:** Estimations of the original distribution using IBU for the $\varepsilon = 0.6$ and $\varepsilon = 2$ noisy distributions.</figcaption></figure>

10 road segments, where each segment is 100 meters long, for $\varepsilon \ge 0.5$. However, more than 90% of the EVs achieve a zero cost of privacy for $\varepsilon \ge 1.5$, irrespective of the truncation radius as illustrated in Figure 4.6. Due to increasing perturbation in disclosed location, the width of the confidence interval for zero cost of privacy increases, as seen in Figure 4.6. The likelihood of achieving zero cost of privacy fluctuates over a wider range and it does not monotonically decrease with the growing radius due to rising randomness.

## Impact of Dummy Data Generation

Considering an adversary interested in finding the true locations of the EVs, $(\alpha, \beta]$-identifiability is defined for any location $x$ as $\mathbb{P}[d(y,x) < \alpha) > \beta$, where $y$ is any guessed location by the adversary. With the proposed method, with a sufficiently small radius of truncation to obfuscate the true location using the truncated Laplace and generating $m-1$ dummy locations in the area of coverage of the Edge, the probability of hitting the true $x$ within an error of $\alpha$ is $\mathbb{P}[d(x,y) < \alpha] = \frac{1}{m}ce^{-\varepsilon\alpha} = \beta$, where $c$ is the normalising constant.
There has been some work in this area from the perspective of just GeoI [109–111, 126, 127] or just from the standpoint of generating dummy locations exploiting anonymisation techniques [128, 129]. One of the first major concerns in using only GeoI is when we allow dynamic and multiple queries along the journey of the EVs, as individual locations, despite being privatised, can still be interpolated to approximate the entire trace. If only dummy locations are used, however, any estimated (or observed) $y$ could be the real location w.p. $\frac{1}{m-1}$, as there is no formal privacy guaranteed, i.e., every location $x$ has, is $(0, 1/m - 1)$-identifiable among $(m - 1)$ dummy locations. With potential parallel processing, brute-force attacks are just one way that it has been shown that anonymisation techniques are not sufficient to protect privacy [130].

Figure 4.7 illustrates how the CoP increases with an increase in the noise due to the lack of dummy locations under the same level of identifiability. To achieve the same $(\alpha, \beta)$-identifiability with just AGeoI without dummy locations, the parameter $\varepsilon$ needs to be scaled by $\frac{1}{\ln m}$, i.e., more noise needs to be added, which results in having a worse trade-off between privacy and CoP for the same level of privacy.

## Real-time Predictive Study

Predicting the availability of CS is a crucial component of EV trip planning and can help ease range anxiety. Some existing methods adhered to machine learning-based approaches to develop such prediction models [131–135]. The main consideration of these models is that drivers can book timeslots for CS and the prediction is made based on factors such as past usage of CSs, traffic density, and some other features such as weather conditions. However, such consideration may be limited to facilitating effective EV journey planning, given that traffic is highly dynamic and subject to unexpected changes. Due to the traffic, EVs may be late for their scheduled charging time, and another EV cannot be navigated to charge from the same station, despite the fact that it is empty. Hence, a real-time predictive analysis would be critical to determine the likelihood of a CS being available when an EV arrives. Our proposed method provides privacy-preserved live traffic distribution of the querying vehicles. IBU is applied to estimate the real-time distribution of the traffic and, hence, the statistical distance between the estimated and the original distributions are shown in Figure 4.9. We considered two different levels of AGeoI with $\varepsilon = 0.6$ and $\varepsilon = 2$ and IBU was run for 100 iterations. The results demonstrate that the distance between the original and the estimated distributions of the traffic is decreasing. The accuracy of the estimation of the original distribution from the noisy locations is illustrated by the heatmaps of Figure 4.9 depicting the original, noisy, and estimated traffic distributions. This essentially highlights the high statistical utility of our proposed method and, specifically, helps in the prediction of how likely a CS will be available when the vehicle arrives and the traffic, in general.
# Part III

## Federated learning
"Learn continually. There's always one more thing to learn."

– Steve Jobs
5

Advancing Personalized Federated Learning:
Group Privacy, Fairness, and Beyond

**5.1 Introduction**

The widespread collection of user data in modern machine learning has raised concerns regard-
ing privacy violations and the potential disclosure of sensitive personal information [136, 137].
To address these concerns, Federated Learning [26] was introduced as a collaborative machine
learning paradigm, where users' devices train a global predictive model without transmitting
raw data to a central server. While FL offers promises of preserving user privacy and main-
taining model performance, the heterogeneity of data distributions among clients can lead to
challenges such as reduced model utility and convergence issues during training. In response,
personalized federated learning approaches have emerged, aiming to tailor models to clusters
of users with similar data distributions [138-140].

Furthermore, it has been demonstrated that avoiding the release of users' raw data alone
does not provide sufficient protection against potential privacy violations [141–143]. To ad-
dress this issue, researchers have explored the application of Differential Privacy (DP) [13, 14]
to federated learning, providing privacy guarantees for users participating in the optimization
process. DP mechanisms introduce randomness in the model updates released by clients, mak-
ing each user's contribution to the final model probabilistically indistinguishable up to a certain
likelihood factor. To bound this factor, the domain of secrets (i.e., the parameter space in FL)
is artificially constrained, either to offer central [144, 145] or local DP guarantees [146, 147].
However, constraining the optimization process to a subset of ℝⁿ can have negative effects,
such as when the optimal model parameters for a particular cluster of users lie outside such a
bounded domain.

To address the challenges of personalization and local privacy protection, we propose the adoption of a more general notion of DP called *d*-privacy or metric-based privacy [17] which has been in the spotlight of late mainly in the context of location-privacy [55, 148, 149]. This concept of privacy does not require a bounded domain and provides guarantees based on the distance between any two points in the parameter space. Therefore, assuming that clients with similar data distributions have similar optimal fitting parameters, *d*-privacy offers strong indis- tinguishability guarantees. Conversely, privacy guarantees degrade gracefully for clients with significantly different data distributions.

In addition to addressing privacy concerns, this work also investigates the impact of our method on fairness aspects in federated model training, extending the analysis conducted in [150]. As machine learning-based decision systems become more prevalent, it has become apparent that many of these systems exhibit gender and racial biases that disproportionately affect mi- nority populations [151, 152]. Therefore, beyond protecting user privacy, it is crucial to explore cutting-edge machine learning algorithms that can potentially mitigate this pervasive lack of fairness among participating clients. However, we have observed that systems aiming to protect privacy while ensuring fairness often involve a trade-off between the two [153]. This trade-off arises because privacy protection techniques based on DP tend to minimize the impact of outliers or minorities within the overall dataset. In other words, the application of *d*-privacy, a metric- based generalization of DP, to personalized FL could potentially compromise the fairness of the machine learning model. This work presents extensive experimental results demonstrating that the use of personalized FL under group privacy guarantees not only significantly improves fair- ness compared to the classical (non-personalized) FL framework, but also maintains a relatively small trade-off between privacy and fairness.

## Contributions

The key contributions of this chapter are:

1. We propose an algorithm for collaborative training of machine learning models, leveraging advanced techniques for model personalization and addressing user privacy concerns by formalizing privacy guarantees in terms of *d*-privacy.

2. Our research focuses on studying the Laplace mechanism under Euclidean distance and providing a closed-form expression for its generalization in $R^n$, as well as an efficient sampling procedure.

3. We show that personalized federated learning under formal privacy guarantees improves group fairness significantly compared to the non-personalized federated learning framework and, hence, establish that our method enhances the trade-off between privacy and fairness.
<figure><img src="image_26.png" /><figcaption>Figure 5.1: A schematic overview of the personalized approach of federated model training</figcaption></figure>

## 5.2 Technical Preliminaries

### 5.2.1 Personalized Federated Learning

The problem of personalized federated learning falls within the framework of stochastic optimization, and we adopt the notation from [138] to determine the set of minimizers $\theta_j^* \in \mathbb{R}^n$ with $j \in \{1, \dots, k\}$ of the cost functions

$$F(\theta_j) = \mathbb{E}_{z \sim \mathcal{D}_j} [f(\theta_j; z)], \qquad (5.1)$$

where $\{\mathcal{D}_1, \dots, \mathcal{D}_k\}$ are the data distributions which cannot be accessed directly but only through a collection of client datasets $Z_c = \{z | z \sim \mathcal{D}_j, z \in \mathbb{D}\}$ for some $j \in \{1, \dots, k\}$ with $c \in C = \{1, \dots, N\}$ the set of clients, and $\mathbb{D}$ a generic domain of data points. $C$ is partitioned in $k$ disjoint sets

$$S_j^* = \{c \in C \mid \forall z \in Z_c, z \sim \mathcal{D}_j \quad \forall j \in \{1, \dots, k\} \qquad (5.2)$$

The mapping $c \to j$ is unknown and we rely on estimates $S_j$ of the membership of $Z_c$ to compute the empirical cost functions

$$\tilde{F}(\theta_j) = \frac{1}{|S_j|} \sum_{c \in S_j} \tilde{F}_c(\theta_j; Z_c); \\ \tilde{F}_c(\theta_j; Z_c) = \frac{1}{|Z_c|} \sum_{z_i \in Z_c} f(\theta_j; z_i) \qquad (5.3)$$

The cost function $f: \mathbb{R}^n \times \mathbb{D} \to \mathbb{R}_{\ge 0}$ is applied on $z \in \mathbb{D}$, parametrized by the vector $\theta_j \in \mathbb{R}^n$. Thus, the optimization aims to find, $\forall j \in \{1, \dots, k\}$,

$$\hat{\theta}_j^* = \underset{\theta_j}{\operatorname{argmin}} \tilde{F}(\theta_j) \qquad (5.4)$$