# Rounding function used in Saber Key Exchange

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$$?

• I have little idea of MLWR, but might it just be the floor() function? Nov 20 '20 at 15:16

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.