Opened 4 years ago

Last modified 3 years ago

# Discrete Gaussian Lattice Sampler Unexpected Behaviour over RDF (Gram-Schmidt related)

Reported by: Owned by: katestange major sage-6.5 statistics discrete gaussian lattice sampler gram-schmidt malb Martin Albrecht N/A u/malb/t17764-discrete-gaussian-vs-rdf (Commits) 38842a4ad449632cff813b82f869066dff83207a

### Description

Briefly, DiscreteGaussianDistributionLatticeSampler? produces vectors which are much too large when the matrix is given over RDF. It behaves as expected if the same matrix is given over QQ.

For any lattice L of dimension n, the norm of a sampled vector should be > sqrt(2*pi)*sigma*sqrt(n) with probability no greater than 2-2n (essentially never).

[Reference: Lemma 2.8 of A Toolkit for Ring-LWE Cryptography, Lyubashevsky, Peikert, Regev, quoted in turn from Banaszczyk, New bounds in some transference theorems in the geometry of numbers.]

Here's a simple example of the behaviour.

```n = 10
sigma = 30.0

from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler

M = Matrix(ZZ, n, n)

for i in range(n):

M[i, i] = i+1

D = DiscreteGaussianDistributionLatticeSampler(M, sigma)

want = RR(sqrt(n)*D.sigma)
have = mean([D().norm().n() for _ in range(10000)])

want, have, want/have
```

output:

(94.8683298050514, 92.3605709689830, 1.02715183340422)

If we alter the lonely ZZ to RDF, we get

(94.8683298050514, 564.835099977431, 0.167957568162534)

I discussed this with Martin Albrecht, and I think the most useful thing I can do is quote something he wrote about this:

I think the issue is this difference in behaviour:

```sage: n = 5
sage: M = Matrix(ZZ, n, n)
sage: for i in range(n):
....:         M[i, i] = i+1
....:

sage: M.gram_schmidt()[0]
[1 0 0 0 0]
[0 2 0 0 0]
[0 0 3 0 0]
[0 0 0 4 0]
[0 0 0 0 5]

sage: M.change_ring(RDF).gram_schmidt()[0]

[ 1.0 -0.0 -0.0 -0.0 -0.0]
[ 0.0  1.0  0.0  0.0  0.0]
[ 0.0  0.0  1.0  0.0  0.0]
[ 0.0  0.0  0.0  1.0  0.0]
[ 0.0  0.0  0.0  0.0  1.0]
```

In particular, the following comment from the documentation of gram_schmidt:

• "orthonormal" - default: "False" - if "True" the returned orthogonal vectors are unit vectors. This keyword is ignored if the matrix is over "RDF" or "CDF" and the results are always orthonormal.

The sampler calls the gram_schmidt() routine during setup and hence you're running into your unexpected behaviour.

My documentation is a bit fuzzy: it one the one hand claims only integer matrices are supporter) but also claims that anything where matrix(B) works is supported which is clearly not true.

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

• Priority changed from minor to major

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

• Branch set to u/malb/t17764-discrete-gaussian-vs-rdf
• Commit set to 81682ce4b4b5eff345fb926de6c15fd0966ed320

New commits:

 ​81682ce `work around gram_schmidt() orthonormalization`

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

• Authors set to Martin Albrecht
• Status changed from new to needs_review

### comment:4 Changed 4 years ago by chapoton

As suggested by patchbot report, please replace

```...     M[i, i] = i+1
```

by

```....:    M[i, i] = i+1
```

This is the "new style doctest continuation".

### comment:5 Changed 4 years ago by git

• Commit changed from 81682ce4b4b5eff345fb926de6c15fd0966ed320 to 130487b9b27613bb6bde364bdef137d3e9270250

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

 ​7596df4 `Merge branch 'develop' of git://trac.sagemath.org/sage into u/malb/t17764-discrete-gaussian-vs-rdf` ​130487b `fix doctest continuation`

Fixed, thanks.

### comment:7 Changed 3 years ago by git

• Commit changed from 130487b9b27613bb6bde364bdef137d3e9270250 to 38842a4ad449632cff813b82f869066dff83207a

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

 ​348369b `work around gram_schmidt() orthonormalization` ​38842a4 `fix doctest continuation`

### comment:8 Changed 3 years ago by malb

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

### comment:9 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.