Opened 4 years ago

# Discrete Gaussian Lattice Sampler Unexpected Behavour for _call_in_lattice()

Reported by: Owned by: haochen_uw minor sage-6.9 statistics discrete gaussian lattice sampler call_in_lattice malb Martin Albrecht N/A u/malb/t19138-discrete-gaussian-lattice (Commits) 8de8bed4dc46f4b912c411e2563516c468b3b4e9

### 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().

### comment:1 Changed 4 years ago by malb

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

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

New commits:

 ​0e0749d `whitespace changes` ​4cd6b25 `fix 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:

 ​647a482 `whitespace changes` ​b4c52f0 `fix 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:

 ​8de8bed `fix 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.