Traceable and Collision-Resilient Differential Privacy
Kai Zhang, Xin Yuan, Ruoxi Sun, Chaoqun Hong, Minhui Xue
Abstract
Differential Privacy (DP) is a preeminent technique for data privacy by introducing noise to sensitive information. However, traditional DP mechanisms excessively rely on third parties to ensure traceability, necessitating strong background assumptions that are frequently impractical in real-world scenarios. This reliance makes it difficult to preserve both privacy and traceability. To address these challenges, we propose a novel Traceable and Collision-Resilient Differential Privacy (TCRDP) mechanism. The TCRDP mechanism simultaneously publishes perturbed results and data fingerprints, retaining partial information from the original data in a collision-resilient manner to facilitate future verification. Moreover, the TCRDP mechanism integrates an innovative noise generation process, leveraging hash values and a customized Laplace-like distribution to produce noise. This strategy mitigates the risk of adversaries compromising privacy through enumeration and yields a more concentrated noise distribution with reduced variance. We evaluated the TCRDP mechanism using three datasets: ICUs, Diabetes, and RAHRD, across various query types. The experimental results demonstrated significant improvements in data utility, with the TCRDP mechanism achieving great reductions in Mean Absolute Error (MAE) and Mean Squared Error (MSE) compared to traditional mechanisms. The TCRDP mechanism also maintained lower Accuracy Loss (AL) across different privacy budgets and dataset sizes, highlighting its robustness and scalability. These findings underscore the potential of the TCRDP mechanism to advance privacy-preserving data analysis, offering significant enhancements over existing methods in both accuracy and utility.