Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as HFE, Quartz and Sflash

Nicolas T.  Courtois

Paper 2004/143

Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as HFE, Quartz and Sflash

Nicolas T. Courtois

Abstract

This paper should be considered as a draft. Part of it is an extended version of the paper Generic Attacks and the Security of Quartz presented at PKC 2003 and at the second Nessie workshop. It also contains a lot of new material that is not published elsewhere: -(yet another) discussion about what is and what isn't a secure signature scheme -up-to-date security results fo Sflash and Quartz -new results on computational security of Sflash w.r.t algebraic relation attacks in the light of Faugère-Joux Crypto 2003 paper. -and more... Comments are welcome !

Note: On the margin of this paper: The recent HFE paper by Faugère and Joux heavily misrepresents the actual state of contributions, regarding the security of HFE systems. All the attacks Faugère et al. attribute to themselves, were already known and published in not less than 5 previously published papers (!), by Patarin himself, Shamir and Kipnis, Courtois, Daum and Felke. The details are found in Section 8.2. of this draft.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: digital signatures provable security short signatures multivariate cryptography HFE Quartz Sflash algebraic attacks multivariate polynomial equations Grobner bases
Contact author(s): courtois @ minrank org
History: 2005-06-15: last of 3 revisions; 2004-06-18: received; See all versions
Short URL: https://ia.cr/2004/143
License: CC BY

BibTeX

@misc{cryptoeprint:2004/143,
      author = {Nicolas T.  Courtois},
      title = {Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as {HFE}, Quartz and Sflash},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/143},
      year = {2004},
      url = {https://eprint.iacr.org/2004/143}
}