Abstract
Recent work showed the necessity of incorporating a user’s background knowledge to improve the accuracy of estimates from noisy responses of histogram queries. Various types of constraints (e.g., linear constraints, ordering constraints, and range constraints) may hold on the true (non-randomized) answers of histogram queries. So the idea was to apply the constraints over the noisy responses and find a new set of answers (called refinements) that are closest to the noisy responses and also satisfy known constraints. As a result, the refinements expect to boost the accuracy of final histogram query results. However, there is one key question: is the ratio of the distributions of the results after refinements from any two neighbor databases still bounded? In this paper, we introduce a new definition, ρ-differential privacy on refinement, to quantify the change of distributions of refinements. We focus on one representative refinement, the linear refinement with linear constraints and study the relationship between the classic ε-differential privacy ( on responses) and our ρ-differential privacy on refinement. We demonstrate the conditions when the ρ-differential privacy on refinement achieves the same ε-differential privacy. We argue privacy breaches could incur when the conditions do not meet.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating Noise to Sensitivity in Private Data Analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006)
Dwork, C.: A Firm Foundation for Private Data Analysis. Communications of the ACM (January 2011)
Hay, M., Rastogi, V., Miklau, G., Suciu, D.: Boosting the Accuracy of Differentially Private Histograms Through Consistency. Proceedings of the VLDB Endowment 3(1) (2010)
Xiao, X., Wang, G., Gehrke, J.: Differential Privacy via Wavelet Transforms. In: Proceedings of the 26th IEEE International Conference on Data Enginering, pp. 225–236. IEEE (2010)
Li, C., Hay, M., Rastogi, V., Miklau, G., McGregor, A.: Optimizing Linear Counting Queries Under Differential Privacy. In: Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems of Data, pp. 123–134. ACM (2010)
Dwork, C., Lei, J.: Differential Privacy and Robust Statistics. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 371–380. ACM (2009)
Hay, M., Li, C., Miklau, G., Jensen, D.: Accurate Estimation of the Degree Distribution of Private Networks. In: Proceedings of the 9th IEEE International Conference on Data Mining, pp. 169–178. IEEE (2009)
Martin, D., Kifer, D., Machanavajjhala, A., Gehrke, J., Halpern, J.: Worst-Case Background Knowledge for Privacy-Preserving Data Publishing. In: Proceedings of the 26th IEEE International Conference on Data Enginering. IEEE (2007)
Du, W., Teng, Z., Zhu, Z.: Privacy-MaxEnt: Integrating Background Knowledge in Privacy Quantification. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, ACM (2008)
Ganta, S., Kasiviswanathan, S., Smith, A.: Composition Attacks and Auxiliary Information in Data Privacy. In: Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 265–273. ACM (2008)
Kifer, D., Machanavajjhala, A.: No Free Lunch in Data Privacy. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 193–204. ACM (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ying, X., Wu, X., Wang, Y. (2013). On Linear Refinement of Differential Privacy-Preserving Query Answering. In: Pei, J., Tseng, V.S., Cao, L., Motoda, H., Xu, G. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2013. Lecture Notes in Computer Science(), vol 7819. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37456-2_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-37456-2_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37455-5
Online ISBN: 978-3-642-37456-2
eBook Packages: Computer ScienceComputer Science (R0)