為什麼學習錯誤需要一堆樣本？

解決具有平均情況復雜度的錯誤學習（LWE）與解決具有最壞情況復雜度的 SVP 一樣困難。

LWE 要求 $ n $ 維晶格和 $ m $ 它的樣本，Decisional-LWE 是

$ (\mathbf{A},\mathbf{sA+e}) \approx (\mathbf{A},\mathbf{r}) $

我的問題是為什麼隨機矩陣是形式 $ \mathbf{A} \in \mathbb{Z}_q^{m\times n} $ ( $ m >> n $ )?

是 $ m=1 $ 容易解決？

我認為在 Ring LWE 的情況下， $ m=1 $ 能行得通。

1. 矩陣中的行數 $ \textbf{A} $ 顯示 LWE 樣本的數量和 $ m=1 $ 意味著對手只能訪問一個樣本。這將是一個幼稚的對手模型，不適合評估問題的真實難度。考慮一個更強大的對手模型，一個（看似）更強的定義是假設對手可以訪問任意 $ m $ 獨立樣本。
2. 在 R-LWE 的情況下，單個樣本 ( $ m=1 $ ) 代替 $ n $ （相關）LWE 樣本。

即使我們假設對手只有一個樣本，那麼就像在 LWE 中一樣，找到秘密似乎（直覺上）更難。

引用自：https://crypto.stackexchange.com/questions/50825