We demonstrate crowd-blending private mechanisms for histograms and for releasing 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. This holds even if the pre-sampling is slightly biased and an adversary knows whether certain individuals were sampled or not. Taken together, our results yield a practical approach for collecting and privately releasing data while ensuring higher utility than previous approaches.
Category / Keywords: Publication Info: CRYPTO 2012 Date: received 12 Aug 2012 Contact author: luied at cs cornell edu Available format(s): PDF | BibTeX Citation Note: This is the full version of the paper "Crowd-Blending Privacy". Version: 20120813:150417 (All versions of this report) Short URL: ia.cr/2012/456 Discussion forum: Show discussion | Start new discussion