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?

  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Aug 17, 2020 at 0:36
  • $\begingroup$ 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. $\endgroup$
    – Joe Zhou
    Aug 17, 2020 at 0:49

1 Answer 1


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.


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.