Introduction to Privacy-Preserving Data Publishing: Concepts and Techniques

9781420091502-f......Page 1
Contents......Page 6
List of Figures......Page 13
List of Tables......Page 15
List of Algorithms......Page 18
Preface......Page 19
Acknowledgments......Page 25
About the Authors......Page 26
I. The Fundamentals......Page 28
1. Introduction......Page 29
1.1 Data Collection and Data Publishing......Page 30
1.2 What Is Privacy-Preserving Data Publishing?......Page 33
1.3 Related Research Areas......Page 35
2. Attack Models and Privacy Models......Page 38
2.1 Record Linkage Model......Page 39
2.1.1 k-Anonymity......Page 40
2.1.3 Dilemma on Choosing QID......Page 43
2.2 Attribute Linkage Model......Page 44
2.2.1 ℓ-Diversity......Page 45
2.2.3 (X, Y)-Linkability......Page 48
2.2.5 (β, k)-Anonymity......Page 49
2.2.6 LKC-Privacy......Page 50
2.2.7 (k, e)-Anonymity......Page 51
2.2.9 Personalized Privacy......Page 52
2.2.10 FF-Anonymity......Page 53
2.3 Table Linkage Model......Page 54
2.4.2 ε-Differential Privacy......Page 55
2.4.4 Distributional Privacy......Page 56
2.5.1 Skyline Privacy......Page 57
2.5.3 Skyline (B, t)-Privacy......Page 58
3.1 Generalization and Suppression......Page 60
3.2 Anatomization and Permutation......Page 63
3.3.1 Additive Noise......Page 66
3.3.3 Synthetic Data Generation......Page 67
4.1.1 Minimal Distortion......Page 68
4.1.3 Discernibility Metric......Page 69
4.2 Special Purpose Metrics......Page 70
4.3 Trade-Off Metrics......Page 72
5.1.1 Optimal Anonymization......Page 74
5.1.2 Locally Minimal Anonymization......Page 76
5.1.3 Perturbation Algorithms......Page 79
5.2.1 ℓ-Diversity Incognito and ℓ+-Optimize......Page 80
5.2.3 Top-Down Disclosure......Page 81
5.2.4 Anatomize......Page 82
5.2.6 Personalized Privacy......Page 83
5.4 Algorithms for the Probabilistic Attack Model......Page 84
5.5.1 Minimality Attack......Page 86
5.5.2 deFinetti Attack......Page 88
5.5.3 Corruption Attack......Page 89
II. Anonymization for Data Mining......Page 92
6.1 Introduction......Page 93
6.2.1 Privacy Model......Page 98
6.2.2 Information Metrics......Page 99
6.2.3 Problem Statement......Page 105
6.3 High-Dimensional Top-Down Specialization (HDTDS)......Page 106
6.3.1 Find the Best Specialization......Page 107
6.3.2 Perform the Best Specialization......Page 108
6.3.4 Discussion......Page 111
6.4.1 Single Categorical Target Attribute......Page 113
6.4.2 Single Numerical Target Attribute......Page 114
6.4.4 Discussion......Page 115
6.5.1 The Anonymization Algorithm......Page 116
6.5.2 Data Structure......Page 117
6.6 Genetic Algorithm......Page 119
6.7 Evaluation Methodology......Page 120
6.7.1 Data Utility......Page 121
6.7.2 Efficiency and Scalability......Page 126
6.8 Summary and Lesson Learned......Page 127
7.2 Anonymization Framework for Cluster Analysis......Page 129
7.2.1 Anonymization Problem for Cluster Analysis......Page 132
7.2.2 Overview of Solution Framework......Page 136
7.2.3 Anonymization for Classification Analysis......Page 138
7.2.4 Evaluation......Page 142
7.2.5 Discussion......Page 145
7.3.1 Dimensionality Reduction......Page 148
7.3.2 The DRBT Method......Page 149
7.5 Summary......Page 150
III. Extended Data Publishing Scenarios......Page 152
8.1 Introduction......Page 153
8.2.1 Violations by Multiple Selection-Project Views......Page 155
8.2.3 Discussion......Page 158
8.3 Checking Violations with Marginals......Page 159
8.5 Multi-Level Perturbation......Page 162
8.6 Summary......Page 163
9.1.1 Motivations......Page 164
9.1.2 Anonymization Problem for Sequential Releases......Page 168
9.2 Monotonicity of Privacy......Page 172
9.3.1 Overview of the Anonymization Algorithm......Page 174
9.3.2 Information Metrics......Page 175
9.3.3 (X, Y )-Linkability......Page 176
9.3.4 (X, Y )-Anonymity......Page 179
9.5 Summary......Page 180
10.1 Introduction......Page 182
10.2.1 Data Model......Page 185
10.2.2 Correspondence Attacks......Page 186
10.2.3 Anonymization Problem for Continuous Publishing......Page 189
10.2.4 Detection of Correspondence Attacks......Page 196
10.2.5 Anonymization Algorithm for Correspondence Attacks......Page 199
10.2.6 Beyond Two Releases......Page 201
10.3 Dynamic Data Republishing......Page 202
10.3.1 Privacy Threats......Page 203
10.3.2 m-invariance......Page 204
10.4 HD-Composition......Page 206
10.5 Summary......Page 211
11.1 Introduction......Page 213
11.2 Privacy-Preserving Data Mashup......Page 214
11.2.1 Anonymization Problem for Data Mashup......Page 219
11.2.2 Information Metrics......Page 221
11.2.3 Architecture and Protocol......Page 222
11.2.4 Anonymization Algorithm for Semi-Honest Model......Page 224
11.2.5 Anonymization Algorithm for Malicious Model......Page 230
11.2.6 Discussion......Page 237
11.3.1 Secure Multiparty Computation......Page 238
11.3.2 Minimal Information Sharing......Page 239
11.4 Summary and Lesson Learned......Page 240
12.1 Introduction......Page 241
12.2 Privacy Model......Page 242
12.3 Overview of the Solution......Page 243
12.4 Discussion......Page 244
IV. Anonymizing Complex Data......Page 246
13.1.1 Motivations......Page 247
13.1.2 The Transaction Publishing Problem......Page 248
13.1.3 Previous Works on Privacy-Preserving Data Mining......Page 249
13.1.4 Challenges and Requirements......Page 250
13.2 Cohesion Approach......Page 252
13.2.1 Coherence......Page 253
13.2.2 Item Suppression......Page 254
13.2.3 A Heuristic Suppression Algorithm......Page 255
13.2.4 Itemset-Based Utility......Page 258
13.2.5 Discussion......Page 259
13.3 Band Matrix Method......Page 260
13.3.2 Constructing Anonymized Groups......Page 261
13.3.3 Reconstruction Error......Page 263
13.3.4 Discussion......Page 264
13.4.1 km-Anonymity......Page 265
13.4.2 Apriori Anonymization......Page 266
13.4.3 Discussion......Page 268
13.5.1 k-Anonymity for Set Valued Data......Page 270
13.5.3 Discussion......Page 272
13.6.1 Token-Based Hashing......Page 273
13.6.2 Secret Sharing......Page 274
13.6.4 Other Related Works......Page 275
13.7 Summary......Page 276
14.1.1 Motivations......Page 278
14.1.2 Attack Models on Trajectory Data......Page 279
14.2 LKC-Privacy......Page 281
14.2.1 Trajectory Anonymity for Maximal Frequent Sequences......Page 282
14.2.2 Anonymization Algorithm for LKC-Privacy......Page 286
14.2.3 Discussion......Page 293
14.3.1 Trajectory Anonymity for Minimal Distortion......Page 295
14.3.2 The Never Walk Alone Anonymization Algorithm......Page 297
14.3.3 Discussion......Page 298
14.4.1 Trajectory Anonymity for Minimal Information Loss......Page 299
14.4.2 Anonymization Algorithm for MOB k-Anonymity......Page 301
14.5 Other Spatio-Temporal Anonymization Methods......Page 305
14.6 Summary......Page 306
15.1 Introduction......Page 307
15.1.2 Attack Models......Page 308
15.2 General Privacy-Preserving Strategies......Page 313
15.2.2 Equivalence Classes of Nodes......Page 314
15.3.1 Edge Insertion and Label Generalization......Page 315
15.3.2 Clustering Nodes for k-Anonymity......Page 316
15.3.3 Supergraph Generation......Page 317
15.3.6 Not Releasing the Network......Page 318
15.5 Summary......Page 319
16.1 Introduction......Page 321
16.2.2 Privacy Model: K-Safety......Page 322
16.2.3 Problem Statement......Page 323
16.2.4 Sanitization Algorithms for K-Safety......Page 324
16.3.1 De-Identification Models......Page 325
16.3.2 The HIDE Framework......Page 326
16.4 Summary......Page 327
17.1 Interactive Query Model......Page 328
17.2 Privacy Threats Caused by Data Mining Results......Page 330
17.3 Privacy-Preserving Distributed Data Mining......Page 331
17.4 Future Directions......Page 332
References......Page 334