Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
It is well-known that to make the result of a $\mathbb{R}^d$-valued query $(\varepsilon,\delta)$-differentially private, you can add noise to it. If you add Laplace noise, you need to scale the noise by the $L_1$-sensitivity of the query; if you add Gaussian noise, you need to scale it by the $L_2$-sensitivity instead.
Are there noise functions that scale with, say, $L_3$-sensitivity, or any other $L_p$-sensitivity with $p>2$? If not, how to formalize and prove this impossibility result?
You can measure your sensitivity in an arbitrary norm. The exponential mechanism, that samples from the distribution proportional to $\exp(-\epsilon |z-f(x)|_p / 2)$ will give pure DP. This is more general, and the K-norm mechanism will allow you handle sensitivity measured in norms other than some p-norm. For pure DP, these p-norm mechanisms are optimal. In particular, when sensitivity is measured in the $\ell_2$ norm, the optimal mechanism adds noise from the Gamma distribution.
How then does the Gaussian noise mechanism do better? It gives you $(\epsilon, \delta)$-DP instead of pure DP. It is natural to ask what the optimal approximate DP mechanism is for other sensitivity measures. It turns out that for approximate DP, the right Gaussian mechanism is always optimal. You just convert your $\ell_p$ sensitivity bound into an $\ell_2$ sensitivity bound (by finding the smallest $\ell_2$ ball that contains your $\ell_p$ ball) and add Gaussian noise based on that. Here again, there are analogous results for sensitivity being measured in non-p-norms.
Some caveats are in order. Optimal above is for your error being measured in the Euclidean distance. Some of the results are optimal only up to logarithmic factors. When you care about error in other norms (say $\ell_\infty$), there can be other more interesting mechanisms.
References: The upper bounds for $\ell_p$ balls are straightforward. The lower bounds are in https://arxiv.org/abs/0907.3754, and https://arxiv.org/abs/1212.0297. Simpler lower bounds for CDP/RDP are in https://arxiv.org/abs/1911.08339.
What you are looking for seems like the K-norm mechanism by Hardt and Talwar (2009). In a recent paper, Awan and Slavković formulate it in a way that directly answers your question in a generic way (see Proposition 2.8): Releasing with an additive noise with the density function $$f(x) = \frac{\exp(−\frac{\varepsilon}{\Delta}‖x‖_p)}{\Gamma(m+1) \lambda (\frac{\Delta}{\varepsilon}p))},$$ where $\Delta$ is any upper bound on the sensitivity of the query in the $L_p$ norm, will satisfy $\varepsilon$-DP.
