# Privacy engineering through obfuscation

Ero Balsa  imec-COSIC, KU Leuven
<EMAIL_ADDRESS>
###### Abstract

_Obfuscation_ in privacy engineering denotes a diverse set of data operations
aimed at reducing the privacy loss that users incur in by participating in
digital systems. Obfuscation’s domain of application is vast: privacy-
preserving database analysis, location-based privacy, private web search or
privacy-friendly recommender systems are but a few examples of the contexts in
which privacy engineers have resorted to obfuscation. Yet an understanding of
the role that obfuscation, in general, plays in the engineering of privacy has
so far proved elusive. Similarly, we lack a cohesive view of the wide array of
privacy measures that assist the evaluation of obfuscation technologies. This
paper contributes to closing these research gaps. First, we provide a general
analysis framework that brings together a multiplicity of obfuscation methods
under the same analytical umbrella. Second, we distinguish between mechanism-
centred and attack-centred evaluation, making explicit a hierarchy of
assumptions behind privacy measures that assists and demystifies obfuscation
tools’ evaluation. Finally, we examine the role that obfuscation technology
plays in privacy engineering by introducing the concepts of _personal_ and
_public utility_ and distinguishing between utility-degrading and utility-
preserving obfuscation. We observe that public utility requirements require us
to resort to utility-degrading obfuscation to arbitrarily reduce privacy loss.
Conversely, personal utility requirements do not, _in theory_ , impose such a
privacy-utility trade-off, and we illustrate how to perform utility-preserving
obfuscation through _chaff_.

§§footnotetext: This paper was entirely written while the author was at KU
Leuven.

##  I Introduction

In computer security, _obfuscation_ denotes a family of techniques to achieve
disparate security and privacy properties. In software engineering and
cryptography, obfuscation mainly denotes a set of transformations to source or
machine code that make it difficult for humans to understand and reverse-
engineer software programs, e.g. the program’s purpose or internal values.
Software engineers and cryptographers approach program obfuscation in
radically different ways —the former using _security through obscurity_
techniques, the latter favouring _open_ and _provable_ security and formal
properties— however, program obfuscation still denotes a somewhat narrowly
defined and concrete problem [1]. Conversely, privacy engineers use the term
_obfuscation_ to describe an array of methods and techniques that serve a
disparate set of ends and purposes in various contexts such as web search
privacy [2, 3], location privacy [4, 5, 6], statistical disclosure control [7,
8] or anonymous communications [9, 10], among others, pursuing privacy
properties specific to each of these contexts.

Privacy engineers perform obfuscation using a host of data operations such as
randomisation, addition and suppression, generalisation, shuffling and
swapping [11]. However, even if privacy engineers use the same set of
techniques across contexts, they do not always refer to them as _obfuscation_.
Whereas location privacy researchers often refer to the operations they
perform on location data as _obfuscation_ [5, 12, 13], database privacy
researchers rarely do so, favouring alternative terms such as _perturbation_
or more specific terminology such as _randomisation_ or _generalisation_ ,
even if the set of techniques both use is oftentimes the same or analogous.
Moreover, while researchers do work across contexts, bringing insights and
expertise from one area to another [3, 6, 14], a broader, more general
bird’s-eye view of obfuscation methods across contexts has so far been
elusive; terminology is often inconsistent and piecemeal, and the common
underlying rationale and analogies between diverse obfuscation methods is not
made explicit. This prevents a more general understanding of the role
obfuscation plays —regardless of the particular form it takes and context in
which it is applied— in the design of privacy technologies. When and why do we
use obfuscation as opposed to other mechanisms in the engineering of privacy?
How does obfuscation complement or replace alternative protection mechanisms?
When _must_ we use obfuscation and when does it represent a suboptimal but
useful, even needed, solution? What trade-offs do obfuscation methods impose
on other requirements such as utility or cost, and under which conditions?
While this set of questions has been examined for particular contexts and
scenarios, under a more or less narrow set of assumptions, a more holistic and
general understanding of the role that obfuscation plays in privacy
engineering is still missing.

_Obfuscation tools_ enable us to pursue a wide range of privacy properties
under diverse conditions and assumptions, e.g. from the limited set of
assumptions that differentially-private mechanisms rely on to attain
independence from adversaries’ background knowledge, to the more concrete
adversaries’ specification that distortion-based measures of privacy require
[15]. The design and evaluation of obfuscation tools requires that we define
the privacy properties we seek and under which assumptions. Then, to assess
the extent to which obfuscation tools satisfy those privacy properties, we
need to determine how to operationalise such properties through the right
privacy measures. Whereas debate in the literature as to which privacy
measures one must choose to evaluate obfuscation technology abounds, such
debate has been largely confined to narrow contexts and applications, be it
web search privacy, location privacy or anonymous communications [3, 16, 17].
The types of measures we can select to evaluate obfuscation solutions, the
reason why we should choose one measure over another, as well as the
underlying set of assumptions on which these measures depend, these are
questions that call for a cohesive, comprehensive understanding of the
conditions and assumptions under which any particular measure suitably assists
the evaluation of obfuscation technologies.

Hence, in this paper we provide _a bird’s-eye view of obfuscation_ tools in
privacy engineering. To that end, a first contribution of this paper is to
bring obfuscation methods under a common analysis framework, thus making
explicit the relationship across obfuscation techniques and enabling a
holistic study and understanding of the role these operations play in privacy
engineering.111 We note that we do not intend to replace or force the use of
the term obfuscation across disciplines. Rather, by referring to them as
_obfuscation_ , we simply bring these analogous techniques under the same
analytical umbrella.

The second contribution is to propose an evaluation framework for obfuscation
technologies _in general_ , abstracting away from the particularities of
specific contexts and laying bare the set of assumptions that privacy measures
depend on and their impact on the design and evaluation of obfuscation
technology. We propose two approaches to evaluating obfuscation tools: a
mechanism-centred evaluation and an attack-centred evaluation. This
conceptualisation enables us to make explicit the underlying assumptions and
level of generality of different privacy measures, as well as to examine the
role these measures play in the design and evaluation of obfuscation
technologies, e.g. when it makes sense to seek _independence from the
adversary’s knowledge_ as opposed to when we need to focus on one adversary
with a particular instance of background knowledge and attack strategy.

The third contribution is to equip the analytical framework for obfuscation we
propose in this paper with a set of conceptual tools that enable us to examine
the role of obfuscation in privacy engineering. More specifically, we
introduce the concepts of _personal_ and _public utility_ , and distinguish
between two types of obfuscation: utility-degrading obfuscation (UDO) and
utility-preserving obfuscation (UPO). Through this conceptual framework, we
observe that arbitrarily reducing privacy loss under public utility
requirements mandates the deployment of UDO: we _must_ resort to (utility-
degrading) obfuscation, no other privacy technology or method enables us to
arbitrarily minimise the privacy losses that the production of public utility
prompts. Conversely, personal utility alone does not impose a trade-off
between utility and privacy, meaning that deploying UDO to balance personal
utility against privacy is suboptimal; and yet, obfuscation still plays a key
role in defending users against privacy-invasive service providers that, be it
for vested interests in data collection or the high costs involved in setting
up their systems according to stringent privacy-by-design principles, fail to
protect users’ privacy.

Lastly, the fourth contribution is to highlight the role of _chaff_ , namely,
the generation of fake or dummy activity, as a means to perform UPO. We
examine the conditions that enable or hinder the deployment of this
obfuscation method and highlight that escaping the trade-off between utility
and privacy invokes an alternative trade-off between privacy and cost.

##  II An abstract model of obfuscation tools

An individual uses an online service that offers a set of functionalities
$\\{f_{i}\\}$, e.g. sending messages to friends, browsing the Internet,
posting on a blog or searching the web. We refer to this individual as the
_user_ and abstract from the particular type of service; the user performs
service requests $r_{i}$ and obtains responses ${o_{i}=f_{i}(r_{i})}$ so that
$f:\mathcal{R}\rightarrow\mathcal{O}$ with $\mathcal{R}$ the universe of user
requests and $\mathcal{O}$ the universe of service responses. A request $r$
denotes not only the service the user solicits but also input data that the
execution of the service requires, e.g. the message a user sends to a friend
on an instant messaging app or the URL of the website she wishes to access
from a set of search results. We more generally refer to $r$ as the user
_input_ and to $o$ as the system _output_. We denote a _sequence_ of user
inputs as $\mathbf{r}=[r_{1},r_{2},\ldots,r_{n}]$ and a sequence of responses
as $\mathbf{o}=[o_{1},o_{2},\ldots,o_{n}]$. We describe $\mathbf{r}$ through a
set of features or random variables $R^{j}$; using superscripts $j$ to denote
a particular feature or set of features, e.g. timing, content, size of
individual actions $r$, or any other relationships therein. Moreover, the
user’s input $\mathbf{r}$ feeds a set of _public utility functions_ $h_{i}$
with ${h:\mathbf{R}\rightarrow\mathcal{Z}}$, where $\mathcal{Z}$ is the
universe of public utility function outcomes $z_{i}$, e.g. film
recommendations or traffic-aware driving directions, based on a user’s film
reviews and position on the road while driving, respectively, that other
(untrusted and potentially adversarial) users of the system can benefit from.

An adversary is interested in the input sequence $\mathbf{r}$ to obtain some
information $\mathbf{x}=g(\mathbf{r})$, where $\mathbf{x}$ represents e.g. the
type or frequency of actions a user performs, or any other information that
one may infer from the user’s input. Function
${g:\mathbf{R}\rightarrow\mathbf{X}}$ thus maps the universe of input
sequences $\mathbf{R}=\\{\mathbf{r}\\}$ to the universe
$\mathbf{X}=\\{\mathbf{x}\\}$. Allowing the adversary to obtain $\mathbf{x}$
invades the user’s privacy. Depending on its capabilities, the adversary may
be able to obtain $\mathbf{r}$ directly or indirectly, using adversarial
function $g_{h}$ to extract information about $\mathbf{r}$ from public utility
outcomes $z$ that derive from $\mathbf{r}$.

We account for the utility users derive and the privacy loss they incur in
from disclosing $\mathbf{r}$ (either directly or through $z$). The user
obtains _personal utility_ $u_{f}$ from functionalities $f_{i}$ so that
${u_{f}:\mathbf{R}\rightarrow\mathbb{R}^{+}}$. The user incurs privacy loss
$l$ so that ${l:\mathbf{R}\rightarrow\mathbb{R}^{+}}$. Moreover, the user also
“produces” _public utility_ by contributing to $z$ so that
${u_{h}:\mathbf{R}\rightarrow\mathbb{R}^{+}}$. _Public utility_ refers to
utility a user produces for everyone, including people she does not trust,
i.e. (potential) adversaries. We refer to users that produce public utility as
_utility producers_. Consider a service like Google Maps, which provides
functionalities $f_{i}$ such as route planning and navigation based on real-
time traffic conditions. To plan and navigate a route in real-time, a user
needs to input her location, desired destination and chosen means of transport
($r_{i}$). At the same time, Google relies on users’ location and navigation
data to calculate the time it takes to complete a route, obtain real-time
traffic conditions or detect roadblocks, among other elements involved in
route planning. Hence, users contribute with their data $\mathbf{r}$ to
improve the navigation service for everyone (including themselves). If we
consider that Google and other Maps’s users are non-trusted, potentially
adversarial —i.e. they may leak or abuse the information that other users
provide while using the service— then, we may refer to the utility these non-
trusted entities obtain from $\mathbf{r}$ as public utility.

