Paper 2011/399

Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic

Luk Bettale, Jean-Charles Faugère, and Ludovic Perret

Abstract

We investigate in this paper the security of HFE and Multi-HFE schemes as well as their minus and embedding variants. Multi-HFE is a generalization of the well-known HFE schemes. The idea is to use a multivariate quadratic system -- instead of a univariate polynomial in HFE -- over an extension field as a private key. According to the authors, this should make the classical direct algebraic (message-recovery) attack proposed by Faugère and Joux on HFE no longer efficient against Multi-HFE. We consider here the hardness of the key-recovery in Multi-HFE and its variants, but also in HFE (both for odd and even characteristic). We first improve and generalize the basic key recovery proposed by Kipnis and Shamir on HFE. To do so, we express this attack as matrix/vector operations. In one hand, this permits to improve the basic Kipnis-Shamir (KS) attack on HFE. On the other hand, this allows to generalize the attack on Multi-HFE. Due to its structure, we prove that a Multi-HFE scheme has much more equivalent keys than a basic HFE. This induces a structural weakness which can be exploited to adapt the KS attack against classical modifiers of multivariate schemes such as minus and embedding. Along the way, we discovered that the KS attack as initially described cannot be applied against HFE in characteristic 2. We have then strongly revised KS in characteristic 2 to make it work. In all cases, the cost of our attacks is related to the complexity of solving MinRank. Thanks to recent complexity results on this problem, we prove that our attack is polynomial in the degree of the extension field for all possible practical settings used in HFE and Multi-HFE. This makes then Multi-HFE less secure than basic HFE for equally-sized keys. As a proof of concept, we have been able to practically break the most conservative proposed parameters of multi-HFE in few days (256 bits security broken in 9 days).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Extended version of PKC 2011 Paper
Keywords
HFEMinRankGröbner bases
Contact author(s)
luk bettale @ lip6 fr
History
2011-07-28: received
Short URL
https://ia.cr/2011/399
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/399,
      author = {Luk Bettale and Jean-Charles Faugère and Ludovic Perret},
      title = {Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic},
      howpublished = {Cryptology ePrint Archive, Paper 2011/399},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/399}},
      url = {https://eprint.iacr.org/2011/399}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.