1 Introduction
Organizations and companies are becoming increasingly interested in collecting user data and telemetry to make data-driven decisions. While collecting and analyzing user data is beneficial to improve services and products, users’ privacy poses a major concern. Recently, the concept of Local Differential Privacy (LDP) has emerged as the accepted standard for privacy-preserving data collection [1], [2], [3]. In LDP, each user locally perturbs their sensitive data on their device before sharing the perturbed version with the data collector. The perturbation is performed systematically such that the data collector cannot infer with strong confidence the true value of any user given their perturbed value, yet it can still make accurate inferences pertaining to the general population. Due to its desirable properties, LDP has been adopted by major companies to perform certain tasks, including Google to analyze browser homepages and default search engines in Chrome [2], [4], Apple for determining emoji frequencies and spelling prediction in iOS [5], [6], and Microsoft to collect application telemetry in Windows 10 [7].