Sarve: synthetic data and local differential privacy for private frequency estimation

Area of Science:

• Computer Science
• Data Privacy
• Machine Learning

Background:

• Service providers collect user attributes for predictive models, raising privacy concerns.
• Frequency oracles randomize user data to estimate attribute frequencies while protecting identity.
• Balancing computational and communication complexities is crucial in service-oriented architectures.

Purpose of the Study:

• To introduce Sarve, a novel frequency oracle combining RAPPOR and HR with fake data.
• To minimize computational and communication complexities in privacy-enhancing systems.
• To achieve statistical results comparable to original data with enhanced user privacy.

Main Methods:

• Utilized a variant of RAPPOR implemented with memory-efficient bloom filters (O(1) time complexity).
• Employed Hadamard Response (HR) for optimal communication costs (log(b) for b-bits).
• Integrated fake data and an adaptive solution enhanced from Arcolezi et al.

Main Results:

• Sarve demonstrates how combining existing privacy methods with fake data yields comparable statistical results.
• RAPPOR provided superior privacy-utility tradeoffs across various privacy budgets.
• The system effectively balances privacy guarantees with the utility of statistical analysis.

Conclusions:

• Sarve represents a significant advancement in frequency oracles, merging privacy techniques for robust data analysis.
• The proposed method offers a practical approach to address the privacy-utility tradeoff in user data analysis.
• Future work can further optimize these combined techniques for diverse privacy requirements.