抵抗量子傅立葉採樣攻擊的 McEliece 和 Niederreiter 密碼系統

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• 原文連結
• PDF 來源

論文資訊

• 類型：工作論文
• 編號：工作論文 #259
• 日期：2026-03-18

摘要

量子電腦可以破解 RSA、El Gamal 和橢圓曲線公鑰密碼系統，因為它們可以有效地分解整數並提取離散對數。這推動了後量子密碼系統的發展：可以用當今的電腦實現的經典密碼系統，即使在存在量子攻擊的情況下也能保持安全。在本文中，我們展示了基於理性 Goppa 代碼的 McEliece 密碼系統和基於經典 Goppa 代碼的 Niederreiter 密碼系統精確地抵抗了 RSA 和 El Gamal 密碼系統易受攻擊的攻擊，即基於生成和測量陪集狀態的攻擊。這消除了幾乎所有已知的量子演算法指數加速都基於的強傅立葉取樣方法。具體來說，我們表明 McEliece 型密碼系統歸約的隱藏子群問題的自然情況不能透過強傅立葉採樣或任何陪集狀態的測量來解決。為此，我們將圖同構量子演算法的最新負面結果擴展到線性碼自同構群的子群。這給出了 McEliece 型密碼系統在面對量子對手時的安全性的第一個嚴格結果，增強了它們作為後量子密碼學的候選資格。我們也強化了 Kempe、Pyber 和 Shalev 關於 S_n 中隱藏子群問題的一些結果。