Towards Formalizing the GDPR's Notion of Singling Out

1 Introduction

• The authors address uncertainty about whether formal privacy guarantees match legal expectations, against a backdrop of privacy attacks and techniques that may fall short of legal standards.They propose translating a legal concept into a mathematical model to examine its requirements and implications.Source: §1 · p. 3

1.1 Singling out in the GDPR

• The paper interprets GDPR singling out broadly: any predicate that distinguishes one person in a dataset may count, not only a collection of attributes.The GDPR identifies singling out as a means reasonably likely to identify a person; the paper notes that context affects whether a trait distinguishes someone.Source: §1.1 · pp. 4–5

1.2.1 Defining security against predicate singling out

• Predicate singling out occurs when an adversary uses a released mechanism output to produce a predicate isolating a row with success above a weight-dependent statistical baseline.The predicate acts on the original dataset’s rows, not the mechanism’s output; the baseline addresses isolation that could occur by chance.Source: §1.2.1 · pp. 5–6

1.2.2 Analyzing security against predicate singling out

• PSO security withstands post-processing but not composition: ω(log n) exact counts can enable isolation, and two individually PSO-secure mechanisms can together reveal a row.The paper also connects differential privacy to PSO security through statistical generalization, while showing that k-anonymity does not prevent attacks.Source: §1.2.2 · pp. 6–7

1.3 Implication for the GDPR

• The authors present PSO security as a necessary condition for anonymization under the GDPR, but not a sufficient privacy guarantee or the only possible formalization.The model assumes i.i.d. data and does not cover other identification means such as linkage and inference; the authors also acknowledge plausible alternative formalizations.Source: §1 · p. 3, §1.3 · pp. 7–8

2 Preliminaries

• Datasets contain n independently sampled rows, and predicate weight is its expected value under the data distribution.The text also defines predicate counts on a dataset and indicator notation.Source: §2 · pp. 8–9
• The analysis uses n as its asymptotic parameter, with negligible functions describing quantities that decay faster than any inverse polynomial.The data domain dimension may depend on n.Source: §2 · p. 9, §2.1 · p. 9

2.1 Preliminaries from randomness extraction

• Average conditional min-entropy is bounded below by ordinary min-entropy minus the logarithm of the conditioning variable’s support size.The stated fact also bounds average conditional min-entropy above by ordinary min-entropy.Source: §2.1 · p. 9
• A 2-universal hash family lets the paper use hash outputs that are close to uniform with high probability when the input has sufficient min-entropy.The generalized Leftover Hash Lemma gives a statistical-distance guarantee, and its corollary states that the hash output is α-close to uniform for all but an α fraction of hashes.Source: §2.1 · p. 9

3 Security against predicate singling out (PSO security)

• A predicate singles out a row when it matches exactly one dataset row, and security compares an informed adversary’s success with a trivial-adversary baseline.The adversary observes the mechanism’s output and produces a predicate; the dataset rows are sampled i.i.d. from D.Source: §3 · p. 10
• A trivial adversary can isolate a row with probability about 37% by choosing a predicate whose weight is near 1/n.This motivates measuring excess success over baseline risk rather than requiring isolation probability to be negligible.Source: §3 · p. 10

3.1 Security against predicate singling out

• The definition compares success within admissible predicate classes, including predicates with low or high distributional weight.The classes are defined by weight thresholds around 1/n.Source: §3.1 · p. 11, §3 · p. 11
• The paper also defines full predicate singling out, where an adversary outputs distinct negligible-weight predicates isolating every row.The predicates are pairwise disjoint on the dataset with high probability.Source: §3.1 · pp. 11–12
• A many-to-one transformation can still enable full predicate singling out: revealing the last n/2 bits lets predicates isolate rows with probability 1 − negl(n).Under the stated uniform-data example, each predicate has weight 2^-n/2.Source: §3.1 · p. 12

3.2 Bounding the baseline

• For every distribution, the low- and high-weight baselines are bounded above by B(n,wlow) and B(n,whigh), respectively.With sufficient min-entropy, the corresponding lower bounds are within 2^-c, and hash-based predicates support an efficient uniform trivial adversary.Source: §3.2 · p. 13
• The B(n,w) bound can differ from the exact baseline by as much as 1/e, but is nearly tight for distributions with moderate min-entropy.The corresponding lower bound is achievable by an efficient uniform trivial adversary oblivious to the distribution.Source: §3.2 · p. 13

