Proceedings of the VLDB Endowment · 2013 · 100 citations · 25 references
ComputingData ScienceData AnalyticsData MiningStatisticsData AnonymizationData PrivacyData ProtectionDifferential PrivacyPrivacy ProtectionPrivacy-preserving AnalyticsDifferentially Private StatisticsNoise InjectionSampling
We address one-time publishing of non-overlapping counts with ε-differential privacy. These statistics are useful in a wide and important range of applications, including transactional, traffic and medical data analysis. Prior work on the topic publishes such statistics with prohibitively low utility in several practical scenarios. Towards this end, we present GS, a method that pre-processes the counts by elaborately grouping and smoothing them via averaging. This step acts as a form of preliminary perturbation that diminishes sensitivity, and enables GS to achieve ε-differential privacy through low Laplace noise injection. The grouping strategy is dictated by a sampling mechanism, which minimizes the smoothing perturbation. We demonstrate the superiority of GS over its competitors, and confirm its practicality, via extensive experiments on real datasets.
25
Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke et al. · ACM Transactions on Knowledge Discovery from Data · 2007 · 3.6K citations
Towards Sharp Inapproximability For Any 2-CSP
Per Austrin · 2007 · 1.4K citations
Smooth sensitivity and sampling in private data analysis
Kobbi Nissim, Sofya Raskhodnikova, Adam Smith · 2007 · 1K citations
A firm foundation for private data analysis
Cynthia Dwork · Communications of the ACM · 2010 · 858 citations