#15915: add discrete Gaussian samplers to Sage
-------------------------------------+-------------------------------------
Reporter: malb | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.2
Component: statistics | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/malb/15915_discrete_gaussians | 6aa658c1999c3f151b15a76f61f6c404bc347143
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by malb):
Daniel Cabarcas looked at the C part of the code, here is what he said
(and my reply which I sent via e-mail)
> I looked at the code and I think it is an important improvement over
what we had
> before. I looked in detail at the uniform+table and the uniform+online
versions and I > think they are correct. I don't know the details of the
logtable algorithms so I
> didn't looked at the corresponding code. I have a few comments so far:
> The name of the library is DGS for discrete Gaussian samplers. However,
all
> implementations are over the integers, and not over a more general
lattice. I was
> wondering if it would be wiser to call it discrete Gaussian over the
integers,
> foreseeing implementations over other lattices.
My idea was to include the discrete Gaussian sampler over lattices (+
cosets)
into this implementation. Hence the name. However, for that I needed to do
#15976 first. I plan to go back to the samplers over the lattices once
both tickets
are merged (and I can rely on them).
> Have you consider implementing other samplers? if you are looking for
speed
> Knuth-Yao is quite impressive, and if you are looking for a time-memory
tradeoff the > discrete Ziggurat algorithm is nice. Moreover, in terms of
flexibility of the library > design, do you think it would be easy to add
other samplers in the future which
> require perhaps other parameters?
I haven't thought about Knuth-Yao or Ziggurat, do you have any good
references at hand? I'm happy to implement more samplers, might as well be
comprehensive. I was also thinking about extending the logtable approach
to arbitrary Gaussian parameters sigma.
As for the interface, I guess I should check the two algorithms you
mentioned above to see what would need to be generalised. If other
parameters are needed in the future I can simply add another constructor
which accepts those parameters, that was my thinking anyway.
> I was wondering about the source of randomness. You use standard c
functions, which >
> is probably ok for many tests. However, you know for sure how critical
is the source
> of randomness in crypto implementations. Moreover, there are huge
differences in
> speed between the standard random c function and a secure random
function, thus, for
> testing efficiency of Gaussian samplers it is crucial to have the
flexibility to
> choose your source of randomness. For this reason, in some
implementation we did, we
> had the source of randomness as a parameter. Perhaps, you'd like to
consider doing
> that.
I currently have two versions, one using GMP's randstate and one using
libc. GMP should give cryptographically strong pseudorandom numbers. In my
experience the difference in running time is - as you write - pretty much
down to how long it takes to sample random numbers, so I figured I offer
one with a good random number generator and one with a fast which is good
enough for testing.
--
Ticket URL: <http://trac.sagemath.org/ticket/15915#comment:7>
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.