Conversely, _personal utility_ refers to the utility an individual obtains
from $f_{i}$ exclusively for herself and for others she trusts. Consider a
Google Maps user who does not want Google to leverage her data to provide
utility to others, i.e. she wishes to obtain route recommendations for herself
without letting Google use her data to improve recommendations for everyone.
In this case, the user exclusively seeks _personal utility_ , i.e. she is a
_utility consumer_. Another example: a user that sends a private message to a
friend and intends that information to be of utility to no one besides herself
and her friend, whom she trusts. In short, users may exchange and reveal data
among a trusted group of relatives, friends or coworkers. These exchanges do
not represent public utility; rather, the utility users derive from disclosing
$\mathbf{r}$ to trusted peers is part of their personal utility. Public
utility exclusively derives from data disclosures to untrusted parties, e.g.
that the general public can benefit from. Whereas this decision may seem
arbitrary,222 Deciding which peers or entities a user trusts is in fact
entirely at the user’s or system designers’ own discretion.  it enables us to
establish a crisp separation between the disclosure requirements that either
type of utility imposes and the role of obfuscation in privacy engineering, as
we discuss in Sect. IV.

Figure 1: System and threat model with utility and privacy loss flows.

Figure 1 depicts the system and adversary model we have introduced in this
section: a user submits to the system an input sequence
$\mathbf{r}=[r_{1},r_{2},\ldots,r_{n}]$ and retrieves a sequence of outputs
$\mathbf{o}=[o_{1},o_{2},\dots,o_{n}]$, where $o_{i}=f_{i}(r_{i})$. As a
result, the user derives some _personal utility_ $u_{f}(\mathbf{r})$ for
herself. Moreover, the system feeds the user’s input $\mathbf{r}$ to a public
utility function $h$, releasing a public utility outcome $z$ that produces
some _public utility_ $u_{h}(\mathbf{r})$ for _everyone_ , including the user.
At the same time, by submitting $\mathbf{r}$ to the system, the user incurs
some privacy loss $l(\mathbf{r})$ due to two archetypal adversaries: one the
one hand, advesaries that have access to the system itself, capturing input
sequence $\mathbf{r}$ and obtaining some information
$\mathbf{x}=g(\mathbf{r})$; on the other hand, adversaries that exploit the
public utility outcome $z$ to some obtain information
$\mathbf{x}_{h}=g_{h}(z)$ about the user. Table I summarises the notation we
use throughout this paper.

Symbol Meaning |  | Symbol Meaning
---|---|---
$r$ |  User input/request |  | $\mathbf{r}$ |  Sequence $[r_{1},r_{2},\ldots,r_{n}]$
$\mathcal{R}$ |  Universe of user inputs |  | $\mathbf{R}$ |  Universe sequences $\mathbf{r}$
$R$ |  Random variable over $\mathbf{r}$ |  | $R^{j}$ |  Input sequence feature
$o$ |  Output/response, $o=f(r)$ |  | $\mathbf{o}$ |  Sequence $[o_{1},o_{2},\ldots,o_{n}]$
$\mathcal{O}$ |  Universe of outputs $o$ |  | $\mathbf{O}$ |  Universe of sequences $\mathbf{o}$
$f$ |  Personal functionality |  | $u_{f}$ |  Personal utility
$g$ |  Adversarial function |  | $l$ |  Privacy loss function
$h$ |  Public utility function |  | $u_{h}$ |  Public utility
$\mathbf{x}$ |  Adversarial function’s outcome, ${\mathbf{x}=g(\mathbf{r})}$ |  | $\mathbf{X}$ |  Universe of adversarial outcomes
$X$ |  Random variable over $\mathbf{x}$ |  | $\hat{\mathbf{r}}$ |  _Deobfuscated_ user input
$z$ |  Public utility outcome |  | $\mathcal{Z}$ |  Universe of $z$
$R^{u}$ |  Feature contributes to utility |  | $R^{\bar{u}}$ |  Feature _does not_ contribute to utility
$R^{l}$ |  Feature contributes to privacy loss |  | $R^{\bar{l}}$ |  Feature _does not_ contribute to privacy loss
$\Phi$ |  Obfuscation function |  | I |  Mutual information
$\mathcal{G}$ |  Information gain |  | $\mathbf{E}$ |  Expected estimation error
$\mathbf{q}$ |  Obfuscated sequence |  | $\mathbf{Q}$ |  Universe sequences $\mathbf{q}$
$Q$ |  Random variable over $\mathbf{q}$ |  | $w$ |  Obfuscated public outcome, $w=\Phi(z)$
$\mathbf{d}$ |  Sequence of _chaff_ |  |  |
|  |  |  |
TABLE I: Notation

##### Obfuscation tools

An _obfuscation tool_ (OT) modifies $\mathbf{r}$ or $z$ with the aim of
limiting or preventing privacy loss. To that end, an obfuscation mechanism
$\Phi$ modifies $\mathbf{r}$ or $z$ to produce an obfuscated sequence
${\mathbf{q}=\Phi(\mathbf{r})}$ or obfuscated output $w=\Phi(z)$,
respectively. OTs may rely on different forms of obfuscation, such as the
generation of chaff (i.e. fake user activity) or, conversely, the suppression
or discarding of user inputs [8, 18]; OTs may also modify individual user
inputs $r_{i}$ into $q_{i}$ by generalising or adding random noise to their
values [8, 19, 20].

As a result, the adversary observes an obfuscated input $\mathbf{q}$ or
obfuscated output $w$ that should ideally leak no or less information about
$\mathbf{x}$, so that $l(\mathbf{q})<l(\mathbf{r})$ (respectively
${l(w)<l(z)}$). However, obfuscation impacts utility too, with personal and
public utility becoming $u_{f}(\mathbf{q})$ and $u_{h}(\mathbf{q})$,
respectively.

Figure 2: Process flow of obfuscation tools, user deployment.

Figure 2 depicts the deployment of an OT by the user. Alternatively, Fig. 3
depicts the service provider obfuscating public utility outcomes, which
implicitly assumes a trusted service provider that implements obfuscation on
behalf of its users, e.g. the trusted data curator that releases noisy
statistics in the classic differential privacy model [21]. Still, users may
deem insufficient the level of protection that results from service provider
obfuscation, leading to the deployment of obfuscation by both users and
service providers, as Fig. 4 shows. For the sake of brevity, in this paper we
focus on the first scenario, i.e. user-deployment of obfuscation tools, as
that offers protection against both types of adversaries so that most of the
observations and insights we provide in this paper implicitly extend to the
latter two scenarios (yet we offer additional clarification where
appropriate).

Figure 3: Process flow of obfuscation tools, service provider deployment.
Figure 4: Deployment of OTs by both user and service provider.

##### Adversary model

As we have just mentioned, we consider two types of adversaries, depending on
whether they have access to either $\mathbf{q}$ or $w$. We focus on the first
type of adversary but the assumptions and notation introduced below trivially
extrapolate to the second _‘external’_ type of adversary.

The adversary’s goal is to obtain ${\mathbf{x}=g(\mathbf{r})}$.333 Analogously
${\mathbf{x}_{h}=g_{h}(z)}$ for the ‘external’ adversary.  The adversary knows
that an OT is in place, i.e. that ${\mathbf{q}=\Phi(\mathbf{r})}$. The
adversary has full knowledge about the OT’s design, i.e. it can test and
simulate runs of the OT or perform an analytical evaluation of its obfuscation
mechanism $\Phi$, e.g. to determine the OT’s conditional probability
distribution $P(\,Q\;|\;R\,)$, where $R$ is a random variable (r.v.) that
describes users’ input sequences $\mathbf{r}$ and $Q$ the r.v. that describes
obfuscated sequences $\mathbf{q}$. We make no assumptions about the
adversary’s _background knowledge_ or _auxiliary_ information on users, which
may relate to a particular individual, to an _“average”_ user or to the
general population.

Lastly, the adversary is _strategic_ , i.e. it attempts to retrieve
$\mathbf{x}$ _“undoing”_ obfuscation to the best of its abilities. The
adversary thus recovers an approximation $\mathbf{\hat{x}}$ so that, ideally,
$\mathbf{\hat{x}}=\mathbf{x}$. Note that Figures 2 through 4 implicitly depict
the adversary’s attack whereby it obtains $\mathbf{\hat{x}}$ and $\hat{z}$
from $\mathbf{q}$ and $w$, respectively. Still, the adversary is honest-but-
curious (HbC), i.e. it does not interfere with users’ service requests
—regardless of its ability to do so—; it does not drop, delay or modify any
(obfuscated) user actions. As an example of this kind of adversary, we
consider an _honest-but-curious adversarial service provider_ throughout this
paper.

##  III Evaluating obfuscation tools

This section introduces a framework for the evaluation of OTs. We unpack key
assumptions underlying privacy measures for the design and evaluation of OTs.
To that end, we distinguish between two approaches to measuring the level of
privacy protection OTs afford: _mechanism-centred_ and _attack-centred_. A
mechanism-centred approach evaluates OTs with independence from a particular
adversary or attack strategy, they focus on the relation between an OT’s
inputs and outputs, rather than on the knowledge or exploits of a particular
adversary; conversely, attack-centred approaches focus on more detailed
adversaries and attacks. Mechanism-centred evaluation (MCE) measures relate to
the OT’s _leakage_ , this is, how much information OTs leak or disclose
regardless of the ability of an adversary to exploit that information. Attack-
centred evaluation (ACE) measures on the other hand relate to adversarial
_retrieval_ , this is, the extent to which an adversary takes advantage of the
information an OT leaks to recover $\mathbf{x}$. Figure 5 illustrates how MCE
focuses on the relationship between an OT’s input $\mathbf{r}$ and output
$\mathbf{q}$, abstracting away from a particular attack, whereas ACE does take
into account the adversary’s knowledge and attack, capturing the combined,
intertwined effect of obfuscation tool and adversarial attack, i.e. evaluating
an OT’s ability to mitigate privacy loss through a measure of adversarial
success.

Figure 5: Mechanism-centred and attack-centred evaluation.

###  III-A Mechanism-centred analysis

To illustrate the type of privacy measures that fall within mechanism-centred
analysis, we review measures of _indistinguishability_ and measures of
_information leakage_.

####  III-A1 Indistinguishability

With its roots in cryptography, indistinguishability measures an OT’s ability
to generate obfuscated inputs $\mathbf{q}$ so that any sequence $\mathbf{r}$
could have led to $\mathbf{q}$, rendering an adversary unable to determine the
original input $\mathbf{r}$ with higher than random chance, i.e. based on the
_prior_ probability $P(\,\mathbf{r}\,)$ alone.

Several works have proposed privacy definitions based on the notion of
indistinguishability [22, 23], the most prominent to date being _differential
privacy_ (DP) [24]. Initially defined as $\epsilon$-indistinguishability, DP
requires that the outcome $\mathbf{q}=\Phi(\mathbf{r})$ is equally likely
(within a multiplicative factor $e^{\epsilon}$) if the input to the function
were an input $\mathbf{r}^{\prime}$, for all pairs of inputs $\mathbf{r}$ and
$\mathbf{r}^{\prime}$ and all possible $\mathbf{q}\in\mathbf{Q}$. An
obfuscation tool thus ensures $\epsilon$-indistinguishability if the
probability of any input $\mathbf{r}$ or $\mathbf{r}^{\prime}$ leading to
obfuscated input $\mathbf{q}$ is bounded by a multiplicative factor
$e^{\epsilon}$, namely:

$\sup_{S\in\mathbf{Q};\;\mathbf{r},\mathbf{r}^{\prime}\in\mathbf{R}}\frac{\Phi(S\;|\;\mathbf{r})}{\Phi(S\;|\;\mathbf{r}^{\prime})}\leq
e^{\epsilon}$ (1)

Note that we do not specify that $\mathbf{r}$ and $\mathbf{r}^{\prime}$ differ
on at most in one record or action $r$ as the classic differential privacy
definition does. In fact, since we focus on the user deploying an obfuscation
tool, Eq. 1 corresponds to a definition of _local_ differential privacy [25].
Alternatively, a (trusted) curator releasing public outputs $z$ may adopt a
differentially-private obfuscation mechanism that satisfies:

