2
$\begingroup$

Differential privacy can be used to show that the "privacy loss" of a certain computation is "bounded" in a meaningful way. In cryptography, often "indistinguishability" is considered, i.e. we want $\Delta(D_0, D_1)$ to be small. Can these two concepts be related?

I know vaguely that standard notions of differential privacy can be related to things like "concentrated differential privacy", which itself is a Renyi-type bound on two distributions (which is somewhat similar to the total variation distance bound that I want). But I want to end my proof with "So, the two distributions are indistinguishable" --- can differential privacy help me with this goal?

$\endgroup$
2
  • $\begingroup$ Can you specify the "renyi type" bound you're talking about. A quick look at Dwork's paper shows bounds depending on subgaussian properties. $\endgroup$
    – kodlu
    Mar 16 '21 at 1:08
  • $\begingroup$ @kodlu Later papers by Bun and Steinke recast things in terms of Renyi-divergences I think. I'm mostly going on information from this paper. $\endgroup$
    – Mark
    Mar 16 '21 at 1:33
2
$\begingroup$

These sorts of arguments come up in the theory of randomness extractors where we argue that a random function from a certain family when applied to inputs with a certain minimum entropy ($H_\infty$, the -ve log-maximum probability of an outcome in the Renyi notation) produce outputs that are indistinguishable from uniform up to some $\epsilon$ bound. The differential privacy of the uniform and extractor distributions can be bounded in terms of input size, output size and $H_\infty$ (see for example the Kamp and Zuckerman theorem of the article).

The min-entropy should be the choice of entropy function when using differential privacy as it bounds the worst case scenario of concentration of inputs.

$\endgroup$

Your Answer

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

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