解佈於二元體之多項式方程組之快速窮舉法

Fast Exhaustive Search for Polynomial Systems over F2

周彤(Tung Chou)

指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.01494

摘要

解多變量系統的問題在許多領域，包含代數攻擊和多變量密碼學，都具有重要的地位。然而，現存的演算法如 F4/F5 和 XL 雖然對於具有某些特性的系統效果特別顯著，但在面對一般的系統時，通常都無法有效率地解決問題，甚至會帶來嚴重的記憶體匱乏的問題。

基於上述的理由，我們便開始尋求另一個適合一般系統的解決方案，也就是窮舉搜尋 (exhaustive search) 的方式。在這篇論文中，我們提出並深入研究了一個窮舉搜尋的演算法 GGCE (generalized Gray code enumeration)，用以解佈於二元體的多項式系統。這個演算法不僅相當易於平行化，對於解低次數的系統也有非常好的表現。對於這個演算法理論上的效能和記憶體需求等重要議題，在之後也會有深入的分析。

以實際面而言，我們將 GGCE 實作於顯示卡及 CPU 上。經過適當的最佳化之後，我們發現 GGCE 不僅在理論上相當有效率，實際的表現甚至遠勝過現有的演算法。換句話說，在面對一般系統時，窮舉搜尋可能是最好的解法。

簡而言之，我們提出了一個不同於以往的策略來解多變量系統。GGCE 證明了窮舉搜尋本身的強大能力，對於需要解多變量系統的眾多領域，勢必也會產生相當的影響。

關鍵字

顯示卡 ； 代數攻擊 ； 多變量密碼學 ； 窮舉搜尋 ； 平行化

並列摘要

無資料

並列關鍵字

algebraic cryptanalysis ； multivariate cryptography ； multivariate polynomials ； solving systems of equations ； exhaustive search ； parallelization ； CUDA ； Graphic Processing Units (GPUs)

參考文獻

[6] M. Bardet, J.-C. Faugère, B. Salvy, and B.-Y. Yang. Asymptotic expansion

[8] D. J. Bernstein, T.-R. Chen, C.-M. Cheng, T. Lange, and B.-Y. Yang. ECM

[1] B.-Y. Yang and J.-M. Chen All in the XL Family: Theory and Practice. Proc.

3506, Lecture Notes in Computer Science, pages 67-86, 2004.

edition, 2009.