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:


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


(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


....:    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:// 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.