Laplace mechanism does not appear to be differentially private

[frankmcsherry]

I may be missing a lot of context, in which case I apologize, but it appears that your implementation of the Laplace mechanism just calls in to the generator of the probability crate and then rescales the result. This is known to not be differentially private. There are several fixes, including Mironov's "snapping mechanism" and directly producing fixed precision samples by sampling their bits independently.

Google has an open source implementation that addresses many of these issues that you can consult:

https://github.com/google/differential-privacy/blob/e819e03a20f9d7b0a30f2547c00ba74065b3f549/differential_privacy/algorithms/numerical-mechanisms.h

[globusharris]

Thank you for looking over the codebase, we really appreciate it!

We are working on floating point vulnerabilities and Ilya’s attack; they are the impetus for the use of the geometric mechanism as a default where possible. We’ve had discussions with Ilya and have an implementation of the snapping mechanism we are currently working on. We’re also working on integrating a floating-point safe exponential mechanism. https://arxiv.org/abs/1912.04222

Thank you for the link to the google implementation of the snapping mechanism, we are looking at it now.

In terms of producing fixed precision samples, we hadn’t thought of using the approach in Our Data, Ourselves. For larger epsilon and delta this looks promising. We are also looking at this working paper on a discrete Gaussian as another possible solution: https://arxiv.org/pdf/2004.00010.pdf.

Thank you again for looking through the repo and raising this issue.

[Shoeboxam]

The latest library release improves handling of this. The Laplace mechanism remains in the library, but protect_floating_point must be disabled in the privacy definition to use it. There is also now an implementation of the snapping mechanism, enabled by default for non-integer queries.

The snapping mechanism is here: https://github.com/opendifferentialprivacy/smartnoise-core/blob/24ef807487a8405c9542ba57469b3b6bb70e7e5a/runtime-rust/src/utilities/mechanisms.rs#L39-L112

Snapping noise internals 1: https://github.com/opendifferentialprivacy/smartnoise-core/blob/24ef807487a8405c9542ba57469b3b6bb70e7e5a/runtime-rust/src/utilities/noise.rs#L660-L724

Snapping noise internals 2: https://github.com/opendifferentialprivacy/smartnoise-core/blob/24ef807487a8405c9542ba57469b3b6bb70e7e5a/runtime-rust/src/utilities/mod.rs#L453-L497

Pre-execution validation and utilities: https://github.com/opendifferentialprivacy/smartnoise-core/blob/24ef807487a8405c9542ba57469b3b6bb70e7e5a/validator-rust/src/components/snapping_mechanism.rs#L253-L359

Whitepaper with additional implementation notes: https://github.com/opendifferentialprivacy/smartnoise-core/blob/a9c7c3ba799c2aa1d77145bf572ed01cac6e4b52/whitepapers/mechanisms/snapping/snapping_implementation_notes.pdf

Happy to reopen if there are further concerns.