Differential Privacy Sample Clauses

Differential Privacy. Differential privacy has emerged as one of the strongest privacy definitions for statistical data release. It guarantees that if an adversary knows complete information of all the tuples in D except one, the output of a differentially private randomized algorithm should not give the adversary too much additional information about the remaining tuples. We say datasets D and Dj differing in only one tuple if we can obtain Dj by removing or adding only one tuple from D. A formal definition of differential privacy is given as follows: 3.1.1 (s-differential privacy [3]). Let A be a randomized algorithm over two datasets D and Dj differing in only one tuple, and let O be any arbitrary set of possible outputs of A. Algorithm A satisfies s-differential privacy if and only if the following holds: Pr[A(D) ∈ O] ≤ esPr[A(Dj) ∈ O] Intuitively, differential privacy ensures that the released output distribution of A remains nearly the same whether or not an individual tuple is in the dataset. The most common mechanism to achieve differential privacy is the Laplace mech- anism [3] that adds a small amount of independent noise to the output of a numeric function f to fulfill s-differential privacy of releasing f , where the noise is drawn from Laplace distribution with a probability density function Pr[η = x] = 1 e− |x| . A 2b Laplace noise has a variance 2b2 with a magnitude of b. The magnitude b of the noise depends on the concept of sensitivity which is defined as follows. 3.1.2 (Sensitivity [3]). Let f denote a numeric function and the sensi- tivity of f is defined as the maximal L1-norm distance between the outputs of f over the two datasets D and Dj which differs in only one tuple. Formally, ∆f = maxD,Dj ||f (D) − f (Dj)||1. 3.1. PRELIMINARIES 19

Differential Privacy. Intuitively, a randomized mechanism A is differ- entially private if its outcome is not significantly affected by the removal or addi- tion of any record. s-differential privacy is formally defined as Pr[A(D) ∈ O] ≤ esPr[A(Dj) ∈ O], where O is any arbitrary set of possible outputs of A, D and Dj are two neighbouring datasets differing in at most one record (i.e. D can be obtained from Dj by adding or removing at most one record). In our problem definition, an adversary should learn approximately the same information about any individual user given D˜ , irrespective of its presence or absence in D, and one individual can be present in up to N snapshots in D. Two series of dynamic datasets D and Dˆ are user-level neighbors if one can be obtained by adding or removing one individual (including all its occurrences in the snapshots) from the other. Then user-level s-differential privacy is defined as below. 4.1. PRELIMINARIES 47 Definition 4.1.1 (user-level s-differential privacy). Let A be a randomized mecha- nism over two user-level neighbors D, and Dˆ which differ in one user’s presence in the entire series, and let O be any arbitrary set of possible outputs of A. Algorithm A satisfies s-differential privacy iff the following holds Pr[A(D) ∈ O] ≤ esPr[A(Dˆ ) ∈ O] Laplace Mechanism. Dwork et al. [3] show that s-differential privacy can be achieved by adding i.i.d. Laplace noise to query result q(D), where D is a dataset. Formally, q˜(D) = q(D) + (ν1, . . . , νM )j, where νi ∼ Lap(0, GS(q)), for i = 1, . . . , M , and M is the dimension of q(D). νi follows a Laplace distribution with mean zero and scale GS(q), where GS(q) denotes the global sensitivity [3] of the query q. The global sensitivity is the maximum L1 distance between the results of q from any two neighbouring datasets D and Dj, formally defined as GS(q) = maxD,Dj ||q(D) − q(Dj)||1. In our problem setting, the global sensitivity of any two user-level neighbors D and Dˆ is formally defined as GS(q) = maxD,Dˆ ||q(D) − q(Dˆ)||N . For a sequence of DP mechanisms, the sequential composition theorem [6] guar- antees its overall privacy as follows: Theorem 4.1.1 (Sequential Composition [6]). For a sequence of n mechanisms M1, . . . , Mn and each Mi provides si-differential privacy, the sequence of Mi will pro- i=1 vide (Σn si) differential privacy. Hence, one way to achieve epsilon-differential privacy for the entire series of D is to apply Laplace mechanism for each Di with noise Lap(N ), which leads to O...