gapBDD broken with poly approx factors?

[D. J. Bernstein]

Eldar and Shor have posted a new paper that claims to solve the
following lattice problem efficiently on a quantum computer:

given a lattice L, a vector v, and numbers b = lambda_1(L)/n^17,
a = lambda_1(L)/n^13 decide if v's distance from L is in the range
[a/2,a] or at most b, where lambda_1(L) is the length of L's
shortest non-zero vector.

Regarding "efficient": the theorem statement appears to claim polynomial
time for this GapBDD problem for exponents 13+epsilon, 17+epsilon.

For comparison, Regev says that the hardness of LWE for exponential q
"is based on the standard assumption that GapSVP is hard to approximate
to within polynomial factors", and that the hardness of LWE for poly q
"is based on slightly less standard (but still quite believable)
assumptions".

Eldar and Shor comment that the GapBDD requirement on v having distance
in [a/2,a] union [b,infty] "yields some implicit information about the
length of the shortest vector of the input lattice". Calling this
"implicit" seems to say that a,b aren't actually required as input, but
I haven't dug into the details yet. Anyway, it's hard to see how anyone
can be confident in GapSVP hardness---or the hardness of "less standard"
assumptions---if GapBDD is broken.

If this paper holds up then it shreds the picture of

approx factor | hardness
---------------+---------------
tiny | NP-hard
poly | hard
subexponential | subexponential
exponential | poly

that is frequently claimed in lattice advertising. Developments in the
last few years have already severely damaged this picture for various
ideal-lattice problems, but the Eldar--Shor attack gets down to poly
time for a poly approximation factor in arbitrary lattices.

This doesn't imply that lattice-based cryptography is broken, but it
does mean that many people were wildly overestimating the importance of
huge approximation factors for breakability. It is no longer defensible,
even in purely asymptotic papers, to say just "polynomial approximation
factor" as if any polynomial were safe. The exponent of the polynomial
is important!

Figuring out the approximation factors in existing systems might be a
nice project for an enterprising student. A simple encryption system is
analyzed in Section 6.5 of https://eprint.iacr.org/2016/360 (with
details in a supplemental PDF on http://anotherlook.ca) but there are
many other systems in the literature---often with much larger
approximation factors.

---Dan

[Alperin-Sheriff, Jacob (Fed)]

You seem to have made a mistake. On the bottom of page 2, their definition of gapBDD (or a problem somewhat stronger than what I would straightforwardly define as gapBDD) involves a promise that the target vector is within distance

[0,b] union [a/2, a], not [a/2,a] union [b, infty]

Or am I misreading it?

--
You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algo...@googlegroups.com.
To post to this group, send email to cryptanalyti...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/20161123145345.25526.qmail%40cr.yp.to.
For more options, visit https://groups.google.com/d/optout.

[D. J. Bernstein]

Alperin-Sheriff, Jacob (Fed) writes:
> [0,b] union [a/2, a], not [a/2,a] union [b, infty]

Sorry, yes, I got the cutoffs backwards. Pictorially (not to scale!) the
promise regarding the distance from v to the nearest lattice point is

0 ......................... b ........ a/2 .................. a
| distance in this interval | | or in this interval |

where b = lambda_1(L)/n^17 and a = lambda_1(L)/n^13. The problem is to
tell whether the distance is in the left part or the right part.

---Dan

[John Schanck]

In the authors' own words "Our proposed algorithm [...] requires an additional promise

that the input vector is at least "somewhat close" to the lattice. We believe that this is

not an artifact of the proof, but goes to the core of the scheme".

I haven't finished checking out the details, but on a first pass it looks like there might be

distance intervals outside of the "very close" interval that have acceptance probability

similar to the "very close" interval. Likewise there will be intervals outside of the

"somewhat close" interval that have rejection probability similar to the "somewhat close"

interval. I'll leave it to your imagination to see how this could undermine the cryptanalytic

utility of the algorithm, meanwhile I'll get back to reading propositions 7 and 8.

Cheers,

John

---Dan

--
You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.

To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algorithms+unsub...@googlegroups.com.
To post to this group, send email to cryptanalytic-algorithms@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/20161123153048.27524.qmail%40cr.yp.to.

[Christopher J Peikert]

To close the loop on this thread, the paper has a serious flaw:
https://groups.google.com/forum/#!topic/cryptanalytic-algorithms/WNMuTfJuSRc

[Alperin-Sheriff, Jacob (Fed)]

Do you or anyone else have any idea when Oded (or the paper’s authors) will give us some idea of what the serious flaw is, and whether or not it’s worth reading at all? Both I and some other colleagues working on NIST’s Post-Quantum Cryptographic initiative were obviously very interested in understanding this work if it survived peer review, and it would be nice to know what the serious flaw is and whether the paper will be wholesale withdrawn or just modified …

On 11/25/16, 9:06 AM, "cpei...@gmail.com on behalf of Christopher J Peikert" <cpei...@gmail.com on behalf of cpei...@alum.mit.edu> wrote:

To close the loop on this thread, the paper has a serious flaw:
https://groups.google.com/forum/#!topic/cryptanalytic-algorithms/WNMuTfJuSRc

--
You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.

To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algo...@googlegroups.com.
To post to this group, send email to cryptanalyti...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/CACOo0QheVKgy1qXLAtvjd0fp2sGt%3DpgEET%2B1fhRRyOvEb6nRWw%40mail.gmail.com.

[Christopher J Peikert]

Some information: the arxiv page for the paper (see
https://arxiv.org/abs/1611.06999 ) now has the following note:

"This paper has been withdrawn by the author due to an error in Fact
7: the concentration of measure of the n-dimensional sinc^2 function
is not a probability of at least 1-n^{-3} for vectors of length at
most n^2, but rather 1 - n^{-1.5} for vectors of length n^3."

Based on a very cursory reading of how Fact 7 is used in the paper, my
hunch is that this affects the post-selection strategy and the "very
close vectors are accepted"/"somewhat close vectors are rejected"
claims.

Sincerely yours in cryptography, Chris

> To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/44EDD2A1-1BF7-4892-A606-BCBB2FD94A75%40nist.gov.