#19138: Discrete Gaussian Lattice Sampler Unexpected Behavour for
_call_in_lattice()
-------------------------+-------------------------------------------------
Reporter: | Owner:
haochen_uw | Status: new
Type: defect | Milestone: sage-6.9
Priority: minor | Keywords: discrete gaussian lattice
Component: | sampler call_in_lattice
statistics | Authors:
Merged in: | Report Upstream: N/A
Reviewers: | Branch:
Work issues: | Dependencies:
Commit: |
Stopgaps: |
-------------------------+-------------------------------------------------
The _call_in_lattice() 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().
--
Ticket URL: <http://trac.sagemath.org/ticket/19138>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
