0
$\begingroup$

We possess a database containing entries, where each entry consists of a person's ID and the corresponding fractional number $w$ (e.g., 2.34, 3.4, 12.3 etc) falling within the range of 1.00 to 100.00. We are considering sending a "SELECT" query to this database, aiming to add some noise to the corresponding row (let's say by the Laplace mechanism) and return the noisy secret to the individual.

I am wondering whether such a query is permissible within the framework of differential privacy. If it is, could you please guide me on how to provide differential privacy for this query? How should $\epsilon$ be computed in the Laplace mechanism? It is essential that the output of the query does not disclose any extra information to potential adversaries.

The database is locally accessed.

$\endgroup$
1
  • $\begingroup$ I edited the question now and clarified it. There was a typo in the question. We aim to make $w$ noisy after sending the query "Select". $\endgroup$ Feb 7 at 8:18

1 Answer 1

1
+50
$\begingroup$

As described, I think that it is a bad idea. I assume that a query consists of supplying an ID and the goal is to hide the associated fraction from an adversary.

However, as an adversary if I submit multiple SELECT queries with the same ID the process would add (presumably) independent Laplace noise to the value. By taking the mean of the returned values, I have an unbiased estimator for the value and given sufficiently many queries I can estimate the value to high precision with high confidence.

$\endgroup$
2
  • $\begingroup$ Allow me to rephrase my question: Within the context of differential privacy, we submit queries to extract information from a dataset while maintaining privacy. These queries typically involve tasks like determining counts, maximum values, medians, and so on. I'm curious about the relevance of using a "SELECT" query in this context. If it is applicable, what adjustments should be made to the epsilon and Laplace function? Perhaps, should I consider the range between the minimum and maximum values in the database as the sensitivity? In my example, the difference between the min and max of $w$. $\endgroup$ Feb 7 at 10:25
  • 1
    $\begingroup$ What you describe is not a "valid" attack on differential privacy. Differential privacy is a parameterized notion. So if calling the mechanism once is $(\epsilon,\delta)$-DP, calling it $k$ times is something like $(\epsilon k, \delta\sqrt{k})$-DP (maybe -- I'd have to check). For large enough $k$ this will start to give vacuous guarantees (and you will be able to recover the underlying value), but the solution to that is to tune $\epsilon, \delta$, and restrict the number of queries that can occur. $\endgroup$
    – Mark Schultz-Wu
    Feb 10 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.