Lightweight Local Differential Privacy For High-dimensional Data
Tianyu Zheng, Xiaolin Zhao, Zhenyan Liu, Chaorong Song, Yunsheng Li, Yukun Huang · 2025
Frequency publication, as a data release mechanism, typically involves data counting and aggregation. When integrated with differential privacy, this approach introduces carefully calibrated randomness during data transmission and publication processes to mitigate personal privacy leakage risks. However, challenges such as excessive user response ranges or flawed encoding schemes may induce dimensional expansion of local desensitization data, leading to high-dimensional issues including model fitting difficulties, communication overhead explosion, and computational complexity escalation. This paper proposes two innovative solutions. First, the Succinct Histograms Based on Encoding Optimization (OSH) algorithm employing orthogonal matrix encoding effectively addresses the prevalent accuracy degradation problem in conventional sampling-based methods. Second, the Local, Private, Efficient Protocols Succinct Histograms Based on non-cryptographic Hash Algorithm (NCHOSH) utilizes non-cryptographic hashing for encoding, which enhances encoding efficiency while resolving collision issues inherent in prior approaches, and enables data desensitization in unknown candidate value scenarios. Both methodologies achieve lightweight implementation through mapping-based dimension reduction, significantly reducing communication costs and computational burdens associated with high-dimensional data processing. Experimental comparisons with mainstream algorithms demonstrate superior performance of OSH and NCHOSH in multiple metrics.