Enhancing Local Differential Privacy Accuracy by Exploiting Inherent Uncertainty

Peng Tang; Xiya Shao; Rui Chen; Ning Wang; Shanqing Guo

doi:10.1145/3786647

journal article Apr 02, 2026

Enhancing Local Differential Privacy Accuracy by Exploiting Inherent Uncertainty

Peng Tang

Proceedings of the ACM on Management of Data Vol. 4 No. 1 pp. 1-26 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/3786647

Abstract

Local differential privacy (LDP) is a standard for privacy preservation in the local setting: classical LDP mechanisms protect directly sensitive attributes by injecting uncertainty between users' true values and reported data. In many deployments, however, practitioners also choose to perturb attributes that are not inherently sensitive but are correlated with latent sensitive ones, using LDP as a system-level choice to limit attribute-inference risks. When such correlated attributes are naively treated as fully sensitive, the resulting mechanisms may satisfy a given privacy requirement but inject more noise than necessary, causing utility loss. This raises the challenge of quantifying how much uncertainty correlations already provide about sensitive attributes and using this to optimize perturbation under fixed privacy constraints. We address this challenge via inherent uncertainty, a metric that captures correlation-induced uncertainty between collected non-sensitive attributes and associated sensitive attributes. We also introduce a correlation-aware LDP framework that exploits this metric to recalibrate perturbation parameters, while providing the same ε-LDP guarantee for sensitive attributes as a treat-as-sensitive baseline. We further consider a hybrid scenario in which a single collected attribute contains both sensitive values and non-sensitive-but-correlated values, and propose a dual-phase perturbation method that provides differentiated protection and improves utility. Our mechanisms satisfy ε-LDP and the specified inference guarantees, and experiments on real datasets demonstrate their utility gains. Code is available at https://github.com/null944/enhanced-accuracy-in-ldp.

Topics

No keywords indexed for this article. Browse by subject →

References

38

[1]

Jayadev Acharya, Kallista A. Bonawitz, Peter Kairouz, Daniel Ramage, and Ziteng Sun. 2020. Context Aware Local Differential Privacy. In ICML, Vol. 119. 52-62.

[2]

Miguel E. Andrés, Nicolás Emilio Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. 2013. Geo-indistinguishability: differential privacy for location-based systems. In CCS. 901-914.

[3]

Raef Bassily and Adam Smith. 2015. Local, private, efficient protocols for succinct histograms. In STOC. 127-135.

[4]

10.1007/978-3-030-17653-2_13

[5]

Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. 2018. Marginal Release Under Local Differential Privacy. In SIGMOD. 131-146.

[6]

Badi Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. In NeurIPS. 3305-3314.

[7]

Rong Du, Qingqing Ye, Yue Fu, and Haibo Hu. 2021. Collecting High-Dimensional and Correlation-Constrained Data with Local Differential Privacy. In SECON. 1-9.

[8]

Flávio du Pin Calmon and Nadia Fawaz. 2012. Privacy against statistical inference. In Allerton. 1401-1408.

[9]

Jiawei Duan, Qingqing Ye, and Haibo Hu. 2022. Utility Analysis and Enhancement of LDP Mechanisms in High-Dimensional Space. In ICDE. 407-419.

[10]

Minimax Optimal Procedures for Locally Private Estimation

John C. Duchi, Michael I. Jordan, Martin J. Wainwright

Journal of the American Statistical Association 10.1080/01621459.2017.1389735

[11]

Cynthia Dwork. 2006. Differential privacy. In ICALP. 1-12.

[12]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In TCC. 265-284.

[13]

Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. Rappor: Randomized aggregatable privacy-preserving ordinal response. In CCS. 1054-1067.

[14]

Xiaolan Gu, Ming Li, Li Xiong, and Yang Cao. 2020. Providing Input-Discriminative Protection for Local Differential Privacy. In ICDE. 505-516.

[15]

Mehmet Emre Gursoy, Acar Tamersoy, Stacey Truex, Wenqi Wei, and Ling Liu. 2021. Secure and Utility-Aware Data Collection with Condensed Local Differential Privacy. TDSC, Vol. 18, 5 (2021), 2365-2378.

[16]

Hsiang Hsu, Shahab Asoodeh, and Flávio P. Calmon. 2019. Information-Theoretic Privacy Watchdogs. In ISIT. 552-556.

[17]

10.1109/tdsc.2020.3041733

[18]