$\sup_{S\in\mathcal{Z};\;D,D^{\prime}\in\mathbf{R}^{N}}\frac{\Phi(S\;|\;D)}{\Phi(S\;|\;D^{\prime})}\leq
e^{\epsilon}$ (2)

where $D$ and $D^{\prime}$ represent two datasets that differ at most on the
contribution of one individual, e.g. $D$ could be the data the service
provider has collected on every user,
$D=[\mathbf{r}_{1},\mathbf{r}_{2},\ldots,\mathbf{r}_{N}]$ so that $D$ and
$D^{\prime}$ differ at most on the sequence of actions $\mathbf{r}$ of any
user.

Many alternatives and variations of $\epsilon$-indistinguishability or DP
exist, such as statistical distance (an _additive_ —as opposed to
_multiplicative_ — measure of indistinguishability), relaxations such as
$(\epsilon,\delta)$-differential privacy and
$(\epsilon,\ell,\delta)$-differential privacy, the particular choice depending
on the desired stringency of the measure [24, 26, 27, 28]. Researchers have
also proposed proposed variants for specific contexts, such as location
privacy or anonymous communications [16, 29].

The key point is that these indistinguishability measures do not depend on how
the adversary attacks or what the adversary knows: they measure privacy loss
by focusing on the inputs and outputs of an OT alone, thereby providing a
measure of privacy independent from adversarial knowledge.

####  III-A2 Information leakage

We may conceptualise OTs as communication channels through which the user
transmits a sequence of messages $\mathbf{r}$ to the adversary, who receives a
_noisy_ sequence $\mathbf{q}$, as Fig. 6 shows. Information theory enables us
to measure the amount of information the channel (i.e. the OT) _leaks_ , i.e.
how much information $\mathbf{q}$ provides about $\mathbf{r}$. If the channel
is _perfectly noisy_ , $\mathbf{q}$ leaks no information about input
$\mathbf{r}$: it is no easier for an adversary to determine $\mathbf{x}$ after
obtaining $\mathbf{q}$ than before, i.e. with _prior information_ about
$\mathbf{x}$ alone. Conversely, if the channel introduces no noise, obfuscated
input $\mathbf{q}$ univocally reveals the OT’s input $\mathbf{r}$ —so the
adversary can trivially compute $\mathbf{x}$.

Figure 6: An OT as a noisy channel. Output sequences $\mathbf{q}$ result from
the obfuscation of $\mathbf{r}$.

To measure the amount of information obfuscated sequence $\mathbf{q}$ leaks
about $\mathbf{r}$, we compute the _mutual information_ $\text{I}(R;Q)$:

$\begin{split}\text{I}(R;Q)&\equiv\text{H}(R)-\text{H}(R\;|\;Q)=\\\
&=\sum_{\mathbf{r}\in R}\sum_{\mathbf{q}\in
Q}P(\,\mathbf{r},\mathbf{q}\,)\log\frac{P(\,\mathbf{r},\mathbf{q}\,)}{P(\,\mathbf{r}\,)P(\,\mathbf{q}\,)}\end{split}$
(3)

Mutual information (MI) provides a measure of the channel’s information
leakage, but only _for a particular probability distribution_ $P(\,R\,)$ [30,
31]; MI says little about the performance of an OT in general, this is, for
any probability distribution other than $P(\,R\,)$. To determine the OT’s
information leakage with more generality, we consider mutual information
between inputs and outputs to the OT over _all_ possible input probability
distributions, namely, the channel’s _capacity_ , which is the maximum
information leakage over all possible probability distributions of the input
r.v. $R$. Formally:

$\begin{split}C=\sup_{P_{R}(\mathbf{r})}\text{I}(R;Q)\end{split}$ (4)

Ideally, a perfect obfuscator has $C=0$, i.e. it leaks no information on no
matter what input probability distribution. Channel capacity thus provides a
tight upper bound of an OT’s information leakage.444 Yet, as Chatzikokolakis
et al. concede, whenever we are able to accurately determine the probability
distribution $P(\,R\,)$, mutual information provides a tighter measure of
information leakage as we do not need to consider input distributions under
which the obfuscator performs worse [30].

Similarly to indistinguishability measures, there are alternative measures of
information leakage, such as min-leakage and min-capacity or generalised
notions based on gain functions such as $g$-leakage, that provide slightly
different measures of information leakage [32, 33]. Appendix -A provides a
discussion on alternative measures of information leakage that do not rely on
Shannon’s entropy.

#### Independence from adversarial knowledge

Under certain assumptions, mechanism-centred evaluation (MCE) provides privacy
guarantees _independently from adversarial knowledge_. Differentially-private
mechanism design represents a prominent example of attempting to enforce such
a property. The guarantee differential privacy offers —namely, that the
probability of a privacy breach will be more or less the same whether or not a
user participates in the system— holds, under certain assumptions about the
data-generation process, regardless of what the adversary knows [24, 34].
Hence, it represents a property of the mechanism itself, unrelated to what the
adversary does or knows [21]. Similarly, a channel’s capacity measures the
maximum amount of leaked information, providing an upper bound on what the
adversary may feasibly extract from the OT. Information-theoretical measures
do however depend on the mechanism’s input data probability distribution;
capacity is not independent from the input data probability distribution per
se, yet by considering _all possible_ probability distributions, it also
becomes independent from the adversary’s knowledge [35].

#### Indistinguishability or information leakage?

Either type of privacy measure provides different types of guarantees.
Multiplicative measures of indistinguishability ensure a minimum level of
privacy for each particular user input; capacity on the other hand provides an
_average_ of the amount of information the OT leaks, but no bounds on the
distinguishability between any two inputs: the OT may expose some users’
inputs $\mathbf{r}$ at the same time that it leaks very little on others. In
fact, $\epsilon$-indistinguishability entails bounds on information leakage
but the opposite is not generally true [36, 37, 35].

Hence, measures like $\epsilon$-indistinguishability are best suited to deal
with scenarios with stringent privacy requirements, i.e. where privacy
guarantees must hold for every OT’s user and against any possible adversary.
However, it is often too expensive or too disruptive to guarantee
$\epsilon$-DP in many settings, e.g. in the context of location privacy [38,
39]. By providing an average measure of the protection an OT affords,
information theoretical measures can better accommodate trade-offs between
privacy and utility or cost, e.g. by ensuring an acceptable average level of
privacy protection, even if that means subjecting specific users to greater
privacy loss.

However, both types of measures, being detached from any particular adversary
or attack, are often hard to interpret [39]. Enforcing differential privacy,
it is unclear which value to assign to $\epsilon$ or $\delta$ other than
$\epsilon=\delta=0$ when we wish (and it is feasible) to prevent _any_
information leakage. The privacy guarantee
${\epsilon\text{-indistinguishability}}$ provides is _relative_ , i.e. it
holds regardless of the adversary’s background knowledge, yet does not say
what an adversary armed with sufficient knowledge actually learns. To
determine the _“absolute”_ level of privacy, we must consider a particular
adversary with a concrete instance of background knowledge and attack strategy
[15]. Information-theoretic measures on the other hand do capture an absolute
level of privacy, i.e. the number of bits of information leakage; however, it
is still hard to interpret that number of bits as the risk an OT’s user faces,
e.g. the adversary may have enough prior information that in spite of how
little information the OT leaks, the user’s privacy is breached. Conversely,
by focusing on specific adversaries and attack strategies, attack-centred
evaluation (ACE) represents an easier-to-interpret approach to privacy
measures, arguably better capturing the actual level of user privacy [6, 15].

###  III-B Attack-centred analysis

We consider two attack-centred evaluation (ACE) measures: _information gain_
and _expected estimation error_.

####  III-B1 Information gain

Information leakage measures the dependence between OTs’ inputs and outputs
through the joint probability distribution $P(\,R,Q\,)$. As Chatzikokolakis et
al. note, we may decompose $P(\,R,Q\,)=P(\,Q\;|\;R\,)\cdot P(\,Q\,)$, where
$P(\,Q\;|\;R\,)$ is a parameter from the OT that does not depend on the input
probability distribution, enabling an adversary to, upon having observed an
output $\mathbf{q}$, update the probability of input $\mathbf{r}$ using
Bayes’s rule as [30]:

$P(\,\mathbf{r}\;|\;\mathbf{q}\,)=\frac{P(\,\mathbf{q}\;|\;\mathbf{r}\,)P(\,\mathbf{r}\,)}{\sum_{i}P(\,\mathbf{q}\;|\;\mathbf{r}_{i}\,)P(\,\mathbf{r}_{i}\,)}$

To recover the _‘correct’_ posterior probability
${P(\,\mathbf{r}\;|\;\mathbf{q}\,)}$, however, the adversary needs to know the
correct prior probability $P(\,\mathbf{q}\,)$, and this is not necessarily
always the case. Adversaries may possess incorrect priors that (mis)lead them
to estimate a wrong posterior $P_{\beta}(\mathbf{r}\;|\;\mathbf{q})$ [40, 41].
Let us denote an adversary’s _belief_ through the subindex $\beta$. When the
OT’s output $\mathbf{q}$ contradicts an adversary’s prior and outputs a
sequence $\mathbf{q}$ so that, e.g.
$P(\,\mathbf{q}\;|\;\mathbf{r}_{\mathbf{x}}\,)=0$ while
$P_{\beta}(\mathbf{r}_{\mathbf{x}})\rightarrow 1$, the adversary’s uncertainty
increases, and yet it gains information to correct her erroneous belief [40].
Conversely, when the OT’s output $\mathbf{q}$ strongly supports an erroneous
prior, the adversary may wrongly recover with high certainty an input
$\hat{\mathbf{r}}_{\mathbf{x}}\neq\mathbf{r}_{\mathbf{x}}$ or, by chance, the
actual input $\mathbf{r}_{\mathbf{x}}$.555 These artifacts however tend to
disappear with an increasing number of observations, as the OT leaks more
information.

Moreover, Franz et al. warn against adversaries that obtain side knowledge
beyond what the OT’s output leaks, even if, as Hamadou et al. indicate, such
side knowledge may also be erroneous [42, 43]; e.g. adversaries may possess
background knowledge on a particular OT’s user $v$, enabling them to obtain
more information about her input $\mathbf{r}_{v}$ than what adversaries that
only have access to the population’s prior $P(\,R=\mathbf{r}\,)$ and
obfuscated input $\mathbf{q}$ are able to.

To incorporate an adversary’s (potentially inaccurate) prior and side
information into the evaluation, previous authors have resorted to
_information gain_ , defined as the _Kullback-Leibler divergence_
($D_{\text{KL}}$) between an adversary’s _belief_ —that includes both prior
and side knowledge— and the actual OT’s input value $\mathbf{r}$ before and
after observation [43]. Let $b(\mathbf{r})$ and $b(\mathbf{r}|\mathbf{q})$
represent the adversary’s beliefs that an OT obfuscates some input
$\mathbf{r}$ before and after observing the output $\mathbf{q}$, i.e.
$b(\mathbf{r})=P_{\beta}(\mathbf{r})$ and
$b(\mathbf{r}|\mathbf{q})=P_{\beta}(\mathbf{r}\;|\;\mathbf{q})$, respectively.
Let $\delta(\mathbf{r})$ represent the degenerate probability distribution
$P(\,\mathbf{r}\,)$ taking values $P(\,\mathbf{r}\,)=1$ when
$\mathbf{r}=\mathbf{r}_{\mathbf{x}}$ (the actual input to the OT) and
$P(\,\mathbf{r}\,)=0$ otherwise. We obtain the adversary’s information gain
$\mathcal{G}$ as:

