Abstract
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 (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 ∈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 ∈ > 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.
Chapter PDF
Similar content being viewed by others
References
D. Coppersmith, J. Stern and S. Vaudenay, The Security of the Birational Permutation Signature Scheme, Journal of Cryptology, 1997, pp. 207–221.
H. Fell and W. Diffe, Analysis of a Public Key Approach Based on Polynomial Substitution, Crypto 85, Springer Verlag, pp. 340–349.
A. Kipnis and A. Shamir, Cryptanalysis of the Oil and Vinegar Signature Scheme, Crypto 98, Springer Verlag, pp. 257–266.
N. Koblitz Algebraic Aspects of Cryptography, Springer Verlag, 1998.
T. Matsumoto and H. Imai, Public Quadratic Polynomial Tuples for Efficient Signature Verification and Message Encryption, Eurocrypt 88, Springer Verlag, pp. 419–453.
H. Ong, C. P. Schnorr, and A. Shamir A Fast Signature Scheme Based on Quadratic Equations, Proc. 16-th ACM Symp. Theory of Computation, 1984, pp. 208–216.
J. Patarin, Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt 88, Crypto 95, Springer Verlag, pp.248–261.
J. Patarin, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms, Eurocrypt 96, Springer Verlag, pp.33–48.
J. Patarin, Asymmetric Cryptography with a Hidden Monomial, Crypto 96, Springer Verlag, pp. 45–60.
J. Patarin, The Oil and Vinegar Algorithm for Signatures, presented at the Dagstuhl Workshop on Cryptography, September 97.
J. M. Pollard and C. P. Schnorr, An Efficient Solution of the Congruence x2 + ky2 = m(mod n), IEEE Trans. Information Theory, vol. IT-33, no. 5, 1987, pp. 702–709.
A. Shamir Efficient Signature Schemes Based on Birational Permutations, Crypto 93, Springer Verlag, pp.1–12.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kipnis, A., Shamir, A. (1999). Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. In: Wiener, M. (eds) Advances in Cryptology — CRYPTO’ 99. CRYPTO 1999. Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48405-1_2
Download citation
DOI: https://doi.org/10.1007/3-540-48405-1_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66347-8
Online ISBN: 978-3-540-48405-9
eBook Packages: Springer Book Archive
Keywords
- Quadratic Equation
- Signature Scheme
- Univariate Polynomial
- Multivariate Polynomial
- Multivariate Signature Scheme
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.