Database reconstruction attacks
In 2018, three researchers from the US Census Bureau published a paper entitled Understanding Database Reconstruction Attacks on Public Data." [1] The article showed that private data on many individuals could be reverse engineered from public data.
As I wrote about a few days ago, census blocks are at the bottom of the US Census Bureau's hierarchy of geographical entities. On average a census block may contain about 40 people, but a block may contain only one person.
In hindsight it seems fairly obvious that data reported at the census block level is vulnerable to re-identification, and yet this doesn't seem to have been noticed before around 2000. There were some privacy measures in place before then, but it wasn't clear that these methods were insufficient to protect privacy.
You can think of each fact about each person as a variable and each reported statistic as an equation. When the number of equations is comparable to the number of variables, it's possible that the system of equations has a unique solution. (We know a priori that there exists at least one solution, assuming the reported statistics were correctly computed.)
It's not quite as simple as that, though that is roughly the idea in [1]. The data collected in the census is binary or integer data, which makes database reconstruction easier. Ages, for example, are integers, and typically integers less than 100.
One of the techniques the Census Bureau previously used in an attempt to protect individual privacy was a sort of small cell rule, a rule to not report statistics based on three or fewer individuals. This may or may not help. In the example given in [1], there are 7 people in a hypothetical census block, of whom 4 are adults and an unreported number are minors. Determining the number of minors is left as an exercise for the reader.
The set of equations is more complicated than a set of linear equations. The inference problem is a matter of logic programming or constraint satisfaction. Missing data is not always as trivial to reconstruct as in the preceding paragraph, but missing data can still convey partial information. The very fact that the data is missing tells you something.
The discrete nature of the data makes the solution process both harder and easier. It makes things harder in the sense of requiring a more complicated solution algorithm, but it makes things easier in the sense of increasing the likelihood that the equations have a unique solution.
This is why the Census Bureau embraced differential privacy for the 2020 census. They had no choice but to do something substantially different than they had done in the past once it became apparent that their previous approach failed rather badly at protecting confidentiality.
Related posts[1] Simson Garfinkel, John M. Abowd, Christain Martindale. Understanding Database Reconstruction Attacks on Public Data. ACM Quque, October 2018. The article was also published in Communications of the ACM in March 2019.
The post Database reconstruction attacks first appeared on John D. Cook.