Lowering the cost of anonymization

2.2.3 Neighborhood definition (N) ✿

The original definition of differential privacy considers datasets differing in one record. Thus, the datasets can differ in two possible ways: either they have the same size and differ only on one record, or one is a copy of the other with one extra record. These two options do not protect the same thing: the former protects the value of the records while the latter also protects their presence in the data: together, they protect any property about a single individual.

In many scenarios, it makes sense to protect a different property about their dataset, e.g., the value of a specific sensitive field, or entire groups of individuals. It is straightforward to adapt DP to protect different sensitive properties: all one has to do is change the definition of neighborhood in the original definition.

Changing the sensitive property

The original definition states that the $ε$ -indistinguishability property should hold for “any datasets $D_{1}$ and $D_{2}$ that differ only on the data of one individual”. Modifying the set of pairs $(D_{1}, D_{2})$ such that $M (D_{1}) \approx_{ε} M (D_{2})$ is equivalent to changing the protected sensitive property.

Weaker notions

In DP, the difference between $D_{1}$ and $D_{2}$ is sometimes interpreted as “one record value is different”, or “one record has been added or removed”. In [KM11], the authors formalize these two options as bounded DP and unbounded DP. They also introduced attribute DP and bit DP, for smaller changes within the differing record.

Definition 20 ( [KM11]). If a privacy mechanism $M$ satisfies $M (D_{1}) \approx_{ε} M (D_{2})$ for any pair $D_{1}, D_{2}$ , where $D_{1}$ can be obtained from $D_{2}$ by…

…adding or removing one record, then $M$ is $ε$ -unbounded DP (uBoDP).
…changing exactly one record, then $M$ is $ε$ -bounded DP (BoDP).
…changing one attribute in a record, then $M$ is $ε$ -attribute DP (AttDP).
…changing one bit of an attribute in a record, then $M$ is $ε$ -bit DP (BitDP).

In [KM11], authors show that $ε$ -unbounded DP implies $2 ε$ -bounded DP, as changing a record can be seen as deleting it and adding a new one in its place. The original definition of $ε$ -DP is the conjunction of $ε$ -unbounded DP and $ε$ -bounded DP. However, bounded DP is frequently used in the literature: locally differentially private mechanisms, in particular, in which each user randomizes their own data before sending it to the aggregator, typically uses bounded DP. It is often simply called differential privacy, and sometimes renamed, like in [FMTT18], where the authors call it per-person DP.

Variants of differential privacy that do not protect individuals, but single contributions (in the case where the same person can contribute multiple times to a dataset), are also often used in practice, especially for machine learning applications [MRTZ18]. Some recent works also argue that in-between definitions are appropriate: rather than protecting a single contribution or entire users contributions, authors in [ADJ19] suggest that protecting elements that reveal information about users, after deduplicating or clustering contributions. For example, rather than protecting all website visits by a single user, or each visit individually, one might choose to protect the fact that a user ever visited a website (but not whether the user visited the same website once or many times). They call the corresponding definition element-level DP (ELDP).

Another way to relax the neighborhood definition in DP is to consider that only certain types of information are sensitive. For example, if the attacker learns that their target has cancer, this is more problematic than if they learn that their target does not have cancer. This idea is captured in one-sided DP [KDH $+$ 20]: the neighbors of a dataset $D$ are obtained by replacing a single sensitive record with any other record (sensitive or not). The idea of sensitivity is formalized by a policy $P$ , which specifies which records are sensitive. This idea cannot be captured simply by $ε$ -indistinguishability, since one-sided DP is asymmetric.

Definition 21 ( $(P, ε)$ -one-sided differential privacy [KDH $+$ 20]). Given a policy $P \subseteq T$ , a privacy mechanism $M$ is $(P, ε)$ -one-sided DP (OSDP) iff for all datasets $D_{1}$ and $D_{2}$ , where $D_{2}$ has been obtained by replacing a record $t \in D_{1} \cap P$ by any other record and for all $S \subseteq O$ :

P [M (D_{1}) \in S] \leq e^{ε} \cdot P [M (D_{2}) \in S] .

When $P = T$ , this is equivalent to bounded DP. Similar ideas were proposed in multiple papers:

In [APV19], the authors propose sensitive privacy, which determines which records are sensitive based on the data itself and a normality property $N$ and a graph-based definition of $k$ -neighborhood, instead of using a data-independent determination.
In [BSW18], the authors introduce anomaly-restricted DP, which assumes that there is only one outlier in the dataset, and that this outlier should not be protected.

