Opened 4 years ago

Last modified 3 years ago

#17764 needs_work defect

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

Reported by: katestange Owned by:
Priority: major Milestone: sage-6.5
Component: statistics Keywords: discrete gaussian lattice sampler gram-schmidt
Cc: malb Merged in:
Authors: Martin Albrecht Reviewers:
Report Upstream: N/A Work issues:
Branch: u/malb/t17764-discrete-gaussian-vs-rdf (Commits) Commit: 38842a4ad449632cff813b82f869066dff83207a
Dependencies: Stopgaps:

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.

Change History (9)

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:

81682cework 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:

7596df4Merge branch 'develop' of git://trac.sagemath.org/sage into u/malb/t17764-discrete-gaussian-vs-rdf
130487bfix doctest continuation

comment:6 Changed 4 years ago by malb

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:

348369bwork around gram_schmidt() orthonormalization
38842a4fix 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.