1 of 51

FriendlyCore:�Tool for Differentially Private Aggregation

Eliad Tsfadia

Joint with: Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer

2 of 51

About Me

PhD Student at Tel Aviv University Cryptography

Researcher at Google

Differential Privacy

This Talk

3 of 51

 

 

Differentially Privacy (DP)

Dwork, McSherry, Nissim, Smith 2006

 

4 of 51

 

Differentially Privacy (DP)

Dwork, McSherry, Nissim, Smith 2006

 

5 of 51

Example: DP Averaging [Dwork, McSherry, Nissim, Smith 2006]

 

 

 

6 of 51

Friendly datasets

 

 

 

 

7 of 51

Friendly datasets

 

“almost” friendly

 

 

 

 

With DP: (almost) same output

8 of 51

(wishful) FriendlyCore Paradigm

 

 

 

 

x

x

 

 

9 of 51

Sample and Aggregate Framework �Nissim, Raskhodnikova, Smith 2007

  •  

 

 

Indication: A random sample of the data provides a good answer (non privately)

10 of 51

 

 

Example: Clustering

k-tuple Clustering

11 of 51

​

​

​

​

Friendly tuples:

 

x

x

x

x

12 of 51

(wishful) FriendlyCore Paradigm

 

 

13 of 51

(wishful) FriendlyCore Paradigm

 

 

14 of 51

(wishful) FriendlyCore Paradigm

 

 

 

15 of 51

K-tuples: Friendly DP is not DP!

 

 

 

 

16 of 51

K-tuples: Friendly DP is not DP!

 

 

 

17 of 51

K-tuples: Friendly DP is not DP!

 

 

 

18 of 51

K-tuples: Friendly DP is not DP!

 

 

 

19 of 51

K-tuples: Friendly DP is not DP!

 

 

 

D is not friendly => Step 2 may induce different clusters.

​

Key Property:

D and D’ are friendly => Same clusters in Step 2,�(and clustering becomes trivial).

20 of 51

FriendlyCore (simplified)

 

 

 

21 of 51

FriendlyCore (simplified)

 

 

 

Averaging

 

 

 

22 of 51

FriendlyCore (simplified)

 

 

 

k-tuple Clustering

 

 

 

 

 

 

 

23 of 51

FriendlyCore (simplified)

 

 

 

Averaging ordered k-tuples

 

 

 

 

 

 

 

 

 

 

24 of 51

FriendlyCore (simplified)

 

 

 

 

 

 

 

 

 

25 of 51

FriendlyCore for DP

 

 

 

 

26 of 51

FriendlyCore for zCDP (simp.)

 

 

 

27 of 51

FriendlyCore DP vs. zCDP

 

 

 

28 of 51

FriendlyCore

 

 

 

 

29 of 51

Demo: �Mean estimation

30 of 51

 

 

 

31 of 51

 

 

32 of 51

 

 

33 of 51

Demo: �Clustering via Sample and Aggregate

34 of 51

 

35 of 51

  • Random partition to 300 parts.
  • On each part: Run KMeans (sklearn) 🡪 3 centers (3-tuple)
  • Showing 900 points of the 300 3-tuples

36 of 51

  • FriendlyCore of the 300 3-tuples 🡪 207/300 tuples

37 of 51

  • Pick an arbitrary tuple (black) from the core
  • Use tuple to split into 3 clusters

Safe because the core is CERTIFIED to be friendly!

38 of 51

  • Compute a DP average in each set �(using FriendlyCore Average)
  • We get 3 private points (red)

39 of 51

The 3 private centers placed in the original dataset

40 of 51

Performing a final private Lloyd Step

41 of 51

Averaging: Previous results

 

 

 

 

42 of 51

 

 

 

 

43 of 51

 

 

 

 

44 of 51

 

 

 

 

45 of 51

Clustering: Previous Results

 

46 of 51

k-Means Clustering

 

47 of 51

k-Means Clustering

 

 

FriendlyCore: creating 200 tuples�using Python KMeans (sklearn)

48 of 51

k-Means Clustering

49 of 51

k-GMM

 

FriendlyCore: creating 200 tuples�using PCA based clustering

50 of 51

k-Means Clustering (Real Data)

 

 

FriendlyCore: creating 200 tuples�using Python KMeans (sklearn)

51 of 51

Summary

  • FriendlyCore: tool for private aggregation tasks
    • Examples: averaging (mean estimation) and clustering
  • Flexibility in specification of the predicates – can support further applications
  • Averaging:
    • Advantage on high dimension.
    • Not tailored for Gaussians.
  • Clustering:
    • FriendlyCore: Accurate results on success, but it might fail.
    • FriendlyCore + LSH as backup: preferable in many cases.

​

Thank you!