eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2009/619

A Family of Weak Keys in HFE (and the Corresponding Practical Key-Recovery)

Charles Bouillaguet, Pierre-Alain Fouque, Antoine Joux, and Joana Treger

Abstract

The HFE (Hidden Field Equations) cryptosystem is one of the most interesting public-key multivariate scheme. It has been proposed more than 10 years ago by Patarin and seems to withstand the attacks that break many other multivariate schemes, since only subexponential ones have been proposed. The public key is a system of quadratic equations in many variables. These equations are generated from the composition of the secret elements: two linear mappings and a polynomial of small degree over an extension field. In this paper we show that there exist weak keys in HFE when the coefficients of the internal polynomial are defined in the ground field. In this case, we reduce the secret key recovery problem to an instance of the Isomorphism of Polynomials (IP) problem between the equations of the public key and themselves. Even though for schemes such as SFLASH or $C^*$ the hardness of key-recovery relies on the hardness of the IP problem, this is normally not the case for HFE, since the internal polynomial is kept secret. However, when a weak key is used, we show how to recover all the components of the secret key in practical time, given a solution to an instance of the IP problem. This breaks in particular a variant of HFE proposed by Patarin to reduce the size of the public key and called the ``subfield variant''.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Cryptanalysismultivariate cryptographyHFEweak keysGröbner Bases
Contact author(s)
charles bouillaguet @ ens fr
History
2009-12-17: received
Short URL
https://ia.cr/2009/619
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/619,
      author = {Charles Bouillaguet and Pierre-Alain Fouque and Antoine Joux and Joana Treger},
      title = {A Family of Weak Keys in HFE (and the Corresponding Practical Key-Recovery)},
      howpublished = {Cryptology ePrint Archive, Paper 2009/619},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/619}},
      url = {https://eprint.iacr.org/2009/619}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.