Efficient estimation of statistical functions while preserving client-side privacy

Preview

PDF WRAP_Theses_Kulkarni_2019.pdf - Submitted Version - Requires a PDF viewer. Download (4MB) | Preview

Request Changes to record.

Abstract

Aggregating service users’ personal data for analytical purposes is a common practice in today’s Internet economy. However, distrust in the data aggregator, data breaches and risks of subpoenas pose significant challenges in the availability of data. The framework of differential privacy is enjoying wide attention due to its scalability and rigour of privacy protection it provides, and has become a de facto standard for facilitating privacy preserving information extraction. In this dissertation, we design and implement resource efficient algorithms for three fundamental data analysis primitives, marginal, range, and count queries while providing strong differential privacy guarantees.

The first two queries are studied in the strict scenario of untrusted aggregation (aka local model) in which the data collector is allowed to only access the noisy/perturbed version of users’ data but not their true data. To the best of our knowledge, marginal and range queries have not been studied in detail in the local setting before our works. We show that our simple data transfomation techniques help us achieve great accuracy in practice and can be used for performing more interesting analysis.

Finally, we revisit the problem of count queries under trusted aggregation. This setting can also be viewed as a relaxation of the local model called limited precision local differential privacy. We first discover certain weakness in a well-known optimization framework leading to solutions exhibiting pathological behaviours. We then propose more constraints in the framework to remove these weaknesses without compromising too much on utility.

Request changes or add full text files to a record

Repository staff actions (login required)

View Item