Unbiased Locally Private Estimator for Polynomials of Laplacian Variables

This work presents a mechanism to debias polynomial functions computed from locally differentially private data. Local differential privacy is a widely used privacy notion where users add Laplacian noise to their information before submitting it to a central server. That, however, causes bias when we calculate non-linear functions based on those noisy information. Our proposed recursive algorithm debiases these functions, with a calculation time of O(r n log n), where r is the polynomial degree and n is the number of users. We evaluate our method on the problems of k-star counting and variance estimation, comparing results with state-of-the-art algorithms. The results show that our method not only eliminates bias, but also provides at least 100 times more accuracy than previous works.