小秘密LPN的硬度問題
帶有雜訊的學習奇偶校驗 (LPN) 假設指出，對於一個固定的秘密 $ s $ 從統一選擇 $ {0,1}^n $ ，然後是輸出的分佈 $ (a,a\cdot s+e) $ ， 在哪裡 $ a $ 是均勻的 $ {0,1}^n $ 和 $ e $ 根據伯努利分佈抽樣 $ \mathsf{Ber}_\tau $ （帶參數 $ \tau\in[0,1/2] $ )，是偽隨機的。
我的問題是：LPN 假設是否成立，即使 $ s $ 根據與誤差 相同的分佈進行選擇，即 $ \mathsf{Ber}_\tau^n $ ?
換句話說，給定 $ s $ 從 $ \mathsf{Ber}^n_\tau $ , 是分佈 $ (a,a\cdot s+e) $ 偽隨機？
有一個簡單的技巧（在 LWE 文獻中稱為問題的 Hermite 範式），它採用現有的 LPN 問題並將其轉換為秘密具有與錯誤相同的伯努利分佈的問題。Applebaum 等人的引理 2 證明了這個技巧。對於更一般的情況，或者關於Kirchner（第 4.3.2 節）或Bernstein 和 Lange（第 3 節）的 (Ring-)LPN 攻擊。
這個想法是你從一些 $ n $ 樣品 $ (\mathbf{a}i, c_i) $ ， 在哪裡 $ c_i = \mathbf{a}i \cdot \mathbf{s} $ . 現在假設， $ \mathbf{a}i $ 向量是線性獨立的（你不需要更多 $ n $ 隨機抽樣 $ \mathbf{a}i $ 對於這種情況），並讓它們形成矩陣 $ M = { \mathbf{a}{i_1}, \dots, \mathbf{a}{i_k}} $ . 然後我們有$$ \mathbf{c} = M^T\mathbf{s} + \mathbf{e}, $$在哪裡 $ \mathbf{c} = { c{i_1}, \dots, c{i_k}} $ 和 $ \mathbf{e} = { e_{i_1}, \dots, e_{i_k}} $ 是所選的對應向量 $ \mathbf{a}_i $ . 但我們也有$$ \mathbf{s} = {M^T}^{-1}(\mathbf{c} + \mathbf{e}). $$
現在我們有了這個矩陣 $ M $ ，用新樣本查詢 LPN 預言機 $ \mathbf{u} $ ， 接收 $ (\mathbf{u}, v = \mathbf{s}\cdot \mathbf{u} + e) $ . 但是您可以將其轉換為返回的第二個預言機 $ (M^{-1}\mathbf{u}, \mathbf{c}\cdot M^{-1}\mathbf{u} + v) $ . 明顯地， $ M(M^{-1}\mathbf{u}) = \mathbf{u} $ . 更遠， $$ \begin{align} \phantom{=} &\mathbf{e}\cdot M^{-1}\mathbf{u} + e \ = &(M^T\mathbf{s} + \mathbf{c})\cdot(M^{-1}\mathbf{u}) + e \ = &M^T\cdot\mathbf{s}\cdot M^{-1}\mathbf{u} + \mathbf{c}\cdot M^{-1}\mathbf{u} + e \ = &\mathbf{s}\cdot M M^{-1}\cdot u + \mathbf{c}\cdot M^{-1}\mathbf{u} + e \ = &\mathbf{c} \cdot M^{-1}\mathbf{u} + v. \end{align} $$所以這現在是一個具有伯努利分佈秘密的 LPN 實例 $ \mathbf{e} $ ，您可以從中提取原始秘密為 $ \mathbf{s} = {M^T}^{-1}(\mathbf{c} + \mathbf{e}) $ .
換句話說，給定一些使用伯努利分佈秘密求解 LPN 的算法，您也可以求解具有相同誤差分佈的正常 LPN。