3.3 Reflections on modelling assumption

• The guarantee addresses i.i.d. data only, and satisfying the definition is not sufficient to establish GDPR anonymization or protection in all relevant circumstances.The paper identifies other reasonably likely identification means and cautions that real-life data may not be modeled as i.i.d.Source: §3.3 · p. 14

4 Properties of PSO security

• PSO security withstands post-processing but not composition, unlike differential privacy’s stated closure under composition.The paper presents the lack of composition closure as a significant weakness of PSO security.Source: §4 · p. 14
• A collection of ω(log n) exact counts, each individually PSO secure, can enable isolation with probability arbitrarily close to one using a negligible-weight predicate.Source: §4 · p. 14
• Even two individually PSO-secure mechanisms can compose into a mechanism that permits recovery of a dataset row.This second construction is described as less natural and borrows ideas from.Source: §4 · p. 14
• The authors argue that non-closure under composition makes PSO security useful for disqualifying technology, but insufficient alone for approving it.They also state that a privacy concept lacking composition closure should not be accepted as sufficient from a legal or policy perspective.Source: §4 · p. 15

4.1 Post Processing

• If M is PSO secure, applying a function F to its output preserves the same PSO security parameters.The proof simulates an adversary on F(M(x)) using M(x), producing an identical predicate-output distribution.Source: §4.1 · p. 15
• The definition and proof extend to interactive mechanisms.Source: §4.1 · p. 15

4.2 Example PSO-secure mechanisms

• The two mechanisms develop intuition for PSO security and ground the next section's examples of self-composition failures.Source: §4.2 · p. 15

4.2.1 Counting Mechanism

• Adversary success is bounded by |Y| times the statistical baseline, where Y is the mechanism's output codomain.Source: §4.2.1 · p. 15
• For every predicate q, the Counting Mechanism is PSO secure, although exact counts are not differentially private.Source: §4.2.1 · pp. 15–16

4.2.2 Predicate Mechanism

• The Predicate Mechanism outputs q evaluated on each row and is PSO secure.Source: §4.2.2 · p. 16

4.3.1 Failure to compose ω(log n) times

• A fixed set of ω(log n) counts can raise singling-out success close to e^-1, and this probability can be amplified to 1-negl(n).A single count remains PSO secure, and security extends to O(log n) counts, even when chosen adaptively.Source: §4.3.1 · p. 17
• For distributions with moderate min-entropy, hashing extends the count attack by randomizing the attacked set of counts.The data is hashed to a smaller domain where its image is almost uniformly distributed.Source: §4.3.1 · pp. 17–18
• For uniform {0,1}^m data, ω(log n) bit predicates can fully predicate-single-out with a predicate of negligible weight 2^-m.The attack uses predicates for individual bits and combines their released values to identify a row.Source: §4.3.1 · pp. 17–18

4.3.2 Failure to compose twice

• Mext and Menc are individually PSO secure, yet their composition enables high-probability row recovery for uniform data when ω(log n) ≤ m ≤ n/8.Mext extracts a key from part of the dataset; Menc uses the key to encrypt the last row, and the combined outputs allow its recovery.Source: §4.3.2 · pp. 18, 20

4.3.3 Singling out and failure to compose

• Counting-query attacks may generalize to other singling-out notions; the two-mechanism example is more contrived, and composable alternatives likely must forbid Menc.The authors note that counting queries underlie many statistical analyses and machine-learning algorithms.Source: §4.3.3 · p. 20

5.1 Preliminaries from differential privacy

• Differential privacy compares mechanism outputs on datasets differing in one element, with probabilities taken over the mechanism’s randomness.The section also states basic and parallel composition bounds for differentially private mechanisms.Source: §5.1 · pp. 20–21

5.2 Differential privacy implies PSO security

• The proof connects PSO security and differential privacy to statistical generalization, using a generalization lemma on algorithms operating over sub-datasets.The proof of Theorem 5.4 consists of two claims, each using one part of the lemma.Source: §5.1 · p. 21, §5.2 · p. 21
• When ε = O(1), δ = negl(n), wlow ≤ 1/n, and whigh(n) = ω(log n/n), differential privacy implies PSO security with parameters ε′, δ′, wlow, and whigh.The theorem states the implication for an (ε, δ)-differentially private mechanism.Source: §5.2 · p. 21
• The proof selects an index using the exponential mechanism and invokes basic and parallel composition to bound the constructed algorithm’s privacy.Its utility is based on the predicate’s value on the selected sub-dataset.Source: §5.1 · p. 21, §5.2 · pp. 22–23

