Discrete Gaussian Lattice Sampler Unexpected Behavour for _call_in_lattice()

2b7e2412-d835-4200-b08a-fddc54a17084 commented 9 years ago

The _call_inlattice() method for DiscreteGaussianLatticeSampler is supposed to be a shortcut for call(), which outputs a sample from the discrete Gaussian distribution $D{\Lambda, c}$, in the case when the vector $c$ is in the lattice. The algorithm being used for sampling is [Gentry, Craig, Chris Peikert, and Vinod Vaikuntanathan. "Trapdoors for hard lattices and new cryptographic constructions." Proceedings of the fortieth annual ACM symposium on Theory of computing. ACM, 2008].

However, this shortcut function seems to be oversimplifying the sampling process. For example, we take a non-standard basis of the standard lattice in dimension 2 and take $c = 0$:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: B = Matrix([[1,1],[1,0]]); 
sage: D = DiscreteGaussianDistributionLatticeSampler(B, 5.0); 

sage: v0, v1 =[], []
sage: for i in range(100):
              v = D()
              v0.append(v[0])
              v1.append(v[1])

sage: RR(std(v0))
8.42768405826052

sage: RR(std(v1))
3.82193298177398

The standard deviation of the two coordinates are visibly different, while they should be the same, since the Gaussian distribution on the standard lattice has spherical symmetry.

I would guess a simple fix is to not use _call_in_lattice() and always use the more general _call().

CC: @malb

Component: statistics

Keywords: discrete gaussian lattice sampler call_in_lattice

Author: Martin Albrecht

Branch/Commit: u/malb/t19138-discrete-gaussian-lattice @ 8de8bed

Issue created by migration from https://trac.sagemath.org/ticket/19138

malb commented 9 years ago

Author: Martin Albrecht

malb commented 9 years ago

comment:1

You're right, I was being silly when I wrote that optimisation.

New commits:

`0e0749d`	`whitespace changes`
`4cd6b25`	`fix discrete gaussian distribution cf. #19138`

malb commented 9 years ago

Branch: u/malb/t19138-discrete-gaussian-lattice

malb commented 9 years ago

Commit: 4cd6b25

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`647a482`	`whitespace changes`
`b4c52f0`	`fix discrete gaussian distribution cf. #19138`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 4cd6b25 to b4c52f0

malb commented 8 years ago

comment:3

I've rebased this ticket to the current development branch. Anybody up for reviewing this ticket?

fchapoton commented 8 years ago

comment:4

wrong syntax here:

that `trac:19138` is fixed

should be

that :trac:`19138` is fixed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

8de8bed fix format in docstring

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from b4c52f0 to 8de8bed

fchapoton commented 8 years ago

comment:6

does not apply

sagemath / sage

Discrete Gaussian Lattice Sampler Unexpected Behavour for _call_in_lattice() #19138