Privacy violation even when queries with too few results are rejected

Question

I was reading a Computing security book¹ and saw a question regarding database security and privacy. I can't quite figure out the answer, so I thought I will ask here.

One approach to ensure privacy is the small result rejection, in which the system rejects (returns no result from) any query, the result of which is derived from a small number, for example, five, of records. Show how to obtain sensitive data by using only queries derived from six records.
_{Emphasis added}

¹ Excerpt copied from Security in computing By Charles P. Pfleeger, Shari Lawrence Pfleeger

If someone can help me with the answer, I would appreciate it.

Answer 1

I think what the book is saying is that if you can come up with such a specific query that there are only a few results, you can identify one particular target in the database.

For example, if a car dealer had a database of customers, and they "anonymized" the database to include only zip code, make, model, year, color, and salary, you could find your neighbor's salary if you know they bought a car from that dealer.

For example, you could run a query that selects the salary of all people who own a Green 2012 Chevy Volt in your zip code. If you got only a handful of records showing salaries of 20K 30K 40K and 300K and you know your neighbor is a successful attorney, you can guess that he has the 300K salary.

But if the system refused to show less than 100 results, it's harder to find the target such a result set.

Answer 2

Simple answer:

If any SQL query is allowed, you can also just artificially boost the record count by doing something like a UNION SELECT myKnownRecord at the end.

More general answer:

This issue is part of a larger family of strategies known as de-anonymization. One of the methods for avoiding unintended disclosure when other methods like k-anonymity enforcement, aggregation, rounding, and blurring or coarsening data don't work is suppressing results for small groups.

The biggest reason this method of restricting queries that result in small ranges doesn't work universally is that there are many other ways to get a complete picture of what's going on even if you don't look at results with less than 5 entries.

Suppose we have different criteria a,b, and c. The set A is the set of all records that match criteria a, the set A ∩ B is the set of all records that match criteria a and b (corresponding to an SQL JOIN or similar operation), etc.

Let's suppose that A ∩ B ∩ C is a small enough set to identify the records for our target (A ∩ B ∩ C has less than five elements). However, a minimum record criteria restricts us from directly viewing A ∩ B ∩ C. However, we could view A ∩ B, A ∩ C, and A ∩ B, then manually do a union of two of those to get a union the union we want A ∩ B ∩ C. This is however, assuming that the result you want is unique. If the records are not unique (say they're letter grades, income categories, yes/no answers, or an average based on the returned records), your can't do manual joins and I can't think of a universal way to get the exact values.

Unions (outer joins) could also be used on occasion to cricumvent this protection strategy. If you know your target is one of the few members of set A (perhaps because the results for A were hidden) we could look at aggregate results for A U C and any results near 0% or 100% would apply to our target in A.

Another way that this protection can be circumvented is by using other results to subtract our way to the result we want. If we know there are 120 out of 160 people have passing grades in set A, and 120 out of 157 have passing grades in A ∩ B, then even if A ∩ B' (A and not B) is hidden due to having too few results we already know that no one is passing in that group. This can usually be avoided if we avoid disclosure of how many entries are in each set, by rounding percentages aggressively, or grouping percentages into categories ("< 5%" or 3% instead of 3.1%).

To use an example (modified from the one provided by National Center for Education Statistics), say a school discloses that only one male American Indian/Alaskan Native student was enrolled in 2010. If the school discloses the graduation rate for this demographic, the individual's privacy has been compromised. The student's privacy could also be violated if complementary groups can be used to get a complete picture of the student, like the graduation rate being 0% for American Indian/Alaskan Natives or that all other demographics total up to 100% of graduates.

To provide context, L. Sweeney at Carnegie Mellon did a study that concluded: "It was found that combinations of few characteristics often combine in populations to uniquely or nearly uniquely identify some individuals. Clearly, data released containing such information about these individuals should not be considered anonymous. Yet, health and other person-specific data are publicly available in this form. Here are some surprising results using only three fields of information, even though typical data releases contain many more fields... even at the county level, {county, gender, date of birth} are likely to uniquely identify 18% of the U.S. population. In general, few characteristics are needed to uniquely identify a person." Similar personal identification and de-anonymization has been proved for a database of credit card transactions that had been naively anonymized. So even such simple queries as "all records with this gender, DOB, and geographic area" or "people who visited these four shops recently and spent about $50" are likely to seriously compromise privacy. Because these kinds of records like birth date and city can be combined to de-anonymize data, HIPAA, FERPA, and similar standards are written to strictly limit any kind of disclosure of this information.

In summary, as Anupam Datta of CMU said, "Naïve anonymization mechanisms do not work."

Answer 3

Selecting it through a SQL query only, you could check suggestion to this question. Both answers there are more or less equal (JOIN, when it's type is not specified, defaults to INNER JOIN in most RDBMS anyway).

This is however highly inefficient way of producing results with a minimum number of records. A lot easier, but also faster, would be to check for the required number of records before displaying results in your front-end generating code, and then deciding whether to list matched records, or display a non-disclosing error message.

This is easier because you don't have to change your existing SQL queries to accommodate for this new requirement, faster because there's no internal linking to aggregate result sets, and also more convenient since you'd be required to handle both cases in your front-end generating code anyway.

Basically, all you'd have to do is to display same (or similar) message when query returns less than n records, as before with empty result sets.

Language-agnostic example:

query.run;
if (query.recordcount >= 6) {
  display_results(query);
} else {
  error(minimum_not_reached);
}

that replaces:

query.run;
if (query.recordcount > 0) {
  display_results(query);
} else {
  error(no_results);
}

Returned error message of course shouldn't disclose the minimum required records, and is probably best to keep minimum_not_reached equal to no_results. Which just so happens is also a lot more convenient, if you're modifying an existing code, as it barely requires any change (query.recordcount > 0 to query.recordcount > 5).

Depending on RDBMS in use, this could be also achieved with stored procedures ;)