Rounding function used in Saber Key Exchange

Question

In Saber: Module-LWR based key exchange, the authors use a rounding function called $\textit{bits}$, defined (in page 3) as follows:

$bits(x, i, j)$, with $j \leq i$, gives $j$ consecutive bits of a positive integer $x$ ending at the $i$-th index (assuming the least significant bit in the $0$-th index), producing an integer in $\mathbb{Z}_{2^{j}}$.

How does this rounding function actually work? How does it relate to the rounding function typically used in Learning with Rounding, $\left\lfloor x \right\rceil_p = \left\lfloor \frac{p}{q}\cdot x\right\rceil\bmod p$?

Answer 1

If $p$ and $q$ are powers of two, as in Saber, then multiplying and diving by $p$ and $q$ amounts to simple bit shift operations.

In Saber, $p = 2^{10}$ and $q = 2^{13}$. Thus, $p/q = 1/2^3$ and $x/8$ can be computed by a right-shift of 3 bits. Using the $bits$ notation, $\frac{p}{q}x = bits(x, \log(p/q), \log p)$.

But we can do better, and also compute the rounding operation in terms of the bits function. Right-shifting by some bits is equivalent to a floor operation. We can express rounding in terms of flooring, with $\lfloor x \rceil = \lfloor x + 1/2\rfloor$ (where $\lfloor x \rceil$ denotes rounding to the closest integer, and $\lfloor x \rfloor$ is the integer floor of $x$).

The same reasoning can be applied here. We want to add $1/2$ before the flooring operation. Since we are dividing everything by $8$, if we add $4$ to the original value $x$, we obtain $p/q( x + 4) = x/8 + 1/2$, as desired.

Hence, $\left\lfloor \frac{p}{q} x \right\rceil = bits(x + (\log p)/2, \log(p/q), \log p)$.

Note that this works only because $p$ and $q$ are powers of two. If Saber had chosen prime moduli, the scaling and rounding operations would be more involved than a simple addition and bitshift operation.