Peter Kairouz, Keith Bonawitz, and Daniel Ramage. 2016. Discrete distribution estimation under local privacy. In ICML. 2436-2444.

[19]

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2014. Extremal mechanisms for local differential privacy. In NeurIPS. 2879-2887.

[20]

10.1137/090756090

[21]

10.1145/2414456.2414474

[22]

Zitao Li, Tianhao Wang, Milan Lopuhaä-Zwakenberg, Ninghui Li, and Boris Skoric. 2020. Estimating Numerical Distributions under Local Differential Privacy. In SIGMOD. ACM, 621-635.

[23]

Milan Lopuhaä-Zwakenberg. 2020. The Privacy Funnel from the viewpoint of Local Differential Privacy. CoRR, Vol. abs/2002.01501 (2020).

[24]

Milan Lopuhaä-Zwakenberg, Haochen Tong, and Boris Skoric. 2020. Data Sanitisation Protocols for the Privacy Funnel with Differential Privacy Guarantees. CoRR, Vol. abs/2008.13151 (2020).

[25]

10.14778/3659437.3659455

[26]

Takao Murakami and Yusuke Kawamoto. 2019. Utility-Optimized Local Differential Privacy Mechanisms for Distribution Estimation. In USENIX. 1877-1894.

[27]

10.1109/tifs.2023.3289007

[28]

Xuebin Ren Liang Shi Weiren Yu Shusen Yang Cong Zhao and Zongben Xu. 2022. LDP-IDS: Local Differential Privacy for Infinite Data Streams. In SIGMOD Zachary G. Ives Angela Bonifati and Amr El Abbadi (Eds.). 1064-1077. 10.1145/3514221.3526190

[29]

10.1007/978-3-030-59410-7_6

[30]

Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, and Ge Yu. 2019. Collecting and Analyzing Multidimensional Data with Local Differential Privacy. In ICDE. 638-649.

[31]

Shaowei Wang, Yiwen Nie, Pengzhan Wang, Hongli Xu, Wei Yang, and Liusheng Huang. 2017c. Local private ordinal data distribution estimation. In INFOCOM. IEEE, 1-9.

[32]

Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017a. Locally differentially private protocols for frequency estimation. In USENIX Security. 729-745.

[33]

Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017b. Locally Differentially Private Protocols for Frequency Estimation. In USENIX. 729-745.

[34]

Tianhao Wang Milan Lopuhaä-Zwakenberg Zitao Li Boris Skoric and Ninghui Li. 2020. Locally Differentially Private Frequency Estimation with Consistency. In NDSS. 10.14722/ndss.2020.24157

[35]

10.1080/01621459.1965.10480775

[36]

Emre Yilmaz, Tianxi Ji, Erman Ayday, and Pan Li. 2022. Genomic Data Sharing under Dependent Local Differential Privacy. In CODASPY. 77-88.

[37]

10.3390/e25040679

[38]

Zhikun Zhang, Tianhao Wang, Ninghui Li, Shibo He, and Jiming Chen. 2018. CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy. In CCS. 212-229.

Metrics

0

Citations

38

References

Details

Published: Apr 02, 2026
Vol/Issue: 4(1)
Pages: 1-26

Authors

P

Peng Tang

School of Cyber Science and Technology, Shandong University, Qingdao, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, China, and Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, China

X

Xiya Shao

School of Cyber Science and Technology, Shandong University, Qingdao, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, China, and Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, China

R

Rui Chen

College of Computer Science and Technology, Harbin Engineering University, Harbin, China

N

Ning Wang

Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou, China

S

Shanqing Guo

School of Cyber Science and Technology, Shandong University, Qingdao, China, State Key Laboratory of Cryptography and Digital Economy Security, Shandong University, Qingdao, China, and Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, China

Funding

National Natural Science Foundation of China Award: No. 62372268

Shandong Provincial Natural Science Foundation Award: No. ZR2025MS1038

Key R&D Program of Shandong Province Award: No. 2024CXGC010114

Heilongjiang Key R&D Program of China under Grant Award: No. GA23A915

Cite This Article

Peng Tang, Xiya Shao, Rui Chen, et al. (2026). Enhancing Local Differential Privacy Accuracy by Exploiting Inherent Uncertainty. Proceedings of the ACM on Management of Data, 4(1), 1-26. https://doi.org/10.1145/3786647

Enhancing Local Differential Privacy Accuracy by Exploiting Inherent Uncertainty

You May Also Like