This file implements oracles which return samples from a lattice following a discrete Gaussian distribution. That is, if
is big enough relative to the provided basis, then vectors are returned with a probability proportional to . More precisely lattice vectors in are returned with probability:AUTHORS:
EXAMPLES:
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^10, 3.0)
sage: D(), D(), D()
((3, 0, -5, 0, -1, -3, 3, 3, -7, 2), (4, 0, 1, -2, -4, -4, 4, 0, 1, -4), (-3, 0, 4, 5, 0, 1, 3, 2, 0, -1))
Bases: sage.structure.sage_object.SageObject
GPV sampler for Discrete Gaussians over Lattices.
EXAMPLE:
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^10, 3.0); D
Discrete Gaussian sampler with σ = 3.000000, c=(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) over lattice with basis
[1 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 1]
We plot a histogram:
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(identity_matrix(2), 3.0)
sage: S = [D() for _ in range(2^12)]
sage: l = [vector(v.list() + [S.count(v)]) for v in set(S)]
sage: list_plot3d(l, point_list=True, interploation='nn')
Graphics3d Object
REFERENCES:
[GPV08] | Craig Gentry, Chris Peikert, Vinod Vaikuntanathan. How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions. STOC 2008. http://www.cc.gatech.edu/~cpeikert/pubs/trap_lattice.pdf |
Construct a discrete Gaussian sampler over the lattice
with parameter sigma and centerINPUT:
EXAMPLE:
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: n = 2; sigma = 3.0; m = 5000
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^n, sigma)
sage: f = D.f
sage: c = D._normalisation_factor_zz(); c
56.2162803067524
sage: l = [D() for _ in xrange(m)]
sage: v = vector(ZZ, n, (-3,-3))
sage: l.count(v), ZZ(round(m*f(v)/c))
(39, 33)
sage: target = vector(ZZ, n, (0,0))
sage: l.count(target), ZZ(round(m*f(target)/c))
(116, 89)
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: qf = QuadraticForm(matrix(3, [2, 1, 1, 1, 2, 1, 1, 1, 2]))
sage: D = DiscreteGaussianDistributionLatticeSampler(qf, 3.0); D
Discrete Gaussian sampler with σ = 3.000000, c=(0, 0, 0) over lattice with basis
[2 1 1]
[1 2 1]
[1 1 2]
sage: D()
(0, 1, -1)
Return a new sample.
EXAMPLE:
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^3, 3.0, c=(1,0,0))
sage: L = [D() for _ in range(2^12)]
sage: abs(mean(L).n() - D.c)
0.08303258...
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^3, 3.0, c=(1/2,0,0))
sage: L = [D() for _ in range(2^12)] # long time
sage: mean(L).n() - D.c # long time
(0.0607910156250000, -0.128417968750000, 0.0239257812500000)
Center .
Samples from this sampler will be centered at .
EXAMPLE:
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^3, 3.0, c=(1,0,0)); D
Discrete Gaussian sampler with σ = 3.000000, c=(1, 0, 0) over lattice with basis
[1 0 0]
[0 1 0]
[0 0 1]
sage: D.c
(1, 0, 0)
Compute precision to use.
INPUT:
EXAMPLE:
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(100, RR(3))
100
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(100, RealField(200)(3))
100
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(100, 3)
100
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(None, RR(3))
53
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(None, RealField(200)(3))
200
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(None, 3)
53
Gaussian parameter
.Samples from this sampler will have expected norm
whereEXAMPLE:
sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^3, 3.0, c=(1,0,0))
sage: D.sigma
3.00000000000000