UOV-Pepper:  New Public Key Short Signature   in Degree 3

Gilles Macario-Rat; Jacques Patarin

Paper 2021/1006

UOV-Pepper: New Public Key Short Signature in Degree 3

Gilles Macario-Rat and Jacques Patarin

Abstract

In this paper, we present a new perturbation for the design of multivariate schemes that we call ``Pepper''. From this idea, we present some efficient multivariate signature schemes with explicit parameters that resist all known attacks. In particular they resist the two main (and often very powerful) attacks in this area: the Gröbner attacks (to compute a solution of the system derived from the public key) and the MinRank attacks (to recover the secret key). Pepper can also be seen as a new perturbation that can be used to strengthen many other multivariate schemes. The ``Pepper'' perturbation works only for public key equations of degree (at least) 3. Despite this, the size of the public key may still be reasonable since we can use larger fields (and also maybe non dense equations). Furthermore, the size of the signatures can be very short.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: public-key cryptography post-quantum multivariate cryptography UOV HFE
Contact author(s): gilles macariorat @ orange com
jpatarin @ club-internet fr
History: 2021-08-03: received
Short URL: https://ia.cr/2021/1006
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1006,
      author = {Gilles Macario-Rat and Jacques Patarin},
      title = {{UOV}-Pepper:  New Public Key Short Signature   in Degree 3},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1006},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1006}
}