稀疏矩陣的 LWE 問題
當矩陣時 LWE 問題容易嗎 $ A $ 稀疏嗎？
回想一下 LWE 問題如下： $ q $ 是一個素數，讓 $ \chi $ 是一個分佈 $ \textit{small} $ 元素超過 $ \mathbb{Z}/q $ ， 然後讓 $ n,m $ 是兩個整數（我們使用的向量的維度）。樣本 $ s \leftarrow \chi^n $ , $ e \leftarrow \chi^m $ 和 $ A \leftarrow \mathbb{Z}/q^{m \times n} $ , 其中元素 $ A $ 隨機均勻採樣。讓 $ t=As + e $ .
給定 $ A $ 和 $ t $ ， 尋找 $ s $ .
在一些合理的假設下，這個問題被認為是困難的 $ q $ , $ \chi $ , $ n $ , $ m $ .
我的問題是 - 什麼是 $ A $ 是一個（有點）稀疏矩陣，例如 $ n=m $ ， 和 $ A $ 有 $ \approx\sqrt{n} $ 每列中的非零元素，並且每個非零元素是 $ \pm1 $ . 問題仍然很難嗎？還是問題變得微不足道？如果我增加怎麼辦 $ m $ 從 $ m=n $ 更大的東西？
首先我們應該注意到這個 LWE 問題有很多解決方案，而 LWE 問題通常只有一個。讓 $ u_i $ 成為 $ i $ 位置為條目 1 的標準基向量 $ i $ 其他位置為零。然後 $$ (s’,e’):=(s+u_i,e-Au_i) $$ 滿足 $ As’+e’=t $ 和 $ s’ $ 不同於 $ s $ 在單個位置上減 1，而 $ e’ $ 不同於 $ e $ 是 $ O(\sqrt n) $ 最多 1 個位置。此解決方案與 $ (s,e) $ 從高斯分佈中得出，除非 $ \sigma $ 確實很小。應該清楚如何產生一個更大的家庭。
此外，很容易找到這樣的解決方案。一種攻擊 LWE 的老派方法是花費大量計算來為通過增 $ A $ 創建以下基礎 $$ \left[\begin{matrix}A&I\ qI & 0\\end{matrix}\right] $$ 然後使用 Euchner-Schnorr 列舉來解決目標的閉向量問題 $ (t,0) $ 因向量而異 $ (-e,s) $ . 除非 $ q $ 非常小，通過選擇非常稀疏的 $ A $ 你正在為第一個給出的這個增廣晶格的一個子晶格提供一個壯觀的基礎 $ n $ 行（向量是 $ L_2 $ -規範 $ O(\sqrt n) $ 增廣晶格是維數 $ 2n $ 和行列式 $ q^n $ ）這將導致一個非常容易的列舉問題（進一步受到對條目大小的限制的幫助） $ s $ 和 $ e $ 從問題設置中），這將很快出現許多解決方案之一。考慮這一點的一種方法是觀察 $ t $ 幾乎可以肯定沒有通過減少模數來改變 $ q $ 這意味著解決方案族都位於我們的具有壯觀基礎的子晶格中。
從密碼學的角度來看，基於私鑰值的系統 $ s $ 將導致一系列等效的私鑰，這些私鑰也可用於扮演合法使用者的角色。同樣，恢復其中一個私鑰確實非常容易。
增加 $ m $ 不會消除這些問題，因為我總是可以扔掉決賽 $ m-n $ 的條目 $ t $ .