Opened 4 years ago
Last modified 3 years ago
#19138 needs_work defect
Discrete Gaussian Lattice Sampler Unexpected Behavour for _call_in_lattice()
Reported by:  haochen_uw  Owned by:  

Priority:  minor  Milestone:  sage6.9 
Component:  statistics  Keywords:  discrete gaussian lattice sampler call_in_lattice 
Cc:  malb  Merged in:  
Authors:  Martin Albrecht  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/malb/t19138discretegaussianlattice (Commits)  Commit:  8de8bed4dc46f4b912c411e2563516c468b3b4e9 
Dependencies:  Stopgaps: 
Description
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 nonstandard 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().
Change History (6)
comment:1 Changed 4 years ago by
 Branch set to u/malb/t19138discretegaussianlattice
 Commit set to 4cd6b255ead3a345d271bafa6c06b550b89d804f
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
 Commit changed from 4cd6b255ead3a345d271bafa6c06b550b89d804f to b4c52f00db4be9900ef907e4a60cf434feae6ab3
comment:3 Changed 3 years ago by
I've rebased this ticket to the current development branch. Anybody up for reviewing this ticket?
comment:4 Changed 3 years ago by
wrong syntax here:
that `trac:19138` is fixed
should be
that :trac:`19138` is fixed
comment:5 Changed 3 years ago by
 Commit changed from b4c52f00db4be9900ef907e4a60cf434feae6ab3 to 8de8bed4dc46f4b912c411e2563516c468b3b4e9
Branch pushed to git repo; I updated commit sha1. New commits:
8de8bed  fix format in docstring

You're right, I was being silly when I wrote that optimisation.
New commits:
whitespace changes
fix discrete gaussian distribution cf. #19138