Differential Privacy via Haar Wavelet Transform and Gaussian Mechanism for Range Query

Area of Science:

• Computer Science
• Data Privacy
• Signal Processing

Background:

• Range queries are crucial in data publishing but pose privacy risks.
• Large range queries necessitate more noise injection, potentially compromising data utility.
• Existing methods struggle to balance privacy and utility effectively.

Purpose of the Study:

• To develop a privacy-preserving technique for range queries using differential privacy.
• To analyze the limitations of the Laplace mechanism for range queries with Haar wavelet transform.
• To propose and evaluate a novel approach combining Haar wavelet transform and the Gaussian mechanism.

Main Methods:

• Analysis of noise injection via the Laplace mechanism for range queries.
• Development of a method for injecting noise into Haar wavelet coefficients using the Gaussian mechanism.
• Derivation of the maximum variance for range queries under the proposed framework.

Main Results:

• The Laplace mechanism is suboptimal for range queries with Haar wavelet transform due to noise distribution properties.
• The proposed Haar wavelet transform and Gaussian mechanism effectively preserve differential privacy for data and queries.
• The new mechanism achieves significantly lower noise variance compared to using the Gaussian mechanism alone.
• Experimental results on census data demonstrate reduced noise variance for range-count queries.

Conclusions:

• The Haar wavelet transform combined with the Gaussian mechanism offers a superior approach to differential privacy for range queries.
• This method provides enhanced privacy protection with improved data utility by minimizing noise.
• The findings are validated through experimental analysis on real-world datasets.