1

I am trying to understand the Basic Enumeration algorithm of BKZ algorithm for lattice reduction.

At this point I understand all the algorithm except line 8 where we set $u_t \leftarrow \text{round}(c_t)$.

This step corresponds when we move down in the tree, which can be interpreted as a "good / forward" step, and what I don't understand is why to go to the node $\text{round}(c_t)$.

I mean, to go up we use the zig-zag pattern, and for going down we use a different thing.

Thanks for helping!

enter image description here

The algorithm in the image is in https://eprint.iacr.org/2010/097.pdf

Leafar
  • 1,723

1 Answers1

1

The step $u_t = \lfloor c_t \rceil$ basically means the algorithm starts with the guess for the coefficient $u_t$ that would lead to the shortest lattice vector.

Note that $\mathbf{v} = \sum_{i=t+1}^n u_i \mathbf{b}_i$ is the current combination of basis vectors we are considering, and $c_t = \sum_{i=t+1}^n u_i \mu_{i,t}$ is the length of $\mathbf{v}$ projected onto $\mathbf{b}_t$ - the shortest combination that can be formed by $\mathbf{v}$ and a multiple of $\mathbf{b}_t$ is by choosing $u_t = -\lfloor c_t \rceil$. (As noted in the comments, there is probably a minus sign missing in the paper.)

And the reason why you'd want to optimize this is that if, after choosing $u_t = -\lfloor c_t \rceil$ we already have $\ell_t > A$, then we can skip this entire branch of the tree. If we started with a different choice for $u_t$, we would not know yet that we can trim this entire part of the tree.

TMM
  • 9,976
  • By the way, I'm not sure if you'd want to take $-u_t$ as the coefficient and if this is a typo with the sign in the paper or not. – TMM Dec 16 '16 at 19:44
  • I think that I have understand, but as you said in comment, we must have $u_t \leftarrow - \lfloor c_t \rceil$ with the negative sign isn't it? – Leafar Dec 16 '16 at 20:07
  • @Leafar Yes, I think that's a mistake in the paper. As in line 4 in the algorithm, you compute $\ell_t = \ell_{t-1} + (u_t + c_t)^2 |\mathbf{b}_t^*|^2$ as the length of the vector so far, and you want to go from small to large. And clearly the quantity is minimized (as a function of $u_t \in \mathbb{Z}$) by taking $u_t = -\lfloor c_t \rceil$. – TMM Dec 16 '16 at 20:10