$\mathcal{G}=D_{\text{KL}}(\,\delta(\mathbf{r})\,||\,b(\mathbf{r})\,)-D_{\text{KL}}(\,\delta(\mathbf{r})\,||\,b(\mathbf{r}|\mathbf{q})\,)=\\\
=\log(P_{\beta}(\mathbf{r}_{\mathbf{x}}|\mathbf{q}))-\log(P_{\beta}(\mathbf{r}_{\mathbf{x}}))$
(5)

with logarithm base $2$ giving information gain in _bits_.666 Clarkson et al.
provide an intuitive interpretation of information gain measured in bits,
namely, _“ $k$ bits of leakage correspond to a $k$-fold doubling of the
probability that the attacker ascribes to reality”_ [41].

Information gain thus provides a measure that is specific to an adversary with
a particular instance of prior information and side knowledge; it does not
capture an OT’s performance against adversaries with more or less knowledge
—accurate or otherwise. While information leakage equals information gain if
the adversary has a correct prior and no additional side knowledge, both
measures conceptually differ in that information gain measures what the
adversary learns and information leakage what the OT leaks. The former factors
in adversarial beliefs, whereas the latter is a function of the inputs and
outputs to the channel alone.

Adversaries with incorrect prior knowledge are in general of lesser concern in
OTs’ design, as wrong prior adversarial _beliefs_ hinder adversaries’ ability
to recover users’ data.777 Hamadou et al. [44] show that min-conditional
entropy is always smaller than or equal to the min-conditional entropy of an
adversary with wrong beliefs, i.e.
$\text{H}_{\infty}(R\;|\;Q)\leq\text{H}_{\infty}^{\beta}(R\;|\;Q)$, with
$\text{H}_{\infty}^{\beta}$ representing the uncertainty of an adversary whose
prior _belief_ $P_{\beta}(\mathbf{r})$ is incorrect. On the other hand,
adversaries with accurate side knowledge pose a greater threat than those
without, yet OTs’ designers are unlikely to be able to precisely determine the
side knowledge adversaries have or may be able to acquire in the future. In
general, designing a tool with a particular instance of adversarial beliefs in
mind renders OTs vulnerable to adversaries with beliefs other that what
designers account for. However, information gain still assists targeted
analyses when we wish to ascertain the extent to which particular adversaries
may breach users’ privacy, e.g. as part of an audit or privacy impact
assessment.

####  III-B2 Expected estimation error

In the context of their work on privacy-preserving location based services
(LBSs), Shokri et al. argue that _«[n]either the uncertainty metric nor the
inaccuracy metric, however, quantify the privacy of the users. What matters
for a user is whether the attacker finds the correct answer to his attack, or,
alternatively, how close the attacker’s output is to the correct answer»_ [6].
Shokri et al.’s definitions of _uncertainty_ and _inaccuracy_ loosely map to
this framework’s _information leakage_ and _information gain_ , respectively.
Their claim echoes our previous observations on the difficulty of interpreting
measures that are detached from a specific adversary or attack in return for
generality: avoiding assumptions about adversarial beliefs and attack
strategies prevents us from estimating how successful the adversary is at
retrieving $\mathbf{r}$. Shokri et al. hence propose _expected estimation
error_ , a probabilistic measure of how _close_ the adversary gets to
$\mathbf{r}$, incorporating a definition of ‘how bad’ it is that the adversary
recovers $\hat{\mathbf{r}}$ instead. We note that none of the previous
measures we have reviewed so far consider the sequence $\hat{\mathbf{r}}$ the
adversary _actually_ recovers or the outcome
$\mathbf{\hat{x}}=g(\hat{\mathbf{r}})$ (as opposed to
$\mathbf{x}=g(\mathbf{r})$) that the adversary ultimately obtains; the
measures we have hitherto introduced abstract away from the adversary’s
function $g$ to provide a measure independent from it.

We borrow Shokri et al.’s definitions of _expected estimation error_ and
_expected distortion privacy_ to define a slight variant of the latter [6,
15]. Our goal is to highlight the implications of incorporating the
adversary’s beliefs, the adversary’s function $g$ and a measure of adversarial
success $\ell$ to the evaluation of OTs.888We refer the reader to Appendix -B
for a detailed explanation of how the adaptation of expected distortion
privacy introduced in this section differs from Shokri’s [15]. Let
$P(\,\mathbf{x}\,)$ represent the probability of the adversary’s target, i.e.
$P(\,\mathbf{x}\,)=P(\,g(\mathbf{r})\,)$, and
$P(\,\mathbf{q}\;|\;\mathbf{x}\,)$ represent the conditional probability that
the OT outputs $\mathbf{q}$ given that $\mathbf{r}$ maps to
$\mathbf{x}=g(\mathbf{r})$. Further, let
$P(\,\mathbf{\hat{x}}\;|\;\mathbf{q}\,)$ represent the probability
distribution that results from the attack strategy _and_ (estimated) prior
knowledge the adversary relies on to recover an estimated $\mathbf{\hat{x}}$
from an observed sequence $\mathbf{q}$. Lastly, let
$\ell(\mathbf{\hat{x}},\mathbf{x})$ represent the distance at which
$\mathbf{\hat{x}}$ and $\mathbf{x}$ are, this distance according to the user’s
privacy requirements, i.e. the greater $\ell(\mathbf{\hat{x}},\mathbf{x})$ is,
the better for user privacy. We compute expected estimation error,
$\mathbf{E}$, as:

$\mathbf{E}=\sum_{\mathbf{x}}P(\,\mathbf{x}\,)\sum_{\mathbf{q}}P(\,\mathbf{q}\;|\;\mathbf{x}\,)\sum_{\mathbf{\hat{x}}}P(\,\mathbf{\hat{x}}\;|\;\mathbf{q}\,)\cdot\ell(\mathbf{\hat{x}},\mathbf{x})$
(6)

Eq. 6 incorporates previous measures’ assumptions about an OT’s inputs and
operation, and further integrates the adversary’s beliefs and attack strategy.
The first two summations
$\sum_{\mathbf{x}}P(\,\mathbf{x}\,)\sum_{\mathbf{q}}P(\,\mathbf{q}\;|\;\mathbf{x}\,)$,
characterise the channel as information leakage measures do, albeit assuming a
single input probability distribution, thus with the limitations and decreased
generality of mutual information as opposed to capacity (which considers all
possible probability distributions) and indistinguishability (which is
independent from the prior $P(\,\mathbf{r}\,)$). The term
$\sum_{\mathbf{\hat{x}}}P(\,\mathbf{\hat{x}}\;|\;\mathbf{q}\,)$ captures the
attack strategy of the adversary as the probability that the adversary
recovers $\mathbf{\hat{x}}$ after updating its prior knowledge with its
observation of obfuscated input $\mathbf{q}$. Lastly, the term
$\ell(\mathbf{\hat{x}},\mathbf{x})$ incorporates a definition of how
$\mathbf{\hat{x}}$ contributes to user privacy, namely, it measures how
_better_ it is for users that the adversary recovers $\mathbf{\hat{x}}$ as
opposed to $\mathbf{x}$ [15].

Expected estimation error as defined in Eq. 6 departs from previous measures
in two significant ways. First, it incorporates a distance
$\ell(\mathbf{\hat{x}},\mathbf{x})$ that unambiguously defines the advantages
of having an adversary recovering $\mathbf{\hat{x}}$ as opposed to
$\mathbf{x}$. Note that previous measures, as we have defined them, are
_agnostic_ to what it means that an adversary recovers either
$\mathbf{\hat{x}}_{1}$ or $\mathbf{\hat{x}}_{2}$ as long as they are different
from $\mathbf{x}$, i.e. they do not consider whether it is better or worse
that the adversary recovers $\mathbf{\hat{x}}_{1}$ or $\mathbf{\hat{x}}_{2}$
as opposed to $\mathbf{x}$. That _“semantic agnosticism”_ reinforces their
generality at the cost of expressiveness, i.e. an OT’s information leakage
$\text{I}(R;Q)$ depends on the probability distributions $P(\,R\,)$,
$P(\,Q\,)$ and the joint $P(\,R,Q\,)$, but it is oblivious to the actual
values that those random variables take and the metric space we may choose to
represent them on.999 Having said that, it is possible to incorporate
assumptions about the meaning of $R$’s and $Q$’s values by e.g. grouping them
in bins. Second, we note that we could express expected estimation error (EEE)
as a function of the distance $\ell(\mathbf{r},\hat{\mathbf{r}})$ instead of
$\ell(\mathbf{x},\mathbf{\hat{x}})$. With the latter we choose to emphasise
the post-processing that “raw” data $\mathbf{r}$ or $\hat{\mathbf{r}}$ undergo
at the hands of the adversary, such as the inference of user attributes which
are not explicit in the observed data $\mathbf{r}$ per se, e.g. an adversary
may collect users’ location data $(\mathbf{r})$ to determine their political
affiliation ($\mathbf{x}_{1}$) and purchasing power ($\mathbf{x}_{2}$),
neither explicit in $\mathbf{r}$, but which the adversary extracts through
inference functions $g_{1}$ and $g_{2}$, respectively.101010Expressing EEE in
terms of $\ell(\mathbf{r},\hat{\mathbf{r}})$ is a perfectly valid alternative.
This adds another layer of assumptions about the mapping between $\mathbf{r}$
and $\mathbf{x}$ through $g$ which previous measures are also independent (and
agnostic) from.

EEE indeed represents the last step in a sequence of measures from more
abstract and general —less assumptions, less details about the adversary—, to
more specific and concrete —more assumptions, more details about the
adversary. We depict this idea in Fig. 7. MCE characterises the extent to
which an OT’s protects privacy with independence of an adversary’s side
knowledge and attack strategies. ACE measures on the other hand incorporate
particular details of an adversary: information gain considers a particular
instance of background knowledge, while EEE further considers the particular
$\mathbf{\hat{x}}$ the adversary recovers, thereby implying that not every
$\mathbf{\hat{x}}$ the adversary recovers is equally _bad_ for the user, which
in turn depends on a particular adversarial post-processing function.

Figure 7: Hierarchy of measures. Less assumptions confer more generality.

Yet EEE as an absolute measure of privacy conflates the effect on users’
privacy of the obfuscation mechanism with the adversary’s prior and side
knowledge as well as its profiling function $g$. EEE does not compare users’
privacy before and after the adversary observes an obfuscated user input
$\mathbf{q}$. An adversary with an exceptionally good prior may perform
equally well without $\mathbf{q}$, highlighting the impossibility of absolute
disclosure prevention that motivates differential privacy [45]. Hence, even if
EEE provides a good measure of privacy against a particular adversary, it does
not properly acknowledge the OT’s ability to prevent privacy breaches.

###  III-C MCE or ACE?

Disagreements between proponents of different types of measures abound in the
literature. Andrés et al. argue that EEE is _“explicitly defined in terms of
the attacker’s prior knowledge, and is therefore unsuitable for scenarios
where the prior is unknown”_ [16]; they propose _geo-indistinguishability_ , a
measure of location privacy based on differential privacy. On the other hand,
as a relative measure, the $\epsilon$ in $\epsilon$-geo-indistinguishability
says very little about what the adversary actually knows about the location of
a user, as that requires a specific evaluation that takes an adversary’s prior
and side knowledge into consideration. Similarly, Li et al. [17] argue, in the
context of website fingerprint defence evaluation, that _“validating
[defences] by accuracy alone is flawed […] when accuracy is low, its
corresponding information leakage is far from certain”_ , and propose mutual
information as a measure of information leakage. Li et al.’s critique echoes
our previous point about the difference between MCE and ACE. The latter
conflate the protection an OT affords with the adversary’s prior knowledge and
attack strategy. Adversaries may successfully infer $\mathbf{x}$ either due to
a weak OT that reveals too much or because of robust, prior side information
that enables them to obtain $\mathbf{x}$ regardless of what little information
an OT leaks, thus underestimating the strong privacy protection the OT would
provide in less hopeless scenarios. Conversely, adversarial failure may result
either from a robust OT or from flawed side information and a suboptimal
attack strategy, the latter leading to the overestimation of an OT’s
performance.

Hence, the choice between MCE and ACE depends on how much generality and
stringent a measure of privacy we seek. MCE measures provide stronger, more
general privacy guarantees as they do not rest upon specific assumptions on
adversarial knowledge, i.e. they are resilient to changes in the attack the
adversary deploys and the knowledge it has. An OT’s capacity ($C$) does not
depend on the side knowledge an adversary has; neither do differential privacy
bounds. MCE measures’ generality and independence from contextual details
makes them suitable as constraints or protection goals in OT’s design, i.e. as
privacy bounds that OTs must generally satisfy. However, such generality comes
at the expense of expressiveness: MCE measures do not capture what particular
adversaries actually learn or retrieve. Conversely, by incorporating specific
details about the adversary, ACE provides more expressive measures of privacy
loss. However, this specificity often renders ACE measures a poor choice when
it comes to imposing generic privacy bounds: because they depend on
particularities of the adversary, such as its background knowledge, they
cannot generally hold for _every_ adversary, e.g. imposing that an OT
guarantees a maximum expected estimation error is impossible against
adversaries with enough background knowledge, who may violate such constraints
armed with side knowledge alone (i.e. without exploiting the information the
OT leaks). Hence, ACE measures are best suited to determine the threat that
particular adversaries pose to OTs, to evaluate OTs’ deployment in particular
contexts, taking into account publicly available information that adversaries
may exploit or side-channel leakages that MCE is oblivious to.

Lastly, we note that the selection of measures we have provided in this
section has allowed us to illustrate the differences between the two types of
analyses, _mechanism-centred_ and _attack-centred_ , yet this set of measures
is not comprehensive, with possible variations or combinations of the above
also possible, depending upon the particular context or OT under evaluation.
Moreover, the conceptual separation between mechanism-centred and attack-
centred evaluation is not always sharply delineated; some measures elude or
straddle this binary classification, e.g. in the next section we resort to
mutual information $\text{I}(R^{j},X)$ between a user input $\mathbf{r}$’s
features and the adversary’s target $\mathbf{x}$ as a measure of information
leakage that incorporates assumptions about the adversarial function $g$. In
so doing, we lose some of the generality that abstracting away from a
particular function $g$ confers, but we keep some generality by refraining
from focusing on a concrete attack strategy or instance of background
knowledge. In short, the separation between MCE and ACE is not always clear-
cut in practice; rather, it is continuum or spectrum that ranges from the most
broad and generic measures that avoid most assumptions about the adversary to
the most specific measures that focus on very concrete attackers.

##  IV Obfuscation and privacy engineering

The previous section examines how we can measure the level of privacy loss $l$
that OTs prevent. In this section, we more generally examine the role of
obfuscation in privacy engineering. To that end, we explore the relationship
between utility and privacy loss, distinguishing two types of obfuscation,
utility-preserving and utility-degrading, and their respective roles as part
of the privacy engineering toolkit.

###  IV-A Utility-preserving and utility-degrading obfuscation

We distinguish between two types of obfuscation: _utility-degrading_ and
_utility-preserving_. Utility-degrading obfuscation (UDO) reduces users’
privacy loss at the expense of utility. Formally:

$\Phi(\mathbf{r})=\mathbf{q}:l(\mathbf{q})\leq l(\mathbf{r})\wedge
u(\mathbf{q})<u(\mathbf{r})$ (7)

Utility-preserving obfuscation (UPO) modifies $\mathbf{r}$ to reduce users’
privacy loss while preserving utility. Formally:

$\Phi(\mathbf{r})=\mathbf{q}:l(\mathbf{q})\leq l(\mathbf{r})\wedge
u(\mathbf{q})=u(\mathbf{r})$ (8)

Based on the decomposition of a user’s input $\mathbf{r}$ into features or
random variables $R^{j}$ as we propose in Sect. II, we observe the following.
First, to protect a user’s privacy, there is no need to obfuscate features
$R^{\bar{l}}$ that provide no information about $X$, with $X$ the random
variable that describes the adversary’s target $\mathbf{x}$, i.e. in terms of
information leakage, we refer to features
${R^{\bar{l}}:\text{I}(X;R^{\bar{l}})=0}$.111111 Note how this formulation
implicitly incorporates assumptions about the adversarial function $g$ that
maps inputs $\mathbf{r}$ to targets $\mathbf{x}$. This is not strictly
necessary; alternatively we may (rather trivially) refer to features
${R^{\bar{l}}:\text{I}(R^{l};R^{\bar{l}})=0}$. Indeed, determining that
features $R^{\bar{l}}$ do not provide information about $X$ depends on a set
of assumptions about the underlying _data generation process_ and the
adversarial function $g$ [46]. Such assumptions may however not hold in
practice. To achieve the most stringent privacy guarantees, we may assume an
arbitrary data generation process whereby every feature $R^{u}$ provides
information about $\mathbf{x}$, i.e. $R:\forall R^{u},\text{I}(X\,;\,R^{u})>0$
according to an arbitrary conditional probability distribution
$P(X\;|\;R^{u})$.  This holds regardless of whether $R^{\bar{l}}$ provide
utility or not, as these features bring the adversary no closer to obtaining
$\mathbf{x}$. Second, modifying features $R^{\bar{u},l}$ that leak information
about $\mathbf{x}$ but which functions $f_{i}$ and $h_{i}$ are oblivious to
(so that outcomes $o$ and $z$ do not depend on $R^{j}$) always represents UPO.
We denote this set of features as $R^{\bar{u},l}$ as opposed to the set of
features $R^{u,l}$ that do intervene in the computation of either $f_{i}$ or
$h_{i}$ _and_ leak information about $X$. Obfuscating $R^{\bar{u},l}$ does not
however necessarily lead to decreased privacy loss, as $R^{\bar{u},l}$ may
provide redundant information that the adversary can extract from $R^{u,l}$
alone. The set of features $R^{u,l}$ thus represents a major point of
contention in obfuscation tools’ design, as they _may_ force a trade-off
between utility and privacy. We examine the conditions that enable us to
escape that trade-off in Sect. IV-B. Figure 8 represents the decomposition of
the user input $\mathbf{r}$ into features that intervene in utility and
privacy loss.

Figure 8: Decomposing $\mathbf{r}$ into features relevant to utility and
privacy loss.

###  IV-B Factoring in utility: disclosure requirements

We observe that if features $R^{u,l}$ contribute to personal utility and
privacy loss, there is no inherent trade-off between privacy and _personal_
utility $u_{f}$. The system’s architecture may impose such a trade-off, but it
should be theoretically possible to avoid it with an alternative architecture,
as personal utility alone does not, by definition, require disclosures to
untrusted parties. Conversely, public utility imposes a trade-off with privacy
as long as it depends on features $R^{u,l}$ that leak information about $X$,
as producing public utility inherently requires that users disclose
information to untrusted, adversarial parties.

To illustrate how personal utility does not fundamentally require information
leakage, let us consider a video streaming service, such as YouTube, and a set
of users that seek to obtain _only_ personal utility from this service, i.e.
they want to watch a set of videos without producing any public utility. As
per the current (privacy-unfriendly) system architecture, YouTube requires
users to disclose the list of videos they wish to watch, leading to privacy
loss because of what the service provider can learn from users’ watching
patterns. There is however no inherent need for users to disclose to YouTube
which videos they wish to watch, as a private information retrieval
(PIR)implementation of this service proves [47]. It is therefore the system
architecture that forces users to disclose information to meet personal
utility requirements, not the functionality itself.

A trivial universal implementation that illustrates why personal utility does
not require users to reveal information has the provider sending to users all
the data and code they need to run the service, so that they do not have to
disclose any usage information. Still, what is theoretically possible may not
always be achievable in practice due to cost, available infrastructure or
usability (e.g. unacceptable delays), among other constraints.121212 A PIR
implementation of a streaming service offering a small number of media files
(e.g. in the few thousands) such as Netflix may be feasible [47], but this may
not scale well to services such as Google search, indexing _“hundreds of
billions of webpages”_ and with stringent latency requirements [48, 49, 50].
Similarly, a service such as Facebook Messenger may require two users to
expose their private messages to Facebook itself, yet there is no inherent
need to do so, as users can exchange messages encrypted end-to-end. Moreover,
users can even establish a dedicated out-of-band channel that enables them to
bypass Facebook altogether, which shows that there is nothing inherent in the
functionality itself that requires them to disclose their messages or
messaging patterns to Facebook or any other third-party provider, as only
those two users require access to the messages they exchange.

Hence, whichever personal utility function $f$ users are interested in,
personal utility itself does not inherently require that users disclose
information to adversarial parties. It is the system’s architecture that
compels users to reveal _excess information_ for the fulfilment of that
functionality. Moreover, whereas functionality $f$ requires a set of features
$R^{u}$ to provide the set of outcomes $\mathbf{o}$ whence users derive
utility, the system’s architecture may further require that users disclose
features $R^{\bar{u},l}$ that leak information about $X$ yet are unnecessary
for the provision of utility. Figure 9 illustrates this notion: the horizontal
bar represents the amount information that sequence $\mathbf{r}$ leaks to the
adversary, from zero information (leftmost edge) to maximum information
(rightmost edge). Personal utility does not require that users provide
information to an adversary; hence, the minimum amount of information about
$\mathbf{r}$ that users should reveal is zero, which we represent with a
tightly dotted line. Anything to the right of the tightly dotted line is
_excess information_ , up to the maximum information leakage limit that
features $R^{l}$ determine, as $R^{\bar{l}}$ do not provide information to the
adversary.

Figure 9: Personal utility disclosure requirements.
Personal utility alone should not require UDO.

Utility _producers_ on the other hand _always_ need to reveal _some_
information, the rationale being that whoever obtains utility from a utility
producer must have access to at least some function over the producer’s data
$h(\mathbf{r})$. Revealing information is therefore _unavoidable_ , as the
intrinsic nature of public utility itself requires it. Changes to the system
architecture can decrease privacy risk by preventing the exposure of
information that is unnecessary for the production of public utility, but
cannot completely prevent information leakage without destroying all public
utility —this is, whenever $R^{u}$ provides information about
$\mathbf{x}$.131313 In other words, we cannot arbitrarily decrease privacy
loss without destroying all public utility. The rationale follows from the
impossibility of absolute disclosure prevention formulated by Dwork and Naor,
namely, unless we completely randomise $\mathbf{r}$ —in turn resulting in
total utility loss— it is impossible to provide absolute guarantees on what an
adversary is able to learn with the information that $\mathbf{r}$ discloses
[45].

To illustrate how public utility always requires some degree of information
leakage, consider the personalised recommendations on what to watch next that
YouTube curates for its users. Recommendation algorithms typically rely on
probabilistic modelling to determine relationships between media items that
viewers often like, e.g. whether viewers that enjoy video A also often enjoy
video B. To determine such relationships, recommendation systems require
samples of the set of videos each person watches. YouTube’s recommendation
system relies on a central party (YouTube) collecting all users’ viewing
histories, computing a recommendation model, then offering personalised
suggestions to each individual viewer. YouTube users thus produce public
utility by letting YouTube use their viewing histories ($\mathbf{r}$) to
provide recommendations to others, i.e.
$z=h(\mathbf{r}_{1},\mathbf{r}_{2},\ldots,\mathbf{r}_{N})$.

