Secure Distributed Framework for Achieving Differential Privacy

 
Secure Distributed Framework for
Achieving 
ϵ
-Differential Privacy
 
Dima Alhadidi, Noman Mohammed, Benjamin C. M. Fung, and Mourad Debbabi
Concordia Institute for Information Systems Engineering
Concordia University, Montreal, Quebec, Canada
{dm_alhad,no_moham,fung,debbabi}@encs.concordia.ca
 
Outline
 
Motivation
Problem Statement
Related Work
Background
Two-Party Differentially Private Data
Release
Performance Analysis
Conclusion
 
 
Outline
 
Motivation
Problem Statement
Related Work
Background
Two-Party Differentially Private Data
Release
Performance Analysis
Conclusion
 
Motivation
 
 
Centralized
 
Distributed
 
Motivation
 
Distributed: Vertically-Partitioned
 
Motivation
 
Distributed: Vertically-Partitioned
 
Motivation
 
Distributed: Horizontally-Partitioned
 
Motivation
 
Distributed: Horizontally-Partitioned
 
Motivation
 
Distributed: Horizontally-Partitioned
 
Motivation
 
Distributed: Horizontally-Partitioned
 
Motivation
 
Distributed: Horizontally-Partitioned
 
Outline
 
Motivation
Problem Statement
Related Work
Background
Two-Party Differentially Private Data
Release
Performance Analysis
Conclusion
 
 
Problem Statement
 
Desideratum to develop a two-party
data publishing algorithm for
horizontally-partitioned data which :
achieves differential privacy and
satisfies the security definition of secure
multiparty computation (SMC).
 
 
Outline
 
Motivation
Problem Statement
Related Work
Background
Two-Party Differentially Private Data
Release
Performance Analysis
Conclusion
 
 
Related Work
 
Outline
 
Motivation
Problem Statement
Related Work
Background
Two-Party Differentially Private Data
Release
Performance Analysis
Conclusion
 
 
k-Anonymity
 
k-Anonymity
Quasi-identifier (QID)
 
k-Anonymity
 
Differential Privacy
 
 
D
 
D
Laplace Mechanism
D
 
Exponential Mechanism
 
McSherry and Talwar have proposed
the exponential mechanism that can
choose an output  that is close to the
optimum with respect to a utility
function while preserving differential
privacy.
 
Outline
 
Motivation
Problem Statement
Related Work
Background
Two-Party Differentially Private Data
Release
Performance Analysis
Conclusion
 
 
Two-Party Differentially
Private Data Release
 
 
Generalizing the raw data
Adding noisy count
Generalizing the raw data
Distributed Exponential Mechanism
(DEM)
Generalization
Distributed Exponential Mechanism
(DEM)
 
Adding Noisy Count
 
Each party adds a Laplace noise to
its count .
Each party sends the result to the
other party.
 
Two-Party Protocol for
Exponential Mechanism
 
 
Input:
1.
Two raw data sets by two parties
2.
Set of candidates
3.
Privacy budget
Output : Winner candidate
 
Max Utility Function
 
D
1
 
 
Max Utility Function
 
 
D
2
 
Max Utility Function
 
D
1
 &
 
D
2
 
Computing Max Utility
Function
 
Blue-collar
 
Computing Max Utility
Function
 
max=1  
Blue-collar
 
Computing Max Utility
Function
 
max=1  
Blue-collar
Computing Max Utility
Function
max=5, sum=5  
Blue-collar
 
Computing Max Utility
Function
 
sum=5  
White-collar
 
Computing Max Utility
Function
 
max=2, sum=5 
White-collar
 
Computing Max Utility
Function
 
max=2, sum=5 
White-collar
Computing Max Utility
Function
max=3, sum=8 
White-collar
Result: Shares 
1 
and 
2
 
Computing the Exponential
Equation
Given the scores of all the
candidates, exponential mechanism
selects the candidate having score u
with the following probability:
Shares 
1 
and 
2
 
Computing the Exponential
Equation
 
 
=
Taylor Series
 
=
Computing the Exponential
Equation
 
Lowest common multiplier of {2!,…,w!}, no fraction
Approximating up to a predetermined number s
 after the decimal point
Computing the Exponential
Equation
 
No fraction
Computing the Exponential
Equation
 
Oblivious Polynomial Evaluation
First Party
Second Party
 
Result
First Party
Second Party
Computing the Exponential
Equation
 
Second
 Party
First Party
Computing the Exponential
Equation
 
0
1
 
0.5
 
0.3
 
0.2
 
0.7
Picking a random number
[0,1]
Computing the Exponential
Equation
0
Picking a random number
[0,                   ]
Picking a Random Number
 
Second
 Party
 