6 Does k-anonymity provide PSO security?

• A k-anonymized dataset can typically reveal enough information for an attacker to predicate single out with constant probability, challenging the Article 29 Working Party’s conclusion.The authors state that their results also hold for ℓ-diversity and t-closeness, which the Working Party likewise concluded prevent singling out.Source: §6 · p. 24, §6.1 · p. 24

6.1 Preliminaries

• A k-anonymous release requires each row to match at least k rows after generalization and suppression; a k-anonymizer must produce such a release derived from its input.The section generalizes this property to predicate k-anonymity, where every output predicate matches at least k rows.Source: §6.1 · p. 24
• Predicate k-anonymity relaxes k-anonymity’s syntactic requirements, and the general attack assumes that the number of matching rows is computable from the anonymizer’s output.The theorem’s scope uses a kmax-bounded anonymizer, which outputs a predicate matching at most kmax rows.Source: §6.1 · p. 24

6.2 Illustrative examples

• The bit-suppression construction leaves many group bits suppressed while the surviving bits make the group predicate low-weight under the uniform-data setting.The example assumes i.i.d. records from a uniform distribution over {0, 1}^n.Source: §6.2 · p. 25
• In the bit-suppression example, an attacker combines the group-agreement predicate with a low-weight predicate to isolate a row with probability approximately 0.37.The conjunction’s weight is negligible because it is bounded by the group-agreement predicate’s weight.Source: §6.2 · p. 25
• For interval buckets, an endpoint reveals a row, letting an attacker predicate single out with probability 1 using a predicate of weight 2^-n.The example sorts rows and releases intervals covering groups of k rows.Source: §6.2 · p. 25

6.3 k-Anonymity enables predicate singling out

• The general theorem extends the attack to kmax-bounded predicate anonymizers under a min-entropy condition, with success approximately η/e.The authors decompose success into η, the probability of a low-weight predicate, and the approximately 1/e probability of isolating within a group; they expect information-preserving anonymizers to yield low-weight predicates.Source: §6.3 · pp. 25–26

• For any set of target weights W, the proof equates the base success over predicates with weights in W to the supremum of base success at a single weight in W.It introduces trivial adversaries that either output predicates of a realizable weight or cannot output that weight.Source: A Omitted proofs from Section 3 · p. 29
• The hashing proof first projects hashed outputs to [0, 1] and chooses a nearby multiple of 2^-m below the target weight.The stated argument treats weights w ≥ 2^-(m−1); the proof for smaller weights is analogous.Source: A Omitted proofs from Section 3 · p. 30
• A 2-universal hash family yields predicates whose D-weight lies within 3 · 2^-m of a target weight with probability at least 1 − 2^-m when the min-entropy is at least 5m.The proof sets α = 2^-m and Δ = 2α.Source: A Omitted proofs from Section 3 · p. 30

• A 2-universal hash transforms the data before applying the mechanism, while the adversary maps its output predicate back through the hash.The proof uses hashes for which h(D) is α-close to uniform to relate predicate weights under D and under the uniform distribution.Source: B Omitted proofs from Section 4 · pp. 30–31
• For min-entropy λ = m + 2 log(1/α^2) and m = ω(log n), the corollary supplies O(m) predicates and a negligible wlow; its proof amplifies success to 1 − negl(n).The proof applies the hashing lemma and expresses the resulting mechanism using predicates qh_i(x) = q_i(h(x)).Source: B Omitted proofs from Section 4 · p. 31
• The composition example is meaningful only if each mechanism M#qh_i is individually PSO secure; the remark says each is an instance of the counting mechanism and thus secure.Source: B Omitted proofs from Section 4 · p. 31

• The proof of Lemma 6.3 proves the second inequality first and reuses the idea from (9) in (10).Source: C Omitted proofs from Section 6 · p. 31
• The corollary gives outputs close to uniform when each variable has sufficient conditional min-entropy given the others.Source: C Omitted proofs from Section 6 · p. 32
• The construction of q uses the Leftover Hash Lemma and resembles the predicate construction in Lemma 3.4.Source: C Omitted proofs from Section 6 · p. 32
• The proof establishes that xφ satisfies the corollary’s average min-entropy condition, then applies the corollary.Source: C Omitted proofs from Section 6 · p. 33