0
$\begingroup$

It is well-known that the binary randomized response mechanism is differentially private, with $\varepsilon=ln(3)$ if each person answers truthfully with probability $0.5$, and uniformly randomly otherwise.

A slightly generalized version can be: each person answers truthfully with probability $p$, and uniformly randomly otherwise. Then, using the formula on the last slide of this deck, we get $\varepsilon=\frac{1+p}{1-p}$.

My question: what if we have more than one option? I'm guessing the following mechanism would also be differentially private: answer truthfully with probability $p$, and uniformly otherwise. Do we get the same $\varepsilon$ than in the binary case, or does the privacy parameter get worse as the number of option increases?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.