Documentation
¶
Overview ¶
Package sample includes samplers for sampling random values from different probability distributions.
Package sample provides the Sampler interface along with different implementations of this interface. Its primary purpose is support choosing random *big.Int values from selected probability distributions.
Implementations of the Sampler interface can be used, for instance, to fill vector or matrix structures with the desired random data.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var SigmaCDT, _ = new(big.Float).SetString("0.84932180028801904272150283410")
SigmaCDT is a constant sqrt(1/(2ln(2)))
Functions ¶
func Bernoulli ¶
Bernoulli returns true with probability proportional to 2^{-t/l^2}. A polynomial approximation is used to evaluate the exponential function. The implementation is based on paper: "FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers" by R. K. Zhao, R. Steinfeld, and A. Sakzad (https://eprint.iacr.org/2018/1234.pdf). See the above paper where it is argued that such a sampling achieves a relative error at most 2^{-45} with the chosen parameters.
Types ¶
type NormalCDT ¶
type NormalCDT struct {
// contains filtered or unexported fields
}
NormalCDT samples random values from the discrete Normal (Gaussian) probability distribution, limited to non-negative values (half-Gaussian). In particular each value x from Z^+ is sampled with probability proportional to exp(-x^2/sigma^2) where sigma = sqrt(1/2ln(2)). The implementation is based on paper: "FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers" by R. K. Zhao, R. Steinfeld, and A. Sakzad (https://eprint.iacr.org/2018/1234.pdf). See the above paper where it is argued that such a sampling achieves a relative error at most 2^{-46} with the chosen parameters.
func NewNormalCDT ¶
func NewNormalCDT() *NormalCDT
NewNormalCDT returns an instance of NormalCDT sampler.
type NormalCumulative ¶
type NormalCumulative struct {
// contains filtered or unexported fields
}
NormalCumulative samples random values from the cumulative Normal (Gaussian) probability distribution, centered on 0. This sampler is the fastest, but is limited only to cases when sigma is not too big, due to the sizes of the precomputed tables. Note that the sampler offers arbitrary precision but the implementation is not constant time.
func NewNormalCumulative ¶
func NewNormalCumulative(sigma *big.Float, n uint, twoSided bool) *NormalCumulative
NewNormalCumulative returns an instance of NormalCumulative sampler. It assumes mean = 0. Values are precomputed when this function is called, so that Sample merely returns a precomputed value.
type NormalDouble ¶
type NormalDouble struct {
// contains filtered or unexported fields
}
NormalDouble samples random values from the normal (Gaussian) probability distribution, centered on 0. This sampler works in a way that it first samples from a NormalCumulative with some small sigma and then using another sampling from uniform distribution creates a candidate for the output, which is accepted or rejected with certain probability. Note that the sampler offers arbitrary precision but the implementation is not constant time.
func NewNormalDouble ¶
NewNormalDouble returns an instance of NormalDouble sampler. It assumes mean = 0. Values are precomputed when this function is called, so that Sample merely samples a value. sigma should be a multiple of firstSigma. Increasing firstSigma a bit speeds up the algorithm but increases the number of precomputed values
type NormalDoubleConstant ¶
type NormalDoubleConstant struct {
// contains filtered or unexported fields
}
NormalDoubleConstant samples random values from the normal (Gaussian) probability distribution, centered on 0. This sampler works by double sampling: it first samples from a fixed Gaussian distribution with NormalCDT and then using another sampling from uniform distribution creates a candidate for the output, which is accepted or rejected with certain probability. The sampler algorithm is constant time in the sense that the sampled value is independent of the time needed. The implementation is based on paper: "FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers" by R. K. Zhao, R. Steinfeld, and A. Sakzad, see https://eprint.iacr.org/2018/1234.pdf. See the above paper for the argumentation of the choice of parameters and proof of precision and security.
func NewNormalDoubleConstant ¶
func NewNormalDoubleConstant(l *big.Int) *NormalDoubleConstant
NewNormalDoubleConstant returns an instance of NormalDoubleConstant sampler. It assumes mean = 0. Parameter l needs to be given, such that sigma = l * sqrt(1/2ln(2)).
type NormalNegative ¶
type NormalNegative struct {
// contains filtered or unexported fields
}
NormalNegative samples random values from the possible outputs of Normal (Gaussian) probability distribution centered on 0 and accepts or denies each sample with probability defined by the distribution
func NewNormalNegative ¶
func NewNormalNegative(sigma *big.Float, n uint) *NormalNegative
NewNormalNegative returns an instance of NormalNegative sampler. It assumes mean = 0. Values are precomputed when this function is called, so that Sample merely returns a precomputed value.
type Sampler ¶
type Sampler interface {
// Sample samples random big integer values,
// possibly returning an error.
Sample() (*big.Int, error)
}
Sampler samples random big integer values. Implementations of this interface provide a method for sampling random values from the desired distribution.
type Uniform ¶
type Uniform struct {
UniformRange
}
Uniform samples random values from the interval [0, max).
type UniformRange ¶
type UniformRange struct {
// contains filtered or unexported fields
}
UniformRange samples random values from the interval [min, max).
func NewUniform ¶
func NewUniform(max *big.Int) *UniformRange
NewUniform returns an instance of the Uniform sampler. It accepts an upper bound on the sampled values.
func NewUniformRange ¶
func NewUniformRange(min, max *big.Int) *UniformRange
NewUniformRange returns an instance of the UniformRange sampler. It accepts lower and upper bounds on the sampled values.
Source Files