opened
sebastian-sohr
username_0
Hallo,
I think I found a discrepancy between the implementation of the snapping mechanism in the method

`virtual double AddNoise(double result, double privacy_budget)`

of the class LaplaceMechanism in the file

`differential_privacy/algorithms/numerical-mechanisms.h`

and the theory given in **Mironov, 2012,** (which is cited in the code):

The rounding is done _towards 0_ while Mironov uses _rounding towards closest multiple of `nearest_power` with ties resolved towards +infty_.

This could (not very elegantly) be achieved by

```
virtual double AddNoise(double result, double privacy_budget) {
    CHECK_GT(privacy_budget, 0);
    // Implements the snapping mechanism defined by
    // Mironov (2012, "On Significance of the Least Significant Bits For
    // Differential Privacy").
    double noise = distro_->Sample(1.0 / privacy_budget);
    double noised_result =
        Clamp<double>(LowerBound<double>(), UpperBound<double>(), result) +
        noise;
    double nearest_power = GetNextPowerOfTwo(diversity_ / privacy_budget);
    double remainder =
        (nearest_power == 0.0) ? 0.0 : fmod(noised_result, nearest_power);
    double rounded_result = noised_result - remainder;
    if (remainder >= nearest_power / 2) {
      rounded_result += nearest_power;
    }
    if (remainder < -nearest_power / 2) {
      rounded_result -= nearest_power;
    }
    return ClampDouble<double>(LowerBound<double>(), UpperBound<double>(),
                               rounded_result);
  }

```
But, maybe, I oversee some detail of the implementation :-) .

Regards,

Sebastian.
Is snapping mechanism in LaplaceMechanism->AddNoise implemented correctly ?
issue
created
dasmdasm
username_1
I think the proof can be adapted for a different rounding technique, but rounding to the nearest integer also reduces the amount of error introduced by the mechanism, so it's a good change to make regardless.
comment
created
sebastian-sohr
username_0
You are right.
comment
closed
sebastian-sohr
username_0
issue