Attacks on Deidentification's Defenses

Introduction

A relatively small number of data points suffice to distinguish individuals from the general population. For example, in the 2010 census 44% of the population was unique based only on census block, age, and sex . Turning this insight into a privacy notion, $k$-anonymity aims to capture a sort of anonymity of a crowd.

Real world reidentification attacks, including on the Netflix and AOL datasets , led to a policy debate about the QI-deidentification. Critics argued that the distinction between quasi-identifying attributes and other attributes—foundational to the whole approach—was untenable . Defenders argued that deidentification experts are good at determining what information is externally available . The debate left unspoken and unexamined the core tenet of QI-deidentification: that if every attribute is treated as a quasi-identifier, then $k$-anonymity provides meaningful protection. Our work is the first to directly challenge that tenet.

Why bother attacking QI-deidentification? After all, the security and privacy research communities don’t put much stock in these techniques. For example, it is well known that contrived mechanisms can formally satisfy $k$-anonymity but provide no protection. Even so, many policymakers and practitioners are convinced that QI-deidentification is effective in the real world.

Our goal in this paper is to rebut the actual arguments that QI-deidentification practioners use to justify its continued use. We rebut three arguments that—until this work—have gone unchallenged. First, that no attacks have been shown against datasets deidentified by experts and in accordance with strict privacy regulations, let alone simple attacks. Second, that $k$-anonymity provides meaningful protection when every attribute is a quasi-identifier. Third, that although QI-deidentification doesn’t meet cryptographic standards of security, it suffices to meet the obligations in data protection regulation. We briefly elaborate these three arguments next.

Rhetorically, trust in QI-deidentification hinges on the wholesale dismissal of existing attacks as unconvincing. Practitioners dismiss many attacked datasets as “improperly de-identified” . “Proper de-identification” must be done by a “statistical expert” and in accordance with procedures outlined in regulation , the increasing availability of QI-deidentification software notwithstanding. This argument has proven very effective in policy spheres. Moreover, practitioners dismiss attacks carried out by privacy researchers because they are privacy researchers. That these attacks are published in “research based articles within the highly specialized field of computer science” is used to argue that re-identification requires a “highly skilled ‘expert’ ” and therefore is of little concern .

Technically, trust in QI-deidentification hinges on an unspoken, unexamined tenet:

QI-deidentification’s tenet: If every attribute is treated as quasi-identifying, then $k$-anonymity provides meaningful protection.

Legally, the use of QI-deidentification hinges on the gap between the protection required by regulation and the protection desired by the academic research community. Practitioners claim only that QI-deidentification meets regulatory standards, not security researchers’ stringent standards. For example, cryptographic security definitions typically make no assumptions about the techniques or auxiliary knowledge available to an adversary. However, the European Union’s General Data Protection Regulation (GDPR) restricts the adversary’s techniques by protecting only against “means reasonably likely to be used” by an attacker.GDPR, Article 4 Likewise, the United State’s Family Educational Rights and Privacy Act (FERPA) restricts the adversary’s knowledge by protecting only against an attacker lacking “personal knowledge of the relevant circumstances.”34 CFR §99.3

We present three attacks on QI-deidentification schemes: two theoretical attacks and one real world reidentification attack. Together, these attacks undermine the above justifications for the continued use of QI-deidentification.

First, we introduce a new class of privacy attack called downcoding, which recovers large fractions of the data hidden by QI-deidentification without any auxiliary knowledge. In short, downcoding undoes hierarchical generalization. A downcoding attack takes as input a dataset generalized and recovers some fraction of the generalized data. We call this downcoding as it corresponds to recoding records down a generalization hierarchy.

We prove that every QI-deidentification scheme is vulnerable to downcoding attacks if it is minimal and hierarchical. QI-deidentification is hierarchical if it works by generalizing attributes according to a fixed hierarchy (e.g., city$\to$country$\to$continent). QI-deidentification is minimal if no record is generalized more than necessary to achieve the privacy requirement, in a weak, local sense. Our downcoding attacks are powered by a simple observation: minimality leaks information. Figures 1 and 2 give simple examples of downcoding and of leakage from minimality, respectively.

Second, we convert our downcoding attacks into powerful predicate singling-out (PSO) attacks. PSO attacks were recently proposed as a way to demonstrate that a privacy mechanism fails to legally anonymize under the GDPR . We introduce a stronger type of PSO attack called compound PSO attacks and prove that minimal hierarchical QI-deidentification enables compound PSO attacks, greatly improving over the prior work.

Our downcoding and PSO attacks are the first attacks on QI-deidentification that work even when every attribute is a quasi-identifier. As such, they apply to QI-deidentification beyond $k$-anonymity, and refute the foundational tenet of QI-deidentification.

Third, we used LinkedIn.com to reidentify 3 students in a $k$-anonymized dataset published by Harvard and MIT from their online learning platform EdX. Despite being “properly” $k$-anonymized by “statistical experts” in accordance with FERPA, we show that thousands more students are potentially vulnerable to reidentification and disclosure.

Not only do these attacks rebut the arguments described above, they also show that QI-deidentification fails to satisfy three properties of a worthwhile measure of privacy of a computation, even without resorting to contrived mechanisms. Namely, we show that QI-deidentification mechanisms used in practice aren’t robust to post-processing, do not compose, and rely on distributional assumptions on the data for their security.

Section 2 discusses related work. Section 3 introduces notation and defines $k$-anonymity, along with hierarchical and minimal $k$-anonymity. Section 4 defines downcoding attacks and proves that minimal hierarchical $k$-anonymous mechanisms enable them. Section 5 defines compound predicate singling-out attacks and proves that minimal hierarchical $k$-anonymous mechanisms enable them. Section 6 describes the EdX dataset and shows that it is vulnerable to reidentification. Section 7 concludes that our attacks rebut the three core arguments that support the continued use of QI-deidentification in practice. The appendix includes additional details and proofs.

Related Work

Predicate singling-out (PSO) attacks were recently introduced in the context of data anonymization under Europe’s General Data Protection Regulation (GDPR) . They were proposed as a mathematical test to show that a privacy mechanism fails to legally anonymize data under Europe’s General Data Protection Regulation (GDPR) . The prior work gives a simple but weak PSO attack against a large class of $k$-anonymous mechanisms. We give much stronger PSO attacks against a restricted class of $k$-anonymous mechanisms.

Prior work shows that $k$-anonymity does not compose: multiple $k$-anonymous datasets can completely violate privacy when combined . We show for the first time that composition failures can occur in real world uses of $k$-anonymity.

Differential privacy (DP) presents one alternative to QI-deidentification, especially DP synthetic data or local DP . Switching to DP requires accepting that the resulting data will not provide the one-to-one correspondence with underlying records that makes QI-deidentification so attractive to users and laypeople.

We reviewed the deidentification definitions included in the most comprehensive survey we could find . Our downcoding attacks apply to any refinement of $k$-anonymity: namely, any definition that collapses to $k$-anonymity when every attribute is quasi-identifying. These include:

$k$-anonymity and variants: $k^{m}$-, $(\alpha,k)$-, $p$-sensitive-, $(k,p,q,r)$-, and $(\epsilon,m)$-anonymity

$t$-closeness and variant $(n,t)$-closeness

Our downcoding attacks don’t apply to Anatomy (which doesn’t generalize quasi-identifiers at all) or differential privacy (which eschews the quasi-identifier framework all together). We have not determined whether the following definitions – which bound some posterior probability given the deidentified dataset – refine $k$-anonymity in the relevant sense: $\delta$-presence, $\varepsilon$-privacy, skyline privacy, $(\rho_{1},\rho_{2})$-privacy, $(c,k)$-safety, and $\rho$-uncertainty.

We leave testing our downcoding attacks on actual deidentification software packages for future work. Free to use software packages include ARX Anonymization, $\mu$-Argus, sdcMicro, University of Texas Toolkit, Amnesia, Anonimatron, Python Mondrian. All but Python Mondrian implement hierarchical algorithms. ARX Anonymization, sdcMicro, and Amenesia offer some version of local recoding (footnote 5). To the best of our knowledge, none guarantee minimality.

Preliminaries

$\mathcal{U}^{D}$ is a $D$-dimensional data universe, where $\mathcal{U}$ is the attribute domain. For simplicity we take all attribute domains to be identical, though in reality they are usually distinct (e.g., the EdX dataset).

