This is a difficult problem, regardless of how you look at it. But some solutions might be good enough. Here, you have the advantage that you are returning aggregate statistics, and not individual records.
Enforcing a minimum size for result sets is a good idea, and should provide privacy guarantees similar to k-anonymity. If a query result would be too small, you could provide a minimum count (e.g. returning users: 25 even if the true value is users: 4).
But if larger counts are accurate and if all possible categories are known, this may still enable recovery of the true value via multiple queries. E.g. if we know that there are 1000 records in total, that there are 599 Android users, 399 iOS users, and that the only other possible OS is Windows Mobile, we can infer that exactly 2 users fall into that category. Similarly, multiple requests with overlapping date ranges could make it possible to make inferences about small result sets.
Differential Privacy makes such inferences unreliable. This works by adding noise to the result, where the appropriate level of noise depends on the specific query. If all queries merely count the number of matching records, this is fairly feasible (in differential-privacy lingo, the L1-sensitivity of such queries is 1). On average, the noisy results will still be accurate (and the bit of noise won't matter on larger counts), but adversaries cannot make accurate inferences about small samples.
In practice, this can still be difficult to implement appropriately.
For example, an attacker might try to recover the true result of a query by issuing it multiple times.
If each response samples a different noisy result, the true value will be around the average of the responses.
E.g. Reddit fuzzes vote counts, but rolls a different number each time a vote count is requested. Request the count three times, and you'll have a good idea of the true vote count.
You can defend against this by using the same RNG seed for each query-response, for example by hashing the query + true result.
But then this makes it possible for an attacker to detect when the true value changes: as long as they get the same result they can be somewhat sure that the true value has changed. If the rate of changes is lower than the rate of queries, this could enable an attacker to estimate the true rate of changes, which may allow inferences about the true result of the query (especially since you allow queries for specific time ranges).
There is still the issue that an attacker can issue multiple distinct queries with overlapping result sets in order to make inferences. E.g. if an attacker issues a query for A="Monday", B="Tuesday", and C="Monday to Tuesday", they obtain three random variables, but they know that their expected value is related via E[A] + E[B] = E[C]. They can use this to defeat some of the added noise. This means that your Differential Privacy Budget (the standard deviation of the noise distribution) must be large enough to obfuscate the true result of all queries combined, not just the result of a single query.
Depending on the sensitivity of the data, I would combine a number of strategies to reduce possible inferences by an attacker:
- do not provide a complete list of facets/categories/values to users
- reject requests that go over some rate limit
- reject requests that are very specific (e.g. too many facets, too small date ranges)
- count the true number of matching records for the query
- increment that count to some minimum value
- derive an RNG seed, for example by hashing the count, current date, and normalized query. Use a cryptographically secure hash function, e.g. SHA-2
- add random noise to the count. The standard deviation of the noise distribution should match your privacy requirements. Larger SD → more privacy, but less accurate results. Use a cryptographically secure RNG, or just use the hash as a source of random bits if it is long enough.
- if the query could cover recent/live data: cache the noisy result for a reasonable time in order to mask changes to the true value
If you have very stringent privacy requirements, do not run live queries. Instead, determine all possible queries up front, derive a combined privacy budget from their combined query complexity, then evaluate them together and store the results. Alternatively, determine some privacy budget up front and run live queries, but stop serving responses once the privacy budget has been exhausted.
