Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization

摘要: The RSA public key cryptosystem is based on a single modular equation in one variable. A natural generalization of this approach to consider systems several equations variables. In paper we Patarin's Hidden Field Equations (HFE) scheme, which believed be the strongest schemes type. We represent published system multivariate polynomials by univariate polynomial special form over an extension field, and use it reduce cryptanalytic problem Ɛm2 quadratic m variables field. Finally, develop new relinearization method for solving such any constant Ɛ > 0 expected time. type attack quite general, companion other algebraic schemes, as Dragon encryption signature schemes. However, would like emphasize that time complexities may infeasibly large some choices parameters, thus variants these remain practically unbroken spite attack.