A record $\mathbf{x}=(x_{1},\dots,x_{D})$ is an element of the data universe. A generalized record $\mathbf{y}$, denoted $(y_{1},\dots,y_{D})$, is a subset of the data universe specified by the Cartesian product $y_{1}\times\dots\times y_{D}$, where $y_{d}\subseteq\mathcal{U}$ for every $d\in[D]$. Note that a record $\mathbf{x}$ naturally corresponds to the generalized record $(\{x_{1}\},\dots,\{x_{D}\})$, a singleton. We say $\mathbf{y}$ generalizes $\mathbf{x}$ if $\mathbf{x}\in\mathbf{y}$ (i.e., $\forall d,\ x_{d}\in y_{d}$). For example, $\mathbf{y}=(Female,1970\text{--}1975)$ generalizes $\mathbf{x}=(Female,1972)$. For generalized records $\mathbf{z}\subseteq\mathbf{y}$, we say that $\mathbf{y}$ generalizes $\mathbf{z}$ and $\mathbf{z}$ refines $\mathbf{y}$. If $\mathbf{z}\subsetneq\mathbf{y}$, the generalization/refinement is strict.

A dataset $\mathbf{X}$ is an $N$-tuple of records $(\mathbf{x}_{1},\dots,\mathbf{x}_{N})$. $\mathbf{X}$ can be viewed as a matrix with $\mathbf{X}_{n,d}$ the $d$th coordinate of $\mathbf{x}_{n}$. A generalized dataset $\mathbf{Y}$ is an $N$-tuple of generalized records $(\mathbf{y}_{1},\dots,\mathbf{y}_{N})$. For (generalized) datasets $\mathbf{Y},\mathbf{Z}$, we write $\mathbf{Z}\preceq\mathbf{Y}$ if $\mathbf{z}_{n}\subseteq\mathbf{y}_{n}$ for all $n$. We extend the meaning of generalization and refinement accordingly. We write $\mathbf{Z}\prec\mathbf{Y}$ when at least one containment is strict. We call $\mathbf{y}_{n}$ the record in $\mathbf{Y}$ corresponding to $\mathbf{z}_{n}$, and vice-versa. Note that $\preceq$ is a partial order on datasets of $N$ records from a given data universe.More generally, we could consider datasets whose rows are permuted relative to one another. Define $\mathbf{Z}\preceq\mathbf{Y}$ if there exists a permutation $\pi:[N]\to[N]$ such that $\mathbf{z}_{n}\subseteq\mathbf{y}_{\pi(n)}$ for all $n$, choosing some canonical $\pi$ arbitrarily if more than one exists. Then $\preceq$ is a partial order over equivalence classes of datasets induced by $\mathbf{Y}\sim\mathbf{Y}^{\prime}\iff\exists\pi\ \forall n\ \mathbf{y}_{n}=\mathbf{y}^{\prime}_{\pi(n)}$. We omit this additional complexity for clarity. We believe all our results would hold, mutatis mutandis.

2 k𝑘k-anonymity

Formally, $\mathbf{Y}$ is $k$-anonymous if any individual row in the release cannot be distinguished from $k-1$ other individuals . This requirement is typically parameterized by a subset $Q$ of the attribute domains $Q\subseteq\{\mathcal{U}_{d}\}_{d\in[D]}$ called a quasi-identifier. We denote by $\mathbf{y}(Q)$ the restriction of $\mathbf{y}$ to $Q$. For $\mathbf{Y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{N})$, we denote by $I(\mathbf{Y},\mathbf{y},Q)\triangleq\{n:\mathbf{y}_{n}(Q)=\mathbf{y}(Q)\}$ the indices of records in $\mathbf{Y}$ that match $\mathbf{y}$ on $Q$ (including $\mathbf{y}$ itself). Let $\mathsf{EA}(\mathbf{Y},\mathbf{y},Q)=|I(\mathbf{Y},\mathbf{y},Q)|$. This is called the effective anonymity of $\mathbf{y}$ in $\mathbf{Y}$ with respect to $Q$.

For $k\geq 2$, $\mathbf{Y}$ is $k$-anonymous with respect to $Q$ if for all $\mathbf{y}\in\mathbf{Y}$, $\mathsf{EA}(\mathbf{Y},\mathbf{y},Q)\geq k$. An algorithm $M:\mathbf{X}\mapsto\mathbf{Y}$ is $k$-anonymizer if for every $\mathbf{X}$, $\mathbf{Y}\leftarrow M(\mathbf{X})$ is $k$-anonymous (anonymity) and generalizes $\mathbf{X}$ (correctness). We omit $Q$ when $Q=\mathcal{U}^{D}$ is the whole data universe.

A few remarks are in order. First, beyond correctness and anonymity, $k$-anonymity places no restriction on the output $\mathbf{Y}$. Second, the term quasi-identifier is inconsistently defined in the literature. Our definition of a quasi-identifier as the collection of multiple attributes is from Sweeney . Quasi-identifier is commonly used to refer to one of the constituent attributes—including by the authors of the EdX dataset . So each -quasi-identifier consists of multiple -quasi-identifers. We adopt the quasi-identifier-as-a-set definition because it simplifies the discussion of the EdX dataset in Section 6. The distinction disappears in Sections 4 and 5: our downcoding and PSO attacks work even when every attribute is part of the quasi-identifier (i.e., $Q=\mathcal{U}^{D}$).

It is easy to contrive $k$-anonymizers that reveal $\mathbf{X}$ completely. Directing our attention to more natural and widespread mechanisms, we focus on hierarchical $k$-anonymizers.

A common way of $k$-anonymizing data is to generalize an attribute domain $\mathcal{U}$ according to a data-independent generalization hierarchy $H$ which specifies how a given attribute may be recoded. Hierarchical algorithms differ on whether they use local recoding or global recoding. Using local recoding, attributes in different records can be generalized to different levels of the hierarchy. Using global recoding, all records must use the same level in the hierarchy for any given attribute. We consider local recoding which produces higher quality datasets in general. Many natural ways of generalizing data fits this mold: using nesting geographies (e.g., city$\to$state$\to$country); dropping digits of postal codes (e.g., $91011\to 9101\star\to 910\star\star$); grouping ages into ranges of 5, 10, 25, or 50 years; suppressing attributes or whole records altogether; and the techniques used to create the EdX dataset.

Formally, a generalization hierarchy $H$ defines a structured collection of permissible subsets $\mathbf{y}$ of an attribute domain $\mathcal{U}$ (Figure 5). $H$ is a rooted tree labelled by subsets of $\mathcal{U}$, where the subsets on any level of $H$ form a partition of $\mathcal{U}$ and the partition on every level is a strict refinement of the partition above. The label of the root is $\mathcal{U}$ itself, and the leaves are all labelled with singletons $\{x\}$. Identifying $H$ with the set of all its labels, we write $y\in H$ if there is some node in $H$ labelled by $y$. We extend the hierarchy $H$ to the data universe $\mathcal{U}^{D}$ coordinate-wise, writing $\mathbf{y}\in H^{D}$ if $y_{d}\in H$ for all $d\in[D]$.

$\mathbf{Y}$ respects $H$ if $\mathbf{y}\in H^{D}$ for all $\mathbf{y}\in\mathbf{Y}$. An algorithm $M:(\mathbf{X},H)\mapsto\mathbf{Y}$ is a hierarchical $k$-anonymizer if for all $\mathbf{X}$ and all hierarchies $H$, $M_{H}:\mathbf{X}\mapsto M(\mathbf{X},H)$ is a $k$-anonymizer and its output $\mathbf{Y}=M(\mathbf{X},H)$ respects $H$.

Observe that one can always implement hierarchical $k$-anonymity by simply outputting $N$ copies of $\mathcal{U}^{D}$. But a privacy technique that completely destroys the data is not useful, which leads us to consider data quality.

We consider minimal mechanisms . A mechanism is minimal if no record is generalized more than necessary to achieve the privacy requirement (in a local way). For example, suppose a $k$-anonymous $\mathbf{Y}$ contains a location attribute. If there is a subset of records whose location “USA” can be changed to “California” without violating $k$-anonymity, then the mechanism that produced $\mathbf{Y}$ would not be minimal. Anoter example is given in Figure 2. We call this property minimality because it is equivalent to requiring minimality with respect to the partial ordering $\preceq$. Unlike global optimality, minimality is computationally tractable.

$M:(\mathbf{X},H)\mapsto\mathbf{Y}$ is minimal if $\mathbf{Y}$ is always minimal in the set of all $H$-respecting, $k$-anonymous $\mathbf{Y}$ that generalize $\mathbf{X}$, partially ordered by $\preceq$. That is, for all strict refinements $\mathbf{Z}\prec\mathbf{Y}$, either: (a) $\mathbf{Z}$ is not $k$-anonymous, (b) $\mathbf{Z}$ does not respect $H$, or (c) $\mathbf{Z}$ does not generalize $\mathbf{X}$.

Downcoding attacks on syntactic privacy techniques

In short, downcoding undoes hierarchical generalization. A downcoding attack takes as input a dataset generalized and recovers some fraction of the generalized data. We call this downcoding as it corresponds to recoding records down a generalization hierarchy. Our downcoding attacks are powered by a simple observation: minimality leaks information. Figures 1 and 2 give simple examples of downcoding and of leakage from minimality, respectively.

