From Isolation to Identification

We present a mathematical framework for understanding when successfully distinguishing a person from all other persons in a data set—a phenomenon which we call isolation—may enable identification, a notion which is central to deciding whether a release based on the data set is subject to data protection regulation. We show that a baseline degree of isolation is unavoidable in the sense that isolation can typically happen with high probability even before a release was made about the data set and hence identification is not enabled. We then describe settings where isolation resulting from a data release may enable identification.

1. 1.

   Regulation (EU) 2016/679 (General Data Protection Regulation), Article 4.

2. 2.

   For variations and sources, see https://csrc.nist.gov/glossary/term/identification.

3. 3.

   For example: \((25\le \text{ Age } \le 28) \wedge (10,000 \le \text{ Salary } \le 50,000)\).

4. 4.

   General Data Protection Regulation, Recital 26. See also: Article 29 Working Party, Opinion 05/2014 on Anonymisation Techniques.

5. 5.

   See citations in [12] for more.

6. 6.

   “If an individual is not present in a dataset, and is independent of all other individuals in the dataset, then the release of that dataset does not violate that individual’s privacy.”.

7. 7.

   Our results are robust to a substantial relaxation of these assumptions, in particular, knowledge of the distribution P and the number of records n may be approximate. See Remark 3 and Appendix A.

8. 8.

   Query access to the release mechanism can also be used in other ways, see Remark 4 below.

9. 9.

   Access to alternative sources of information may also be used for boosting the information receiver’s confidence that a guess B isolates.

10. 10.

    The number of records n is included as part of the the receiver’s prior knowledge since n can often be inferred (exactly or approximately) from public information. Examples include (i) where a survey design specifying n was made public prior to the collection of information, and (ii) where n was made public in previous surveys (e.g., a census). For a reader who considers n as part of the release, this section should be understood as demonstrating that the release of n alone suffices for isolation.

11. 11.

    We exclude \(P(B) \ge \frac{1}{n}\), as the chance that B uniquely distinguishes an individual in a population of size \(N = n/r\) in extremely small. Namely, \((1-P(B))^{N-n} \le e^{-(1-r)/r}\). Taking \(r = 0.01\), say, the probability is about \(10^{-43}\).

12. 12.

    Accounting for the variance of P(B) yields only an insignificant improvement.

13. 13.

    E.g., for Governor Weld’s attributes used by Sweeney, they estimated \((1-P(B))^{N-1} \approx 0.58\).

14. 14.

    The proof of this fact is somewhat nuanced, as \(A_i\) can depend arbitrarily on the dataset \(\textbf{X}\).

15. 15.

    See https://www.slideserve.com/ordell/razi-mukatren-golan-salman, and https://archive.is/W20kx.

16. 16.

    Chebyshev’s inequality: \(\Pr \left[ |X-\textbf{E}[X]|\ge k\right] \le \frac{\textbf{Var}[X]}{k^2}\).

Work of K.N. was supported by NSF Grant No. CCF2217678 “DASS: Co-design of law and computer science for privacy in sociotechnical software systems” and a gift to Georgetown University. Work completed while K.N. visited Bocconi University, Milan.

Authors and Affiliations

1. LUISS University, Rome, Italy

   Giuseppe D’Acquisto

2. University of Chicago, Chicago, USA

   Aloni Cohen

3. LUMSA University, Rome, Italy

   Maurizio Naldi

4. Georgetown University, Washington, DC, USA

   Kobbi Nissim

Corresponding author

Correspondence to Aloni Cohen .

Editors and Affiliations

1. Rovira i Virgili University, Tarragona, Tarragona, Spain

   Josep Domingo-Ferrer

2. EURECOM, Biot, France

   Melek Önen

A Isolating with a Partial Knowledge of P

The analysis in Sects. 3.1 and 3.2 assumed that the information receiver has perfect knowledge of the underlying probability measure P (but not \(\textbf{X}\) sampled from P). We now discuss what the receiver may do when they do not know P in full.

Observation 1 and Theorem 2 teach that all the information receiver needs is a partition of the data space into sets of probability weight \(p^* =\frac{1}{\max (n,k)}\) and Remark 3 suggests that it suffices that the partition is close to the optimal weight for the information receiver to succeed in isolating. We now develop these ideas.

Let \(\mathcal{C}=\{C_i\}_{i=1}^\ell \) be a partition of D where \(\ell =\max (n,k)\). The information receiver may choose the partition \(\mathcal{C}\) heuristically in combination with their partial knowledge about P and the data domain D. For example, \(\mathcal{C}\) may partition D into high-dimensional rectangles, each described as the conjunction of one or more attribute ranges (e.g., all combinations of 5-year Age by Sex by City). Denote by \(p_i = P(C_i)\) the probability of an individual falling into \(C_i\). We show that if \(\underline{p} =(p_1,\ldots ,p_\ell )\) is close close enough to \(p^*=(\frac{1}{\ell },\ldots ,\frac{1}{\ell })\) then (even without knowing \(p_1,\ldots ,p_\ell \)) the information receiver succeeds in isolating.

As \(\mathcal{C}\) is a partition of the data domain D we have that \(\sum _{i=1}^\ell p_i=1\). Hence, if we pick a partition element at random, then, in expectation, its probability weight would be exactly \(p^*=\frac{1}{\ell }\):

where we use \(i\sim U_\ell \) to denote that the expectancy is over choosing an element of the partition \(i\in \{1,\dots ,\ell \}\) uniformly at random.

An important parameter of the partition is its standard deviation \(\sigma \):

If the standard deviation \(\sigma \) is small compared to \(\frac{1}{\ell }\), say \(\sigma \le \frac{c}{\ell }\) for \(c\ll 1\), then many of the elements of the partition have weight \(p_i \approx \frac{1}{\ell }\). More precisely, by Chebyshev’s inequality^{Footnote 16} we have:

Hence, if the information receiver samples guesses \(B_1,\ldots ,B_k\) from the partition \(\mathcal{C}\) without replacement, then in expectation at least \((1-4c^2)k\) of them would satisfy \(p(B_i) \in \left[ \frac{1}{2\ell },\frac{3}{2\ell }\right] \). Using Eq. 1 each of these guesses would result in isolation probability \(p^\textsf{iso}(B_i) \ge n\cdot \min (\frac{1}{2\ell } \cdot (1-\frac{1}{2\ell })^{n-1}, \frac{3}{2\ell } \cdot (1-\frac{3}{2\ell })^{n-1})\), and in expectation the number of isolating guesses would be at least

As an example, if \(c=\frac{1}{4}\) and \(k=n\) (hence \(\ell =k=n\)) we get that in expectation the number successful isolations is at least

I.e., in expectation almost a quarter of the guesses would consist successful isolations in spite of \(B_i\) not being chosen optimally.

Remark 6

Cohen and Nissim [5] used hashing to create a structure that is equivalent to a partition \(\mathcal{C}\) where \(p_i\) is very close to \(\frac{1}{\ell }\) (assuming P has sufficient min-entropy). The main qualitative difference between the hashing approach and the one described in this work is that hashing destroys the structure of the data domain and makes it harder for the information receiver to make effective use of isolation (e.g., as a step towards a linkage attack) whereas in the approach described herein the information receiver may choose partitions \(\mathcal{C}\) that are more suitable for their purposes.

Reprints and permissions

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics