Cryptology ePrint Archive: Report 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 !

Category / Keywords: public-key cryptography / digital signatures, provable security, short signatures, multivariate cryptography, HFE, Quartz, Sflash, algebraic attacks, multivariate polynomial equations, Grobner bases

Date: received 17 Jun 2004, last revised 15 Jun 2005

Contact author: courtois at minrank org

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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.

Version: 20050615:164807 (All versions of this report)

Discussion forum: Show discussion | Start new discussion