what to include

[Martin Albrecht]

Hi there,

= Polly Cracker =

I thought about including PollyCracker with Noise again and I came to the
conclusion that we shouldn't include it. It doesn't really fit in that well as
we would have to return multivariate polynomials instead of vectors to account
for the structure (of the secret). We could return linearised samples (==
vectors) but that would mean we're not actually returning Polly Cracker
samples.

Hence, I propose to drop Polly Cracker. I'll consider submitting it to Sage
separately (and we published a generator for Polly Cracker for Sage already
anyway)

= Ring-LWE =

We haven't done anything on this yet. We definitely should include it.

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de

[Florian Göpfert]

Hi,

I only know the Ring-LWE variant used by Stehlé and Steinfeld in their
"Making NTRUEnrypt and NTRUSign as Secure as Standard WorstCase Problems
over Ideal Latties"-paper, but I would probably need help to implement
it (at least to implement it efficient), as it needs complex discrete
Fourier transforms (and other stuff I never implemented). The other
opportunity would be to wait for Daniel. Or does anybody know an easier
variant of Ring-LWE?

Florian

[Michael Schneider]

Hi,

FFT is only required for fast polynomial multiplication; I guess Florian
and I can give a try to implement the ringLWE-Sampler tomorrow.




The lindner_peikert() routine gives an error in find_root() everytime I
call it, independent of the parameters m and n:


/var/tmp/root/sage-5.0-linux-64bit-ubuntu_10.04.3_lts-x86_64-Linux/local/lib/python2.7/site-packages/sage/numerical/optimize.pyc
in find_root(f, a, b, xtol, rtol, maxiter, full_output)
70 """
71 try:
---> 72 return
f.find_root(a=a,b=b,xtol=xtol,rtol=rtol,maxiter=maxiter,full_output=full_output)
73 except AttributeError:
74 pass

/var/tmp/root/sage-5.0-linux-64bit-ubuntu_10.04.3_lts-x86_64-Linux/local/lib/python2.7/site-packages/sage/symbolic/expression.so
in sage.symbolic.expression.Expression.find_root
(sage/symbolic/expression.cpp:31805)()

/var/tmp/root/sage-5.0-linux-64bit-ubuntu_10.04.3_lts-x86_64-Linux/local/lib/python2.7/site-packages/sage/numerical/optimize.pyc
in find_root(f, a, b, xtol, rtol, maxiter, full_output)
88 else:
89 return s
---> 90 raise RuntimeError, "f appears to have no zero on
the interval"
91 # If we found such an s, then we just instead find
92 # a root between left and s or s and right.

RuntimeError: f appears to have no zero on the interval

[Martin Albrecht]

Hey,

I just checked in a refactoring because I noticed that it might be useful to
get q and stddev out for Regev and LindnerPeikert, so now I propose the
interface works like this:

sage: samples(10, 5, Regev) # 10 samples for n=10 and Regev's parameters
sage: samples(10, 5, "Regev") # same but one doesn't have to import the class

sage: lwe = Regev(5)
sage: samples(10, 5, lwe) # it also accepts instances

As for Lindner-Peikert it seems it fails for small n:

sage: LindnerPeikert(5)
...

RuntimeError: f appears to have no zero on the interval

sage: LindnerPeikert(10)
...

RuntimeError: f appears to have no zero on the interval

sage: LindnerPeikert(20)
LWE(20, 2053, DiscreteGaussianSamplerRejection(3.600954, 53, 4), 'uniform')

It is pretty annoying that Sage throws a runtime error instead of a
ValueError. In any case, we should catch this error and pick some value
instead.

[Martin Albrecht]

Hi,

I should mention that Sage has asymptotically fast polynomial multiplication
mod q (not that it matters for the dimensions we're probably going to
consider)

On Monday 18 Mar 2013, Michael Schneider wrote:

> Hi,
>
> FFT is only required for fast polynomial multiplication; I guess Florian
> and I can give a try to implement the ringLWE-Sampler tomorrow.
>
>
>
>
> The lindner_peikert() routine gives an error in find_root() everytime I
> call it, independent of the parameters m and n:
>
>
> /var/tmp/root/sage-5.0-linux-64bit-ubuntu_10.04.3_lts-x86_64-Linux/local/li
> b/python2.7/site-packages/sage/numerical/optimize.pyc in find_root(f, a, b,
> xtol, rtol, maxiter, full_output)
> 70 """
> 71 try:
> ---> 72 return
> f.find_root(a=a,b=b,xtol=xtol,rtol=rtol,maxiter=maxiter,full_output=full_ou
> tput) 73 except AttributeError:
> 74 pass
>

> /var/tmp/root/sage-5.0-linux-64bit-ubuntu_10.04.3_lts-x86_64-Linux/local/li
> b/python2.7/site-packages/sage/symbolic/expression.so in
> sage.symbolic.expression.Expression.find_root
> (sage/symbolic/expression.cpp:31805)()
>
> /var/tmp/root/sage-5.0-linux-64bit-ubuntu_10.04.3_lts-x86_64-Linux/local/li