Private Means and the Curious Incident of the Free Lunch

2024/08/19 by Fitzsimons, Jack, James Honaker, Honaker, James +4
Social Sciences · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Law in Society and Culture

paper · pdf · doi:10.48550/arxiv.2408.10438

openalex publication_date 2024/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the most well-known and fundamental building blocks of DP implementations -- sum, mean, count (and many other linear queries) -- can be released with substantially reduced noise for the same privacy guarantee. We achieve this by projecting individual data with worst-case sensitivity R onto a simplex where all data now has a constant norm R. In this simplex, additional ``free'' queries can be run that are already covered by the privacy-loss of the original budgeted query, and which algebraically give additional estimates of counts or sums.

Related

• Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms
• Differentially Private Mechanisms for Count Queries
• Pure-DP Statistical Query Release at the Conjectured Square-Root Rate
• Learning Numeric Optimal Differentially Private Truncated Additive Mechanisms
• Private Data Release via Learning Thresholds