關於 CRYSTALS-Kyber 中壓縮和解壓的問題
我目前正在研究Kyber Paper。我有一個關於第 2.2 節壓縮和解壓的問題，但首先我想引用以下聲明：
壓縮和解壓。我們現在定義一個函式 $ \text{Compress}_q (x, d) $ 需要一個元素 $ x ∈ \mathbb{Z}_q $ 並輸出一個整數 $ {0,…, 2^d − 1} $ ， 在哪裡 $ d < \lceil\log_2(q) \rceil $ . 我們還定義了一個函式 $ \text{Decompress}_q $ , 這樣 $$ x’ =\text{Decompress}_q(\text{Compress}_q(x,d),d) \quad (1) $$是一個接近的元素 $ x $ - 進一步來說 $ |x’-x \text{ mod}^{\pm} q|\leq B_q := \lceil \frac{q}{2^{d+1}} \rfloor $ . 滿足這些要求的函式定義為： $$ \text{Compress}_q(x,d)= \lceil (2^d / q) \cdot x \rfloor \text{ mod}^+ 2^d , \ \text{Decompress}_q(x,d) = \lceil (q/2^d) \cdot x \rfloor $$如果 $ x’ $ 是一個函式 $ x $ 如方程式。(1)，那麼對於隨機選擇的 $ x\leftarrow \mathbb{Z}_q $ , 的分佈 $$ x’ - x \text{ mod}^\pm q $$在最多數量級的整數上幾乎是一致的 $ B_q $ .
- 我的第一個問題是關於不平等的 $ |x’-x \text{ mod}^{\pm} q|\leq B_q := \lceil \frac{q}{2^{d+1}} \rfloor $ ，如何詳細得出這個估計？我不太明白你怎麼能說數量小於中心二項分佈 $ B_q $ .
- 我的第二個問題是關於 Compress 和 Decompress 函式的定義（來自“滿足這些要求的函式…… ”）。我現在看不到這些功能如何滿足要求，如果有人能解開這個問題，那對我有很大的幫助。
對於這些問題的有用答案，我將非常高興。
首先，了解這裡 $ B_q $ 不代表居中二項分佈，而是整數值 $ \lceil\frac q{2^{d+1}}\rfloor $ .
接下來，考慮如下壓縮和解壓縮函式可能會有所幫助：
考慮分數 $ x/q $ 並找到分母最近的分數 $ 2^d $ ，假設這是 $ c/2^d $ 然後 $ \mathrm{Compress}(x,d)=c\mod^+2^d $ .
考慮分數 $ x/2^d $ 並找到分母最近的分數 $ q $ ，假設這是 $ b/q $ 然後 $ \mathrm{Decompress}(x,d)=b $ .
因為 $ q>2^d $ 每個分數都有分母 $ c/2^d $ 是區間的中心 $ ((2c-1)/2^{d+1},(2c+1)/2^{d+1}) $ 其中包含 $ \lfloor q/2^d\rfloor $ 或者 $ \lceil q/2^d\rceil $ 帶分母的分數 $ q $ 在裡面。這些分數中的每一個的分子（並且沒有其他整數 $ 0,q-1) $ ) 將映射到 $ c $ 在壓縮下，而 $ \mathrm{Decompress}(c,d) $ 將映射到分子列表中途的分子。最壞的情況是當我們從 $ x $ 它位於分子列表的最末端。在這種情況下，Compress then Decompress 將我們映射到分子列表中部的分子頂部，因此最多為 $ \lceil q/2^{d+1}\rfloor $ 遠離我們開始的地方。
沒有比例因子可能最容易理解這一點（一般技術適用於任意晶格）。考慮簡單的格子 $ L = \mathbb{Z}^n $ . 可以唯一分解 $ \mathbb{R}^n $ 作為 $ \mathbb{Z}^n + [-1/2, 1/2)^n $ . 這是通過採取一個點來完成的 $ \vec x\in\mathbb{R}^n $ 並將其分成其“整數部分”（在 $ \mathbb{Z}^n $ ）和“小數部分”（在 $ [-1/2, 1/2)^n $ ）。這就是說可以壓縮 $ \vec x\in\mathbb{R}^n $ 進入一個點 $ \mathbb{Z}^n $ ，直到有界誤差 $ [-1/2, 1/2)^n $ .
Kyber 的壓縮機製本質上是通過以下方式“擴大規模” $ (q/2^d) $ . 這就是說一個唯一的分解 $ (q/2^d)\mathbb{R}^n = \mathbb{R}^n $ 成一對 $ (q/2^d)\mathbb{Z}^n + [-(q/2^d)/2, (q/2^d)/2)^n $ ，即變成“整數部分” $ (q/2^d)\mathbb{Z}^n $ ，以及有界大小的“小數部分”（由 $ q/2^{d+1} $ 在每個座標中）。這就是說，如果你了解事情的情況 $ q = 2^d $ ，應該會簡單很多，然後可以嘗試泛化為 $ q\neq 2^d $ .