Differentially private range counting: where asymptotically better fails, integer covering prevails
研究了差分隐私下范围计数查询的隐私保护问题，发现现有方法在小到中等窗口存在局限，提出一种组合区间覆盖方法，通过分析覆盖族厚度实现低误差的ε-差分隐私，并给出搜索最优族的算法，在相关场景中优于现有方案。
Abstract This work addresses the problem of maintaining privacy in range counting queries, with a focus on rolling-window queries over sensitive data. By employing differential privacy (DP), we can protect sensitive data used in these queries, as demonstrated in applications like COVID-19 tracking. Our research, however, identifies significant limitations in existing DP methods for small to medium-sized windows or ranges, which are commonly found in practical applications. We introduce a novel combinatorial interval covering approach, providing a detailed analysis of privacy-utility trade-offs within the DP framework. Our characterization of interval covering families’ thickness provides new insights into achieving $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -DP with minimal error. Additionally, we propose a search-based method for selecting optimal families for differentially private range counting queries, specifically for small to medium windows, which outperforms current solutions in relevant scenarios. This work contributes to both the theoretical foundation and practical application of differential privacy in data analytics, ensuring robust privacy protection without compromising query accuracy.