blob: f8fd0fcaedbf6b7a9d32396cdcacdb5e41e6a9a4 [file] [log] [blame]
//
// Copyright 2019 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
#ifndef DIFFERENTIAL_PRIVACY_ALGORITHMS_DISTRIBUTIONS_H_
#define DIFFERENTIAL_PRIVACY_ALGORITHMS_DISTRIBUTIONS_H_
#include <memory>
#include <cstdint>
#include "absl/status/status.h"
#include "absl/status/statusor.h"
namespace differential_privacy {
namespace internal {
// Allows samples to be drawn from a Gaussian distribution over a given stddev
// and mean 0 with optional per-sample scaling.
// The Gaussian noise is generated according to the binomial sampling mechanism
// described in
// https://github.com/google/differential-privacy/blob/main/common_docs/Secure_Noise_Generation.pdf
// This approach is robust against unintentional privacy leaks due to artifacts
// of floating point arithmetic.
class GaussianDistribution {
public:
// Builder for GaussianDistribution.
class Builder {
public:
Builder& SetStddev(double stddev);
absl::StatusOr<std::unique_ptr<GaussianDistribution>> Build();
private:
double stddev_;
};
virtual ~GaussianDistribution() {}
virtual double Sample();
// Samples the Gaussian with distribution Gauss(scale*stddev).
virtual double Sample(double scale);
// Returns the standard deviation of this distribution.
double Stddev() const;
// Returns the granularity that is also used when calculating Sample(). Be
// careful when using GetGranularity() together with Sample() and make sure to
// use the same parameter for scale in such cases.
double GetGranularity(double scale) const;
// Returns the cdf of the Gaussian distribution with standard deviation stddev
// at point x.
static double cdf(double stddev, double x);
// Returns the quantile (inverse cdf) of the Gaussian distribution with
// standard deviation stddev at point x.
static double Quantile(double stddev, double x);
private:
// Constructor for Gaussian with specified stddev.
explicit GaussianDistribution(double stddev);
// Sample from geometric distribution with probability 0.5. It is much faster
// then using GeometricDistribution which is suitable for any probability.
double SampleGeometric();
double SampleBinomial(double sqrt_n);
double stddev_;
};
// Returns a sample drawn from the geometric distribution of probability
// p = 1 - e^-lambda, i.e. the number of bernoulli trial failures before the
// first success where the success probability is as defined above. lambda must
// be positive. If the result would be higher than the maximum int64_t, returns
// the maximum int64_t, which means that users should be careful around the edges
// of their distribution.
class GeometricDistribution {
public:
// Builder for GeometricDistribution.
class Builder {
public:
Builder& SetLambda(double lambda);
absl::StatusOr<std::unique_ptr<GeometricDistribution>> Build();
private:
double lambda_;
};
virtual ~GeometricDistribution() {}
virtual double GetUniformDouble();
virtual int64_t Sample();
virtual int64_t Sample(double scale);
double Lambda();
protected:
explicit GeometricDistribution(double lambda);
private:
double lambda_;
};
// DO NOT USE. Use LaplaceMechanism instead. LaplaceMechanism has an interface
// that directly accepts DP parameters, rather than requiring an error-prone
// conversion to Laplace parameters.
//
// Allows sampling from a secure Laplace distribution, which uses a geometric
// distribution to generate its noise in order to avoid the attack from
// Mironov's 2012 paper, "On Significance of the Least Significant Bits For
// Differential Privacy":
// http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.5957&rep=rep1&type=pdf
class LaplaceDistribution {
public:
// Builder for LaplaceDistribution.
class Builder {
public:
Builder& SetEpsilon(double epsilon);
Builder& SetSensitivity(double sensitivity);
absl::StatusOr<std::unique_ptr<LaplaceDistribution>> Build();
private:
double epsilon_;
double sensitivity_;
};
virtual ~LaplaceDistribution() = default;
virtual double GetUniformDouble();
virtual double Sample();
virtual int64_t MemoryUsed();
virtual bool GetBoolean();
virtual double GetGranularity();
virtual double GetVariance() const;
// Returns the parameter defining this distribution, often labeled b.
double GetDiversity() const;
// Returns the smallest possible valid epsilon.
static double GetMinEpsilon();
// Returns the cdf of the Laplace distribution with scale b at point x.
static double cdf(double b, double x);
// Returns the quantile (inverse cdf) of the Laplace distribution with
// scale b at the point p.
static double Quantile(double b, double p);
// Calculates 'r' from the secure noise paper (see
// ../../common_docs/Secure_Noise_Generation.pdf)
static absl::StatusOr<double> CalculateGranularity(double epsilon,
double sensitivity);
protected:
explicit LaplaceDistribution(
double epsilon, double sensitivity, double granularity,
std::unique_ptr<GeometricDistribution> geometric_distro);
// Constructor that might fail during initialization of granularity or the
// GeometricDistribution.
explicit LaplaceDistribution(double epsilon, double sensitivity);
private:
static absl::Status ValidateEpsilon(double epsilon);
double epsilon_;
double sensitivity_;
double granularity_;
// Inclusive lower bound for epsilon when calculating granularity.
static constexpr double kMinEpsilon = 1.0 / (int64_t{1} << 50);
protected:
std::unique_ptr<GeometricDistribution> geometric_distro_;
};
} // namespace internal
} // namespace differential_privacy
#endif // DIFFERENTIAL_PRIVACY_ALGORITHMS_DISTRIBUTIONS_H_