McEliece 使用非二進制 Goppa 程式碼是否安全？
具有長度碼字的二進制 Goppa 碼 $ n $ 可以修復的位 $ t $ 多項式錯誤 $ GF(2^m) $ 可以編碼 $ k = n - mt $ 位長數據。這是一個需要添加 $ mt $ 檢查位以修復 $ t $ 位。這意味著最多 1/m 個碼字可以被錯誤填充。
另一方面，如果您在以下領域工作 $ GF(p) $ 在哪裡 $ p $ 是一些素數，要修復 $ t $ 您只需要添加錯誤的符號 $ 2t $ 更多符號（因為一般情況的多項式需要有兩倍的度數）。所以 $ k = n - 2t $ . 在最極端的情況下，程式碼字的一半可能是錯誤的。
如果我理解正確“資訊集解碼”依賴於找到一個 $ k $ 不包含錯誤的傳輸數據的符號長子集。所以這意味著能夠在消息中引入更多錯誤是一個優勢。似乎一般的 Goppa 程式碼在這方面做得更好。
我們使用二進制 Goppa 程式碼而不是通用 Goppa 程式碼有什麼特別的原因嗎？二進制程式碼能更好地抵御其他類型的攻擊嗎？
編輯：我也對程式碼多項式結束的情況感興趣 $ GF(2^m) $ ，但碼字的元素還沒有結束 $ GF(2) $ 但也結束了 $ GF(2^m) $ . 使用類似的欄位很誘人 $ GF(2^{16}) $ 因此矩陣和多項式元素由“短字”表示，並且省略了到位的轉換部分，因此我們可以在單個欄位中完成所有工作，生成矩陣的元素也是短字。並且輸入也被處理為 2 字節批次：更容易和更快的矢量化實現是可能的。
編輯2：
在資訊集解碼中，我們正在尋找密文中沒有錯誤的子集。在一個 $ [n, k, t] $ 程式碼。我們可以選擇k個元素 $ {n \choose k} $ 方式和可能的正確猜測的數量是 $ {n-t \choose k} $ . 所以偶然發現無錯誤序列的機會是 $ {n-t \choose k}/{n \choose k} $ .
現在讓我們使用通用的 Goppa 程式碼 $ GF(1021) $ . 讓 $ n = 725 $ , $ t = 145 $ 和 $ k = 725 - 2*145 = 435 $
所以計算 $ {725-145 \choose 435}/{725 \choose 435} \approx 6.953 \cdot 10^{-71} $ . 這是關於 $ 2^{-233} $ . 所以 233 位的安全性。
中的元素 $ GF(1021) $ 可以用 10 位表示，給我們一個 3153750 位或大約 400kB 的密鑰大小。
使用二進制 Goppa 程式碼需要更多檢查符號。考慮擴展欄位上的程式碼 $ GF(2^{13}) $ 帶參數 $ n = 5600 $ , $ t = 172 $ ， 所以 $ k = 3364 $ $ {5600-172 \choose 3364}/{5600 \choose 3364} \approx 4.373 \cdot 10^{-71} $ . 對於類似的安全級別。但是矩陣現在大於 2 MB。
因此我的問題。
問題是您僅指的是普通資訊集解碼。事實上，對於普通的 ISD，攻擊 Goppa 程式碼的複雜性 $ \mathbb F_q $ 將按預期進行擴展 $ q $ .
然而，Stern 的 ISD 算法並不僅僅與程式碼大小有關。
遵循幾何分佈，我們可以將 ISD 算法的預期成本表示為
$$ \mathbb E [\text{cost}] = \frac{\text{cost of one iteration}}{\mathbb P [\text{successful iteration}]}\text. $$
對於 Stern 算法，給定參數 $ p $ 和 $ 0 \le p \le w $ （在哪裡 $ w $ 是誤差向量的權重）和 $ l $ 和 $ 0 \le l \le n - k $ ,
- 成功迭代的機率不直接取決於 $ q $ 並且可以表示為 $ n $ , $ k $ , $ w $ , $ l $ 和 $ p $ .
- 一次迭代的成本是 $$ (n - k)^2 (n + k) + ((\kappa - p + 1) + 2 N {(q - 1)}^p)l + \frac{q}{q - 1} (w - 2p + 1) 2p (1 + \frac{q - 2}{q - 1}) \frac{N^2 {(q - 1)}^{2p}}{q^l}\text, $$ 在哪裡 $ \kappa = k / {2} $ 和 $ N = \binom{k / {2}}{p} $ .
如您所見，算法的擴展方式 $ q $ 很大程度上取決於參數 $ p $ 和 $ l $ . 所以， $ p $ 通常選擇非常小以最小化經過太多子集的影響（ $ {(q - 1)}^p $ 和 $ {(q - 1)}^{2p} $ 條款）。
請參閱 Christiane Peters 的論文，其中有一整章專門討論這一點。它還討論了額外的改進並提出了準確的值 $ p $ 和 $ l $ .
當然，也有 Goppa 碼 $ \mathbb F_q $ 這樣的密碼系統將是安全的。你也可以在論文中找到一些建議和分析。