Stronger notions

More restrictive definitions are also possible. First, some definitions make the definition of neighborhood more explicit when a single person can contribute multiple times to a dataset; this is the case for client/participant DP, defined in [MRTZ18]. In [Dwo08], the authors implicitly define $(c, ε)$ -group privacy considers datasets that do not differ in one record, but possibly several, to protect multiple individuals. This can also be interpreted as taking correlations into account when using DP: DP under correlation [CFYD14] uses an extra parameter to describe the maximum number of records that the change of one individual can influence.

These two definitions are formally equivalent; but the implicit interpretation of DP behind them is different. $(c, ε)$ -group privacy is compatible with the associative view under the strong adversary assumption (the adversary knows all records except $c$ ) or the causal view ( $c$ records are changed after the data is generated). Meanwhile, DP under correlation implicitly considers the associative view with the independence assumption; and tries to relax that assumption. This last approach was further developed via dependent DP [LCM16], which uses “dependence relationships” to describe how much the variation in one record can influence the other records.

Definition 22 ( $(R, c, ε)$ -dependent differential privacy [LCM16]). A privacy mechanism $M$ is $(R, c, ε)$ -dependent DP (DepDP) where $R$ is the probabilistic dependence relationship and $c$ is the dependence size, if for any pair of datasets $D_{1}$ and $D_{2}$ , where $D_{2}$ has been obtained from $D_{1}$ by changing one record and the corresponding at most $c - 1$ other records according to $R$ , $M (D_{1}) \approx_{ε} M (D_{2})$ .

Note that when $R$ is the empty relation, or when $c = 1$ , this definition is equivalent to bounded DP: under the associative view of DP, this represents independence between records. Similar definitions appear in [WDN17, WWK $+$ 17] as correlated DP (CorDP), in which correlations are defined by an observation on other datasets, and in in [YSN15] as bayesian DP⁶ (BayDP^[YSN15]), where the neighborhood relation is defined by an adversary having some knowledge about correlations in the data. An extension is proposed in [LRYY19] as prior DP (PriDP) which considers a family of adversaries instead of a single adversary. The strongest possible variant is considered in [KM11], where the authors define free lunch privacy, in which the attacker must be unable to distinguish between any two datasets, even if they are completely different. This guarantee can be interpreted as a reformulation of Dalenius’ privacy goal [Dal77], which we mentioned in Section 2.1.6. As such, all mechanisms that satisfy free lunch privacy have a near-total lack of utility.

Definition 23 ( $ε$ -free lunch privacy [KM11]). A privacy mechanism $M$ satisfies $ε$ -free lunch privacy (FLPr) if $M (D_{1}) \approx_{ε} M (D_{2})$ for any pair of datasets $D_{1}, D_{2}$ .

Limiting the scope of the definition

Redefining the neighborhood property can also be used to reduce the scope of the definitions. In [SCDFSM17], the authors note that DP requires $ε$ -indistinguishability of results between any pair of neighboring datasets, but in practice, the data custodian has only one dataset $D$ they want to protect. Thus, they only require $ε$ -indistinguishability between this dataset $D$ and all its neighbors, calling the resulting definition individual DP. An equivalent definition was proposed in [CH16] as conditioned DP.

Definition 24 ( $(D, ε)$ -individual differential privacy [SCDFSM17]). Given a dataset $D \in D$ , a privacy mechanism $M$ satisfies $(D, ε)$ -individual DP (IndDP) if for any dataset $D^{'}$ that differs in at most one record from $D$ , $M (D) \approx_{ε} M (D^{'})$ .

This definition was further restricted in [Wan17] where besides fixing a dataset $D$ , a record $t$ is also fixed.

Applying the definition to other types of input

Many adaptations of differential privacy are simply changing the neighborhood definition to protect different types of input data than datasets. A few examples follow.

