4

In short, with this multiplicative definition, it could be ruled out the possibility that an individual's record would be randomly selected and published. Consider a malicious algorithm $M^*$ that picks a random individual's record from the input database (of size $n$) and outputs it. Note that this $M^*$ should not be considered secure for a good ...


3

No, it means that the functions are chosen from some domain with some probability distribution. This is standard for randomized algorithms. For simplicity, assume there are $N$ randomized functions $\mathcal{K}$ possible, and one choose one uniformly with probability $1/N.$ For example, if we restricted ourselves to polynomials of degree $\leq k$ over $...


2

I think this is a reference to group privacy. See Theorem 2.2 in the Dwork-Roth book. If you have $(\varepsilon,0)$-differential privacy for changing 1 edge, then you have $(1,0)$-differential privacy for changing $1/\varepsilon$ edges.


1

I think what you are looking for is "Perceptual Hashing". What I understand from your question is that you need a way for programmatically identifying images even when they have been manipulated beyond human recognition. Their is a Microsoft project called PhotoDNA. I believe the have a cloud API. You may also want to look at this Python example


1

Differential privacy is a property of an algorithm (or if you like, a probability distribution over functions), not a property of either the inputs or the outputs of that algorithm. The definition of differential privacy has a universal quantifier over its inputs: for all pairs of inputs that differ in at most one record, the probabilities of any outcome ...


1

Model inversion attacks are, by definition, impossible if the model generation process is $\epsilon$-differentially private for a sufficiently small $\epsilon$: differential privacy guarantees that if your original data was completely different, you would not be able to tell the difference just by looking at the model. Your data is effectively indiscernible ...


1

It would be helpful to have a link to the paper you are referring to. But the basic composition theorem says that each query $i$ an attacker sends to the database will just add its corresponding $\varepsilon_i$ to the total $\varepsilon$ of the entire process: $\varepsilon=\sum_i\varepsilon_i$. So "session" probably means "single query" in the context of ...


1

Reversible implies collision-resistant, as you have defined it. The criteria you have written down are essentially the criteria of deterministic encryption; if you add the criterion that it be hard for anyone without an app's key to forge a masked user id, then deterministic authenticated encryption[1] is exactly what you seem to be looking for. If a user ...


1

In Salil Vadhan's textbook The Complexity of Differential Privacy the author states in section 1.4 The choice of a multiplicative measure of closeness between distributions is important, and we will discuss the reasons for it later. It is technically more convenient to use $e^\epsilon$ instead of $(1 + \epsilon)$, because the former behaves more nicely ...


Only top voted, non community-wiki answers of a minimum length are eligible