Small cells, big leaks: reconstruction attacks on institutional returns, and what differential privacy costs

The draft Digital Personal Data Protection Bill published last month will, if it passes in anything like its current form, make colleges accountable for personal data in a way they have not been before. Most of the discussion has been about consent forms and breach notification. Very little has been about the tables colleges publish every year, which are personal data in disguise.

A college’s statutory return, its ranking submission and its accreditation report between them describe the same students along most of the dimensions that identify them: programme, year, social category, gender, disability. Some of those tables also carry examination results. The usual protection, where there is one, is to suppress counts below five. This paper asks whether that works, using the method that persuaded the United States Census Bureau that it does not: reconstruct the underlying records from the published tables, and see what can be learned about individuals.

The release

The simulated college has 9,000 students across 24 programmes of uneven size, three years of study, five social categories, three gender categories (the third very small, as it is in reality), and a 1.8% rate of declared disability. Each student either passed every paper or failed at least one, at a college-wide rate near 20% that varies by programme. The college publishes eight tables:

The attack

Let x be the vector of 4,320 joint counts (programme × year × category × gender × disability × result), and let A be the 0/1 matrix that sums joint cells into published cells, so that the release is b = Ax. The attacker solves

using only the counts that were actually published. Nothing more sophisticated is needed: this is the linear-algebra core of the reconstruction attacks Dinur and Nissim analysed in 2003 and that Garfinkel, Abowd and Martindale ran against the 2010 US census. The attacker then plays a classmate who knows a target’s programme, category and gender, and reads off the reconstructed share of failures in that cell. If it is at least 0.95, they conclude the target failed.

We measure harm only for students in cells of four or fewer at that level, the students suppression is meant to protect. They are about 1% of the college, around 87 students. The headline measure is the precision of confident failure claims: of the students the attacker would announce as having failed, what share actually did. A useless attacker has precision equal to the base rate of failure in this group, about 17%.

Result 1: suppression protects nobody

With the exact tables published, the attacker makes a confident failure claim about 5.1 of every 100 small-cell students and is right every time, exposing 31% of the small-cell students who failed. Replacing every count from one to four with ‘<5’, which withholds 22% of the cells of T4, changes none of those numbers. The reason is arithmetic. If T4 suppresses the failures in a cell but publishes the passes, and T8 publishes the enrolment of the same cell, the failures are the difference. Across all simulated releases the attacker recovered 93% of suppressed cells exactly.

Small-cell suppression is applied table by table. Reconstruction is applied to all the tables at once. A protection that does not account for the other tables a college publishes is not a protection.

Result 2: rounding helps, and costs

Unbiased random rounding to base five, used by several statistical agencies, replaces each count c with 5⌊c/5⌋ or 5⌊c/5⌋ + 5 with probabilities that preserve its expectation. It breaks exact differencing, and the precision of confident failure claims falls to 38%. That is a real improvement and still more than twice the base rate. It also costs accuracy: a reader computing failure rates by programme and category from the rounded tables is off by 3.8 points on average, and by more than 9 points in one cell in ten. Combining rounding with suppression gave similar protection (35%) and worse utility (5.6 points), because suppressed cells then simply drop out of readers’ sums.

Result 3: differential privacy protects, at a price set by the number of tables

A randomised release M is ε-differentially private if adding or removing any one student changes the probability of any output by at most a factor of e^ε:

For counts, the natural mechanism adds two-sided geometric noise, the discrete analogue of Laplace noise, which Ghosh, Roughgarden and Sundararajan showed is optimal for a broad class of users:

Each student appears once in every table, so each table has sensitivity one, and by sequential composition the total privacy loss is the sum of the per-table budgets. Publishing eight tables at a total ε therefore gives each table ε_t = ε/8. That division is the whole story of this section.

Applied to all eight tables at ε = 1, differential privacy does what suppression could not. The attacker still makes confident-looking claims, more of them in fact, because noise produces spurious extremes, but only 19% of those claims are true, which is what picking students at random would give. The cost is severe. The per-table noise at ε_t = 0.125 has a standard deviation of about eleven, so a reader’s programme-by-category failure rates are wrong by 15 points on average. At ε = 8 the tables become usable again (2.8 points) and the protection mostly goes (49% precision).

The way out is to publish less. We replaced the eight tables with three coarser ones that answer the questions statutory returns and rankings actually need: programme × year × result, programme × category × result, and year × category × gender for enrolment. With only three tables sharing the budget, each gets ε/3 instead of ε/8, and none of them isolates the small programme-category-gender cells. At ε = 1 the attacker’s precision is 22%, essentially the base rate, and the failure-rate error is 4.3 points. At ε = 2 the error is 2.3 points; the attacker makes a confident claim about fewer than two students in a hundred, right 41% of the time. At ε = 4 it can make none at all.

