Abstract: Range queries are key indicators in data analysis under various scenarios. However, when dealing with individuallevel data, personal privacy issues will be involved. To address this problem, range query protocols that meet local differential privacy (LDP) have been proposed. These protocols enable data collectors to collect aggregated information about the population without relying on trusted third parties while protecting the privacy of each user. Nevertheless, the perturbation methods used in the existing range query protocols based on LDP have limitations, which restrict their effectiveness. In addition, these protocols usually exhibit poor estimation performance for small range intervals. In light of this, a Hierarchical Range Query protocol based on the differential privacy shuffling model (SHRQ) is proposed. Firstly, this paper extensively analyzes the variance of the perturbation methods in previous protocols. The SHRQ protocol selects the optimal perturbation method according to the number of nodes in each layer. Then, the SHRQ makes the most of the advantages of the shuffling model by leveraging prior knowledge from the previous round for multiple iterations, significantly improving the estimation accuracy of small range query intervals. Through extensive comparative experiments on both simulated and realworld datasets, it is demonstrated that after a few iterations, SHRQ reduces the estimation error for small ranges by an order of magnitude and for large ranges by half an order of magnitude compared to previous protocols.

Key words: differential privacy, range query, privacy protection, shuffle model, data security

摘要： 范围查询是各种场景下数据分析的关键指标.然而，在处理个体层面的数据时会涉及个人隐私问题.为了解决这个问题，满足本地化差分隐私(local differential privacy, LDP)的范围查询协议被提出.这些协议使数据收集者能够在不依赖可信第三方的情况下收集关于总体的聚合信息，同时保护每个用户的隐私.尽管如此，现有基于LDP的范围查询协议中使用的扰动方法存在局限性，限制了方法的有效性.此外，这些协议对于小范围区间通常表现出较差的估计性能.鉴于此提出了一种基于差分隐私洗牌模型的分层范围查询(shuffling hierarchical range query, SHRQ)协议.首先，广泛分析了原有协议中扰动方法的方差，SHRQ协议根据每个层次中的节点数量选择最佳扰动方法.然后，SHRQ协议通过利用前一轮的先验知识进行多次迭代，最大限度地发挥洗牌模型的优势，显著提高了小范围查询区间的估计准确性.通过在模拟数据集和真实世界数据集上与原有协议进行大量对比实验，证明了在较少的迭代次数后，SHRQ协议将小范围的估计误差降低1个数量级，将大范围的估计误差降低半个数量级.

关键词: 差分隐私, 范围查询, 隐私保护, 洗牌模型, 数据安全