Paper 2020/914

Ultra-Short Multivariate Public Key Signatures

Jacques Patarin, Gilles Macario-Rat, Maxime Bros, and Eliane Koussa


In this paper, we study and construct multivariate schemes with “ultra-short” signatures. We focus on the classic case where the public key is a set of multivariate polynomials of degree 2. To design ultra-short signature schemes, we consider that signing a message and verifying a signature could require up to 1 minute of computation on a modern personal computer. Shorter time could be considered but at the cost of a few additional bits in the signatures, more generally, a trade-off may be found between computation time and signature size, depending on the applications one is targeting. Despite the fact that a time of 1 minute is far bigger than the time required by general purpose multivariate-based signature schemes, such as Rainbow, GeMMS, and Quartz, it enables us to reach ultra-short signature lengths; for instance, around 70 bit-long signatures for a security of 80 bits. In a first part, we describe generic and specific attacks against multivariate public key signature schemes and use them to derive the minimal parameters that an ultra-short signature scheme could have. In a second part, we give explicit ultra-short signature schemes with security in 80, 90 and 100 bits. In order to construct these signatures scheme, we use “nude HFE” (i.e. the classic HFE algorithm, without perturbations) and the new projection HFE algorithm described in [18]. Recent progress has been made on attacking the MinRank problem, which is strongly connected to HFE, in [2], and on attacking HFEv- ;in [24]. These potential threats against multivariate signature schemes have been taken into account in this paper.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
HFEMultivariate CryptographyPublic Key CryptographyUltra-Short Signature.
Contact author(s)
jpatarin @ club-internet fr
ejkoussa @ outlook com
maxime bros @ unilim fr
gilles macariorat @ orange com
2021-09-17: last of 4 revisions
2020-07-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jacques Patarin and Gilles Macario-Rat and Maxime Bros and Eliane Koussa},
      title = {Ultra-Short Multivariate Public Key Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2020/914},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.