Result 4: the differencing attack, and what ε means in practice

A simpler attack needs no reconstruction. If a college publishes a results table in two consecutive months and one student withdraws in between, the difference between the two releases is that student’s row. With exact tables the attacker learns their result with certainty. Under the geometric mechanism we simulated the attacker’s best guess from the two noisy releases.

At a per-table budget of 0.5 the attacker is right 58% of the time, at 1.0 66%, at 2.0 81%. This is the most useful way we have found to explain ε to a registrar: it bounds how much better than a coin toss anyone can do at learning one fact about one student. It also makes the composition problem concrete. Twelve monthly releases at 0.5 each are a budget of 6, not 0.5.

Recommendations

• Stop treating suppression as protection. If tables broken down by result and by enrolment share dimensions, suppressed cells can be recovered by subtraction.
• Publish the fewest tables that answer the question. The number of tables, not the noise mechanism, was the largest single lever on utility in this study.
• Add calibrated noise to what remains, at a total ε of 1 to 2 per annual release, and publish the mechanism and the budget so that users can compute their own error bars.
• Budget across the year, not per table. Monthly or termly releases compose.
• Keep exact tables inside the institution for the people who need them to act, under access control. Privacy-preserving publication is for publication.

Method

Limitations

Our attacker is deliberately simple. An integer-programming attacker that uses the fact that counts are whole numbers, or one with side information beyond a classmate’s, would do better against every mechanism except differential privacy, whose guarantee does not depend on the attacker. We post-processed nothing: the noisy counts were published as drawn, including negative values, whereas a real release would round negatives to zero and enforce consistency between tables, which improves utility without weakening the guarantee. Ten replicates per mechanism leave the precision figures with a few points of Monte Carlo noise, especially where the attacker makes few claims. And ε has no agreed ‘safe’ value. We recommend a range and an explanation, not a number to hide behind.

Simulated data only. The population generator, the eight-table release, the attack and every mechanism are published so that a college can test its own release plan before it publishes anything. Write to team@eduplatter.com.

Related work

Reconstruction from aggregate statistics is Dinur and Nissim [1]; Garfinkel, Abowd and Martindale [2] describe the reconstruction of the 2010 US census tables that led the Census Bureau to adopt differential privacy for 2020, and Abowd and colleagues [3] document the resulting system. Differential privacy is Dwork, McSherry, Nissim and Smith [4]; the geometric mechanism and its optimality are Ghosh, Roughgarden and Sundararajan [5]; Dwork and Roth [6] cover composition. Traditional statistical disclosure control, including suppression, complementary suppression and rounding, is surveyed by Willenborg and de Waal [7] and Hundepool and colleagues [8]; complementary suppression exists precisely because of the differencing we exploit, and is rarely applied by institutions publishing their own tables. Sweeney [9] showed how few attributes are needed to single a person out. The Indian legal context is the draft bill [10]. Our earlier paper on small-n reporting [11] addresses the statistical rather than the privacy cost of small cells.

Artefacts

Everything below is published or available on request. A number nobody can reproduce is an advertisement, not a result. Real institutional records are never shareable under our processor obligations, so where that applies we release a simulated corpus that reproduces the qualitative finding.

References

1. Dinur, I., & Nissim, K. (2003). Revealing Information While Preserving Privacy. ACM PODS.
2. Garfinkel, S., Abowd, J. M., & Martindale, C. (2019). Understanding Database Reconstruction Attacks on Public Data. Communications of the ACM, 62(3), 46–53.
3. Abowd, J. M., Ashmead, R., Cumings-Menon, R., et al. (2022). The 2020 Census Disclosure Avoidance System TopDown Algorithm. Harvard Data Science Review, Special Issue 2.
4. Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006). Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography Conference.
5. Ghosh, A., Roughgarden, T., & Sundararajan, M. (2009). Universally Utility-Maximizing Privacy Mechanisms. ACM STOC.
6. Dwork, C., & Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4).
7. Willenborg, L., & de Waal, T. (2001). Elements of Statistical Disclosure Control. Springer.
8. Hundepool, A., Domingo-Ferrer, J., Franconi, L., et al. (2012). Statistical Disclosure Control. Wiley.
9. Sweeney, L. (2000). Simple Demographics Often Identify People Uniquely. Carnegie Mellon University, Data Privacy Working Paper 3.
10. Ministry of Electronics and Information Technology, Government of India (2022). Draft Digital Personal Data Protection Bill, 2022. Published for consultation, 18 November 2022.
11. Bhardwaj, M. (2022). Small sections, loud numbers: empirical Bayes shrinkage for course-level result analysis. EduPlatter Research, EPR-2022-01.