Fast Exhaustive Search for Polynomial Systems over F2
Date Issued
2010
Date
2010
Author(s)
Chou, Tung
Abstract
解多變量系統的問題在許多領域，包含代數攻擊和多變量密碼學，都具有重要的地位。然而，現存的演算法如 F4/F5 和 XL 雖然對於具有某些特性的系統效果特別顯著，但在面對一般的系統時，通常都無法有效率地解決問題，甚至會帶來嚴重的記憶體匱乏的問題。
基於上述的理由，我們便開始尋求另一個適合一般系統的解決方案，也就是窮舉搜尋 (exhaustive search) 的方式。在這篇論文中，我們提出並深入研究了一個窮舉搜尋的演算法 GGCE (generalized Gray code enumeration)，用以解佈於二元體的多項式系統。這個演算法不僅相當易於平行化，對於解低次數的系統也有非常好的表現。對於這個演算法理論上的效能和記憶體需求等重要議題，在之後也會有深入的分析。
以實際面而言，我們將 GGCE 實作於顯示卡及 CPU 上。經過適當的最佳化之後，我們發現 GGCE 不僅在理論上相當有效率，實際的表現甚至遠勝過現有的演算法。換句話說，在面對一般系統時，窮舉搜尋可能是最好的解法。
簡而言之，我們提出了一個不同於以往的策略來解多變量系統。GGCE 證明了窮舉搜尋本身的強大能力，對於需要解多變量系統的眾多領域，勢必也會產生相當的影響。
Subjects
algebraic cryptanalysis
multivariate cryptography
multivariate polynomials
solving systems of equations
exhaustive search
parallelization
CUDA
Graphic Processing Units (GPUs)
File(s)![Thumbnail Image]()
Loading...
Name
ntu-99-R97921069-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):2d5d8165b90909312e30b3f6c6b35bdc