1
$\begingroup$

We have a set of query answers, i.e., $A = \{A_1, A_2, \dots, A_m\}$ and then we add noise to each of $A_i$ using a mechanism ($M$) providing differential privacy, i.e., $M(A_i) = O_i$. We denote the set of noisy query answers by $O = \{O_1, O_2, \dots, O_m\}$.

Let's say an adversary is given the sets $A$ and $O$ (in some shuffled order), and they need to correctly match up the pairs $(A_i, O_i)$. I want to compute the probability that an adversary can correctly match up each pair. Is there any mathematical formula to compute the probability based on our mechanism parameters?

For example, in the worst case where all $O_i$ are the same, then the adversary can match up each pair correctly with probability $1/m$. In the best case, where the noise is minimal, and the accuracy is very high, then the adversary can match up a pair correctly with a probability close to a hundred percent.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What does it mean for $O_i$ to be associated with $A_i$? $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Feb 25 at 3:56
  • $\begingroup$ I meant with which probability someone can relate $O_i$ to $A_i$ from which $O_i$ is resulted. $\endgroup$
    – Amirhossein Adavoudi
    Commented Feb 25 at 7:53
  • $\begingroup$ More precisely, I want to compute the probability that an adversary can relate $O_i$ to $A_i$, from which $O_i$ is derived. $\endgroup$
    – Amirhossein Adavoudi
    Commented Feb 25 at 7:59
  • 1
    $\begingroup$ This can still mean many things. For example, you could say that some adversary is given the entire sets of $\{A_1,\dots, A_m\}$, $\{O_1,\dots, O_m\}$ (in some shuffled order), and they need to correctly match up the pairs $\{A_i, O_i\}$. You could say that the adversary is given correct mappings $\{(A_1,O_1),\dots, (A_{m-1}, O_{m-1})\}$, and then given $O_m$, and must exactly recover $A_m$. You could say the adversary has to approximately recover $A_m$. There are a ton of other options $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Feb 25 at 7:59
  • 3
    $\begingroup$ I do not think your edits have clarified at all what you are asking. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Feb 25 at 7:59

1 Answer 1

Reset to default
2
+50
$\begingroup$

Your question is very generic and so only very generic principles can be described.

An simple example is when $A_i$ and $O_i$ are 1-dimensional values. In this case the best (maximum likelihood) strategy for an adversary is to sort both lists and then pair up the values according to their sorted positions. The noise model will provide a means to compute the order statistics of the $O$-values conditioned on the $A$-values and by seeing where $A_i$ occurs in the sorted list one can compute the probability that the corresponding $O$-value is $O_i$.

For multi-dimensional data, the adversary's best strategy is to compute the most likely ensemble of errors corresponding to an assignment (or a greedy approximation thereto) and the probability of success is a Bayes factor calculation against other possible assignments and errors.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Given that our values are one dimensional and we have used Laplace distribution for adding noise, is there any other efficient methods than order statistics? Does order statistics work fine in this case? $\endgroup$
    – Amirhossein Adavoudi
    Commented Feb 27 at 22:02
  • $\begingroup$ To Daniel S: Could you explain how the noise model can help to compute the order statistics, given that, in our case, we use the Laplace distribution. $\endgroup$
    – Amirhossein Adavoudi
    Commented Feb 28 at 10:06

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.