Sabre 密鑰交換中使用的捨入函式
在Sabre: Module-LWR based key exchange中，作者使用了一個舍入函式，稱為 $ \textit{bits} $ ，定義（在第 3 頁）如下：
$ bits(x, i, j) $ ， 和 $ j \leq i $ , 給出 $ j $ 正整數的連續位 $ x $ 結束於 $ i $ -th 索引（假設在 $ 0 $ -th 索引），產生一個整數 $ \mathbb{Z}_{2^{j}} $ .
這個舍入函式實際上是如何工作的？它與Learning with Rounding中通常使用的捨入函式有什麼關係， $ \left\lfloor x \right\rceil_p = \left\lfloor \frac{p}{q}\cdot x\right\rceil\bmod p $ ?
如果 $ p $ 和 $ q $ 是 2 的冪，就像在 Saber 中一樣，然後乘以除以 $ p $ 和 $ q $ 相當於簡單的位移操作。
在軍刀中， $ p = 2^{10} $ 和 $ q = 2^{13} $ . 因此， $ p/q = 1/2^3 $ 和 $ x/8 $ 可以通過右移 3 位來計算。使用 $ bits $ 符號， $ \frac{p}{q}x = bits(x, \log(p/q), \log p) $ .
但我們可以做得更好，還可以根據位函式計算舍入操作。右移一些位相當於取地板操作。我們可以用地板來表示舍入， $ \lfloor x \rceil = \lfloor x + 1/2\rfloor $ （在哪裡 $ \lfloor x \rceil $ 表示四捨五入到最接近的整數，並且 $ \lfloor x \rfloor $ 是整數下限 $ x $ ).
同樣的推理也可以應用在這裡。我們想添加 $ 1/2 $ 在地板操作之前。由於我們將所有內容除以 $ 8 $ , 如果我們添加 $ 4 $ 到原來的值 $ x $ ， 我們獲得 $ p/q( x + 4) = x/8 + 1/2 $ ， 如預期的。
因此， $ \left\lfloor \frac{p}{q} x \right\rceil = bits(x + (\log p)/2, \log(p/q), \log p) $ .
請注意，這僅是因為 $ p $ 和 $ q $ 是二的冪。如果 Sabre 選擇了素數模數，則縮放和舍入操作將比簡單的加法和位移操作更複雜。