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: sage-6.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/t19138-discrete-gaussian-lattice (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 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().

Change History (6)

comment:1 Changed 4 years ago by malb

  • Authors set to Martin Albrecht
  • Branch set to u/malb/t19138-discrete-gaussian-lattice
  • Commit set to 4cd6b255ead3a345d271bafa6c06b550b89d804f
  • Status changed from new to needs_review

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


New commits:

0e0749dwhitespace changes
4cd6b25fix discrete gaussian distribution cf. #19138

comment:2 Changed 3 years ago by git

  • Commit changed from 4cd6b255ead3a345d271bafa6c06b550b89d804f to b4c52f00db4be9900ef907e4a60cf434feae6ab3

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

647a482whitespace changes
b4c52f0fix discrete gaussian distribution cf. #19138

comment:3 Changed 3 years ago by malb

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

comment:4 Changed 3 years ago by chapoton

wrong syntax here:

that `trac:19138` is fixed

should be

that :trac:`19138` is fixed

comment:5 Changed 3 years ago by git

  • Commit changed from b4c52f00db4be9900ef907e4a60cf434feae6ab3 to 8de8bed4dc46f4b912c411e2563516c468b3b4e9

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

8de8bedfix format in docstring

comment:6 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

does not apply

Note: See TracTickets for help on using tickets.