We prove that there exist data distributions and hierarchies such that every minimal hierarchical $k$-anonymizer is vulnerable to downcoding attacks. Hence any privacy provided by QI-deidentification is subject to distributional assumptions.

The downcoding attack adversary $\mathsf{A}$ gets as input a QI-deidentified dataset $\mathbf{Y}$ which is the output of an unknown mechanism $M$ on an unknown dataset $\mathbf{X}$. $\mathsf{A}$ also knows anything published with $\mathbf{Y}$, namely $N$, $k$, and the hierarchy $H$. (Without $H$ data users would be unable to interpret $\mathbf{Y}$.) Finally we also allow the adversary to depend on the data distribution $U$. One interpretation is that the security that a mechanism affords against downcoding attacks depends on limiting the attacker’s knowledge, which is not good security practice. Moreover, in many settings $U$ can be efficiently learned from an independent sample $\mathbf{X}^{\prime}$.

Formally, we construct a distribution $U$ over $\omega(\log n)$ attributes and a generalization hierarchy $H$ such that every minimal hierarchical algorithm enables downcoding attacks on datasets drawn i.i.d. from $U$. Our first attack uses a natural data distribution (i.e., clustered heteroskedastic data in Section 4.4) and a tree-based hierarchy, and allows an attacker to completely recover a constant fraction of the deidentified records with high probability. Our second attack uses a less natural data distribution and hierarchy, and allows an attacker to recover $3/8$ths of every record with 99% probability.

2 Definition

Let $\mathbf{Y}$ be a $k$-anonymous version of a dataset $\mathbf{X}$ with respect to generalization hierarchy $H$. A downcoding attack takes $\mathbf{Y}$ as input and outputs a strict refinement $\mathbf{Z}$ of $\mathbf{Y}$ that simultaneously respects $H$ and generalizes $\mathbf{X}$.

Let $\mathbf{Y}$ be a hierarchical $k$-anonymous generalization of a (secret) dataset $\mathbf{X}$ with respect to some hierarchy $H$. $\mathbf{Z}$ is a downcoding of $\mathbf{Y}$ if $\mathbf{X}\preceq\mathbf{Z}$, $\mathbf{Z}\prec\mathbf{Y}$, and $\mathbf{Z}\in H$.

If $\mathbf{Y}$ is minimal and $\mathbf{Z}$ is a downcoding of $\mathbf{Y}$, then $\mathbf{Z}$ violates $k$-anonymity.

We consider three measures of an attack’s strength: How many records are refined? How much are records refined? How often records refined? Recall that if $\mathbf{Z}\prec\mathbf{Y}$, then $\mathbf{z}_{n}\subseteq\mathbf{y}_{n}$ for all $n$ and $\mathbf{z}_{n}\subsetneq\mathbf{y}_{n}$ for at least one $n$.

$\daleth$:$\daleth$ is pronounced “dah-let” and is the fourth letter of the Hebrew alphabet. How often are records refined? Consider the probability experiment $\mathbf{X}\sim U^{N}$, $\mathbf{Y}\leftarrow M(\mathbf{X},H)$, and $\mathbf{Z}\leftarrow\mathsf{A}(\mathbf{Y})$ where $U$ is a distribution over data records, $M$ is a $k$-anonymizer, and $\mathsf{A}$ is a downcoding adversary. $\daleth(\Delta_{N},\Delta_{D})\in$ is the probability that $\mathbf{Z}$ downcodes with parameters at least $\Delta_{N}$ and $\Delta_{D}$. For any fixed $\Delta_{N}$ and $\Delta_{D}$, an attacker prefers larger $\daleth$.

3 Minimal k𝑘k-anonymizers enable downcoding attacks

Downcoding may seem impossible: How can one strictly refine $\mathbf{Y}$ using only the information contained in $\mathbf{Y}$ itself? Our attacks leverage minimality. The mere fact that $\mathbf{Y}$ is a minimal hierarchical generalization of $\mathbf{X}$ reveals more information about $\mathbf{X}$ that we use for strong downcoding attacks. See Figure 2 for a simple example.

A general-purpose hierarchical $k$-anonymizer $M$ works for every generalization hierarchy $H$. Our theorems state that there exist data distributions $U$ and corresponding hierarchies $H$ such that every minimal hierarchical $k$-anonymizer $M$ is vulnerable to downcoding. By Observation 4.1, these attacks defeat the $k$-anonymity of $M$.

For all constants $k\geq 2$, $\alpha>0$, $D=\omega(\log N)$, and $T=\lceil N^{2}/\alpha\rceil$, there exists a distribution $U$ over $\mathcal{U}^{D}=[0,T]^{D}$, and a generalization hierarchy $H$ such that all minimal hierarchical $k$-anonymizers $M$ enable downcoding attacks with $\Delta_{N}=N$, $\Delta_{D}=D$, and $\daleth(N,D)>1-\alpha$. The attack also works for $k=N$ and $D=\omega(N\log N)$.

Each of the theorems has some advantages over the other. The attacker in Theorem 4.3 manages to recover every attribute of every record $\mathbf{x}\in\mathbf{X}$ except with probability $\alpha$. However the parameters of the construction depend polynomially on $1/\alpha$. Theorem 4.2 removes this dependency, at the expense of attacking only a constant fraction of records and attributes—still a serious failure of $k$-anonymity. The more significant advantage of Theorem 4.2 is that the data distribution and generalization hierarchy are both very natural (Example B.2). In contrast, the distribution and hierarchy in the proof of Theorem 4.3 are more contrived.

Full proofs of both Theorems 4.2 and 4.3 are in Appendix B. Both proofs follow the same structure at a very high level. We prove a structural result on minimal, hierarchical $k$-anonymous mechanisms for a specially constructed hierarchy $H$ (Claims B.1 and B.3). This structural result states that if $\mathbf{X}$ satisfies certain conditions then $\mathbf{Y}$ must take a restricted form which allows the downcoding adversary to construct $\mathbf{Z}$. To prove the theorem, we construct a data distribution $U$ such that random $\mathbf{X}\sim U^{N}$ will satisfy the conditions of the structural result with probability close to 1.

4 Example: Clustered Gaussians

The proof of Theorem 4.2 shows that distributions satisfying certain properties are vulnerable to downcoding attacks. Example B.2 describes a family of clustered Gaussian distributions that satisfy those properties. Here we give an instantiation of this family of distributions for $k=10$ and describe the corresponding hierarchy and downcoding adversary.

The adversary $\mathsf{A}$ is described in Algorithm 1. It takes as input $\mathbf{Y}$, $k$, and a description of $H$. It looks at each group of generalized records $\widehat{\mathbf{Y}}_{t}$ of the output. If the number of records in $\widehat{\mathbf{Y}}_{t}$ is not $k$, then the whole group of records is copied to the output $\mathbf{Z}$ unchanged (i.e., no downcoding on these records). If $\widehat{\mathbf{Y}}_{t}$ has exactly $k$ records, then by $k$-anonymity these records are all identical copies of some $\mathbf{y}^{t}$. Some of $\mathbf{y}^{t}$’s entries may be aggregated to $[A_{t},A_{t+1})$. If it’s many more or many less than half the entries, then the whole group of records is copied to the output $\mathbf{Z}$ unchanged (i.e., no downcoding on these records). Otherwise, the $k$ records in $\widehat{\mathbf{Y}}_{t}$ all get downcoded as described in the algorithm.

It follows from Example B.2 that for $k=10$, the distribution described above, and $\mathbf{Y}$ produced by any minimal hierarchical $k$-anonymizer, $\mathsf{A}$ will downcode a constant fraction of the records in $\mathbf{Y}$ (with constant probability).

Predicate singling-out attacks on syntactic privacy techniques

Our downcoding attacks yield powerful predicate singling-out (PSO) attacks against minimal hierarchical $k$-anonymous mechanisms. PSO attacks were recently proposed as a way to demonstrate that a privacy mechanism fails to legally anonymize under Europe’s General Data Protection Regulation . Our new attacks undermine the use $k$-anonymity and other QI-deidentification techniques for GDPR compliance, challenging prevailing European guidance on anonymization .

In this section, we recall the prior work on PSO attacks and define a generalization called compound PSO attacks. We prove that minimal hierarchical $k$-anonymizers enable compound PSO attacks.

Predicate singling-out attacks were recently introduced by Cohen and Nissim in the context of data anonymization under Europe’s General Data Protection Regulation (GDPR) . They were proposed as a mathematical test to show that a privacy mechanism fails to legally anonymize data under GDPR . A mechanism $M$ legally anonymizes under GDPR if it suffices to transform regulated personal data into unregulated anonymous data. That is, if $M(\mathbf{X})$ is free from GDPR regulation regardless of what $\mathbf{X}$ is. If a mechanism enables PSO attacks, then it does not legally anonymize under GDPR .

