Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.05067 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910515984334848 |
|---|---|
| author | Hladík, Richard Tětek, Jakub |
| author_facet | Hladík, Richard Tětek, Jakub |
| contents | Smooth sensitivity is one of the most commonly used techniques for designing practical differentially private mechanisms. In this approach, one computes the smooth sensitivity of a given query $q$ on the given input $D$ and releases $q(D)$ with noise added proportional to this smooth sensitivity. One question remains: what distribution should we pick the noise from?
In this paper, we give a new class of distributions suitable for the use with smooth sensitivity, which we name the PolyPlace distribution. This distribution improves upon the state-of-the-art Student's T distribution in terms of standard deviation by arbitrarily large factors, depending on a "smoothness parameter" $γ$, which one has to set in the smooth sensitivity framework. Moreover, our distribution is defined for a wider range of parameter $γ$, which can lead to significantly better performance.
Moreover, we prove that the PolyPlace distribution converges for $γ\rightarrow 0$ to the Laplace distribution and so does its variance. This means that the Laplace mechanism is a limit special case of the PolyPlace mechanism. This implies that out mechanism is in a certain sense optimal for $γ\to 0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05067 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Smooth Sensitivity Revisited: Towards Optimality Hladík, Richard Tětek, Jakub Cryptography and Security Smooth sensitivity is one of the most commonly used techniques for designing practical differentially private mechanisms. In this approach, one computes the smooth sensitivity of a given query $q$ on the given input $D$ and releases $q(D)$ with noise added proportional to this smooth sensitivity. One question remains: what distribution should we pick the noise from? In this paper, we give a new class of distributions suitable for the use with smooth sensitivity, which we name the PolyPlace distribution. This distribution improves upon the state-of-the-art Student's T distribution in terms of standard deviation by arbitrarily large factors, depending on a "smoothness parameter" $γ$, which one has to set in the smooth sensitivity framework. Moreover, our distribution is defined for a wider range of parameter $γ$, which can lead to significantly better performance. Moreover, we prove that the PolyPlace distribution converges for $γ\rightarrow 0$ to the Laplace distribution and so does its variance. This means that the Laplace mechanism is a limit special case of the PolyPlace mechanism. This implies that out mechanism is in a certain sense optimal for $γ\to 0$. |
| title | Smooth Sensitivity Revisited: Towards Optimality |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2407.05067 |