An Efficient Range Sum Query Scheme Under Local Differential Privacy
Ellen Z. Zhang, Yunguo Guan, Yantao Yu, Rongxing Lu, Harry Zhang · 2024
Crowdsourcing has received considerable attention in recent years; however, privacy in crowdsourcing remains a challenge. In this paper, we present a privacy-preserving range sum query scheme under Local Differential Privacy (LDP) that not only enhances accuracy but also guarantees privacy in crowdsourcing applications. Specifically, our proposed scheme employs keyed hash, prefix encoding, and garbled bloom filter techniques to convert a large query range into a small domain, independent of the range length, thus improving accuracy. For the query response, the Optimal Unary Encoding (OUE) technique is applied to achieve ε-LDP. Security analysis shows that our proposed scheme can achieve the desirable privacy requirement for users' private items and the server's query range. In addition, performance evaluations also confirm the efficiency of our scheme in terms of computational costs and communication overhead. Furthermore, extensive experiments validate that our proposed scheme outperforms a potential strawman solution in terms of accuracy.