Informally, $M$ enables PSO attacks if given $M(\mathbf{X})$, an adversary is able to learn an extremely specific description $\psi$ of a single record in $\mathbf{X}$. Because $\psi$ is so specific, it not only distinguishes the victim in the dataset $\mathbf{X}$, but likely also in the greater population. Hence PSO attacks can be a stepping stone to more blatant attacks.

To perform a PSO attack, $\mathsf{A}$ outputs a single negligible-weight predicate $\psi$ that isolates a record $\mathbf{x}\in\mathbf{X}$ with non-negligible probability.

$M$ enables predicate singling-out (PSO) attacks if there exists $U$, $\mathsf{A}$, and $\beta(n)$ non-negligible such that

2 Compound predicate singling-out attacks

PSO attacks can be unsatisfying. For example, the attack from outputs $L$ predicates and at best about $L/e$ manage to actually isolate a record in the dataset $\mathbf{X}$. Moreover, which predicates isolate and which don’t is impossible for the attacker to know without additional information. So even though there exists many isolated records with high probability, the attacker doesn’t know which ones or how many. In contrast, consider an attacker that outputs $L=N$ predicates, each of which isolates a distinct record in $\mathbf{X}$. It is obvious the new attacker is stronger, but in a way that isn’t captured by the definition of predicate singling-out.

We define a generalization of PSO attacks called compound PSO attacks. Whereas PSO attacks only require that a record is isolated with non-negligible probability, compound PSO attacks require many records to be isolated often.

To perform a compound PSO attack, $\mathsf{A}$ outputs multiple negligible-weight predicates $\Psi=\{\psi_{1},\dots,\psi_{L}\}$ each of which isolates a distinct record $\mathbf{x}\in\mathbf{X}$ with probability at least $1-\alpha$. The strength of the attack is measured by $L$ and $\alpha$, with $L\to n$ and $\alpha\to 0$ reflecting stronger attacks. Vanilla PSO attacks correspond to the setting $L=1$ and $\alpha=1-\beta$.

$M$ enables $(\alpha,L)$-compound predicate singling-out attacks if there exists $U$, $\mathsf{A}$ such that

in the probability experiment $\mathbf{X}\sim U^{N}$, $\Psi\leftarrow\mathsf{A}(M(\mathbf{X}))$.

In the language of compound attacks, the prior work gives an $(1-O(e^{-L}),L)$-compound-PSO attack against bounded $k$-anonymizers for $L<cN$ and some $c>0$.

For all constants $k\geq 2$, $\alpha>0$, $D=\omega(\log N)$, and $T=\lceil N^{2}/\alpha\rceil$, there exists a distribution $U$ over $\mathcal{U}^{D}=[0,T]^{D}$, a generalization hierarchy $H$, such that all minimal hierarchical $k$-anonymizers $M$ enable $(\alpha,N)$-compound-PSO attacks. The attack also works for $k=N$ and $D=\omega(N\log N)$.

These theorems mirror Theorems 4.2 and 4.3, inheriting their advantages and disadvantages. Proofs for both attacks follow the same general structure, using the corresponding downcoding attacks in non-black-box ways (Appendix B). The key observation is that some of the downcoded records in the downcoding attacks immediately give the predicates needed to predicate single-out.

Algorithm 2 illustrates the compound-PSO adversary for the example of clustered Gaussians described in Section 4.4. Compare to the downcoding adversary in Algorithm 1. Instead of outputting a complete dataset $\mathbf{Z}$ (as in the downcoding attack), we simply output descriptions of certain records within $\mathbf{Z}$. Namely, $\mathsf{matches}(\mathbf{z}):\mathbf{x}\mapsto\{0,1\}$ is the predicate that outputs $1$ if and only if $\mathbf{x}$ is consistent with $\mathbf{z}$ (i.e., $\mathbf{x}\subseteq\mathbf{z})$.

Reidentifying EdX students using LinkedIn

597,692 individuals registered for 17 online courses offered by Harvard and MIT through the EdX platform . We show that thousands of these students are potentially vulnerable to reidentification. The EdX dataset represents an egregious failure of $k$-anonymity in practice and in a case where the dataset was “properly deidentified” by “statistical experts” in accordance with regulations, undermining one of the main arguments used to justify the continued use of QI-deidentification .

EdX collected data about students’ demographics, engagement with course content, and final course grade. EdX sought to make the data public to enable outside research but considered it protected by the Family Educational Rights and Privacy Act (FERPA), a data privacy law restricting the disclosure of certain educational records . “To meet these privacy specifications, the HarvardX and MITx research team (guided by the general counsel, for the two institutions) opted for a $k$-anonymization framework” . A value of $k=5$ “was chosen to allow legal sharing of the data” in accordance with FERPA. Ultimately, EdX published the 5-anonymized dataset with 476,532 students’ records.

We show that thousands of these students are potentially vulnerable to reidentification. As a proof of concept, we reidentified 3 students out of 135 students for whom we searched for matching users on LinkedIn. Each of the reidentified users failed to complete at least one course in which they were enrolled, a private fact disclosed by the reidentification attack.

The limiting factor of this attack was not the privacy protection offered by $k$-anonymity itself, but the fact that many records in the raw dataset were missing demographic variables altogether. In order to boost the confidence of our attack, we restricted our attention to unambiguously unique records. To demonstrate the possibility of attribute disclosure, we further restricted our attention to students that had enrolled in, but failed to complete, a course on EdX.

$\mathbf{X}_{\mathsf{ed}}$ has 476,532 rows, one per student.The dataset as published was such that each row represented a student-course pair, with a separate row for each course in which a student enrolled. Records corresponding to the same student shared a common UID. $\mathbf{X}_{\mathsf{ed}}$ as described above is the result of aggregating the information by UID. See the appendix for additional background on the EdX dataset. Each row contains the student’s basic demographic information, and information about the student’s activities and outcomes in each of 16 of the 17 EdX courses.

The demographics included self-reported level of education, gender, and year of birth, along with a country inferred from the student’s IP address. Many students chose not to report level of education, gender, and year of birth at all, so these columns are missing many entries. For each course, $\mathbf{X}_{\mathsf{ed}}$ indicates whether the student enrolled in the course, their final grade, and whether they earned a certificate of completion. $\mathbf{X}_{\mathsf{ed}}$ also includes information about students’ activities in courses including how many forum posts they made.

$\mathbf{X}_{\mathsf{ed}}$ was $5$-anonymized with respect to 17 overlapping quasi-identifiers separately: $Q_{1},\dots,Q_{16}$, and $Q_{*}$ defined next. Recall that each quasi-identifier is a subset of attributes, not a single attribute (Def. 3.1).

$Q_{i}=$ {gender, year of birth, country, enrolled in course $i$, number of forum posts in course $i$}

$Q_{*}=$ {enrolled in course 1, …, enrolled in course 16}.

Anonymization was done hierarchically. First, locations were globally coarsened to countries or continents. Then other attributes or whole records were suppressed as needed.

2 Uniques in the EdX dataset

Table 1 summarizes the results of all analyses described in this section. Let $Q_{\mathsf{all}}=Q_{*}\cup Q_{1}\cup\dots\cup Q_{16}$. $\mathbf{X}_{\mathsf{ed}}$ is very far from 5-anonymous with respect to $Q_{\mathsf{all}}$. We find that 7.1% of students (33,925 students) in $\mathbf{X}_{\mathsf{ed}}$ are unique with respect to $Q_{\mathsf{all}}$ and 15.3% have effective anonymity less than 5.

Despite EdX’s goals, $\mathbf{X}_{\mathsf{ed}}$ was not even $5$-anonymous with respect to $Q_{*}$: 245 students were unique and 753 had effective anonymity less than 5! We suspect this blunder is due to $k$-anonymity’s fragility with respect to post-processing. The raw data was first 5-anonymized with respect to $Q_{*}$ and afterwards with respect to $Q_{1},\dots,Q_{16}$. Some rows in the dataset were deleted in the latter stage, ruining $5$-anonymity for $Q_{*}$.

We emphasize that the creators of the EdX dataset never intended or claimed to provide 5-anonymity with respect to $Q_{\mathsf{all}}$. But they admit that each of the attributes in $Q_{\mathsf{all}}$ is potentially public. In our view, the union of quasi-identifiers should also be considered a quasi-identifier and any exception should be justified. No justification is given.

A naive interpretation of the 7.1% unique students is that an attacker who knows $Q_{\mathsf{all}}$ would be able to definitively learn the grades of 7.1% of the students. But there is a major source of ambiguity: missing information. Gender, year of birth, and level of education were voluntarily self-reported by students. Many students chose not to provide this information: 14.9% of students records are missing at least one of these attributes. It is missing in the raw data, not just the published data. Thus, a female Italian born in 1986 might appear in the dataset with any or all three attributes missing.

This makes the 7.1% result difficult to interpret. From an inferential standpoint, the relevant question is not how many students have unique quasi-identifiers, but how many are unambiguously unique. We compute the ambiguous effective anonymity $\mathsf{EA_{\mathsf{amb}}}$ (defined in App. A.1) of each record by treating any missing attribute values as the set of all possible values for that attribute. This number may be much lower than 7.1%. We stress that this ambiguity comes from missing data, not from $k$-anonymity.

