Algorithms For Data And Computation Privacy

Contents......Page 6
Acronyms......Page 16
Part I Privacy Preserving Queries......Page 18
1.1.1 Background and Motivation......Page 19
1.1.3 Security Model......Page 21
1.1.4 Summary and Limitation of Prior Art......Page 22
1.1.6 Technical Challenges and Solutions......Page 23
1.3 PBtree Construction......Page 24
1.3.2 Tree Construction......Page 25
1.3.3 Node Randomization Using Bloom Filters......Page 28
1.3.4 Trapdoor Computation......Page 29
1.3.6 False Positive Analysis......Page 30
1.4 PBtree Search Optimization......Page 31
1.4.1 Traversal Width Optimization......Page 32
1.4.2 Traversal Depth Optimization......Page 35
1.5.1 PBtree Insertion Algorithm......Page 37
1.5.2 PBtree Modification Algorithm......Page 38
1.5.3 PBtree Deletion Algorithm......Page 39
1.6.1 Security Model......Page 40
1.6.2 Security Proof......Page 41
1.7.1.1 Data Sets......Page 43
1.7.1.3 Query Types......Page 44
1.7.2 Evaluation of PBtree Construction......Page 45
1.7.3.1 Prefix Query Evaluation......Page 46
1.7.3.2 Range Query Evaluation......Page 47
1.7.4.1 Average Time of Updating......Page 48
References......Page 50
2.1.1 Motivation and Problem Statement......Page 53
2.1.3 Security Model......Page 54
2.1.4 Limitation of Prior Art......Page 55
2.1.5 Proposed Approach......Page 56
2.2 Related Work......Page 57
2.3.1 Index Element Encoding......Page 58
2.3.2 IBF Construction......Page 59
2.3.3 IBtree Construction......Page 60
2.3.4 Trapdoor Computation......Page 61
2.3.5 Query Processing......Page 63
2.4.1 IBtree Traversal Width Minimization......Page 64
2.4.2 IBtree Traversal Depth Minimization......Page 67
2.4.3 IBtree Compression......Page 69
2.5 Security Analysis......Page 72
2.6.1 Experimental Methodology......Page 74
2.6.2 Index Size......Page 76
2.6.3 Index Construction Time......Page 77
2.6.4 Query Processing Time......Page 78
2.6.5 Compared with PBtree and KRB......Page 79
References......Page 81
3.1 Introduction......Page 84
3.2 Insecurity of ASPE......Page 85
3.2.2 Attack Method......Page 86
3.2.3 Experimental Results......Page 88
3.3 Hardness Analysis......Page 90
3.4 Conclusions......Page 91
References......Page 92
4.1.1 Motivations......Page 94
4.1.3 Service Model and Design Goals......Page 95
4.1.4 Comparison with Prior Arts......Page 97
4.1.5 Technical Challenges and Proposed Solutions......Page 98
4.1.7 Main Contributions......Page 99
4.2.1 Projection Function Introduction......Page 100
4.2.2 Space Encoding via a Single Primitive Projection Function......Page 101
4.2.3 Projection Function Composition Introduction......Page 102
4.2.4 Space Encoding via Projection Function Composition......Page 103
4.3.1 kNN Protocol Design......Page 105
4.3.2 Analysis of kNN Protocol Parameters......Page 107
4.4.1 Prefix-Free Encoding......Page 110
4.4.3 Indistinguishable Bloom Filter Tree Based Secure Index......Page 111
4.4.4 SkNN Protocol (SecEQP) Design......Page 113
4.4.5 Security Analysis......Page 114
4.5.2 Datasets, Metrics, and Implementation......Page 116
4.5.3 Experiment Results......Page 117
4.5.4 Improve Result Accuracy......Page 119
References......Page 122
5.1.1 Motivation......Page 124
5.1.2 Problem Statement......Page 125
5.1.4 Limitations of Prior Art......Page 126
5.1.5 Technical Challenges and Proposed Approach......Page 127
5.2 Related Work......Page 128
5.3 System Model and Assumptions......Page 129
5.4.1 Approximating Uniform Distribution......Page 130
5.4.2 Data Partitioning for Integrity Verification......Page 132
5.4.3 Embedding Intervals with Data......Page 133
5.5.1 Prefix Encoding and Bloom Filter Indexing......Page 134
5.5.2 Randomizing Bloom Filter Indexes......Page 135
5.6.1 Top-k to Top-Range Query......Page 137
5.6.3 Query Execution......Page 139
5.6.5 False Positive Rate Analysis......Page 140
5.7 Security Analysis......Page 141
5.8.1 Experimental Setup......Page 144
5.8.2 Summary for Experimental Results......Page 145
5.8.3 Comparison with Prior Art......Page 146
References......Page 148
Part II Privacy Preserving Computation......Page 151
6.1.1 Background and Motivation......Page 152
6.1.2 Technical Challenges......Page 153
6.1.4 Our Solution......Page 154
6.3 Background......Page 155
6.4 Oblivious Comparison......Page 156
6.5.1 FDD Construction......Page 159
6.5.3 Prefix Numericalization......Page 161
6.5.5 Applying XOR and HMAC by IBM......Page 162
6.6 Filtering Protocol......Page 163
6.6.2 Prefix Membership Verification......Page 164
6.6.3 Packet Preprocessing by IBM......Page 165
6.6.5 Packet Processing by MSU......Page 166
6.7.1 The Bootstrapping Protocol......Page 167
6.7.2 The Filtering Protocol......Page 168
6.8.2 Decision Caching......Page 170
6.8.4 Special Treatment of IP Addresses......Page 171
6.8.5 Securing Keys of MSU......Page 172
6.8.6 Stateful Firewalls......Page 173
6.8.8 Hash Collision......Page 174
6.9.1 Secure Function Evaluation......Page 175
6.9.2 CDCF Framework......Page 176
6.9.3 Secure Queries......Page 177
6.10.1 Efficiency on Real-Life Firewall Policies......Page 178
6.10.2 Efficiency on Synthetic Firewall Policies......Page 180
References......Page 182
7.1.1 Background and Motivation......Page 184
7.1.2 Limitation of Prior Art......Page 185
7.1.3 Cross-Domain Quantification of Reachability......Page 186
7.1.4 Technical Challenges......Page 187
7.1.5 Our Approach......Page 188
7.2.1 Network Reachability......Page 189
7.2.3 Privacy Preserving Collaborative Firewall Enforcement in VPN......Page 191
7.3.2 Problem Statement......Page 192
7.3.3 Threat Model......Page 193
7.4.1 Privacy-Preserving Range Intersection......Page 194
7.4.1.5 [Pi, Pj]: Private Set Intersection......Page 195
7.4.2 ACL Preprocessing......Page 196
7.4.3.1 Encoding and Encryption of ACL Aj (1≤j ≤n-1)......Page 198
7.4.4 ACL Comparison......Page 200
7.5 Incremental Updates of ACLs......Page 202
7.5.2 Addition of Rules with Discard Decision......Page 203
7.6 Stateful Firewalls......Page 204
7.7.1 Security Analysis......Page 205
7.7.2 Complexity Analysis......Page 206
7.9 Experimental Results......Page 207
7.9.1 Efficiency on Real ACLs......Page 208
7.9.2 Efficiency on Synthetic ACLs......Page 209
7.9.3 Efficiency of Incremental Updates of ACLs......Page 211
7.10 Conclusions......Page 212
References......Page 213
8.1.1 Background and Motivation......Page 215
8.1.3 Cross-Domain Inter-Firewall Optimization......Page 216
8.1.4 Technical Challenges and Our Approach......Page 217
8.1.5 Key Contributions......Page 218
8.3.1 System Model......Page 219
8.3.2 Threat Model......Page 220
8.4.1 Privacy-Preserving Range Comparison......Page 221
8.4.2 Processing Firewall FW1......Page 222
8.4.3 Processing Firewall FW2......Page 225
8.4.4 Single-Rule Coverage Redundancy Detection......Page 227
8.4.5 Multi-Rule Coverage Redundancy Detection......Page 228
8.4.6 Identification and Removal of Redundant Rules......Page 231
8.5 Firewall Update After Optimization......Page 232
8.6.1 Security Analysis......Page 233
8.6.2 Complexity Analysis......Page 234
8.7.2 Methodology......Page 235
8.7.3 Effectiveness and Efficiency on Real Policies......Page 236
8.7.4 Efficiency on Synthetic Policies......Page 238
8.8 Conclusions and Future Work......Page 240
References......Page 241
9.1.1 Motivation......Page 243
9.1.3 Adversary and Security Model......Page 244
9.1.5 Proposed Approach......Page 245
9.1.7 Key Contributions......Page 246
9.3 Pattern Aware Secure Search Tree......Page 247
9.3.2 PASStree Structure......Page 248
9.3.3 Preserving Privacy of Bloom Filters......Page 250
9.3.4 Query Trapdoor Generation and Processing......Page 251
9.4.2 Optimizing PASStree......Page 252
9.5.1 Recording Matching Positions......Page 254
9.6.1 Security Model......Page 255
9.6.2 Security Proof......Page 256
9.7.1.1 Data Sets......Page 258
9.7.1.3 Query Types......Page 259
9.7.2 PASStree Construction and Size......Page 260
9.7.4 Ranking Precision......Page 261
References......Page 262
10.1.1 Background and Motivation......Page 264
10.1.3 Proposed Solution......Page 265
10.1.5 Key Contributions......Page 267
10.2 Related Work......Page 268
10.3.1 Eigenvector Centrality......Page 269
10.3.3 Definition of PCC......Page 270
10.3.4 Generalized PCC......Page 271
10.3.6 Decentralized Eigendecomposition Algorithm......Page 274
10.4.1.1 Facebook A and Facebook B......Page 276
10.4.1.2 Twitter......Page 277
10.4.3 Comparison with Ground Truth......Page 279
10.4.3.1 Verification of Optimal PCC Parameter......Page 280
10.4.3.2 Accuracy of PCC in Predicting Top-2000 Users......Page 282
10.4.3.3 Accuracy of PCC in Predicting Top-k Users......Page 283
10.4.3.4 Accuracy of PCC in Rank Prediction......Page 284
References......Page 285
Part III Differential Privacy......Page 288
11.1.1 Background and Motivation......Page 289
11.1.3 Limitations of Prior Art......Page 290
11.1.5 Technical Challenges......Page 291
11.1.6 Key Contributions......Page 292
11.2.2 Differential Privacy in Data Publishing......Page 293
11.3 Random Matrix Approach......Page 294
11.3.1 Theoretical Guarantee on Differential Privacy......Page 296
11.3.2 Theoretical Guarantee on Eigenvector Approximation......Page 299
11.4 Experimental Results......Page 302
11.4.2 Node Clustering......Page 303
11.4.3 Node Ranking......Page 310
11.5 Utility Comparison......Page 313
References......Page 318
12.1 Introduction......Page 322
12.2 Related Work......Page 323
12.3.1 Threat Model......Page 324
12.4.1.1 Overview of the System Model......Page 325
12.4.1.3 Sensitivity......Page 326
12.4.2 The Basic Laplacian Mechanism......Page 327
12.4.3.2 Enhanced Feature #2: Trend Protection......Page 329
12.4.3.4 Privacy Analysis of Salus Algorithm......Page 330
12.5.1 Data Reconstruction Error: A Quantitative Analysis......Page 331
12.5.2 Data Reconstruction Error: A Lower Bound......Page 334
12.6.1 Average (AVG)......Page 337
12.6.2 Histogram (HIST)......Page 340
12.6.3 Classifiers (CLS)......Page 342
12.7 The P3 Framework for Predictable Privacy-Preserving MCS......Page 346
12.8 Performance Evaluation......Page 347
12.8.2 System Overhead......Page 348
12.8.3.1 Community Health Survey......Page 349
12.8.3.2 Collaborative Emotion Classification......Page 351
References......Page 353
13.1 Introduction......Page 356
13.1.2 Proposed Approach......Page 358
13.1.3 Advantages over Prior Art......Page 359
13.2.1 MAB Algorithms Without Budgets......Page 360
13.2.2 MAB Algorithms with Budgets......Page 361
13.3 Problem Statement......Page 362
13.3.2 DP-Aware BMAB Over Matroids......Page 363
13.3.3 An Example in Crowdsourcing......Page 364
13.4 Bounding the Optimal Policy......Page 365
13.5 Algorithm Design......Page 366
13.5.2 The OPBM Algorithm......Page 367
13.6 Regret Analysis......Page 373
13.7.1 Experimental Setup......Page 376
13.7.3 Regret Performance......Page 377
13.7.4 Time Efficiency......Page 379
Appendix: Missing Definitions, Lemmas and Proofs......Page 380
Proof of Lemma 13.1......Page 381
Proof of Theorem 13.1......Page 382
Proof of Lemma 13.8......Page 383
Proof of Lemma 13.10......Page 384
Proof of Lemma 13.11......Page 386
Proof of Theorem 13.4......Page 387
Proof of Theorem 13.5......Page 388
References......Page 390
Part IV Breaking Privacy......Page 392
14.1 Introduction......Page 393
14.2.1 Mix Network De-anonymization......Page 395
14.3.1 IM Service Architecture......Page 396
14.4 COLD: COmmunication Link De-anonymization......Page 398
14.4.1 Architecture......Page 399
14.4.2.2 Choosing the Optimal Number of Decomposition Levels......Page 400
14.4.2.4 Correlation......Page 401
14.4.3 Example......Page 402
14.5 Experimental Results......Page 403
14.5.1.2 Ground Truth Data......Page 404
14.5.3 Results......Page 406
14.5.4 Discussions......Page 408
14.6 Evasion and Countermeasures......Page 410
References......Page 411