×

Cryptanalysis of the HFE public key cryptosystem by relinearization. (English) Zbl 0940.94012

Wiener, Michael (ed.), Advances in cryptology - CRYPTO ’99. 19th annual international cryptology conference Santa Barbara, CA, USA, August 15-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1666, 19-30 (1999).
Summary: The RSA public key cryptosystem is based on a single modular equation in one variable. A natural generalization of this approach is to consider systems of several modular equations in several variables. In this paper we consider Patarin’s hidden field equations scheme (HFE), which is believed to be one of the strongest schemes of this type [J. Patarin, Eurocrypt 96, Lect. Notes, Comput Sci. 1070, 33-48 (1996)]. 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 \(\varepsilon m^2\) quadratic equations in \(m\) variables over the extension field. Finally, we develop a new relinearization method for solving such systems for any constant \(\varepsilon> 0\) in expected polynomial time. The new type of attack is quite general, and in a companion paper we use it to attack other multivariate algebraic schemes such as the Dragon encryption and signature schemes. However, we would like to emphasize that the polynomial time complexities may be infeasibly large for some choices of the parameters, and thus some variants of these schemes may remain practically unbroken in spite of the new attack.
For the entire collection see [Zbl 0921.00042].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite