# How can we define $\epsilon$-differential privacy for non-deterministic algorithms?

We know that non-trival deterministic algorithm does not guarantee privacy and randomization is essential for privacy (pp.16 in [Dwork and Roth 2014] ). The well-known $$\epsilon$$-diferential privacy is defined for randomized (probabilistic) algorithm (see the link https://en.wikipedia.org/wiki/Differential_privacy).

From a broader perspective of uncertainty, I wonder whether we can define a similar diferential privacy notion for non-determinstic (multi-valued or set-valued) algorithms? And how?

• what on earth is the difference between randomized and non-deterministic? explain better, instead of citing a page in a reference that is either a book or a paper. Aug 17, 2020 at 0:36
• In my question, randomized algorithm actually means probabilistic, i.e., for each input, the algorithm output is a probabilistic distribution over the output space. In contrast, a nondeterministic (set-valued) algorithm output is a subset of the output space instead. Aug 17, 2020 at 0:49

I find that question very interesting. They are arguing that there is not a notion of diferential privacy for all non-deterministic algorithms. Some non-deterministic algorithms could be $$(\varepsilon,\delta)$$-differential private. But not every non-deterministic algorithm is $$(\varepsilon,\delta)$$-differential private, they give the example of the algorithm.
Input: Database $$D$$
Output: $$f(D)$$ dropping a row/register from D (non-deterministically), where $$f$$ is the query function (median,sum,etc).
Note this algorithm is non-deterministic but it is possible to know all the information from the databases if you use this algorithm repetitively. Consider the worst case, the attacker knows all the database except one row (That's why is a condition that $$|D-D'|\leq 1$$). Therefore you can't guarantee privacy for all or some the rows/registers.