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

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