It is however possible to disclose less information and produce the same level
of public utility; e.g. we may rely on private information retrieval (PIR)
_and federated learning_ to prevent a centralised party (YouTube) from
collecting every user’s viewing history [51]. With PIR, each user watches
videos from the platform privately, without disclosing her viewing history to
anyone. With federated learning, users train an individual recommendation
model locally —i.e. on their own devices— based on their individual viewing
histories, which they send to the central party. The central party then
averages individual models to obtain a global model that users download to
update their local model and obtain recommendations. The new system
architecture preserves utility _and_ improves users’ privacy: users still
benefit from (arguably the same) recommendations but no longer need to
disclose the list of videos they have watched, only the individual models they
compute locally on their devices. Indeed, federated learning adds a level of
indirection and complexity that prevents unsophisticated adversaries from
breaching users’ privacy; however, local models still leak information about
individual users [52, 53].

To prevent the central party from obtaining individual models, users may get
rid of the central party altogether by running a distributed secure multi-
party computation (MPC) protocol, i.e. instead of computing their individual
models locally and sending them to the provider, they run a distributed MPC
protocol among themselves to privately compute a global model in a way that no
participant needs to disclose her individual user model [54, 55]. Taking this
approach to the extreme, rather than disclosing a global model that anyone
could download and try to exploit to extract knowledge about individual media
consumption patterns, users could simply rely on MPC to privately and
collectively compute their individual video recommendations, without
disclosing any intervening, intermediary data: not the list of videos they
have watched, not their individual models, not even a global model. This
architecture further improves users’ privacy without compromising public
utility.

And yet, the resulting recommendations still present biases from each
participating utility producer, leaking information that a knowledgeable
adversary could exploit to extract information about individual users.141414
One particular example of such well-informed adversaries is the classic
_“knows-all-records-but-one”_ or _“has-arbitrary-knowledge”_ adversaries that
the _differential privacy_ literature considers [34], e.g. MPC does not
protect against $n-1$ colluding parties out of $n$ participants. Let us
consider an adversary that observes the recommendation
$h(\mathbf{r}_{v},\\{\mathbf{r}_{2},\ldots,\mathbf{r}_{n}\\})=z$, where
$\mathbf{r}_{v}$ represents the input of the target user and the remaining
$\mathbf{r}_{j}$ the inputs of the $n-1$ colluding parties. Knowing $h$, the
colluding parties’ $\mathbf{r}_{j}$ and the function output $o_{h}$, the
adversary could either determine the actual value of input $\mathbf{r}_{v}$ or
the set of values that could not have possibly led to $o_{h}$, therefore
learning _something_ about the actual user value $\mathbf{r}_{v}$ —the
exception being that $h$ is insensitive to the user’s input $\mathbf{r}_{v}$,
in which case the user input is irrelevant, i.e. public utility does not
depend on it. However, at this point it is impossible to further reduce the
information users disclose without a drop in utility: we have redesigned the
system to only disclose what is strictly necessary for the production of
public utility, namely, recommendations themselves. Any intervening data in
such computation is not explicitly exposed, but the production of public
utility inherently requires that we disclose _some_ information, this is,
those bits of information from $\mathbf{r}$ that contribute to produce those
recommendations. Hence, users must resort to some form of UDO, e.g. randomised
response, to further minimise the privacy risk they incur by contributing to
the production of public utility [56, 57].

This succession of system (re)designs enable us to see that there are two
types of disclosure requirements: those that _public_ utility imposes, and
those that the system architecture imposes. The system architecture may
require that we expose more information than what is actually necessary to
reveal, i.e. disclose $\mathbf{r}$ or some function thereof as opposed to the
minimum amount of information that public utility requires, i.e. the outcome
$z=h(\mathbf{r})$. Figure 10 depicts this idea: The system architecture
requires users to expose, from left to right, features $R^{u,l}$ that
contribute to public utility and leak information to the adversary (white and
grey backgrounds), features $R^{\bar{u},l}$ that _do not_ contribute to public
utility but still leak information to the adversary (striped background) and
features $R^{\bar{l}}$ that may or may not contribute to public utility, but
they do not leak information to the adversary (chequered background). The
tightly dotted line where $h()$ points to marks the minimum amount of
information the user must disclose without public utility loss; the portion of
the bar to the right of this line represents _excess_ information that the
architecture —unnecessarily— leaks.

Figure 10: Interplay between public utility exposure requirements, a system’s
architecture and obfuscation.

The disclosure requirements that either personal or social utility impose thus
have key implications for privacy engineering. Since personal utility does not
inherently require users’ data disclosure, systems that do require utility
consumers to disclose their data to adversarial parties reveal an unequivocal
culprit: the system does not satisfy privacy-by-design requirements, requiring
that users reveal more information than what is strictly necessary, be it for
reasons of cost, lack of expertise or intentional data siphoning [58]. Hence,
utility _consumers_ should not be forced to _unilaterally_ resort to OTs to
protect their privacy (q.v. Figure 2) even if obfuscation represents a
valuable tool for users to contest privacy-invasive system architectures [59].
Instead, as Figure 9 suggests, system designers should ideally _embbed_ UPO or
alternative privacy technologies in the system design,151515 As illustrated
earlier in this section, system designers may resort to utility-preserving
privacy technologies that do not rely on obfuscation, e.g. through the use of
cryptographic primitives such as PIR. e.g.  _embedding_ in the system the
user-deployed OT that Fig. 2 depicts to protect utility consumers’ privacy _by
design_. As we argue in the next section, exclusively relying on UPO to
protect utility consumer’s privacy is indeed theoretically, conceptually
possible through the use of _chaff_. UDO does however represent an alternative
in those situations where the system architecture or high costs prevent the
deployment of UPO in practice, even if the trade-off between utility and
privacy that UDO imposes is not fundamentally necessary.

Conversely, since social utility mandates users’ data disclosure (or a
function thereof), once we expose nothing but the strictly necessary
information about $\mathbf{r}$ that the production of public utility requires,
there is no workaround to the trade-off between public utility and privacy. At
this point, we _must_ resort to (utility-degrading) obfuscation to remove
information that both intervenes in the production of public utility and
contributes to privacy loss, meaning that once we reach the point at which the
system exposes nothing but the minimum information required to fully guarantee
public utility, UDO represents the only solution to further decrease users’
privacy loss. Returning to the YouTube example above, when users engage in a
distributed MPC protocol to privately learn their recommendations, they expose
the minimum amount of information to preserve public utility; from that point
onwards, participating users can only resort to some form of input
randomisation (à la differential privacy) to further diminish the privacy loss
they incur in the production of public utility. Such input randomisation leads
to utility-loss and thus represents UDO. Hence, obfuscation is key to enable
individuals to balance the privacy loss they incur in the production of public
utility. System designers may thus incorporate obfuscation on behalf of
utility producers (see Fig. 3), provide support for user-generated obfuscation
(as in Fig. 2) or both (Fig. 4).

A system’s architecture may however also require that users expose more
information than what is strictly necessary for the production of public
utility, e.g. YouTube requires that users disclose their viewing histories to
serve recommendations to others. In such cases, we can deploy UPO to remove
information about features $R^{u,\bar{l}}$ that do not intervene in the
production of public utility; however, features $R^{u,l}$ require the
deployment of UDO even if that set of features still leaks more information
than what is strictly necessary. Returning to the YouTube example above, the
interventions we propose (i.e. computing the global model using federated
learning and MPC) prevent the disclosure of _some_ excess information while
preserving all public utility, but still leak more than strictly necessary,
forcing users that do not wish to expose as much information about
$\mathbf{r}$ to resort to UDO. Figure 10 represents this interplay between
obfuscation, public utility and a system’s architecture: the tightly dotted
vertical line represents the minimum amount of information about $\mathbf{r}$
that users must expose to preserve all public utility. The white area to the
left of that line represents the range where a trade-off between privacy and
utility is unavoidable: further decreasing privacy loss entails diminished
public utility. Navigating such trade-off necessarily requires the deployment
of UDO. The grey area to the right of that line represents excess information
embedded in features $R^{u,l}$ that the system’s architecture exposes to
fulfil public utility requirements, thereby forcing the deployment of UDO to
reduce privacy loss even if such a trade-off is not strictly necessary.

##  V Utility-preserving obfuscation and chaff

Utility-preserving obfuscation (UPO) requires that users’ inputs are either
left intact or replaced by inputs that result in identical or equivalent
utility (i.e. that result in the same outputs $o$ and $z$). Interleaving the
user’s genuine input $\mathbf{r}$ with a sequence $\mathbf{d}$ of _chaff_ ,
this is, dummy or fake user activity, pollutes an adversary’s observation but
does not modify the user’s individual activities $r_{i}$. Under the assumption
that chaff is _indistinguishable_ from the user’s real activity —the key
requirement for any chaff-based obfuscation strategy to work—, the adversary’s
observes a _polluted_ set of input data $\mathbf{q}$ that should ideally
reveal less or no information about $\mathbf{r}$, thereby reducing privacy
loss [18]. Moreover, if the generation of chaff meets certain conditions
(which we review below) and the OT can filter out responses $o_{d}$, the user
receives the original output $\mathbf{o}$, hence the same utility [2]. Chaff
can thus prevent privacy loss _and_ preserve personal utility, enabling UPO.
Figure 11 depicts the system model featuring a chaff-based OT. Below we
illustrate through three different scenarios how to perform UPO with chaff.

Figure 11: Operation of a chaff-based obfuscation tool

Let us return to the previous video streaming use case (e.g. YouTube). First,
let us consider the service offers no personalisation, i.e. the set of results
$o=f_{0}(r)$ (a list of videos) any search query $r_{i}$ leads to does not
depend on previous queries by _any user_. In this scenario, an OT can filter
out responses to dummy queries $o_{d}$ that the service returns to the user
ensuring that responses $o_{r}$ remain the same as if no dummies were added,
preserving personal utility. However, the adversary observes a sequence of
real and dummy queries $\mathbf{q}$ which ideally prevents it from retrieving
the original $\mathbf{r}$.

Second, let us consider the service offers individual personalisation, i.e.
each query $r_{i}$ depends on previous queries _by the same user_. The search
function $f_{1}$ takes a query $r_{i}$ and the sequence
$\mathbf{r}=[r_{1},\dots,r_{i}]$ of previous queries (or subset thereof) to
produce a list of videos $o$, i.e. $o=f_{1}(r_{i},\mathbf{r})$. In this
scenario, an OT cannot simply generate dummy queries and filter the
corresponding dummy responses to preserve utility, as $f_{1}$ would feed on an
obfuscated input $\mathbf{q}$ that contains dummy queries, disrupting
personalisation, i.e. $f_{1}(r,\mathbf{q})\neq f_{1}(r,\mathbf{r})\Rightarrow
u_{f}(\mathbf{q})<u_{f}(\mathbf{r})$.161616 Note that this implicitly assumes
search results become less useful if the personalisation function feeds on
dummy queries $d_{i}$ unrelated to the user’s search queries $\mathbf{r}$.  To
overcome this issue, the OT generates chaff by creating dummies of _the least
reducible unit of data_ that the function the user obtains utility from (i.e.
$f_{1}$) _feeds_ on, namely, dummy units of the entire user input
$\mathbf{r}$. To do so, the OT resorts to Sybil accounts: the OT generates
dummy user accounts on which it sends dummy queries, but keeps the genuine
user account free of chaff. The honest-but-curious service provider returns
personalised search results for the real user account and each of the dummy
accounts independently, thus preserving utility for the user. In terms of
privacy, assuming indistinguishability between the real user account and the
Sybils, the adversary cannot distinguish the real input $\mathbf{r}$, which
ideally results in reduced privacy loss, i.e.
$l(\mathbf{q})<l(\mathbf{r})$.171717 One may protest that, first, this
configuration does not protect the user against practices like profiling
because, since the user’s actual account is free from chaff, the adversary can
still subject the user to unfair or discriminative targeted advertising. In
fact, and second, the adversary may be unaware of the existence of Sybil
accounts and fail to link them to the OT’s user. We recall that the model in
Sect. II specifies a _strategic_ adversary whose goal is to recover
$\mathbf{x}=g(\mathbf{r})$, which means that it _knows_ the OT generates Sybil
accounts and the consequences derived from the recovery of $\mathbf{x}$ or
$\mathbf{\hat{x}}$ (such as targeted advertising) are out of scope. Note that,
even in the previous scenario ($f_{0}$), the OT cannot prevent profiling based
on a filtered $\mathbf{\hat{x}}$ that ultimately leads to worse outcomes on
the user. This further highlights the protective goal that obfuscation plays
in this setting: it attempts to prevent the adversary from obtaining
(additional) knowledge, rather than prevent subsequent processing that may
take place regardless. Addressing this issue may require a departure from
privacy technology to solutions that focus on the impact of algorithmic
decision-making, such as protective optimisation technologies [60, 61].

