A Study of Key Problems of HFE Cryptosystem

The design and analysis of multivariate cryptosystems play an important role in theory research and practical use. The HFE cryptosystem presented by Jacques Patarin in 1996 has long been regarded as the most promising one of multivariate cryptosystems, and is a promising public key cryptosystem with many practical applications: very fast or very short digital signatures, fast public key encryption, etc. The security of the HFE cryptosystem is based on the problem of solving a system of multivariate quadratic equations over a finite field F. The problems about keys, which haven't been investigated in detail in literature, are very important in the HFE cryptosystem. Nontrivial public key and nontrivial private key are defined. If a reversible linear mapping φ:K→Fn is given where K is an extension of degree n of the finite field F and char(F)=2, there are the corresponding qn(n+1)∏ni=1(q\+i-1)\+2 nontrivial private keys for per nontrivial public key. A conclusion that solving a system of m multivariate quadratic equations with n variants (m≤n) over F is reduced to finding root of polynomial equation over K. This result leads to a deeper understanding of HFE and may yield a new kind of attack. In addition, two categories of weak keys on the HFE cryptosystem over F are introduced.