Random Value Protocol
[Bunn and Ostrovsky 2007]
First Party
Second
 Party
First Party
 
Picking a Winner
 
Outline
 
Motivation
Problem Statement
Related Work
Background
Two-Party Differentially Private Data
Release
Performance Analysis
Conclusion
 
 
Performance Analysis
 
Adult: 
is a 
Census data
6 numerical attributes.
8 categorical attributes.
45,222 census records
Cost Estimates
37.5 minutes of computation
37.3 minutes of communication using T
1
line with 1.544 Mbits/second bandwidth.
 
Scaling Impact
 
 
Outline
 
Motivation
Problem Statement
Related Work
Background
Two-Party Differentially Private Data
Release
Performance Analysis
Conclusion
 
 
Conclusion
 
Data release algorithm
Two-party
Differentially-private
Secure
Horizontally-partitioned
Non-interactive setting
 
Future Work
 
Consider different scenarios
Two parties vs. multiple parties
Semi-honest vs. malicious adversary
model
Horizontally vs. Vertically partitioned
data
For all these scenarios, we need
efficient algorithms
Slide Note
Embed
Share

This research discusses a secure distributed framework for achieving differential privacy, focusing on motivation, problem statement, related work, background, two-party differentially private data release, and performance analysis. The framework aims to address the challenges of anonymization algorithms, data distribution, and privacy preservation in centralized and distributed systems.

  • Secure Framework
  • Differential Privacy
  • Data Privacy
  • Distributed Systems
  • Anonymization Algorithms

