Abstract
Local differential privacy (LDP) has received much interest recently. In existing protocols with LDP guarantees, a user encodes and perturbs his data locally before sharing it to the aggregator. In common practice, however, users would prefer not to answer all the questions due to different privacy-preserving preferences for some questions, which leads to data missing or the loss of data quality. In this paper, we demonstrate a new approach for addressing the challenges of data perturbation with consideration of users’ privacy preferences. Specifically, we first propose BiSample: a bidirectional sampling technique value perturbation in the framework of LDP. Then we combine the BiSample mechanism with users’ privacy preferences for missing data perturbation. Theoretical analysis and experiments on a set of datasets confirm the effectiveness of the proposed mechanisms.
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
Similar content being viewed by others
References
Bassily, R., Nissim, K., Stemmer, U., Thakurta, A.G.: Practical locally private heavy hitters. In: Advances in Neural Information Processing Systems, pp. 2288–2296 (2017)
Bassily, R., Smith, A.: Local, private, efficient protocols for succinct histograms. In: Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, pp. 127–135. ACM (2015)
Cormode, G., Kulkarni, T., Srivastava, D.: Marginal release under local differential privacy. In: Proceedings of the 2018 International Conference on Management of Data, pp. 131–146. ACM (2018)
Ding, B., Kulkarni, J., Yekhanin, S.: Collecting telemetry data privately. In: Advances in Neural Information Processing Systems, pp. 3571–3580 (2017)
Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Local privacy and statistical minimax rates. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 429–438. IEEE (2013)
Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Privacy aware learning. J. ACM (JACM) 61(6), 38 (2014)
Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Minimax optimal procedures for locally private estimation. J. Am. Stat. Assoc. 113(521), 182–201 (2018)
Dwork, C., Roth, A., et al.: The algorithmic foundations of differential privacy. Found. Trends® Theoret. Comput. Sci. 9(3–4), 211–407 (2014)
Erlingsson, Ú., Pihur, V., Korolova, A.: Rappor: randomized aggregatable privacy-preserving ordinal response. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 1054–1067. ACM (2014)
Kairouz, P., Oh, S., Viswanath, P.: Extremal mechanisms for local differential privacy. In: Advances in Neural Information Processing Systems, pp. 2879–2887 (2014)
Kohavi, R., Becker, B.: UCI repository of machine learning databases: Adult data set (1999). https://archive.ics.uci.edu/ml/datasets/Adult
Li, N., Li, T., Venkatasubramanian, S.: t-closeness: Privacy beyond k-anonymity and l-diversity. In: 2007 IEEE 23rd International Conference on Data Engineering, pp. 106–115. IEEE (2007)
Nguyên, T.T., Xiao, X., Yang, Y., Hui, S.C., Shin, H., Shin, J.: Collecting and analyzing data from smart device users with local differential privacy. arXiv preprint arXiv:1606.05053 (2016)
Qin, Z., Yang, Y., Yu, T., Khalil, I., Xiao, X., Ren, K.: Heavy hitter estimation over set-valued data with local differential privacy. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 192–203. ACM (2016)
Ren, X., et al.: LoPub: high-dimensional crowdsourced data publication with local differential privacy. IEEE Trans. Inf. Forensics Secur. 13(9), 2151–2166 (2018)
Samarati, P., Sweeney, L.: Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Technical report, SRI International (1998)
Wang, N., et al.: Collecting and analyzing multidimensional data with local differential privacy. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 638–649. IEEE (2019)
Warner, S.L.: Randomized response: a survey technique for eliminating evasive answer bias. J. Am. Stat. Assoc. 60(309), 63–69 (1965). https://doi.org/10.1080/01621459.1965.10480775. http://www.tandfonline.com/doi/abs/10.1080/01621459.1965.10480775
Ye, Q., Hu, H., Meng, X., Zheng, H.: PrivKV: key-value data collection with local differential privacy. In: IEEE Symposium on Security and Privacy (SP), May 2019
Acknowledgements
This work is supported by National Key Research and Development Program of China (No. 2019QY1402/2016YFB0800901). Jun Zhao’s research was supported by Nanyang Technological University (NTU) Startup Grant M4082311.020, Alibaba-NTU Singapore Joint Research Institute (JRI) M4062640. J4I, Singapore Ministry of Education Academic Research Fund Tier 1 RG128/18, RG115/19, and Tier 2 MOE2019-T2-1-176, and NTU-WASP Joint Project M4082443.020.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Sun, L., Ye, X., Zhao, J., Lu, C., Yang, M. (2020). BiSample: Bidirectional Sampling for Handling Missing Data with Local Differential Privacy. In: Nah, Y., Cui, B., Lee, SW., Yu, J.X., Moon, YS., Whang, S.E. (eds) Database Systems for Advanced Applications. DASFAA 2020. Lecture Notes in Computer Science(), vol 12112. Springer, Cham. https://doi.org/10.1007/978-3-030-59410-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-59410-7_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59409-1
Online ISBN: 978-3-030-59410-7
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)