Paper 2012/456

Crowd-Blending Privacy

Johannes Gehrke, Michael Hay, Edward Lui, and Rafael Pass


We introduce a new definition of privacy called \emph{crowd-blending privacy} that strictly relaxes the notion of differential privacy. Roughly speaking, $k$-crowd blending private sanitization of a database requires that each individual $i$ in the database ``blends'' with $k$ other individuals $j$ in the database, in the sense that the output of the sanitizer is ``indistinguishable'' if $i$'s data is replaced by $j$'s. 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.

Note: This is the full version of the paper "Crowd-Blending Privacy".

Available format(s)
Publication info
Published elsewhere. CRYPTO 2012
Contact author(s)
luied @ cs cornell edu
2012-08-13: received
Short URL
Creative Commons Attribution


      author = {Johannes Gehrke and Michael Hay and Edward Lui and Rafael Pass},
      title = {Crowd-Blending Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2012/456},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.