announcing the Ring-LWE challenges

[Christopher J Peikert]

It's a great pleasure to finally announce a project that has been in

progress for several months: Ring-LWE challenges!  This is joint work

with my tireless and accomplished student Eric Crockett, which uses

our Λ ○ λ (pronounced "L O L") framework for lattice- and ring-based

cryptography.  (See https://hackage.haskell.org/package/lol )

We have prepared challenges for 516 concrete instantiations of

Ring-LWE/LWR on cyclotomic rings, covering a wide variety of

parameterizations and estimated hardness levels.  To give convincing

evidence that the challenges were properly generated, we designed and

implemented a non-interactive, publicly verifiable "cut and choose"

protocol, which is in progress at this very moment. (The "random

beacon" phase will occur on Wed 17 Aug 2016, and we will complete the

protocol on Fri 19 Aug 2016).

See our website for all the details, including the accompanying paper

and a link to the challenges archive (please seed the torrent!):

   https://web.eecs.umich.edu/~cpeikert/rlwe-challenges

Sincerely yours in cryptography,

Chris

PS: for the cut-and-choose protocol, I am obliged to point out that

our challenges archive, corresponding to the "commit" phase of the

protocol, was timestamped on 14 Aug 2016 via the Bitcoin blockchain:

http://www.originstamp.org/s/07cdf7445c9d178c8b135a4247caa1435320c1048ee8c6348914a9155757dcef

[jacob.alperin-sheriff]

Disclaimer: This does not necessarily represent the official view or policy of NIST or the federal government.

Some thoughts:

I think it would be very useful if you were to also issue some challenges over (the ring of integers of) some non-cyclotomic number fields as well. In particular, I would like to see it over examples of number fields that Dan Bernstein has been advocating here for a while as superior to cyclotomic rings (e.g. those generated by the roots of f(x)=x^p-x-1 ), so we can see if any algorithms that come out of it perform (significantly) better in one case or the other.

These challenges are also only for the search version of ring-LWE, whereas the security of cryptosystems is generally based on the decision version of the problem ...

Search-to-decision reductions do exist for the problem over cyclotomic fields, but they are not super tight and as published, are limited to certain moduli (although I believe they can be extended to all moduli via “modulus switching,” this comes at an additional cost in the relative magnitude of the error, and as far as I know such a reduction has not actually been published yet). Moreover, for number fields of the type proposed by Bernstein, I don’t know that any such search-to-decision reductions exist at all.

How much extra work would these additional challenges take to release? 

[Christopher J Peikert]

I think it would be very useful if you were to also issue some challenges over (the ring of integers of) some non-cyclotomic number fields as well. In particular, I would like to see it over examples of number fields that Dan Bernstein has been advocating here for a while as superior to cyclotomic rings (e.g. those generated by the roots of f(x)=x^p-x-1 ), so we can see if any algorithms that come out of it perform (significantly) better in one case or the other.

It would certainly be good to have such challenges, but currently we (Eric and I) don't have the code to create them in our framework.

Ring-LWE is well-defined over such rings, and search versions are even supported by worst-case hardness theorems, but the associated error distributions look rather different from the ones used in (say) NTRU Prime.  (For one, they are significantly wider.)

These challenges are also only for the search version of ring-LWE, whereas the security of cryptosystems is generally based on the decision version of the problem ...

Yes, this is discussed in Section 1.1 of the paper (page 4).  It seems quite tricky to give practical challenges for decision problems -- whether for lattice problems or otherwise -- in the cryptographic regime where even a tiny adversarial advantage is considered a success.

(As far as I know, no challenges have ever been issued for any decision problem used in crypto.)

How much extra work would these additional challenges take to release?

Not a little, but perhaps not a lot either.  We'd be happy to take contributions!  (All our code is free/open source and available on GitHub.)

[damien...@gmail.com]

Dear Jacob,

I'm just replying on this. 

> Search-to-decision reductions do exist for the problem over cyclotomic fields, but they are not super tight and as published, are limited to certain moduli (although I believe they can be extended to all moduli via “modulus switching,” this comes at an additional cost in the relative magnitude of the error, and as far as I know such a reduction has not actually been published yet)

The reduction is given in this article. 

  http://perso.ens-lyon.fr/damien.stehle/downloads/MSIS.pdf 

Published as  Des. Codes Cryptography 75(3):565-599 (2015).

Best regards, 

Damien

[jacob.alperin-sheriff]

I don't know why that slipped my mind. I guess I was focusing more on the module lattice definition when I read that paper. Sorry.