google / google/differential-privacy

Sensitivity off by a factor of 2 with 'replace_one' neighbouring relation

Open
#378 2 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.