Skip to main content
Cryptography

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • 6
    $\begingroup$ My quick educated guess is that LLL reduction does not give a good enough solution (i.e., short enough vectors) to break DGHV. Remember that LLL only gives an exponential (in the dimension) approximation to the shortest vector. Breaking DGHV would require a much smaller approximation, and thus much higher running time—exponential in $\lambda$, if all the calculations are right. $\endgroup$ Commented Oct 2, 2018 at 21:58
  • $\begingroup$ It gives the right answer iff t > the bound I stated $\endgroup$ Commented Oct 2, 2018 at 21:59
  • 2
    $\begingroup$ But here “Reducing a $t$-dimensional lattice” does not mean just running LLL on it; you need a shorter vector than LLL would give, which requires more time to find. Your calculations don’t appear to have accounted for the approximation factor required to break DGHV. $\endgroup$ Commented Oct 2, 2018 at 22:02
  • 1
    $\begingroup$ From page 5, the bound on t is obtained by comparing the gap between the sizes of our target vector and the next independent shortest vector in the lattice. LLL solves the AGCD if the ratio of their norms is greater than $2^{t/2}$, because LLL is guaranteed to find a vector within that bound of the shortest vector. $\endgroup$ Commented Oct 2, 2018 at 22:44
  • 1
    $\begingroup$ As far as I can tell your explanation below appears to make sense. It’s a bit puzzling because I had thought that the formulas were claimed to yield (asymptotically) exponential $2^\lambda$ security for parameters that were polynomial in $\lambda$. But LLL has a polynomial running time for such parameters. $\endgroup$ Commented Dec 6, 2018 at 2:02