Uploaded on Sep 21, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Secure Distributed Framework for Achieving -Differential Privacy Dima Alhadidi, Noman Mohammed, Benjamin C. M. Fung, and Mourad Debbabi Concordia Institute for Information Systems Engineering Concordia University, Montreal, Quebec, Canada {dm_alhad,no_moham,fung,debbabi}@encs.concordia.ca

  2. Outline Motivation Problem Statement Related Work Background Two-Party Differentially Private Data Release Performance Analysis Conclusion 6/24/2012 2

  3. Outline Motivation Problem Statement Related Work Background Two-Party Differentially Private Data Release Performance Analysis Conclusion 6/24/2012 3

  4. Motivation Centralized Individuals Data Publisher Anonymization Algorithm Data Recipients Distributed 6/24/2012 4

  5. Motivation Distributed: Vertically-Partitioned ID ID Job Job ID Sex Salary 1 Writer 1 M 30K 2 Dancer 2 M 25K 3 Writer 3 M 35K 4 Dancer 4 F 37K 5 Engineer 5 F 65K 6 Engineer 6 F 35K 7 Engineer 7 M 30K 8 Dancer 8 F 44K 9 Lawyer 9 M 44K 10 Lawyer 10 F 44K 6/24/2012 5

  6. Motivation Distributed: Vertically-Partitioned ID ID Job Job Sex Salary 1 Writer M 30K 2 Dancer M 25K 3 Writer M 35K 4 Dancer F 37K 5 Engineer F 65K 6 Engineer F 35K 7 Engineer M 30K 8 Dancer F 44K 9 Lawyer M 44K 10 Lawyer F 44K 6/24/2012 6

  7. Motivation Distributed: Horizontally-Partitioned ID ID Job Job Sex Sex Age Age Surgery Surgery ID ID Job Job Sex Sex Age Age Surgery Surgery 8 Doctor M 58 Plastic 1 Janitor M 34 Transgender 9 Doctor M 24 Urology 2 Lawyer F 58 Plastic 10 Janitor F 63 Vascular 3 Mover M 58 Urology 11 Mover F 63 Plastic 4 Lawyer M 24 Vascular 5 Mover M 34 Transgender 6 Janitor M 44 Plastic 7 Doctor F 44 Vascular 6/24/2012 7

  8. Motivation Distributed: Horizontally-Partitioned ID ID Job Job Sex Sex Age Age Surgery Surgery 1 Janitor M 34 Transgender 2 Lawyer F 58 Plastic 3 Mover M 58 Urology 4 Lawyer M 24 Vascular 5 Mover M 34 Transgender 6 Janitor M 44 Plastic 7 Doctor F 44 Vascular 8 Doctor M 58 Plastic 9 Doctor M 24 Urology 10 Janitor F 63 Vascular 11 Mover F 63 Plastic 6/24/2012 8

  9. Motivation Distributed: Horizontally-Partitioned ID ID Job Job Sex Sex Age Age Surgery Surgery 1 Janitor M 34 Transgender 2 Lawyer F 58 Plastic 3 Mover M 58 Urology 4 Lawyer M 24 Vascular 5 Mover M 34 Transgender 6 Janitor M 44 Plastic 7 Doctor F 44 Vascular 8 Doctor M 58 Plastic 9 Doctor M 24 Urology 10 Janitor F 63 Vascular 11 Mover F 63 Plastic 6/24/2012 9

  10. Motivation Distributed: Horizontally-Partitioned ID ID Job Job Sex Sex Age Age Surgery Surgery 1 Janitor M 34 Transgender 2 Lawyer F 58 Plastic 3 Mover M 58 Urology 4 Lawyer M 24 Vascular 5 Mover M 34 Transgender 6 Janitor M 44 Plastic 7 Doctor F 44 Vascular 8 Doctor M 58 Plastic 9 Doctor M 24 Urology 10 Janitor F 63 Vascular 11 Mover F 63 Plastic 6/24/2012 10

  11. Motivation Distributed: Horizontally-Partitioned ID ID Job Job Sex Sex Age Age Surgery Surgery 1 Janitor M 34 Transgender 2 Lawyer F 58 Plastic 3 Mover M 58 Urology 4 Lawyer M 24 Vascular 5 Mover M 34 Transgender 6 Janitor M 44 Plastic 7 Doctor F 44 Vascular 8 Doctor M 58 Plastic 9 Doctor M 24 Urology 10 Janitor F 63 Vascular 11 Mover F 63 Plastic 6/24/2012 11

  12. Outline Motivation Problem Statement Related Work Background Two-Party Differentially Private Data Release Performance Analysis Conclusion 6/24/2012 12

  13. Problem Statement Desideratum to develop a two-party data publishing algorithm for horizontally-partitioned data which : achieves differential privacy and satisfies the security definition of secure multiparty computation (SMC). 6/24/2012 13

  14. Outline Motivation Problem Statement Related Work Background Two-Party Differentially Private Data Release Performance Analysis Conclusion 6/24/2012 14

  15. Related Work Data Owner Data Owner Privacy Model Privacy Model Algorithms Algorithms Distributed Differential Privacy Partition- based Privacy Centralized Horizontally Vertically LeFevre et al., Fung et al., etc Xiao et al. , Mohammed et al. , etc. Jurczyk and Xiong, Mohammed et al. Jiang and Clifton, Mohammed et al. Our proposal 6/24/2012 15

  16. Outline Motivation Problem Statement Related Work Background Two-Party Differentially Private Data Release Performance Analysis Conclusion 6/24/2012 16

  17. k-Anonymity Raw patient table Job Sex Age Disease Engineer Male 35 Fever Engineer Male 38 Fever Lawyer Male 38 Hepatitis Musician Female 30 Flu Musician Female 30 Hepatitis Dancer Female 30 Hepatitis Dancer Female 30 Hepatitis 6/24/2012 17

  18. k-Anonymity Quasi-identifier (QID) Raw patient table Disease Job Sex Age Engineer Male 35 Fever Engineer Male 38 Fever Lawyer Male 38 Hepatitis Musician Female 30 Flu Musician Female 30 Hepatitis Dancer Female 30 Hepatitis Dancer Female 30 Hepatitis 6/24/2012 18

  19. k-Anonymity Raw patient table 3-anonymous patient table Job Sex Age Disease Job Sex Age Disease Engineer Male 35 Fever Professional Male [36-40] Fever Engineer Male 38 Fever Professional Male [36-40] Fever Lawyer Male 38 Hepatitis Professional Male [36-40] Hepatitis Musician Female 30 Flu Artist Female [30-35] Flu Musician Female 30 Hepatitis Artist Female [30-35] Hepatitis Dancer Female 30 Hepatitis Artist Female [30-35] Hepatitis Dancer Female 30 Hepatitis Artist Female [30-35] Hepatitis 6/24/2012 19

  20. Differential Privacy D D 6/24/2012 20

  21. Laplace Mechanism D 6/24/2012 21

  22. Exponential Mechanism McSherry and Talwar have proposed the exponential mechanism that can choose an output that is close to the optimum with respect to a utility function while preserving differential privacy. 6/24/2012 22

  23. Outline Motivation Problem Statement Related Work Background Two-Party Differentially Private Data Release Performance Analysis Conclusion 6/24/2012 23

  24. Two-Party Differentially Private Data Release Generalizing the raw data Adding noisy count 6/24/2012 24

  25. Generalizing the raw data Distributed Exponential Mechanism (DEM) 6/24/2012 25

  26. Generalization Distributed Exponential Mechanism (DEM) 6/24/2012 26

  27. Adding Noisy Count Each party adds a Laplace noise to its count . Each party sends the result to the other party. 6/24/2012 27

  28. Two-Party Protocol for Exponential Mechanism Input: 1. Two raw data sets by two parties 2. Set of candidates 3. Privacy budget Output : Winner candidate 6/24/2012 28

  29. Max Utility Function ID ID Class Class Job Job Sex Sex Age Age Surgery Surgery Class Class Max Max Job Job Data Set Data Set 1 N Janitor M 34 Transgender Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 2 Y Lawyer F 58 Plastic 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar 3 Y Mover M 58 Urology D1 4 N Lawyer M 24 Vascular 5 Y Mover M 34 Transgender 3 D2 6 Y Janitor M 44 Plastic 7 Y Doctor F 44 Vascular 8 Integrated D1 and D2 D D1 1 6/24/2012 29

  30. Max Utility Function ID ID Class Class Job Job Sex Sex Age Age Surgery Surgery Class Class Max Max Job Job Data Set Data Set 8 N Doctor M 58 Plastic Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 9 Y Doctor M 24 Urology 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar 10 Y Janitor F 63 Vascular D1 11 Y Mover F 63 Plastic 3 D2 D D2 2 8 Integrated D1 and D2 6/24/2012 30

  31. Max Utility Function ID ID Class Class Job Job Sex Sex Age Age Surgery Surgery Class Class Max Max Job Job Data Set Data Set 1 N Janitor M 34 Transgender Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 2 Y Lawyer F 58 Plastic 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar 3 Y Mover M 58 Urology D1 4 N Lawyer M 24 Vascular 5 Y Mover M 34 Transgender 3 D2 6 Y Janitor M 44 Plastic 7 Y Doctor F 44 Vascular 8 Integrated D1 and D2 8 N Doctor M 58 Plastic 9 Y Doctor M 24 Urology 10 Y Janitor F 63 Vascular 11 Y Mover F 63 Plastic D D1 1 & & D D2 2 6/24/2012 31

  32. Computing Max Utility Function Blue-collar Class Class Max Max Job Job Data Set Data Set Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar D1 3 D2 8 Integrated D1 and D2 6/24/2012 32

  33. Computing Max Utility Function max=1 Blue-collar Class Class Max Max Job Job Data Set Data Set Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar D1 3 D2 8 Integrated D1 and D2 6/24/2012 33

  34. Computing Max Utility Function max=1 Blue-collar Class Class Max Max Job Job Data Set Data Set Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar D1 3 D2 8 Integrated D1 and D2 6/24/2012 34

  35. Computing Max Utility Function max=5, sum=5 Blue-collar Class Class Max Max Job Job Data Set Data Set Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar D1 3 D2 8 Integrated D1 and D2 6/24/2012 35

  36. Computing Max Utility Function sum=5 White-collar Class Class Max Max Job Job Data Set Data Set Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar D1 3 D2 8 Integrated D1 and D2 6/24/2012 36

  37. Computing Max Utility Function max=2, sum=5 White-collar Class Class Max Max Job Job Data Set Data Set Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar D1 3 D2 8 Integrated D1 and D2 6/24/2012 37

  38. Computing Max Utility Function max=2, sum=5 White-collar Class Class Max Max Job Job Data Set Data Set Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar D1 3 D2 8 Integrated D1 and D2 6/24/2012 38

  39. Computing Max Utility Function max=3, sum=8 White-collar Class Class Max Max Job Job Data Set Data Set Y Y 3 2 2 1 5 3 N N 1 1 0 1 1 2 5 Blue-collar White-collar Blue-collar White-collar Blue-collar White-collar D1 3 D2 8 Integrated D1 and D2 Result: Shares 1 and 2 6/24/2012 39

  40. Computing the Exponential Equation Given the scores of all the candidates, exponential mechanism selects the candidate having score u with the following probability: Shares 1 and 2 6/24/2012 40

  41. Computing the Exponential Equation Taylor Series = = 6/24/2012 41

  42. Computing the Exponential Equation Lowest common multiplier of {2!, ,w!}, no fraction Approximating up to a predetermined number s after the decimal point 6/24/2012 42

  43. Computing the Exponential Equation No fraction 6/24/2012 43

  44. Computing the Exponential Equation First Party Oblivious Polynomial Evaluation Result First Party Second Party Second Party 6/24/2012 44

  45. Computing the Exponential Equation First Party Second Party 6/24/2012 45

  46. Computing the Exponential Equation Picking a random number [0,1] 0 1 0.2 0.7 0.3 0.5 6/24/2012 46

  47. Computing the Exponential Equation Picking a random number [0, ] 0 6/24/2012 47

  48. Picking a Random Number First Party Second Party Random Value Protocol [Bunn and Ostrovsky 2007] Second Party First Party 6/24/2012 48

  49. Picking a Winner 6/24/2012 49

  50. Outline Motivation Problem Statement Related Work Background Two-Party Differentially Private Data Release Performance Analysis Conclusion 6/24/2012 50

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#