Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication

Understand

We study the problem of estimating $k$-ary distributions under $\varepsilon$-local differential privacy.

• $n$ samples are distributed across users who send privatized versions of their sample to a central server.
• All previously known sample optimal algorithms require linear (in $k$) communication from each user in the high privacy regime $(\varepsilon=O(1))$, and run in time that grows as $n\cdot k$, which can be prohibitive for large domain size $k$.
• We propose Hadamard Response (HR}, a local privatization scheme that requires no shared randomness and is symmetric with respect to the users.