We find that 1.9% of students (9,125 students) are unambiguously unique with respect to $Q_{\mathsf{all}}$ and 4.7% have ambiguous effective anonymity less than 5. Over 9,000 students are unambiguously identifiable in the dataset to anybody who knows all the quasi-identifiers, without knowing whether the students chose to self-report their gender, year of birth, or level of education. This allows an attacker to draw meaningful inferences about them.

2.2 Limiting the attacker’s knowledge

Students in the EdX dataset are vulnerable to reidentification by adversaries who have much less auxiliary information than $Q_{\mathsf{all}}$. We consider the (ambiguous) effective anonymity for three attackers who could plausibly reidentify students in the EdX dataset: a prospective employer, a casual acquaintance, and an EdX classmate. The results are summarized in Table 1.

In Section 6.3, we carry out the prospective employer attack using LinkedIn. This demonstrates that some students in the EdX dataset can be reidentified by anybody.

Consider a prospective employer who is interested in discovering whether a job applicant failed an EdX course. An applicant is likely to list EdX certificates on their resume. The employer very likely knows $Q_{\mathsf{resume}}=$ {gender, year of birth, location, level of education, certificates earned in courses 1–16}. $Q_{\mathsf{resume}}$ only includes those certificates actually earned, but omits courses in which a student enrolled but did not earn a certificate.

5,546 students in $\mathbf{X}_{\mathsf{ed}}$ have effective anonymity 1 with respect to $Q_{\mathsf{resume}}$, and 10,942 have effective anonymity less than 5. These numbers may seem small, but they constitute 34.2% and 67.4% of the 16,224 students in the dataset that earned any certificates whatsoever. Moreover, 732 students are unambiguously unique—333 of whom failed at least one course, and 38 of whom failed three or more courses. Thus, 2.1% of students (333 students) who earned certificates of completion failed at least one course and have unambiguous effective anonymity 1 with respect to $Q_{\mathsf{resume}}$.

Casual acquaintances might, in the course of normal conversation, discuss their experiences on EdX. They would likely discuss which courses they took, and would naturally know each other’s ages, genders, and locations. So acquaintances know $Q_{\mathsf{acq}}=${gender, year of birth, location, enrollment in courses 1–16} $\subseteq Q_{\mathsf{all}}$. 6.7% of students in $\mathbf{X}_{\mathsf{ed}}$ have effective anonymity 1 with respect to $Q_{\mathsf{acq}}$, and 14.6% have effective anonymity less than 5.

Moreover, acquaintances typically know each other’s level of education too, even though this is not included in $Q_{\mathsf{all}}$. If we augment the acquaintance’s knowledge with level of education $Q_{\mathsf{acq+}}=Q_{\mathsf{acq}}\cup\{\mbox{education}\}$, then things become even worse. 8.7% students in $\mathbf{X}_{\mathsf{ed}}$ have effective anonymity 1 with respect to $Q_{\mathsf{acq+}}$, and 20.6% have effective anonymity less than 5.

Each EdX course had an online forum for student discussions. Because these posts were public to all students enrolled in a given course, the number of forum posts made by any user was deemed publicly available information. But ignoring composition, EdX did not consider the combination of forum post counts made by a user across courses.

Consider an attacker who knows $Q_{\mathsf{posts}}=${number of forum posts in courses 1–16} $\subseteq Q_{\mathsf{all}}$. 120 students in $\mathbf{X}_{\mathsf{ed}}$ are unambiguously unique with respect to $Q_{\mathsf{posts}}$, and 216 have ambiguous effective anonymity less than 5. These numbers may seem minute, but they constitute 1.7% and 3.0% of the 7251 students in the dataset that made any forum posts whatsoever. Effective anonymity and ambiguous effective anonymity are always the same for this attacker because $Q_{\mathsf{posts}}$ excludes the demographic columns that are missing many entries.

Who knows $Q_{\mathsf{posts}}$? 20 students in the dataset itself enrolled in all 16 courses and could have compiled forum post counts across all courses for all other EdX students. To any one of these 20 students the 120 students with distinguishing forum posts are uniquely identifiable. Such an attacker can then learn these 120 students ages, genders, level of educations, locations, and their grades in the class.

In fact, each of the 120 vulnerable students can be unambiguously uniquely distinguished by 23–70 classmates; 60 students by 40–49 classmates each. This enables more classmates to act as attackers than just the 20 who took all courses. This is because distinguishing a student using forum posts doesn’t require being enrolled in all 16 courses. For each of the 120 vulnerable students, we find which subsets of their forum posts suffices to distinguish them. This analysis amounts to checking whether these students remain unambiguously unique if some subset of their forum post counts are redacted.

3 Reidentifying EdX students on LinkedIn

On LinkedIn.com, people show off the courses they completed. They may be unwittingly revealing which courses they gave up on. 2.1% of students who earned certificates of completion (333 students) failed at least one course and have unambiguous effective anonymity 1 with respect to $Q_{\mathsf{resume}}$.

We reidentified three of these 333 students, with a rough confidence estimate of 90–95%.

We performed the attack as follows. We restricted our attention to 135 students in $\mathbf{X}_{\mathsf{ed}}$ who were unambiguously unique using only certificates earned plus at most one of gender, year of birth, and location, and who also had no missing demographic attributes. We manually searched for LinkedIn users that listed matching course certificates on their profile by searching for course numbers (e.g., "HarvardX/CS50x/2012"). We attempted to access the profiles for the resulting users, whether they were in our extended network or by searching on Google. If successful, we checked whether the LinkedIn user lists exactly the same certificates as the EdX student, and whether the demographic information on LinkedIn was consistent with the EdX student. If everything matched, we consider this a reidentification.

3.2 Results

We reidentified 3 of the attempted 135 EdX students, each of whom registered for but failed to complete an EdX course. Two were unambiguously unique using only certificates of completion. In each case, the EdX student’s gender matched the LinkedIn user’s presenting gender based on profile picture and name. In each case, the LinkedIn user’s highest completed degree in 2013 matched the EdX student’s listed level of education.

3.3 Confidence

We cannot know for sure whether our purported reidentifications on LinkedIn are correct because were instructed by our IRB not to contact the reidentified EdX students.

In this section, we estimate that our reidentifications are correct with 90–95% confidence. Moreover, an error is most likely a result of our imperfect ability to corroborate location and year of birth on LinkedIn, not a result of the protection afforded by $k$-anonymity. Our analysis is necessarily very rough. A precise error analysis is impossible. We omit details to avoid imparting any other impression.

We consider two main sources of uncertainty. First is the limited information available on LinkedIn profiles, especially age and location. We inferred a range of possible ages by extrapolating from educational milestones. We inferred a set of possible locations based on listed activities around 2013. Both methods are imperfect. The locations in EdX were inferred from IP address and are likely imperfect. LinkedIn users or EdX students can report their attributes inconsistently. Note that they cannot lie about earning EdX certificates: this data comes from EdX itself and the LinkedIn certificates are digitally signed and cryptographically verifiable.An example certificate is available here: https://verify.edx.org/cert/26121b8dec124bc094d324f51b70e506. Instructions for verifying the signature are here: https://verify.edx.org/cert/26121b8dec124bc094d324f51b70e506/verify.html We estimate the probability of error on at least one attribute inferred from LinkedIn is on the order of 5–10%.

The second source of error is suppressed student records. Of the 597,692 students enrolled in EdX courses over the relevant period, only 476,532 appear in the published dataset. 121,160 students (20.3%) are completely suppressed. We matched students $\mathbf{x}_{\mathsf{edx}}$ in EdX with users on LinkedIn $\mathbf{x}_{\mathsf{li}}$ using $Q_{\mathsf{resume}}=$ {gender, year of birth, location, level of education, certificates earned in courses 1–16} as well as we could. An error will occur if a suppressed student $\mathbf{x}^{\prime}_{\mathsf{edx}}$ is the true match for the LinkedIn user. For this to happen, $\mathbf{x}^{\prime}_{\mathsf{edx}}$ and $\mathbf{x}_{\mathsf{edx}}$ must agree on $Q_{\mathsf{all}}$. If $\mathbf{x}_{\mathsf{edx}}$ is unique in the complete dataset, no error occurs.

We do a back of the envelope calculation of the chance of error from record suppression under two simplifying assumptions. First, that random student records are suppressed.There are more sophisticated techniques for estimating the probability of error under this assumption . But in EdX omitted records are “outliers and highly active users because these users are more likely to be unique and therefore easy to re-identify” . As such, using the more sophisticated techniques would not give more meaning to our very coarse estimates. Second, that the number of certificates of completion that a user earns is statistically independent of their other attributes (assuming they registered for enough courses). We compute 99.5%-confidence upper bounds for two parameters: the probability $p$ that a random EdX student matches our reidentified EdX student; the probability $q$ that a random EdX student earns the same number of certificates as our reidentified EdX student. 121,160$\cdot pq$ is a very coarse estimate of the probability that a supressed student record causes an error. For the three students we reidentified, this comes out to 0.1–1%.

