量化暴力攻擊（搜尋）LPN的成功機率
我一直在嘗試了解對 LPN 的攻擊（ $ n $ -位秘密，雜訊率 $ \eta $ )，並且已經發現了幾個對蠻力算法的暗示，該算法在時間指數中執行 $ n $ 並且需要線性數量的樣本 $ n $ . 例如，本套牌的第三張幻燈片或原始BKW 論文。也就是說，我無法找到該算法的成功機率，也無法自己推導它。
LPN挑戰者：
- 初始化時，隨機選擇 $ s \in \mathbb{Z}_2^n $
- 查詢時，選擇隨機 $ a \in \mathbb{Z}_2^n $ , 計算 $ c = a \cdot s \mod{2} $ 並返回真 $ (a, c) $ 有機率 $ 1 - \eta $ ，或損壞的 $ (a, 1 \oplus c) $ 有機率 $ \eta $ .
蠻力算法：
- 向 LPN 挑戰者查詢 $ m $ 標記樣本 $ (x_1, l_1),…,(x_m, l_m) \in \mathbb{Z}_2^n \times \mathbb{Z}_2 $
- 對於每個潛在的秘密 $ s_j \in \mathbb{Z}2^n $ , 計算經驗錯誤率 $ r_j = (1/m) (\sum{i=1}^m (x_i \cdot s_j) + l_i \mod{2}) $ （注意總和的每一項都是計算出來的 $ \mod{2} $ 但總和本身是通過整數計算的）
- 輸出潛在秘密 $ s_t $ 具有經驗錯誤率 $ r_t $ 最接近雜訊率 $ \eta $ （IE $ t = arg,min_t \lvert r_t - \eta \rvert $ )
直覺地說，這個算法似乎應該成功的機率明顯優於普通算法 $ \frac{1}{2^n} $ 隨機猜測的機率。但我不確定如何在這裡量化成功機率。任何指向文獻或直接答案的指針表示讚賞。
**編輯：**我不是 100% 肯定蠻力的最後一步實際上是文獻中引用的算法，因為我看到使用的片語是“檢查哪個 s 是最合適的”和“找到最不經驗的錯誤”。因此，如果我對蠻力算法描述有誤，請告訴我。
如果我們簡單地選擇得分最低的秘密（這也是最大概似解釋），這是最簡單的。在這種情況下，我可以寫下繁瑣的精確表達式，然後就是你可能喜歡使用哪種近似值的問題。讓我們省去 $ 1/m $ 分數的因素。
精確表達
請注意，對於因果解決方案 $ s_t $ 分數 $ r_t $ 是分佈式的 $ \mathrm{Bin}(m,\eta) $ . 我們還注意到，只有當因果解決方案的分數大於非因果分數的最大值時，測試才有可能成功。應分配非因果分數 $ \mathrm{Bin}(m,0.5) $ 以及其中一個小於或等於某個界限的機會 $ r $ 是（誰）給的 $ F(r;m,0.5) $ 在哪裡 $ F $ 是二項式累積分佈函式。因此，所有的機會 $ 2^n-1 $ 非因果答案大於 $ r $ 是（誰）給的 $$ (1-F(r;m,0.5))^{2^n-1}. $$
對可能的值求和 $ r_t $ 我們看到因果分數大於所有非因果分數的機率由下式給出 $$ \sum_{r=1}^m\left(1-F(r;m,0.5)\right)^{2^n-1}\left({m\atop r}\right)\eta^r(1-\eta)^{m-r}. $$
近似值和界限
$ F $ 計算起來很麻煩，因此您可能希望使用Chernoff 或 Hoeffding bounds來近似它。這也不是世界上最糟糕的計劃，將上述總和從下方限制為 $ r_t $ 小於或等於某個固定界限 $ r $ （由 $ F(r;m,\eta) $ ) 乘以非因果分數的最小值大於相同固定界限的機率 $ r $ ： $$ \left(1-F(r;m,0.5)\right)^{2^n-1}F(r;m,\eta). $$ 一個不錯的選擇 $ r $ 在這種情況下可能是 $ r\approx\eta m-2\sqrt{m\eta(1-\eta)} $ 以便 $ F(r;m,\eta)\approx 0.95 $ 或者乾脆 $ r\approx(1-\eta)m $ 以便 $ F(r;m,\eta)\approx 0.5 $ .