Cryptanalysis of the HFE Public Key Cryptosystem


Published: Apr 04, 2000 Updated: Apr 04, 2000 Section: Network Security Library :: Cryptography Author: Printable Version Adjust font size: Rating: 3/5 - 4 Votes 1 2 3 4 5

In this paper we consider Patarin's Hidden Field Equations (HFE) scheme, which is believed to be one of the strongest schemes of this type. We represent the published system of multivariate polynomials by a single univariate polynomial of a special form over an extension field, and use it to reduce the cryptanalytic problem to a system of em^2 quadratic equations in m variables over the extension field. Finally, we develop a new relinearization method for solving such systems for any constant epsilon > 0 in expected polynomial time.

Click Here to download this article