我們可以使用 Arora-Ge 算法解決 LPN 問題嗎？
我最近研究瞭如何使用 Arora 和 Ge 提出的代數關係來解決 LWE（錯誤學習）（論文：New Algorithms for Learning in Presence of Errors）。據我了解，對於表單的 LWE 實例 $ \vec{a}_i,b_i = <\vec{a}_i,\vec{s}>+e_i~mod~q $ 對於某個整數 $ q $ , 對手生成具有根的代數多項式 $ e_i = b_i - <\vec{a}_i,\vec{s}>~mod~q $ . 如果對手獲得足夠多的多項式，那麼他們可以恢復秘密向量 $ \vec{s} $ 使用線性化技術。
因此，我認為 Arora-Ge 算法也可以解決 LPN（學習有雜訊的奇偶校驗）問題，因為實例的形式為 $ \vec{a}_i,b_i = <\vec{a}_i,\vec{s}>+e_i~mod~2 $ . 但是，我找不到任何關於結果的參考，所以我想我有一些錯誤。
為什麼我不能使用 Arora-Ge 算法求解 LPN？
很自然地想知道 Arora-Ge 是否可以打破 LPN，但正如您所懷疑的那樣，它不起作用。本質問題是，因為模數是 $ q=2 $ , 該方法沒有找到唯一解 $ s $ ，它甚至也沒有縮小可能的解決方案的範圍。
原因是算法的第一步是將每個 LPN 樣本轉換為二次（在 $ s $ ) 編碼條件的方程 $ \langle a_i, s \rangle = b_i \text{ or } b_i +1 \pmod{2} $ . 然後它將這些方程線性化並求解 $ s $ . 但是，請注意任何 $ s’ $ 是這些方程的解，因為右邊總是“0 或 1”。因此，算法建立的系統不攜帶任何關於 $ s $ ，從一開始。
Arora-Ge 適用於 LWE 因為/當模量 $ q $ 大於可能的錯誤值的數量。那麼，條件“ $ \langle a_i, s \rangle = b_i \text{ or } b_i+1 \text{ or } b_i-1 \ldots $ ” 擷取對秘密的重要約束 $ s $ ，並且足夠多的這樣的方程可以唯一地指定它。