Cryptology ePrint Archive: Report 2020/914

Ultra-Short Multivariate Public Key Signatures

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

Abstract: In this paper we study multivariate public key signature schemes with "ultra"-short signatures. In order to do so, we consider that signing and verifying a signature could require up to 1 minute of computation on a modern personal computer. Of course, very close results would be obtained for times around one second, at the cost of 6 to 10 more bits in the signatures, and more generally a trade-off could be found between computation time and signature size at each security level. Despite the fact that a time of one minute is way bigger than the time required by general purpose multivariate-based signature schemes, such as Quartz or GeMMS, it enables us to reach ultra-short signature lengths, for instance, around 70 bits long signatures for a security of 80 bits. Two main issues arise when one wants to build a signature scheme with ultra-short signatures: avoiding the birthday paradox attack and having the ability to sign arbitraly long messages, this paper gives ways to overcome both. In a first part, we describe the attacks against multivariate public key signatures and use them to compute the minimal parameters that an ultra-short signature scheme would have. In a second part, we give an explicit example of such an ultra-short signature scheme using HFE-like algorithms. In the end, we give parameters for several level of security: 80, 90, 100 bits and the classic 128, 192, and 256 bits; for each of them, we propose different choices of finite fields.

Category / Keywords: public-key cryptography / HFE, Multivariate Cryptography, Public Key Cryptography, Ultra-Short Signature.

Date: received 22 Jul 2020, last revised 9 Sep 2020

Contact author: jpatarin at club-internet fr , ejkoussa@outlook com , maxime bros@unilim fr , gilles macariorat@orange com

Available format(s): PDF | BibTeX Citation

Version: 20200909:134518 (All versions of this report)

Short URL: ia.cr/2020/914