Core-SVP Hardness of Kyber

Question

This question is with reference to the python file model_BKZ.py provided in the GitHub repository https://github.com/pq-crystals/security-estimates/blob/master/model_BKZ.py

In this file, there is function called construct_BKZ_shape. I am not able to understand what it is doing. I have read BKZ algorithm from this paper and the YouTube lecture by Prof. Damien Stehlé.

I am not able to link the mathematical theory I read through these sources with the code provided here. Can somebody please explain this code from the mathematical point of view? What we are trying to do through this code?

def construct_BKZ_shape(q, nq, n1, b):
    """ Simulate the (log) shape of a basis after the reduction of
        a [q ... q, 1 ... 1] shape after BKZ-b reduction (nq many q's, n1 many 1's)
        This is implemented by constructing a longer shape and looking
        for the subshape with the right volume. Also outputs the index of the
        first vector <q, and the last >q.

        # Note: this implentation takes O(n). It is possible to output
        # a compressed description of the shape in time O(1), but it is much
        # more prone to making mistakes

    """
    d = nq+n1
    if b==0:
        L = nq*[log(q)] + n1*[0]
        return (nq, nq, L)


    slope = -2 * log(delta_BKZ(b))
    lq = log(q)
    B = int(floor(log(q) / - slope))    # Number of vectors in the sloppy region
    L = nq*[log(q)] + [lq + i * slope for i in range(1, B+1)] + n1*[0]

    x = 0
    lv = sum (L[:d])
    glv = nq*lq                     # Goal log volume

    while lv > glv:                 # While the current volume exceeeds goal volume, slide the window to the right
        lv -= L[x]
        lv += L[x+d]
        x += 1

    assert x <= B                   # Sanity check that we have not gone too far

    L = L[x:x+d]
    a = max(0, nq - x)             # The length of the [q, ... q] sequence
    B = min(B, d - a)              # The length of the GSA sequence

    diff = glv - lv
    assert abs(diff) < lq               # Sanity check the volume, up to the discretness of index error
    for i in range(a, a+B):        # Small shift of the GSA sequence to equiliBrate volume
        L[i] += diff / B
    lv = sum(L)
    assert abs(lv/glv - 1) < 1e-6        # Sanity check the volume

    return (a, a + B, L)

Answer 1

This code is attempting to model the size of the logarithms of the norms of the Gram-Schmidt vectors associated with a BKZ reduced basis under the Geometric Series Assumption where before reduction the basis was of the form

$$\begin{bmatrix}A & I_{n_1}\\ qI_{n_q} & 0\end{bmatrix}.$$

In lattice basis reduction, for a basis $\mathbf b_1,\ldots, \mathbf b_d$ we typically also keep track of its Gram-Schmidt orthogonalisation $\mathbf b^*_1,\ldots,\mathbf b^*_d$. Reduction processes are meant to produce bases where the Gram-Schmidt vectors do not become too small in norm. An empirical observation (see the remarks at the end of section 2 of the Chen and Nguyen paper) is the "Geometric Series Assumption" that reduction processes such as LLL or BKZ tend to produce reduced bases where the norms of the $\mathbf b^*_i$ decrease as an approximate geometric progression: $|\mathbf b^*_i|\approx \delta^{i-1}|\mathbf b^*_1|$ for some $\delta<1$ dependent on the block size (related to the delta_BKZ(b) in the code). This observation is subject to the limitation that Gram-Schmidt norms should not be bigger than the biggest initial vector, nor smaller than 1 for lattices with integer entries. If we plot the logarithm of the G-S norms against the index, the GSA means that we should see an approximate piecewise linear plot that can take one of the following shapes:

The exact shape and parameters are determined by the slope (which is $\log\delta$) and the area beneath the plot (which is the log of the determinant of the lattice).

In the code, the exact shape is found by notionally constructing a piecewise linear plot of $n_q+B+n_1$ width where $B$ is the width of the base of right-angled triangle with height $\log q$ and hypotenuse with slope $\delta$. They then look for a window of width $d=n_q+n_1$ of this plot where the area within the window and beneath the plot is equal to the log of the determinant of the lattice. This is the desired shape.

Here's a legend for some of the variable names in terms of the above description

Variable	Meaning
d	$d$ the dimension of the lattice
nq	$n_q$ the number of columns in the $qI$ sub matrix
n1	$n_1$ the number of columns in the $I$ sub matrix
slope	$\log\delta$ the notional slope of the diagonal part of the plot
lq	$\log q$ the upper bound for the size of the log of the Gram-Schmidt norms
B	$B$ the width of a sloped region descending from $\log q$ to 0 with slope $\log \delta$
L	A list of "$y$-values" for the wide plot of width $n_q+B+n_1$
x	The offset into the wide plot of our window
lv	The area beneath the plot in our current window
glv	The target area which is the log of the determinant of our lattice (which is $n_q\log q$)

Because the plot is more accurately described as a histogram with the window sliding one unit at a time, a final adjustment of the sloped region is required to make the areas match. This is the meaning of the lines beginning diff = glv - lv and finishing assert abs...

Finally note this code does not behave correctly for the last shape illustrated (this may be due to restriction of the values of $b$, $n_q$ and $n_1$ under consideration). I would advise against directly reusing this for fully general lattice modelling. As the programmer notes, there are quicker computations of the shape, but it is easy to get things wrong.