在 Miccincio-Peikert-2012 晶格活板門中證明 LWE 反演
我正在查看https://eprint.iacr.org/2011/501中的格子活板門結構。
總而言之，假設我們有一個矩陣 $ G $ 在哪裡，在輸入 $ b $ ，我們可以有效地找到 $ (s,e) $ 這樣 $ s^TG+e^T=b^T $ . 那麼對於可逆 $ H $ , 和一個隨機 $ \overline{A} $ ，我們產生一個矩陣 $ A $ 經過 $$ A = [\overline{A} | HG - \overline{A}R] $$ 對於一些隨機的 $ R $ . 這具有以下屬性 $ A\begin{pmatrix} R\ I\end{pmatrix} = HG $ .
然後 LWE 反演為 $ A $ 給出如下：我們從一些 $ b $ . 我們首先計算 $ \hat{b}^T = b^T\begin{pmatrix} R\ I\end{pmatrix} $ . 然後我們發現 $ (\hat{s},\hat{e}) $ 這樣 $ \hat{s}^TG+\hat{e}^T=\hat{b}T $ . 然後我們讓 $ s^T = \hat{s}^TH^{-1} $ 和 $ e^T = b^T - s^TA $ 成為 LWE 樣本 $ (s,e) $ 令人滿意的 $ s^TA+e^T = b^T $ 和 $ e $ 小的。
我很清楚，根據定義 $ e^T $ , $ s^TA+e^T=b^T $ 持有。事實上，這對任何人都有效 $ s $ . 所以困難的部分是證明 $ e $ 很小，這就是我無法弄清楚的。
我可以展示的一件事是 $$ \begin{align} e^T\begin{pmatrix} R \ I\end{pmatrix} = & b^T\begin{pmatrix} R \ I \end{pmatrix} - s^TA\begin{pmatrix} R \ I\end{pmatrix}\ = & \hat{b}^T - \hat{s}^TH^{-1}HG\ =& \hat{b}^T - \hat{s}^TG\ = & \hat{b}^T - \hat{b}^T + \hat{e}^T\ = & \hat{e}^T \end{align} $$
因此，如果 $ R $ 是可逆且可對角化的，我可以說 $ e^T $ 就最小奇異值而言必須很小 $ R $ 和大小 $ \hat{e}^T $ . 然而，這似乎不是論文的方法，而是關注最大的奇異值 $ R $ . 他們對定理 5.4 的證明對我來說沒有意義：我不明白他們試圖證明什麼，以及為什麼他們沒有證明這一點 $ e $ 是小。
我們得到一些 $ b^t = s^t A + e^t $ 為了 $ A $ 上述形式和短 $ e $ ，並希望恢復 $ s $ （這將立即給我們 $ e $ 以及）。如果 $ e $ 足夠短，那麼 $ \hat{b}^t = (s^t H) G + \hat{e} $ 對於一些足夠短的 $ \hat{e} $ . （這是我們使用展開式或頂部奇異值的界限的地方 $ R $ .) 因此，LWE 逆變器用於 $ G $ 會恢復 $ s^t H $ （和 $ \hat{e} $ )，其中原始 $ s $ 可以通過恢復 $ H^{-1} $ .
非常重要的是 $ e $ 足夠短，以確保 $ \hat{e} $ 足夠短。如果後者太長，則LWE逆變器為 $ G $ 可能會返回錯誤的答案 $ s^t H $ , 導致錯誤 $ s $ 因此是錯誤的，可能很長 $ e $ .