Lwe
證明（環-）LWE 秘密是唯一的
我在 2005 年閱讀了 Regev 關於學習錯誤的論文，他提到 LWE 樣本的秘密是獨一無二的，但我還沒有看到這種說法的證據。有人可以指出我證明這一說法的論文嗎？此外，對於環 LWE 案例，特別是對於兩個 cyclotomics 的冪，秘密總是唯一的嗎？
Regev 的LWE 調查包含證明的草圖。
**算法。**解決 LWE 的一種簡單方法是通過最大概似算法。為簡單起見假設 $ q $ 是多項式並且誤差分佈是正態的，如上所述。那麼，不難證明，經過約 $ O(n) $ 方程，唯一的分配給 $ s $ “大約滿足”方程是正確的。這可以通過基於 Chernoff 界限和聯合界限的標準參數來證明 $ s\in\mathbb{Z}_q^n $ . 這導致算法只使用 $ O(n) $ 採樣，並及時執行 $ 2^{O(n \log n)} $ . 作為推論，我們得到 LWE 是“定義明確的”，即解的機率很高 $ s $ 是唯一的，假設方程的數量是 $ \Omega(n) $ .
從不同的角度看待 LWE 也可能很有用——即作為 SIS 的參數範圍，其中先驗地不清楚解決方案是否應該存在，所以一個“植物”一個。有關這些方面的一些觀點，請參閱這些註釋。請注意，對於標準 SIS，存在許多解決方案的機率很高，因此如果不小心，“LWE = 決策 SIS（在某些參數範圍內）”很容易被混淆，例如看這個問題。