Secure and Privacy-Preserving Distributed Data Release Open Access

Abstract

The rapidly increasing prevalence of distributed data-driven applications highlights security and privacy issues in storing and processing sensitive data. Although manipulating raw data may violate privacy of their owners, techniques for processing and using privacy-preserving data descriptions can help. It remains a challenge, however, to ensure that adapted and new solutions are efficient, secure, and preserve privacy of data owners without disclosing confidentiality of data providers.

This dissertation proposes a new notion of m-privacy that addresses situations in which data providers may act as adversaries. To verify if such adversaries are capable of breaching privacy, we introduce novel strategies and an adaptive algorithm to select and use the most efficient approach. In addition, we design an algorithm to anonymize data to be m-private, i.e., any m colluding parties cannot compromise privacy. All verification and anonymization algorithms are implemented to be run in distributed environments by a trusted third party.

For settings without a trusted third party, we introduce new secure multiparty computation protocols that implement m-privacy verification and anonymization algorithms. For each protocol, we prove its security, analyze its communication complexity, and evaluate its overall performance for various settings.

This dissertation also describes a new two-phase algorithm to release differentially private histograms for records with customized privacy levels. We adapt a v-optimal partitioning algorithm to make it usable with differential privacy, and experimentally evaluate its performance.

Finally, for settings without a trusted third party, this dissertation presents a new distributed differential privacy mechanism that achieves collusion resistance with small overhead. We also define an enhanced fault tolerant and secure scheme for multiparty aggregation operations, and we employ it to implement our differential privacy mechanism in distributed environments. Both the privacy mechanism and the fault tolerant scheme are extensively analyzed and experimentally evaluated.

Table of Contents

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Application Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Syntactic Privacy Notions in Distributed Environments . . . . . . 8
1.2.2 Semantic Privacy Notions (Differential Privacy) in Distributed Environments 11
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Related Work 14
2.1 Data Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Syntactical Privacy Notions . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Security of Computations . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Secure Multiparty Computations . . . . . . . . . . . . . . . . . . . . 16

2.2.2 Secret Sharing Schemes . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Encryption Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Secure Multiparty Computations with Differential Privacy . . . . . 18
2.4 Secure Multiparty Data Statistics with Differential Privacy . . . . 19
3 Distributed Data Aggregation with m-Privacy 20
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 m-Privacy Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 m-Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.2 Monotonicity of Privacy Constraints . . . . . . . . . . . . . . . . . . 25
3.3 m-Privacy Verication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.1 Adversary Space Enumeration . . . . . . . . . . . . . . . . . . . . . . 29
3.3.2 Heuristic Algorithms for EG Monotonic Constraints . . . . . . . . . 30
3.3.3 m-Privacy Verication Algorithm for Non-EG Monotonic Constraints 35
3.3.4 The Worst-Case Time Complexity . . . . . . . . . . . . . . . . . . . . 36
3.3.5 The Average Time Complexity . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Anonymization for m-Privacy . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.2 m-Privacy Verication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.5.3 m-Privacy Anonymization . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5.4 m-Privacy Verication Experiments for non-EG Monotonic Constraints 55
3.5.5 m-Privacy Anonymization Experiments for non-EG Monotonic Constraints 56
4 Secure Multiparty Data Aggregation with m-Privacy 61
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Secure Privacy Constraint Verication Protocols . . . . . . . . . . . . 62
4.2.1 Secure k-Anonymity Verication . . . . . . . . . . . . . . . . . . . . . 62
4.2.2 Secure l-Diversity Verication . . . . . . . . . . . . . . . . . . . . . . . 63
4.3 Secure m-Privacy Verication Protocols . . . . . . . . . . . . . . . . . 65

4.3.1 Secure Leader Election Protocol . . . . . . . . . . . . . . . . . . . . . 66
4.3.2 Secure Sorting and Adaptive Ordering . . . . . . . . . . . . . . . . . 67
4.3.3 Secure m-Privacy Verication Protocol . . . . . . . . . . . . . . . . . 68
4.4 Secure m-Privacy Anonymization Protocols . . . . . . . . . . . . . . . 71
4.4.1 Secure Provider-aware Anonymization Protocol . . . . . . . . . . . 71
4.4.2 Secure Fitness Score Protocol . . . . . . . . . . . . . . . . . . . . . . 74
4.5 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.5.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.5.2 Secure m-Privacy Verication . . . . . . . . . . . . . . . . . . . . . . . 77
4.5.3 Secure m-Privacy Anonymization . . . . . . . . . . . . . . . . . . . . 78
5 Distributed Data Aggregation with Customized Differential Privacy 80
5.1 Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.1.1 Query Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.1.2 m-Privacy and Differential Privacy . . . . . . . . . . . . . . . . . . . . 81
5.2 Customized Privacy Budget . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3 Differentially Private Histograms . . . . . . . . . . . . . . . . . . . . . . . 83
5.3.1 Data-driven Histograms . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.3.2 Privacy- and Data- Driven Histograms . . . . . . . . . . . . . . . . . . 85
5.3.3 Strategies of Spending Privacy Budgets . . . . . . . . . . . . . . . . . 88
5.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.4.1 Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.4.2 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.4.3 Partitioning Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.4 Histogram Building Approaches . . . . . . . . . . . . . . . . . . . . . . . 95
6 Secure Multiparty Data Aggregation with Customized Differential Privacy 96
6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.2 Distributed Differential Privacy Mechanisms . . . . . . . . . . . . . . . . 99
6.2.1 Distributed Laplace Mechanism . . . . . . . . . . . . . . . . . . . . . . . 99

6.2.2 Geometric Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.2.3 Distributed Noise Approximation Mechanisms . . . . . . . . . . . . . . 105
6.2.4 Diluted Distributed Mechanisms . . . . . . . . . . . . . . . . . . . . . . . 106
6.2.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.3 Security Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3.1 Secret Sharing Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3.2 Perturbation-Based Protocols . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.3 Homomorphic Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3.4 Enhanced Fault Tolerant Scheme . . . . . . . . . . . . . . . . . . . . . 113
6.3.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.4.1 Experiments Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.4.2 Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.4.3 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7 Conclusions and Future Work 128
7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.1.1 Syntactic Privacy Notions in Distributed Environments . . . . . . . . 128
7.1.2 Semantic Privacy Notions in Distributed Environments . . . . . . . . 129
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
Books and Journals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Electronic Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Computer Science
Keyword	Privacy-preserving Computations Secure Multiparty Computations Distributed Data Anonymization Customized Differential Privacy Distributed Differential Privacy m-Privacy Secure Multiparty Protocols
Committee Chair / Thesis Advisor	Xiong, Li, Emory University
Committee Members	Fung, Benjamin C. M., McGill University Sunderam, Vaidy S, Emory University Cheung, Shun, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Secure and Privacy-Preserving Distributed Data Release ()	2018-08-28 15:08:12 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions