Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- HFEMultivariate CryptographyPublic Key CryptographyUltra-Short Signature.
- Contact author(s)
-
jpatarin @ club-internet fr
ejkoussa @ outlook com
maxime bros @ unilim fr
gilles macariorat @ orange com - History
- 2021-09-17: last of 4 revisions
- 2020-07-23: received
- See all versions
- Short URL
- https://ia.cr/2020/914
- License
-
CC BY