Edward Lui
Abstract:
We survey two new definitions for data privacy: Zero-Knowledge Privacy and Crowd-Blending Privacy.
Zero-knowledge privacy is strictly stronger than differential privacy (the current standard notion of privacy) and is particularly attractive when modeling privacy in social networks. We demonstrate that zero-knowledge privacy can be meaningfully achieved for tasks such as computing averages, fractions, histograms, and a variety of graph parameters and properties, such as average degree and distance to connectivity.
Crowd-blending privacy strictly relaxes the notion of differential privacy, and is based on the notion of "blending in a crowd". We construct crowd-blending private mechanisms for releasing histograms and synthetic data points, achieving strictly better utility than what is possible using differentially private mechanisms. Additionally, we demonstrate that if a crowd-blending private mechanism is combined with a "pre-sampling" step, where the individuals in the database are randomly drawn from some underlying population (as is often the case during data collection), then the combined mechanism satisfies not only differential privacy, but also the stronger notion of zero-knowledge privacy. Taken together, our results yield a practical approach for collecting and privately releasing data while ensuring higher utility and stronger privacy than previous approaches.
Based on joint works with Johannes Gehrke, Michael Hay, and Rafael Pass.