Options
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 證明了窮舉搜尋本身的強大能力,對於需要解多變量系統的眾多領域,勢必也會產生相當的影響。
基於上述的理由,我們便開始尋求另一個適合一般系統的解決方案,也就是窮舉搜尋 (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)
No Thumbnail Available
Name
ntu-99-R97921069-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):2d5d8165b90909312e30b3f6c6b35bdc