noise

Documentation

Overview

Package noise contains methods to generate and add noise to data.

Index

• func SigmaForGaussian(l0Sensitivity int64, lInfSensitivity, epsilon, delta float64) float64
• type ConfidenceInterval
• type Kind
  • func ToKind(n Noise) Kind
• type Noise
  • func Gaussian() Noise
  • func Laplace() Noise
  • func ToNoise(k Kind) Noise

Functions

func SigmaForGaussian

func SigmaForGaussian(l0Sensitivity int64, lInfSensitivity, epsilon, delta float64) float64

SigmaForGaussian calculates the standard deviation σ of Gaussian noise needed to achieve (ε,δ)-approximate differential privacy.

SigmaForGaussian uses binary search. The result will deviate from the exact value σ_tight by at most gaussianSigmaAccuracy*σ_tight.

Runtime: O(log(max(σ_tight/l2Sensitivity, l2Sensitivity/σ_tight)) +

log(gaussianSigmaAccuracy)).

where l2Sensitivity := lInfSensitivity * math.Sqrt(l0Sensitivity)

TODO: Memorize the results of this function to avoid recomputing it

Types

type ConfidenceInterval

type ConfidenceInterval struct {
	LowerBound, UpperBound float64
}

ConfidenceInterval holds lower and upper bounds as float64 for the confidence interval.

type Kind

type Kind int

Kind is an enum type. Its values are the supported noise distributions types for differential privacy operations.

const (
	GaussianNoise Kind = iota
	LaplaceNoise
	Unrecognised
)

Noise distributions used to achieve Differential Privacy.

func ToKind

func ToKind(n Noise) Kind

ToKind converts a Noise instance into a Kind.

type Noise

type Noise interface {
	// AddNoiseInt64 noise to the specified int64 x so that the output is ε-differentially
	// private given the L_0 and L_∞ sensitivities of the database.
	AddNoiseInt64(x, l0sensitivity, lInfSensitivity int64, epsilon, delta float64) int64

	// AddNoiseFloat64 noise to the specified float64 x so that the output is ε-differentially
	// private given the L_0 and L_∞ sensitivities of the database.
	AddNoiseFloat64(x float64, l0sensitivity int64, lInfSensitivity, epsilon, delta float64) float64

	// Threshold returns the smallest threshold k needed in settings where the Noise instance
	// is used to achieve differential privacy on histograms where the inclusion of histogram
	// partitions depends on which privacy units are present in the database.
	//
	// Inputs:
	//   l0Sensitivity: The maximum number of partitions that a privacy unit can contribute to.
	//   lInfSensitivity: How much any single partition's value can change from
	//     the contribution of a single privacy unit. When adding a privacy unit results in the
	//     creation of a new partition, this bounds the magnitude of that partition.
	//   epsilon: The parameter ε passed to AddNoise.
	//   noiseDelta: The parameter δ passed to AddNoise.
	//   thresholdDelta: Differential privacy loss (0, delta) incurred by thresholding,
	//     i.e. the probability to output a partition that only has one privacy unit in it.
	//
	// More precisely, Threshold returns the smallest k such that the following algorithm:
	//
	//   func Histogram(records []struct{key string, value float64}) map[string]float64 {
	//     sums := make(map[string]float64)
	//	   for _, record := range records {
	//       sums[record.key] = sums[record.key]+record.value
	//     }
	//     noisySums := make(map[string]float64)
	//     for key, sum := range sums {
	//       noisySum := AddNoiseFloat64(sum, sensitivity, epsilon, noiseDelta)
	//       if noisySum ≥ k:
	//         noisySums[key] = noisySum
	//     }
	//     return noisySums
	//   }
	//
	// satisfies (epsilon,noiseDelta+thresholdDelta)-differential privacy under the
	// given assumptions of L_0 and L_∞ sensitivities.
	Threshold(l0Sensitivity int64, lInfSensitivity, epsilon, noiseDelta, thresholdDelta float64) float64

	// ComputeConfidenceIntervalInt64 computes a confidence interval that contains the raw integer value x from which int64
	// noisedX is computed with a probability greater or equal to 1 - alpha based on the specified noise parameters.
	ComputeConfidenceIntervalInt64(noisedX, l0Sensitivity, lInfSensitivity int64, epsilon, delta, alpha float64) (ConfidenceInterval, error)

	// ComputeConfidenceIntervalFloat64 computes a confidence interval that contains the raw value x from which float64
	// noisedX is computed with a probability equal to 1 - alpha based on the specified noise parameters.
	ComputeConfidenceIntervalFloat64(noisedX float64, l0Sensitivity int64, lInfSensitivity, epsilon, delta, alpha float64) (ConfidenceInterval, error)
}

Noise is an interface for primitives that add noise to data to make it differentially private.

func Gaussian

func Gaussian() Noise

Gaussian returns a Noise instance that adds Gaussian noise to its input.

The Gaussian noise is based on a binomial sampling mechanism that is robust against unintentional privacy leaks due to artifacts of floating-point arithmetic. See https://github.com/google/differential-privacy/blob/main/common_docs/Secure_Noise_Generation.pdf for more information.

func Laplace

func Laplace() Noise

Laplace returns a Noise instance that adds Laplace noise to its input. Its AddNoise* functions will fail if called with a non-zero delta.

The Laplace noise is based on a geometric sampling mechanism that is robust against unintentional privacy leaks due to artifacts of floating point arithmetic. See https://github.com/google/differential-privacy/blob/main/common_docs/Secure_Noise_Generation.pdf for more information.

func ToNoise

func ToNoise(k Kind) Noise

ToNoise converts a Kind into a Noise instance.