A much less likely source of error is suppression of individual courses from a student’s record. Such an error will occur if some courses for the purported match $\mathbf{x}_{\mathsf{edx}}$ were suppressed, and there is some other EdX student $\mathbf{x}^{\prime}_{\mathsf{edx}}$ that is the true match for the LinkedIn user $\mathbf{x}_{\mathsf{li}}$. This requires course suppression in $\mathbf{x}_{\mathsf{edx}}$ and also $\mathbf{x}^{\prime}_{\mathsf{edx}}$ (because $\mathbf{x}_{\mathsf{edx}}$ was unambiguously unique on $Q_{\mathsf{resume}}$ in the published EdX data). All in all, we consider course suppression to be a much less likely source of error than student suppression or imperfect attribute inference on LinkedIn.

4 EdX was “properly” deidentified

El Emam, et al., criticize prior reidentification studies as using data that were “improperly deidentified” because they did not “follow[] existing standards” . They thus conclude that there is no convincing evidence of real-world failure of QI-deidentification techniques in a regulated context.

In contrast, the EdX dataset incontrovertibly followed existing standards. FERPA is the relevant regulation. It requires the published information to not enable identification of any student with reasonable certainty. The EdX dataset was specifically created to comply with FERPA, following Department of Education guidance and overseen by general council for Harvard and MIT .

Moreover, the EdX dataset arguably followed the HIPAA Expert Determination–the standard used by El Emam, et al. The Expert Determination standard requires three things:https://www.hhs.gov/hipaa/for-professionals/privacy/special-topics/de-identification/index.html (1) Deidentification be performed by “a person with appropriate knowledge …and experience”. (2) The person determines that the risk of reidentification is “very small”. (3) The person “documents the methods and results of the analysis that justify such determination.” The creation of the EdX data was overseen by Harvard professors in computer science and statistics with specific expertise in privacy and inference. They find a “low probability that the dataset will be re-identified” and their methods and analysis are well-documented . The main deviation from the Expert Determination standard is the difference between “very small” and “low” reidentification risk.

Conclusions

In short, we show that $k$-anonymity – and QI-deidentification generally – fails on its own terms. Our attacks rebut three primary arguments that QI-deidentification’s practioners make to justify its continued use. First, we reidentify individuals in EdX dataset; it was “properly de-identified” by a “statistical experts” and in accordance with procedures outlined in regulation, meeting the high bar set by El Emam, et al. . Second, our downcoding attacks demonstrate that even if every attribute is treated as quasi-identifying, $k$-anonymity and its refinements may provide no protection. Ours are the first attacks in either of these two settings. Third, our attacks also undermine the claim that QI-deidentification meets regulatory standards for deidentification. The compound PSO and reidentification attacks challenge $k$-anonymity’s status under GDPR and FERPA respectively.

Moreover, our attacks show that QI-deidentification violates three properties of a worthwhile privacy notion, even in practice. Namely, avoiding distributional assumptions, robustness against post-processing, and smooth degradation under composition. We expand on these next.

Downcoding attacks prove that whatever privacy is provided by QI-deidentification crucially depends on unstated assumptions on the data distribution. One possible pushback is that our downcoding attacks use specially constructed distributions and hierarchies, not naturally occurring ones. But even a contrived counterexample proves that there is some unnoticed distributional assumption that is critical for security. Moreover, the distributions and hierarchies in Theorem 4.2 are not so unnatural when considering that data are made, not found (to quote danah boyd). Say an analyst wants to $k$-anonymize a high dimensional dataset. One natural approach is to find a low-dimensional projection with clusters of about $k$ rows each, and then construct the generalization hierarchy over this representation. The result could easily satisfy conditions that enable our downcoding attack or a direct extension.

Robustness against post-processing requires that further processing of the output, without access to the data, should not diminish privacy. Downcoding proves that QI-deidentification is not robust to post-processing. Our attacks recover specific secret information about a large fraction of a dataset’s entries with probability close to 1. Also, the EdX dataset also proves that $k$-anonymity is not robust to post-processing for purely syntactic reasons. The result of removing rows from a $k$-anonymous dataset may not satisfy $k$-anonymity as defined. We see this in the EdX data: it is not in fact $5$-anonymous with respect to quasi-identifier $Q_{*}$ (courses), despite claims otherwise. This fragility to post-processing is not so much a privacy failure as a syntactic weakness of the definition itself.

Smooth degradation under composition requires that a combination of two or more private applications mechanisms should also be private, albeit with worse parameters. The EdX dataset proves that QI-deidentification is not robust to composition, even when done by experts in accordance with strict privacy regulations. Ganta et al. present theoretical composition attacks, showing that if the same dataset is $k$-anonymized with different quasi-identifiers the original data can be recovered . With the EdX dataset the possibility became reality. To the best of our knowledge, this is the first example of such a failure in practice.

The most important open question raised by this work is to characterize the power of downcoding attacks. What properties of a data distribution and generalization hierarchy enable downcoding? Is vulnerability to downcoding testable? In what settings is downcoding provably impossible? Can one demonstrated downcoding in the wild? We leave these questions for future work.

After reidentifying one EdX student, we reported the vulnerability to Harvard and MIT who promptly replaced the dataset with a heavily redacted one. Our IRB determined that this research was not human subjects research and did not need IRB approval. However, we were instructed by the IRB not to contact the reidentified LinkedIn users. The code used in our analysis of the EdX dataset is at https://github.com/a785236/EdX-LinkedIn-Reidentification, but we do not distribute the dataset itself to protect the students’ privacy.

References

Appendix A Additional background on the EdX dataset

We summarize the EdX dataset—the chosen quasi-identifiers, the implementation of $k$-anonymization, and the resulting published dataset $\mathbf{X}_{\mathsf{ed,raw}}$ based on documentation included with the dataset and in two articles describing the creation of the dataset itself .

The raw dataset consisted of 841,687 rows for 597,692 students. Each row corresponded to the registration of a single student in a single course and included the information described above. IP addresses were used to infer a student’s location even when a student chose not to self-report their location. EdX considered username and IP address to be identifying. Each username was replaced by a unique 7-digit identification number (UID). A username appearing in multiple rows was replaced by the same UID in each. IP addresses were redacted.

After aggregating the rows by UID, $\mathbf{X}_{\mathsf{ed}}$ can be seen as $k$-anonymized with respect to 17 overlapping quasi-identifiers: $Q_{*}$ as before and $Q_{1},\dots,Q_{16}$, where $Q_{i}=$ {gender, year of birth, country, enrolled in course $i$, number of forum posts in course $i$}.

The final published result $\mathbf{X}_{\mathsf{ed,raw}}$ includes 641,138 course registrations by 476,532 students across 16 courses.

As published, the EdX dataset had 641,138 rows, each representing to a single course registration for one of 476,532 distinct students. But the object of our privacy concerns is a student, not a student-course pair. We aggregated the rows corresponding to the same UID. We call the result $\mathbf{X}_{\mathsf{ed}}$.

The creators of the EdX dataset failed to identify which attributes are publicly available—the very thing that experts are supposed to be good at. Specifically, level of education and certificates of course completion are not included in any of the quasi-identifiers despite both being readily available on LinkedIn. The exclusion of certificates is particularly indefensible: at the same time as the EdX dataset was being created, EdX and LinkedIn collaborated to allows LinkedIn users to include cryptographically unforgeable certificates of completion on their profiles.

We consider a relaxation of the notion of effective anonymity which we call ambiguous effective anonymity. Let $I_{\mathsf{amb}}(\mathbf{Y},\mathbf{y},Q)\triangleq\{n:\mathbf{y}_{n}(Q)\cap\mathbf{y}(Q)\neq\emptyset\}$. The ambiguous effective anonymity of $\mathbf{y}$ in $\mathbf{Y}$ with respect to $Q$ is $\mathsf{EA_{\mathsf{amb}}}(\mathbf{Y},\mathbf{y},Q)=|I_{\mathsf{amb}}(\mathbf{Y},\mathbf{y},Q)|$. Ambiguous effective anonymity helps us reason about what an attacker can infer from the dataset.

We say $\mathbf{y}\in\mathbf{Y}$ is unique with respect to $Q$ if $\mathsf{EA}(\mathbf{Y},\mathbf{y},Q)=1$, and unambiguously unique if $\mathsf{EA_{\mathsf{amb}}}(\mathbf{Y},\mathbf{y},Q)=1$.

