Paper 2002/138

On the Security of HFE, HFEv- and Quartz

Nicolas T. Courtois, Magnus Daum, and Patrick Felke

Abstract

Quartz is a signature scheme based on an HFEv- trapdoor function published at Eurocrypt 1996. In this paper we study "inversion" attacks for Quartz, i.e. attacks that solve the system of multivariate equations used in Quartz. We do not cover some special attacks that forge signatures without inversion. We are interested in methods to invert the HFEv- trapdoor function or at least to distinguish it from a random system of the same size. There are 4 types of attacks known on HFE: Shamir-Kipnis, Shamir-Kipnis-Courtois, Courtois, and attacks related to Gröbner bases such as the F5/2 attack by Jean Charles Faugère. No attack has been published so far on HFEv- and it was believed to be more secure than HFE. In this paper we show that even modified HFE systems can be successfully attacked. It seems that the complexity of the attack increases by at least a factor of $q^{tot}$ with $tot$ being the total number of perturbations in HFE. From this and all the other known attacks we will estimate what is the complexity of the best "inversion" attack for Quartz.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. -
Keywords
asymmetric cryptographyfinite fieldsmultivariate cryptanalysisGröbner basesHidden Field EquationHFE problemQuartzNessie project
Contact author(s)
Magnus Daum @ ruhr-uni-bochum de
History
2002-09-17: revised
2002-09-12: received
See all versions
Short URL
https://ia.cr/2002/138
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/138,
      author = {Nicolas T.  Courtois and Magnus Daum and Patrick Felke},
      title = {On the Security of HFE, HFEv- and Quartz},
      howpublished = {Cryptology ePrint Archive, Paper 2002/138},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/138}},
      url = {https://eprint.iacr.org/2002/138}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.