A Summary on Differential Privacy

By Kato Mivule

The latest state-of-the-art in data privacy, proposed by Cynthia Dwork (2006).

Differential privacy enforces confidentiality by:

• Returning perturbed aggregated query results from databases.

• Such that users cannot discern if any data item has been altered or not.

• An attacker cannot derive info about any data item in the database.

According to Dwork (2006):

• Two databases D₁ and D₂ are considered similar, if they differ in only one element or row,

• That is D₁ Δ D₂ = 1.

• Therefore, a privacy granting procedure q_n satisfies  -differential privacy if results to the same query run on database D₁ and again run on database D₂ should probabilistically be similar, and satisfy the following condition:

P[q_n(D₁) ∈ R] / P[q_n(D₂) ∈ R] ≤ exp()

• Where D₁and D₂ are the two databases.

• P is the probability of the perturbed query results D₁and D₂ respectively.

• q_n() is the privacy granting procedure (perturbation).

• q_n(D₁) the privacy granting procedure on query results from database D₁ .

• q_n(D₂) the privacy granting procedure on query results from database D₂ .

• R is the perturbed query results from the databases D₁and D₂ respectively.

• exp()the exponential  epsilon value.

The probability of the perturbed query results q_n(D₁) divided by the probability of the perturbed query results q_n(D₂) should be less or equal to a exponential  epsilon value.

That is to say, if we run the same query on database D₁, and then run the same query again on database D₂, our query results should probabilistically be similar.

If the condition can be satisfied in the existence or nonexistence of the most influential observation for a specific query, then this condition will also be satisfied for any other observation.

The effect of the most influential observation for a given query is Δf, assessed as follows:

Δf = Max||f(D₁) – f(D₁)|| for all possible observed values of D₁ and D₂

According to Dwork (2006), the results to a query are given as

• f(x) + Laplace(0, b) noise addition

• Where b = Δf/

• x represents a particular observed value of the database

• f(x) represents the true result to the query

• Then the result would satisfy -differential privacy

• The Δf must consider all possible observed values of D₁ and D₁

Differential Privacy Ilustration

Example:

What is the GPA of students at Geek Nerd State University?

We compute the maximum possible difference between two databases that differ in exactly one record for a specific query.

Δf = Max||f(D₁) – f(D₂)||

Let Min GPA = 2.0 for smallest possible GPA

Let Max GPA = 4.0 for largest possible GPA

Δf = | Max GPA – Min GPA|

Δf = 2.0

The parameter b of the Laplace noise is set to Δf/ = 2.0/0.01 = 200

Laplace (0, 200) noise distribution.

Variance of the noise distribution = 2* 200^2 = 80000

A small  value of 0.01 is chosen. Smaller  yield greater privacy by the procedure.

However, utility risks degeneration with a much more smaller value of .

For example,  at 0.0001, will give b as 20000, Laplace (0, 20000) noise distribution.

The unperturbed results of the query +

Noise from Laplace (0, 200) =

Perturbed query results satisfying -differential privacy.

SQL: SELECT GPA FROM Student + Laplace Noise (0, 200) = -differential query results.

Pros and Cons

• Grants across-the-board Privacy.

• Easy to implement with SQL for aggregated data publication.

• Utility a challenge as statistical properties change with a much smaller .

• Noise takes into account the outliers and most influential observation.

• Example, income of Warren Buffet verses income of janitor in Omaha Nebraska.

• Balance between Privacy and Utility still an NP-Hard challenge.

References

[1] C. Dwork, “Differential privacy,” in in ICALP, vol. 2, 2006, pp. 1-12. [Online]. Available: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.83.7534

[2] K. Muralidhar and R. Sarathy, “Does differential privacy protect terry gross’ privacy?” in Privacy in Statistical Databases, ser. Lecture Notes in Computer Science, J. Domingo-Ferrer and E. Magkos, Eds.    Berlin, Heidelberg: Springer Berlin / Heidelberg, 2011, vol. 6344, ch. 18, pp. 200-209. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-15838-4_18

About these ads