$\mathsf{EA_{\mathsf{amb}}}$ is never less than $\mathsf{EA}$, and is very often greater in EdX. The presence of unambiguously unique records in a supposedly-anonymized dataset indicates a clear failure of syntactic anonymity. Considering ambiguous effective anonymity makes critiquing $k$-anonymity much harder. We are giving $k$-anonymity the benefit of all the additional ambiguity that comes from missing data rather than from the anonymizer itself.

Appendix B Deferred Proofs

Let $H$ be a hierarchy with $T$ nodes at the second level: $H_{1},\dots,H_{t}$ (as in Figure 4). Let $\mathbf{X}\in\mathcal{U}^{D}$ be a dataset, $M$ be a minimal hierarchical $k$-anonymizer, and $\mathbf{Y}\leftarrow M(\mathbf{X},H)$. For $t\in[1,T]$, let $\mathbf{X}_{t}=\mathbf{X}\cap H_{t}^{D}$ and let $\mathbf{Y}_{t}$ be the records in $\mathbf{Y}$ corresponding to the records in $\mathbf{X}_{t}$. If $\mathbf{X}=\cup_{t}\mathbf{X}_{t}$, then for all but at most one $t\in\{t:|\mathbf{X}_{t}|=k\}$, $\mathbf{y}\subseteq H_{t}^{D}$ for all $\mathbf{y}\in\mathbf{Y}_{t}$.

Note that as defined, the generalized records in $\mathbf{Y}_{t}$ are not necessarily contained in $H^{D}_{t}$. The claim says that if $\mathbf{X}$ consists of data in the $T$ clusters $\mathbf{X}_{1},\dots,\mathbf{X}_{T}$, then the records in $\mathbf{Y}_{t}$ will be contained in $H^{D}_{t}$ for almost all clusters of size exactly $k$.

First, we show that for any $\mathbf{y}=(y_{1},\allowbreak\dots,\allowbreak y_{D})$, a single coordinate of $\mathbf{y}$ is generalized to $H=\mathcal{U}$ if and only if every coordinate in $\mathbf{y}$ is generalized to $H$. Namely, if $y_{d}=H$ for some $d$, then $\mathbf{y}=H^{D}$.

Suppose for contradiction that there exists $\mathbf{y}=(y_{1},\dots,y_{D})$ corresponding to $\mathbf{x}\in\mathbf{X}$ such that $y_{1}=H$ but $y_{2}\subseteq H_{t}$ for some $t$. By the assumption on $\mathbf{X}$, there exists $t^{\prime}$ such that $\mathbf{y}\in\mathbf{Y}_{t^{\prime}}$. Because $y_{2}\subseteq H_{t}$, $t^{\prime}=t$ and hence $\mathbf{y}\in\mathbf{Y}_{t}$. By $k$-anonymity, there are at least $k-1$ additional records $\mathbf{y}^{\prime}\in\mathbf{Y}$ such that $\mathbf{y}^{\prime}=\mathbf{y}$. Repeating the previous argument, $\mathbf{y}^{\prime}\in\mathbf{Y}_{t}$.

Let $\mathbf{y}^{*}=(H_{t},y_{2},\dots,y_{D})\subsetneq\mathbf{y}$. Construct $\mathbf{Y}^{*}$ by replacing all copies of $\mathbf{y}$ in $\mathbf{Y}$ with $\mathbf{y}^{*}$. It is immediate that $\mathbf{Y}^{*}$ is $k$-anonymous and respects the hierarchy. By the assumption that $y_{1}=H$, $\mathbf{Y}^{*}$ strictly refines $\mathbf{Y}$. Additionally, $\mathbf{Y}^{*}$ generalizes $\mathbf{X}$, because all altered rows were in $\mathbf{Y}_{t}$. This contradicts the minimality of the $k$-anonymizer $M$. Therefore we have proved that if $y_{d}=H$ for some $d$, then $y_{d}=H$ for all $d$.

Next, we show that for all but at most one $t\in\{t:|\mathbf{X}_{t}|=k\}$, there exists $\mathbf{y}\in\mathbf{Y}_{t}$ such that $\mathbf{y}\subseteq H^{D}_{t}$. By the preceding argument, it suffices to show that $\mathbf{y}\neq H^{D}$. Suppose for contradiction there exists $t\neq t^{\prime}$ such that for all $\mathbf{y}\in\mathbf{Y}_{t}\cup\mathbf{Y}_{t^{\prime}}$, $\mathbf{y}=H^{D}$. Construct $\mathbf{Y}^{\prime}$ by replacing each $\mathbf{y}\in\mathbf{Y}_{t^{\prime}}$ with $H_{t^{\prime}}^{D}\subsetneq\mathbf{y}$. It is easy to see that $\mathbf{Y}^{\prime}$ respects the hierarchy, satisfies $k$-anonymity, generalizes $\mathbf{X}$, and strictly refines $\mathbf{Y}$. This contradicts the minimality of the $k$-anonymizer $M$.

To complete the proof, let $t\in\{t:|\mathbf{X}_{t}|=k\}$ and suppose there exists $\mathbf{y}\in\mathbf{Y}_{t}$ such that $\mathbf{y}\subseteq H^{D}_{t}$. By $k$-anonymity, there must be at least $k-1$ distinct $\mathbf{y}^{\prime}=\mathbf{y}\subseteq H^{D}_{t}$. By assumption on $\mathbf{X}$, each such $\mathbf{y}^{\prime}$ must be an element of $\mathbf{Y}_{t}$. Because $|\mathbf{Y}_{t}|=|\mathbf{X}_{t}|=k$, every element of $\mathbf{Y}_{t}$ is equal to $\mathbf{y}\subseteq H^{D}_{t}$. ∎

The adversary $\mathsf{A}$ takes as input $\mathbf{Y}$ and produces the output $\mathbf{Z}$ as follows. For $t\in[T]$, let $\widehat{\mathbf{Y}}_{t}=\mathbf{Y}\cap H_{t}^{D}$. If $|\widehat{\mathbf{Y}}_{t}|\neq k$, copy every $\mathbf{y}\in\widehat{\mathbf{Y}}_{t}$ into the output $\mathbf{Z}$. Otherwise $|\widehat{\mathbf{Y}}_{t}|=k$. By $k$-anonymity $\widehat{\mathbf{Y}}_{t}$ consists of $k$ copies of a single generalized record $\mathbf{y}^{t}$. Let ${\mathsf{big}}_{t}=\{d:y^{t}_{d}=H_{t}\}$ be the large coordinates of $\mathbf{y}^{t}$, and let $B_{t}=|{\mathsf{big}}_{t}|$ be the number of large coordinates. If $\left|B_{t}-D/2\right|>D/8$, then $\mathsf{A}$ writes $k$ copies of $\mathbf{y}^{t}$ to the output $\mathbf{Z}$. Otherwise $\mathsf{A}$ writes $k-1$ copies of $H_{t,{\mathsf{sml}}}^{D}$ and one copy of $\mathbf{z}^{t}=(z^{t}_{1},\ldots,z^{t}_{D})$ to the output, where

It is immediate from the construction that $\mathbf{Z}\preceq\mathbf{Y}$. Moreover, it is easy to arrange the records in $\mathbf{Z}$ so that $\mathbf{z}_{n}\subseteq\mathbf{y}_{n}$ for all $n\in[N]$. By construction, $\mathbf{z}_{n}\subsetneq\mathbf{y}_{n}$ implies that $\mathbf{z}_{n}$ differs from $\mathbf{z}_{n}$ differs from $\mathbf{y}_{n}$ on at at least $B_{t}\geq 3D/8$ coordinates.

To prove the theorem, it remains to show that w.h.p. $\mathbf{X}\preceq\mathbf{Z}$ and $\mathbf{Z}\prec_{\Omega(N)}\mathbf{Y}$. Let $\mathbf{X}_{\mathsf{big}}=\mathbf{X}\setminus\left(\bigcup_{t}\ H^{D}_{t,{\mathsf{sml}}}\right)$ consist of all the records $\mathbf{x}$ that have at least one large coordinate (i.e., $x_{d}\in H_{t,{\mathsf{big}}}$ for some $t,d$).

For all $t\in[T]$, let $\mathbf{X}_{t}=\mathbf{X}\cap H_{t}^{D}$ and let $\widehat{\mathbf{X}}_{t}\subseteq\mathbf{X}_{t}$ be the records $\mathbf{x}\in\mathbf{X}$ that correspond to the records in $\widehat{\mathbf{Y}}_{t}$. (Whereas $\mathbf{X}_{t}$ consists of all records that are in cluster $t$, $\widehat{\mathbf{X}}_{t}$ consists of only those records that correspond to generalized records $\mathbf{y}\in\widehat{\mathbf{Y}}_{t}$ that can be easily inferred to be in cluster $t$ based on $\mathbf{Y}$.) A cluster $t$ is $\mathbf{X}$-good if $|\mathbf{X}_{t}|=k$ and $|\mathbf{X}_{t}\cap\mathbf{X}_{\mathsf{big}}|=1$. A cluster $t$ is $\widehat{\mathbf{Y}}$-good if $\widehat{\mathbf{Y}}_{t}=k$ and $|B_{t}-D/2|\leq D/8$.

