google / google/differential-privacy
Sensitivity off by a factor of 2 with 'replace_one' neighbouring relation
- Dominant language
- Go
- Stars
- 3.4k
- Forks
- 434
- Avg merge
- 4d 9h
- Merged PRs (30d)
- 9
Description
The (descriptions) of the sensitivity of a GaussianDpEvent are inconsistent between the class definition and its use in the Renyi accountant, in Python:
The [Gaussian mechanism event](https://github.com/google/differential-privacy/blob/406de87234928900dc739d6b7d0b3d24aaa015e2/python/dp_accounting/dp_accounting/dp_event.py#L264C1-L271C26) is defined with a noise multiplier = noise variance / clipping threshold.
```python
class GaussianDpEvent(DpEvent):
"""Represents an application of the Gaussian mechanism.
For values v_i and noise z ~ N(0, s^2I), this mechanism returns sum_i v_i + z.
If the norms of the values are bounded ||v_i|| <= C, the noise_multiplier is
defined as s / C.
"""
noise_multiplier: float
```
For `ADD_OR_REMOVE_ONE` sensitivity, this is the same as the ratio 'noise variance' / 'sensitivity of sum', but for a `REPLACE_ONE` neighbouring relation, the l2 sensitivity of the function is twice the clipping bound (in the worst case, we replace +C with -C), so he `GaussianDpEvent.noise_multiplier` is twice as high as the 'true' noise multiplier of the mechanism.
But, this quantity is then passed directly into the Renyi accountant with subsampling: [here](https://github.com/google/differential-privacy/blob/406de87234928900dc739d6b7d0b3d24aaa015e2/python/dp_accounting/dp_accounting/rdp/rdp_privacy_accountant.py#L417), and is assumed to the be true noise multiplier for the `REPLACE_ONE` neighbouring relation:
```
Args:
q: The sampling proportion = m / n. Assume m is an integer <= n.
noise_multiplier: The ratio of the standard deviation of the Gaussian noise
to the l2-sensitivity of the function to which it is added.
orders: An array of RDP orders.
```
Similarly, when subsampling is not applied [(here)](https://github.com/google/differential-privacy/blob/main/python/dp_accounting/dp_accounting/rdp/rdp_privacy_accountant.py#L1021), the `GaussianDpEvent.noise_multiplier` is passed directly into code that assumes a
`ADD_OR_REMOVE_ONE` or `REPLACE_SPECIAL` neighbouring relation.
```python
elif isinstance(event, dp_event.GaussianDpEvent):
if do_compose:
self._rdp += count * _compute_rdp_poisson_subsampled_gaussian(
q=1.0, noise_multiplier=event.noise_multiplier, orders=self._orders
)
````
I suspect this neighbouring relation is not widely used, but I think it would be good to sort this out somehow. The simplest is probably to rephrase the definition of the GaussianDpEvent to use sensitivity, and maybe mention what that means for the different neighbouring relations?
Contributor guide
Assessment
This issue has not been assessed yet.