PLDP: Personalized LDP for Collecting and Analyzing Multidimensional Data

doi:10.3778/j.issn.1673-9418.2107035

Abstract

Abstract: The popularity of crowdsourcing applications accelerates the development of enterprises, and the privacy leakage has become the focus of public attention. The existing local differential privacy (LDP) mechanism mainly focuses on the utility optimization of a single privacy level, which will cause some users to refuse to share data due to insufficient privacy protection level, while some users get too much privacy protection. In order to meet different privacy protection needs of users, this paper proposes a personalized local differential privacy (PLDP) mechanism for collecting and analyzing multi-dimensional mixed data, which provides multiple privacy protection levels for users. Specifically, this paper proposes a personalized user data perturbation framework, which implements perso-nalized mean estimation algorithm and frequency estimation algorithm for numerical data and classified data respectively, and proves the confidentiality and effectiveness of the algorithm through theoretical analysis. In addition, a personalized sampling scheme is proposed, which preprocesses the attribute tags according to preferences of the server, and biases the data dimensions according to their collection preferences. Experiments on two real datasets show that, compared with traditional LDP mechanism, the proposed mechanism not only guarantees the privacy of user data, but also reduces the statistical error of collecting numerical data and classified data, so it pro-vides a better balance between privacy protection and data availability.

Key words: local differential privacy (LDP), personalized local differential privacy (PLDP), numerical data;classified data, crowdsourcing

摘要： 众包应用的普及加速了企业的发展，随之而来的隐私泄露问题已经成为公众关注的焦点。现有的本地化差分隐私（LDP）机制主要关注单个隐私级别的效用优化，这会导致某些用户因提供的隐私保护级别不足拒绝共享数据，而某些用户则获得过多的隐私保护。为满足用户不同的隐私保护需求，针对收集和分析多维混合型数据提出一种个性化本地差分隐私（PLDP）机制，为用户提供多个隐私保护级别。具体来说，提出一个个性化用户数据扰动框架，该框架针对数值型数据和分类型数据分别执行个性化的均值估计算法和频率估计算法，并通过理论分析证明算法的保密性和有效性。另外，提出一个个性化的采样方案，该方案根据服务器端的偏好对属性标签进行预处理，并按照其收集偏好对数据维度进行有偏采样。在两个真实数据集上的实验表明，与传统的LDP机制相比，提出的机制在保证用户数据隐私的同时，降低了收集数值型数据和分类型数据的统计误差，因此在隐私保护和数据可用性之间提供了更好的平衡。

关键词: 本地化差分隐私（LDP）, 个性化本地差分隐私（PLDP）, 数值型数据, 分类型数据, 众包

