2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I have little idea of MLWR, but might it just be the floor() function? $\endgroup$
    – cisnjxqu
    Nov 20 '20 at 15:16
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.