Flatten如何真正使LWE中向量矩陣的係數變小
在來自錯誤學習的同態加密中：概念上更簡單，漸近更快，基於屬性，紳士等。al 將Flattening定義如下；
讓 $ \vec{a},\vec{b} $ 是某個維度的向量 $ k $ 超過 $ \mathbb{Z}_q $ . 讓 $ \ell = \lfloor \log_2q \rfloor +1 $ 和 $ N = k \cdot \ell $
定義 $ \operatorname{BitDecomp}(\vec{a}) $ 成為 $ N $ -維向量 $ = (a_{1,0},\ldots,a_{1,\ell-1} \ldots,a_{k,0},\ldots,a_{k,\ell-1}) $ ， 在哪裡 $ a_{i,j} $ 是個 $ j $ -th 位 $ a_i $ 的二進製表示，按位順序從最低有效到最高有效。
為了 $ \vec{a}’ = (a_{1,0},\ldots,a_{1,\ell-1}, \ldots,a_{k,0},\ldots,a_{k,\ell-1}) $ ， 讓 $$ \operatorname{BitDecomp}^{-1}(\vec{a}) = (\sum 2^j\cdot a_{1,j}, \ldots, \sum 2^j\cdot a_{k,j}) $$是的倒數 $ \operatorname{BitDecomp} $ , 但當輸入不是 $ 0/1 $ 向量。
這只不過是通常的分解為位，並且數據已經以分解的方式儲存。
為了 $ N $ 維向量 $ \vec{a}’ $ ， 讓 $ \operatorname{Flatten}(\vec{a}’) = \operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1} (\vec{a}’)) $ .
什麼時候 $ A $ 是一個矩陣，讓 $ \operatorname{BitDecomp}(A), \operatorname{BitDecomp}^-1(A) $ ， 或者 $ \operatorname{Flatten}(A) $ 是通過將操作應用於每一行形成的矩陣 $ A $ 分開。
一個有趣的特點 $ \operatorname{Flatten} $ 是它使向量矩陣的係數 $ small $ 在不影響其產品的情況下 $ \operatorname{Powersof2}(\vec{b}) $ ，並且不知道 $ \vec{b}’ $
我不清楚如何 $ \operatorname{Flatten} $ 製作向量矩陣的係數 $ \boldsymbol{small} $ . 我看到這兩個操作， $ \operatorname{BitDecomp} $ 和 $ \operatorname{BitDecomp} $ , 只是彼此的倒數。有人可以詳細說明我在這裡缺少什麼嗎？
您錯過的重要部分是第一個塊的最後一句話：
$ BitDecdomp^{-1} $ 仍然是明確定義的，如果它沒有得到 $ N $ 維位向量（所有條目來自 $ {0,1} $ ).
在第二個引用中， $ Flatten $ 被定義為首先使用 $ BitDecdomp^{-1} $ ，然後使用 $ BitDecomp $ . 所以輸出 $ Flatten $ 將是一個位向量。僅當輸入也是來自的向量時，這將與輸入相同 $ {0,1} $ - 但它是為任何向量定義的 $ \mathbb{Z}_q $ .
這裡的基本思想是使用從較小域到較大域的延續。