GU Xiang, LI Yanhui, YUAN Ye, LI Xinling, WANG Guoren. PLDP: Personalized LDP for Collecting and Analyzing Multidimensional Data[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(4): 964-972.

谷香, 李艳辉, 袁野, 李新玲, 王国仁. PLDP：收集和分析多维数据的个性化LDP[J]. 计算机科学与探索, 2023, 17(4): 964-972.

References

[1] LI X, ZHAO Y, ZHOU X F, et al. Consensus-based group task assignment with social impact in spatial crowdsourcing[J]. Data Science and Engineering, 2020, 5(4): 375-390.
[2] CUI L Z, CHEN J, HE W, et al. Achieving approximate glo-bal optimization of truth inference for crowdsourcing micro-tasks[J]. Data Science and Engineering, 2021, 6(3): 294-309.
[3] YUAN H T, LI G L. A survey of traffic prediction: from spatio-temporal data to intelligent transportation[J]. Data Science and Engineering, 2021, 6(1): 63-85.
[4] DUCHI J C, JORDAN M I, WAINWRIGHT M J. Local privacy and statistical minimax rates[C]//Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, Berkeley, Oct 26-29, 2013. Piscataway: IEEE, 2013: 429-438.
[5] TAKURTAA G, VYRROS A H, VAISHAMPAYAN U S, et al. Emoji frequency detection and deep link frequency:US20190068628[P/OL]. (2017-02-28)[2021-06-12]. https://www.freepatet-sonline.com/y2019/0068628.html.
[6] DING B, KULKARNI J, YEKHANIN S. Collecting telemetry data privately[C]//Proceedings of the Annual Conference on Neural Information Processing Systems 2017, Long Beach, Dec 4-9, 2017. Red Hook: Curran Associates, 2017: 3571-3580.
[7] YE Q Q, HU H B, MENG X F, et al. PrivKV: key-value data collection with local differential privacy[C]//Procee-dings of the 2019 IEEE Symposium on Security and Privacy, San Francisco, May 19-23, 2019. Piscataway: IEEE, 2019: 317-331.
[8] WANG T H, LI N H, JHA S. Locally differentially private frequent itemset mining[C]//Proceedings of the 2018 IEEE Symposium on Security and Privacy, San Francisco, May 21-23, 2018. Washington: IEEE Computer Society, 2018: 127-143.
[9] CHEN R, LI H R, QIN A K, et al. Private spatial data aggre-gation in the local setting[C]//Proceedings of the 32nd IEEE International Conference on Data Engineering, Helsinki, May 16-20, 2016. Washington: IEEE Computer Society, 2016: 289-300.
[10] WANG S W, HUANG L S, TIAN M M, et al. Personalized privacy-preserving data aggregation for histogram estima-tion[C]//Proceedings of the 2015 IEEE Global Communi-cations Conference, San Diego, Dec 6-10, 2015. Piscataway: IEEE, 2015: 1-6.
[11] NIE Y W, YANG W, HUANG L S, et al. A utility-optimized framework for personalized private histogram estimation[J].IEEE Transactions on Knowledge and Data Engineering, 2019, 31(4): 655-669.
[12] SHEN Z X, XIA Z H, YU P P. PLDP: personalized local differential privacy for multidimensional data aggregation[J]. Security and Communication Networks, 2021, 4: 1-13.
[13] DWORK C. Differential privacy[C]//LNCS 4052: Proceedings of the 33rd International Colloquium on Automata, Langua-ges and Programming, Venice, Jul 10-14, 2006. Berlin, Hei-delberg: Springer, 2006: 1-12.
[14] KASIVISWANATHAN S P, LEE H K, NISSIM K, et al. What can we learn privately?[C]//Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Oct 25-28, 2008. Washington: IEEE Computer Society, 2008: 531-540.
[15] WARNER S L. Randomized response: a survey technique for eliminating evasive answer bias[J]. Journal of the Ame-rican Statistical Association, 1965, 60(309): 63-69.
[16] ERLINGSSON ú, PIHUR V, KOROLOVA A. RAPPOR: ran-domized aggregatable privacy-preserving ordinal response[C]//Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, Nov 3-7, 2014. New York: ACM, 2014: 1054-1067.
[17] WANG T H, BLOCKI J, LI N H, et al. Locally differen-tially private protocols for frequency estimation[C]//Procee-dings of the 26th USENIX Security Symposium, Vancouver, Aug 16-18, 2017. Berkeley: USENIX Association, 2017: 729-745.
[18] BASSILY R, SMITH A D. Local, private, efficient protocols for succinct histograms[C]//Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, Portland, Jun 14-17, 2015. New York: ACM, 2015: 127-135.
[19] DWORK C, McSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]//LNCS 3876: Proceedings of the 3rd Conference on Theory of Crypto-graphy, New York, Mar 4-7, 2006. Berlin, Heidelberg: Sprin-ger, 2006: 265-284.
[20] DUCHI J C, JORDANM I, WAINWRIGHTM J. Minimax optimal procedures for locally private estimation[J]. Journal of the American Statistical Association, 2018, 113(521): 182-201.
[21] WANG N, XIAO X K, YANG Y, et al. Collecting and analy-zing multidimensional data with local differential privacy[C]//Proceedings of the 35th IEEE International Conference on Data Engineering, Macao, China, Apr 8-11, 2019. Piscata-way: IEEE, 2019: 638-649.