An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors
This work addresses the problem of enabling practical and private data analysis for applications where users distrust data collectors, offering a solution that is less restrictive than local models but more secure than global models.
The paper tackles the limitations of local differential privacy in commercial systems by proposing a framework based on trusted processors and a new definition called Oblivious Differential Privacy, which combines the strengths of local and global models to enable private data analysis with reduced errors.
Differential privacy has emerged as the main definition for private data analysis and machine learning. The {\em global} model of differential privacy, which assumes that users trust the data collector, provides strong privacy guarantees and introduces small errors in the output. In contrast, applications of differential privacy in commercial systems by Apple, Google, and Microsoft, use the {\em local model}. Here, users do not trust the data collector, and hence randomize their data before sending it to the data collector. Unfortunately, local model is too strong for several important applications and hence is limited in its applicability. In this work, we propose a framework based on trusted processors and a new definition of differential privacy called {\em Oblivious Differential Privacy}, which combines the best of both local and global models. The algorithms we design in this framework show interesting interplay of ideas from the streaming algorithms, oblivious algorithms, and differential privacy.