I know that Sieve Algorithms are good attacks against CKKS Encryption Techniques.
I want to know the exact expression of the complexity of the Sieve Algorithm attacks, according to Miklós Ajtai, Ravi Kumar, and D. Sivakumar, A Sieve Algorithm for the Shortest Lattice Vector Problem (PDF via CiteSeerX, official DOI).
Is it $2^{c n}$ where $n$ is the lattice dimension $c$ is a constant?
From a pure operations count I believe that the best algorithm for lattice-sieving for short vectors uses locality sensitive filtering and is due to Becker et al in New directions in nearest neighbor searching with applications to lattice sieving with these methods a complexity of $(3/2)^{n/2+o(n)}\approx 2^{0.292n+o(n)}$ operations can be achieved. Note that this estimate is log-asymptotic and the $o(n)$ term can have a dramatic variational effect. Note also that this approach minimises operations by using a similar amount of memory. The large memory usage can be practically challenging and there are other parts of the parameters space which use less memory, but more operations.
The original AKS description used naive search for reducible pairs without the use of locality sensitive hashing or filtering. An analysis by Nguyen and Vidick Sieve Algorithms for the Shortest Vector Problem are Practical suggested a complexity of $(4/3+\epsilon)^n\approx 2^{0.415n}$ polynomial time operations and $(4/3+\epsilon)^{n/2}\approx 2^{0.2075n}$ memory.