In [EG16, CBY $+$ 18, XX15], the authors adopted differential privacy for locations. In [EG16] the authors defined location privacy, in which neighbors are datasets which differ in at most one record, and the two differing records are at a physical distance smaller than a given threshold. This definition also appears in [CBY $+$ 18] as DP on $r$ -location set⁷. Several more location-related differential privacy variants were defined in [NV20]: untrackability (which adopts differential privacy for set of locations by protecting whether they originated from a single user or by two users), undetectability and multi user untrackability, (which extend this idea further by not assuming both sets originated from the same private data and to multiple users respectively).
In [HLMJ09, TC12, Reu18, Pin18, SXK $+$ 19, DWWG13], the authors adopt differential privacy to graph-structured data. In [HLMJ09], authors present multiple alternative definitions, which protect different parts of the graph: the strongest is node-DP, which protects a node and all its edges; the weakest is edge-DP, only protects one edge; and an intermediate definition is $k$ -edge-DP, which protects a total of $k$ edges and nodes. In [TC12], the authors introduce out-link privacy, which protects all outgoing edges from a given node. In [Reu18], the author introduces $QL$ -edged-labeled DP similar to out-link privacy, but only protecting a predetermined subset of outgoing edges. In [Pin18], the author introduces $l_{1}$ -weighted DP, in which graph edges are weighted, and graphs are neighbors when the total weight of their differing edges is smaller than 1; this notion was also defined implicitly in [Sea16]. In [SXK $+$ 19], the authors define decentralized DP which extends the graph neighborhood to two jumps. In [KRWY16], the authors introduce protected DP, which adapts DP for graphs and guarantees that no observer can learn much about the set of edges corresponding to any protected node while offering no guarantees for the other nodes. Finally, in [DWWG13] the authors introduce seamless privacy, which rather than protecting characteristics of a specific input graph, it ensures that certain pairs of queries on this graph return similar answers.
In [DNPR10, DNP $+$ 10, Dwo10, KPXP14, Far20, WSMD20], authors adapt differential privacy to a streaming context, where the attacker can access the mechanism’s internal states. In [DNPR10, DNP $+$ 10, Dwo10], authors define pan-privacy, which comes in two variants: event-level pan-privacy (called strong DP in [WSMD20]) protects individual events, and user-level pan-privacy protects all events associated to a single user. In [KPXP14], the authors extend the previous idea and propose $w$ -event privacy, which protects any event sequence occurring within a window of at most $w$ timestamps. In [Far20, NV20] this was further extended to an infinite horizon via discounted differential privacy (which keep assigning smaller-and-smaller weights to further-and-further events) and everlasting privacy (which limit the leakage of information users suffer, no matter how many executions a mechanism had), respectively.
In [WCM18] the authors adopt differential privacy for Random Access Memory and Private Information Retrieval. For RAM the neighborhood is defined over the sequence of logical memory requests over time; the same notion appears in [CCMS19] as differential obliviousness and in [ADK $+$ 19] as oblivious DP. The adaptation of neighborhood is similar in case of PIR; a similar notion appears in [TDG16] as $ε$ -private PIR and in [PPY19] as $ε$ -DPIR. Additionally, in [KKNO17], the authors use a similar idea to define differential privacy for outsourced database systems.
In [JLH19], the authors adapt differential privacy for symbolic control systems, and introduce word-DP and substitution-word-DP, protecting respectively pairs of words whose Levenshtein distance is lower than a given parameter, or whose Hamming distance is lower than a given parameter.
In [ZSZ $+$ 18], the authors adapt differential privacy for text vectors, and propose text indistinguishability, in which the neighborhood relationship between two word vectors depends on their Euclidean distance.
In [YLL $+$ 17] the authors defined set operation DP, which adopts differential privacy for set operations where ${D_{1}, D_{2}}$ and ${D_{1}, D_{2}}_{1}^{'}$ are neighbor if either $D_{1}$ and $D_{1}^{'}$ or $D_{2}$ and $D_{2}^{'}$ are neighbors.
In [YWW13, LAG $+$ 19], the authors define refinement DP and pixel DP respectively, which adopts the definition for images with neighbors given by some transformation or metric.
In [HD19], the authors adopt DP to gossip protocols to protect the privacy of information source.
In [Noz19], the authors define functional DP, which adopts differential privacy for functions.
In [SSB16], the authors define phenotypic DP, which adopts differential privacy for genomic data, where the difference in the phenotype vector defines the neighborhood.
In [GKPT15], the authors adapt differential privacy to recommendation systems, and define distance-based DP, which protects not only a given user recommendation but also all the recommendations of a given user for similar items.
In [LBG17], the authors adapt differential privacy to machine learning, and define differential training privacy, which quantifies the risk of membership inference of a record with respect to a classifier and its training data.
In [TD16], the authors define DP for bandit algorithms, where the neighborhood notion is defined by changing any single reward in a multi-armed bandit game sequence. In [BDT19], this definition is renamed to instantaneous DP (Def 5), and few more variants are proposed for this problem space: local DP for bandits, pan-privacy for bandits, sequential privacy for bandits, and environment privacy for bandits.

Extensions

It is natural to generalize the variants of this section to arbitrary neighboring relationships. One example is mentioned in [KM11], under the name generic DP⁸, where the neighboring relation is entirely captured by a relation $R$ between datasets.

Definition 25 ( $(R, ε)$ -generic differential privacy [KM11]). Given a relation $R \subseteq D^{2}$ , a privacy mechanism $M$ satisfies $(R, ε)$ -generic DP (GcDP^[KM11]) if for all $(D_{1}, D_{2}) \in R$ , $M (D_{1}) \approx_{ε} M (D_{2})$ .

This definition is symmetric, but it can easily be modified to accommodate asymmetric definitions like one-sided DP.

Other definitions use different formalizations to also generalize the concept of changing the neighborhood relationship. Some (like pufferfish privacy, see Definition 35 in Section 2.2.5) use pairs of predicates that $D_{1}$ and $D_{2}$ must respectively satisfy to be neighbors. Others (like coupled-worlds privacy, see Definition 44 in Section 2.2.7) use private functions taking datasets as input, and define neighbors to be datasets that have a different output according to this private function. Others use a distance function between datasets, and neighbors are defined as datasets a distance lower than a given distance threshold; this is the case for DP under a neighborhood (DPUN), introduced in [FC14], adjacent DP (AdjDP), introduced in [KM20]⁹, constrained DP (ConsDP), introduced in [ZLW09] (where the distance captures a utility-related constraint), and distributional privacy¹⁰ (DlPr^[ZLW09]), also introduced in [ZLW09] (with additional constraints on the neighborhood definition: neighboring datasets must be part of a fixed set and have elements in common). This distance can also be defined as the sensitivity of the mechanism, like in sensitivity-induced DP [RA17] (SIDP), or implicitly defined by a set of constraints, like what is done implicitly in [KM11] via induced neighbors DP (INDP). One notable instantiation of generic DP is blowfish privacy [HMD14]. Its major building blocks are a policy graph $G$ , that specifies which pairs of domain values in $T$ should not be distinguished between by an adversary; and a set of constraints $Q$ that specifies the set of possible datasets that the definition protects. It was inspired by the Pufferfish framework [KM12] (see Definition 35 in Section 2.2.5), but the attacker is not assumed to have uncertainty over the data: instead, it models an attacker whose knowledge is a set of deterministic constraints on the data.

Definition 26 ( $(G, Q, ε)$ -blowfish privacy [HMD14, HMD15]). Given a policy graph $G \in T^{2}$ and a set of constraints $Q$ , a privacy mechanism $M$ satisfies $(G, ε)$ -blowfish privacy (BFPr) if for all datasets $D_{1}$ and $D_{2}$ that satisfy constraints $Q$ and differ in only one element $i$ such that $(D_{1} (i), D_{2} (i)) \in G$ , $M (D_{1}) \approx_{ε} M (D_{2})$ .

As noted in [HMD14], a mechanism satisfies $ε$ -bounded DP if and only if satisfies $(K, J_{n}, ε)$ -blowfish privacy, where $K$ is the complete graph, and $J_{n}$ is any datasets of size $n$ . A particular instantiation of this idea is explored in [KM11] as induced DP, where the definition of neighbors is induced by a set of constraints.

Multidimensional definitions

Modifying the protected property is orthogonal to modifying the risk model implied by the quantification of privacy loss: it is straightforward to combine these two dimensions. Indeed, many definitions mentioned in this section were actually introduced with a $δ$ parameter allowing for a small probability of error. One particularly general example is adjacency relation divergence DP [KM19a], which combines an arbitrary neighborhood definition (like in generic DP) with an arbitrary divergence function (like in divergence DP).

As the examples in Section 2.2.3 show, it is very common to change the definition of neighborhood in practical contexts to adapt what aspect of the data is protected. Further, local DP mechanisms like RAPPOR [EPK14] implicitly use bounded DP: the participation of one individual is not secret, only the value of their record is protected. Variants that limit the scope of the definition to one particular dataset or user, however, provide few formal guarantees and do not seem to be used in practice.

⁶There are two other notions with the same name: introduced in [TF20, LL12], we mention them in Section 2.2.4 and 2.2.5 respectively.

⁷Distinct from DP on $δ$ -location set [XX15], which we mention in Section 2.2.4.

⁸Another definition with the same name is introduced in [KL10, KL12], we mention it in Section 2.2.4.

⁹Originally simply called “differential privacy” by its authors.

¹⁰Another definition with the same name is introduced in [Rot10, BLR13], we mention it in Section 2.2.4.

LINKPREV LINKUP LINKNEXT