Third, let us consider a service with _collective_ personalisation, this is,
each query depends on other users’ previous queries. The search function
$f_{2}$ takes a query $r_{v}$ from user $v$ and previous queries $\mathbf{r}$
by the querying user and other users, i.e.
$o=f_{2}(r_{v},\mathbf{r}_{v},\mathbf{r}_{1},\ldots,\mathbf{r}_{N-1})$, with
$N$ the user population size. We further consider the user to exclusively be a
utility consumer, i.e. she does not wish to produce public utility and
disregards obfuscation’s impact on personalised results for others. Still, an
OT that relies on Sybil accounts like in the previous scenario is bound to
disrupt global personalisation for everyone, _including_ the OT user: the
service provider may choose to entirely disregard the user input (either real
or dummy) to prevent polluting the collective personalisation model or,
instead, select as input the user account it identifies as real (being
potentially a Sybil), among other strategies. As a result, the user’s input is
either absent or incorrect, affecting collective personalisation for everyone,
changing the search results that other users’ obtain for their queries, thus
further altering the feedback they provide to the personalisation function. In
this particular scenario, to deploy UPO with chaff, the service provider would
need to generate independent collective personalisation for each of the user’s
Sybil accounts, which would in turn require the cooperation of every other
user, by providing feedback to the collective model created for every Sybil
account. Needless to say, this represents a ridiculously expensive and
unrealistic solution. However, it still shows how chaff, _theoretically_ ,
enables UPO. Finally, this third scenario further showcases how, to benefit
from collective personalisation, the user depends on everyone else’s
willingness to produce public utility: if everyone selfishly wished to enjoy
collective personalisation without revealing data about themselves, collective
personalisation would not be possible in the first place. Someone must give
away some or their privacy to produce utility for everyone else.

The fact that the generation of chaff or dummies is often prohibitively costly
points in fact to a different trade-off, namely, not between utility and
privacy, but between privacy and _cost_. Chaff-based OT or non-obfuscation-
based solutions such as PIR or MPC preserve users’ utility yet incur
additional (and sometimes prohibitive) costs for either users or service
providers, or both.

##  VI Conclusion

Obfuscation represents an essential set of techniques in the privacy
engineering toolkit. Yet a holistic understanding of the role that
obfuscation, in general, plays in the engineering of privacy has hitherto been
elusive. Furthermore, the multiplicity of contexts in which obfuscation
technology has been applied has led to a vast array of privacy measures to
evaluate the protection that obfuscation affords. This fragmented landscape of
obfuscation technologies and piecemeal evaluation methods means that we also
lack a cohesive, comprehensive understanding of the conditions and assumptions
under which any particular measure suitably assists the evaluation of
obfuscation technologies.

In this paper we take a step back from each of the specific settings in which
obfuscation is applied to provide a set of general observations that apply to
the broader family of obfuscation technologies as a whole. The core
contribution of this paper is a conceptual framework whose aim is to enable a
better understanding of the role that obfuscation technology plays in the
engineering of privacy. To that end, we have proposed an abstract model of
obfuscation, bringing together a multiplicity of obfuscation methods under the
same analytical umbrella, whether they are deployed by users, trusted curators
or service providers, or both. Moreover, to advance a better grasp of how to
evaluate obfuscation technologies, we have proposed a conceptual separation
between two main types of evaluation: mechanism-centred and attack-centred.
Through this conceptualisation, we have unpacked underlying assumptions to the
measures that fall within either approach and shed further light on the
conditions that call for choosing one measure or another, e.g. mechanism-
centred measures are best suited to impose privacy bounds while attack-centred
measures enable us to measure the privacy loss that particular, concrete
adversaries subject users to.

We have introduced the concepts of _personal_ and _public utility_ as well as,
correspondingly, _utility consumer_ and _producer_. We have distinguished two
types of obfuscation: utility-preserving (UPO) and utility-degrading (UDO),
and observed that the production of public utility _requires_ the deployment
of UDO to arbitrarily reduce privacy loss, whereas personal utility alone does
not impose a trade-off between utility and privacy, thereby _theoretically_
enabling the deployment of UPO or alternative utility-preserving privacy
technologies that do not rely on obfuscation —with UDO being forced by
extrinsic reasons such as cost and adversarial service providers. Lastly, we
have illustrated how to perform UPO through _chaff_ , acknowledging that
escaping the trade-off between utility and privacy invokes a different trade-
off between privacy and cost.

This work opens up a multitude of future research avenues: The separation
between mechanism-centred and attack-centred evaluation can contribute to
spawn more systematic approaches to the evaluation of obfuscation
technologies, providing a framework to compare designs and evaluations that do
not share a common set of adversarial assumptions. Distinguishing between
personal and public utility has an impact on privacy-by-design principles and
policymaking, e.g. should users be able to completely opt-out from public
utility production? In other words, should users be able to participate in a
system exclusively as utility consumers? Furthermore, fully addressing the
trade-off between public utility production and privacy requires utility-
_degrading_ obfuscation, thus raising questions about the impact that
obfuscated data has on subsequent algorithmic decision making. How does the
privacy protection through obfuscation interact with other goals and
requirements, such as algorithmic fairness [61]? Future work should also
advance a better understanding of UPO methods beyond chaff, as well as to
explore further the underlying rationale to different obfuscation
technologies.

## Acknowledgments

The author would like to thank Ward Beullens and Charlotte Bonte for answering
questions about notation and cryptographic obfuscation. This work was
supported by CyberSecurity Research Flanders with reference number VR20192203.