$\Omega(N)$ clusters $t$ are $\mathbf{X}$-good.

All but at most one $\mathbf{X}$-good clusters are $\widehat{\mathbf{Y}}$-good.

For all $\widehat{\mathbf{Y}}$-good clusters $t$, $\widehat{\mathbf{X}}_{t}\cap\mathbf{X}_{\mathsf{big}}=\{\mathbf{x}^{t}\}$ and $\mathbf{x}^{t}\subseteq\mathbf{z}^{t}$.

Note that if $t$ is both $\mathbf{X}$-good and $\widehat{\mathbf{Y}}$-good, then $\widehat{\mathbf{X}}_{t}=\mathbf{X}_{t}$. But there may be $t$ that are $\widehat{\mathbf{Y}}$-good but not $\mathbf{X}$-good.

We lower bound \Pr[t\mbox{\mathbf{X}-good}] by a constant and then apply McDiarmid’s Inequality.

Combining the above, \Pr[t\mbox{\mathbf{X}-good}]=\Omega(1). Quantitatively, for $k\leq 15$, \Pr[t\mbox{\mathbf{X}-good}]\gtrsim 1/(e^{2}\sqrt{k})>1/30.

Thus there are $\Omega(N)$ $\mathbf{X}$-good values of $t$ with high probability.

Cluster $t$ is $\widehat{\mathbf{Y}}$-good if $\widehat{\mathbf{Y}}_{t}=k$ and $|B_{t}-D/2|\leq D/8$. First we show that for all but one $\mathbf{X}$-good $t$, $|\widehat{\mathbf{Y}}_{t}|=k$. Let $\mathbf{Y}_{t}\supseteq\widehat{\mathbf{Y}}_{t}$ be the records in $\mathbf{Y}$ corresponding to the records in $\mathbf{X}_{t}$. (Whereas $\mathbf{Y}_{t}$ consists of all records that correspond to $\mathbf{X}_{t}$, $\widehat{\mathbf{Y}}_{t}$ consists of only those records whose membership in $\mathbf{Y}_{t}$ can be easily inferred from $\mathbf{Y}$.) Observe that $|\mathbf{X}_{t}|=|\mathbf{Y}_{t}|\geq|\widehat{\mathbf{Y}}_{t}|$. By construction, for all $\mathbf{x}\in\mathbf{X}$ there exists $t$ such that $\mathbf{x}\in\mathbf{X}_{t}$ with high probability (i.e., $\mathbf{X}=\cup_{t}\mathbf{X}_{t}$). By Claim B.1, for all but at most one $\mathbf{X}$-good $t$ and every $\mathbf{y}\in\mathbf{Y}_{t}$, $\mathbf{y}\subseteq H_{t}^{D}$. Thus $|\widehat{\mathbf{Y}}_{t}|=\mathbf{Y}_{t}=k$.

Finally we show that for all $\mathbf{X}$-good $t$ as guaranteed by Claim B.1, $B_{t}\in(3D/8,5D/8)$ with high probability. $\widehat{\mathbf{Y}}_{t}$ consists of $k$ copies of the same generalized record $(y_{1},\dots,y_{d})$. Since $M$ is hierarchical, $y_{d}\in\{H_{t},H_{t,{\mathsf{sml}}},H_{t,{\mathsf{big}}}\}$. By the $\mathbf{X}$-goodness of $t$, $\mathbf{X}_{t}$ contains $1$ large-noise record $\mathbf{x}_{\mathsf{big}}$ and $k-1$ small-noise records $\mathbf{x}^{\prime}$ By correctness of the $k$-anonymizer $M$, $x_{{\mathsf{big}},d}\in H_{t,{\mathsf{big}}}$ $\implies y_{d}\supseteq H_{t,{\mathsf{big}}}$. Minimality implies the converse: $y_{d}\supseteq H_{t,{\mathsf{big}}}$ $\implies x_{{\mathsf{big}},d}\in H_{t,{\mathsf{big}}}$. With high probability, $x^{\prime}_{d}\in H_{t,{\mathsf{sml}}}$ $\implies y_{d}\supseteq H_{t,{\mathsf{sml}}}$. Putting it all together,

By construction, ${\mathsf{big}}_{t}=\{d:\exists\mathbf{x}\in\widehat{\mathbf{X}}_{t}\cap\mathbf{X}_{\mathsf{big}}\text{ st }x_{d}\in H_{t,{\mathsf{big}}}\}$. Because $|{\mathsf{big}}_{t}|>0$, $|\widehat{\mathbf{X}}_{t}\cap\mathbf{X}_{\mathsf{big}}|>1$. A simple Chernoff-then-union-bound argument shows that the probability that there exist distinct records $\mathbf{x},\mathbf{x}^{\prime}\in\mathbf{X}_{\mathsf{big}}$ such that $|{\mathsf{big}}_{t}|=|\{d:x_{d}\in H_{t,{\mathsf{big}}}\lor x^{\prime}_{d}\in H_{t,{\mathsf{big}}}\}|<5D/8$ is negligible. Hence $\widehat{\mathbf{X}}_{t}\cap\mathbf{X}_{\mathsf{big}}$ is a singleton $\{\mathbf{x}^{t}\}$ with high probability. $\mathbf{x}^{t}\subseteq\mathbf{z}^{t}$ follows immediately from the construction. ∎

The hierarchy $H$ consists of intervals $H_{t}=[c_{t}-\Delta,c_{t}+\Delta]$ centered at the cluster centers $c_{t}$, for some $\Delta$. The hierarchy further subdivides each $H_{t}$ into a smaller interval $H_{t,{\mathsf{sml}}}=[c_{t}-\tau,c_{t}+\tau)$, for some $\tau<\Delta$, and the complement $H_{t,{\mathsf{big}}}=H_{t}\setminus H_{t,{\mathsf{sml}}}$.

B.2 Proof of Theorem 4.3

A $k$-anonymizer $M:\mathbf{X}\mapsto\mathbf{Y}$ groups records $\mathbf{x}\in\mathbf{X}$ into equivalence classes such that if $\mathbf{x}$ and $\mathbf{x}^{\prime}$ are in the same class, then $\mathbf{Y}(\mathbf{x})=\mathbf{Y}(\mathbf{x}^{\prime})$. In general, $M$ may have a lot of freedom to group the $\mathbf{x}$’s the equivalence classes and also to choose the $\mathbf{y}$’s that generalize each equivalence class.

Claim B.3 states that if $M$ is minimal and generalizes using hierarchy like in Figure 5, then it has much less freedom. Namely, $\mathbf{Y}$ is fully determined by the choice of equivalence classes (with probability at least $1-\alpha$ over the dataset $\mathbf{X}$). $M$ can group the $\mathbf{x}$’s together, but then has no control over the resulting $\mathbf{y}$’s.

Claim B.3 and its proof are meant to be read in the context of the proof of Theorem 4.3 and freely uses its notation.

Let $T=\lceil N^{2}/\alpha\rceil$ and $\mathcal{U}=[0,T]$ be the attribute domain. Records $\mathbf{x}\in\mathcal{U}^{D}$ are sampled according to the distribution $U$ as follows. First sample $t(\mathbf{x})\leftarrow[T]$ uniformly at random. Then sample each coordinate $x_{d}$ of $\mathbf{x}$ i.i.d. with $\Pr[x_{d}=t(\mathbf{x})]=1/2k$ and $x_{d}=0$ otherwise. In other words, $\mathbf{x}\in\{0,t(\mathbf{x})\}^{D}$ consists of $D$ independent samples from $t(\mathbf{x})\cdot\mathsf{Bern}(1/2k)$.

All the $t(\mathbf{x})$ will be distinct except with probability at most ${N\choose 2}\frac{1}{T}<\alpha/2$. If all $t(\mathbf{x})$ are distinct, we say $\mathbf{X}$ is collision-free. The remainder of the proof shows that the adversary succeeds with high probability conditioned on $\mathbf{X}$ collision-free.

Figure 5 defines the generalization hierarchy. It consists of intervals $[0,t]$ and singletons $\{t\}$ for $t\in[T]$.

Claim B.3 states that the output $\mathbf{Y}\leftarrow M(\mathbf{X},H)$ of a minimal hierarchical $k$-anonymizer must take a restricted form. For $\mathbf{y}\in\mathbf{Y}$, let $\mathbf{X}_{\mathbf{y}}=\{\mathbf{x}\in\mathbf{X}:\mathbf{Y}(\mathbf{x})=\mathbf{y}\}$ be the records in $\mathbf{X}$ that correspond to a copy of $\mathbf{y}\in\mathbf{Y}$. The claim states that

Moreover, if $\mathbf{X}$ is collision-free then for all $\mathbf{y}\in\mathbf{Y}$ and $d\in[D]$: