U.S. flag

An official website of the United States government

Skip Header


An Uncertainty Principle is a Price of Privacy-Preserving Microdata

Written by:
Working Paper Number ced-wp-2021-008

Abstract

Privacy-protected microdata are often the desired output of a differentially private algorithm since microdata is familiar and convenient for downstream users. However, there is a statistical price for this kind of convenience. We show that an uncertainty principle governs the trade-off between accuracy for a population of interest (“sum query”) vs. accuracy for its component sub-populations (“point queries”). Compared to differentially private query answering systems that are not required to produce microdata, accuracy can degrade by a logarithmic factor. For example, in the case of pure differential privacy, without the microdata requirement, one can provide noisy answers to the sum query and all point queries while guaranteeing that each answer has squared error O(1/ε2). With the microdata requirement, one must choose between allowing an additional log2(d) factor (d is the number of point queries) for some point queries or allowing an extra O(d2) factor for the sum query. We present lower bounds for pure, approximate, and concentrated differential privacy. We propose mitigation strategies and create a collection of benchmark datasets that can be used for public study of this problem.

Page Last Revised - January 20, 2023
Is this page helpful?
Thumbs Up Image Yes Thumbs Down Image No
NO THANKS
255 characters maximum 255 characters maximum reached
Thank you for your feedback.
Comments or suggestions?

Top

Back to Header