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
[ Cryptology ePrint archive ]