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
- Priority changed from minor to major
comment:2 Changed 4 years ago by
- Branch set to u/malb/t17764-discrete-gaussian-vs-rdf
- Commit set to 81682ce4b4b5eff345fb926de6c15fd0966ed320
comment:3 Changed 4 years ago by
- Status changed from new to needs_review
comment:4 Changed 4 years ago by
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
- Commit changed from 81682ce4b4b5eff345fb926de6c15fd0966ed320 to 130487b9b27613bb6bde364bdef137d3e9270250
comment:6 Changed 4 years ago by
Fixed, thanks.
comment:7 Changed 3 years ago by
- Commit changed from 130487b9b27613bb6bde364bdef137d3e9270250 to 38842a4ad449632cff813b82f869066dff83207a
comment:8 Changed 3 years ago by
I've rebased this to current development branch. Anybody up for reviewing this bugfix?
New commits:
work around gram_schmidt() orthonormalization