Lattice reduction question regarding the capability of LLL and BKZ 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?
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.