隱藏體方程式之 Gröbner 基底改良攻擊法

Abstract

目前針對隱藏體系統之密碼系統最佳的攻擊法是 Gröbner 基底攻擊演算法，可快速解出由隱藏體系統的公鑰所建構的，定義在有限體上的⼆次多變數的多項式系統的解。 在此篇論文中，我們將陳述隱藏體系統的加解密結構，以及針對產生 Gröbner 基底的演算法，F4 演算法，做其運算結構之陳述。我們另外提出針對原始定義在 GF(2) 底下的 Gröbner 基底攻擊演算法的優化，並進一步使用空間優化來加速原始 F4 演算法的運算效能。

The current best attack to break the Hidden Field Equations (HFE) cryptosystem is known as the fast Gröbner basis computation, which can solve the quadratic multivariate polynomial systems over finite field formed from HFE’s public key. In this paper, we aim to reveal the structure of HFE and the flow of F4 algorithm which computes the Gröbner basis for the given polynomial system. We give an optimization for the Gröbner basis approach attack under GF(2), and use some space tradeoff to improve the performance of the original F4 algorithm to run faster.