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 signaturesprovable securityshort signaturesmultivariate cryptographyHFEQuartzSflashalgebraic attacksmultivariate polynomial equationsGrobner 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2004/143}},
      url = {https://eprint.iacr.org/2004/143}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.