Upload
zeroraider
View
214
Download
0
Embed Size (px)
Citation preview
8/11/2019 CERIAS_Presentation.pdf
1/17
A Practical
Beginners Guide
to Differential Privacy
4/30/2012 C P 1
C PD C
C D
P
A: C C
Presentation Outline
4/30/2012 C P 2
?
H?
?
4/30/2012 C P 3
What?
Youre handed a survey
4/30/2012 C P 4
1) Do you like listening to Justin Bieber?
2) How many Justin Bieber albums do you own?
3) What is your gender?
4) What is your age?
,
.
: .
?
8/11/2019 CERIAS_Presentation.pdf
2/17
The Notation
4/30/2012 C P 5
The Notation
4/30/2012 C P 6
The Notation
4/30/2012 C P 7
I
The Notation
4/30/2012 C P 8
8/11/2019 CERIAS_Presentation.pdf
3/17
The Notation
4/30/2012 C P 9
I
The Notation
4/30/2012 C P 10
Q
R
The Notation
4/30/2012 C P 11
What do we want?
4/30/2012 C P 12
I
I
.
I
R
( )
.
Q(D(I)) = Q(DI)
P(() R) =
P(())
8/11/2019 CERIAS_Presentation.pdf
4/17
Why cant we have it?
4/30/2012 C P 13
I
I R
( 1015
J B),
, ( I
).
B ,
Q(D(I)) = Q(DI) Q(DI) = Q(D)
P(() (P) )
> P(())
Why cant we have it?
4/30/2012 C P 14
E ,
:
I
I
. (E I
!)
(() = 2*)
(() )
( = 14) ( = F)
(() = 28)
(() = M)
One more try
4/30/2012 C P 15
,
A
,
(
).
?
One more try
4/30/2012 C P 16
I .
I I
R
, I
.
8/11/2019 CERIAS_Presentation.pdf
5/17
Differential Privacy
4/30/2012 C P 17
D P
:
R
, .
( = )
( = )
, , ,
, .
1 . A 1, . I=1,
. F, = > 0,
, .
Differential Privacy
4/30/2012 C P 18
R
, .
= ) = )
, , , > 0
P(R) = AP(R) = B
A B
G R, ?
Dont get carried away
4/30/2012 C P 19
:
I
,
.
A ,
,
, !
R
,
.
())
()) ,
, ,
> 0
Dont get carried away
4/30/2012 C P 20
:
A
.
D
,
.
? I
,
,
, .
R
,
.
())
( )) ,
,,
> 0
8/11/2019 CERIAS_Presentation.pdf
6/17
Differential Privacy
4/30/2012 C P 21
D R
.
I ,
P I I
. I .
Differential Privacy
4/30/2012 C P 22
D R
.
I .
I
:
R .
Differential Privacy
4/30/2012 C P 23
D R
.
I .
I .
I
.
.
4/30/2012 C P 24
How?
8/11/2019 CERIAS_Presentation.pdf
7/17
How do we do it?
4/30/2012 C P 25
1) Do you like listening to Justin Bieber?
2) How many Justin Bieber albums do you own?
3) What is your gender?
4) What is your age?
How do we do it?
4/30/2012 C P 26
3
37
. H ?
Global Sensitivity
4/30/2012 C P 27
G 1 2 ,
() , D,
.
F : =
, 1 2 1
I,
.
Global Sensitivity
4/30/2012 C P 28
F :
= ,
1 2 1
I,
.
+1
=1
H J B?
8/11/2019 CERIAS_Presentation.pdf
8/17
Global Sensitivity
4/30/2012 C P 29
F :
= ,
1 2 1
I,
.
+1
+1
=1
H ?
Global Sensitivity
4/30/2012 C P 30
F :
= ,
1 2 1
I,
.
+1
+1
+1
= 2
H ?
A H J B?
Global Sensitivity
4/30/2012 C P 31
F :
= ,
1 2 1
I,
.
+
=?
B ?
Global Sensitivity
4/30/2012 C P 32
F :
= ,
1 2 1
I,
.
+ 3
= 3
B ?
8/11/2019 CERIAS_Presentation.pdf
9/17
Global Sensitivity
4/30/2012 C P 33
F :
= ,
1 2 1
I,
.
+ /
=?
?
Laplacian Noise
4/30/2012 C P 34
I
,
.
?
R
L
. , .
P L D:
=
2
Laplacian Noise
4/30/2012
=
2
A L
.
Laplacian Noise
4/30/2012
1 2 30
J R,
.
, . B
.
=
2
8/11/2019 CERIAS_Presentation.pdf
10/17
THE PROOF!
4/30/2012 C P 37
L
. E!
: ())
())
THE PROOF!
4/30/2012 C P 38
L
. E!
: ())
())
L :
2
2
THE PROOF!
4/30/2012 C P 39
L
. E!
:
:
THE PROOF!
4/30/2012 C P 40
L
. E!
:
R :
8/11/2019 CERIAS_Presentation.pdf
11/17
8/11/2019 CERIAS_Presentation.pdf
12/17
Give it a try!
4/30/2012 C P 45
,
. F, :
H ?
A L F = 1,
Give it a try!
4/30/2012 C P 46
,
. F, :
H
? (, ?,
?,
1216?, )
Give it a try!
4/30/2012 C P 47
,
. F, :
H ? (, ?,
?,
1216?, )
A L F = 5,
Give it a try!
4/30/2012 C P 48
,
. F, :
H , I , (
) I ?
8/11/2019 CERIAS_Presentation.pdf
13/17
Give it a try!
4/30/2012 C P 49
,
. F, :
H , I
, (
) I ?
A L F = 2,
Give it a try!
4/30/2012 C P 50
,
. F, :
H
? L ,
H ?
Give it a try!
4/30/2012 C P 51
,
. F, :
H ? L ,
H ?
Q : . ,
(
,
1 ,
).
Give it a try!
4/30/2012 C P 52
,
. F, :
H
? L , H ?
B A: M
( ),
( ) .
.
D1 D2 .
8/11/2019 CERIAS_Presentation.pdf
14/17
Breaking and Fixing Things
4/30/2012 C P 53
O , . H
:
H I ,
J B?
, :
(610), (1113), (1416), (1720), (2025), (2535), (3545), (> 45)
Breaking and Fixing Things
4/30/2012 C P 54
O , . H
:
H I ,
J B?
, :
(610), (1113), (1416), (1720), (2025), (2535), (3545), (> 45)
B, ! ,
( ). .
Breaking and Fixing Things
4/30/2012 C P 55
O , . H
:
H I ,
J B?
, :
(610), (1113), (1416), (1720), (2025), (2535), (3545), (> 45)
B, ! ,
I (
, , , ).
Breaking and Fixing Things
4/30/2012 C P 56
O , . H
:
H I ,
J B?
, :
(610), (1113), (1416), (1720), (2025), (2535), (3545), (> 45)
B, ! ,
B (
). F , ,
.
8/11/2019 CERIAS_Presentation.pdf
15/17
8/11/2019 CERIAS_Presentation.pdf
16/17
8/11/2019 CERIAS_Presentation.pdf
17/17
General Differential Privacy
4/30/2012 C P 65
():
C D. 2008. D : . I
(AMC'08), M A, D D, D, A
L (E.). , B, H, 119
:
D K A M. 2011. N .
I 0 (IGMOD
'11). ACM, N , N,
J G, E L, R P. 2011.
: . I
(CC'11), I (E.). ,
B, H, 432449
4/30/2012 C P 66
Questions?