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

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

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 ...


1

I believe you're talking about homomorphic encryption. It allows to have operations on encrypted data. A simple use-case example: Sometimes data has to be kept confidential (i.e. names, address, ... ). It could be that you want to perform computing on data but you're missing the computational power to do so. So you're outsourcing this computation to ...


1

Naive hashing protocol Suppose Alice has items $x_1, \ldots, x_n$ and Bob has items $y_1, \ldots, y_n$. In the naive hashing protocol, they agree on a common hash function $H$, and Alice sends $H(x_1), \ldots, H(x_n)$ to Bob. Bob can compute $H(y_1), \ldots, H(y_n)$ and then calculate the plaintext intersection between these two lists. Insecurity of naive ...


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 ...


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