## References

  * [1] N. Kuzurin, A. Shokurov, N. Varnovsky, and V. Zakharov, “On the concept of software obfuscation in computer security,” in _Proceedings of Information security conference (ISC)_. Springer, 2007, pp. 281–298.
  * [2] E. Balsa, C. Troncoso, and C. Diaz, “OB-PWS: Obfuscation-based private web search,” in _IEEE Symposium on Security and Privacy (S &P’12)_, 2012, pp. 491–505.
  * [3] A. Gervais, R. Shokri, A. Singla, S. Capkun, and V. Lenders, “Quantifying web-search privacy,” in _Proceedings of Computer and communications security (CCS)_. ACM, 2014, pp. 966–977.
  * [4] C. A. Ardagna, M. Cremonini, E. Damiani, S. De Capitani di Vimercati, and P. Samarati, “Location privacy protection through obfuscation-based techniques,” in _IFIP Annual Conference on Data and Applications Security and Privacy (DBSec’07)_. Springer, 2007, pp. 47–60.
  * [5] M. Duckham and L. Kulik, “A formal model of obfuscation and negotiation for location privacy,” in _Proceedings of International conference on pervasive computing_. Springer, 2005, pp. 152–170.
  * [6] R. Shokri, G. Theodorakopoulos, J.-Y. Le Boudec, and J.-P. Hubaux, “Quantifying location privacy,” in _Proceedings of Symposium on security and privacy (S &P)_. IEEE, 2011, pp. 247–262.
  * [7] A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam, “$\ell$-diversity: Privacy beyond $k$-anonymity,” _ACM Transactions on knowledge discovery from data (TKDD)_ , vol. 1, no. 1, p. 3, 2007.
  * [8] L. Sweeney, “$k$-anonymity: a model for protecting privacy,” _International journal of uncertainty, fuzziness and knowledge-based systems_ , vol. 10, no. 5, pp. 557–570, 2002.
  * [9] O. Berthold and H. Langos, “Dummy traffic against long term intersection attacks,” in _Proceedings of Workshop on privacy enhancing technologies (PET)_. Springer, 2002, pp. 110–128.
  * [10] M. Juarez, M. Imani, M. Perry, C. Diaz, and M. Wright, “Toward an efficient website fingerprinting defense,” in _Proceedings of European symposium on research in computer security (ESORICS)_. Springer, 2016, pp. 27–46.
  * [11] C. C. Aggarwal and P. S. Yu, “A general survey of privacy-preserving data mining models and algorithms,” in _Privacy-preserving data mining: models and algorithms_ , C. C. Aggarwal and P. S. Yu, Eds. Springer, 2008, pp. 11–52.
  * [12] R. Shokri, G. Theodorakopoulos, C. Troncoso, J.-P. Hubaux, and J.-Y. Le Boudec, “Protecting location privacy: optimal strategy against localization attacks,” in _Proceedings of the 2012 ACM conference on Computer and communications security_ , 2012, pp. 617–627.
  * [13] N. Takbiri, A. Houmansadr, D. L. Goeckel, and H. Pishro-Nik, “Limits of location privacy under anonymization and obfuscation,” in _2017 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2017, pp. 764–768.
  * [14] A. Gervais, A. Filios, V. Lenders, and S. Capkun, “Quantifying web adblocker privacy,” in _European Symposium on Research in Computer Security_. Springer, 2017, pp. 21–42.
  * [15] R. Shokri, “Privacy games: Optimal user-centric data obfuscation,” _Proceedings on privacy enhancing technologies (PoPETs)_ , vol. 2015, no. 2, pp. 299–315, 2015.
  * [16] M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: differential privacy for location-based systems,” in _Proceedings of Computer & communications security (CCS’13)_. ACM, 2013, pp. 901–914.
  * [17] S. Li, H. Guo, and N. Hopper, “Measuring information leakage in website fingerprinting attacks and defenses,” in _Proceedings of Computer and communications security (CCS)_. ACM, 2018, pp. 1977–1992.
  * [18] E. Balsa, “Chaff-based profile obfuscation,” Ph.D. dissertation, KU Leuven, The address of the publisher, December 2019, an optional note.
  * [19] C. C. Aggarwal and P. S. Yu, “A general survey of privacy-preserving data mining models and algorithms,” in _Privacy-preserving data mining_. Springer, 2008, pp. 11–52.
  * [20] E. Bertino, D. Lin, and W. Jiang, “A survey of quantification of privacy preserving data mining algorithms,” in _Privacy-preserving data mining_. Springer, 2008, pp. 183–205.
  * [21] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Foundations and trends in theoretical computer science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [22] J. Hermans, A. Pashalidis, F. Vercauteren, and B. Preneel, “A new RFID privacy model,” in _Proceedings of European symposium on research in computer security (ESORICS)_. Springer, 2011, pp. 568–587.
  * [23] C. Yao, L. Wang, S. X. Wang, and S. Jajodia, “Indistinguishability: The other aspect of privacy,” in _Proceedings of Workshop on Secure data management (SDM)_. Springer, 2006, pp. 1–17.
  * [24] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” _Journal of privacy and confidentiality_ , vol. 7, no. 3, pp. 17–51, 2017.
  * [25] P. Kairouz, S. Oh, and P. Viswanath, “Extremal mechanisms for local differential privacy,” in _Advances in neural information processing systems_ , 2014, pp. 2879–2887.
  * [26] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” in _Proceedings of Advances in cryptology (EUROCRYPT)_. Springer, 2006, pp. 486–503.
  * [27] F. McSherry and I. Mironov, “Differentially private recommender systems: Building privacy into the Netflix Prize contenders,” in _Proceedings of Knowledge discovery and data mining (KDD)_. ACM, 2009, pp. 627–636.
  * [28] R. Bassily and A. Smith, “Local, private, efficient protocols for succinct histograms,” in _Proceedings of Symposium on theory of computing (STOC)_. ACM, 2015, pp. 127–135.
  * [29] M. Backes, A. Kate, P. Manoharan, S. Meiser, and E. Mohammadi, “Anoa: A framework for analyzing anonymous communication protocols,” in _2013 IEEE 26th Computer Security Foundations Symposium_. IEEE, 2013, pp. 163–178.
  * [30] K. Chatzikokolakis, C. Palamidessi, and P. Panangaden, “Anonymity protocols as noisy channels,” _Information and computation_ , vol. 206, no. 2-4, pp. 378–401, 2008.
  * [31] I. B. Damgård, T. P. Pedersen, and B. Pfitzmann, “Statistical secrecy and multibit commitments,” _IEEE Transactions on information theory_ , vol. 44, no. 3, pp. 1143–1151, 1998.
  * [32] M. S. Alvim, K. Chatzikokolakis, C. Palamidessi, and G. Smith, “Measuring information leakage using generalized gain functions,” in _Proceedings of Computer security foundations symposium (CSF)_. IEEE, 2012, pp. 265–279.
  * [33] G. Smith, “Quantifying information flow using min-entropy,” in _Proceedings of Quantitative evaluation of systems (QEST)_. IEEE, 2011, pp. 159–167.
  * [34] D. Kifer and A. Machanavajjhala, “No free lunch in data privacy,” in _Proceedings of International conference on management of data (SIGMOD)_. ACM, 2011, pp. 193–204.
  * [35] P. Cuff and L. Yu, “Differential privacy as a mutual information constraint,” in _Proceedings of Computer and communications security (CCS)_. ACM, 2016, pp. 43–54.
  * [36] M. S. Alvim, M. E. Andrés, K. Chatzikokolakis, P. Degano, and C. Palamidessi, “Differential privacy: on the trade-off between utility and information leakage,” in _Proceedings of Formal Aspects of Security and Trust (FAST)_. Springer, 2011, pp. 39–54.
  * [37] G. Barthe and B. Kopf, “Information-theoretic bounds for differentially private mechanisms,” in _Proceedings of Computer security foundations symposium (CSF)_. IEEE, 2011, pp. 191–204.
  * [38] V. Bindschaedler and R. Shokri, “Synthesizing plausible privacy-preserving location traces,” in _Proceedings of Symposium on security and privacy (S &P)_. IEEE, 2016, pp. 546–563.
  * [39] S. Oya, C. Troncoso, and F. Pérez-González, “Is geo-indistinguishability what you are looking for?” in _Proceedings of Workshop on privacy in the electronic society (WPES)_. ACM, 2017, pp. 137–140.
  * [40] M. R. Clarkson, A. C. Myers, and F. B. Schneider, “Belief in information flow,” in _Proceedings of Computer security foundations workshop (CSFW)_. IEEE, 2005, pp. 31–45.
  * [41] ——, “Quantifying information flow with beliefs,” _Journal of computer security_ , vol. 17, no. 5, pp. 655–701, 2009.
  * [42] M. Franz, B. Meyer, and A. Pashalidis, “Attacking unlinkability: The importance of context,” in _Workshop on privacy enhancing technologies (PET)_. Springer, 2007, pp. 1–16.
  * [43] S. Hamadou, V. Sassone, and C. Palamidessi, “Reconciling belief and vulnerability in information flow,” in _Symposium on security and privacy (S &P)_. IEEE, 2010, pp. 79–92.
  * [44] S. Hamadou, C. Palamidessi, and V. Sassone, “Quantifying leakage in the presence of unreliable sources of information,” _Journal of computer and system sciences_ , vol. 88, pp. 27–52, 2017.
  * [45] C. Dwork and M. Naor, “On the difficulties of disclosure prevention in statistical databases or the case for differential privacy,” _Journal of privacy and confidentiality_ , vol. 2, no. 1, pp. 93–107, 2010.
  * [46] D. Kifer and A. Machanavajjhala, “Pufferfish: A framework for mathematical privacy definitions,” _ACM Transactions on Database Systems (TODS)_ , vol. 39, no. 1, pp. 1–36, 2014.
  * [47] T. Gupta, N. Crooks, W. Mulhern, S. T. Setty, L. Alvisi, and M. Walfish, “Scalable and private media consumption with Popcorn,” in _Proceedings of Networked systems design and implementation (NSDI)_. USENIX, 2016, pp. 91–107.
  * [48] I. Arapakis, X. Bai, and B. B. Cambazoglu, “Impact of response latency on user behavior in web search,” in _Proceedings of SIGIR conference on Research & development in information retrieval (SIGIR’14)_. ACM, 2014, pp. 103–112.
  * [49] “How search organizes information.” In _Google Search Blog_ at https://www.google.com/search/howsearchworks/crawling-indexing/, last accessed on 30 July 2019.
  * [50] N. J. Taylor, A. R. Dennis, and J. W. Cummings, “Situation normality and the shape of search: The effects of time delays and information presentation on search behavior,” _Journal of the Association for information science and technology_ , vol. 64, no. 5, pp. 909–928, 2013.
  * [51] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, pp. 1–19, 2019.
  * [52] G. Ateniese, L. V. Mancini, A. Spognardi, A. Villani, D. Vitali, and G. Felici, “Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers,” _International Journal of Security and Networks_ , vol. 10, no. 3, pp. 137–150, 2015.
  * [53] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, “Membership inference attacks against machine learning models,” in _Proceedings of Symposium on security and privacy (S &P)_. IEEE, 2017, pp. 3–18.
  * [54] I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, and N. P. Smart, “Practical covertly secure MPC for dishonest majority – or: Breaking the SPDZ limits,” in _Proceedings of European symposium on research in computer security (ESORICS)_. Springer, 2013, pp. 1–18.
  * [55] D. W. Archer, D. Bogdanov, Y. Lindell, L. Kamm, K. Nielsen, J. I. Pagter, N. P. Smart, and R. N. Wright, “From keys to databases—real-world applications of secure multi-party computation,” _The Computer Journal_ , vol. 61, no. 12, pp. 1749–1771, 2018.
  * [56] A. Beimel, K. Nissim, and E. Omri, “Distributed private data analysis: Simultaneously solving how and what,” in _Annual International Cryptology Conference_. Springer, 2008, pp. 451–468.
  * [57] P. Kairouz, S. Oh, and P. Viswanath, “Differentially private multi-party computation,” in _2016 Annual Conference on Information Science and Systems (CISS)_. IEEE, 2016, pp. 128–132.
  * [58] S. Gürses, C. Troncoso, and C. Diaz, “Engineering privacy by design reloaded,” in _Amsterdam Privacy Conference_ , 2015, pp. 1–21.
  * [59] F. Brunton and H. Nissenbaum, _Obfuscation: A user’s guide for privacy and protest_. MIT Press, 2015.
  * [60] S. Gürses, R. Overdorf, and E. Balsa, “POTs: the revolution will not be optimized?” presented at _Workshop on hot topics in privacy enhancing technologies (HotPETs)_ , 2018.
  * [61] B. Kulynych, R. Overdorf, C. Troncoso, and S. Gürses, “Pots: Protective optimization technologies,” ser. FAT* ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 177–188. [Online]. Available: https://doi.org/10.1145/3351095.3372853
  * [62] C. Cachin, “Entropy measures and unconditional security in cryptography,” Ph.D. dissertation, ETH Zurich, 1997.
  * [63] J. O. Pliam, “On the incomparability of entropy and marginal guesswork in brute-force attacks,” in _Proceedings of International conference on cryptology in India (Indocrypt)_. Springer, 2000, pp. 67–79.

###  -A On alternative measures of information leakage

Both mutual information and capacity are based on Shannon’s entropy which,
according to Cachin’s interpretation, measures information as _“the average
number of binary questions an adversary needs to ask about $\mathbf{r}$ to
determine its value”_ [62]. Mutual information thus measures information
leakage in terms of the average number of binary questions one no longer has
to ask after observing $\mathbf{q}$, i.e. reducing uncertainty about
$\mathbf{r}$. However, this may not always be the most meaningful measure of
information leakage.

Among other authors, Smith has prominently questioned the research community’s
over-reliance in Shannon’s entropy as a one-size-fits-all measure of
uncertainty [33]. Smith shows that Shannon’s entropy underestimates the
_vulnerability_ of the most likely $\mathbf{r}$ [33], i.e. if we are mostly
concerned about the information an OT leaks about the most likely input
$\mathbf{r}$. Pliam also shows that there is an unbounded gap between
Shannon’s entropy and _marginal guesswork_ , related to the minimum number of
searches a brute-force attacker must perform to attain a certain probability
of success [63]. This means that the higher the probability
$\max(P(\,R=\mathbf{r}\,))$, the more likely the adversary guesses it
correctly _regardless of obfuscation_ ; yet Shannon’s entropy may remain
arbitrarily high as long as there are sufficient alternative sequences
$\mathbf{r}^{\prime}$ with greater than zero (even if negligible) probability.
These critiques illustrate that there are multiple ways of measuring the
amount of information an OT leaks, e.g. min-entropy-based measures such as
min-entropy leakage and min-capacity capture better the information that OTs
leak about the most likely input $\mathbf{r}$, whereas measures derived from
marginal guesswork may better capture an OT’s leakage of information in a
setting where multiple guesses are allowed. More recently, the notion of
$g$-leakage provides a generalisation of min-entropy that uses _gain
functions_ to capture a variety of adversarial attack strategies [32].

These information leakage variants thus capture different notions of the type
of information an OT should _not_ leak, e.g. min-leakage measures the amount
of information an OT leaks about the most likely input
$\text{arg\,max}_{\mathbf{r}}(P(\,\mathbf{r}\,))$, essentially disregarding
the amount of information the OT leaks about less likely inputs. Hence, these
notions implicitly incorporate assumptions about the kind of information that
may be useful to an adversary given a general attack strategy: be it to
recover a single $\mathbf{\hat{x}}$ with the highest probability of being
$\mathbf{x}$ or select the top $k$ most likely $\mathbf{\hat{x}}$, carrying on
under the assumption that any of those inputs may be the actual $\mathbf{x}$
—e.g. to lessen the probability of focusing on a single $\mathbf{\hat{x}}$
that does not match $\mathbf{x}$. Analysts and designers must therefore
carefully select the measure that best represents the kind of information the
OT should not leak.

###  -B On Shokri’s _expected distortion privacy_

Shokri’s definition of _expected distortion privacy_ uses $\pi(\mathbf{r})$
instead of $P(\,\mathbf{r}\,)$, with $\pi(\mathbf{r})$ representing
$P(\,\mathbf{r}\,)$ as given by prior, publicly available information [15].
Shokri notes that $\pi(\mathbf{r})$ does not however denote an adversary’s
auxiliary knowledge, which is generally unknown, i.e. $\pi(\mathbf{r})$
represents an estimation of what the adversary knows based on publicly
available information, not what the adversary _really_ knows (e.g. through
other information channels that neither we know nor control). Using
$\pi(\mathbf{r})$ instead of $P(\,\mathbf{r}\,)$ is consistent with Shokri’s
goal, namely, to design an obfuscation mechanism that _optimises_ the
obfuscation strategy based on previous disclosures assuming an informed
adversary that uses an optimal attack strategy. Conversely, we consider an
adversary with potentially incorrect prior knowledge and suboptimal attack
strategy. Hence, we use $P(\,\mathbf{r}\,)$ to average over the actual
probability of inputs $\mathbf{r}$ and incorporate the adversary’s prior
knowledge (which, as Shokri, we acknowledge is an estimation, not the actual
knowledge) in the term that Shokri reserves for the inference attack alone,
i.e. $P(\,\hat{\mathbf{r}}\;|\;\mathbf{q}\,)$. These changes enable us to
measure the expected estimation error of adversaries with incorrect priors.