3
$\begingroup$

I've been reading How to estimate the hardness of SIS instances? and following some of its sources, and I want to confirm a few things.

LLL algorithm runs in polynomial time, but isn't capable of producing arbitrarily small basis, and is therefore not very relevant in cryptanalysis in most lattice-based schemes. Is that correct?

BKZ algorithm invokes a SVP (Shortest Vector Problem) oracle polynomial number of times, and the lower-bounded of the norm of the basis it produces is inversely proportional to the block size the SVP oracle operates on, regardless of the norm of the input basis; and the SVP oracle it uses runs in time exponential to the block size. Is that correct?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Yes, if you instantiate the SVP oracle in BKZ using sieving then the cost is exponential in time and memory. (If you instantiate it using enumeration then the cost is $k^{1/8\,k + o(k)}$). The norm of the output vector is expected to be $\delta_k^{d-1} \cdot \operatorname{Vol}(\Lambda)^{1/d}$ with $\delta_k \approx GH(k)^{1/(k-1)}$. Here $\operatorname{Vol}(\Lambda)$ is the volume of the lattice, and $GH(k) \approx \sqrt{k/(2\pi e)}$ is the Gaussian heuristic for a lattice with volume 1. This does not depend on the norm of the input basis.

Improve this answer
$\endgroup$
3
  • $\begingroup$ $\operatorname{Vol}(\Lambda)$ - > $\operatorname{Vol}(\Lambda)^{\mathbf 1/d}$ $\endgroup$
    – LeoDucas
    Oct 7, 2020 at 7:06
  • $\begingroup$ Thanks for this Léo $\endgroup$
    – Martin R. Albrecht
    Oct 7, 2020 at 11:05
  • $\begingroup$ Nevertheless LLL is important in cryptanalysis, serving as generic function to find short vectors under certain conditions. There is plenty of work that simply requires a polynomial time lattice reduction, where the lattice can be constructed in such a way that LLL is successful. And since LLL was the first, I believe it often takes this role as "generic lattice reduction". $\endgroup$
    – Fleeep
    Oct 8, 2020 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.