#17764: Discrete Gaussian Lattice Sampler Unexpected Behaviour over RDF (Gram-
Schmidt related)
-------------------------+-------------------------------------------------
Reporter: | Owner:
katestange | Status: new
Type: defect | Milestone: sage-6.5
Priority: minor | Keywords: discrete gaussian lattice
Component: | sampler gram-schmidt
statistics | Authors:
Merged in: | Report Upstream: N/A
Reviewers: | Branch:
Work issues: | Dependencies:
Commit: |
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
}}}
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/17764>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
